CayleyNets: Graph Convolutional Neural Networks With Complex Rational Spectral Filters

By Ron Levie, Federico Monti, Xavier Bresson, Michael M. Bronstein. 2017

754 citations recorded by the source corpus.

The rise of graph-structured data such as social networks, regulatory networks, citation graphs, and functional brain networks, in combination with resounding success of deep learning in various applications, has brought the interest in generalizing deep learning models to non-Euclidean domains. In this paper, we introduce a new spectral domain convolutional architecture for deep learning on graphs. The core ingredient of our model is a new class of parametric rational complex functions (Cayley polynomials) allowing to efficiently compute spectral filters on graphs that specialize on frequency bands of interest. Our model generates rich spectral filters that are localized in space, scales linearly with the size of the input data for sparsely connected graphs, and can handle different constructions of Laplacian operators. Extensive experimental results show the superior performance of our approach, in comparison to other spectral domain convolutional architectures, on spectral image classification, community detection, vertex classification, and matrix completion tasks.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

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

In Statistical and Nonlinear Physics

Citations in the corpus

Provably Powerful Graph Networks (2019, background): “This paper resulted in multiple follow up works with more efficient and spatially localized convolutions (Henaff et al., 2015; Defferrard et al., 2016; Kipf and Welling, 2016; Levie et al., 2017).”
Dynamic Graph CNN for Learning on Point Clouds (2018, methodology): “Computational drawbacks of this foundational approach were alleviated in follow-up works using polynomial [Def-ferrard et al. 2016; Kipf and Welling 2017; Monti et al. 2017b, 2018], or rational [Levie et al. 2017] spectral filters that avoid Laplacian eigendecomposition and guarantee localization.”
SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels (2017, methodology): “We use a SplineCNN similar to the network architecture introduced in [15, 12, 18]: SConv((2),1433,16) → SConv((2),16,7), with ELU activation after the first SConv layer and m = 1.”
Deformable Shape Completion with Graph Convolutional Autoencoders (2017, methodology): “Related independent efforts developed CNN-type architectures for general graphs [11, 20, 14, 26, 35, 31].”
Metric learning with spectral graph convolutions on brain connectivity networks (2018, background): “Kipf and Welling (2016) later introduced a renormalisation trick to speedup computations, while Levie et al. (2017) proposed Cayley polynomial filters, a new class of parametric rational complex functions, to compute localised regular filters.”
Graph Convolutional Networks with EigenPooling (2019, methodology): “Another stream of graph neural networks was developed based on the graph Fourier transform [4, 8, 19, 24].”
Representation Learning for Dynamic Graphs: A Survey (2019, background): “Graph convolutions have spatial (see, e.g., Hamilton et al. (2017a,b); Schlichtkrull et al. (2018); Gilmer et al. (2017)) and spectral constructions (see, e.g., Liao et al. (2019); Kipf and Welling (2017); Defferrard et al. (2016); Levie et al. (2017)).”
RGCNN: Regularized Graph CNN for Point Cloud Segmentation (2018, methodology): “Hence, several methods propose to approximate the convolution in the spectral domain by spatial filtering, such as Chebyshev polynomials [9], Lanczos method [26], Cayley polynomials [15], etc.”
Residual Gated Graph ConvNets (2017, methodology): “Defferrard et al. (2016) used Chebyshev polynomials to achieve linear complexity for sparse graphs, Levie et al. (2017) applied Cayley polynomials to focus on narrow-band frequencies, and Monti et al. (2017b) dealt with multiple (ﬁxed) graphs.”
Edge Attention-based Multi-Relational Graph Convolutional Networks (2018, methodology): “In particular, Chebyshev polynomials [9] and Cayley polynomials [25] have been utilized in these convolutional architectures to efficiently produce localized filters.”
Graph convolutional networks: a comprehensive review (2019, methodology): “Many graph convolutional network models have been proposed, to name a few, including [5, 37, 42, 61, 95].”
BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation (2021, background): “Recent studies suggest that many popular GNNs operate as polynomial graph spectral filters [7, 13, 5, 16, 2, 35].”
DiffusionNet: Discretization Agnostic Learning on Surfaces (2020, methodology): “We also note that our use of the Laplacian in defining the diffusion operator is related to methods based on polynomials of the Laplacian [Defferrard et al. 2016; Kostrikov et al. 2018], CayleyNets [Levie et al. 2018] and their recent application in shape matching using ACSCNNs [Li et al. 2020b].”
Mining Point Cloud Local Structures by Kernel Correlation and Graph Pooling (2017, positive): “a connectivity graph or a polygon mesh can be used to represent a 3D point cloud, convert to the spectral representation and apply convolution in spectral domain [4, 8, 10, 13, 19, 22].”
PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks (2020, background): “Many GNN’s architectures with high predictive performance should be mentioned are ChebNets [4], Graph Convolutional Networks [5], GraphSage [6], Graph Attention Networks [7], among others [8, 9, 10, 11, 12, 13].”
Rethinking Graph Neural Networks for Anomaly Detection (2022, background): “Unfortunately, most of the current GNNs are low-pass ﬁlters (Nt & Maehara, 2019; Wu et al., 2019) or adaptive ﬁlters (Def-ferrard et al., 2016; He et al., 2021; Dong et al., 2021; Levie et al., 2018) that are neither guaranteed to be band-pass nor spectral-localized (Balcilar et al., 2020).”