🔥 awesome-expressive-gnn

A collection of papers studying and/or improving the expressiveness of graph neural networks (GNNs).

Please feel free to submit a pull request if you want to add good papers.

Survey

[arXiv 2020] A Survey on The Expressive Power of Graph Neural Networks [Paper]
[arXiv 2021] Weisfeiler and Leman go Machine Learning: The Story so far [Paper]
[arXiv 2022] Theory of Graph Neural Networks: Representation and Learning [Paper]

[ICLR 2023] Rethinking the Expressive Power of GNNs via Graph Biconnectivity [Paper]
[ICLR 2023] Graph Neural Networks for Link Prediction with Subgraph Sketching [Paper]
[ICLR 2023] On Representing Linear Programs by Graph Neural Networks [Paper]
[ICLR 2023] Boosting the Cycle Counting Power of Graph Neural Networks with I²-GNNs [Paper]
[ICLR 2023] Cycle to Clique (Cy2C) Graph Neural Network: A Sight to See beyond Neighborhood Aggregation [Paper]
[ICLR 2023] Agent-based Graph Neural Networks [Paper]
[ICLR 2023] A New Hierarchy of Expressivity for Graph Neural Networks [Paper]
[ICML 2023] On the Expressive Power of Geometric Graph Neural Networks [Paper]

[arXiv 2022] Your Neighbors Are Communicating: Towards Powerful and Scalable Graph Neural Networks [Paper]
[arXiv 2022] Collaboration-Aware Graph Convolutional Networks for Recommendation Systems [Paper][Code]
[NeurIPS 2022] Ordered Subgraph Aggregation Networks [Paper]
[NeurIPS 2022] Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries [Paper][Code]
[NeurIPS 2022] How Powerful are K-hop Message Passing Graph Neural Networks [Paper][Code]
[NeurIPS 2022] A Practical, Progressively-Expressive GNN [Paper][Code]
[ICML 2022] A Theoretical Comparison of Graph Neural Network Extensions [Paper]
[ICML 2022] SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks [Paper][Code]
[ICLR 2022] From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness [Paper][Code]
[ICLR 2022] A New Perspective on "How Graph Neural Networks Go Beyond Weisfeiler-Lehman?" [Paper]
[ICLR 2022] Equivariant Subgraph Aggregation Networks [Paper][Code]
[TPAMI] Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [Paper][Code]

[NeurIPS 2021] DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks [Paper][Code]
[NeurIPS 2021] Nested Graph Neural Networks [Paper][Code]
[NeurIPS 2021] Decoupling the Depth and Scope of Graph Neural Networks [Paper][Code]
[NeurIPS 2021] Weisfeiler and Lehman Go Cellular: CW Networks [Paper][Code]
[ICASSP 2021] Ego-GNNs: Exploiting Ego Structures in Graph Neural Networks [Paper]
[ICML 2021] Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks [Paper][Code]
[ICLR 2021] On Graph Neural Networks versus Graph-Augmented MLPs [Paper][Code]
[AAAI 2021] Identity-aware Graph Neural Networks [Paper]
[IJCAI 2021] The Surprising Power of Graph Neural Networks with Random Node Initialization [Paper]
[SDM 2021] Random Features Strengthen Graph Neural Networks [Paper]

[NeurIPS 2020] Can Graph Neural Networks Count Substructures? [Paper][Code]
[NeurIPS 2020] Principal Neighbourhood Aggregation for Graph Nets [Paper][Code]
[NeurIPS 2020] Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [Paper][Code]
[NeurIPS 2020] Weisfeiler and Leman Go Sparse: Towards Scalable Higher-Order Graph Embeddings [Paper][Code]
[NeurIPS 2020] Building Powerful and Equivariant Graph Neural Networks with Structural Message-Passing [Paper][Code]
[ICLR 2020] What Graph Neural Networks Cannot Learn: Depth vs Width [Paper]
[IJCAI 2020] Coloring Graph Neural Networks for Node Disambiguation [Paper]
[IJCAI 2020] Improving Attention Mechanism in Graph Neural Networks via Cardinality Preservation [Paper]

[NeurIPS 2019] On the Equivalence between Graph Isomorphism Testing and Function Approximation with GNNs [Paper][Code]
[NeurIPS 2019] Provably Powerful Graph Networks [Paper]
[ICML 2019] Relational Pooling for Graph Representations [Paper][Code]
[AAAI 2019] Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks [Paper][Code]
[ICLR 2019] How Powerful are Graph Neural Networks? [Paper][Code]