mlsanityData to 14 Oct 2026

The logic of rational graph neural networks

arXiv 2310.13139 ↗First posted 19 Oct 2023cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

The expressivity of Graph Neural Networks (GNNs) can be described via appropriate fragments of the first order logic. Any query of the two variable fragment of graded modal logic (GC2) interpreted over labeled graphs can be expressed using a Rectified Linear Unit (ReLU) GNN whose size does not grow with graph input sizes [Barcelo & Al., 2020]. Conversely, a GNN expresses at most a query of GC2, for any choice of activation function. In this article, we prove that some GC2 queries of depth 3 cannot be expressed by GNNs with any rational activation function. This shows that not all non-polynomial activation functions confer GNNs maximal expressivity, answering a open question formulated by [Grohe, 2021]. This result is also in contrast with the efficient universal approximation properties of rational feedforward neural networks investigated by [Boull'e & Al., 2020]. We also present a rational subfragment of the first order logic (RGC2), and prove that rational GNNs can express RGC2 queries uniformly over all graphs.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 14 of its 21 references that are in the map. First posted on arXiv 19 Oct 2023.

Builds on

14 of 21 references.

References · 14

  1. 2018How Powerful are Graph Neural Networks?cited by 4,393
  2. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  3. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  4. 2022Graph neural networks for materials science and chemistrycited by 182
  5. 2021The Logic of Graph Neural Networkscited by 85
  6. 2020Rational neural networkscited by 75
  7. 2022MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solverscited by 49
  8. 2022PaSca: a Graph Neural Architecture Search System under the Scalable Paradigmcited by 37
  9. 2021Graph Neural Network Reinforcement Learning for Autonomous Mobility-on-Demand Systemscited by 28
  10. 2023The Descriptive Complexity of Graph Neural Networkscited by 26
  11. 2022Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networkscited by 21
  12. 2023Some Might Say All You Need Is Sumcited by 21
2 more
  1. 2021Decoding the Protein-ligand Interactions Using Parallel Graph Neural Networkscited by 10
  2. 2023On the power of graph neural networks and the role of the activation functioncited by 8

Built on by

Not cited yet.