mlsanityData to 14 Oct 2026

On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Leman

arXiv 2609.16412 ↗First posted 14 Sep 2026cs.SI cs.AI cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Whitney's theorem allows isomorphism testing for connected simple graphs, apart from K3 and K1,3, to be formulated as distinguishing their line graphs. However, the relation between fixed-dimensional Weisfeiler--Leman (WL) expressivity on line graphs and on their roots remains unresolved. We study this relation through Implicit Line-Graph WL (ILG-k-WL), which is exactly k-WL on L(G), executed over the edges of G with line-graph relations derived from endpoint incidence and without explicitly constructing L(G). On the Whitney-general class, the relation between root-domain and line-graph WL depends on k. For k=1,2, ILG-k-WL adds no distinguishing power beyond root-domain 1-WL and misses some pairs that 1-WL separates. For k=3, we prove the backward containment L(G)equiv3-WLL(H)Rightarrow Gequiv3-WLH. Strongly regular witness pairs, including the Shrikhande/rook pair, show that ILG-3-WL is strictly more expressive than 3-WL. The backward containment also extends to disconnected graphs with no isolated vertices when every connected component is Whitney-general. Deterministic ILG-3-WL separates all three substructure-counting witness pairs, all 105 pairs in SR25, and 359 of 400 BREC pairs. An untrained dense ILG-3-GNN gives the same pairwise verdicts on these evaluations.

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

Builds on

17 of 30 references.

References · 17

  1. 2017Inductive Representation Learning on Large Graphscited by 6,320
  2. 2018How Powerful are Graph Neural Networks?cited by 4,393
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  4. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  5. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  6. 2019Provably Powerful Graph Networkscited by 389
  7. 2017Learning to Represent Programs with Graphscited by 220
  8. 2021Equivariant Subgraph Aggregation Networkscited by 154
  9. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  10. 2020Line Graph Neural Networks for Link Predictioncited by 89
  11. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  12. 2020Co-embedding of Nodes and Edges with Graph Neural Networkscited by 30
5 more
  1. 20221-WL Expressiveness Is (Almost) All You Needcited by 15
  2. 2023Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehmancited by 13
  3. 2025Bridging Theory and Practice in Link Representation with Graph Neural Networkscited by 4
  4. 2024Theoretical Insights into Line Graph Transformation on Graph Learningcited by 2
  5. 2025LGAN: An Efficient High-Order Graph Neural Network via the Line Graph Aggregationcited by 1

Built on by

Not cited yet.