Graph-based methods have been quite successful in solving unsupervised and semi-supervised learning problems, as they provide a means to capture the underlying geometry of the dataset. It is often desirable for the constructed graph to satisfy two properties: first, data points that are similar in the feature space should be strongly connected on the graph, and second, the class label information should vary smoothly with respect to the graph, where smoothness is measured using the spectral properties of the graph Laplacian matrix. Recent works have justified some of these smoothness conditions by showing that they are strongly linked to the semi-supervised smoothness assumption and its variants. In this work, we reinforce this connection by viewing the problem from a graph sampling theoretic perspective, where class indicator functions are treated as bandlimited graph signals (in the eigenvector basis of the graph Laplacian) and label prediction as a bandlimited reconstruction problem. Our approach involves analyzing the bandwidth of class indicator signals generated from statistical data models with separable and nonseparable classes. These models are quite general and mimic the nature of most real-world datasets. Our results show that in the asymptotic limit, the bandwidth of any class indicator is also closely related to the geometry of the dataset. This allows one to theoretically justify the assumption of bandlimitedness of class indicator signals, thereby providing a sampling theoretic interpretation of graph-based semi-supervised classification.

Current formulations of critically-sampled graph wavelet filterbanks work only for bipartite graphs where downsampling signals on either partition leads to a spectrum folding phenomenon. The lack of such a natural downsampling scheme for arbitrary graphs poses difficulties in designing filterbanks. In this paper, we propose a critical sampling scheme on an arbitrary graph that chooses a sampling set for each channel, given a set of analysis/synthesis filters, by seeking to minimize a bound on the overall reconstruction error associated with the filterbank. Our algorithm is efficient since it requires a few simple graph filtering operations in each iteration. Our initial experiments show that its output is consistent with the sampling scheme for bipartite graphs and results in superior performance over other methods.

Image restoration schemes have traditionally been targeted only for use in a blind scenario, where the aim is to improve the quality of an image or video after it has suffered degradations in capture, processing, storage, coding or transmission, at a time when the undegraded source is no longer available. However, these schemes can also be adopted for compression, because any information that can be restored can be saved, thereby aiding compressibility. In this use case, the source is known at the time of compression, and the encoder can send additional side-information to the decoder with the compressed bit-stream to specify how the decoder is supposed to restore. In this paper, we describe three novel schemes that are applied in-loop to reconstructed frames after a conventional deblocking loop filter has been applied. These schemes are switchable within a frame per suitably sized tile. The specific schemes described are based on separable symmetric Wiener filters, dual self-guided filters with subspace projection, and domain transform recursive filters. Results with the new coding tool are presented on the emerging AV1 video codec on standard test sets, showing upwards of 2% bit-rate savings.

The advent of advanced acquisition techniques in 3D media applications has led to an increasing trend of capturing dynamic objects and scenes via 3D point cloud sequences. This form of data is composed of time-indexed frames, each consisting of a collection of points with position and color attributes. Compression of such datasets is challenging because of the lack of efficient techniques for exploiting spatial and temporal correlations between the attributes. In our approach, we create an intermediate high-resolution representation of the point clouds, using consistent subdivisional triangular meshes, that captures all the features of the underlying object or scene. This representation is easy to obtain, significantly simplifies motion compensation and allows us to design efficient wavelet transforms using the recently developed framework of Biorthogonal Graph Wavelet Filterbanks. Preliminary experiments show that our approach can be an effective compression technique for 3D point cloud sequences.

Graph-based methods play an important role in unsupervised and semi-supervised learning tasks by taking into account the underlying geometry of the data set. In this paper, we consider a statistical setting for semi-supervised learning and provide a formal justification of the recently introduced framework of bandlimited interpolation of graph signals. Our analysis leads to the interpretation that, given enough labeled data, this method is very closely related to a constrained low density separation problem as the number of data points tends to infinity. We demonstrate the practical utility of our results through simple experiments.

In this paper, we extend the Nyquist-Shannon theory of sampling to signals defined on arbitrary graphs. Using spectral graph theory, we establish a cut-off frequency for all bandlimited graph signals that can be perfectly reconstructed from samples on a given subset of nodes. The result is analogous to the concept of Nyquist frequency in traditional signal processing. We consider practical ways of computing this cut-off and show that it is an improvement over previous results. We also propose a greedy algorithm to search for the smallest possible sampling set that guarantees unique recovery for a signal of given bandwidth. The efficacy of these results is verified through simple examples.

We consider the problem of offline, pool-based active semi-supervised learning on graphs. This problem is important when the labeled data is scarce and expensive whereas unlabeled data is easily available. The data points are represented by the vertices of an undirected graph with the similarity between them captured by the edge weights. Given a target number of nodes to label, the goal is to choose those nodes that are most informative and then predict the unknown labels. We propose a novel framework for this problem based on our recent results on sampling theory for graph signals. A graph signal is a real-valued function defined on each node of the graph. A notion of frequency for such signals can be defined using the spectrum of the graph Laplacian matrix. The sampling theory for graph signals aims to extend the traditional Nyquist-Shannon sampling theory by allowing us to identify the class of graph signals that can be reconstructed from their values on a subset of vertices. This approach allows us to define a criterion for active learning based on sampling set selection which aims at maximizing the frequency of the signals that can be reconstructed from their samples on the set. Experiments show the effectiveness of our method.