Nowadays, more and more data natively “live” on the vertices of a graph: brain activity supported by neurons in networks, traffic on transport and energy networks, data from users of social media, complex 3D surfaces describing real objects… Although graphs have been extensively studied in mathematics and computer science, a “signal processing” viewpoint on these objects remains largely to be invented. As such, “signal processing on graphs” (SPG) is an emerging topic, that has already lead to pioneering theoretical and practical work to formalize foundational definitions and tools. This has opened the path to many exciting future research, calling to revisit most of the usual signal processing tasks (filtering, denoising, compression, etc.).
Wavelets on graphs. Among signal processing tools, transforms naturally play a key role in modelling data. Thanks to spectral graph theory, a Fourier transform can be defined on graphs from the eigen decomposition of the graph’s Laplacian operator. Various wavelet transforms can also be defined on graphs, and the teams involved in this proposal have pioneered the design of wavelet transforms on graphs using spectral graph theory. Fourier or wavelet transforms on graphs allow the extension of notions such as the smoothness of a signal. More generally they open the door to using the extensive toolset of sparse signal models that, in recent years, have achieved tremendous success in solving large classes of inverse problems with guaranteed performances and efficient algorithms based on convex optimization. Transposed to general graph data, this leads to applications as diverse as community detection, recommender systems, or matrix completion on graphs.
Sampling k-bandlimited signals on graphs . Leveraging ideas from compressive sensing, it is possible to design efficient sampling strategies for low-pass signals on graphs. We propose two such sampling strategies that consist in selecting a small subset of nodes at random. The first strategy is non-adaptive, i.e., independent of the graph structure, and its performance depends on a parameter called the graph coherence. On the contrary, the second strategy is adaptive but yields optimal results. Indeed, no more than O(k log(k)) measurements are sufficient to ensure an accurate and stable recovery of all k-bandlimited signals. This second strategy is based on a careful choice of the sampling distribution, which can be estimated quickly. Then, we propose a computationally efficient decoder to reconstruct k-bandlimited signals from their samples. We prove that it yields accurate reconstructions and that it is also stable to noise. Finally, we conduct several experiments to test these techniques.
Compressive spectral clustering. Building upon recent advances in graph signal processing, one can propose a faster spectral clustering algorithm. Indeed, classical spectral clustering is based on the computation of the first k eigenvectors of the similarity matrix’ Laplacian, whose computation cost, even for sparse matrices, becomes prohibitive for large datasets. We show that we can estimate the spectral clustering distance matrix without computing these eigenvectors: by graph filtering random signals. Also, we take advantage of the stochasticity of these random vectors to estimate the number of clusters k. We compare our method to classical spectral clustering on synthetic data, and show that it reaches equal performance while being faster by a factor at least two for large datasets.
Fast Graph Fourier Transforms ? Many graph signal processing tools rely on the Graph Fourier transform, but a Fast Graph Fourier Transform is generally lacking. Leveraging the recently introduced Flexible Approximate MUlti-layer Sparse Transforms (FAµST) we propose to compute approximate FFTs on graphs. The approach is validated on several types of classical graphs and finally used for fast filtering, showing good potential .
