Expressive Power of Graph Transformers via Logic

• URL: http://arxiv.org/abs/2508.01067v1
• Date: Fri, 01 Aug 2025 20:59:13 GMT
• Title: Expressive Power of Graph Transformers via Logic
• Authors: Veeti Ahvonen, Maurice Funk, Damian Heiman, Antti Kuusisto, Carsten Lutz,
• Abstract summary: We study the expressive power of graph transformers (GTs) by Dwivedi and Bresson ( 2020) and GPS-networks by Ramp'asek et al. (2022)<n>With reals, we show that GPS-networks have the same expressive power as graded modal logic (GML) with the global modality.<n>With floats, GPS-networks turn out to be equally expressive as GML with the counting global modality.
• Score: 7.89576199021427
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Transformers are the basis of modern large language models, but relatively little is known about their precise expressive power on graphs. We study the expressive power of graph transformers (GTs) by Dwivedi and Bresson (2020) and GPS-networks by Ramp\'asek et al. (2022), both under soft-attention and average hard-attention. Our study covers two scenarios: the theoretical setting with real numbers and the more practical case with floats. With reals, we show that in restriction to vertex properties definable in first-order logic (FO), GPS-networks have the same expressive power as graded modal logic (GML) with the global modality. With floats, GPS-networks turn out to be equally expressive as GML with the counting global modality. The latter result is absolute, not restricting to properties definable in a background logic. We also obtain similar characterizations for GTs in terms of propositional logic with the global modality (for reals) and the counting global modality (for floats).

Related papers

• Size Transferability of Graph Transformers with Convolutional Positional Encodings [82.27361992510494]
  Graph Transformers (GTs) are attention-based architectures for graph-structured data.<n>We study GTs through the lens of manifold limit models for graph sequences.<n>We show that GTs inherit transferability guarantees from their positional encodings.
  arXiv  Detail & Related papers  (2026-02-16T22:38:56Z)
• The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic [8.430502131775723]
  We propose GNN architectures that correspond precisely to prominent fragments of first-order logic (FO)<n>Our results provide a unifying framework for understanding the logical expressiveness of GNNs within FO.
  arXiv  Detail & Related papers  (2025-05-12T19:45:45Z)
• Plain Transformers Can be Powerful Graph Learners [64.50059165186701]
  Researchers have attempted to migrate Transformers to graph learning, but most advanced Graph Transformers have strayed far from plain Transformers.<n>This work demonstrates that the plain Transformer architecture can be a powerful graph learner.
  arXiv  Detail & Related papers  (2025-04-17T02:06:50Z)
• Learning Efficient Positional Encodings with Graph Neural Networks [109.8653020407373]
  We introduce PEARL, a novel framework of learnable PEs for graphs.<n>PEARL approximates equivariant functions of eigenvectors with linear complexity, while rigorously establishing its stability and high expressive power.<n>Our analysis demonstrates that PEARL approximates equivariant functions of eigenvectors with linear complexity, while rigorously establishing its stability and high expressive power.
  arXiv  Detail & Related papers  (2025-02-03T07:28:53Z)
• Global Graph Counterfactual Explanation: A Subgraph Mapping Approach [54.42907350881448]
  Graph Neural Networks (GNNs) have been widely deployed in various real-world applications. Counterfactual explanation aims to find minimum perturbations on input graphs that change the GNN predictions. We propose GlobalGCE, a novel global-level graph counterfactual explanation method.
  arXiv  Detail & Related papers  (2024-10-25T21:39:05Z)
• Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats [6.176021290715425]
  In this article, we give exact logical characterizations of recurrent graph neural networks (GNNs) in two scenarios.<n>For floats, the formalism matching recurrent GNNs is a rule-based modal logic with counting, while for reals we use a suitable infinitary modal logic.<n>Applying our characterizations, we prove that, relative to graph properties definable in monadic second-order logic, our infinitary and rule-based logics are equally expressive.
  arXiv  Detail & Related papers  (2024-05-23T14:19:21Z)
• Topology-Informed Graph Transformer [7.193109202139812]
  'Topology-Informed Graph Transformer (TIGT)' is a novel transformer enhancing both discriminative power in detecting graph isomorphisms and the overall performance of Graph Transformers.<n>TIGT consists of four components: A topological positional embedding layer using non-isomorphic universal covers based on cyclic subgraphs of graphs to ensure unique graph representation.<n>TIGT outperforms previous Graph Transformers in classifying synthetic dataset aimed at distinguishing isomorphism classes of graphs.
  arXiv  Detail & Related papers  (2024-02-03T03:17:44Z)
• Graph Transformers for Large Graphs [57.19338459218758]
  This work advances representation learning on single large-scale graphs with a focus on identifying model characteristics and critical design constraints. A key innovation of this work lies in the creation of a fast neighborhood sampling technique coupled with a local attention mechanism. We report a 3x speedup and 16.8% performance gain on ogbn-products and snap-patents, while we also scale LargeGT on ogbn-100M with a 5.9% performance improvement.
  arXiv  Detail & Related papers  (2023-12-18T11:19:23Z)
• The logic of rational graph neural networks [0.7614628596146602]
  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. 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.
  arXiv  Detail & Related papers  (2023-10-19T20:32:25Z)
• Pure Transformers are Powerful Graph Learners [51.36884247453605]
  We show that standard Transformers without graph-specific modifications can lead to promising results in graph learning both in theory and practice. We prove that this approach is theoretically at least as expressive as an invariant graph network (2-IGN) composed of equivariant linear layers. Our method coined Tokenized Graph Transformer (TokenGT) achieves significantly better results compared to GNN baselines and competitive results.
  arXiv  Detail & Related papers  (2022-07-06T08:13:06Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  We show that standard Graph Neural Networks (GNNs) produce more discriminative representations than the Weisfeiler-Lehman (WL) algorithm. We also show that simple convolutional architectures with white inputs, produce equivariant features that count the closed paths in the graph.
  arXiv  Detail & Related papers  (2022-05-19T18:40:25Z)
• On the expressive power of message-passing neural networks as global feature map transformers [5.040463208115643]
  We investigate the power of message-passing neural networks (MPNNs) in their capacity to transform the numerical features stored in the nodes of their input graphs. Our focus is on global expressive power, uniformly over all input graphs, or over graphs of bounded degree with features from a bounded domain.
  arXiv  Detail & Related papers  (2022-03-17T18:37:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.