Graph Neural Network (GNNs)

Papers that I like on GNNs with interesting theoretical analysis.

Contents

• Interesting Models
• Statistical Behaviours
• Expressive Power

Interesting Models

1. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering.

   • NIPS 2016.
   • Michaël Defferrard, Xavier Bresson, Pierre Vandergheynst.
   • paper

2. Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks.

   • AAAI 2019.
   • Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, Martin Grohe.
   • paper

3. Invariant and Equivariant Graph Networks.

   • ICLR 2019.
   • Haggai Maron, Heli Ben-Hamu, Nadav Shamir & Yaron Lipman.
   • paper

4. Provably Powerful Graph Networks.

   • NeurIPS 2019.
   • Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, Yaron Lipman.
   • paper

5. Nested Graph Neural Networks.

   • NeurIPS 2021.
   • Muhan Zhang, Pan Li.
   • paper

6. A New Perspective on "How Graph Neural Networks Go Beyond Weisfeiler-Lehman?"

   • ICLR 2022.
   • Asiri Wijesinghe, Qing Wang.
   • paper

7. p-Laplacian Based Graph Neural Networks.

   • ICML 2022.
   • Guoji Fu, Peilin Zhao, Yatao Bian.
   • paper

Statistical Behaviours

1. Stability and Generalization of Graph Convolutional Neural Networks.

   • KDD 2019.
   • Saurabh Verma, Zhi-Li Zhang.
   • paper

2. Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case.

   • ICML 2020.
   • Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yu Chen, Jinjun Xiong.
   • paper

3. Convergence and Stability of Graph Convolutional Networks on Large Random Graphs.

   • NeurIPS 2020.
   • Nicolas Keriven, Alberto Bietti, Samuel Vaiter.
   • paper

4. A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks.

   • ICLR 2021.
   • Renjie Liao, Raquel Urtasun, Richard Zemel.
   • paper

5. From Local Structures to Size Generalization in Graph Neural Networks.

   • ICML 2021.
   • Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, Haggai Maron.
   • paper

6. Subgroup Generalization and Fairness of Graph Neural Networks.

   • NeurIPS 2021.
   • Jiaqi Ma, Junwei Deng, Qiaozhu Mei.
   • paper

7. Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks.

   • NeurIPS 2021.
   • Pascal Mattia Esser, Leena C. Vankadara, Debarghya Ghoshdastidar.
   • paper

8. Generalization Bounds for Graph Convolutional Neural Networks via Rademacher Complexity.

   • arXiv 2021.
   • Shaogao Lv.
   • paper

9. Convergence of Invariant Graph Networks.

   • ICML 2022.
   • Chen Cai, Yusu Wang.
   • paper

10. Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling.

    • Abstract

    • ICML 2022.
    • Hongkang Li, Meng Wang, Sijia Liu, Pin-Yu Chen, Jinjun Xiong.
    • paper

11. Probing GNN Explainers: A Rigorous Theoretical and Empirical Analysis of GNN Explanation Methods.

    • AISTAT 2022.
    • Chirag Agarwal, Marinka Zitnik, Himabindu Lakkaraju.
    • paper

12. Stability and Generalization Capabilities of Message Passing Graph Neural Networks.

    • arXiv 2022.
    • Sohir Maskey, Yunseok Lee, Ron Levie, Gitta Kutyniok.
    • paper

Expressive Power

1. How Powerful are Graph Neural Networks?

   • ICLR 2019.
   • Keyulu Xu, Weihua Hu, Jure Leskovec, Stefanie Jegelka.
   • paper

2. On the Universality of Invariant Networks.

   • ICML 2019.
   • Haggai Maron, Ethan Fetaya, Nimrod Segol, Yaron Lipman.
   • paper

3. On the Equivalence Between Graph Isomorphism Testing and Function Approximation with GNNs.

   • NeurIPS 2019.
   • Zhengdao Chen, Soledad Villar, Lei Chen, Joan Bruna.
   • paper

4. Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology.

   • NeurIPS 2019.
   • Nima Dehmamy, Albert-László Barabási, Rose Yu.
   • paper

5. Fundamental Limits of Deep Graph Convolutional Networks.

   • arXiv 2019.
   • Abram Magner, Mayank Baranwal, Alfred O. Hero III.
   • paper

6. What Can Neural Networks Reason About?

   • ICLR 2020.
   • Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken-ichi Kawarabayashi, Stefanie Jegelka.
   • paper

7. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification.

   • ICLR 2020.
   • Kenta Oono, Taiji Suzuki.
   • paper
   • code

8. What Graph Neural Networks Cannot Learn: Depth vs Width.

   • ICLR 2020.
   • Andreas Loukas.
   • paper

9. How Hard is to Distinguish Graphs with Graph Neural Networks?

   • Neurips 2020.
   • Andreas Loukas.
   • paper

10. On the Equivalence of Molecular Graph Convolution and Molecular Wave Function with Poor Basis Set.

    • Neurips 2020.
    • Masashi Tsubaki, Teruyasu Mizoguchi.
    • paper

11. Generalization and Representational Limits of Graph Neural Networks.

    • arXiv 2020.
    • Vikas K. Garg, Stefanie Jegelka, Tommi Jaakkola.
    • paper

12. How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks.

    • ICLR 2021.
    • Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S. Du, Ken-ichi Kawarabayashi, Stefanie Jegelka.
    • paper

13. On the Bottleneck of Graph Neural Networks and its Practical Implications.

    • ICLR 2021.
    • Uri Alon, Eran Yahav.
    • paper

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

    • ICLR 2021.
    • Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, Paul Honeine.
    • paper

15. A Unified Lottery Ticket Hypothesis for Graph Neural Networks.

    • ICML 2021.
    • Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, Zhangyang Wang.
    • paper

16. On Provable Benefits of Depth in Training Graph Convolutional Networks.

    • NeurIPS 2021.
    • Weilin Cong, Morteza Ramezani, Mehrdad Mahdavi.
    • paper

17. Reconstruction for Powerful Graph Representations.

    • NeurIPS 2021.
    • Leonardo Cotta, Christopher Morris, Bruno Ribeiro.
    • paper

18. On the Universality of Graph Neural Networks on Large Random Graphs.

    • NeurIPS 2021.
    • Nicolas Keriven, Alberto Bietti, Samuel Vaiter.
    • paper

19. GemNet: Universal Directional Graph Neural Networks for Molecules.

    • NeurIPS 2021.
    • Johannes Klicpera, Florian Becker, Stephan Günnemann.
    • paper

20. Expressiveness and Approximation Properties of Graph Neural Networks.

    • ICLR 2022.
    • Floris Geerts, Juan L Reutter.
    • paper

21. A New Perspective on "How Graph Neural Networks Go Beyond Weisfeiler-Lehman?"

    • ICLR 2022.
    • Asiri Wijesinghe, Qing Wang.
    • paper

22. A New Perspective on the Effects of Spectrum in Graph Neural Networks.

    • Abstract

    • ICML 2022.
    • Mingqi Yang, Yanming Shen, Rui Li, Heng Qi, Qiang Zhang, Baocai Yin.
    • paper

23. How Powerful are Spectral Graph Neural Networks.

    • ICML 2022.
    • Xiyuan Wang, Muhan Zhang.
    • paper

24. On the Equivalence Between Temporal and Static Graph Representations for Observational Predictions.

    • ICML 2022.
    • Jianfei Gao, Bruno Ribeiro.
    • paper

25. A Theoretical Comparison of Graph Neural Network Extensions.

    • ICML 2022.
    • Pál András Papp, Roger Wattenhofer.
    • paper

26. The Exact Class of Graph Functions Generated by Graph Neural Networks.

    • arXiv 2022.
    • Mohammad Fereydounian, Hamed Hassani, Javid Dadashkarimi, Amin Karbasi.
    • paper

27. Not Too Little, Not Too Much: a Theoretical Analysis of Graph (over)Smoothing.

    • arXiv 2022.
    • Nicolas Keriven.
    • paper

28. Graph Neural Networks Are More Powerful Than We Think.

    • arXiv 2022.
    • Charilaos I. Kanatsoulis, Alejandro Ribeiro.
    • paper

29. When Does A Spectral Graph Neural Network Fail in Node Classification?

    • arXiv 2022.
    • Zhixian Chen, Tengfei Ma, Yang Wang.
    • paper