SOURCE-LINKED INTELLIGENCE

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

arXiv · AI, language, vision and robotics · article · Sep 14, 2026 · UTC

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

Read original source ↗ Open in workspace

recordType

paper

region

Global