pith. sign in

arxiv: 2410.01308 · v6 · submitted 2024-10-02 · 💻 cs.LG · cs.AI

How Hard Is It for Message-Passing GNNs to Simulate One Weisfeiler-Lehman Color-Refinement Step?

Guanyu Cui , Yuhe Guo , Zhewei Wei , Hsin-Hao Su This is my paper

Pith reviewed 2026-05-23 19:47 UTC · model grok-4.3

classification 💻 cs.LG cs.AI
keywords graph neural networksWeisfeiler-Lehman algorithmmessage passingcolor refinementoblivious simulationcomputational complexityrandomness in GNNs
0
0 comments X

The pith

Oblivious message-passing GNNs cannot simulate one Weisfeiler-Lehman color refinement step with shallow depth and small messages unless randomness is allowed.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper quantifies the resources message-passing graph neural networks need to perform one step of Weisfeiler-Lehman color refinement on unattributed graphs. It separates input-independent oblivious simulation, where parameters are fixed in advance, from instance-dependent simulation that can use graph-specific parameters. In the oblivious regime deterministic and zero-error randomized networks require either greater depth or larger messages to succeed in the worst case. Bounded-error randomness reduces the cost to a single layer with logarithmic message size when the number of colors is large, yet the same logarithmic number of random bits is necessary. Small color sets force an unavoidable layer-versus-message-size tradeoff even in stronger models.

Core claim

The local aggregation performed by message-passing GNNs must solve an underlying global relabeling problem to realize Weisfeiler-Lehman color refinement, and this problem cannot be solved obliviously by deterministic or zero-error networks without sufficient depth or message size; bounded-error randomness suffices for large color sets in one layer while small color sets demand explicit resource trade-offs.

What carries the argument

The oblivious versus instance-dependent distinction that governs whether network parameters may depend on the input graph before simulation begins.

If this is right

  • Deterministic oblivious MPGNNs fail to simulate color refinement on some graphs unless depth or message size grows with graph size.
  • A one-layer MPGNN with logarithmic message size and logarithmic random bits succeeds when the color set is large.
  • The same logarithmic number of random bits is required for any shallow small-message simulation even with bounded error.
  • Rooted port-aware models admit nearly matching upper bounds that nearly close the gap for the oblivious case.
  • Instance-dependent simulation can be performed with far fewer layers, but the required parameters are not guaranteed to be easy to compute.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Designers of practical GNNs may need mechanisms that adapt parameters to each graph or inject controlled randomness to reach WL-level refinement in few layers.
  • The hidden global relabeling task suggests that color refinement cost could be studied through communication or distributed computing lenses.
  • For applications that rely on repeated WL iterations, the per-step cost established here implies that full WL simulation may accumulate substantial depth or randomness requirements.

Load-bearing premise

The analysis assumes simulation parameters must be chosen independently of the specific input graph.

What would settle it

An explicit family of graphs together with a fixed shallow network and fixed small message size that correctly produces the new color partition for every possible initial coloring on those graphs would falsify the oblivious lower bound.

Figures

Figures reproduced from arXiv: 2410.01308 by Guanyu Cui, Hsin-Hao Su, Yuhe Guo, Zhewei Wei.

Figure 1
Figure 1. Figure 1: The three phases of computation in GNNs under the RL-CONGEST model. Left: Given an [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Relevant complexity classes and problems. [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A path graph and a cycle graph that differ only by the edge [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The constructed basic graph G(n,m) . Nodes are colored according to x. Alice and Bob also fix a bijection c between the set of pairs hlm n mi × [n] and the set h n · lm n mi8 . For example, define c((i, j)) = (i − 1)n + j and c −1 (i) =  i n  ,(i − 1) mod n + 1 . Given an instance (a, b) ∈ {0, 1} m × {0, 1} m of EQm, Alice receives a = (a1, a2, · · · , am) and Bob receives b = (b1, b2, · · · , bm), the… view at source ↗
read the original abstract

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. We study the cost of simulating a single color-refinement step on unattributed graphs. We distinguish input-independent, or oblivious, simulation from instance-dependent simulation. In the former, the parameters, or their distributions in randomized models, are fixed before the input instance is known. Our results show that the local form of WL color refinement hides a global relabeling problem. In the oblivious setting, deterministic and zero-error randomized MPGNNs cannot solve this problem in the worst case using only shallow networks with small messages. We complement this lower bound with a nearly matching construction in a stronger rooted, port-aware model. By contrast, when the color set is large, bounded-error randomness can greatly reduce the cost, and a one-layer MPGNN with messages of logarithmic size and a logarithmic number of random bits suffices. We show that this logarithmic number of random bits is essentially necessary for shallow, small-message simulations. When the color set is small, we still obtain a rooted, port-aware simulation, but this construction requires more layers or larger messages. We also prove that this extra cost is partly unavoidable, as small color sets force a nontrivial trade-off between the number of layers and the message size. Finally, instance-dependent simulation can be much shallower, but the required instance-specific parameters are not necessarily easy to find. Together, these results reveal quantitative structure hidden behind the statement that MPGNNs match WL color refinement.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper examines the resource requirements (depth, message size, randomness) for message-passing GNNs to simulate a single Weisfeiler-Lehman color-refinement step on unattributed graphs. It distinguishes oblivious simulation (parameters or distributions fixed before the input is known) from instance-dependent simulation. In the oblivious regime the authors prove that deterministic and zero-error randomized MPGNNs cannot achieve worst-case simulation with shallow depth and small messages, supply a nearly matching construction in a stronger rooted port-aware model, show that bounded-error randomness reduces the cost to one layer with logarithmic message size and random bits when the color set is large, establish necessity of the logarithmic randomness, and prove layer/message-size trade-offs for small color sets. Instance-dependent simulation can be shallower but requires instance-specific parameters that are not necessarily easy to obtain.

Significance. If the results hold, the work supplies the first quantitative resource analysis of the MPGNN-WL relationship, exposing that the ostensibly local WL step conceals a global relabeling problem whose cost is governed by the oblivious/instance-dependent distinction and the availability of randomness. The explicit lower-bound arguments, matching constructions, and contrasting upper bounds constitute clear strengths; they furnish falsifiable predictions about model depth and message size that go beyond qualitative expressivity comparisons. The separation of regimes is particularly useful for clarifying when MPGNNs can or cannot efficiently realize WL steps.

minor comments (3)
  1. [Abstract] Abstract: the statement that 'a one-layer MPGNN with messages of logarithmic size and a logarithmic number of random bits suffices' should be cross-referenced to the precise theorem (including the dependence on color-set cardinality) so that readers can immediately locate the formal claim.
  2. [Introduction] The distinction between oblivious and instance-dependent parameter regimes is central; a short illustrative example early in the introduction would help readers see why the lower bounds apply only in the former regime.
  3. Notation for message alphabets, port labels, and random-bit usage should be unified across the lower-bound and upper-bound statements to avoid minor inconsistencies in variable names.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment, the clear summary of our contributions, and the recommendation for minor revision. We are glad that the distinction between oblivious and instance-dependent simulation, the role of randomness, and the quantitative lower bounds are viewed as useful for clarifying the MPGNN-WL relationship.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper establishes lower bounds on depth and message size for oblivious deterministic/zero-error MPGNN simulation of one WL step via direct combinatorial arguments on hidden global relabeling, complemented by explicit constructions in rooted port-aware models and separate upper bounds using bounded-error randomness for large color sets. These steps rely on fresh analysis of the oblivious regime (parameters fixed before input) versus instance-dependent simulation, with no reduction of any claimed result to fitted inputs, self-definitions, or load-bearing self-citations. The central claims are conditioned on the stated distinction and do not invoke prior author work as an unverified uniqueness theorem or ansatz.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard domain assumptions about message-passing with bounded message size and finite precision; no free parameters are fitted to data because the work is a complexity-theoretic analysis rather than an empirical fit.

axioms (2)
  • domain assumption MPGNNs operate with bounded-size messages and finite numerical precision on unattributed graphs.
    Explicitly stated as the setting under study.
  • domain assumption The distinction between oblivious (input-independent) and instance-dependent simulation is a meaningful and well-defined separation for resource analysis.
    Central organizing distinction of the paper.

pith-pipeline@v0.9.0 · 5855 in / 1541 out tokens · 68782 ms · 2026-05-23T19:47:00.104406+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

93 extracted references · 93 canonical work pages · 2 internal anchors

  1. [1]

    Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer, Sandeep Silwal, and Tal Wagner

    Anders Aamand, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer, Sandeep Silwal, and Tal Wagner. Exponentially improving the complexity of simulating the weisfeiler- lehman test with graph neural networks. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors,Advances in Neural Information ...

    work page 2022

  2. [2]

    The surprising power of graph neural networks with random node initialization

    Ralph Abboud, İsmail İlkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Zhi-Hua Zhou, editor,Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 2112–2118. ijcai.org, 2021

    work page 2021

  3. [3]

    Finlayson, Michelle M

    Emily Alsentzer, Samuel G. Finlayson, Michelle M. Li, and Marinka Zitnik. Subgraph neural networks. In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 20...

    work page 2020

  4. [4]

    Diffwire: Inductive graph rewiring via the lovász bound

    Adrián Arnaiz-Rodríguez, Ahmed Begga, Francisco Escolano, and Nuria Oliver. Diffwire: Inductive graph rewiring via the lovász bound. In Bastian Rieck and Razvan Pascanu, editors,Learning on Graphs Conference, LoG 2022, 9-12 December 2022, Virtual Event, volume 198 ofProceedings of Machine Learning Research, page 15. PMLR, 2022

    work page 2022

  5. [5]

    Expressive power of invariant and equivariant graph neural networks

    Waïss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural networks. In9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021

    work page 2021

  6. [6]

    Kostylev, Mikaël Monet, Jorge Pérez, Juan L

    Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020

    work page 2020

  7. [7]

    Graph neural networks and arithmetic circuits

    Timon Barlag, Vivian Holzapfel, Laura Strieker, Jonni Virtema, and Heribert Vollmer. Graph neural networks and arithmetic circuits. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors,Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Process...

    work page 2024

  8. [8]

    Towards invariance to node identifiers in graph neural networks.CoRR, abs/2502.13660, 2025

    Maya Bechler-Speicher, Moshe Eliasof, Carola-Bibiane Schönlieb, Ran Gilad-Bachrach, and Amir Globerson. Towards invariance to node identifiers in graph neural networks.CoRR, abs/2502.13660, 2025

    work page arXiv 2025

  9. [9]

    Understanding oversquashing in gnns through the lens of effective resistance

    Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors,International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume ...

    work page 2023

  10. [10]

    Bronstein

    Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting.IEEE Trans. Pattern Anal. Mach. Intell., 45(1):657–668, 2023

    work page 2023

  11. [11]

    An optimal lower bound on the number of variables for graph identification

    Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. In30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 612–617. IEEE Computer Society, 1989. 13

    work page 1989

  12. [12]

    Deterministic expander routing: Faster and more versatile

    Yi-Jun Chang, Shang-En Huang, and Hsin-Hao Su. Deterministic expander routing: Faster and more versatile. In Ran Gelles, Dennis Olivetti, and Petr Kuznetsov, editors,Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC 2024, Nantes, France, June 17-21, 2024, pages 194–204. ACM, 2024

    work page 2024

  13. [13]

    Siegelmann

    Stephen Chung and Hava T. Siegelmann. Turing completeness of bounded-precision recurrent neural networks. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jen- nifer Wortman Vaughan, editors,Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, Dece...

    work page 2021

  14. [14]

    Reconstruction for powerful graph representa- tions

    Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph representa- tions. In Marc’Aurelio Ranzato, AlinaBeygelzimer, Yann N. Dauphin, PercyLiang, and JenniferWortman Vaughan, editors,Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, Decembe...

    work page 2021

  15. [15]

    Approximation by superpositions of a sigmoidal function.Math

    George Cybenko. Approximation by superpositions of a sigmoidal function.Math. Control. Signals Syst., 2(4):303–314, 1989

    work page 1989

  16. [16]

    Expander graph propagation

    Andreea Deac, Marc Lackenby, and Petar Velickovic. Expander graph propagation. In Bastian Rieck and Razvan Pascanu, editors,Learning on Graphs Conference, LoG 2022, 9-12 December 2022, Virtual Event, volume 198 ofProceedings of Machine Learning Research, page 38. PMLR, 2022

    work page 2022

  17. [17]

    How powerful are k-hop message passing graph neural networks

    Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors,Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orl...

    work page 2022

  18. [18]

    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. Extending the design space of graph neural networks by rethinking folklore weisfeiler-lehman. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors,Advances in Neural Information Processing Systems 36: Annual Conference on ...

    work page 2023

  19. [19]

    Fast Graph Representation Learning with PyTorch Geometric

    Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric.CoRR, abs/1903.02428, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1903

  20. [20]

    Bronstein, and Haggai Maron

    Fabrizio Frasca, Beatrice Bevilacqua, Michael M. Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors,Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022,...

    work page 2022

  21. [21]

    M. R. Garey and David S. Johnson.Computers and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman, 1979

    work page 1979

  22. [22]

    Garg, Stefanie Jegelka, and Tommi S

    Vikas K. Garg, Stefanie Jegelka, and Tommi S. Jaakkola. Generalization and representational limits of graph neural networks. InProceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 ofProceedings of Machine Learning Research, pages 3419–3430. PMLR, 2020

    work page 2020

  23. [23]

    Floris Geerts and Juan L. Reutter. Expressiveness and approximation properties of graph neural networks. InThe Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022

    work page 2022

  24. [24]

    Distributed graph algorithms

    Mohsen Ghaffari. Distributed graph algorithms. Course Notes for Distributed Algorithms, 2022. Accessed: September, 2024. 14

    work page 2022

  25. [25]

    New distributed algorithms in almost mixing time via transformations from parallel algorithms

    Mohsen Ghaffari and Jason Li. New distributed algorithms in almost mixing time via transformations from parallel algorithms. In Ulrich Schmid and Josef Widder, editors,32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, volume 121 ofLIPIcs, pages 31:1–31:16. Schloss Dagstuhl - Leibniz-Zentrum für In...

    work page 2018

  26. [26]

    Schoenholz, Patrick F

    Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Teh, editors,Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 ofProceedings of Machine Learning Research, pa...

    work page 2017

  27. [27]

    Gripenberg

    G. Gripenberg. Approximation by neural networks with a bounded number of nodes at each level.J. Approx. Theory, 122(2):260–266, 2003

    work page 2003

  28. [28]

    Finite variable logics in descriptive complexity theory.Bull

    Martin Grohe. Finite variable logics in descriptive complexity theory.Bull. Symb. Log., 4(4):345–398, 1998

    work page 1998

  29. [29]

    Cambridge University Press, 2017

    Martin Grohe.Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, volume 47 ofLecture Notes in Logic. Cambridge University Press, 2017

    work page 2017

  30. [30]

    The descriptive complexity of graph neural networks

    Martin Grohe. The descriptive complexity of graph neural networks. In38th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2023, Boston, MA, USA, June 26-29, 2023, pages 1–14. IEEE, 2023

    work page 2023

  31. [31]

    Efficient algorithms for spanning tree centrality

    Takanori Hayashi, Takuya Akiba, and Yuichi Yoshida. Efficient algorithms for spanning tree centrality. In Subbarao Kambhampati, editor,Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pages 3733–3739. IJCAI/AAAI Press, 2016

    work page 2016

  32. [32]

    Spectral gaps of random graphs and applications.International Mathematics Research Notices, 2021(11):8353–8404, 2021

    Christopher Hoffman, Matthew Kahle, and Elliot Paquette. Spectral gaps of random graphs and applications.International Mathematics Research Notices, 2021(11):8353–8404, 2021

    work page 2021

  33. [33]

    Approximation capabilities of multilayer feedforward networks.Neural Networks, 4(2):251– 257, 1991

    Kurt Hornik. Approximation capabilities of multilayer feedforward networks.Neural Networks, 4(2):251– 257, 1991

    work page 1991

  34. [34]

    Stinchcombe, and Halbert White

    Kurt Hornik, Maxwell B. Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators.Neural Networks, 2(5):359–366, 1989

    work page 1989

  35. [35]

    A short tutorial on the weisfeiler-lehman test and its variants

    Ningyuan Teresa Huang and Soledad Villar. A short tutorial on the weisfeiler-lehman test and its variants. InIEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2021, Toronto, ON, Canada, June 6-11, 2021, pages 8533–8537. IEEE, 2021

    work page 2021

  36. [36]

    An analysis of virtual nodes in graph neural networks for link prediction (extended abstract)

    EunJeong Hwang, Veronika Thost, Shib Sankar Dasgupta, and Tengfei Ma. An analysis of virtual nodes in graph neural networks for link prediction (extended abstract). InThe First Learning on Graphs Conference, 2022

    work page 2022

  37. [37]

    Banerjee, and Guido Montúfar

    Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montúfar. Fosr: First-order spectral rewiring for addressing oversquashing in gnns. InThe Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023

    work page 2023

  38. [38]

    Patrick Kidger and Terry J. Lyons. Universal approximation with deep narrow networks. In Jacob D. Abernethy and Shivani Agarwal, editors,Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 ofProceedings of Machine Learning Research, pages 2306–2327. PMLR, 2020

    work page 2020

  39. [39]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017

    work page 2017

  40. [40]

    D. J. Klein and M. Randić. Resistance distance.Journal of Mathematical Chemistry, 12(1):81–95, Dec 1993. 15

    work page 1993

  41. [41]

    Cambridge University Press, 1997

    Eyal Kushilevitz and Noam Nisan.Communication complexity. Cambridge University Press, 1997

    work page 1997

  42. [42]

    Lin, Allan Pinkus, and Shimon Schocken

    Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function.Neural Networks, 6(6):861–867, 1993

    work page 1993

  43. [43]

    On the computational capability of graph neural networks: A circuit complexity bound perspective.CoRR, abs/2501.06444, 2025

    Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Wei Wang, and Jiahao Zhang. On the computational capability of graph neural networks: A circuit complexity bound perspective.CoRR, abs/2501.06444, 2025

    work page arXiv 2025

  44. [44]

    Distributive graph algorithms-global solutions from local data

    Nathan Linial. Distributive graph algorithms-global solutions from local data. In28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, pages 331–335. IEEE Computer Society, 1987

    work page 1987

  45. [45]

    Locality in distributed graph algorithms.SIAM J

    Nathan Linial. Locality in distributed graph algorithms.SIAM J. Comput., 21(1):193–201, 1992

    work page 1992

  46. [46]

    What graph neural networks cannot learn: depth vs width

    Andreas Loukas. What graph neural networks cannot learn: depth vs width. In8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. Open- Review.net, 2020

    work page 2020

  47. [47]

    Random walks on graphs.Combinatorics, Paul erdos is eighty, 2(1-46):4, 1993

    László Lovász. Random walks on graphs.Combinatorics, Paul erdos is eighty, 2(1-46):4, 1993

    work page 1993

  48. [48]

    The expressive power of neural networks: A view from the width

    Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors,Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information P...

    work page 2017

  49. [49]

    Provably powerful graph networks

    Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors,Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, Decem...

    work page 2019

  50. [50]

    Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe

    Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, T...

    work page 2019

  51. [51]

    Dropgnn: Random dropouts increase the expressiveness of graph neural networks

    Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors,Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information ...

    work page 2021

  52. [52]

    Society for Industrial and Applied Mathematics, USA, 2000

    David Peleg.Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, USA, 2000

    work page 2000

  53. [53]

    Borgwardt

    Paolo Pellizzoni, Till Hendrik Schulz, Dexiong Chen, and Karsten M. Borgwardt. On the expressivity and sample complexity of node-individualized graph neural networks. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors,Advances in Neural Information Processing Systems 38: Annual Confe...

    work page 2024

  54. [54]

    Fast computation of small cuts via cycle space sampling

    David Pritchard and Ramakrishna Thurimella. Fast computation of small cuts via cycle space sampling. ACM Trans. Algorithms, 7(4):46:1–46:30, 2011. 16

    work page 2011

  55. [55]

    PhD thesis, Massachusetts Institute of Technology, 2005

    David David Alexander Griffith Pritchard.Robust network computation. PhD thesis, Massachusetts Institute of Technology, 2005

    work page 2005

  56. [56]

    Distinguished in uniform: Self-attention vs

    Eran Rosenbluth, Jan Tönshoff, Martin Ritzert, Berke Kisin, and Martin Grohe. Distinguished in uniform: Self-attention vs. virtual nodes. InThe Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024

    work page 2024

  57. [57]

    Random features strengthen graph neural networks

    Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. InCarlottaDemeniconiandIanDavidson, editors,Proceedings of the 2021 SIAM International Conference on Data Mining, SDM 2021, Virtual Event, April 29 - May 1, 2021, pages 333–341. SIAM, 2021

    work page 2021

  58. [58]

    Siegelmann and Eduardo D

    Hava T. Siegelmann and Eduardo D. Sontag. On the computational power of neural nets. In David Haussler, editor,Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, COLT 1992, Pittsburgh, PA, USA, July 27-29, 1992, pages 440–449. ACM, 1992

    work page 1992

  59. [59]

    Towards understanding generalization of graph neural networks

    Huayi Tang and Yong Liu. Towards understanding generalization of graph neural networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors,International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 ofProceedings of Machine Learning Research, pa...

    work page 2023

  60. [60]

    Depth-first search and linear graph algorithms.SIAM J

    Robert Endre Tarjan. Depth-first search and linear graph algorithms.SIAM J. Comput., 1(2):146–160, 1972

    work page 1972

  61. [61]

    Thiede, Wenda Zhou, and Risi Kondor

    Erik H. Thiede, Wenda Zhou, and Risi Kondor. Autobahn: Automorphism-based graph neural nets. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors,Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021...

    work page 2021

  62. [62]

    PP is as hard as the polynomial-time hierarchy.SIAM J

    Seinosuke Toda. PP is as hard as the polynomial-time hierarchy.SIAM J. Comput., 20(5):865–877, 1991

    work page 1991

  63. [63]

    Bronstein

    Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. InThe Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022

    work page 2022

  64. [64]

    Leslie G. Valiant. The complexity of enumeration and reliability problems.SIAM J. Comput., 8(3):410– 421, 1979

    work page 1979

  65. [65]

    Graph attention networks

    Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018

    work page 2018

  66. [66]

    Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks

    Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, Ziyue Huang, Qipeng Guo, Hao Zhang, Haibin Lin, Junbo Zhao, Jinyang Li, Alexander J. Smola, and Zheng Zhang. Deep graph library: Towards efficient and scalable deep learning on graphs. CoRR, abs/1909.01315, 2019

    work page internal anchor Pith review arXiv 1909

  67. [67]

    How powerful are spectral graph neural networks

    Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In Kamalika Chaud- huri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors,International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 ofProceedings of Machine Learning Research, pages 23341–23362....

    work page 2022

  68. [68]

    The reduction of a graph to canonical form and the algebra which appears therein.nti, Series, 2(9):12–16, 1968

    Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein.nti, Series, 2(9):12–16, 1968

    work page 1968

  69. [69]

    Expressivity and generalization: Fragment-biases for molecular gnns

    Tom Wollschläger, Niklas Kemper, Leon Hetzel, Johanna Sommer, and Stephan Günnemann. Expressivity and generalization: Fragment-biases for molecular gnns. InForty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. 17

    work page 2024

  70. [70]

    How powerful are graph neural networks? In7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019

    work page 2019

  71. [71]

    Some complexity questions related to distributive computing(preliminary report)

    Andrew Chi-Chih Yao. Some complexity questions related to distributive computing(preliminary report). InProceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC ’79, pages 209–213, New York, NY, USA, 1979. Association for Computing Machinery

    work page 1979

  72. [72]

    Error bounds for approximations with deep relu networks.Neural Networks, 94:103–114, 2017

    Dmitry Yarotsky. Error bounds for approximations with deep relu networks.Neural Networks, 94:103–114, 2017

    work page 2017

  73. [73]

    Rethinking the expressive power of gnns via graph biconnectivity

    Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. InThe Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023

    work page 2023

  74. [74]

    From relational pooling to subgraph gnns: A universal framework for more expressive graph neural networks

    Cai Zhou, Xiyuan Wang, and Muhan Zhang. From relational pooling to subgraph gnns: A universal framework for more expressive graph neural networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors,International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA...

    work page 2023

  75. [75]

    For node u, determine if there are two neighboring nodess and t such that R(s, u) + R(u, t) = R(s, t)

    Junru Zhou, Jiarui Feng, Xiyuan Wang, and Muhan Zhang. Distance-restricted folklore weisfeiler-leman gnns with provable cycle counting power. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors,Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 20...

    work page 2023

  76. [76]

    For example, definec((i, j)) = (i−1)n+jandc −1(i) = i n ,(i−1) modn+ 1 . Given an instance(a,b ) ∈ {0, 1}m × {0, 1}m of EQm, Alice receivesa = (a1,a 2,· · ·,a m)and Bob receives b= (b 1,b 2,· · ·,b m), they completeG(n,m) toG (n,m);(a,b) withΘ(n)nodes andΘ(m)edges as follows: • For eachk∈ { 1, 2,· · ·, m} , let( i, j) = c−1(k). If ak = 0, Alice adds edge(...

    work page

  77. [77]

    This process takesO(1)rounds

    Each node u sends a message(u,x u)to its neighbors and receives messages from them to form the set Su ={(u, v,x v) :v∈N(u)∪ {u}}. This process takesO(1)rounds

    work page

  78. [78]

    This process takesO(D)rounds

    Node1initiates theFloodalgorithm to construct a BFS spanning tree rooted at node1. This process takesO(D)rounds

    work page

  79. [79]

    This process takes O D+ m w rounds, as there areP u∈V O(du) = O(m)messages to gather, and each edge can transmitwmessages per round

    TheUpcastalgorithm is used to collect all sets Su at the root node1along the spanning tree. This process takes O D+ m w rounds, as there areP u∈V O(du) = O(m)messages to gather, and each edge can transmitwmessages per round

    work page

  80. [80]

    This step can be completed in one round and requiresO(m)time, since there areO(m)tuples inS u Su

    Node1merges allS u to form the set K={(u,(x u,{ {xv :v∈N(u)} })) :u∈V}. This step can be completed in one round and requiresO(m)time, since there areO(m)tuples inS u Su

    work page

Showing first 80 references.