Skip to Main content Skip to Navigation
Conference papers

Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective

Muhammet Balcilar 1 Renton Guillaume 1 Pierre Héroux 1 Benoit Gaüzère 1 Sébastien Adam 1 Paul Honeine 1
1 DocApp - LITIS - Equipe Apprentissage
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
Abstract : In the recent literature of Graph Neural Networks (GNN), the expressive power of models has been studied through their capability to distinguish if two given graphs are isomorphic or not. Since the graph isomorphism problem is NP-intermediate, and Weisfeiler-Lehman (WL) test can give sufficient but not enough evidence in polynomial time, the theoretical power of GNNs is usually evaluated by the equivalence of WL-test order, followed by an empirical analysis of the models on some reference inductive and transductive datasets. However, such analysis does not account the signal processing pipeline, whose capability is generally evaluated in the spectral domain. In this paper, we argue that a spectral analysis of GNNs behavior can provide a complementary point of view to go one step further in the understanding of GNNs. By bridging the gap between the spectral and spatial design of graph convolutions, we theoretically demonstrate some equivalence of the graph convolution process regardless it is designed in the spatial or the spectral domain. Using this connection, we managed to re-formulate most of the state-of-the-art graph neural networks into one common framework. This general framework allows to lead a spectral analysis of the most popular GNNs, explaining their performance and showing their limits according to spectral point of view. Our theoretical spectral analysis is confirmed by experiments on various graph databases. Furthermore, we demonstrate the necessity of high and/or band-pass filters on a graph dataset, while the majority of GNN is limited to only low-pass and inevitably it fails. Code available at https://github.com/balcilar/gnn-spectral-expressive-power.
Complete list of metadata

https://hal-normandie-univ.archives-ouvertes.fr/hal-03135633
Contributor : Paul Honeine <>
Submitted on : Tuesday, February 9, 2021 - 10:28:55 AM
Last modification on : Tuesday, February 23, 2021 - 3:27:37 AM
Long-term archiving on: : Monday, May 10, 2021 - 6:24:45 PM

File

ExpressivePowerGNN_ICLR (final...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03135633, version 1

Citation

Muhammet Balcilar, Renton Guillaume, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, et al.. Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective. Proceedings of the International Conference on Learning Representations (ICLR), May 2021, Vienna, Austria. ⟨hal-03135633⟩

Share

Metrics

Record views

73

Files downloads

28