Expressive power of implicit line-graph methods for graph comparison

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

Social and Information NetworksArtificial IntelligenceMachine Learning

Summary

Comparing complex networks to find out if they are essentially the same is an important problem. The authors study a way to compare graphs by looking at their edges and how those edges connect, without building an entire new graph explicitly. They show that this new method is at least as powerful as traditional methods in recognizing when two graphs are different and sometimes more so. Their approach works well on challenging example graphs and can be used to improve neural network models that analyze graphs.

What this means in practice

  • For machine learning engineers: Improve graph neural network designs by using implicit line-graph methods to better distinguish graph structures in data.
  • For network analysis teams: Provide improved algorithms to compare network topologies using edge relations without explicit graph conversion steps.

Authors

Fan Yang

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.