Accelerated filtering on graphs using Lanczos method

By Ana Susnjara, Nathanael Perraudin, Daniel Kressner, Pierre Vandergheynst. 2015

61 citations recorded by the source corpus.

Signal-processing on graphs has developed into a very active field of research during the last decade. In particular, the number of applications using frames constructed from graphs, like wavelets on graphs, has substantially increased. To attain scalability for large graphs, fast graph-signal filtering techniques are needed. In this contribution, we propose an accelerated algorithm based on the Lanczos method that adapts to the Laplacian spectrum without explicitly computing it. The result is an accurate, robust, scalable and efficient algorithm. Compared to existing methods based on Chebyshev polynomials, our solution achieves higher accuracy without increasing the overall complexity significantly. Furthermore, it is particularly well suited for graphs with large spectral gaps.

Subfields: Artificial Intelligence, Geometry and Topology, Statistical and Nonlinear Physics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Raquel Urtasun
2. Xavier Bresson
3. Pierre Vandergheynst
4. Renjie Liao
5. Richard S. Zemel
6. Michaël Defferrard
7. Cesare Alippi
8. Nathanael Perraudin

In Geometry and Topology

1. Michaël Defferrard
2. Xavier Bresson
3. Pierre Vandergheynst
4. Renjie Liao
5. Raquel Urtasun
6. Filippo Maria Bianchi
7. Cesare Alippi
8. Vassilis Kalofolias

In Statistical and Nonlinear Physics

1. Pierre Vandergheynst
2. Xavier Bresson
3. Nathanael Perraudin
4. Michaël Defferrard
5. Renjie Liao
6. Raquel Urtasun
7. Cesare Alippi
8. Filippo Maria Bianchi

In Optimization & Training

1. Pierre Vandergheynst
2. Wei Hu
3. Cesare Alippi
4. Richard S. Zemel
5. Vassilis Kalofolias
6. Nathanael Perraudin
7. Renjie Liao
8. Raquel Urtasun

Citations in the corpus

• Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering (2016, methodology): “Our technique leverages on this work, and we will show how to overcome these limitations and beyond.”
• A Comprehensive Survey on Graph Neural Networks (2019, neutral): “Graph Convolution Networks Spectral-based [12], [14], [20], [21], [22], [23], [43] Spatial-based [13], [17], [18], [19], [24], [25], [26], [27], [44], [45] [46], [47], [48], [49], [50], [51], [52], [53], [54] Pooling modules [12], [21], [55], [56] Graph Attention Networks [15], [28], [57], [58] Grap”
• RGCNN: Regularized Graph CNN for Point Cloud Segmentation (2018, methodology): “introduce the Lancoz method for approximation [26].”
• GSPBOX: A toolbox for signal processing on graphs (2014, methodology): “Note that the toolbox uses accelerated algorithms to scale almost linearly with the number of sample [11].”
• LanczosNet: Multi-Scale Deep Graph Convolutional Networks (2019, methodology): “Lanczos method has been explored for graph convolution in [35] for the purpose of acceleration.”
• Graph Neural Networks With Convolutional ARMA Filters (2019, methodology): “…(FIR) and realize a weighted moving average filtering of graph signals on local node neighbourhoods (Tremblay et al., 2018), thus allowing for fast distributed implementations based on Chebyshev polynomials and Lanczos iterations (Susnjara et al., 2015; Defferrard et al., 2016; Liao et al., 2019).”