Fetching the paper…
Reading the bibliography…
Message-passing graph neural networks (MPGNNs) are commonly compared with the Weisfeiler-Lehman (WL) color-refinement procedure, but this comparison does not quantify the resource parameters a network needs to realize color refinement with bounded-size messages and finite numerical precision.
The reduction of a graph to canonical form and the algebra which appears therein
Boris Weisfeiler and Andrei Leman · 1968
Earlier work this paper cites.
Universal classes of hash functions
J Lawrence Carter and Mark N Wegman · 1977
Earlier work this paper cites.
Some complexity questions related to distributive computing (preliminary report)
Andrew Chi-Chih Yao · 1979
Earlier work this paper cites.
Distributive graph algorithms-global solutions from local data
Nathan Linial · 1987
Earlier work this paper cites.
Simple constructions of almost k-wise independent random variables
Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta · 1992
Earlier work this paper cites.
Locality in distributed graph algorithms
Nathan Linial · 1992
Earlier work this paper cites.
Communication complexity
Eyal Kushilevitz and Noam Nisan · 1997
Earlier work this paper cites.
Transductive inference for text classification using support vector machines
Thorsten Joachims · 1999
Earlier work this paper cites.
Distributed computing: a locality-sensitive approach
David Peleg · 2000
Earlier work this paper cites.
The Nature of Statistical Learning Theory, Second Edition
Vladimir Naumovich Vapnik · 2000
Earlier work this paper cites.
On the communication complexity of sparse set disjointness and exists-equal problems
Mert Saglam and Gábor Tardos · 2013
Earlier work this paper cites.
Understanding Machine Learning - From Theory to Algorithms
Shai Shalev-Shwartz and Shai Ben-David · 2014
Earlier work this paper cites.
Certifying equality with limited interaction
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P Woodruff, and Grigory Yaroslavtsev · 2016
Earlier work this paper cites.
Neural message passing for quantum chemistry
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl · 2017
Earlier work this paper cites.
Inductive representation learning on large graphs
William L. Hamilton, Zhitao Ying, and Jure Leskovec · 2017
Cited alongside, same era.
Foundations of machine learning
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar · 2018
Cited alongside, same era.
Graph convolutional neural networks for web-scale recommender systems
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec · 2018
Cited alongside, same era.
Provably powerful graph networks
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman · 2019
Cited alongside, same era.
Weisfeiler and leman go neural: Higher-order graph neural networks
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe · 2019
Cited alongside, same era.
Neural graph collaborative filtering
Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua · 2019
Cited alongside, same era.
Reconstruction for powerful graph representations
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro · 2021
Later among the works it cites.
Dropgnn: Random dropouts increase the expressiveness of graph neural networks
Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer · 2021
Later among the works it cites.
Exponentially improving the complexity of simulating the weisfeiler-lehman test with graph neural networks
Anders Aamand, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer, Sandeep Silwal, and Tal Wagner · 2022
Later among the works it cites.
How powerful are k-hop message passing graph neural networks
Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang · 2022
Later among the works it cites.
Understanding and extending subgraph gnns by rethinking their symmetries
Fabrizio Frasca, Beatrice Bevilacqua, Michael M. Bronstein, and Haggai Maron · 2022
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Pushing the boundaries of molecular representation for drug discovery with the graph attention mechanism
Zhaoping Xiong, Dingyan Wang, Xiaohong Liu, Feisheng Zhong, Xiaozhe Wan, Xutong Li, Zhaojun Li, Xiaomin Luo, Kaixian Chen, Hualiang Jiang, et al · 2019
Cited alongside, same era.
How powerful are graph neural networks?
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka · 2019
Cited alongside, same era.
Subgraph neural networks
Emily Alsentzer, Samuel G. Finlayson, Michelle M. Li, and Marinka Zitnik · 2020
Cited alongside, same era.
Lightgcn: Simplifying and powering graph convolution network for recommendation
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yong-Dong Zhang, and Meng Wang · 2020
Cited alongside, same era.
The communication complexity of set intersection and multiple equality testing
Dawei Huang, Seth Pettie, Yixiang Zhang, and Zhijun Zhang · 2020
Cited alongside, same era.
The iteration number of colour refinement
Sandra Kiefer and Brendan D. McKay · 2020
Cited alongside, same era.
Expressiveness and approximation properties of graph neural networks
Floris Geerts and Juan L. Reutter · 2022
Later among the works it cites.
Extending the design space of graph neural networks by rethinking folklore weisfeiler-lehman
Jiarui Feng, Lecheng Kong, Hao Liu, Dacheng Tao, Fuhai Li, Muhan Zhang, and Yixin Chen · 2023
Later among the works it cites.
Learning skillful medium-range global weather forecasting
Remi Lam, Alvaro Sanchez-Gonzalez, Matthew Willson, Peter Wirnsberger, Meire Fortunato, Ferran Alet, Suman Ravuri, Timo Ewalds, Zach Eaton-Rosen, Weihua Hu, et al · 2023
Later among the works it cites.
Rethinking the expressive power of gnns via graph biconnectivity
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He · 2023
Later among the works it cites.
From relational pooling to subgraph gnns: A universal framework for more expressive graph neural networks
Cai Zhou, Xiyuan Wang, and Muhan Zhang · 2023
Later among the works it cites.
Distance-restricted folklore weisfeiler-leman gnns with provable cycle counting power
Junru Zhou, Jiarui Feng, Xiyuan Wang, and Muhan Zhang · 2023
Later among the works it cites.
Distributed graph algorithms
Mohsen Ghaffari · 2024
Closest in time.
Communication complexity of equality and error-correcting codes
Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan Prior, and Ilya Volkovich · 2025
Closest in time.