Built on

S. Ivanov, S. Sviridov, and E. Burnaev, “Understanding Isomorphism Bias in Graph Data Sets,” in arXiv preprint , 2019. [Online]. Available: http://arxiv.org/abs/1910.12091
Original
1910
Earlier work this paper cites.
B. Y. Weisfeiler and A. A. Leman, “The Reduction of a Graph To Canonical Form and the Algebra which Appears Therein,” pp. 1–11, 1968
1968
Earlier work this paper cites.
V. N. Vapnik and A. Y. Chervonenkis, “On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities,” Theory of Probability And Its Applications , vol. 16, no. 2, pp. 264–280, 1971
1971
Earlier work this paper cites.
L. Babai, P. Erdo˝s, and S. M. Selkow, “Random Graph Isomorphism,” SIAM Journal on Computing , vol. 9, no. 3, pp. 628–635, 1980
1980
Earlier work this paper cites.
B. Bollobás, “Distinguishing vertices of random graphs,” Annals of Discrete Mathematics , vol. 13, pp. 33–50, 1982
1982
Earlier work this paper cites.
R. Paige and R. E. Tarjan, “Three Partition Refinement Algorithms,” SIAM Journal on Computing , vol. 16, no. 6, pp. 973–989, 1987
1987
Earlier work this paper cites.
R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, “Network Motifs: Simple Building Blocks of Complex Networks,” Science , vol. 298, no. 5594, pp. 824–827, 2002
2002
Earlier work this paper cites.
A. Ben-Hur and W. S. Noble, “Kernel methods for predicting protein-protein interactions,” Bioinformatics , vol. 21, 2005
2005
Earlier work this paper cites.
G. Bouritsas, F. Frasca, S. Zafeiriou, and M. M. Bronstein, “Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting,” in Thirty-fifth Conference on Neural Information Processing Systems , 2020, pp. 1–29. [Online]. Available: http://arxiv.org/abs/2006.09252
Original
2006
Earlier work this paper cites.
C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann, “TUDataset: A collection of benchmark datasets for learning with graphs,” in Workshop on Graph Representation Learning and Beyond at ICML , 2020. [Online]. Available: http://arxiv.org/abs/2007.08663
Original
2007
Earlier work this paper cites.
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The Graph Neural Network Model,” IEEE Transactions on Neural Networks , vol. 20, no. 1, pp. 61–80, 2009
2009
Earlier work this paper cites.
N. Shervashidze and K. M. Borgwardt, “Fast subtree kernels on graphs,” Advances in Neural Information Processing Systems , pp. 1660–1668, 2009
2009
Earlier work this paper cites.
W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in Proceedings of the 31st Conference on Neural Information Processing Systems , 2017, pp. 1025–1035
2017
Earlier work this paper cites.

Similar

T. N. Kipf and M. Welling, “Semi-Supervised Classification with Graph Convolutional Networks,” in Proceedings of the 5th International Conference on Learning Representations , 2017, pp. 1–14
2017
Cited alongside, same era.
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph Attention Networks,” in Proceeding of the 6th International Conference on Learning Representations , 2018, pp. 1–12
2018
Cited alongside, same era.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How Powerful are Graph Neural Networks?” 7th International Conference on Learning Representations , pp. 1–17, 2019
2019
Cited alongside, same era.
C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe, “Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks,” in 33rd AAAI Conference on Artificial Intelligence , 2019, pp. 4602–4609
2019
Cited alongside, same era.

Then

F. Errica, M. Podda, D. Bacciu, and A. Micheli, “A Fair Comparison of Graph Neural Networks for Graph Classification,” in International Conference on Learning Representations , 2020, pp. 1–14
2020
Later among the works it cites.
M. M. Bronstein, J. Bruna, T. Cohen, and P. Veličković, “Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges,” arXiv preprint , 2021. [Online]. Available: http://arxiv.org/abs/2104.13478
Original
2021
Later among the works it cites.
P. A. Papp, K. Martinkus, L. Faber, and R. Wattenhofer, “DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks,” in Thirty-fifth Conference on Neural Information Processing Systems , 2021. [Online]. Available: http://arxiv.org/abs/2111.06283
Original
2021
Later among the works it cites.
C. Bodnar, F. Frasca, N. Otter, Y. G. Wang, P. Liò, G. Montúfar, and M. Bronstein, “Weisfeiler and Lehman Go Cellular: CW Networks,” in Thirty-fifth Conference on Neural Information Processing Systems , 2021, pp. 1–28
2021
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2022

1-WL Expressiveness Is (Almost) All You Need

Zopf, Markus

Understand

It has been shown that a message passing neural networks (MPNNs), a popular family of neural networks for graph-structured data, are at most as expressive as the first-order Weisfeiler-Leman (1-WL) graph isomorphism test, which has motivated the development of more expressive architectures.

In this work, we analyze if the limited expressiveness is actually a limiting factor for MPNNs and other WL-based models in standard graph datasets.
Interestingly, we find that the expressiveness of WL is sufficient to identify almost all graphs in most datasets.
Moreover, we find that the classification accuracy upper bounds are often close to 100\%.

Built on

S. Ivanov, S. Sviridov, and E. Burnaev, “Understanding Isomorphism Bias in Graph Data Sets,” in arXiv preprint , 2019. [Online]. Available: http://arxiv.org/abs/1910.12091
Original
1910
Earlier work this paper cites.
B. Y. Weisfeiler and A. A. Leman, “The Reduction of a Graph To Canonical Form and the Algebra which Appears Therein,” pp. 1–11, 1968
1968
Earlier work this paper cites.
V. N. Vapnik and A. Y. Chervonenkis, “On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities,” Theory of Probability And Its Applications , vol. 16, no. 2, pp. 264–280, 1971
1971
Earlier work this paper cites.
L. Babai, P. Erdo˝s, and S. M. Selkow, “Random Graph Isomorphism,” SIAM Journal on Computing , vol. 9, no. 3, pp. 628–635, 1980
1980
Earlier work this paper cites.
B. Bollobás, “Distinguishing vertices of random graphs,” Annals of Discrete Mathematics , vol. 13, pp. 33–50, 1982
1982
Earlier work this paper cites.
R. Paige and R. E. Tarjan, “Three Partition Refinement Algorithms,” SIAM Journal on Computing , vol. 16, no. 6, pp. 973–989, 1987
1987
Earlier work this paper cites.
R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, “Network Motifs: Simple Building Blocks of Complex Networks,” Science , vol. 298, no. 5594, pp. 824–827, 2002
2002
Earlier work this paper cites.
A. Ben-Hur and W. S. Noble, “Kernel methods for predicting protein-protein interactions,” Bioinformatics , vol. 21, 2005
2005
Earlier work this paper cites.
G. Bouritsas, F. Frasca, S. Zafeiriou, and M. M. Bronstein, “Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting,” in Thirty-fifth Conference on Neural Information Processing Systems , 2020, pp. 1–29. [Online]. Available: http://arxiv.org/abs/2006.09252
Original
2006
Earlier work this paper cites.
C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann, “TUDataset: A collection of benchmark datasets for learning with graphs,” in Workshop on Graph Representation Learning and Beyond at ICML , 2020. [Online]. Available: http://arxiv.org/abs/2007.08663
Original
2007
Earlier work this paper cites.
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The Graph Neural Network Model,” IEEE Transactions on Neural Networks , vol. 20, no. 1, pp. 61–80, 2009
2009
Earlier work this paper cites.
N. Shervashidze and K. M. Borgwardt, “Fast subtree kernels on graphs,” Advances in Neural Information Processing Systems , pp. 1660–1668, 2009
2009
Earlier work this paper cites.
W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in Proceedings of the 31st Conference on Neural Information Processing Systems , 2017, pp. 1025–1035
2017
Earlier work this paper cites.

Similar

T. N. Kipf and M. Welling, “Semi-Supervised Classification with Graph Convolutional Networks,” in Proceedings of the 5th International Conference on Learning Representations , 2017, pp. 1–14
2017
Cited alongside, same era.
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph Attention Networks,” in Proceeding of the 6th International Conference on Learning Representations , 2018, pp. 1–12
2018
Cited alongside, same era.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How Powerful are Graph Neural Networks?” 7th International Conference on Learning Representations , pp. 1–17, 2019
2019
Cited alongside, same era.
C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe, “Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks,” in 33rd AAAI Conference on Artificial Intelligence , 2019, pp. 4602–4609
2019
Cited alongside, same era.

Then

F. Errica, M. Podda, D. Bacciu, and A. Micheli, “A Fair Comparison of Graph Neural Networks for Graph Classification,” in International Conference on Learning Representations , 2020, pp. 1–14
2020
Later among the works it cites.
M. M. Bronstein, J. Bruna, T. Cohen, and P. Veličković, “Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges,” arXiv preprint , 2021. [Online]. Available: http://arxiv.org/abs/2104.13478
Original
2021
Later among the works it cites.
P. A. Papp, K. Martinkus, L. Faber, and R. Wattenhofer, “DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks,” in Thirty-fifth Conference on Neural Information Processing Systems , 2021. [Online]. Available: http://arxiv.org/abs/2111.06283
Original
2021
Later among the works it cites.
C. Bodnar, F. Frasca, N. Otter, Y. G. Wang, P. Liò, G. Montúfar, and M. Bronstein, “Weisfeiler and Lehman Go Cellular: CW Networks,” in Thirty-fifth Conference on Neural Information Processing Systems , 2021, pp. 1–28
2021
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

J. B. Lee, S. Kim, R. A. Rossi, E. Koh, X. Kong, and A. Rao, “Graph convolutional networks with motif-based attention,” International Conference on Information and Knowledge Management, Proceedings , pp. 499–508, 2019

2019

Cited alongside, same era.

H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman, “Provably Powerful Graph Networks,” in 33rd Conference on Neural Information Processing Systems , 2019

2019

Cited alongside, same era.

Z. Chen, S. Villar, L. Chen, and J. Bruna, “On the equivalence between graph isomorphism testing and function approximation with GNNs,” Advances in Neural Information Processing Systems , vol. 32, no. NeurIPS, pp. 1–9, 2019

2019

Cited alongside, same era.

A. Loukas, “What graph neural networks cannot learn: depth vs width,” in International Conference on Learning Representations , 2020

2020

Cited alongside, same era.

——, “How hard is to distinguish graphs with graph neural networks?” in Thirty-fourth Conference on Neural Information Processing Systems , 2020

2020

Cited alongside, same era.

V. P. Dwivedi, C. K. Joshi, T. Laurent, Y. Bengio, and X. Bresson, “Benchmarking Graph Neural Networks,” in arXiv preprint , 2020

2020

Cited alongside, same era.

S. Kiefer, “Power and Limits of the Weisfeiler-Leman Algorithm,” Disseration, RWTH Aachen University, 2020

2020

Cited alongside, same era.

V. K. Garg, S. Jegelka, and T. Jaakkola, “Generalization and representational limits of graph neural networks,” Proceedings of the 37th International Conference on Machine Learning , pp. 3377–3388, 2020

2020

Cited alongside, same era.

C. Bodnar, F. Frasca, Y. Guang, N. Otter, G. Mont, and P. Li, “Weisfeiler and Lehman Go Topological : Message Passing Simplicial Networks,” in Proceedings of the 38th International Conference on Machine Learning , 2021

2021