3-WL in Depth: Universal Graph Identification via Iterated Line Graph Transformation

The expressive power of graph neural networks is commonly studied through the Weisfeiler–Leman (WL) hierarchy, where higher dimensions distinguish more graph pairs. Through an injective graph transformation, the same model may also distinguish additional pairs while the original graph remains recoverable up to isomorphism. We study iterated line graph transformation and prove that every pair of non-isomorphic finite simple graphs is distinguished by $3$-WL at some finite transformation depth $r$. Each additional transformation can distinguish pairs missed at all earlier depths, although no fixed depth suffices for all graphs. Based on these results, we introduce a universal line graph adapter for applying $3$-WL-equivalent model families such as PPGN++ and G${}^2$N${}^2$ to iterated line graphs, and extend the implicit line graph neural network (ILG-$3$-GNN) to arbitrary line depth. On BREC, line graph transformation improves separation for all tested $3$-WL-equivalent GNNs, with the best results matching $3$-WL on $L^r(G)$ for $r\le 3$, which separates $399$ of the $400$ pairs. Compared with $4$-WL on the original graphs, shallow transformations can reduce time and memory per refinement round at lower edge densities, while density and degree variation raise the cost of further steps.