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

arXiv: https://arxiv.org/abs/2609.16412 · HTML: https://mlsanity.com/paper/2609.16412/

## 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 (most cited first, 17 of 17)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Learning to Represent Programs with Graphs](https://mlsanity.com/paper/1711.00740/) (2017)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [Line Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2010.10046/) (2020)
- [An Empirical Study of Realized GNN Expressiveness](https://mlsanity.com/paper/2304.07702/) (2023)
- [Co-embedding of Nodes and Edges with Graph Neural Networks](https://mlsanity.com/paper/2010.13242/) (2020)
- [1-WL Expressiveness Is (Almost) All You Need](https://mlsanity.com/paper/2202.10156/) (2022)
- [Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman](https://mlsanity.com/paper/2306.03266/) (2023)
- [Bridging Theory and Practice in Link Representation with Graph Neural Networks](https://mlsanity.com/paper/2506.24018/) (2025)
- [Theoretical Insights into Line Graph Transformation on Graph Learning](https://mlsanity.com/paper/2410.16138/) (2024)
- [LGAN: An Efficient High-Order Graph Neural Network via the Line Graph Aggregation](https://mlsanity.com/paper/2512.10735/) (2025)

## 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.