Spectral Graph Convolutional Network

A Spectral Graph Convolutional Network is a Graph Convolutional Network that is based on the spectral graph theory.

• AKA: Spectral Network, Spectral Graph Neural Network.
• Context:
  • It was first developed by Bruna et al. (2013).
• Example(s):
  • an Adaptive Graph Convolution Network (Li et al., 2018),
  • a CayleyNet (Levie et al., 2018),
  • a ChebNet (Defferrard et al., 2016).
  • ...
  • …
• Counter-Example(s):
  • a Spatial Graph Convolutional Network,
  • a Graph Attention Network (GAT),
  • a Graph Recurrent Network (GRN),
  • a Graph Wavelet Neural Network (GWNN).
• See: Recurrent Neural Network, Feedforward Neural Network, Attention Mechanism.

---

---

References

2020a

• (Wu et al., 2020) ⇒ Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu (2020). "A Comprehensive Survey on Graph Neural Networks". In: IEEE transactions on neural networks and learning systems, 32(1), 4-24.
  • QUOTE: ConvGNNs are divided into two main streams, the spectral-based approaches and the spatial-based approaches. The first prominent research on spectral-based ConvGNNs was presented by Bruna et al. (2013), which developed a graph convolution based on the spectral graph theory.

2020b

• (Zhou et al., 2020) ⇒ Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun (2020). "Graph neural networks: A review of methods and applications". AI Open, 1, 57-81.
  • QUOTE: Spectral approaches work with a spectral representation of the graphs.

2019

• (Zhang et al., 2019) ⇒ Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski (2019). "Graph convolutional networks: a comprehensive review". In: Computational Social Networks, 6(1), 1-23.
  • QUOTE: (...) we categorize the graph convolutional neural networks into the spectral-based methods and the spatial-based methods, respectively. We consider the spectral-based methods to be those methods that start with constructing the frequency filtering.

    (...)

    As the spectral graph convolution relies on the specific eigen-functions of Laplacian matrix, it is still nontrivial to transfer the spectral-based graph convolutional network models learned on one graph to another graph whose eigenfunctions are different.

2018a

• (Levie et al., 2018) ⇒ Ron Levie, Federico Monti, Xavier Bresson, and Michael M. Bronstein. "CayleyNets: Graph Convolutional Neural Networks With Complex Rational Spectral Filters". In: IEEE Transactions on Signal Processing Volume: 67, Issue: 1.
  • QUOTE: 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.

2018b

• (Li et al., 2018) ⇒ Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang (2018). "Adaptive Graph Convolutional Neural Networks". In: Proceedings of The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18).
  • QUOTE: In the paper, we propose a novel spectral graph convolution network that feed on original data of diverse graph structures. e.g the organic molecules that consist of a different number of benzene rings.

2017

• (Kipf & Welling, 2017) ⇒ Thomas N. Kipf, and Max Welling (2017). "Semi-Supervised Classification with Graph Convolutional Networks". In: ICLR 2017.

2016

• (Defferrard et al., 2016) ⇒ Michael Defferrard, Xavier Bresson, and Pierre Vandergheynst (2016). "Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering". In: Proceeding of the Advances in Neural Information Processing Systems 29 (NIPS 2016).

2013

• (Bruna et al., 2013) ⇒ Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun (2013). "Spectral Networks and Locally Connected Networks on Graphs". In: arXiv:1312.6203

---