Elamur Research
☰
home / papers / 2016 / Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "arXiv — non-exclusive license to distribute" does not allow redistributing the text itself. Original — arxiv.org/pdf/1606.09375

Summary

Classical CNNs depend on convolution and pooling defined on regular grids. This excludes data whose structure is an arbitrary graph, such as social networks, brain connectomes or word-embedding spaces. Defferrard, Bresson and Vandergheynst reformulate graph convolution using spectral graph theory and graph signal processing. Each filter is a truncated Chebyshev polynomial of a rescaled graph Laplacian, evaluated through a recurrence of sparse matrix–vector products. This removes the need for an eigendecomposition or a stored dense Fourier basis. Each filter reaches only vertices within K hops and has just K trainable coefficients. For pooling, graphs are coarsened with the Graclus multilevel clustering, and vertices are rearranged into a binary tree so pooling works like ordinary 1D pooling. On MNIST, treated as a grid graph, the model comes close to a classical CNN. On 20NEWS it beats fully connected networks but not multinomial naive Bayes. It is both more accurate and much cheaper than the earlier spectral graph CNN, which made it a foundational design for later graph neural networks.

Key points

  • Filtering costs O(K|E|) operations, which is linear in input size for sparse k-NN graphs. Learning complexity is O(K), as in standard CNNs. Training time scales as O(n), versus O(n²) for the earlier spectral CNN, and GPU speedups resemble those of classical CNNs.

  • On MNIST with an 8-NN grid graph, GC32 reaches 97.40% and GC32-P4-GC64-P4-FC512 reaches 99.14%. With a random graph, these drop to 96.88% and 95.39%, showing that graph structure matters.

  • The 20NEWS experiment uses 18,846 documents in 20 classes, with a 10,000-word bag-of-words vocabulary. Words form a 16-NN graph built from word2vec embeddings (132,834 edges), classified by GC32 with K = 5.

  • On 20NEWS, the choice of word graph changes GC32 accuracy:

    Graph constructionAccuracy
    Learned word2vec68.26%
    Approximate (LSHForest)67.86%
    Random67.75%
    Bag-of-words67.50%
    Pre-learned word2vec66.98%

  • A TensorFlow implementation is released open source at github.com/mdeff/cnn_graph.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: AI & machine learning

Cited by

124 papers of our library cite it (of the 140673 whose bibliographies we read); 11 of them have a page here, 113 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1606.09375 · arXiv 1606.09375

@misc{defferrard2016convolutional,
  title = {{Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering}},
  author = {Defferrard, Michael and Bresson, Xavier and Vandergheynst, Pierre},
  year = {2016},
  doi = {10.48550/arxiv.1606.09375},
  eprint = {1606.09375},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1606.09375}
}

References

34 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Martín Abadi et al. TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems. 2016. find our card
  2. M. Bawa, T. Condie, and P. Ganesan. LSH Forest: Self-Tuning Indexes for Similarity Search. In International Conference on World Wide Web, pages 651–660, 2005. find
  3. M. Belkin and P. Niyogi. Towards a Theoretical Foundation for Laplacian-based Manifold Methods. Journal of Computer and System Sciences, 74(8):1289–1308, 2008. find
  4. J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral Networks and Deep Locally Connected Networks on Graphs. arXiv:1312.6203, 2013. — [arXiv:1312.6203](https://arxiv.org/abs/1312.6203) find
  5. T.N. Bui and C. Jones. Finding Good Approximate Vertex and Edge Partitions is NP-hard. Information Processing Letters, 42(3):153–159, 1992. find
  6. F. R. K. Chung. Spectral Graph Theory, volume 92. American Mathematical Society, 1997. find
  7. A. Coates and A.Y. Ng. Selecting Receptive Fields in Deep Networks. In Neural Information Processing Systems (NIPS), pages 2528–2536, 2011. find
  8. R.R. Coifman and S. Lafon. Diffusion Maps. Applied and Computational Harmonic Analysis, 21(1):5–30, 2006. find
  9. I. Dhillon, Y. Guan, and B. Kulis. Weighted Graph Cuts Without Eigenvectors: A Multilevel Approach. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 29(11):1944–1957, 2007. find
  10. M. Gavish, B. Nadler, and R. Coifman. Multiscale Wavelets on Trees, Graphs and High Dimensional Data: Theory and Applications to Semi Supervised Learning. In International Conference on Machine Learning (ICML), pages 367–374, 2010. find
  11. K. Gregor and Y. LeCun. Emergence of Complex-like Cells in a Temporal Product Network with Local Receptive Fields. In arXiv:1006.0448, 2010. — [arXiv:1006.0448](https://arxiv.org/abs/1006.0448) find
  12. D. Hammond, P. Vandergheynst, and R. Gribonval. Wavelets on Graphs via Spectral Graph Theory. Applied and Computational Harmonic Analysis, 30(2):129–150, 2011. find
  13. M. Henaff, J. Bruna, and Y. LeCun. Deep Convolutional Networks on Graph-Structured Data. arXiv:1506.05163, 2015. — [arXiv:1506.05163](https://arxiv.org/abs/1506.05163) find
  14. Max Jaderberg, Karen Simonyan, Andrew Zisserman, et al. Spatial transformer networks. In Advances in Neural Information Processing Systems, pages 2017–2025, 2015. find
  15. T. Joachims. A Probabilistic Analysis of the Rocchio Algorithm with TFIDF for Text Categorization. Carnegie Mellon University, Computer Science Technical Report, CMU-CS-96-118, 1996. find
  16. G. Karypis and V. Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM Journal on Scientific Computing (SISC), 20(1):359–392, 1998. find
  17. D. Kingma and J. Ba. Adam: A Method for Stochastic Optimization. arXiv:1412.6980, 2014. find
  18. Y. LeCun, Y. Bengio, and G. Hinton. Deep Learning. Nature, 521(7553):436–444, 2015. find
  19. Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-Based Learning Applied to Document Recognition. In Proceedings of the IEEE, 86(11), pages 2278–2324, 1998. find
  20. Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated Graph Sequence Neural Networks. find
  21. U. Von Luxburg. A Tutorial on Spectral Clustering. Statistics and Computing, 17(4):395–416, 2007. find
  22. S. Mallat. A Wavelet Tour of Signal Processing. Academic press, 1999. find
  23. Jonathan Masci, Davide Boscaini, Michael Bronstein, and Pierre Vandergheynst. Geodesic convolutional neural networks on riemannian manifolds. In Proceedings of the IEEE International Conference on Computer Vision Workshops, pages 37–45, 2015. find
  24. T. Mikolov, K. Chen, G. Corrado, and J. Dean. Estimation of Word Representations in Vector Space. In International Conference on Learning Representations, 2013. find
  25. B. Pasdeloup, R. Alami, V. Gripon, and M. Rabbat. Toward an Uncertainty Principle for Weighted Graphs. In Signal Processing Conference (EUSIPCO), pages 1496–1500, 2015. find
  26. N. Perraudin, B. Ricaud, D. Shuman, and P. Vandergheynst. Global and Local Uncertainty Principles for Signals on Graphs. arXiv:1603.03030, 2016. — [arXiv:1603.03030](https://arxiv.org/abs/1603.03030) find
  27. I. Ram, M. Elad, and I. Cohen. Generalized Tree-based Wavelet Transform. IEEE Transactions on Signal Processing,, 59(9):4199–4209, 2011. find
  28. D. Ron, I. Safro, and A. Brandt. Relaxation-based Coarsening and Multiscale Graph Organization. SIAM Iournal on Multiscale Modeling and Simulation, 9:407–423, 2011. find
  29. F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The Graph Neural Network Model. 20(1):61–80. find
  30. J. Shi and J. Malik. Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 22(8):888–905, 2000. find
  31. D. Shuman, S. Narang, P. Frossard, A. Ortega, and P. Vandergheynst. The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and other Irregular Domains. IEEE Signal Processing Magazine, 30(3):83–98, 2013. find
  32. D.I. Shuman, M.J. Faraji, and P. Vandergheynst. A Multiscale Pyramid Transform for Graph Signals. IEEE Transactions on Signal Processing, 64(8):2119–2134, 2016. find
  33. A. Susnjara, N. Perraudin, D. Kressner, and P. Vandergheynst. Accelerated Filtering on Graphs using Lanczos Method. preprint arXiv:1509.04537, 2015. — [arXiv:1509.04537](https://arxiv.org/abs/1509.04537) find
  34. M. Tsitsvero and S. Barbarossa. On the Degrees of Freedom of Signals on Graphs. In Signal Processing Conference (EUSIPCO), pages 1506–1510, 2015. find