Paper deep dive
On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Leman
Fan Yang
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2609.16412v1
- Canonical: https://arxiv.org/abs/2609.16412v1
Trouble viewing inline? Open PDF directly →
Full Text
171,574 characters extracted from source content.
Expand or collapse full text
On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler–Leman Fan Yang Affiliation: Independent Researcher Email: lukeyf.ubc@gmail.com Abstract Whitney’s theorem allows isomorphism testing for connected simple graphs, apart from K3K_3 and K1,3K_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)L(G), executed over the edges of G with line-graph relations derived from endpoint incidence and without explicitly constructing L(G)L(G). On the Whitney-general class, the relation between root-domain and line-graph WL depends on k. For k=1,2k=1,2, ILG-k-WL adds no distinguishing power beyond root-domain 11-WL and misses some pairs that 11-WL separates. For k=3k=3, we prove the backward containment L(G)≡3-WLL(H)⇒G≡3-WLHL(G) _3-WLL(H) G _3-WLH. Strongly regular witness pairs, including the Shrikhande/rook pair, show that ILG-33-WL is strictly more expressive than 33-WL. The backward containment also extends to disconnected graphs with no isolated vertices when every connected component is Whitney-general. Deterministic ILG-33-WL separates all three substructure-counting witness pairs, all 105105 pairs in SR25, and 359359 of 400400 BREC pairs. An untrained dense ILG-33-GNN gives the same pairwise verdicts on these evaluations. 1 Introduction Graph neural networks (GNNs) are used in molecular property prediction [14], social-network analysis [16], combinatorial optimization [18], and program analysis [1]. Their ability to distinguish non-isomorphic inputs matters independently of the learning objective: if a graph encoder assigns two graphs the same representation, a downstream predictor cannot distinguish them from that representation alone. The Weisfeiler–Leman (WL) hierarchy formalizes this limitation. Standard message-passing neural networks (MPNNs) are bounded by 11-WL [27, 22], which fails to separate many regular and highly symmetric graphs. Higher-order GNNs use states indexed by multiple vertices, as in higher-order WL refinement. The k-GNN family operates on vertex subsets [22], whereas Provably Powerful Graph Networks (PPGN) use pair-indexed feature matrices and have provable 33-WL expressive power [20]. Graph transformations can also change what a fixed WL dimension detects. The line graph L(G)L(G) represents every root edge by a vertex and joins two such vertices when their edges share an endpoint. For connected simple graphs G,HG,H, Whitney’s theorem [26] states that L(G)≅L(H)L(G) L(H) implies G≅HG H, except when G,H=K3,K1,3\G,H\=\K_3,K_1,3\. This isomorphism statement does not imply equal fixed-dimensional WL power on roots and their line graphs. Existing line-graph models address community detection [9], link prediction [7], joint node–edge learning [17], and atomistic learning [10]. Other methods transform the refinement domain: LGAN forms local line graphs [11], ESAN processes selected subgraphs [3], and δ-k-LWL restricts tuple replacements to local neighbors [21]. Simplicial and cellular WL add cliques or cells and refine colors through their incidences [5, 4]. These works do not determine how fixed-dimensional WL on L(G)L(G) compares with the same dimension on G. Figure 1: Graph pairs separated by 33-WL (left) and ILG-33-WL (right). Left: 33-WL separates K3,3K_3,3 and the triangular prism, whereas 11-WL does not. Right: ILG-33-WL separates the Shrikhande and 4×44× 4 rook graphs, whereas 33-WL does not; their four-clique counts are 00 and 88, respectively. This paper compares fixed-dimensional WL on G and L(G)L(G) through Implicit Line-Graph WL (ILG-k-WL), which runs k-WL over root edges using endpoint-derived line-graph relations without constructing L(G)L(G). The Shrikhande and rook graphs illustrate why this comparison is nontrivial. They are non-isomorphic strongly regular graphs with the same parameters and form a standard hard case for 33-WL [2, 5]. Yet 33-WL separates their line graphs; line-graph transformation can break strong regularity [28]. Figure 1 shows this pair. Contributions. We determine the relation between root-domain and line-graph WL for k∈1,2,3k∈\1,2,3\ on the Whitney-general class. ILG-k-WL is strictly weaker than root-domain k-WL for k=1,2k=1,2 (Corollary 2), whereas Theorem 1 and strongly regular witnesses give 3-WL≺ILG-3-WL3-WL -3-WL (Corollary 5). One global pair update counts four-cliques exactly on every finite simple graph (Corollary 3). Backward transfer also extends to disconnected graphs with no isolated vertices and Whitney-general components (Theorem 2). Both backward-transfer theorems are formalized in Lean 4 (Appendix C). Direct ILG-k-WL is k-WL on L(G)L(G). For k≥3k≥ 3, its global-edge form implements (k−1)(k-1)-FWL using Θ(mk−1) (m^k-1) root-edge tuple states and endpoint-derived line-graph relations. On bounded finite domains, ILG-k-GNNs can match any fixed number of global-edge ILG-k-WL rounds, and every parameterization is bounded by that refinement. We evaluate deterministic ILG-33-WL and an untrained dense ILG-33-GNN on the three substructure-counting witness pairs, all 105105 SR25 pairs, and all 400400 BREC pairs. Their verdicts coincide: 3/33/3, 105/105105/105, and 359/400359/400 separations, respectively (Section 6). 2 Background and Conventions Throughout, G and H denote finite, undirected, simple graphs, and L(G)L(G) and L(H)L(H) denote their line graphs. For one graph G, we write V(G)V(G) and E(G)E(G) for its vertex and edge sets and abbreviate n=|V(G)|n=|V(G)| and m=|E(G)|m=|E(G)| when no second graph is present. Edges are unordered two-element subsets e=u,ve=\u,v\; an implementation may list the edges in any order and store the two endpoints of each edge in either order. For u∈V(G)u∈ V(G), let NG(u)N_G(u) and dG(u)d_G(u) denote its neighborhood and degree; we omit the subscript only when the graph is unambiguous. We write AGA_G for the adjacency matrix of G, and IS,JSI_S,J_S for the identity and all-ones matrices indexed by a finite set S. Vertices and edges of G,HG,H are called root vertices and root edges; a root edge e∈E(G)e∈ E(G) is canonically the line-graph vertex e∈V(L(G))e∈ V(L(G)). We write Deg(G)=dG(u):u∈V(G)Deg(G)= \\! \d_G(u):u∈ V(G) \\! \ for the root degree multiset. The line graph L(G)L(G) has vertex set E(G)E(G), with two vertices adjacent exactly when the corresponding distinct edges of G share an endpoint. Definition 1 (Whitney-general class). A graph is Whitney-general if it is connected, simple, and not isomorphic to K3K_3 or K1,3K_1,3. Whitney’s theorem [26] guarantees that its line graph determines it up to isomorphism. A graph is componentwise Whitney-general if it has no isolated vertices and every connected component is Whitney-general. Definition 2 (Line-graph relation code). For e,f∈E(G)e,f∈ E(G), write e∼L(G)fe _L(G)f when e≠fe≠ f and e∩f≠∅e∩ f≠ — that is, when e and f are adjacent in L(G)L(G) — and define the three-valued relation code rG(e,f)=0,e=f,1,e∼L(G)f,2,otherwise.r_G(e,f)= cases0,&e=f,\\ 1,&e _L(G)f,\\ 2,&otherwise. cases The graph-level signature of a coloring c:S→c:S over a finite state set S is its multiset of colors c(s):s∈S \\! \c(s):s∈ S \\! \; a refinement procedure distinguishes two graphs when their graph-level signatures differ after stabilization or after a specified number of rounds. All occurrences of HASHHASH below mean a fixed injective encoding of the displayed finite signature; only the induced color partition matters. When two graphs are compared, their refinements are run in parallel with the same encoding of signatures, while every replacement sweep remains inside its own graph. Thus equal color names have a graph-independent meaning and no vertexwise correspondence is assumed. WL convention. Throughout, 11-WL denotes ordinary vertex color refinement: from the constant initial color c0(v)c_0(v), it updates ct+1(v)=HASH(ct(v),ct(w):w∈NG(v)).c_t+1(v)=HASH (c_t(v), \\! \c_t(w):w∈ N_G(v) \\! \ ). For every k≥2k≥ 2, k-WL denotes the oblivious k-dimensional WL algorithm customary in graph learning [22, 12]: it colors ordered k-tuples with separate per-coordinate replacement. We use “k-WL” without further qualification for this convention throughout. For a graph G, a tuple =(v1,…,vk)∈V(G)kv=(v_1,…,v_k)∈ V(G)^k, and k≥2k≥ 2, initialize c0()=HASH(atpG())c_0(v)=HASH(atp_G(v)), where the atomic type records all equality and adjacency relations among the coordinates, and update by ct+1()=HASH(ct(),(ct([i←w]):w∈V(G))i=1k),c_t+1(v)=HASH (c_t(v), ( \\! \c_t(v[i← w]):w∈ V(G) \\! \ )_i=1^k ), where [i←w]v[i← w] denotes the tuple with its i-th coordinate replaced by w: [i←w]=(v1,…,vi−1,w,vi+1,…,vk).v[i← w]=(v_1,…,v_i-1,w,v_i+1,…,v_k). This procedure stores Θ(nk) (n^k) tuple states. For k≥3k≥ 3, the non-oblivious or folklore algorithm on ordered (k−1)(k-1)-tuples, denoted (k−1)(k-1)-FWL, has the same stable graph-distinguishing power as this separate-coordinate k-WL algorithm [12]. It uses simultaneous all-coordinate replacement and Θ(nk−1) (n^k-1) tuple states. This is an arity-shift equivalence of graph distinguishability, not a round-by-round identification of tuple colors. We use this global-replacement form in Section 3.3. For either ordinary 11-WL or the above k-WL convention, we write G≡k-WLHG _k-WLH when the stable graph-level signatures of G and H, computed with the shared encoding convention above, are equal. We write G≢k-WLHG _k-WLH when they differ. Unless features are stated explicitly, all graphs are initially uncolored: 11-WL starts from one constant vertex color and k-WL for k≥2k≥ 2 starts from atomic types. For two refinement procedures , A, B, we write ⪯ A B when every graph pair separated by A is also separated by B, and ≺ A B when the containment is strict. Two low-dimensional conventions matter below. On finite simple graphs, 11-WL and 22-WL have the same graph-distinguishing power [12]; and substituting k=1k=1 into the tuple rule above would give a trivial global multiset, which is why ordinary 11-WL is defined separately. 3 Implicit Line-Graph WL Since V(L(G))=E(G)V(L(G))=E(G), k-WL on L(G)L(G) can be executed over the root edges. We give its first-order, direct higher-order, and arity-shifted global-edge forms. 3.1 ILG-11-WL ILG-11-WL is ordinary 11-WL on L(G)L(G): each root edge e starts from a common color (or its given edge label) and updates from ct(f):f≠e,f∩e≠∅ \\! \c_t(f):f≠ e,\ f∩ e≠ \\! \. Replacing the hash by neural message, aggregation, and update maps gives ILG-11-GNN. Lemma 1 (ILG-11-GNN is an MPNN on the line graph). With shared initial features and message, update, aggregation, and readout maps, an ILG-11-GNN on G and an MPNN on L(G)L(G) agree at every layer and at graph readout. Proof. Their neighborhoods coincide; see Appendix D.1. ∎ 3.2 ILG-k-WL For k≥2k≥ 2, direct ILG-k-WL applies the k-WL update of Section 2 to ordered tuples in E(G)kE(G)^k, with atomic types computed from rGr_G and replacements ranging over E(G)E(G). Proposition 1 (ILG-k-WL equals k-WL on the line graph). For every graph G and k≥1k≥ 1, ILG-k-WL on G and k-WL on L(G)L(G) produce identical state partitions after each round, up to canonical renaming of colors. Proof. Under V(L(G))=E(G)V(L(G))=E(G), the domains, atomic types, and replacement ranges coincide; see Appendices D.2 and D.5. ∎ 3.3 Global-Edge Form with Θ(mk−1) (m^k-1) Tuple-State Storage Direct ILG-k-WL uses Θ(mk) (m^k) tuple states and Θ(mk+1) (m^k+1) replacement entries per round. Applying the standard arity shift to L(G)L(G) gives the same stable distinguishing power on Θ(mk−1) (m^k-1) tuples [12]; its k=3k=3 instance underlies PPGN [20]. Global-edge ILG-k-WL is this (k−1)(k-1)-FWL formulation on ordered root-edge tuples: for each g∈E(G)g∈ E(G), its message collects the k−1k-1 coordinate-wise replacements ct([i←g])c_t(e[i← g]). Appendix D.6 gives the full recurrence. This form uses Θ(mk−1) (m^k-1) tuple states and Θ(mk) (m^k) replacement entries per round. Endpoint comparisons evaluate rG(e,f)r_G(e,f) in O(1)O(1) time from a Θ(m) (m)-space m×2m× 2 table, avoiding Θ(m+mL) (m+m_L) stored line-graph adjacency without changing tuple-state or update asymptotics. Appendices D.10 and E give the details and measurements. Corollary 1 (Global-edge ILG-k-WL has k-WL graph-distinguishing power on L(G)L(G)). For every simple graph G and every k≥3k≥ 3, global-edge ILG-k-WL has the same graph-level distinguishing power as k-WL on L(G)L(G), using Θ(mk−1) (m^k-1) rather than Θ(mk) (m^k) tuple states. Proof. The recurrence is exactly (k−1)(k-1)-FWL on L(G)L(G) (Appendix D.6), and the arity shift [12] gives the claim. ∎ 4 Expressivity Analysis ILG-k-WL is strictly weaker than root-domain k-WL for k=1,2k=1,2, but strictly stronger for k=3k=3, on Whitney-general graphs. At k=1,2k=1,2, some pairs separated on the roots are not separated on their line graphs, even when the roots have equal order. At k=3k=3, joint pair refinement on the line graphs determines the stable ordered-pair coloring of the roots and separates some pairs that root-domain 33-WL does not. The backward result extends componentwise to the disconnected class in Definition 1. 4.1 First-Order: Loss at k=1k=1 The restriction to Whitney-general roots removes the classical K3,K1,3K_3,K_1,3 ambiguity. Any loss shown below therefore occurs even though the line graph determines its root up to isomorphism. Proposition 2 (11-WL equivalence transfers to line graphs). For all simple graphs G,HG,H (without restriction): G≡1-WLH⟹L(G)≡1-WLL(H).G _1-WLH L(G) _1-WLL(H). Thus, ILG-11-WL can separate a pair only if root-domain 11-WL also separates it. Proof sketch. By the fractional-isomorphism/equitable-partition characterization [24, 15], G≡1-WLHG _1-WLH iff their stable 11-WL colorings have matching class sizes and between-class neighbor counts. The table of these counts is the equitable quotient. The induced edge coloring c^G(e)=cG(u),cG(v) c_G(e)= \\! \c_G(u),c_G(v) \\! \, where cGc_G is the stable vertex coloring, is an equitable partition of L(G)L(G) whose class sizes and equitable quotient are determined by the 11-WL data of G. Since these agree for G and H, the stable 11-WL colorings of L(G)L(G) and L(H)L(H) coincide, giving L(G)≡1-WLL(H)L(G) _1-WLL(H). See Appendix D.3 for the full argument. ∎ Proposition 3 (Equal-order backward failure at first order). There exist Whitney-general graphs G,HG,H with L(G)≡1-WLL(H)L(G) _1-WLL(H) but G≢1-WLHG _1-WLH. Figure 2: Equal-order backward failure at first order. Root 11-WL separates G,HG,H by their degree multisets, but L(G),L(H)L(G),L(H) have the same stable equitable quotient with cells of sizes 2,4,42,4,4. Line vertices are labeled by their root edges; hollow and filled vertices have degrees two and four. Proof. The pair and its line graphs are displayed in Figure 2; both graphs are Whitney-general, and their root degree multisets differ, so 11-WL separates G and H in its first round. In either line graph, degree refinement followed by one neighbor-color refinement stabilizes with cells of sizes 2,4,42,4,4 and the same equitable quotient A:(0,2,0)A:\,(0,2,0), B:(1,1,2)B:\,(1,1,2), C:(0,2,2)C:\,(0,2,2), so L(G)≡1-WLL(H)L(G) _1-WLL(H). The computation is verified in Appendix D.4. ∎ Remark 1 (Why k=1k=1 and k=2k=2 fail). Root order is not the only reason backward transfer fails: a line color records endpoint-degree sums and an equitable quotient of edge neighborhoods, but not how those colors are distributed among root stars. Joint pair refinement at k=3k=3 additionally records common-neighbor data for ordered edge pairs, from which Section 4.3 recovers the stable ordered-pair coloring of the root. Corollary 2 (ILG is strictly weaker for k=1,2k=1,2). On the Whitney-general class: ILG-1-WL≺1-WL,ILG-2-WL≺2-WL.ILG-1-WL 1-WL, -2-WL 2-WL. Proof. The first statement follows from Propositions 2 and 3. For the second, apply the equivalence of 11-WL and 22-WL [12] both to the roots and to their line graphs, and use Proposition 1. ∎ 4.2 Strictness at k=3k=3 An srg(v,d,λ,μ)srg(v,d,λ,μ) is d-regular on v vertices, with λ and μ common neighbors for adjacent and nonadjacent vertex pairs, respectively. On two strongly regular graphs with the same parameters, the initial pair types and all simultaneous-replacement counts depend only on equality and adjacency. Induction leaves the 22-FWL colors parameter-determined. The arity shift then makes co-parametric non-isomorphic strongly regular graphs standard examples not separated by 33-WL [12]. Corollary 3 (Universal four-clique counting). For every finite simple graph G, one global pair-refinement round of ILG-33-WL determines the exact number cl4(G)cl_4(G) of four-vertex cliques. More precisely, cl4(G)=16|(e,f)∈E(G)2:e∩f=∅,|NL(G)(e)∩NL(G)(f)|=4|.cl_4(G)= 16 | \(e,f)∈ E(G)^2:e∩ f= , |N_L(G)(e)∩ N_L(G)(f) |=4 \ |. Consequently, ILG-33-WL-equivalent finite simple graphs have the same four-clique count. Proof. The first pair color records initial nonadjacency and the common-neighbor multiplicity. The resulting factor-six double count is proved in Appendix B.1. ∎ Proposition 4 (Shrikhande/rook separation at k=3k=3). On the Whitney-general class, ILG-33-WL can separate graph pairs that 33-WL on the root graph cannot. Proof. The Shrikhande and 4×44× 4 rook graphs are Whitney-general, co-parametric srg(16,6,2,2)srg(16,6,2,2) graphs, so their root 33-WL signatures agree. The Shrikhande graph has no K4K_4, whereas the rook graph has eight. By Corollary 3, the corresponding ordered-pair color therefore has multiplicities 00 and 4848, so pair refinement separates their line graphs, as does 33-WL by the arity shift. Proposition 1 identifies the direct line-graph test with ILG-33-WL. ∎ 4.3 Backward Transfer on Whitney-General Graphs at k=3k=3 The preceding witness shows that ILG-33-WL can be stronger, but not that it preserves every distinction made by root 33-WL. The next theorem proves that it does on Whitney-general graphs. Theorem 1 (Backward transfer at 33-WL). For Whitney-general graphs G,HG,H, L(G)≡3-WLL(H)⟹G≡3-WLH.L(G) _3-WLL(H)\; \;G _3-WLH. Proof idea. Let BGB_G be the unsigned vertex–edge incidence matrix. The identity BG⊤BG=2I+AL(G)B_G B_G=2I+A_L(G) shows that 2I+AL(G)2I+A_L(G) is the Gram matrix of the root incidence vectors. At k=3k=3, stable line-pair colors span a matrix algebra closed under multiplication. The Gram identity therefore lets us recover endpoint degrees and local endpoint profiles without choosing the shared endpoints globally. Stable 11-WL records vertex color classes and their neighbor counts but provides no such coherent pair algebra, so the same reconstruction is unavailable below k=3k=3. Appendix A gives the full argument in five stages. 1. Line algebra (§A.1). The indicator matrices of stable 22-FWL colors span a coherent matrix algebra. Line-graph equivalence induces an isomorphism between the two such algebras. 2. Local root data (§A.2). The line algebra recovers endpoint degrees, star profiles (incident-edge counts by stable line color), and dart profiles (relation counts at a specified endpoint). Small roots K1,K2K_1,K_2, the paw, and the diamond are treated separately, while K3,K1,3K_3,K_1,3 are excluded. 3. Unequal endpoint profiles (§A.3). A common ordering of the transported profile labels orients these edges in both roots. Their signed incidence matrices then define mixed Gram matrices that are mapped by the line-algebra isomorphism. 4. Equal endpoint profiles (§A.4). No canonical orientation is available. A cancellation identity shows that either endpoint choice acts identically on matrices in the recovered root space. This recovers the cells for equal and adjacent root-vertex pairs. 5. All distances (§A.5–A.6). Induction on root distance recovers the remaining pair cells, whose disjoint 00-11 supports give Hadamard closure and hence the stable root pair algebra. The arity shift [12] converts this 22-FWL statement into Theorem 1. ∎ Corollary 4 (Connected graphs and the Whitney exception). Let G,HG,H be connected finite simple graphs. If L(G)≡3-WLL(H)L(G) _3-WLL(H), then either G≡3-WLHG _3-WLH or G,H=K3,K1,3\G,H\=\K_3,K_1,3\. Proof. If neither root belongs to the Whitney pair, both are Whitney-general and Theorem 1 applies. If one root belongs to that pair, its line graph is K3K_3. Stable 33-WL equivalence preserves the order and degree multiset of the line graph, so the other line graph is also K3K_3; Whitney’s theorem leaves exactly the two stated roots. ∎ Theorem 2 (Backward transfer for disconnected graphs). For componentwise Whitney-general graphs G,HG,H, L(G)≡3-WLL(H)⟹G≡3-WLH.L(G) _3-WLL(H)\; \;G _3-WLH. Proof idea. Stable pair refinement matches the components of L(G)L(G) and L(H)L(H). Since the roots have no isolated vertices, these are exactly the line graphs of their root components, so Theorem 1 applies to each matched pair. Combining the component equivalences proves the claim; see Appendix A.7. ∎ Corollary 5 (Strict containment at 33-WL). On both the Whitney-general and componentwise Whitney-general classes, 3-WL≺ILG-3-WL.3-WL\ \ ILG-3-WL. Proof. Theorems 1 and 2 give containment, and Proposition 4 makes it strict. ∎ Remark 2 (Comparison with root 44-WL). Root 44-WL and ILG-33-WL are incomparable, even on connected Whitney-general simple graphs. Root 44-WL distinguishes the incidence graphs of two nonisomorphic Steiner triple systems of order 1313, whereas ILG-33-WL does not. Conversely, ILG-33-WL distinguishes a compressed parity pair over K5K_5 that root 44-WL does not. Appendix B.2 gives both witnesses and their exact traces. 5 Higher-Order Neural Architecture The global-edge recurrence defines a neural model on the same tuple domain. For k≥3k≥ 3, one hidden state is stored for each ordered (k−1)(k-1)-tuple of root edges. A message associated with replacement edge g jointly encodes the k−1k-1 states obtained by placing that same g in each coordinate. We display the first nontrivial case, k=3k=3, whose states are ordered edge pairs. Let qe∈ℝdeq_e ^d_e be an edge feature. All qeq_e are the same constant on an unlabeled graph. Finite vertex labels can instead be included in qeq_e as the unordered pair of endpoint labels; isolated vertices are outside the line-domain representation. This uses labels, not unique vertex or edge identifiers. Let Embr:0,1,2→ℝdrEmb_r:\0,1,2\ ^d_r embed the line-graph relation code; an injective one-hot map suffices for exact WL simulation. Let dhd_h be the hidden-state width, so hef(ℓ)∈ℝdhh_ef^( ) ^d_h. Pair states start from hef(0)=ϕ0(qe,qf,Embr(rG(e,f))),e,f∈E(G).h_ef^(0)= _0 (q_e,q_f,Emb_r(r_G(e,f)) ), e,f∈ E(G). One layer computes Mef(ℓ)=∑g∈E(G)ψℓ(hgf(ℓ),heg(ℓ),qg,Embr(rG(g,e)),Embr(rG(g,f))),M_ef^( )= _g∈ E(G) _ (h_gf^( ),h_eg^( ),q_g,Emb_r(r_G(g,e)),Emb_r(r_G(g,f)) ), then updates hef(ℓ+1)=ηℓ(hef(ℓ),Mef(ℓ)).h_ef^( +1)= _ (h_ef^( ),M_ef^( ) ). After TnetT_net layers, a graph readout may combine pair and edge summaries: hG=READOUT(∑e,f∈E(G)γread(hef(Tnet)),∑e∈E(G)ξ(qe)).h_G=READOUT ( _e,f∈ E(G) _read(h_ef^(T_net)), _e∈ E(G)ξ(q_e) ). Our implementations use multilayer perceptrons (MLPs) for the maps above: ϕ0 _0 initializes pair states, ψℓ _ produces messages, ηℓ _ updates states, and γread,ξ _read,ξ feed the invariant readout. The corresponding WL color already contains qgq_g and the relation codes, so the neural message receives no extra structural information. Vertex relabeling leaves the graph representation unchanged, and reordering the internal edge list only permutes tuple states (Appendix D.9). Appendix D.8 gives the general-k forward pass. Proposition 5 (Expressivity of global-edge ILG-k-GNN). Fix k≥3k≥ 3, a fixed number of rounds, and a graph class with bounded edge count and a finite alphabet of edge features. Finite vertex labels may be included when they are encoded invariantly in the edge features as above. There are choices of Embr,ϕ0,ψℓ,ηℓ,γread,ξEmb_r, _0, _ , _ , _read,ξ, and READOUTREADOUT for which the summed multiset encodings and final readout are injective on every finite domain encountered. With these choices, the GNN simulates the corresponding feature-labeled global-edge ILG-k-WL refinement. Conversely, if two feature-labeled graphs have identical refinement histories, no instance whose messages use only the stated tuple states, edge features, and relation codes can separate them through an invariant readout. Proof sketch. Bounded edge count and a finite feature alphabet allow only finitely many replacement entries. The multiset-encoding lemma of Xu et al. [27] therefore gives injective summed encodings, and induction over layers assigns each refinement color a distinct hidden state. Conversely, every hidden state is a function of its refinement color, so equal color histograms force equal invariant readouts. Appendix D.7 gives the full construction. ∎ 6 Expressivity Evaluation Evaluation objective. We report graph-pair separations by deterministic refinements and neural realizations, together with the relevant WL upper bounds. Table 1 covers the three substructure-counting witness pairs, all 105105 SR25 pairs, and all 400400 BREC pairs. 6.1 Deterministic Refinement For each deterministic method computed in this study, two graphs are separated when their graph-level signatures differ. A pair is reported as not separated only after refinement stabilizes. The mathematical recurrence uses exact canonical signatures. Regression tests on a finite collection of graphs compare ILG with WL on explicitly constructed line graphs, checking the implementation against Proposition 1. SR25 contains 1515 graphs with parameters srg(25,12,5,6)srg(25,12,5,6), giving 105105 unordered pairs [2]. BREC contains 400400 specified non-isomorphic pairs whose main graphs are constructed to be 11-WL-indistinguishable [25]. Its CFI category is based on the Cai–Fürer–Immerman construction [25, 6]. The three substructure-counting witness pairs are C6C_6 versus C3⊔C3C_3 C_3, C8C_8 versus C4⊔C4C_4 C_4, and Shrikhande versus the 4×44× 4 rook graph. The pairs differ in their numbers of triangles, four-cycles, and four-cliques, respectively. If a method does not separate one of these pairs, it cannot count that pattern on all graphs; separation alone does not prove that it can. For four-cliques, Corollary 3 supplies the stronger universal counting result. In the neural block, “set 33-WL” denotes the subset-based refinement associated with Morris 33-GNN, not the ordered-tuple 33-WL used elsewhere in the paper. The table’s WL bound column lists the deterministic refinement whose distinguishing power upper-bounds that of each neural architecture. A dash marks a deterministic method. Table 1: Deterministic refinement results and neural separation counts on the evaluated datasets and graph pairs. BREC is split into four aggregate categories: Regular combines the Simple Regular, Strongly Regular, 4-Vertex Condition, and Distance Regular families; Extension and CFI combine their respective BREC subfamilies. Benchmark entries count separated pairs; the last three columns give one verdict for each substructure-counting witness pair. The PPGN BREC entry † is sourced from Wang and Zhang [25]. The ILG-33-GNN entry ‡ reports an untrained dense evaluation on the three substructure-counting witness pairs, all 105105 SR25 pairs, and all 400400 BREC main pairs. Neural rows use the protocols in Appendix F. BREC pairs Substructure-counting witness pairs Method WL bound SR25 Basic Regular Extension CFI All C3C_3 C4C_4 K4K_4 Deterministic refinement ILG-11-WL — 0/105 0/60 0/140 0/100 0/100 0/400 ✗ ✗ ✗ 33-WL — 0/105 60/60 50/140 100/100 60/100 270/400 ✓ ✓ ✗ ILG-33-WL — 105/105 60/60 139/140 100/100 60/100 359/400 ✓ ✓ ✓ Neural architectures ILG-11-GNN ILG-11-WL 0/105 0/60 0/140 0/100 0/100 0/400 ✗ ✗ ✗ Morris 33-GNN set 33-WL 0/105 60/60 50/140 97/100 0/100 207/400 ✓ ✓ ✗ PPGN 33-WL 0/105 60/60 50/140 100/100 23/100 233/400† ✓ ✓ ✗ ILG-33-GNN‡ ILG-33-WL 105/105 60/60 139/140 100/100 60/100 359/400 ✓ ✓ ✓ On the substructure-counting witness pairs, 33-WL separates the triangle and four-cycle pairs but not Shrikhande/rook. Since the latter roots have different four-clique counts, their shared signature proves that 33-WL cannot count four-cliques in general. ILG-33-WL separates all three pairs. The same difference is universal for four-clique counts by Corollary 3. On SR25, root-domain 33-WL assigns one signature to all 1515 graphs, whereas ILG-33-WL separates every pair. On BREC, ILG-33-WL improves over root-domain 33-WL only in the Regular aggregate. It separates 139/140139/140 pairs there, broken down as 50/5050/50 Simple Regular, 50/5050/50 Strongly Regular, 20/2020/20 4-Vertex Condition, and 19/2019/20 Distance Regular; root-domain 33-WL separates 50/14050/140. 33-WL already separates every pair in Basic and Extension, and both refinements separate 60/10060/100 CFI pairs. The remaining 4141 pairs comprise 2020 CFI-33-WL pairs, 2020 CFI-44-WL pairs, and one Distance Regular pair. On the tested CFI blocks, ILG-33-WL and root-domain 33-WL have identical pairwise outcomes. We make no claim about other CFI families. The only Distance Regular pair not separated is BREC pair 380380 (zero-based); both refinements stabilize without distinguishing it. 6.2 Neural Evaluation The ILG-11-GNN and Morris 33-GNN rows use pair-specific training and the evaluation protocols detailed in Appendix F. The PPGN category counts, totaling 233233 pairs, are taken from Wang and Zhang [25, Table 2]. For ILG-33-GNN, we evaluate an untrained dense model separately on each of the three substructure-counting witness pairs, the 105105 SR25 pairs, and the 400400 BREC main pairs, using the same fixed parameters for both graphs in a pair. The model has constant uncolored edge features, invariant equality/incident/disjoint relation codes, width 3232, five layers, sine activations, and a multiscale readout. Each graph is evaluated in its stored ordering and under three relabelings. A pair is counted as separated only when its minimum cross-graph distance exceeds both within-graph diameters by the fixed numerical tolerance. Every separation uses all four copies; a failed pair may stop after two. The resulting verdicts are 3/33/3 on the substructure-counting witness pairs, 105/105105/105 on SR25, and 359/400359/400 on BREC. Across all three suites, the neural pairwise verdicts coincide with deterministic ILG-33-WL. All SR25 pairs and all three substructure-counting witness pairs are 11-WL-indistinguishable. ILG-11-GNN separates none of them, consistent with Lemma 1 and Proposition 2. Morris 33-GNN uses set-based refinement rather than the ordered-tuple 33-WL studied here. It separates 0/1050/105 SR25 pairs and 207/400207/400 BREC pairs, separating the triangle and four-cycle pairs but not the four-clique pair. Appendix F specifies the trained and untrained protocols and their invariance checks. 7 Discussion and Conclusion The measurements in Appendix E follow the complexity analysis: explicit and implicit line-domain refinement have the same pair-state and per-round update costs, while endpoint access avoids storing the line-graph structure. On SR25, root 44-WL is faster than ILG-33-WL in the shared implementation. This is a cost comparison, not an expressivity ordering: the two methods are incomparable, and ILG-33-WL distinguishes pairs that root 44-WL misses (Remark 2). On Whitney-general graphs, ILG-k-WL is strictly weaker than root-domain k-WL for k=1,2k=1,2, but strictly stronger for k=3k=3; the latter strict containment also holds on componentwise Whitney-general graphs. At k=3k=3, ILG-33-WL counts four-cliques on every finite simple root graph (Corollary 3) and separates more pairs than root-domain 33-WL on SR25 and in BREC’s Regular aggregate. On the tested CFI blocks, the root and line-domain refinements have the same pairwise outcomes. The backward-transfer theorems and Shrikhande/rook pair prove 3-WL≺ILG-3-WL3-WL -3-WL on both classes. The untrained dense ILG-33-GNN reproduces the deterministic ILG-33-WL verdicts on the substructure-counting witness pairs, SR25, and BREC. This comparison tests graph-isomorphism expressivity rather than supervised prediction. Our k=1k=1 result shows that ILG-11-WL is strictly weaker than root 11-WL on Whitney-general graphs. Other line-graph networks report improved task performance. This may arise because the line-graph representation makes useful structural information easier for the model to use, together with task-specific edge features, training, or model bias. Many standard graph-classification datasets contain few hard 11-WL collisions [29]. Since edges are the native line-graph objects, link-level tasks provide a natural setting for downstream evaluation [19]. Backward transfer for k≥4k≥ 4 remains open. The k=3k=3 proof reconstructs the coherent matrix algebra of stable pair refinement; extending it would require a corresponding reconstruction of higher-arity root tuple colors and simultaneous endpoint choices. Repeated line-graph transformation may also simplify isomorphism testing with 33-WL: at most two transformations take every connected graph other than C3,C4,C5C_3,C_4,C_5 outside the strongly regular class [28]. Determining whether this allows 33-WL to distinguish additional graph pairs is an interesting direction for future work. References [1] M. Allamanis, M. Brockschmidt, and M. Khademi (2018) Learning to represent programs with graphs. In International Conference on Learning Representations, External Links: Link Cited by: §1. [2] M. Balcilar, P. Héroux, B. Gaüzère, P. Vasseur, S. Adam, and P. Honeine (2021) Breaking the limits of message passing graph neural networks. In Proceedings of the 38th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 139, p. 599–608. External Links: Link Cited by: §1, §6.1. [3] B. Bevilacqua, F. Frasca, D. Lim, B. Srinivasan, C. Cai, G. Balamurugan, M. M. Bronstein, and H. Maron (2022) Equivariant subgraph aggregation networks. In International Conference on Learning Representations, External Links: Link Cited by: §1. [4] C. Bodnar, F. Frasca, N. Otter, Y. Wang, P. Liò, G. Montúfar, and M. Bronstein (2021) Weisfeiler and Lehman go cellular: CW networks. In Advances in Neural Information Processing Systems, Vol. 34, p. 2625–2640. External Links: Link Cited by: §1. [5] C. Bodnar, F. Frasca, Y. Wang, N. Otter, G. F. Montúfar, P. Liò, and M. M. Bronstein (2021) Weisfeiler and Lehman go topological: message passing simplicial networks. In Proceedings of the 38th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 139, p. 1026–1037. External Links: Link Cited by: §1, §1. [6] J. Cai, M. Fürer, and N. Immerman (1992) An optimal lower bound on the number of variables for graph identification. Combinatorica 12 (4), p. 389–410. External Links: Document Cited by: §6.1. [7] L. Cai, J. Li, J. Wang, and S. Ji (2022) Line graph neural networks for link prediction. IEEE Transactions on Pattern Analysis and Machine Intelligence 44 (9), p. 5103–5113. External Links: Document Cited by: §1. [8] G. Chen and I. Ponomarenko (2019) Lectures on coherent configurations. Note: Online lecture notesUpdated edition External Links: Link Cited by: §A.7. [9] Z. Chen, L. Li, and J. Bruna (2019) Supervised community detection with line graph neural networks. In International Conference on Learning Representations, External Links: Link Cited by: §1. [10] K. Choudhary and B. DeCost (2021) Atomistic line graph neural network for improved materials property predictions. npj Computational Materials 7, p. 185. External Links: Document Cited by: §1. [11] L. Du, L. Bai, J. Li, L. Cui, H. Du, L. Zhang, Y. Chen, and Z. Li (2026) LGAN: an efficient high-order graph neural network via the line graph aggregation. Proceedings of the AAAI Conference on Artificial Intelligence 40 (25), p. 20914–20922. External Links: Document Cited by: §1. [12] J. Feng, L. Kong, H. Liu, D. Tao, F. Li, M. Zhang, and Y. Chen (2023) Extending the design space of graph neural networks by rethinking folklore Weisfeiler-Lehman. In Advances in Neural Information Processing Systems, Vol. 36, p. 9029–9064. External Links: Document, Link Cited by: §A.1, §A.1, Appendix A, §D.6, §2, §2, §2, §3.3, §3.3, §4.1, §4.2, §4.3. [13] F. Fuhlbrück, J. Köbler, and O. Verbitsky (2021) Identifiability of graphs with small color classes by the Weisfeiler–Leman algorithm. SIAM Journal on Discrete Mathematics 35 (3), p. 1792–1853. External Links: Document Cited by: §A.1, §A.1, §A.1. [14] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl (2017) Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 70, p. 1263–1272. External Links: Link Cited by: §1. [15] M. Grohe (2017) Descriptive complexity, canonisation, and definable graph structure theory. Lecture Notes in Logic, Vol. 47, Cambridge University Press. External Links: Document Cited by: §D.3, §4.1. [16] W. L. Hamilton, Z. Ying, and J. Leskovec (2017) Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, Vol. 30, p. 1024–1034. External Links: Link Cited by: §1. [17] X. Jiang, R. Zhu, P. Ji, and S. Li (2023) Co-embedding of nodes and edges with graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence 45 (6), p. 7075–7086. External Links: Document Cited by: §1. [18] E. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song (2017) Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, Vol. 30, p. 6348–6358. External Links: Link Cited by: §1. [19] V. Lachi, F. Ferrini, A. Longa, B. Lepri, A. Passerini, and M. Jaeger (2025) Bridging theory and practice in link representation with graph neural networks. In Advances in Neural Information Processing Systems, Vol. 38. External Links: Document, Link Cited by: §7. [20] H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman (2019) Provably powerful graph networks. In Advances in Neural Information Processing Systems, Vol. 32, p. 2156–2167. External Links: Link Cited by: Appendix F, §1, §3.3. [21] C. Morris, G. Rattan, and P. Mutzel (2020) Weisfeiler and Leman go sparse: towards scalable higher-order graph embeddings. In Advances in Neural Information Processing Systems, Vol. 33, p. 21824–21840. External Links: Link Cited by: §1. [22] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe (2019) Weisfeiler and Leman go neural: higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, p. 4602–4609. External Links: Document, Link Cited by: Appendix F, §1, §2. [23] I. Ponomarenko (2023) On the WL-dimension of circulant graphs of prime power order. Algebraic Combinatorics 6 (6), p. 1469–1490. External Links: Document Cited by: §A.1, §A.1, §A.7. [24] M. V. Ramana, E. R. Scheinerman, and D. Ullman (1994) Fractional isomorphism of graphs. Discrete Mathematics 132 (1–3), p. 247–265. External Links: Document Cited by: §D.3, §4.1. [25] Y. Wang and M. Zhang (2024) An empirical study of realized GNN expressiveness. In Proceedings of the 41st International Conference on Machine Learning, R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp (Eds.), Proceedings of Machine Learning Research, Vol. 235, p. 52134–52155. External Links: Link Cited by: Appendix F, Appendix F, §6.1, §6.2, Table 1. [26] H. Whitney (1932) Congruent graphs and the connectivity of graphs. American Journal of Mathematics 54 (1), p. 150–168. External Links: Document Cited by: §A.1, §1, Definition 1. [27] K. Xu, W. Hu, J. Leskovec, and S. Jegelka (2019) How powerful are graph neural networks?. In International Conference on Learning Representations, External Links: Link Cited by: §D.7, §1, §5. [28] F. Yang and X. Huang (2024) Theoretical insights into line graph transformation on graph learning. In NeurIPS 2024 Workshop on Symmetry and Geometry in Neural Representations, Note: Poster External Links: Link Cited by: §1, §7. [29] M. Zopf (2022) 1-WL expressiveness is (almost) all you need. In 2022 International Joint Conference on Neural Networks, External Links: 2202.10156 Cited by: §7. Appendix A Proof of the 33-WL Backward-Transfer Theorem This appendix first proves the connected Whitney-general core, Theorem 1, using joint pair refinement, and then derives the componentwise extension in Theorem 2. Throughout the core proof, G,HG,H denote the two root graphs and L(G),L(H)L(G),L(H) their line graphs; we do not rename either line graph. “Pair refinement” means the joint ordered-pair update below, i.e., 2-FWL. By the standard arity-shift theorem, its stable graph-distinguishing power equals that of the paper’s separate-coordinate 33-WL [12]. The symbol ∘ denotes the Hadamard (entrywise) product. Proof outline. The proof proceeds in five steps. First, we characterize stable pair refinement by its coherent matrix algebra. Second, we determine root endpoint degrees and star and dart profiles from the stable pair algebra of L(G)L(G). Third, we use these profiles to construct root-side algebras and an isomorphism Ω induced by the line-algebra isomorphism. Fourth, we construct the root profile cells at distances zero and one, treating unequal and equal profile fibers separately. Fifth, we construct the remaining cells by induction on root distance. The resulting algebras are Hadamard closed, and Ω then restricts to an isomorphism of the stable root pair algebras. A.1 Coherent-algebra characterization of pair refinement We first record the standard characterization of joint pair refinement by coherent configurations. Proposition 2.3 of Fuhlbrück et al. [13] identifies the stable joint-pair partition with the coherent closure of the graph relations, and their Lemma 2.4 proves that an algebraic isomorphism preserves every refinement round; see also Ponomarenko [23, Sections 2.2, 2.5, and 3.1]. Those references call the joint update on ordered pairs 22-WL. In the graph-learning terminology used here it is 2-FWL; its equivalence in stable graph-distinguishing power to separate-coordinate 33-WL is the separate arity-shift result [12]. We include the short derivation needed here so that the matrix identities and their index order are explicit. For a graph G, pair refinement assigns colors to ordered pairs by the joint-replacement update ct+1G(x,y)=HASH(ctG(x,y),(ctG(z,y),ctG(x,z)):z∈V(G)).c_t+1^G(x,y)=HASH (c_t^G(x,y), \\! \ (c_t^G(z,y),c_t^G(x,z) ):z∈ V(G) \\! \ ). The order of the two entry components agrees with the global-replacement formula in Section 3.3. Some references list the two entry coordinates in the reverse order; the fixed coordinate swap is a bijection on entries and does not change the induced refinement partition. The initial color c0G(x,y)c_0^G(x,y) records whether x=yx=y, whether x and y are adjacent, or whether they are distinct and nonadjacent. Write c∞Gc_∞^G for the stable coloring, attained at the first round after which one further update no longer refines the induced partition of ordered pairs. Call two graphs pair-refinement equivalent when the stable graph-level signatures of their joint pair refinements, computed with the shared injective encoding of Section 2, are equal. By the standard arity-shift theorem, this is equivalent in stable graph-distinguishing power to G≡3-WLHG _3-WLH [12]. For a stable color ρ, define its 00-11 relation matrix by (RρG)xy=[c∞G(x,y)=ρ].(R_ρ^G)_xy=1[c_∞^G(x,y)=ρ]. We use the same symbol RρGR_ρ^G for the matrix and for its support relation (x,y):c∞G(x,y)=ρ\(x,y):c_∞^G(x,y)=ρ\, writing (x,y)∈RρG(x,y)∈ R_ρ^G accordingly. At stabilization, one more refinement round does not split a color class. Hence, if both (x,y)(x,y) and (x′,y′)(x ,y ) have stable color τ, their stable multisets of replacement entries are equal. The multiplicity of the entry (σ,ρ)(σ,ρ) is therefore independent of the chosen pair of color τ. This defines the intersection number pρστ=|z:(x,z)∈RρG,(z,y)∈RσG|((x,y)∈RτG).p_ρσ^τ= |\z:(x,z)∈ R_ρ^G,\ (z,y)∈ R_σ^G\ | ((x,y)∈ R_τ^G). This representative-independence is the standard intersection-number axiom for a coherent configuration [23, Section 2.2, condition (C3)]; the argument above shows directly why stable pair refinement satisfies it. The reversed order (σ,ρ)(σ,ρ) is exactly the entry order in the update: (z,y)(z,y) has color σ and (x,z)(x,z) has color ρ. Entrywise, for (x,y)∈RτG(x,y)∈ R_τ^G, (RρGRσG)xy (R_ρ^GR_σ^G)_xy =∑z∈V(G)(RρG)xz(RσG)zy = _z∈ V(G)(R_ρ^G)_xz(R_σ^G)_zy =|z:(x,z)∈RρG,(z,y)∈RσG|=pρστ. = |\z:(x,z)∈ R_ρ^G,\ (z,y)∈ R_σ^G\ |=p_ρσ^τ. Because the stable relations partition V(G)2V(G)^2, this entrywise identity is equivalent to RρGRσG=∑τpρστRτG.R_ρ^GR_σ^G= _τp_ρσ^τR_τ^G. The matrices RρGR_ρ^G have disjoint supports and sum to JV(G)J_V(G). The equality and adjacency relations are unions of stable classes because they are distinguished initially, so their real span GA_G contains IV(G)I_V(G) and AGA_G, as well as JV(G)J_V(G). The displayed product formula proves closure under ordinary multiplication. Coordinate swap permutes the stable classes: this follows by induction from the symmetric initial types. If a⊤,b⊤a ,b denote the reversed colors at one round, then an entry (a,b)(a,b) becomes (b⊤,a⊤)(b ,a ) after reversing the outer pair. Thus (RρG)⊤(R_ρ^G) is another basis relation; write ρ⊤ρ for its color, so (RρG)⊤=Rρ⊤G(R_ρ^G) =R_ρ ^G, and write |RρG||R_ρ^G| for the number of ones in RρGR_ρ^G. Disjointness gives RρG∘RσG=[ρ=σ]RρG.R_ρ^G R_σ^G=1[ρ=σ]R_ρ^G. Thus GA_G is closed under transpose and Hadamard multiplication as well. Call a real linear space of square matrices that contains the identity and all-ones matrices and is closed under transpose, ordinary multiplication, and Hadamard multiplication a coherent matrix algebra; GA_G is the stable pair coherent algebra of G. Lemma 2 (Stable-pair algebra characterization). Graphs G,HG,H are pair-refinement equivalent if and only if there is a bijection π between their stable pair colors such that the linear map φ(RρG)=Rπ(ρ)H (R_ρ^G)=R_π(ρ)^H maps IV(G),JV(G),AGI_V(G),J_V(G),A_G to IV(H),JV(H),AHI_V(H),J_V(H),A_H and preserves transpose, ordinary multiplication, Hadamard multiplication, and matrix trace. Proof. Run pair refinement on G and H in parallel with the shared injective color encoding fixed in Section 2. If the stable signatures agree, matching color names gives a bijection π and preserves every relation multiplicity |RρG|=|Rπ(ρ)H||R_ρ^G|=|R_π(ρ)^H|. A stable color τ records its initial equality/adjacency type and the multiplicity of every replacement entry. The observation above therefore shows that π preserves every intersection number pρστp_ρσ^τ, with the same statement for the transposed colors. In particular, π(ρ⊤)=π(ρ)⊤π(ρ )=π(ρ) . Consequently the displayed linear map preserves ordinary multiplication and transpose. It preserves Hadamard multiplication by the disjoint-support identity above. Initial types give preservation of I,AI,A, summing all basis matrices gives preservation of J, and matching relation sizes gives trace preservation: tr(RρG)=|RρG|tr(R_ρ^G)=|R_ρ^G| for an equality-type color and is zero otherwise. Hence trace is preserved on the whole span. Conversely, suppose such a basis bijection and linear map exist. Preservation of I,AI,A, transpose, and multiplication preserves the initial types and all intersection numbers. More explicitly, uniqueness of expansion in the disjoint basis shows from φ(IV(G))=IV(H) (I_V(G))=I_V(H) and φ(AG)=AH (A_G)=A_H that π preserves equality and adjacency type; uniqueness of the expansion of RρRσR_ρR_σ then shows that it preserves every pρστp_ρσ^τ. To see explicitly why this recovers the refinement, observe inductively that each round-t color is a union of stable relations. For a stable relation RτGR_τ^G, the multiplicity of a round-t entry (b,a)(b,a) is the sum of pρστp_ρσ^τ over the stable relations RρGR_ρ^G contained in a and RσGR_σ^G contained in b. Thus the transported unions have identical entry multisets at the next round. This is the same induction as in Fuhlbrück et al. [13, Lemma 2.4], with the two entry components reversed to match our convention. It remains to match graph-level color multiplicities. Trace preservation applied to RρG(RρG)⊤R_ρ^G(R_ρ^G) gives |RρG|=tr(RρG(RρG)⊤)=|Rπ(ρ)H|.|R_ρ^G|=tr\! (R_ρ^G(R_ρ^G) )=|R_π(ρ)^H|. Thus the matched stable colors have the same refinement data and the same multiplicities, so their stable graph-level signatures agree. This is the standard coherent-configuration characterization quoted above. ∎ Equivalently, GA_G is the smallest coherent matrix algebra containing IV(G),JV(G),AGI_V(G),J_V(G),A_G [13, Propositions 2.1 and 2.3]. We also use that a joint level set of finitely many matrices in GA_G is a union of basis relations. Its indicator belongs to GA_G by finite Hadamard interpolation. Explicitly, for a transported pair of matrices, take the union of the finite sets of entries attained on the two sides. For a requested value a in that union, choose the Lagrange polynomial that is one at a and zero at every other value in the union, and evaluate it entrywise using Hadamard products. If a is not attained on one side, the resulting equality indicator on that side is the zero matrix. A requested value outside the union is assigned the zero indicator on both sides. The Hadamard product of these single-matrix indicators is the desired joint-level-set indicator. Because the same polynomial is used on both sides, the entire construction is transported. This convention applies to every entrywise selector below. The paw is a triangle with one pendant edge, and the diamond is K4K_4 with one edge removed. These names are used only for the two small local configurations isolated below. Lemma 3 (Exceptional roots handled directly). Assume G,HG,H are Whitney-general and L(G)≡3-WLL(H)L(G) _3-WLL(H). If either root is K1,K2K_1,K_2, the paw, or the diamond, then G≅HG H. Proof. On a diagonal pair (e,e)(e,e), the multiplicity of adjacency-colored replacement entries records dL(G)(e)d_L(G)(e); hence pair refinement preserves line-graph order and degree multiplicities. Equivalently, the line degree on a diagonal fiber is the sum of the out-valencies of its outgoing adjacent basis relations, while the fiber size is its trace; all these quantities are transported. A connected root with an empty line graph is K1K_1, and a connected root with a one-vertex line graph is K2K_2. The line graph of the paw has degree multiset (3,3,2,2)(3,3,2,2): the two degree-three vertices are universal, so this uniquely determines K4K_4 minus one edge. The line graph of the diamond has degree multiset (4,3,3,3,3)(4,3,3,3,3): the degree-four vertex is universal and the other four vertices induce C4C_4, so the line graph is uniquely K1∨C4K_1 C_4, where ∨ denotes graph join. In either case L(G)L(G) and L(H)L(H) are isomorphic. Neither line graph is K3K_3, so Whitney’s theorem [26] gives G≅HG H. ∎ A.2 Stable line data and root profiles For the remainder, let G,HG,H be Whitney-general roots satisfying L(G)≡3-WLL(H)L(G) _3-WLL(H), and assume by Lemma 3 that both roots have order at least three and that neither is the paw or the diamond. These cases are separated from the general construction for the following reasons. For roots of orders one and two, the line algebra contains no adjacent basis relation. The paw and diamond are the additional Whitney-general roots for which, respectively, the degree collision (A.3) of Lemma 4 and the wedge ambiguity (A.4) of Lemma 6 occur. Lemma 3 treats all four cases directly and proves G≅HG H. Thus only the construction below excludes them. Let L(G)A_L(G) have basis relations RρL(G)R_ρ^L(G). Write DαL(G)D_α^L(G) for those basis relations supported on the coordinate diagonal; each is a diagonal 00-11 projector. Define the associated edge fiber ℰαG=e∈E(G):(DαL(G))ee=1.E_α^G=\e∈ E(G):(D_α^L(G))_e=1\. Define RρL(H),DαL(H),ℰαHR_ρ^L(H),D_α^L(H),E_α^H analogously. We call RρL(G)R_ρ^L(G) adjacent when its support is contained in AL(G)A_L(G), and disjoint when its support consists of ordered pairs of disjoint root edges. If RρL(G)=DαL(G)RρL(G)DβL(G)R_ρ^L(G)=D_α^L(G)R_ρ^L(G)D_β^L(G), write src(ρ)=αsrc(ρ)=α and tgt(ρ)=βtgt(ρ)=β; its out-valency is νρ=|f∈ℰβG:(e,f)∈RρL(G)|,e∈ℰαG. _ρ= |\f _β^G:(e,f)∈ R_ρ^L(G)\ |, e _α^G. Every basis relation lies in a unique block ℰαG×ℰβGE_α^G×E_β^G, so its source and target fibers are well defined. The intersection-number identities make νρ _ρ independent of e, and it is positive for a nonempty basis relation. Summing over the adjacent relations from ℰαE_α to ℰδE_δ gives the fiber valency qαδq_αδ: every e∈ℰαe _α has exactly qαδq_αδ line neighbors in ℰδE_δ. We refer to this constancy as equitability of the diagonal fibers; the numbers qαδq_αδ are sums of intersection numbers. Lemma 2 supplies φ:L(G)⟶L(H) :A_L(G) _L(H) matching all stated algebra operations and trace, with φ(RρL(G))=RρL(H) (R_ρ^L(G))=R_ρ^L(H) and φ(DαL(G))=DαL(H) (D_α^L(G))=D_α^L(H) after synchronizing the labels. From now on, unadorned Rρ,Dα,ℰαR_ρ,D_α,E_α denote the L(G)L(G)-relation, L(G)L(G)-projector, and G-edge fiber, respectively. Their transported mates retain the explicit notation RρL(H),DαL(H),ℰαHR_ρ^L(H),D_α^L(H),E_α^H. We call any such matched objects transported. Coordinate unit vectors are denoted by αe_α or ρe_ρ, according to the index set. For a matrix M, [M=a]1[M=a] denotes the entrywise 00-11 matrix with (e,f)(e,f)-entry [Mef=a]1[M_ef=a]; entrywise inequalities such as [M>0]1[M>0] are interpreted analogously. Finally, every automorphism of a root induces an automorphism of its line graph and, by induction on rounds, preserves each refinement color; stable colors, fibers, and all profiles defined below are therefore automorphism invariant. For a root vertex u, define its star profile (u)=(sα(u))α,sα(u)=|e∈ℰα:u∈e|.s(u)=(s_α(u))_α, s_α(u)= |\e _α:u∈ e\ |. Thus (u)s(u) counts incident root edges by their stable diagonal color in L(G)L(G). A dart is an incident pair (u,e)(u,e) with u∈eu∈ e. For e∈ℰαe _α, define its dart profile (u,e)ρ=|f≠e:u∈f,(e,f)∈Rρ|,d(u,e)_ρ= |\f≠ e:u∈ f,\ (e,f)∈ R_ρ\ |, indexed by all basis relations; it is supported on the adjacent relations leaving ℰαE_α, and only those coordinates appear below. It refines the u-wing of e, namely the other edges incident with u, by the stable relation from e to each such edge. Summing coordinates by target fiber recovers the star profile: sβ(u)=[α=β]+∑ρ adjacent:src(ρ)=α,tgt(ρ)=β(u,e)ρ.s_β(u)=1[α=β]+ _ subarraycρ adjacent:\,src(ρ)=α,\;tgt(ρ)=β subarrayd(u,e)_ρ. The indicator accounts for e itself, which is included in (u)s(u) but excluded from (u,e)d(u,e). For adjacent root edges e=uv,f=uwe=uv,f=uw, call u the center and v,wv,w the outer vertices. The wedge is closed if vwvw is an edge, and open otherwise; in the closed case vwvw is its closing edge. For a root quantity q, call a transported relation label mixed if q is nonconstant on its support in either root or has different constant values on the two transported supports. Thus proving that a label is not mixed proves both within-root constancy and cross-root transport. For a root edge e=uve=uv, put δu=dG(u)−1,δv=dG(v)−1,te=|NG(u)∩NG(v)|; _u=d_G(u)-1, _v=d_G(v)-1, t_e=|N_G(u)∩ N_G(v)|; in comparisons between two representatives, d and N refer to the root containing the displayed representative. For f∈NL(G)(e)f∈ N_L(G)(e), let λe(f)=|NL(G)(e)∩NL(G)(f)| _e(f)=|N_L(G)(e)∩ N_L(G)(f)|, and define LDG(e)=λe(f):f∈NL(G)(e).LD_G(e)= \\! \ _e(f):f∈ N_L(G)(e) \\! \. For integers 0≤δu≤δv0≤ _u≤ _v and 0≤t≤δu0≤ t≤ _u, define the multiset F(δu,δv,t)=[δu]t⊎[δu−1]δu−t⊎[δv]t⊎[δv−1]δv−t,F( _u, _v,t)=[ _u]^t [ _u-1] _u-t [ _v]^t [ _v-1] _v-t, where ⊎ is multiset union and [a]b[a]^b denotes b copies of a. Lemma 4 (Line-degree multisets and their collisions). The diagonal pair color of a root edge e determines LDG(e)LD_G(e), and the multiset is transported. Moreover, LDG(e)=F(δu,δv,te)LD_G(e)=F( _u, _v,t_e) with δu≤δv _u≤ _v, and F determines its three arguments except for the single collision F(0,2,0)=F(1,1,1)=[1,1].F(0,2,0)=F(1,1,1)=[1,1]. Proof. The diagonal pair color of e determines the multiset. Indeed, AL(G)2A_L(G)^2 is in the coherent algebra, so it has a constant value ℓρ _ρ on every adjacent basis relation RρR_ρ. If e∈ℰαe _α, then LDG(e)=⨄ρadjacentsrc(ρ)=α[ℓρ]νρ.LD_G(e)= _ subarraycρ\ adjacent\\ src(ρ)=α subarray[ _ρ] _ρ. Both ℓρ _ρ and the out-valency νρ _ρ are intersection-number data, so this multiset is also transported. Listing the two endpoint wings gives LDG(e)=F(δu,δv,te)LD_G(e)=F( _u, _v,t_e): each wing at an endpoint of degree d contributes one half of (A.2), with tet_e of its edges closed by the opposite endpoint. For the uniqueness claim, |F|=δu+δv|F|= _u+ _v; for nonempty F, maxF=δv−1 F= _v-1 when te=0t_e=0 and δv _v when te>0t_e>0. If two candidates have the same te=0t_e=0 status, these data recover δu,δv _u, _v; for te>0t_e>0, the identity ∑F=δu(δu−1)+δv(δv−1)+2teΣ F= _u( _u-1)+ _v( _v-1)+2t_e recovers tet_e. A collision across the two statuses must compare a positive-t candidate (a,b,t)(a,b,t) with (a−1,b+1,0)(a-1,b+1,0): equality of cardinalities and maxima gives these two shifts. The zero-t multiset contains b+1b+1 copies of its maximum b, which forces a=ba=b; otherwise the positive candidate has at most a<ba<b such copies. With a=ba=b, the zero-t candidate also contains a−1a-1 copies of a−2a-2, absent from the positive candidate. Hence a=1a=1, and equality of the remaining multiplicities forces t=1t=1. This is exactly (A.3). The empty case is immediate. ∎ Lemma 5 (Endpoint-degree recovery). Every diagonal fiber of L(G)A_L(G) fixes its unordered endpoint degrees, and these labels are transported by φ . Proof. By Lemma 4, only the collision (A.3) could make a transported diagonal fiber mixed in its unordered endpoint degrees. In root language, (A.3) confuses a pendant (1,3)(1,3)-edge with a triangular (2,2)(2,2)-edge. Suppose two representatives of a transported diagonal fiber ℰαE_α, either in one root or one in each root, realize the two cases. Write the pendant edge as e=pce=pc, with the other edges at the degree-three vertex c equal to f1=ca,f2=cbf_1=ca,f_2=cb. Write the triangular edge as e′=uve =uv in uvwuvw, with f1′=uw,f2′=vwf _1=uw,f _2=vw. The degree-two vertices u,vu,v are adjacent true twins, so swapping them is a root automorphism; it shows that f1′,f2′f _1,f _2 have one diagonal color β. The α-edge e′e has exactly these two line neighbors. Equitability of the diagonal α-fiber therefore makes the two line neighbors f1,f2f_1,f_2 of e both β-colored. If d(w)=2d(w)=2, then f1′f _1 is again triangular of type (2,2)(2,2), whereas f1f_1, having a degree-three endpoint, must be pendant by (A.3). Thus d(a)=d(b)=1d(a)=d(b)=1, and connectedness gives K1,3K_1,3 on the pendant side and K3K_3 on the triangular side. If d(w)>2d(w)>2, uniqueness of F for the matched β-edges transports both their endpoint degrees and their value te=1t_e=1. Explicitly, 2,d(w)=3,d(a)\2,d(w)\=\3,d(a)\, so d(w)=3,d(a)=2d(w)=3,d(a)=2, and the common-neighbor count gives one common neighbor of c,ac,a, necessarily b. Thus abab is an edge, symmetrically d(b)=2d(b)=2, and p,c,a,bp,c,a,b form a paw and exhaust their degrees. For g=abg=ab, the line vertices e,ge,g have the same open neighborhood, namely f1,f2\f_1,f_2\. Swapping these line-graph twins is an automorphism, so g also has color α. Thus f1f_1 has two α-neighbors. Equitability at the matched β-vertices f1,f1′f_1,f _1 forces f1′f _1 to have two as well. Because the β-fiber has endpoint type 2,3\2,3\, it differs from α; hence f2′f _2 is not the second one, and the third edge h=wrh=wr at w has color α. Since d(w)=3d(w)=3, (A.3) makes h pendant, and the other root is also a paw. In the within-root comparison, the same exhausted configurations are components. Thus the only propagated collisions are the Whitney pair and the paw, and both are excluded by the standing hypotheses. ∎ Lemma 6 (Central degree and wedge type). Every adjacent basis relation fixes its central degree and whether its wedges are open or closed, and these labels are transported by φ . Proof. Take an adjacent pair e=uv,f=uwe=uv,f=uw. Its coherent common-neighbor number is (AL(G)2)ef=d(u)−2+[vw∈E(G)].(A_L(G)^2)_ef=d(u)-2+1[vw∈ E(G)]. If a relation were mixed in its central degree, (A.4) would force a closed wedge of degree c and an open wedge of degree c+1c+1. Lemma 5 fixes the unordered endpoint degrees of each source and target fiber. For either leg, equality of those unordered pairs reads c,d(closed outer)=c+1,d(open outer)\c,d(closed outer)\=\c+1,d(open outer)\. Thus the closed outer endpoint has degree c+1c+1 and the open outer endpoint degree c; all four wedge legs have endpoint type c,c+1\c,c+1\. Let Πh _h be the sum of the diagonal projectors of endpoint type c+1,c+1\c+1,c+1\, and set M=AL(G)Πh,Q=MM⊤.M=A_L(G) _h, Q=M . Here QefQ_ef counts the high–high edges adjacent in L(G)L(G) to both e and f. In the closed realization the only such common neighbor is the closing high–high edge, so Qef=1Q_ef=1. In the open realization the center is the common high endpoint of e,fe,f, so every high–high edge adjacent to e is also adjacent to f, and Qef=QeeQ_ef=Q_e. Constancy on the common basis relation first equates this open value to the closed value one; constancy and transport on the source and target diagonal fibers then equate the corresponding diagonal values. Since QeeQ_e counts high–high edges at the high endpoint of e, every involved degree-(c+1)(c+1) endpoint consequently has exactly one high-degree neighbor. Let U=[Q=1]U=1[Q=1] and put T=AL(G)∘UT=A_L(G) U. The two realizations now have the following data: center degreeouter degrees(T2)efopenc+1c,c−2closedcc+1,c+10 array[]c|c|c|c¢er degree&outer degrees&(T^2)_ef\\ &c+1&c,c&c-2\\ closed&c&c+1,c+1&0 array Indeed, in the open realization the unique high–high edge at the center is not a T-neighbor of itself, whereas each of the other c−2c-2 center edges is a common T-neighbor of e,fe,f. In the closed realization the center is low, and each high outer endpoint has only the closing high–high edge; the closing edge itself is not a T-neighbor, so there is no common T-neighbor. Constancy of T2T^2 on the common relation gives c−2=0c-2=0, hence c=2c=2. A source edge in the closed realization then has two T-neighbors: the other wedge leg and the remaining edge at its degree-three outer endpoint. In the open realization it has the other wedge leg, plus a second T-neighbor exactly when its degree-two outer endpoint is adjacent to the center’s unique high-degree neighbor. Since (T2)ee(T^2)_e is the T-degree of e, equality of the corresponding source diagonal entries forces this edge, and the target calculation forces its analogue at the other outer vertex. The four vertices form a diamond and exhaust their degrees, so connectedness makes the root the diamond, contrary to the hypothesis. ∎ For an edge fiber ℰαE_α, collect the fiber valencies into α=(qαβ)β+2α.q_α=(q_αβ)_β+2e_α. The two endpoint wings of every α-edge uvuv, together with the edge itself once at each endpoint, give (u)+(v)=α.s(u)+s(v)=q_α. For an adjacent basis relation RγR_γ with source ℰαE_α, target ℰβE_β, and representative e=uve=uv, f=uwf=uw, define the vectors hγ⋆(δ)=(AL(G)DδAL(G))ef,hγd(ρ)=(RρAL(G))ef,h _γ(δ)=(A_L(G)D_δA_L(G))_ef, h^d_γ(ρ)=(R_ρA_L(G))_ef, indexed by the diagonal fibers δ and by the adjacent basis relations ρ, respectively. The first counts the common line neighbors of e,fe,f lying in ℰδE_δ; the second counts the common line neighbors g with (e,g)∈Rρ(e,g)∈ R_ρ. Both are sums of intersection numbers, hence constant on RγR_γ and transported. Profile-difference observation. We use the following observation twice. For a closed adjacent relation RγR_γ, suppose each representative has a profile of the form vγ−ℓv_γ-e_ , where the vector vγv_γ is transported and depends only on γ, and the label ℓ is carried by the closing edge of the representative. If such a relation is mixed between profiles ≠x whose representatives carry closing labels ℓ _x and ℓ _y, subtraction gives −=ℓ−ℓ,y-x=e_ _x-e_ _y, so ℓ≠ℓ _x≠ _y, and the two profiles differ, by one, in exactly the two coordinates ℓ,ℓ _x, _y. If moreover the fixed unordered endpoint-profile pair of the source fiber is transported and contains the central profile of every representative, then that pair equals ,\x,y\ in each root, and ,x,y are the only profiles realized on RγR_γ. Lemma 7 (Endpoint star profiles). Every diagonal fiber of L(G)A_L(G) fixes its unordered endpoint star profiles, and every open adjacent basis relation fixes its central star profile. These labels are transported by φ . Proof. Let RγR_γ be an open adjacent relation with source fiber ℰαE_α and target fiber ℰβE_β. The common line neighbors of an open wedge e=uv,f=uwe=uv,f=uw are exactly the other edges at u, so (u)=α+β+hγ⋆.s(u)=e_α+e_β+h _γ. Every nonempty relation has positive constant out-valency on its source fiber. Thus, if an open relation leaves ℰαE_α, every α-edge is the source of a pair in that relation; (A.6) supplies one endpoint profile and (A.5) supplies the other. If none leaves ℰαE_α, then for each α-edge uvuv, every neighbor of either endpoint other than the other endpoint is adjacent to both. Here write N[x]=N(x)∪xN[x]=N(x)∪\x\ for the closed neighborhood. Swapping the adjacent true twins u,vu,v, whose closed neighborhoods coincide, is a root automorphism; its induced line-graph automorphism fixes e and interchanges its two wings. Stable colors are automorphism invariant, so the profiles agree coordinatewise and equal α/2q_α/2. This proves the endpoint-profile assertion, while (A.6) proves the open central-profile assertion. ∎ Lemma 8 (Central star profiles and class sizes). Every adjacent basis relation fixes its central star profile, and every star-profile class size is determined and transported. Proof. By Lemma 7, only a closed relation RγR_γ, with source ℰαE_α and target ℰβE_β, could be mixed between central profiles ≠x . If its x-centered representative has closing-edge fiber χ, direct listing gives hγ⋆=−α−β+χ,h _γ=x-e_α-e_β+e_χ, so the central profile is (α+β+hγ⋆)−χ(e_α+e_β+h _γ)-e_χ, of the form required by the profile-difference observation with the closing-edge fiber as label. With ξ the closing fiber of a y-centered representative, the principle gives −=χ−ξ,y-x=e_χ-e_ξ, and, since Lemma 7 fixes and transports the unordered endpoint pair of the source and target fibers, that pair equals ,\x,y\ and no other central profile occurs on RγR_γ. For K∈G,HK∈\G,H\, let CK=u∈V(K):K(u)=,CK=u∈V(K):K(u)=,C_x^K=\u∈ V(K):s_K(u)=x\, C_y^K=\u∈ V(K):s_K(u)=y\, where Ks_K denotes the star profile in K. We suppress the root superscript inside a one-root calculation. Since both central labels occur in the source and target fibers, Lemma 7 makes every source or target edge of γ join C_x to C_y. In the x-centered realization the χ-edge joins the two outer C_y-vertices, so the fixed endpoint pair of fiber χ is ,\y,y\. Since ≠x , (A.7) gives ξ≠χξ≠χ; moreover xχ=0x_χ=0, and its χ-coordinate gives yχ=1y_χ=1. Consequently (xχ,yχ)=(0,1)(x_χ,y_χ)=(0,1). Symmetrically the ξ-fiber joins C_x to itself and (xξ,yξ)=(1,0)(x_ξ,y_ξ)=(1,0). Hence the ξ- and χ-edges form perfect matchings on C_x and C_y, respectively. Take a x-centered representative e=uv∈ℰαe=uv _α, f=uw∈ℰβf=uw _β, closed by vw∈ℰχvw _χ, and let uu¯∈ℰξu u _ξ be the matching edge at u. For an x-centered γ-pair, this matching edge is its unique common ξ-edge; for a y-centered pair, the closing edge is the unique common ξ-edge. In the latter realization, let Rη,RθR_η,R_θ be the two relations through that witness. Their middle fiber is the ξ-fiber, so every (η,θ)(η,θ)-intermediate is a common ξ-edge. Therefore pηθγ=1p_ηθ^γ=1, while every other decomposition through the ξ-fiber has multiplicity zero. Transport makes uu¯u u the unique witness with (e,uu¯)∈Rη(e,u u)∈ R_η and (uu¯,f)∈Rθ(u u,f)∈ R_θ. In the y-centered realization the witness is the closing edge, so both leg relations are closed. Wedge-type transport (Lemma 6) now supplies u¯v,u¯w uv, uw, producing a K4K_4 with opposite matching-edge fibers ξ,χξ,χ. For every edge fiber δ∉ξ,χδ∉\ξ,χ\, (A.7) gives xδ=yδx_δ=y_δ. If this common coordinate is positive, the fixed endpoint pair of δ contains both profiles and therefore is ,\x,y\; if it is zero, no δ-edge meets either class. Together with the matchings, this shows that C∪C_x∪ C_y has no edge to a third profile class. Connectedness yields V(G)=CG∪˙CGV(G)=C_x^G ∪C_y^G, and analogously for H. After deleting the two internal matchings, the remaining bipartite graph is κ-regular, where κ=∑δ∉ξ,χxδ=∑δ∉ξ,χyδκ= _δ∉\ξ,χ\x_δ= _δ∉\ξ,χ\y_δ. Let DξD_ξ be the diagonal projector onto the ξ-matching edges and define Mξ=AL(G)DξAL(G),Wξ=AL(G)∘Mξ.M_ξ=A_L(G)D_ξA_L(G), W_ξ=A_L(G) M_ξ. Since DξD_ξ and AL(G)A_L(G) are transported, so are Mξ,WξM_ξ,W_ξ, and Wξ2W_ξ^2, and all are constant on basis relations. For an adjacent pair, a common ξ-edge is either the unique matching edge at an x-center or the closing matching edge at an y-center; simplicity prevents both alternatives from occurring at once. Hence WξW_ξ is 00-11. The WξW_ξ-subgraph indexed by a fixed ξ-edge zz¯z z has as its vertices the cross edges incident with z or z¯ z. Two are WξW_ξ-adjacent exactly when they share the same x-endpoint, or when they share a y-endpoint across the ξ-matching. Thus it consists of two κ-cliques, together with the possibly partial cross-matching zy↔z¯yzy zy. Two distinct vertices in one clique have exactly the other κ−2κ-2 clique vertices as common WξW_ξ-neighbors, whereas a cross-match pair has no common WξW_ξ-neighbor. Therefore (Wξ2)ef=κ−2,e≠f lie in the same clique,0,e,f form a cross-match pair.(W_ξ^2)_ef= casesκ-2,&e≠ f lie in the same clique,\\ 0,&e,f form a cross-match pair. cases The preceding construction makes the x-centered pair a same-clique pair and the y-centered pair a cross match. Here κ≥2κ≥ 2. If κ=2κ=2, every vertex of the resulting K4K_4 has no additional incident edge, so connectedness implies that the root is K4K_4. Edge transitivity of K4K_4 then puts all its edges in one diagonal line-algebra fiber, so every vertex has the same star profile and =x=y. Thus κ≥3κ≥ 3, and the values in (A.8) differ, contradicting constancy or transport of Wξ2W_ξ^2 on RγR_γ. This proves the central-profile assertion; it remains to compute the class sizes. On the G-side, for an incident fiber ℰαE_α, |CG|xα=|ℰα|,ℰα joins to a distinct profile,2|ℰα|,ℰα joins to itself.|C_x^G|x_α= cases|E_α|,&E_α joins x to a distinct profile,\\ 2|E_α|,&E_α joins x to itself. cases Every star-profile class has such a fiber with xα>0x_α>0, because the connected nontrivial roots under consideration have no isolated vertices. Since |ℰα|=tr(Dα)|E_α|=tr(D_α) is transported, these formulas recover and transport every profile-class size. ∎ Lemma 9 (Endpoint dart profiles). Every diagonal fiber of L(G)A_L(G) fixes its unordered pair of endpoint dart profiles, and every open adjacent relation RγR_γ fixes its source dart, namely (e∩f,e)=γ+hγdd(e∩ f,e)=e_γ+h^d_γ. These labels are transported by φ . Proof. For a source fiber ℰαE_α, every line neighbor of e=uve=uv shares exactly one endpoint with e, so the two wings split the out-valencies: (u,e)+(v,e)=(νρ)ρ(e=uv∈ℰα).d(u,e)+d(v,e)=( _ρ)_ρ (e=uv _α). For an open relation γ, the common line neighbors g of the wedge e=uv,f=uwe=uv,f=uw with (e,g)∈Rρ(e,g)∈ R_ρ are exactly the ρ-colored edges of the u-wing other than f, so the open-star listing gives (e∩f,e)=γ+hγd.d(e∩ f,e)=e_γ+h^d_γ. If an open relation leaves ℰαE_α, (A.10) fixes one endpoint dart, and (A.9) fixes the other. If no open relation leaves, the true-twin automorphism of Lemma 7 swaps the two wings and makes the profiles equal. This proves the diagonal assertion, and (A.10) is the open source-dart assertion. ∎ Lemma 10 (Source and target dart profiles). For a representative e=uv,f=uwe=uv,f=uw of an adjacent basis relation, the relation fixes the source dart (u,e)d(u,e) and the target dart (u,f)d(u,f), and these labels are transported by φ . Proof. Consider the source dart; the target statement follows by transpose. If the two endpoint star profiles of its source fiber differ, Lemmas 7 and 8 identify the central wing, and the fixed unordered dart pair, together with (A.1), identifies its dart profile: under (A.1), the two dart profiles recover the two distinct endpoint star profiles, so the fixed central star profile selects the correct dart. For equal endpoint star profiles, no adjacent relation can be centered at a degree-one endpoint. At degree two, each dart has one other incident edge, so relation γ fixes the unit dart profile γe_γ. An open relation at any degree is fixed by (A.10). Suppose that a closed relation γ, centered at a root vertex of degree d≥3d≥ 3, is mixed between source-dart profiles ≠x . Interchanging G,HG,H if necessary, take the x-centered representative in G; the y-centered representative may lie in G or in H. In the x-centered representative, let ρ be the relation of the first closing leg (e,g)(e,g), where g is the closing edge. Direct listing gives (u,e)=γ+hγd−ρ,d(u,e)=e_γ+h^d_γ-e_ρ, of the form required by the profile-difference observation, with the closing-leg relation as label. With σ the closing-leg relation of a y-centered representative, the principle gives −=ρ−σ,y-x=e_ρ-e_σ, and, since Lemma 9 fixes and transports the unordered dart pair of the source fiber, that pair equals ,\x,y\ and these are the only source-dart profiles on RγR_γ; in particular ρ≠σρ≠σ. Write (xρ,yρ)=(a,a+1),(xσ,yσ)=(b+1,b).(x_ρ,y_ρ)=(a,a+1), (x_σ,y_σ)=(b+1,b). We first prove a,b>0a,b>0. If a=0a=0, then (A.9) gives the out-valency νρ=xρ+yρ=1 _ρ=x_ρ+y_ρ=1. Thus RρR_ρ has exactly one target from every source edge. Write fρ(e)f_ρ(e) for this target and form ZρL(G)=((RρAL(G))∘AL(G))AL(G),ZρL(H)=φ(ZρL(G)).Z_ρ^L(G)=((R_ρA_L(G)) A_L(G))A_L(G), Z_ρ^L(H)= (Z_ρ^L(G)). Functionality also forces ρ≠γρ≠γ: in the x-centered closed realization, otherwise the other wedge leg and the closing edge would be two distinct RρR_ρ-targets of e. Hence in the y-centered realization the unique RρR_ρ-target is a third edge at the center. On either side K∈G,HK∈\G,H\, functionality makes (ZρL(K))ef(Z_ρ^L(K))_ef count line vertices adjacent simultaneously to e,f,fρ(e)e,f,f_ρ(e). It is zero when fρ(e)f_ρ(e) is the closing edge and d−3d-3 when fρ(e)f_ρ(e) is a third edge at the center. Indeed, functionality gives (RρL(K)AL(K))eg=AL(K)(fρ(e),g)(R_ρ^L(K)A_L(K))_eg=A_L(K)(f_ρ(e),g); the Hadamard product restricts g to a common neighbor of e and fρ(e)f_ρ(e), and the final multiplication by AL(K)A_L(K) additionally requires g∼fg f. For d≥4d≥ 4 this contradicts constancy or transport on RγR_γ. If d=3d=3, distinguish the two representatives as follows. In the star realization write e=uv,f=uw,fρ(e)=uze=uv,f=uw,f_ρ(e)=uz. Write the closing representative as e^=u^v^,f^=u^w e= u v, f= u w, with closing edge g^=v^w g= v w; this hatted realization is the x-centered one in G, while the star realization lies on the side containing the y-centered representative. Then (e^,g^)∈Rρ( e, g)∈ R_ρ; define RθR_θ by (g^,f^)∈Rθ( g, f)∈ R_θ. Functionality gives pρθγ=1p_ρθ^γ=1, and transport forces (uz,f)∈Rθ(uz,f)∈ R_θ in the star realization. Both pairs through the witness are closed in the closing realization. Wedge-type transport (Lemma 6) therefore makes the corresponding wedges in the star realization closed: they supply vz,wzvz,wz, while the original closed γ-wedge supplies vwvw. In the star realization, Rγ,Rρ,RθR_γ,R_ρ,R_θ are centered at the cubic vertex u. In the closing realization these three relations are centered at u^,v^,w u, v, w, respectively. Central-degree transport (Lemma 6) therefore makes all three vertices cubic. The target edge g g of RρR_ρ and the target edge f f of RθR_θ consequently have endpoint-degree pair 3,3\3,3\; transporting their diagonal-fiber labels back gives d(z)=d(w)=3d(z)=d(w)=3. Finally, the equal endpoint star profiles of the source fiber give d(v)=d(u)=3d(v)=d(u)=3, since degree is the sum of the star-profile coordinates. Hence the displayed K4K_4 is cubic and, by connectedness, is the whole root. Its darts are automorphic, contradicting ≠x . Therefore a>0a>0; the symmetric argument gives b>0b>0. Every mixed relation is closed by (A.10). By (A.9), the source fiber’s fixed dart pair ,\x,y\ has total valency vector +x+y. Thus the closing ρ-leg opposite an x-dart is centered at the y-dart, while xρ=a>0x_ρ=a>0 gives a ρ-relation centered at an x-dart; hence ρ is mixed, and symmetrically so is σ. For λ∈ρ,σλ∈\ρ,σ\, let r_x and r_y be its closing-leg labels in its x- and y-centered realizations. Applying the listing that produced (A.11) to RλR_λ gives −=r−r.y-x=e_r_x-e_r_y. Comparison with (A.11) forces r=ρr_x=ρ and r=σr_y=σ. Fix e=uve=uv, with dart profiles x at u and y at v. If a ρ- or σ-neighbor in the u-wing is f=uzf=uz, the closing rule supplies the edge vzvz, which is a ρ-neighbor in the v-wing. The two source sets are disjoint because Rρ≠RσR_ρ≠ R_σ, and simplicity makes the map uz↦vzuz vz injective. Therefore xρ+xσ≤yρ.x_ρ+x_σ≤ y_ρ. By (A.12), this is a+(b+1)≤a+1a+(b+1)≤ a+1, contradicting b>0b>0. ∎ A.3 The profile-oriented ordinary algebra Let ℭG C_G and ℭH C_H be the recovered star-profile classes of G and H, with the transport bijection written C↦CHC C^H. Let BG∈0,1V(G)×E(G)B_G∈\0,1\^V(G)× E(G) and BH∈0,1V(H)×E(H)B_H∈\0,1\^V(H)× E(H) be the unsigned incidence matrices, so BG(u,e)=[u∈e]B_G(u,e)=1[u∈ e], and similarly for H. For C∈ℭGC∈ C_G, define the diagonal 00-11 projectors (PCG)uu′=[u=u′∈C],(PCHH)u′v′=[u′=v′∈CH].(P_C^G)_u =1[u=u ∈ C], (P_C^H^H)_u v =1[u =v ∈ C^H]. For a diagonal edge fiber ℰαE_α, let α+,α−\d_α^+,d_α^-\ be its unordered endpoint dart-profile pair. If the two profiles differ, choose the same ordering of their transported profile labels on G and H, and orient every α-edge toward its ++-dart. Let B~G,α∈−1,0,1V(G)×E(G) B_G,α∈\-1,0,1\^V(G)× E(G) be the signed incidence matrix with entry +1+1 at the ++-dart endpoint, entry −1-1 at the other endpoint, and zero off that fiber; define B~H,α B_H,α analogously. This ordering serves only to synchronize the transported labels; equal-dart-profile fibers are not oriented. Put ℐG=BG∪B~G,α:α+≠α−,ℐH=BH∪B~H,α:α+≠α−.I_G=\B_G\∪\ B_G,α:d_α^+ _α^-\, _H=\B_H\∪\ B_H,α:d_α^+ _α^-\. For each SG∈ℐGS_G _G, write SH∈ℐHS_H _H for the incidence matrix with the same transported label. The next lemma relates the root profile projectors to the stable line algebra. Placing a profile-class projector between two incidence matrices produces an edge-indexed Gram matrix that belongs to the stable line algebra and is transported. Lemma 11 (Mixed Grams). For SG,TG∈ℐGS_G,T_G _G and C∈ℭGC∈ C_G, SG⊤PCGTG∈L(G),S_G P_C^GT_G _L(G), and φ(SG⊤PCGTG)=SH⊤PCHHTH. (S_G P_C^GT_G)=S_H P_C^H^HT_H. Proof. The (e,f)(e,f)-entry is ∑u∈e∩f∩CSG(u,e)TG(u,f). _u∈ e∩ f∩ CS_G(u,e)\,T_G(u,f). It is zero for disjoint edges; the source and target fibers also determine whether either signed incidence is zero. On an adjacent basis relation, Lemmas 8 and 10 fix the central star profile and, whenever a signed incidence occurs, its source or target sign. On a diagonal relation, the unordered endpoint dart profiles (Lemma 9) fix both star memberships through (A.1). A signed factor can then be nonzero only for the fiber containing e=fe=f. If both factors are unsigned or both are signed, (A.13) counts the endpoints in C. With exactly one signed factor it is the signed C-incidence; this is zero when both endpoints have the same star profile, and otherwise its sign is fixed by the synchronized +/−+/- dart labels. Thus (A.13) is constant on every basis relation of L(G)A_L(G) and depends only on transported labels. Consequently SG⊤PCGTG=∑τmτRτS_G P_C^GT_G= _τm_τR_τ with the same coefficients mτm_τ after transport to H, proving both claims. ∎ Define the root-side space G=span(PCG:C∈ℭG∪PCGSGMTG⊤PDG:C,D∈ℭG,SG,TG∈ℐG,M∈L(G)).W_G=span (\P_C^G:C∈ C_G\∪\P_C^GS_GMT_G P_D^G:C,D∈ C_G,\ S_G,T_G _G,\;M _L(G)\ ). Define HW_H by the same formula with the transported H-side objects. Here M is indexed by E(G)×E(G)E(G)× E(G), so each incidence sandwich is a V(G)×V(G)V(G)× V(G) root matrix. The next lemma makes GW_G an ordinary matrix algebra; Hadamard closure is proved only after its value cells are constructed. We call the matrices PCGP_C^G projector atoms and the displayed incidence sandwiches incidence atoms. Lemma 12 (Root-algebra transport and compression). The space GW_G is a unital real algebra—that is, it contains the identity matrix and is closed under real linear combinations and ordinary matrix multiplication—and is closed under transpose. The atomwise prescriptions PCG P_C^G ⟼PCHH, P_C^H^H, PCGSGMTG⊤PDG P_C^GS_GMT_G P_D^G ⟼PCHHSHφ(M)TH⊤PDHH P_C^H^HS_H (M)T_H P_D^H^H extend to a well-defined, unital, transpose- and trace-preserving algebra isomorphism Ω:G⟶H. :W_G _H. For every Z∈GZ _G and UG,VG∈ℐGU_G,V_G _G, UG⊤ZVG∈L(G)U_G ZV_G _L(G) compatibly with Ω,φ , . Moreover, IV(G),JV(G),AGI_V(G),J_V(G),A_G belong to GW_G and are transported to IV(H),JV(H),AHI_V(H),J_V(H),A_H. Proof. Algebra structure. The identity is ∑C∈ℭGPCG _C∈ C_GP_C^G, and transposing an atom exchanges its two outer profile blocks and incidence matrices and replaces M by M⊤M . Multiplication by a projector atom either annihilates a mismatched outer block or leaves the matching block unchanged, so only products of two incidence atoms require calculation. Products with unequal middle projectors vanish; the remaining products reduce as (PCGSGMTG⊤PDG)(PDGUGQVG⊤PFG)=PCGSG(M(TG⊤PDGUG)Q)VG⊤PFG.(P_C^GS_GMT_G P_D^G)(P_D^GU_GQV_G P_F^G)=P_C^GS_G (M(T_G P_D^GU_G)Q )V_G P_F^G. The middle factor belongs to L(G)A_L(G) by Lemma 11. Thus GW_G is a unital transpose-closed algebra, and (A.15) is formally multiplicative and transpose preserving. Well-definedness. To check independence of the chosen expression, first note that a product whose profile-block indices do not close has trace zero on both sides. For a cyclic product of incidence atoms, with Cr=C0C_r=C_0, cyclicity of trace gives the explicit contraction tr(∏i=1rPCi−1GSiMiTi⊤PCiG) \! ( _i=1^rP_C_i-1^GS_iM_iT_i P_C_i^G ) =tr(M1(T1⊤PC1GS2)M2⋯Mr(Tr⊤PC0GS1)), =tr\! (M_1(T_1 P_C_1^GS_2)M_2·s M_r(T_r P_C_0^GS_1) ), where indices are cyclic. Each parenthesized factor is a transported mixed Gram, so the right-hand side is a transported trace in L(G)A_L(G). Projector-only words have trace zero or a transported class size, and any other projector factors are absorbed into adjacent profile blocks. By linearity, all trace words in the spanning atoms are therefore preserved. If a formal linear combination Z represents zero and Z~ Z is its formal image under (A.15), then tr(Z~⊤Z~)=tr(Z⊤Z)=0.tr( Z Z)=tr(Z Z)=0. The left side is the squared real Frobenius norm of Z~ Z, so Z~=0 Z=0. The prescription is therefore independent of the chosen representation. The same construction with φ−1 ^-1 is inverse on every spanning atom, so Ω is bijective. Compression. Compressing an incidence atom gives UG⊤(PCGSGMTG⊤PDG)VG=(UG⊤PCGSG)M(TG⊤PDGVG)∈L(G),U_G (P_C^GS_GMT_G P_D^G)V_G=(U_G P_C^GS_G)M(T_G P_D^GV_G) _L(G), while for a projector atom this is the mixed-Gram lemma. This proves (A.16) and its transport compatibility. The matrices I, J, and A. Let DG=∑C∈ℭGd(C)PCGD_G= _C∈ C_Gd(C)P_C^G, where d(C)d(C) is the common root degree on profile class C, and define DHD_H analogously. Since d(C)=∑αsα(C)d(C)= _αs_α(C), star-profile transport gives Ω(DG)=DH (D_G)=D_H. The roots here are connected and have order at least three, so all degrees are positive; hence DG−1=∑Cd(C)−1PCGD_G^-1= _Cd(C)^-1P_C^G lies in GW_G and is transported to DH−1D_H^-1. The line-side all-ones matrix JE(G)J_E(G) belongs to L(G)A_L(G), and entry inspection gives BGBG⊤=DG+AG,BGJE(G)BG⊤=DGJV(G)DG.B_GB_G =D_G+A_G, B_GJ_E(G)B_G =D_GJ_V(G)D_G. For any M∈L(G)M _L(G), expanding the root identity on both sides shows BGMBG⊤=∑C,DPCGBGMBG⊤PDG,B_GMB_G = _C,DP_C^GB_GMB_G P_D^G, so (A.15) transports this unblocked sandwich to BHφ(M)BH⊤B_H (M)B_H . In particular, BGBG⊤=BGIE(G)BG⊤B_GB_G =B_GI_E(G)B_G , and both sandwiches in (A.17) are sums of the profile-blocked atoms in (A.14). Therefore the matrices IV(G)=∑CPCG,AG=BGBG⊤−DG,JV(G)=DG−1BGJE(G)BG⊤DG−1.I_V(G)= _CP_C^G, A_G=B_GB_G -D_G, J_V(G)=D_G^-1B_GJ_E(G)B_G D_G^-1. belong to GW_G and are transported. ∎ A.4 Diagonal and root-edge profile cells For any finite index set S and square matrix M indexed by S, write DiagS(M)=IS∘MDiag_S(M)=I_S M for coordinate-diagonal extraction. We use S=V(G),V(H)S=V(G),V(H) for root matrices and S=E(G),E(H)S=E(G),E(H) for line-indexed matrices. Call a diagonal edge fiber unequal or equal according as its two endpoint dart profiles differ or agree. For a fiber ℰαE_α, set Δα=∑C∈ℭGsα(C)PCG, _α= _C∈ C_Gs_α(C)P_C^G, where sα(C)s_α(C) is the common coordinate on C; this is the diagonal matrix with entry sα(u)s_α(u) at u. Thus Δα∈G _α _G directly, without using diagonal extraction. If the fiber is unequal, also set Σα=12(BGDαB~G,α⊤+B~G,αDαBG⊤). _α= 12 (B_GD_α B_G,α + B_G,αD_αB_G ). This incidence formula lies in GW_G. Edge by edge, its two rank-one terms cancel at the two off-diagonal endpoint positions and contribute +1+1 and −1-1 at the two diagonal positions. Thus its diagonal entry is the number of ++-darts minus the number of −--darts of that fiber. Both matrices are transported. Lemma 13 (Diagonal extraction). For every Z∈GZ _G, DiagV(G)(Z)∈G,Ω(DiagV(G)(Z))=DiagV(H)(ΩZ).Diag_V(G)(Z) _G, (Diag_V(G)(Z))=Diag_V(H)( Z). Proof. Projector atoms are already diagonal, so it suffices to treat an incidence atom F=PCGSGMTG⊤PCG.F=P_C^GS_GMT_G P_C^G. Terms with different outer projectors have zero diagonal. Explicitly, Fuu=[u∈C]∑e,f∋uSG(u,e)MefTG(u,f).F_u=1[u∈ C] _e,f uS_G(u,e)M_efT_G(u,f). For fixed (u,e)(u,e), separate f=ef=e and group the remaining f’s by adjacent basis relation RρR_ρ. The matrix M is constant on each RρR_ρ, the coordinate (u,e)ρd(u,e)_ρ gives its multiplicity, and the recovered target dart profile fixes the corresponding entry of TGT_G. Hence the inner sum depends only on the source fiber together with the dart profile and its SGS_G-entry. The separated f=ef=e contribution is likewise fixed by the source diagonal fiber and the two incidence labels. More explicitly, for an incident dart (u,e)(u,e) whose edge lies in ℰαE_α and whose dart profile is δ, set κα,δS,T,M:=SG(u,e)∑fMefTG(u,f). _α,δ^S,T,M:=S_G(u,e) _fM_efT_G(u,f). The preceding grouping proves that this number is independent of the chosen incident dart with fiber α and profile δ. Thus the full diagonal sum groups by dart type with a concrete, well-defined coefficient. Write δα _α for the common endpoint dart profile of an equal fiber and δα+,δα− _α^+, _α^- for the ordered profiles of an unequal fiber. An equal fiber contributes κα,δαS,T,M(Δα)uu _α, _α^S,T,M( _α)_u. For an unequal fiber, the two dart counts satisfy n±(u)=(Δα)uu±(Σα)uu2.n_±(u)= ( _α)_u±( _α)_u2. Consequently the exact matrix identity is DiagV(G)(F)=∑αPCGκα,δαS,T,MΔα,ℰα equal,κα,δα+S,T,M+κα,δα−S,T,M2Δα+κα,δα+S,T,M−κα,δα−S,T,M2Σα,ℰα unequal.Diag_V(G)(F)= _αP_C^G cases _α, _α^S,T,M _α,&E_α equal,\\[5.69054pt] _α, _α^+^S,T,M+ _α, _α^-^S,T,M2\, _α+ _α, _α^+^S,T,M- _α, _α^-^S,T,M2\, _α,&E_α unequal. cases Every summand lies in GW_G. The same coefficients occur on H, while PCG,Δα,ΣαP_C^G, _α, _α are carried to their corresponding H-matrices. This proves both assertions in (A.18). ∎ Equal-dart-profile fibers require no canonical orientation. Fix one such fiber ℰαE_α, choose an arbitrary orientation only for the following proof, and let B^α B_α have entry +1+1 at the chosen positive endpoint, −1-1 at the other endpoint, and zero elsewhere, including on columns outside ℰαE_α. Put Kα=B^α⊤BGK_α= B_α B_G. For an adjacent f, the value Kα(e,f)K_α(e,f) is +1+1 or −1-1 according to which oriented endpoint of e is shared. Equality of the two endpoint dart profiles therefore says, for every adjacent basis relation RρR_ρ and every e∈ℰαe _α, ∑f:(e,f)∈RρKα(e,f)=0. _f:(e,f)∈ R_ρK_α(e,f)=0. Indeed, the summands are +1+1 for the RρR_ρ-neighbors in the positive wing of e and −1-1 for those in the negative wing, and equality of the two endpoint dart profiles equates the two counts. Lemma 14 (Equal-fiber cancellation). For every Z∈GZ _G, DiagE(G)(B^α⊤ZBG)=0,DiagE(G)(BG⊤ZB^α)=0.Diag_E(G)( B_α ZB_G)=0, _E(G)(B_G Z B_α)=0. Consequently, for every edge e=uv∈ℰαe=uv _α, Zuu=Zvv,Zuv=Zvu.Z_u=Z_v, Z_uv=Z_vu. Proof. For SG∈ℐGS_G _G and a profile class C, B^α⊤PCGSG=Kα∘(BG⊤PCGSG). B_α P_C^GS_G=K_α (B_G P_C^GS_G). For disjoint edge pairs both sides vanish. For an adjacent off-diagonal pair this is the unique shared-endpoint contribution; on the diagonal both sides vanish because the two endpoints have the same star profile and no B~G,β∈ℐG B_G,β _G is supported on this equal fiber. For an incidence atom, put Q=BG⊤PCGSG∈L(G)Q=B_G P_C^GS_G _L(G) and Q′=MTG⊤PDGBG∈L(G)Q =MT_G P_D^GB_G _L(G). The e-diagonal entry of B^α⊤(PCGSGMTG⊤PDG)BG B_α (P_C^GS_GMT_G P_D^G)B_G is ∑fKα(e,f)Q(e,f)Q′(f,e). _fK_α(e,f)Q(e,f)Q (f,e). For fixed e, Q(e,f)Q(e,f) is constant on RρR_ρ, while Q′(f,e)Q (f,e) is constant on Rρ⊤R_ρ . Diagonal and disjoint relations contribute zero, and (A.19) annihilates each adjacent relation. Projector atoms vanish similarly. This proves the first identity in (A.20). Apply it to Z⊤∈GZ _G and transpose the resulting diagonal to obtain the second. Orient e=uve=uv positively at u. The two equations at e are Zuu+Zuv−Zvu−Zvv=0,Zuu+Zvu−Zuv−Zvv=0.Z_u+Z_uv-Z_vu-Z_v=0, Z_u+Z_vu-Z_uv-Z_v=0. Their sum and difference give (A.21). The conclusion no longer contains B^α B_α, so it is independent of the arbitrary orientation used in the proof. ∎ Fix a basis Z1,…,ZtZ_1,…,Z_t of GW_G and the transported basis ΩZ1,…,ΩZt Z_1,…, Z_t of HW_H. For an ordered root pair on each side define its complete W-profile ζG(u,v) _G(u,v) =((Z1)uv,…,(Zt)uv), =((Z_1)_uv,…,(Z_t)_uv), ζH(u′,v′) _H(u ,v ) =((ΩZ1)u′v′,…,(ΩZt)u′v′). =(( Z_1)_u v ,…,( Z_t)_u v ). Replacing the chosen basis applies an invertible linear transformation to every profile vector and therefore leaves its joint level sets unchanged. Thus the profile cells defined below are basis independent. Use the finite common index set Λ=ζG(u,v):u,v∈V(G)∪ζH(u′,v′):u′,v′∈V(H). =\ _G(u,v):u,v∈ V(G)\∪\ _H(u ,v ):u ,v ∈ V(H)\. Thus Λ includes values attained on only one root; the induction will show that no such one-sided nonempty cell remains at a fixed distance. For every nonnegative integer d and every λ∈Λλ∈ , define Pd,λG(u,v)=[distG(u,v)=d,ζG(u,v)=λ].P^G_d,λ(u,v)=1[dist_G(u,v)=d,\ _G(u,v)=λ]. Define Pd,λHP^H_d,λ by the same formula using ζH _H and distHdist_H. These matrices are defined even when their support is empty; we call a nonzero one a profile cell. We suppress a superscript only in a one-root calculation. Every matrix in GW_G is constant on each G-profile cell by definition. Lemma 15 (Distance-zero and distance-one cells). For every λ∈Λλ∈ and d∈0,1d∈\0,1\, the matrix Pd,λGP^G_d,λ lies in GW_G, and Ω(Pd,λG)=Pd,λH (P^G_d,λ)=P^H_d,λ, including when either displayed matrix is zero. Proof. Diagonal cells. Diagonal extraction and polynomial interpolation of commuting diagonal matrices construct every profile cell on IV(G)I_V(G). Namely, apply finite ordinary polynomial interpolation jointly to DiagV(G)(Z1),…,DiagV(G)(Zt).Diag_V(G)(Z_1),…,Diag_V(G)(Z_t). Their ordinary products evaluate coordinatewise because the matrices are diagonal, so this step does not assume Hadamard closure of GW_G. For each coordinate use the union of the values attained by the corresponding diagonal matrices on G and H, as in the interpolation convention above. Equation (A.18) therefore transports the resulting diagonal selector, including a zero selector for a requested value unattained on one side. Unequal fibers. Let ℰαE_α be unequal and define its endpoint-selector incidences BG,α±=12(BGDα±B~G,α).B_G,α^±= 12(B_GD_α± B_G,α). Each α-column selects its ±-endpoint. Since BG,α±B_G,α^± is a linear combination of BGDα,B~G,αB_GD_α, B_G,α, multiplying DαD_α onto (A.16) shows that (BG,αs)⊤ZBG,αt∈L(G)(B_G,α^s) ZB_G,α^t _L(G) for s,t∈+,−s,t∈\+,-\. Its e-diagonal entry is ZusutZ_u_su_t for e=u+u−e=u_+u_-. Joint level sets over the basis ZiZ_i, intersected with the diagonal projector DαD_α, therefore give transported diagonal projectors Πα,λ+− _α,λ^+- and Πα,λ−+ _α,λ^-+. Explicitly, Πα,λ+− _α,λ^+- selects the edge e=u+u−e=u_+u_- when ζG(u+,u−)=λ _G(u_+,u_-)=λ, while Πα,λ−+ _α,λ^-+ selects it when ζG(u−,u+)=λ _G(u_-,u_+)=λ. They are transported because all the compressed basis matrices used in their joint level sets are transported. The ordered root-edge cell on this fiber is BG,α+Πα,λ+−(BG,α−)⊤+BG,α−Πα,λ−+(BG,α+)⊤.B_G,α^+ _α,λ^+-(B_G,α^-) +B_G,α^- _α,λ^-+(B_G,α^+) . After expanding BG,α±B_G,α^±, absorb every DαD_α and Π -factor into the line-algebra middle matrix. Inserting IV(G)=∑CPCGI_V(G)= _CP_C^G on both root sides then expresses every resulting term as an incidence atom in (A.14). Thus (A.22) lies in GW_G and is transported. Equal fibers. If ℰαE_α is equal, Lemmas 13 and 14 apply as follows. Equation (A.16) places both compressed terms below in L(G)A_L(G); (A.18) transports the extracted root diagonal, and Hadamard multiplication by the transported DαD_α preserves the line algebra. Hence the diagonal line matrix bZα=12Dα∘(BG⊤ZBG−BG⊤DiagV(G)(Z)BG)b_Z^α= 12D_α (B_G ZB_G-B_G Diag_V(G)(Z)B_G ) has value Zuv=ZvuZ_uv=Z_vu at e=uve=uv. Indeed, (BG⊤ZBG)ee−(BG⊤DiagV(G)(Z)BG)ee=Zuv+Zvu=2Zuv,(B_G ZB_G)_e-(B_G Diag_V(G)(Z)B_G)_e=Z_uv+Z_vu=2Z_uv, where the last equality is (A.21). Interpolate the joint values of the bZiαb_Z_i^α to obtain a diagonal line projector Πα,λ _α,λ, per the interpolation convention; then BGΠα,λBG⊤−DiagV(G)(BGΠα,λBG⊤)B_G _α,λB_G -Diag_V(G)(B_G _α,λB_G ) is the corresponding symmetric ordered root-edge cell. Because the root is simple, its off-diagonal support consists exactly of the two orientations of the selected root edges; diagonal extraction removes only the endpoint counts. Summing the fiberwise selectors with the same λ proves the lemma. The fiberwise selectors use the same common value index Λ , so an unattained requested value contributes the zero projector. Applying the same construction to Ω−1 ^-1 shows that nonzero distance-zero and distance-one cells correspond bijectively and, more strongly, establishes the displayed equality for every λ∈Λλ∈ . ∎ A.5 Induction on root distance We extend Lemma 15 by strong induction on root distance. The induction uses ordered edge pairs whose four endpoint distances identify a unique endpoint pair at the current distance. Lemma 16 (Profile cells at all root distances). For every nonnegative integer d and every λ∈Λλ∈ , Pd,λGP^G_d,λ belongs to GW_G and Ω(Pd,λG)=Pd,λH (P^G_d,λ)=P^H_d,λ, including zero cells. Proof. Let (ΓsG)uv=[distG(u,v)=s],(ΓsH)u′v′=[distH(u′,v′)=s]( _s^G)_uv=1[dist_G(u,v)=s], ( _s^H)_u v =1[dist_H(u ,v )=s] be the 00-11 distance matrices. The assertion holds for s=0,1s=0,1 by Lemma 15. Suppose all profile cells at distances below d≥2d≥ 2 have been constructed and transported. Then ΓsG=∑μ∈ΛPs,μG _s^G= _μ∈ P^G_s,μ and ΓsH=∑μ∈ΛPs,μH=Ω(ΓsG) _s^H= _μ∈ P^H_s,μ= ( _s^G) for s<ds<d. Hence Γ≥dG=JV(G)−∑s<dΓsG∈G,Γd−2G∈G. _≥ d^G=J_V(G)- _s<d _s^G _G, _d-2^G _G. Define the two transported line-algebra matrices NdL(G)=BG⊤Γd−2GBG,TdL(G)=BG⊤Γ≥dGBG.N_d^L(G)=B_G _d-2^GB_G, T_d^L(G)=B_G _≥ d^GB_G. Their (e,f)(e,f)-entries count, respectively, the ordered endpoint pairs (x,y)∈e×f(x,y)∈ e× f at distance exactly d−2d-2 and at distance at least d. Define the corresponding matrices for H. Equation (A.16) gives φ(NdL(G))=NdL(H) (N_d^L(G))=N_d^L(H) and φ(TdL(G))=TdL(H) (T_d^L(G))=T_d^L(H). Witness edge-pair identification. Finite level-set interpolation in the stable line algebra gives the transported 00-11 matrix QdL(G)=[NdL(G)>0]∘[TdL(G)=1]∈L(G),QdL(H)=φ(QdL(G)).Q_d^L(G)=1[N_d^L(G)>0] 1[T_d^L(G)=1] _L(G), Q_d^L(H)= (Q_d^L(G)). Thus QdL(G)Q_d^L(G) is a union of stable line-graph basis relations, rather than necessarily a single basis relation. If (QdL(G))ef=1(Q_d^L(G))_ef=1, choose x∈e,y∈fx∈ e,y∈ f with distG(x,y)=d−2dist_G(x,y)=d-2, which is possible because (NdL(G))ef≠0(N_d^L(G))_ef≠ 0. Moving across either root edge changes distance by at most one, so every pair in e×fe× f has distance at most d. The equality (TdL(G))ef=1(T_d^L(G))_ef=1 now says that exactly one ordered endpoint pair has distance d. We call (e,f)(e,f) a witness edge pair for this unique distance-d endpoint pair. The same argument applies on H. Conversely, every ordered pair (u,v)(u,v) at distance d has a witness edge pair. Take a geodesic u=x0,x1,…,xd=vu=x_0,x_1,…,x_d=v and put e=x0x1e=x_0x_1, f=xd−1xdf=x_d-1x_d. The four endpoint distances are d,d−1,d−1,d−2d,d-1,d-1,d-2: the displayed geodesic gives the upper bounds, and the triangle inequality with distG(u,v)=ddist_G(u,v)=d gives the matching lower bounds. Hence (NdL(G))ef≠0(N_d^L(G))_ef≠ 0 and (TdL(G))ef=1(T_d^L(G))_ef=1. This also covers d=2d=2, where x1=xd−1x_1=x_d-1. Profile readout. For Z=∑iaiZi∈GZ= _ia_iZ_i _G, put zμ=∑iaiμiz_μ= _ia_i _i for μ∈Λμ∈ . For every s<ds<d, the already constructed and transported matrix Ls,ZG=∑μ∈ΛzμPs,μGL_s,Z^G= _μ∈ z_μP^G_s,μ is entrywise equal to Z∘ΓsGZ _s^G, but its membership in GW_G follows directly from the induction hypothesis, without assuming Hadamard closure. Define Ls,ΩZHL_s, Z^H by the same coefficient formula; then Ls,ΩZH=Ω(Ls,ZG)L_s, Z^H= (L_s,Z^G). Now form Md,ZL(G)=BG⊤ZBG−∑s<dBG⊤Ls,ZGBG.M_d,Z^L(G)=B_G ZB_G- _s<dB_G L_s,Z^GB_G. Hence (Md,ZL(G))ef=Zuv(M_d,Z^L(G))_ef=Z_uv when (u,v)(u,v) is the unique distance-d endpoint pair associated with (e,f)(e,f). Compression compatibility shows that the analogous matrix on H is Md,ΩZL(H)=φ(Md,ZL(G))M_d, Z^L(H)= (M_d,Z^L(G)). Each term of (A.23) belongs to L(G)A_L(G) by (A.16), so Md,ZL(G)M_d,Z^L(G) is a transported line-algebra matrix. Fix a profile value λ=(λ1,…,λt)λ=( _1,…, _t), and let (Kd,λL(G))ef=(QdL(G))ef∏i=1t[(Md,ZiL(G))ef=λi].(K_d,λ^L(G))_ef=(Q_d^L(G))_ef _i=1^t1[(M_d,Z_i^L(G))_ef= _i]. This is again a union of stable basis relations. Its transported mate Kd,λL(H)=φ(Kd,λL(G))K_d,λ^L(H)= (K_d,λ^L(G)) selects exactly the witness edge pairs whose unique distance-d endpoint pair has complete profile λ. By the interpolation convention, an unattained requested coordinate gives the zero selector on that side. Multiplicity correction. Put Fd,λG=BGKd,λL(G)BG⊤.F_d,λ^G=B_GK_d,λ^L(G)B_G . This matrix belongs to GW_G, and its H-side counterpart is its image under Ω . The matrix Fd,λGF_d,λ^G is supported on root distances at most d, because every endpoint pair of a selected witness edge pair has distance at most d. If Fd,λG=∑iaiZiF_d,λ^G= _ia_iZ_i, put fμ=∑iaiμif_μ= _ia_i _i for μ∈Λμ∈ . The induction hypothesis constructs and transports the lower-layer matrix L<d,λG=∑s<d∑μ∈ΛfμPs,μG.L_<d,λ^G= _s<d _μ∈ f_μP^G_s,μ. Entrywise this matrix equals ∑s<d(Fd,λG∘ΓsG) _s<d(F_d,λ^G _s^G); this equality is an observation about entries, not an appeal to Hadamard closure. For a root pair at distance below d, the lower-distance sum removes the corresponding entry of Fd,λGF_d,λ^G; above distance d, that entry is zero by the support observation. At distance d, every selected witness edge pair contributing to the (u,v)(u,v)-entry has (u,v)(u,v) as its unique distance-d endpoint pair. The entry is then zero unless its profile is λ, and otherwise counts those witness edge pairs. Since Fd,λG∈GF_d,λ^G _G, its value on the complete profile λ=(λ1,…,λt)λ=( _1,…, _t) is the explicit scalar wd,λ:=∑iaiλi.w_d,λ:= _ia_i _i. The transported matrix is ∑iaiΩZi _ia_i Z_i, so it has the same scalar on the transported H-profile. We therefore have the entrywise identities F^d,λG:=Fd,λG−L<d,λG=wd,λPd,λG,Ω(F^d,λG)=wd,λPd,λH. F_d,λ^G:=F_d,λ^G-L_<d,λ^G=w_d,λP^G_d,λ, ( F_d,λ^G)=w_d,λP^H_d,λ. This argument does not use Hadamard closure of GW_G: each lower-distance restriction in the definition of F F was defined first as the already constructed profile-cell sum displayed above. If Pd,λG≠0P^G_d,λ≠ 0, the geodesic construction above gives a selected witness edge pair, so wd,λ>0w_d,λ>0. If instead Pd,λH≠0P^H_d,λ≠ 0, the identical argument on H gives the same conclusion for the common scalar. Dividing (A.24) then constructs both cells at once: Pd,λG=1wd,λF^d,λG,Pd,λH=1wd,λΩ(F^d,λG).P^G_d,λ= 1w_d,λ F_d,λ^G, P^H_d,λ= 1w_d,λ ( F_d,λ^G). If the cell occurs on neither root, both cell matrices are zero. This proves the induction step for every λ∈Λλ∈ , including empty cells, and strong induction establishes the lemma for all root distances. ∎ A.6 Completion of the proof Proof of Theorem 1. If either root is K1,K2K_1,K_2, the paw, or the diamond, Lemma 3 proves the result. We may therefore use the standing hypotheses of the general construction above. The nonempty profile cells from Lemma 16 are pairwise disjoint 00-11 matrices and sum to JV(G)J_V(G). Every matrix in GW_G is its profile-value-weighted sum of these cells, while every cell belongs to GW_G. Disjoint nonzero 00-11 cells are linearly independent, so these two containments show that they form a basis of GW_G, and Pd,λG∘Pd′,μG=[(d,λ)=(d′,μ)]Pd,λG.P^G_d,λ P^G_d ,μ=1[(d,λ)=(d ,μ)]P^G_d,λ. Thus GW_G is Hadamard closed, and the same holds for HW_H. Since Ω maps the profile cells and maps IV(G),JV(G),AGI_V(G),J_V(G),A_G to IV(H),JV(H),AHI_V(H),J_V(H),A_H, it preserves Hadamard products as well as the operations in Lemma 12. We now restrict Ω to the stable root algebras by proving the two required inclusions separately. Let GA_G and HA_H denote the stable root pair algebras from the first subsection. Since GW_G is now a coherent matrix algebra containing IV(G),JV(G),AGI_V(G),J_V(G),A_G, minimality gives G⊆GA_G _G; similarly H⊆HA_H _H. Consider the preimage ℬG=Z∈G:Ω(Z)∈H.B_G=\Z _G: (Z) _H\. Preservation of ordinary and Hadamard multiplication, transpose, and I,J,AI,J,A makes ℬGB_G a coherent matrix algebra containing IV(G),JV(G),AGI_V(G),J_V(G),A_G. Minimality therefore gives G⊆ℬGA_G _G, or Ω(G)⊆H (A_G) _H. Applying the same argument to ℬH=Y∈H:Ω−1(Y)∈GB_H=\Y _H: ^-1(Y) _G\ gives Ω−1(H)⊆G ^-1(A_H) _G, equivalently H⊆Ω(G)A_H (A_G). Hence Ω restricts to an isomorphism Ψ:G⟶H :A_G _H preserving ordinary and Hadamard multiplication, transpose, trace, and I,J,AI,J,A. It remains to verify the basis-bijection hypothesis of Lemma 2. Let Gst,HstC_G st,C_H st be the stable root-color sets and expand Ψ(RρG)=∑σ∈HstaρσRσH. (R_ρ^G)= _σ _H sta_ρσR_σ^H. Because RρG∘RρG=RρGR_ρ^G R_ρ^G=R_ρ^G, Hadamard preservation gives aρσ2=aρσa_ρσ^2=a_ρσ, so every coefficient is 00 or 11. Images of distinct source relations are Hadamard-orthogonal, and ∑ρ∈GstΨ(RρG)=Ψ(JV(G))=JV(H). _ρ _G st (R_ρ^G)= (J_V(G))=J_V(H). Consequently each target relation RσHR_σ^H occurs in exactly one of the displayed images. Injectivity of Ψ makes every source image nonzero. Finally, the relation matrices are bases and Ψ is a linear isomorphism, so |Gst|=dimG=dimH=|Hst|.|C_G st|= _G= _H=|C_H st|. Thus the partition of HstC_H st into the nonempty supports of the source images has singleton parts. There is a bijection π:Gst→Hstπ:C_G st _H st with Ψ(RρG)=Rπ(ρ)H (R_ρ^G)=R_π(ρ)^H. All the remaining hypotheses of Lemma 2 are inherited from Ψ ; in particular relation sizes agree because |RρG|=tr(RρG(RρG)⊤)|R_ρ^G|=tr(R_ρ^G(R_ρ^G) ). The lemma now gives G≡3-WLHG _3-WLH. ∎ A.7 Componentwise extension to disconnected roots We now remove connectedness without changing the connected reconstruction above. For a graph X, let Comp(X)Comp(X) denote its set of connected components, including isolated vertices. Lemma 17 (Component matching for stable pair refinement). If finite graphs X,YX,Y satisfy X≡3-WLYX _3-WLY, then their components admit a bijection β:Comp(X)→Comp(Y)β:Comp(X) (Y) such that X[C]≡3-WLY[β(C)](C∈Comp(X)).X[C] _3-WLY[β(C)] (C (X)). Conversely, any such componentwise bijection implies X≡3-WLYX _3-WLY. Proof. Assume first that the graphs are nonempty. Let , X, Y be their stable-pair coherent configurations and let φ:→ : X→ Y be the trace-preserving algebraic isomorphism induced by joint refinement, with φ(AX)=AY (A_X)=A_Y. The least equivalence relation eX=⟨IX∪AX⟩e_X= I_X∪ A_X has exactly the connected components of X as its classes. It is a parabolic of X, and algebraic isomorphisms transport this equivalence closure, so φ(eX)=eY (e_X)=e_Y [23, Section 2.7, equation (5)]. Use the unique decomposition of a partial parabolic into indecomposable partial parabolics. The isomorphism φ bijects these summands and preserves their numbers of classes; after pairing their classes, it restricts on any paired classes C,DC,D to an algebraic isomorphism of the corresponding restricted coherent configurations [8, Definition 2.1.20, Lemma 2.1.21, Proposition 2.3.25, and Exercise 2.7.31]. This restriction maps AX|C×CA_X|_C× C to AY|D×DA_Y|_D× D. It therefore maps the smallest coherent algebra generated by identity, all-ones, and adjacency on X[C]X[C] into the corresponding stable pair algebra on Y[D]Y[D]; applying the inverse restriction gives the reverse inclusion, hence equality. The restricted isomorphism also preserves relation multiplicities. The coherent-algebra characterization from Lemma 2 gives X[C]≡3-WLY[D]X[C] _3-WLY[D]. Repeating this for every class yields β. For the converse, use the bijective-pebble characterization of counting logic. In each round, take the disjoint union of Duplicator’s bijections for the matched component games. Pebbled vertices in different components stay in different matched components, so equality and adjacency are preserved. The empty-graph case is immediate. ∎ Proof of Theorem 2. Apply Lemma 17 to the assumed equivalence of L(G)L(G) and L(H)L(H). The line graph of a connected component containing an edge is connected, and each connected line-graph component arises this way. Because G and H have no isolated vertices, this gives a bijection between their root components. For each matched pair C,DC,D, L(C)≡3-WLL(D).L(C) _3-WLL(D). Both C and D are Whitney-general, so Theorem 1 gives C≡3-WLDC _3-WLD. The converse direction of Lemma 17 now yields G≡3-WLHG _3-WLH. ∎ Appendix B Four-Clique Counting and Incomparability Witnesses B.1 Universal four-clique count The initial pair color distinguishes nonadjacent line vertices, which for a simple root are distinct disjoint edges. In the first global update of an ordered pair (e,f)(e,f), the multiplicity of the replacement entry (adj,adj)(adj,adj) is exactly |NL(G)(e)∩NL(G)(f)| N_L(G)(e)∩ N_L(G)(f) ; hence the graph-level histogram determines the set in Corollary 3. Write e=abe=ab and f=cdf=cd. Their common line neighbors are precisely the present edges among ac,ad,bc,bdac,ad,bc,bd, so the count is four exactly when the four endpoints induce a K4K_4. Conversely, every K4K_4 has three unordered pairs of opposite edges, hence six ordered pairs, and the endpoint union identifies the clique uniquely. This proves the formula. The Lean development separately checks the local equivalence, the six-to-one fiber count, the first-round histogram implication, and the global-edge ILG-33 corollary. B.2 Exact witnesses for comparison with root 44-WL We verify the two directions in Remark 2 using exact joint 33-FWL on the roots and exact joint 22-FWL on their line graphs. Refinement is collision-safe, uses one shared color namespace for each compared pair, and runs until separation or stability. The color traces, including the atomic round, are witness rootsroot 4-WLILG-3-WLSTS(13) incidence pair14→67→101(separates)3→5→7→7(stable equal)K5 compressed parity pair15→43→43(stable equal)3→8→46(separates) array[]@lcc@ roots&root 4-WL&ILG-3-WL\\ (13) incidence pair&14→ 67→ 101\;(separates)&3→ 5→ 7→ 7\;(stable equal)\\ K_5 compressed parity pair&15→ 43→ 43\;(stable equal)&3→ 8→ 46\;(separates)\\ array For the first pair, translate the base blocks 0,1,4\0,1,4\ and 0,2,7\0,2,7\ modulo 1313, then apply the Pasch trade 014,027,179,249⟷ 017,024,149,279.014,027,179,249\ \ 017,024,149,279. The two systems have respectively 1313 and 88 Pasch configurations, so their connected incidence roots, each with (n,m)=(39,78)(n,m)=(39,78), are nonisomorphic. Figure 3 shows the two roots under a shared cyclic layout. Figure 3: The STS(13)STS(13) incidence witness. Each panel is a root graph: hollow circles are points, squares are blocks, and an edge means that the point belongs to the block. Under the displayed alignment, 7474 light-gray edges are shared; the Pasch trade removes the four orange edges and adds the four blue edges. Root 44-WL separates the pair, whereas ILG-33-WL does not. For the reverse pair, replace every vertex of K5K_5 by the eight parity-constrained bitstrings on its four incident base edges, joining states in adjacent gadgets when their shared-edge bits agree. One root uses even parity in every gadget; the other uses odd parity at one base vertex. Both are connected 1616-regular graphs with (n,m)=(40,320)(n,m)=(40,320); the first contains 6464 copies of K5K_5 and the second contains none. Figure 4 shows these roots under a shared five-gadget layout. Figure 4: The compressed parity witness over K5K_5. Each ViV_i contains eight bitstring states, shown as graph vertices; states in two gadgets are adjacent when their bits for the corresponding base edge agree. The left root uses even parity in every gadget, while the right root uses odd parity in V0V_0. Under the displayed alignment, 288288 gray edges are shared; the 3232 orange edges are removed and the 3232 blue edges are added. Each main panel shows all 4040 vertices and 320320 edges, and the inset enlarges the changed V0V_0–V1V_1 bundle. ILG-33-WL separates the pair, whereas root 44-WL does not. All four roots are therefore nonisomorphic, connected, simple, and Whitney-general. The reproduction script experiments/deterministic/run_incomparability_certificate.py reconstructs both witness pairs and reproduces these refinement traces. Appendix C Machine Verification The accompanying Lean 4 development formalizes finite simple undirected graphs, line graphs, collision-free WL and folklore-WL refinements, the direct and global-edge ILG definitions, and the message-passing model used in the neural expressivity theorem. Top-level import files organize the formalization into line-graph correspondences, first-order results, third-order results, and neural expressivity. The formalized results include the ILG/line-graph refinement and GNN correspondences, forward transfer, the equal-order first-order counterexample, the universal factor-six four-clique identity and its global-edge ILG-33 consequence, the Shrikhande–rook separation, the connected completion with the Whitney exception, and the connected and componentwise backward-transfer theorems. The formalization of backward transfer follows the reconstruction argument in Appendix A and proves the relation between pair refinement and the separate-coordinate 33-WL formulation used in the paper. It also formalizes the lower- and upper-bound directions for global-edge ILG-GNN expressivity. Theorem 1 is stated in the stable-signature form used in the paper and proved equivalent to the all-round collision-free formulation used internally. The Lean development covers the k=3k=3 arity-shift instance used by the backward theorems; the general arity shift and the cited k=2k=2 consequence are taken from the literature. Lean checks all modules containing the stated theorems. The development contains no sorry, admit, or custom axiom declarations. A separate Lean file records the axioms used by the main results. The top-level imports, build instructions, and theorem index mapping each numbered paper result and Appendix A lemma to its Lean declaration are available in the accompanying repository: https://github.com/lukeyf/ilg-wl. Appendix D Proofs of ILG Equivalence and Expressivity Results D.1 ILG-11-GNN Equals MPNN on L(G)L(G) We give the detailed proof of Lemma 1. Let G be a finite simple undirected graph. Under the canonical identification E(G)=V(L(G))E(G)=V(L(G)), define the ILG neighborhood of e∈E(G)e∈ E(G) by NILG(e)=f∈E(G):f≠e,e∩f≠∅.N_ILG(e)=\f∈ E(G):f≠ e,\ e∩ f≠ \. By the definition of the line graph, NILG(e)=NL(G)(e).N_ILG(e)=N_L(G)(e). Consider a TnetT_net-layer MPNN on L(G)L(G) of the form he(ℓ+1)=Uℓ(he(ℓ),AGGℓMℓ(he(ℓ),hf(ℓ),ωefL(G)):f∈NL(G)(e)),h_e^( +1)=U_ (h_e^( ),AGG_ \M_ (h_e^( ),h_f^( ),ω^L(G)_ef ):f∈ N_L(G)(e) \ ), where MℓM_ is the message map, UℓU_ is the update map, AGGℓAGG_ is permutation invariant, and ωefL(G)ω^L(G)_ef is an optional edge feature on the line graph. In the untyped case it is constant. If typed line-graph adjacencies are used, assume the ILG layer uses the corresponding feature ωefILG=ωefL(G)for all f∈NILG(e).ω^ILG_ef=ω^L(G)_ef all f∈ N_ILG(e). The matching ILG-11-GNN on G is h~e(ℓ+1)=Uℓ(h~e(ℓ),AGGℓMℓ(h~e(ℓ),h~f(ℓ),ωefILG):f∈NILG(e)). h_e^( +1)=U_ ( h_e^( ),AGG_ \M_ ( h_e^( ), h_f^( ),ω^ILG_ef ):f∈ N_ILG(e) \ ). Both models are initialized by the same edge features: he(0)=h~e(0)=ϕ0(qe)for all e∈E(G).h_e^(0)= h_e^(0)= _0(q_e) all e∈ E(G). We prove by induction that he(ℓ)=h~e(ℓ)for all e∈E(G)h_e^( )= h_e^( ) all e∈ E(G) at every layer ℓ . The base case ℓ=0 =0 is the shared initialization above. Suppose (D.3) holds at layer ℓ . For a fixed edge e, the MPNN message multiset at the line-graph vertex e is ℳeL(G)=Mℓ(he(ℓ),hf(ℓ),ωefL(G)):f∈NL(G)(e).M^L(G)_e= \\! \M_ (h_e^( ),h_f^( ),ω^L(G)_ef ):f∈ N_L(G)(e) \\! \. Using the neighborhood identity (D.1), the feature identity (D.2), and the induction hypothesis, this multiset is equal to ℳeILG=Mℓ(h~e(ℓ),h~f(ℓ),ωefILG):f∈NILG(e).M^ILG_e= \\! \M_ ( h_e^( ), h_f^( ),ω^ILG_ef ):f∈ N_ILG(e) \\! \. Because AGGℓAGG_ is a function of the multiset rather than the ordering of its elements, AGGℓ(ℳeL(G))=AGGℓ(ℳeILG).AGG_ (M^L(G)_e)=AGG_ (M^ILG_e). Applying the same update map UℓU_ gives he(ℓ+1)=h~e(ℓ+1).h_e^( +1)= h_e^( +1). Thus (D.3) holds at layer ℓ+1 +1, and induction proves the layerwise equivalence. If the implementation stores line-graph vertices in an ordering different from the edge ordering used by the ILG layer, let E P_E be the corresponding permutation matrix. The same argument gives L(G)(ℓ)=E~(ℓ)for all ℓ. Z_L(G)^( )= P_E Z^( ) all . Any graph readout that is invariant to the order of vertices or edges therefore satisfies READOUT(he(Tnet):e∈V(L(G)))=READOUT(h~e(Tnet):e∈E(G)).READOUT (\h_e^(T_net):e∈ V(L(G))\ )=READOUT (\ h_e^(T_net):e∈ E(G)\ ). The equivalence is therefore exact for edge-only ILG-11-GNN. D.2 Atomic Types on the Line Graph Let G be simple and undirected. A vertex of L(G)L(G) is a root edge e∈E(G)e∈ E(G). For ordered edge tuples =(e1,…,ek)∈E(G)ke=(e_1,…,e_k)∈ E(G)^k, the atomic type of e as a tuple of vertices in L(G)L(G) is determined by equality and adjacency among tuple coordinates: atpL(G)()=([ei=ej],[ei∼L(G)ej])1≤i,j≤k.atp_L(G)(e)= (1[e_i=e_j],1[e_i _L(G)e_j] )_1≤ i,j≤ k. Because ei∼L(G)eje_i _L(G)e_j if and only if ei≠eje_i≠ e_j and ei∩ej≠∅e_i∩ e_j≠ , this atomic type can be computed from the root-edge endpoints without building L(G)L(G). For k=2k=2, equality and adjacency collapse to the three-valued relation code rG(e,f)=0 if e=f,rG(e,f)=1 if e∼L(G)f,rG(e,f)=2 otherwise.r_G(e,f)=0 if e=f, r_G(e,f)=1 if e _L(G)f, r_G(e,f)=2 otherwise. Thus every initial color used by k-WL on L(G)L(G) is an endpoint-incidence function on G. Remark 3 (Completeness of the relation code for k=2k=2). The three-valued code rG(e,f)r_G(e,f) determines the atomic type of the ordered pair (e,f)(e,f) in L(G)L(G). The only line-graph relations between two vertices are equality, adjacency, and non-adjacency. Since line-graph adjacency is symmetric for simple undirected G, the code is symmetric: rG(e,f)=rG(f,e)r_G(e,f)=r_G(f,e). The initial atomic type for an ordered pair is therefore (rG(e,f),rG(f,e))=(rG(e,f),rG(e,f))(r_G(e,f),r_G(f,e))=(r_G(e,f),r_G(e,f)), which is determined by rG(e,f)r_G(e,f) alone. D.3 Forward Transfer: 11-WL Equivalence Implies Line-Graph 11-WL Equivalence We prove Proposition 2. Suppose G≡1-WLHG _1-WLH. We argue directly with the stable 11-WL (color-refinement) colorings; this is equivalent to the fractional-isomorphism characterization [24, 15] and avoids constructing an explicit doubly stochastic matrix on edges. Let cGc_G and cHc_H be the stable 11-WL vertex colorings of G and H. For stable colors a,ba,b, let qG(a,b)q_G(a,b) be the number of neighbors of color b at a vertex of color a; define qHq_H analogously. Define an induced coloring of the line graph by c^G(e)=cG(u),cG(v)for e=u,v∈E(G), c_G(e)= \\! \c_G(u),c_G(v) \\! \ e=\u,v\∈ E(G), and likewise c^H c_H on L(H)L(H). c^G c_G is equitable on L(G)L(G). Fix e=u,ve=\u,v\. Its neighbors in L(G)L(G) are the root edges sharing u or v, other than e. For any target color a,b \\! \a,b \\! \, the number of such edges f with c^G(f)=a,b c_G(f)= \\! \a,b \\! \ is determined by cG(u),cG(v)c_G(u),c_G(v) and the quotient numbers qGq_G, with the contribution of e itself removed. It is therefore constant on each c^G c_G-class. Thus c^G c_G is equitable; the same proof applies to c^H c_H. We do not require these induced colorings to be the coarsest equitable partitions. Transfer. Because G≡1-WLHG _1-WLH, a stable-color bijection identifies the class sizes and quotient numbers qG,qHq_G,q_H. It therefore maps c^G c_G-classes to c^H c_H-classes while preserving their sizes and their equitable quotients. Starting color refinement from these matched equitable partitions gives identical stable histograms; coarsening back to the uniform initialization cannot separate the graphs either. Therefore L(G)≡1-WLL(H)L(G) _1-WLL(H). ∎ D.4 Equal-Order Failure of First-Order Backward Transfer For the roots in Proposition 3, the different root degree histograms 42264^22^6 and 36123^61^2 prove 11-WL inequivalence. To verify the line premise without relying on software, start line-graph color refinement from degrees. In both line graphs, two vertices have degree two and eight have degree four. The next round splits the degree-four vertices according to whether they have a degree-two neighbor, producing cells A,B,CA,B,C of sizes 2,4,42,4,4. Their common quotient is A:(0,2,0),B:(1,1,2),C:(0,2,2).A:(0,2,0), B:(1,1,2), C:(0,2,2). This partition is equitable and therefore stable. Thus the two line graphs have identical stable color-class sizes and quotients, while the roots do not. This also explains why an argument based only on root order or inverse-line-graph uniqueness cannot prove first-order backward transfer. D.5 Equivalence of ILG-k-WL and k-WL on L(G)L(G) We prove Proposition 1. For k=1k=1, the ILG update uses exactly the line-neighbor set identified in the proof of Lemma 1; hence its color refinement is exactly 11-WL on L(G)L(G). Assume for the remainder of this subsection that k≥2k≥ 2. Let ctL(G),ctILG,G:E(G)k→tc_t^L(G),c_t^ILG,G:E(G)^k _t denote the two colorings, run with the shared encoding convention of Section 2. Both start from the same atomic type: c0L(G)()=c0ILG,G()=HASH(atpL(G)()).c_0^L(G)(e)=c_0^ILG,G(e)=HASH(atp_L(G)(e)). For =(e1,…,ek)e=(e_1,…,e_k) and g∈E(G)g∈ E(G), write [i←g]=(e1,…,ei−1,g,ei+1,…,ek).e[i← g]=(e_1,…,e_i-1,g,e_i+1,…,e_k). The separate-coordinate k-WL update on L(G)L(G) is ct+1L(G)()=HASH(ctL(G)(),(ctL(G)([i←g]):g∈E(G))i=1k).c_t+1^L(G)(e)=HASH (c_t^L(G)(e), ( \\! \c_t^L(G)(e[i← g]):g∈ E(G) \\! \ )_i=1^k ). The ILG-k-WL update is ct+1ILG,G()=HASH(ctILG,G(),(ctILG,G([i←g]):g∈E(G))i=1k).c_t+1^ILG,G(e)=HASH (c_t^ILG,G(e), ( \\! \c_t^ILG,G(e[i← g]):g∈ E(G) \\! \ )_i=1^k ). The two displayed recurrences have the same domain, initialization, replacement range, and update. Induction on t therefore gives ctL(G)()=ctILG,G()(∈E(G)k)c_t^L(G)(e)=c_t^ILG,G(e) (e∈ E(G)^k) at every round. If two implementations use different injective color names, the same induction instead supplies the canonical bijection between those names. Graph-level consequence. Since the tuple domains are identical and the colors agree at every round, their graph-level signatures agree: ctILG,G():∈E(G)k=ctL(G)():∈E(G)kfor all t. \\! \c_t^ILG,G(e):e∈ E(G)^k \\! \= \\! \c_t^L(G)(e):e∈ E(G)^k \\! \ all t. Therefore any graph pair separated by k-WL on L(G)L(G) is separated by ILG-k-WL on G, and conversely. ∎ D.6 Equivalence of Global-Edge ILG-k-WL and k-WL on L(G)L(G) We prove Corollary 1 for k≥3k≥ 3, writing the update explicitly for k=3k=3. From direct ILG-k-WL to the global-replacement form. The direct ILG-k-WL state space is E(G)kE(G)^k. Its separate-coordinate update contains k replacement multisets and enumerates O(mk+1)O(m^k+1) replacement entries per round; canonical sorting gives the O(mk+1logm)O(m^k+1 m) worst-case time in Table 2. The global-edge construction instead uses the equivalent global-replacement form on (k−1)(k-1)-tuples. At k=3k=3, the pair coloring of L(G)L(G) has the update ϑtL(G)(g,e,f):=(ctFWL,L(G)(g,f),ctFWL,L(G)(e,g)), _t^L(G)(g;e,f):= (c_t^FWL,L(G)(g,f),c_t^FWL,L(G)(e,g) ), ct+1FWL,L(G)(e,f)=HASH(ctFWL,L(G)(e,f),ϑtL(G)(g,e,f):g∈E(G)).c_t+1^FWL,L(G)(e,f)=HASH (c_t^FWL,L(G)(e,f), \\! \ _t^L(G)(g;e,f):g∈ E(G) \\! \ ). This pair-state process has the same stable graph-distinguishing power as the separate-coordinate 33-WL convention fixed in Section 2 [12]. Restriction to k≥3k≥ 3. For k=2k=2, global replacement has one-edge states. Its message ct(g):g∈E(G) \\! \c_t(g):g∈ E(G) \\! \ contains no relation between g and the current edge, so it cannot recover line-graph adjacency; for example, it fails on P4P_4 versus K1,3K_1,3. Adding rG(g,e)r_G(g,e) restores exactly 11-WL power. The k=2k=2 comparison therefore follows from the graph-level equivalence of 11-WL and 22-WL. Specialization to the line graph. All atomic information needed to initialize this pair coloring is given by rG(⋅,⋅)r_G(·,·) (Remark 3). Define the global-edge coloring ctGE,Gc_t^GE,G by c0GE,G(e,f)=HASH(rG(e,f)),c_0^GE,G(e,f)=HASH(r_G(e,f)), and, with ϑtGE,G(g,e,f):=(ctGE,G(g,f),ctGE,G(e,g),rG(g,e),rG(g,f)), _t^GE,G(g;e,f):= (c_t^GE,G(g,f),c_t^GE,G(e,g),r_G(g,e),r_G(g,f) ), ct+1GE,G(e,f)=HASH(ctGE,G(e,f),ϑtGE,G(g,e,f):g∈E(G)).c_t+1^GE,G(e,f)=HASH (c_t^GE,G(e,f), \\! \ _t^GE,G(g;e,f):g∈ E(G) \\! \ ). Redundancy of the extra relation codes. At every round t≥0t≥ 0, the color ctGE,G(e,g)c_t^GE,G(e,g) refines its initial color and therefore determines rG(g,e)r_G(g,e). Symmetrically, ctGE,G(g,f)c_t^GE,G(g,f) determines rG(g,f)r_G(g,f). Thus the two appended relation codes are functions of the first two entry coordinates and cannot refine the multiset partition. Partition equivalence by induction. At t=0t=0, both colorings are injective functions of rG(e,f)r_G(e,f), so they induce the same partition. Assume a color-name bijection πt _t identifies their partitions at round t. The global-replacement multiset is tFWL,L(G)(e,f)=ϑtL(G)(g,e,f):g∈E(G).S_t^FWL,L(G)(e,f)= \\! \ _t^L(G)(g;e,f):g∈ E(G) \\! \. The global-edge multiset is tGE,G(e,f)=ϑtGE,G(g,e,f):g∈E(G).S_t^GE,G(e,f)= \\! \ _t^GE,G(g;e,f):g∈ E(G) \\! \. Apply πt _t to the first two coordinates. The preceding paragraph shows that the remaining two coordinates are fixed functions of them, so the two multisets determine one another. Their full update signatures therefore induce the same partition at round t+1t+1, giving πt+1 _t+1. ∎ D.7 Neural Simulation of the Tuple Refinement We prove Proposition 5 for k=3k=3, where the states are edge pairs. The general construction replaces pairs by ordered (k−1)(k-1)-tuples. Setup. Fix a feature-labeled graph class G with |E(G)|≤mmax|E(G)|≤ m_ for all G∈G , and assume that its edge features range over a fixed finite alphabet. At k=3k=3, the global-edge ILG-k-GNN layer is Mef(ℓ)=∑g∈E(G)ψℓ(hgf(ℓ),heg(ℓ),qg,Embr(rG(g,e)),Embr(rG(g,f))),M_ef^( )= _g∈ E(G) _ (h_gf^( ),h_eg^( ),q_g,Emb_r(r_G(g,e)),Emb_r(r_G(g,f)) ), hef(ℓ+1)=ηℓ(hef(ℓ),Mef(ℓ)).h_ef^( +1)= _ (h_ef^( ),M_ef^( )). Simulation direction (lower bound). We construct functions ψℓ,ηℓ _ , _ such that hef(ℓ)h_ef^( ) encodes the feature-labeled discrete color cℓGE,G(e,f)c_ ^GE,G(e,f). Base case. Choose EmbrEmb_r injective and choose ϕ0 _0 to be injective on the finite domain (qe,qf,Embr(rG(e,f))):e,f∈E(G),G∈\(q_e,q_f,Emb_r(r_G(e,f))):e,f∈ E(G),\ G \. For the feature-labeled refinement, set c0GE,G(e,f)=HASH(qe,qf,rG(e,f)).c_0^GE,G(e,f)=HASH(q_e,q_f,r_G(e,f)). Then hef(0)=ϕ0(qe,qf,Embr(rG(e,f)))h_ef^(0)= _0(q_e,q_f,Emb_r(r_G(e,f))) injectively encodes this initial color. Induction step. Suppose hef(ℓ)=χℓ(cℓGE,G(e,f))h_ef^( )= _ (c_ ^GE,G(e,f)) for an injective code χℓ:ℓ→ℝdh _ :D_ ^d_h. Define the replacement entry τℓG(g,e,f)=(cℓGE,G(g,f),cℓGE,G(e,g),rG(g,e),rG(g,f),qg). _ ^G(g;e,f)= (c_ ^GE,G(g,f),c_ ^GE,G(e,g),r_G(g,e),r_G(g,f),q_g ). The entry set is finite, with cardinality at most |ℓ|2 32|qg|.|D_ |^2\,3^2\,|\q_g\|. Consequently τℓG(g,e,f):g∈E(G) \\! \ _ ^G(g;e,f):g∈ E(G) \\! \ ranges over a finite family of multisets of size at most mmaxm_ . By the multiset-encoding lemma [27], for any countable domain and bounded multiset size, there exists a function ωℓ _ and a dimension d such that Φℓ(τℓG(g,e,f):g∈E(G)):=∑g∈E(G)ωℓ(τℓG(g,e,f))∈ℝd _ ( \\! \ _ ^G(g;e,f):g∈ E(G) \\! \ )\;:=\; _g∈ E(G) _ ( _ ^G(g;e,f))\;∈\;R^d is injective in the multiset argument. Since χℓ _ and EmbrEmb_r are injective, the neural message inputs determine τℓG _ ^G. Choose ψℓ _ to realize ωℓ _ on this finite input domain; an MLP of sufficient width can do so. Then Mef(ℓ)=∑g∈E(G)ψℓ(⋯)=Φℓ(τℓG(g,e,f):g∈E(G)),M_ef^( )= _g∈ E(G) _ (·s)= _ ( \\! \ _ ^G(g;e,f):g∈ E(G) \\! \ ), which is injective in the replacement multiset. Choose ηℓ _ to map (hef(ℓ),Mef(ℓ))(h_ef^( ),M_ef^( )) injectively to a new code for cℓ+1GE,G(e,f)c_ +1^GE,G(e,f). The discrete update shows that these two inputs determine the new color. At the final round, pair colors and edge features range over finite domains. Since the final hidden states injectively encode pair colors and both domains and their multiset sizes are finite, choose γread _read and ξ so that their sums injectively encode the respective multisets. Choose READOUTREADOUT injective on the resulting finite set of summary pairs. The graph output then injectively encodes the complete feature-labeled refinement signature. Upper bound (converse). Run the feature-labeled refinement jointly on G and H, so equal color names have a graph-independent meaning. We prove by induction that, for fixed network parameters, there is one function FℓF_ such that, for K∈G,HK∈\G,H\, hef(ℓ)=Fℓ(cℓGE,K(e,f))(e,f∈E(K)).h_ef^( )=F_ (c_ ^GE,K(e,f)) (e,f∈ E(K)). The base case follows from the initial color above. At the induction step, the new color determines the old color and the complete multiset of replacement entries τℓK(g,e,f) _ ^K(g;e,f). The induction hypothesis therefore determines every message input, its multiset, the aggregate, and the updated state. This defines Fℓ+1F_ +1 independently of K. If the two graphs are not separated by the feature-labeled refinement, the multiplicity of every final pair color is the same on both sides; the same is true for every edge-feature color represented on the diagonal. Hence the graph readout hK=READOUT(∑e,f∈E(K)γread(hef(Tnet)),∑e∈E(K)ξ(qe)),K∈G,H,h_K=READOUT ( _e,f∈ E(K) _read(h_ef^(T_net)), _e∈ E(K)ξ(q_e) ), K∈\G,H\, receives identical multisets of inputs and gives hG=hHh_G=h_H. No tuplewise or edgewise bijection between the graphs is used. ∎ D.8 Algorithmic Specification This section specifies the global-edge ILG-k-GNN forward pass for general k. The procedure operates directly on G without constructing the adjacency list of L(G)L(G). Fix an edge ordering G=(e1,…,em)E_G=(e_1,…,e_m) of E(G)E(G). Step 1: edge features. Construct an edge feature matrix G∈ℝm×de Q_G ^m× d_e. For unlabeled simple graphs, (G)i( Q_G)_i may be a constant vector. With vertex labels, (G)i( Q_G)_i concatenates a constant edge indicator with the one-hot labels of the two endpoints in sorted order. Step 2: relation access. After locally indexing the incident root vertices, store the endpoint table G∈ℕm×2 P_G ^m× 2, whose i-th row lists the two endpoint indices of eie_i. A relation code is computed in O(1)O(1) by comparing two rows: rG(ei,ej)=0r_G(e_i,e_j)=0 when i=ji=j, 11 when the rows share an entry, and 22 otherwise. Constructing and retaining G P_G uses O(m)O(m) time and space. The layer evaluates rGr_G only for the index pairs of the current tuple chunk rather than retaining a relation matrix. In Steps 3–4, (G)ij( R_G)_ij denotes a call to this accessor, not a stored tensor. Implementations that require a dense relation tensor may instead materialize G∈0,1,2m×m R_G∈\0,1,2\^m× m, using O(m2)O(m^2) space. This tensor is not required by the model definition or by an implementation that computes relations on demand. Step 3: tuple initialization. For every ordered (k−1)(k-1)-tuple =(i1,…,ik−1)i=(i_1,…,i_k-1), compute (0)=ϕ0((G)i1,…,(G)ik−1,((G)ip,iq)1≤p<q≤k−1). Z_i^(0)= _0 (( Q_G)_i_1,…,( Q_G)_i_k-1,\; (( R_G)_i_p,i_q )_1≤ p<q≤ k-1 ). This yields (0)∈ℝmk−1×dh Z^(0) ^m^k-1× d_h. Step 4: global-edge message aggregation. For each layer ℓ and each tuple i, aggregate over the global edge index g: (ℓ)=∑g=1mψℓ(([p←g](ℓ))p=1k−1,(G)g,((G)g,ip)p=1k−1), M_i^( )= _g=1^m _ ( ( Z_i[p← g]^( ) )_p=1^k-1,\;( Q_G)_g,\; (( R_G)_g,i_p )_p=1^k-1 ), where [p←g]i[p← g] denotes the tuple with coordinate p replaced by g. Then update (ℓ+1)=ηℓ((ℓ),(ℓ)) Z_i^( +1)= _ ( Z_i^( ), M_i^( )). Step 5: invariant readout. After TnetT_net layers, produce graph logits by applying an invariant readout, where ∥\| denotes vector concatenation: zG=MLP([,∥,]).z_G=MLP ( [ _i _read( Z_i^(T_net))\; \|\; _iξ(( Q_G)_i) ] ). Any fixed edge and tuple ordering may be used. Under a vertex relabeling, G,G, R_G, Q_G, Z are permuted consistently, and the final sums are unchanged. D.9 Permutation Equivariance and Invariance We prove equivariance and invariance for the k=3k=3 instantiation (edge pairs); the general (k−1)(k-1)-tuple case is identical. Let σ:V(G)→V(H)σ:V(G)→ V(H) be a relabeling isomorphism and define its induced edge bijection by σE(u,v)=σ(u),σ(v). _E(\u,v\)=\σ(u),σ(v)\. For e∈E(G)e∈ E(G), write e¯=σE(e) e= _E(e). Primes denote features and hidden states on H=σ(G)H=σ(G). Relation preservation. For any e,f∈E(G)e,f∈ E(G), the edges share an endpoint if and only if their images do. Therefore rH(e¯,f¯)=rG(e,f).r_H( e, f)=r_G(e,f). Initialization. If edge features satisfy qe¯′=qeq_ e =q_e (i.e., features are defined intrinsically), then the initialized pair tensor satisfies he¯,f¯′(0) h_ e, f (0) =ϕ0(qe¯′,qf¯′,Embr(rH(e¯,f¯))) = _0(q_ e ,q_ f ,Emb_r(r_H( e, f))) =ϕ0(qe,qf,Embr(rG(e,f)))=hef(0). = _0(q_e,q_f,Emb_r(r_G(e,f)))=h_ef^(0). Induction. Assume he¯,f¯′(ℓ)=hef(ℓ)h_ e, f ( )=h_ef^( ) for all e,f∈E(G)e,f∈ E(G). The message for the relabeled pair is Me¯,f¯′(ℓ) M_ e, f ( ) =∑g′∈E(H)ψℓ(hg′,f¯′(ℓ),he¯,g′(ℓ),qg′,Embr(rH(g′,e¯)),Embr(rH(g′,f¯))). = _g ∈ E(H) _ (h_g , f ( ),h_ e,g ( ),q_g ,Emb_r(r_H(g , e)),Emb_r(r_H(g , f)) ). Substituting g′=σE(g)g = _E(g), using the bijection E(G)→E(H)E(G)→ E(H), and applying the induction hypothesis, feature identity, and relation preservation gives Me¯,f¯′(ℓ)=∑g∈E(G)ψℓ(hgf(ℓ),heg(ℓ),qg,Embr(rG(g,e)),Embr(rG(g,f)))=Mef(ℓ).M_ e, f ( )= _g∈ E(G) _ (h_gf^( ),h_eg^( ),q_g,Emb_r(r_G(g,e)),Emb_r(r_G(g,f)) )=M_ef^( ). Thus he¯,f¯′(ℓ+1)=ηℓ(hef(ℓ),Mef(ℓ))=hef(ℓ+1)h_ e, f ( +1)= _ (h_ef^( ),M_ef^( ))=h_ef^( +1). Invariance. The graph readout sums over all ordered edge pairs and all edges. Since σE:E(G)→E(H) _E:E(G)→ E(H) is a bijection, the multisets he¯,f¯′(Tnet):e,f∈E(G)andhef(Tnet):e,f∈E(G) \\! \h_ e, f (T_net):e,f∈ E(G) \\! \ \\! \h_ef^(T_net):e,f∈ E(G) \\! \ are identical, and likewise for edge features. Therefore the invariant readouts are equal: hH=hGh_H=h_G. ∎ D.10 Complexity Details Let n=|V(G)|n=|V(G)|, m=|E(G)|m=|E(G)|, mL=|E(L(G))|=∑v∈V(G)(dG(v)2)m_L=|E(L(G))|= _v∈ V(G) d_G(v)2, and fix k≥3k≥ 3. Table 2 reports worst-case upper bounds for fixed k and fixed neural feature widths. Discrete update signatures are streamed one target tuple at a time. For the neural implementation, C is the target-tuple chunk size. Table 2: Worst-case complexity of the root- and line-domain formulations. Initialization is performed once; iterative costs are per refinement round or neural layer. Method Time Peak space Root G (k−1)(k-1)-FWL O(nk−1+n+m)O(n^k-1+n+m) initialization; O(nklogn)O(n^k n) per round O(nk−1+n+m)O(n^k-1+n+m) Direct ILG-k-WL O(mk)O(m^k) initialization; O(mk+1logm)O(m^k+1 m) per round O(mk+m)O(m^k+m) Explicit L(G)L(G) (k−1)(k-1)-FWL O(mk−1+m+mL)O(m^k-1+m+m_L) initialization; O(mklogm)O(m^k m) per round O(mk−1+m+mL)O(m^k-1+m+m_L) Global-edge ILG-k-WL O(mk−1+m)O(m^k-1+m) initialization; O(mklogm)O(m^k m) per round O(mk−1+m)O(m^k-1+m) Global-edge ILG-k-GNN O(mk−1+m)O(m^k-1+m) initialization; O(mk)O(m^k) per layer O(mk−1+Cm)O(m^k-1+Cm) per layer with checkpointing Direct ILG-k-WL stores k-tuples, whereas global-edge ILG-k-WL stores (k−1)(k-1)-tuples; this accounts for the additional factor of m in the direct formulation. Explicit (k−1)(k-1)-FWL on L(G)L(G) and global-edge ILG-k-WL have the same per-round complexity. They differ in whether line-graph adjacency is stored or computed from root-edge endpoints. Since mL≤(m2)=O(m2)m_L≤ m2=O(m^2), both use O(m2)O(m^2) total worst-case space at k=3k=3. The O(m)O(m) versus O(m+mL)O(m+m_L) difference refers only to graph storage, excluding tuple states. If exact color identifiers occupy a dense integer range of suitable size, array-based counting removes the sorting factor. T rounds or layers multiply iterative time by T. The reported ILG-33-GNN experiment and the empirical cost experiment both execute the dense ordered edge-pair state space, so their implementation does not alter these bounds. The deterministic refinement runner represents each canonical signature by a deterministic 128128-bit digest. A digest collision is therefore possible but highly unlikely. Appendix E Empirical Cost and Scaling Objectives. At k=3k=3, we test four claims: line-domain cost scales with m; computing adjacency from root endpoints avoids storing E(L(G))E(L(G)) but leaves the m2m^2 states and m3m^3 updates unchanged; root 44-WL can be cheaper on dense roots; and explicit and implicit implementations return the same signatures. Experimental setup. We compare root 22-FWL (the paper’s root 33-WL), root 33-FWL (root 44-WL), 22-FWL on an explicitly materialized L(G)L(G), and global-edge ILG-33-WL. The explicit and implicit methods use the same deterministic pair-refinement implementation with 128128-bit digests. The explicit method constructs and retains E(L(G))E(L(G)), including isolated line vertices, whereas the implicit method queries the atomic relation from the root-edge endpoints. We checked their final signatures for equality on every measured call; all checks passed. All methods use dense state spaces, one graph per call, and complete refinement rounds. The primary sweep uses connected d-regular roots on n=25n=25 vertices for d∈2,4,6,8,12,16,20,24d∈\2,4,6,8,12,16,20,24\, with three fixed seeds per degree (the endpoints are C25C_25 and K25K_25). This fixes every root-domain state and replacement count while varying m=25d/2m=25d/2. Each call performs atomic initialization and exactly one complete refinement round, avoiding graph-dependent stabilization depth. A fresh single-threaded process first performs one warm-up and then three timed calls; Table 3 reports the median over the resulting nine observations. Peak resident set size (RSS) is measured without allocation tracing in a separate fresh process on the fixed first seed. Root generation and interpreter start-up are excluded from time, while explicit line-graph construction is included. The reference run used an Apple M2 CPU, macOS 26.5.1, Python 3.12.4, and NetworkX 3.6.1. All algorithmic calls are single-process with library thread counts fixed to one. The benchmark runner records every repetition, seed, IQR, pre-call RSS, graph count, software version, and exact output digest. As with the other deterministic experiments, colors use 128128-bit digests, so equality has negligible rather than mathematically zero collision risk. Table 3: Fixed-n=25n=25 one-round cost sweep. Times are median seconds; four representative degrees are shown, while the exponent fit uses all six points with m≥75m≥ 75. RSS columns report absolute fresh-process peaks in MiB for one fixed graph. At the displayed degrees, (m,mL)(m,m_L) equals (25,25)(25,25), (75,375)(75,375), (150,1650)(150,1650), and (300,6900)(300,6900), respectively. Explicit and implicit signatures agreed throughout. End-to-end one-round time [s] Peak RSS [MiB] Method States Entries/round d=2d=2 d=6d=6 d=12d=12 d=24d=24 d=12d=12 d=24d=24 Root 33-WL n2n^2 n3n^3 0.0138 0.0152 0.0160 0.0117 52.6 52.1 Root 44-WL n3n^3 n4n^4 0.4926 0.5934 0.6698 0.3813 54.6 54.5 Explicit L(G)L(G) 22-FWL m2m^2 m3m^3 0.0142 0.2655 1.8221 12.8667 54.9 58.4 Implicit ILG-33-WL m2m^2 m3m^3 0.0134 0.2693 1.7507 11.4022 55.3 60.8 Density-sweep results. For the six points with m≥75m≥ 75, an ordinary least-squares fit of log(time) (time) against logm m gives slope 2.602.60 (95%95\% CI [2.18,3.03][2.18,3.03], R2=0.986R^2=0.986) for explicit line refinement and 2.602.60 ([2.33,2.87][2.33,2.87], R2=0.995R^2=0.995) for implicit ILG. These finite-range slopes describe the measured regime; the benchmark separately records exactly m3m^3 replacement entries per round, which is the claimed combinatorial count. Root 33- and 44-WL retain fixed state and replacement counts throughout the sweep; their measured constants still vary with the color alphabet. The line-domain runtime crosses root 44-WL between m=100m=100 and m=150m=150. At the SR25 scale (n,m)=(25,150)(n,m)=(25,150), implicit ILG takes 2.612.61 times the one-round wall time of root 44-WL. Isolating structural storage. To separate graph representation from tuple state, we first fix m=150m=150 and compare four connected roots with sharply different degree concentration. Endpoint-table preparation and explicit line-graph materialization are timed without refinement. Allocation peaks are traced separately after root generation, avoiding the interpreter baseline that would mask the small endpoint table. Table 4: Fixed-m=150m=150 structural representation cost. Each root has the same m2=22,500m^2=22,500 subsequent line-domain pair states. Times are medians of five calls after one warm-up; allocation is the peak traced Python heap in a separate fresh process. Endpoint table Explicit L(G)L(G) Root n mLm_L Time [ms] Peak [MiB] Time [ms] Peak [MiB] P151P_151 151 149 0.099 0.026 0.510 0.058 Cubic 100 300 0.083 0.026 0.604 0.077 SR25 25 1,650 0.091 0.025 2.357 0.368 K1,150K_1,150 151 11,175 0.089 0.025 15.151 2.017 The same structural-only experiment on Pm+1P_m+1 and K1,mK_1,m for m∈100,200,400,800m∈\100,200,400,800\ gives endpoint-allocation slopes 0.970.97 on both families. Explicit materialization has slope 0.950.95 on paths, where mL=m−1m_L=m-1, and 1.861.86 on stars, where mL=(m2)m_L= m2. At m=800m=800, endpoint preparation takes 0.4090.409 ms and 0.1300.130 MiB on the star, versus 454.7454.7 ms and 59.059.0 MiB for explicit materialization. Once the common pair refinement is included at m=150m=150, however, the four implicit one-round times occupy only 1.381.38–1.461.46 s and the explicit times 1.411.41–1.761.76 s despite a 7575-fold range in mLm_L. Thus the endpoint representation removes the structural term, but the m2m^2 state and m3m^3 replacement work dominate the full k=3k=3 computation. Stabilized SR25 case study. Finally, we run root 33-WL, root 44-WL, and ILG-33-WL to stabilization on all 1515 SR25 graphs. For each graph and method, the reported time is the median of three calls after one warm-up; totals sum the 1515 graph medians. Peak RSS is the maximum over 1515 separate memory processes. Table 5: End-to-end stabilized cost on the 1515 SR25 graphs, yielding 105105 pairwise separation verdicts. All graphs have (n,m,mL)=(25,150,1650)(n,m,m_L)=(25,150,1650). Method States Entries/round Separated Total time [s] Peak RSS [MiB] Root 33-WL 625 15,625 0/105 0.196 52.6 Root 44-WL 15,625 390,625 105/105 48.171 61.6 Implicit ILG-33-WL 22,500 3,375,000 105/105 230.442 67.4 On SR25, ILG has 3636 times the root-33-WL state and 216216 times its replacement count. Relative to root 44-WL, it has 1.441.44 times the state and 8.648.64 times the per-round replacements; stabilized implicit ILG is 4.784.78 times slower and uses 1.091.09 times the peak RSS in this reference implementation. Root 44-WL and ILG-33-WL separate all 105105 pairs. This SR25 cost comparison does not order their expressivity. Root 44-WL and ILG-33-WL are incomparable, so the higher ILG cost can still yield separations that root 44-WL misses (Remark 2). Appendix F Neural Evaluation Protocols This appendix specifies the pair-trained neural baselines and the untrained ILG-33-GNN experiment in Table 1. The ILG-33-GNN architecture and run seed are fixed across the substructure-counting witness pairs, SR25, and BREC evaluations, and no parameter optimization is performed. Pair-trained rows For locally computed pair-trained entries, we initialize and train a separate model for each graph pair and evaluation seed; parameters are not shared across pairs. Training uses a Siamese cosine-embedding loss with target −1-1 and Adam. The protocol uses q=32q=32 copies of each graph under different vertex orderings; here q is the number of copies. A pair counts as separated when its paired-comparison statistic exceeds the BREC threshold 72.3472.34 and its isomorphic-copy reliability statistic remains below that threshold [25]. For the controls, substructure-counting witness pairs, SR25, and ILG-11-GNN BREC results, seeds 0,1,20,1,2 are used and a pair counts as separated when at least two seeds pass both checks. The two controls are an isomorphic copy and the Whitney pair K3,K1,3K_3,K_1,3. Each SR25 pair is trained and evaluated separately, and the table aggregates the 105105 decisions. The locally compared state domains are root edges for ILG-11-GNN, unordered root 33-subsets for Morris 33-GNN, and ordered root-vertex pairs for PPGN [22, 20]. ILG-11-GNN The ILG-11-GNN grid uses the pair-trained protocol on the controls, substructure-counting witness pairs, SR25, and BREC. None of the reported pairs is separated. This is consistent with the theoretical upper bound: under the canonical edge/line-vertex identification, the architecture is an MPNN on L(G)L(G) and is bounded by 11-WL on that graph. Morris 33-GNN on BREC We use a fixed configuration with two shared full-replacement layers of width 6464, mean pooling over all unordered vertex triples, and seeds 100,200,300100,200,300. After verifying that every seed produces valid results for all 400400 pairs, we select the seed with the largest number of separations; pairs from different seeds are not combined. The value 207/400207/400 is reported as a neural separation count rather than as equality with a computed pairwise set-33-WL bound. PPGN The BREC value 233/400233/400 is sourced from Wang and Zhang [25, Table 2] under that paper’s protocol. The SR25 and substructure-counting witness-pair cells are computed locally using the pair-trained protocol above. The row therefore reports graph-pair separation under these source-specific protocols. Untrained ILG-33-GNN configuration We fix run seed 500500 and deterministically derive one fresh initialization for every substructure-counting witness pair, SR25 pair, and BREC pair. The same initialized parameters are used for both graph sides, with no parameter updates. The global-edge architecture maintains dense ordered root-edge-pair states and uses constant edge features, the invariant equality/incident/disjoint relation codes, width 3232, five replacement layers, a 1616-dimensional graph output, σ(x)=sin(5x)σ(x)= (5x), and multiscale sum readout. A parameter-free layer normalization is applied to the graph output before distances are computed. Evaluation uses CPU float64 arithmetic and order-stabilized reductions. The inputs contain no vertex identifiers, edge identifiers, or exact refinement colors, and the single run seed is used throughout. Relabeling decision For each graph, we construct four copies: the stored ordering and three independently relabeled copies. Thus q=4q=4 for the reported result. Let zaG,zbHz^G_a,z^H_b be their graph outputs and define B=mina,b∥zaG−zbH∥2,WG=maxa,a′∥zGa−zGa′∥2,WH=maxb,b′∥zHb−zHb′∥2. splitB&= _a,b z^G_a-z^H_b _2,\\ W_G&= _a,a z^G_a-z^G_a _2, W_H= _b,b z^H_b-z^H_b _2. split The pair is counted as separated only if B−maxWG,WH−τ>0,τ=10−7⋅72.34≈2.6896×10−3.B- \W_G,W_H\-τ>0, τ= 10^-7· 72.34≈ 2.6896× 10^-3. Here τ is the direct-ℓ2 _2 floor induced by the BREC covariance ridge 10−710^-7 and decision threshold 72.3472.34. We use this direct ℓ2 _2 criterion rather than the BREC RPC statistic. Every reported separation uses all four copies; the two-copy stage may reject a pair early. Nonfinite values and execution errors are treated as failures to separate. We apply the same configuration to the three substructure-counting witness pairs, the 105105 SR25 pairs, and the 400400 BREC main pairs; the rule separates 3/33/3, 105/105105/105, and 359/400359/400, respectively. Every evaluation yields valid finite outputs. After computing the neural decisions, we compare each suite with deterministic ILG-33-WL, and the pairwise verdicts coincide. The same protocol does not separate either the isomorphic C6C_6 control or the Whitney pair K3,K1,3K_3,K_1,3. Since L(K3)≅L(K1,3)≅K3L(K_3) L(K_1,3) K_3, every invariant line-graph model with the constant features used here must give the Whitney pair the same output. Dense execution All reported ILG-33-GNN results use the dense ordered edge-pair state space. The implementation also supports exact-color state compression. It groups states with identical exact-refinement transition signatures while retaining the size of each group. For fixed weights, this is an execution optimization of the same recurrence; compression-group indices are not supplied as features, targets, or readout coordinates. The table therefore reports untrained separation counts under the rule above rather than BREC RPC scores or supervised-training results. Full configurations, source runners, tests, and reproduction commands are provided in the accompanying repository: https://github.com/lukeyf/ilg-wl. GenAI Usage Statement Generative AI was used to survey related work, to develop the detailed arguments of the proofs in Appendix A, to assist in constructing the Lean 4 formalization, to assist in designing and implementing the empirical complexity evaluation, and for language editing and code assistance. The choice of research direction and of proof strategy was made by the author. The author reviewed all AI-assisted material, and the formal development is checked by the Lean 4 kernel. The author takes responsibility for the contents of the paper and artifact.