Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective
| Autor: | Muhammet Balcilar, Renton Guillaume, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, Paul Honeine |
|---|---|
| Přispěvatelé: | Equipe Apprentissage (DocApp - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Normandie Université (NU), ANR-18-CE23-0014,APi,Apprivoiser la Pré-image(2018), Honeine, Paul, APPEL À PROJETS GÉNÉRIQUE 2018 - Apprivoiser la Pré-image - - APi2018 - ANR-18-CE23-0014 - AAPG2018 - VALID |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI]
[INFO.INFO-TS] Computer Science [cs]/Signal and Image Processing [INFO.INFO-NE] Computer Science [cs]/Neural and Evolutionary Computing [cs.NE] [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV] [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG] [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE] [STAT.ML] Statistics [stat]/Machine Learning [stat.ML] [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] [INFO.INFO-CY] Computer Science [cs]/Computers and Society [cs.CY] [INFO.INFO-CV] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV] [STAT.ML]Statistics [stat]/Machine Learning [stat.ML] [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG] [INFO.INFO-CY]Computer Science [cs]/Computers and Society [cs.CY] [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST] [MATH.MATH-ST] Mathematics [math]/Statistics [math.ST] [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing [SPI.SIGNAL] Engineering Sciences [physics]/Signal and Image processing |
| Zdroj: | Proceedings of the International Conference on Learning Representations (ICLR) Proceedings of the International Conference on Learning Representations (ICLR), May 2021, Vienna, Austria HAL |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|