CayleyNets: Graph Convolutional Neural Networks With Complex Rational Spectral Filters
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Adam: A Method for Stochastic Optimization
Kingma, D. P., & Ba, J. (2014) · arXiv · doi:10.48550/arxiv.1412.6980 · Cited by 98,946 · see citing works
Gradient-based learning applied to document recognition
Lecun, Y., Bottou, L., Bengio, Y., & Haffner, P. (1998) · Proceedings of the IEEE · doi:10.1109/5.726791 · Cited by 58,805 · see citing works
Semi-supervised classification with graph convolutional networks
Kipf, T. N., & Welling, M. (2016) · arXiv · doi:10.48550/arxiv.1609.02907 · Cited by 24,853 · see citing works
The graph neural network model
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2009) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2008.2005605 · Cited by 9,582 · see citing works
TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M., et al. (2016) · arXiv · doi:10.48550/arxiv.1603.04467 · Cited by 9,408 · see citing works
Horn, R. A., & Johnson, C. R. (2012) · doi:10.1017/cbo9781139020411 · Cited by 4,642 · see citing works
Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., & Vandergheynst, P. (2013) · IEEE Signal Processing Magazine · doi:10.1109/msp.2012.2235192 · Cited by 4,421 · see citing works
Gated Graph Sequence Neural NetworksPreprint
Li, Y., Tarlow, D., Brockschmidt, M., & Zemel, R. (2015) · International Conference on Learning Representations · doi:10.48550/arxiv.1511.05493 · Cited by 3,735 · see citing works
Geometric Deep Learning: Going beyond Euclidean data
Bronstein, M. M., Bruna, J., LeCun, Y., Szlam, A., & Vandergheynst, P. (2017) · IEEE Signal Processing Magazine · doi:10.1109/msp.2017.2693418 · Cited by 3,661 · see citing works
Self-citationCollective Classification in Network Data
Sen, P., Namata, G., Bilgic, M., Getoor, L., Gallagher, B., & Eliassi‐Rad, T. (2008) · AI Magazine · doi:10.1609/aimag.v29i3.2157 · Cited by 3,293 · see citing works
A new model for learning in graph domains
Gori, M., Monfardini, G., & Scarselli, F. (2006) · Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005. · doi:10.1109/ijcnn.2005.1555942 · Cited by 2,075 · see citing works
Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs
Monti, F., Boscaini, D., Masci, J., Rodola, E., Svoboda, J., & Bronstein, M. M. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.576 · Cited by 1,820 · see citing works
Self-citationDiscrete Signal Processing on Graphs
Sandryhaila, A., & Moura, J. M. F. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2238935 · Cited by 1,531 · see citing works
Deep Convolutional Networks on Graph-Structured Data
Henaff, M., Bruna, J., & LeCun, Y. (2015) · arXiv · doi:10.48550/arxiv.1506.05163 · Cited by 1,255 · see citing works
Weighted Graph Cuts without Eigenvectors A Multilevel Approach
Dhillon, I. S., Guan, Y., & Kulis, B. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1115 · Cited by 1,037 · see citing works
Exact matrix completion via convex optimization
Candès, E. J., & Recht, B. (2012) · Communications of the ACM · doi:10.1145/2184319.2184343 · Cited by 1,011 · see citing works
Discrete Signal Processing on Graphs: Frequency Analysis
Sandryhaila, A., & Moura, J. M. F. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2321121 · Cited by 879 · see citing works
Geodesic Convolutional Neural Networks on Riemannian Manifolds
Masci, J., Boscaini, D., Bronstein, M. M., & Vandergheynst, P. (2015) · 2015 IEEE International Conference on Computer Vision Workshop (ICCVW) · doi:10.1109/iccvw.2015.112 · Cited by 721 · see citing works
Self-citationMiller, B., Albert, I., Lam, S. K., Konstan, J. A., & Riedl, J. (2003) · ACM International Conference on Intelligent User Interfaces (IUI) · doi:10.1145/604045.604094 · Cited by 510 · see citing works
Autoregressive Moving Average Graph Filtering
Isufi, E., Loukas, A., Simonetto, A., et al. (2016) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2614793 · Cited by 269 · see citing works
Boscaini, D., Masci, J., Melzi, S., Bronstein, M. M., Castellani, U., & Vandergheynst, P. (2015) · Computer Graphics Forum · doi:10.1111/cgf.12693 · Cited by 205 · see citing works
Self-citationMatrix Completion on GraphsPreprint
Kalofolias, V., Bresson, X., Bronstein, M. M., & Vandergheynst, P. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1408.1717 · Cited by 154 · see citing works
Self-citationAnisotropic Diffusion Descriptors
Boscaini, D., Masci, J., Rodolà, E., Bronstein, M. M., & Cremers, D. (2016) · Computer Graphics Forum · doi:10.1111/cgf.12844 · Cited by 122 · see citing works
Self-citationProvable Inductive Matrix CompletionPreprint
Jain, P., & Dhillon, I. S. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1306.0626 · Cited by 119 · see citing works
A Generalization of Convolutional Neural Networks to Graph-Structured DataPreprint
Hechtlinger, Y., Chakravarti, P., & Qin, J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1704.08165 · Cited by 74 · see citing works
Filter Design for Autoregressive Moving Average Graph Filters
Liu, J., Isufi, E., & Leus, G. J. T. (2018) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2018.2854627 · Cited by 70 · see citing works
Error Forgetting of Bregman Iteration
Yin, W., & Osher, S. (2012) · Journal of Scientific Computing · doi:10.1007/s10915-012-9616-5 · Cited by 69 · see citing works
Constantin, A. (2016) · Cambridge University Press eBooks · doi:10.1017/cbo9781107358508 · Cited by 8 · see citing works
Filter Design for Autoregressive Moving Average Graph FiltersPreprint
Liu, J., Isufi, E., & Leus, G. J. T. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1711.09086 · Cited by 3 · see citing works
Flagged first, then by citations
Research works printed but not linked: 13
- J. Atwood and D. Towsley. Diffusion-convolutional neural networks. pages 1993-2001, 2016.
- D. Boscaini, J. Masci, E. Rodolà, and M. M. Bronstein. Learning shape correspondence with anisotropic convolutional neural networks. In Proc. NIPS, 2016.
- J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and locally connected networks on graphs. Proc. ICLR, 2013.
- A. Coates and A. Ng. Selecting Receptive Fields in Deep Networks. In Proc. NIPS, 2011.
- M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Proc. NIPS, 2016.
- D. K. Duvenaud et al. Convolutional networks on graphs for learning molecular fingerprints. In Proc. NIPS, 2015.
- K. Gregor and Y. LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML'10, pages 399-406, USA, 2010. Omnipress.
- S. I. Ktena, S. Parisot, E. Ferrante, M. Rajchl, M. Lee, B. Glocker, and D. Rueckert. Distance metric learning using graph convolutional networks: Application to functional brain networks. pages 469-477, 2017.
- F. Monti, M. M. Bronstein, and X. Bresson. Geometric matrix completion with recurrent multi-graph neural networks. Proc. NIPS, 2017.
- N. Rao, H.-F. Yu, P. K. Ravikumar, and I. S. Dhillon. Collaborative filtering with graph information: Consistency and scalable methods. In Proc. NIPS, 2015.
- S. Sukhbaatar, a. szlam, and R. Fergus. Learning multiagent communication with backpropa- gation. pages 2244-2252, 2016.
- P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. Proc. ICLR 2018, 2018.
- M. Xu, R. Jin, and Z.-H. Zhou. Speedup matrix completion with side information: Application to multi-label learning. In Proc. NIPS, 2013.
Cited by
Sorted by citations
A Comprehensive Survey on Graph Neural Networks
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.2978386 · Cited by 11,000 · see citing works
Dynamic Graph CNN for Learning on Point Clouds
Wang, Y., Sun, Y., Liu, Z., Sarma, S. E., Bronstein, M. M., & Solomon, J. M. (2019) · ACM Transactions on Graphics · doi:10.1145/3326362 · Cited by 7,199 · see citing works
Self-citationGraph convolutional networks: a comprehensive review
Zhang, S., Tong, H., Xu, J., & Maciejewski, R. (2019) · Computational Social Networks · doi:10.1186/s40649-019-0069-y · Cited by 1,888 · see citing works
CCNet: Criss-Cross Attention for Semantic Segmentation
Huang, Z., Wang, X., Wei, Y., Huang, L., Shi, H., Liu, W., & Huang, T. S. (2023) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2020.3007032 · Cited by 524 · see citing works
SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels
Fey, M., Lenssen, J. E., Weichert, F., & Muller, H. (2018) · 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2018.00097 · Cited by 459 · see citing works
RGCNN: Regularized Graph CNN for Point Cloud Segmentation
Te, G., Hu, W., Zheng, A., & Guo, Z. (2018) · Proceedings of the 26th ACM international conference on Multimedia · doi:10.1145/3240508.3240621 · Cited by 311 · see citing works
Shan, X., Cao, J., Huo, S., Chen, L., Sarrigiannis, P. G., & Zhao, Y. (2022) · Human Brain Mapping · doi:10.1002/hbm.25994 · Cited by 75 · see citing works
“Since then, there have been increasing improvements, approximations, and extensions on spectral-based GNNs (Defferrard et al., 2016; Henaff et al., 2015; Kipf & Welling, 2016; Levie et al., 2018) to reduce the computational complexity Welling, 2016).”
Background
- Authors
- Levie, R., Monti, F., Bresson, X., & Bronstein, M. M.
- Affiliations
- Technische Universität Berlin (DE)
- Università della Svizzera italiana (CH)
- Nanyang Technological University (SG)
- Intel (Israel) (IL)
- Venue
- IEEE Transactions on Signal Processing
- Published
- 2019-01-01
- Volume
- 67
- Issue
- 1
- Pages
- 97-109
- ISSN
- 1053-587X (ISSN-L)
- 1941-0476
- OpenAlex
- W2618170429
- Cited by
- 685
- References
- 29
- Citations by year
- 2026: 34 · 2025: 64 · 2024: 96 · 2023: 76 · 2022: 104 · 2021: 132 · 2020: 99 · 2019: 51 · 2018: 26 · 2017: 3
- FWCI
- 43.39
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- IEEE Transactions on Signal Processing (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- DR-NTU (Nanyang Technological University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- ERC Consolidator (724228 (LEMAN))
- Royal Society Wolfson Research Merit Award
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Graph Theory and Algorithms
- Physical Sciences › Mathematics › Geometry and Topology › Graph theory and applications
- Keywords
- graph convolutional networks, spectral graph convolution, graph Laplacian, spectral image classification, community detection, node classification, matrix completion, non-Euclidean data
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
