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

• URL: http://arxiv.org/abs/2609.16412v1
• Date: Mon, 14 Sep 2026 22:34:54 GMT
• Title: On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Leman
• Abstract summary: We study the relation between fixed-dimensional Weisfeiler--Leman (WL) expressivity on line graphs and on their roots.<n>We show that ILG-$3$-WL is strictly more expressive than $3$-WL.
• Score: 2.6986809342283262
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Whitney's theorem allows isomorphism testing for connected simple graphs, apart from $K_3$ and $K_{1,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)\equiv_{3\text{-WL}}L(H)\Rightarrow G\equiv_{3\text{-WL}}H$. 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.

Related papers

• DRESS: A Continuous Framework for Structural Graph Refinement [0.0]
  We introduce DRESS, a framework that refines the structural similarity of edges in a graph to produce a canonical fingerprint.<n>The fingerprint is isomorphism-invariant by construction, numerically stable (all values lie in $[0,2]$), fast and embarrassingly parallel to compute.<n>$$-DRESS empirically separates all 7,983 graphs in a comprehensive Strongly Regular Graph benchmark, and iterated deletion ($k$-DRESS) climbs the staircase, achieving $(k+2)$-WL at each depthk$.
  arXiv  Detail & Related papers  (2026-02-24T12:18:42Z)
• Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts [3.652509571098291]
  We study the problem of releasing a differentially private (DP) synthetic graph $G'$ that well approximates the triangle-motif sizes of all cuts of any given graph $G'$.<n>Non-private versions of such graphs have found applications in diverse fields such as graph clustering, graph sparsification, and social network analysis.
  arXiv  Detail & Related papers  (2025-07-20T06:20:53Z)
• Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs [60.71360240206726]
  Large language models (LLMs) suffer from hallucinations, especially on knowledge-intensive tasks. Existing works propose to augment LLMs with individual text units retrieved from external knowledge corpora. We propose a framework called Graph Chain-of-thought (Graph-CoT) to augment LLMs with graphs by encouraging LLMs to reason on the graph iteratively.
  arXiv  Detail & Related papers  (2024-04-10T15:41:53Z)
• Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning [17.646846505225735]
  We introduce a novel hierarchy of graph isomorphism tests and a corresponding GNN framework, $r$-$ell$MPNN, that can count cycles up to length $r + 2$. Most notably, we show that $r$-$ell$WL can count homomorphisms of cactus graphs. We empirically validate the expressive and counting power of the proposed $r$-$ell$MPNN on several synthetic datasets and present state-of-the-art predictive performance on various real-world datasets.
  arXiv  Detail & Related papers  (2024-03-20T16:58:28Z)
• Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test [58.1543112860658]
  We uncover misalignments between graph machine learning practitioners' conceptualizations of expressive power and $k$-WL. We argue for extensional definitions and measurement of expressive power based on benchmarks.
  arXiv  Detail & Related papers  (2023-07-11T20:06:12Z)
• Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman [66.23316415757456]
  Message passing neural networks (MPNNs) have emerged as the most popular framework of graph neural networks (GNNs) in recent years. However, their expressive power is limited by the 1-dimensional Weisfeiler-Lehman (1-WL) test. We propose an extension, $(k,t)$-FWL, which considers any equivariant set as neighbors instead of all nodes. N$2$-GNN achieves record-breaking results on ZINC-Subset (0.059), outperforming previous SOTA results by 10.6%.
  arXiv  Detail & Related papers  (2023-06-05T21:35:32Z)
• Three iterations of $(d-1)$-WL test distinguish non isometric clouds of $d$-dimensional points [45.15780579276503]
  We study when the Weisfeiler--Lehman test is complete for clouds of euclidean points represented by complete distance graphs.<n>How many dimensions is enough to distinguish any two non-isometric point clouds in $d$-dimensional Euclidean space?<n>Our main result states that the $(d-1)$-dimensional WL test is complete for point clouds in $d$-dimensional Euclidean space, for any $dge 2$, and that only three iterations of the test suffice.
  arXiv  Detail & Related papers  (2023-03-22T18:23:24Z)
• WL meet VC [9.468816647649104]
  We study the expressive power of graph neural networks (GNNs) through the lens of Vapnik--Chervonenkis (VC) dimension theory. We derive an upper bound for GNNs' VC dimension using the number of colors produced by the $1text-mathsfWL$ and GNNs' VC dimension.
  arXiv  Detail & Related papers  (2023-01-26T11:29:36Z)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk. The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra. As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
  arXiv  Detail & Related papers  (2022-08-12T15:05:07Z)
• Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction [61.01337335214126]
  Link prediction is one important application of graph neural networks (GNNs) Most existing GNNs for link prediction are based on one-dimensional Weisfeiler-Lehman (1-WL) test. We study a completely different approach which can directly obtain node pair (link) representations based on textittwo-dimensional Weisfeiler-Lehman (2-WL) tests.
  arXiv  Detail & Related papers  (2022-06-20T04:50:38Z)

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.