mlsanityData to 7 Oct 2026

The Descriptive Complexity of Graph Neural Networks

arXiv 2303.04613 ↗First posted 8 Mar 2023cs.LO cs.CC cs.LGcited by 26

Not on the map. Why?

Abstract (arXiv)

We analyse the power of graph neural networks (GNNs) in terms of Boolean circuit complexity and descriptive complexity. We prove that the graph queries that can be computed by a polynomial-size bounded-depth family of GNNs are exactly those definable in the guarded fragment GFO+C of first-order logic with counting and with built-in relations. This puts GNNs in the circuit complexity class (non-uniform) TC0. Remarkably, the GNN families may use arbitrary real weights and a wide class of activation functions that includes the standard ReLU, logistic "sigmoid", and hyperbolic tangent functions. If the GNNs are allowed to use random initialisation and global readout (both standard features of GNNs widely used in practice), they can compute exactly the same queries as bounded depth Boolean circuits with threshold gates, that is, exactly the queries in TC0. Moreover, we show that queries computable by a single GNN with piecewise linear activations and rational weights are definable in GFO+C without built-in relations. Therefore, they are contained in uniform TC0.

Key facts. Cited by 26 papers in the map (data through 7 Oct 2026). Builds on 13 of its 34 references that are in the map. First posted on arXiv 8 Mar 2023.

Builds on

13 of 34 references.

References · 13

  1. 2018How Powerful are Graph Neural Networks?cited by 4,355
  2. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  3. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  4. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  5. 2020Random Features Strengthen Graph Neural Networkscited by 184
  6. 2020Machine Learning on Graphs: A Model and Comprehensive Taxonomycited by 156
  7. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  8. 2021The Logic of Graph Neural Networkscited by 84
  9. 2023Some Might Say All You Need Is Sumcited by 21
  10. 2022Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networkscited by 20
  11. 2017First-Order Logic with Counting: At Least, Weak Hanf Normal Forms Always Exist and Can Be Computed!cited by 9
  12. 2022On the expressive power of message-passing neural networks as global feature map transformerscited by 8
1 more
  1. 2020Learning Concepts Described by Weight Aggregation Logiccited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 7; 2025: 11; 2026: 6.

26 papers.

Sort:

By area:

  1. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  2. 2025Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Countingcited by 17
  3. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  4. 2024Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floatscited by 13
  5. 2025Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descentcited by 8
  6. 2024Almost Surely Asymptotically Constant Graph Neural Networkscited by 7
  7. 2024Logical Distillation of Graph Neural Networkscited by 6
  8. 2024Future Directions in the Theory of Graph Machine Learningcited by 5
  9. 2024Graph Neural Networks and Arithmetic Circuitscited by 3
  10. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  11. 2025Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualizationcited by 3
  12. 2025Implicit Hypergraph Neural Networks: A Stable Framework for Higher-Order Relational Learning with Provable Guaranteescited by 3
14 more
  1. 2025A Logical View of GNN-Style Computation and the Role of Activation Functionscited by 3
  2. 2025Verifying Quantized Graph Neural Networks is PSPACE-completecited by 2
  3. 2025Improving Subgraph Matching by Combining Algorithms and Graph Neural Networkscited by 1
  4. 2025What Expressivity Theory Misses: Message Passing Complexity for GNNscited by 1
  5. 2025From Neural Networks to Logical Theories: The Correspondence between Fibring Modal Logics and Fibring Neural Networkscited by 1
  6. 2025Sound Logical Explanations for Mean Aggregation Graph Neural Networkscited by 1
  7. 2026On the Expressive Power of GNNs for Boolean Satisfiabilitycited by 1
  8. 2023The logic of rational graph neural networkscited by 0
  9. 2025Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspectivecited by 0
  10. 2026Query Languages for Machine-Learning Modelscited by 0
  11. 2026Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNscited by 0
  12. 2026Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networkscited by 0
  13. 2026Towards Understanding the Expressive Power of GNNs with Global Readoutcited by 0
  14. 2026Structural Preservation and the Logical Expressiveness of Graph Neural Networkscited by 0