PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Fan Yang

arXiv:2609.16412v1cs.SIcs.AIcs.LG

TL;DR

Fixed-dimensional WL expressivity on a graph’s line graph need not match its expressivity on the root, making their comparison nontrivial. The paper studies this relation through ILG-k-WL and proves a backward-transfer result at k = 3. ILG-3-WL separates many evaluated pairs, and an untrained dense ILG-3-GNN matches its verdicts.

  • Problem

    How fixed-dimensional WL expressivity on line graphs compares with expressivity on their roots is nontrivial, even though line graphs determine Whitney-general roots up to isomorphism.

    Source: §1 · p. 2

  • Method

    The paper compares root-domain and line-graph WL through ILG-k-WL, which runs k-WL over root edges using endpoint-derived line-graph relations.

    Source: §1 · p. 2

  • Results

    ILG-3-WL separated 3/3 substructure-counting witness pairs, 105/105 SR25 pairs, and 359/400 BREC pairs; an untrained dense ILG-3-GNN matched those verdicts.

    Source: §1 · p. 2, §7 · p. 9

  • Takeaways & Limitations

    On Whitney-general graphs, ILG-3-WL is strictly more expressive than root-domain 3-WL, and it counts four-cliques on every finite simple root graph.

    Source: §7 · p. 9

    Backward transfer for k ≥ 4 remains open.

    Source: §7 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

The introduction frames fixed-dimensional WL expressivity on roots and line graphs as a separate question from graph isomorphism, and presents ILG-k-WL as a way to compare them. Its contributions include dimension-dependent expressivity results and strong pair-separation results for ILG-3-WL.

Motivation

  • Whitney’s theorem says a connected simple graph’s line graph determines its root except for the pair K3 and K1,3, but this does not settle fixed-dimensional WL power.The paper focuses on the Whitney-general class, which excludes those exceptional graphs.Source: §1 · p. 1
  • The Shrikhande and 4 × 4 rook graphs have the same strongly regular parameters, yet ILG-3-WL separates them while 3-WL does not.Their four-clique counts are 0 and 8, respectively.Source: §1 · p. 2, Figure 1 · p. 2

Contributions

  • On Whitney-general graphs, ILG-k-WL is strictly weaker than root-domain k-WL for k = 1, 2, but strictly stronger for k = 3.The backward-transfer result also extends to disconnected graphs with no isolated vertices and Whitney-general components.Source: §1 · p. 2
  • ILG-k-WL runs k-WL over root edges using endpoint-derived line-graph relations, without explicitly constructing L(G).For k ≥ 3, its global-edge form uses Θ(m^(k−1)) root-edge tuple states.Source: §1 · p. 2
  • ILG-3-WL separated 3/3 substructure-counting witness pairs, 105/105 SR25 pairs, and 359/400 BREC pairs.The untrained dense ILG-3-GNN gives the same pairwise verdicts on these evaluations.Source: §1 · p. 2

2 Background and Conventions

The section fixes graph notation and the refinement conventions used to compare root graphs and line graphs. It defines the relevant graph classes, relation codes, and graph-level signatures.

Graph and line-graph notation

  • Root vertices and root edges are vertices and edges of G, and each root edge is canonically a vertex of L(G).The section also defines n and m as the numbers of root vertices and edges.Source: §2 · p. 2
  • A Whitney-general graph is connected, simple, and neither K3 nor K1,3; a componentwise Whitney-general graph has no isolated vertices and only Whitney-general components.Whitney’s theorem guarantees that a Whitney-general graph is determined up to isomorphism by its line graph.Source: §2 · p. 2

Line-graph relations

  • The line-graph relation code assigns 0 to identical edges, 1 to distinct edges sharing an endpoint, and 2 otherwise.The line graph joins exactly the distinct root edges that share an endpoint.Source: §2 · pp. 2–3

Refinement conventions

  • A graph-level signature is the multiset of state colors, and refinement distinguishes graphs when their signatures differ after stabilization or a specified number of rounds.Refinements run in parallel with shared encoding conventions, but replacement sweeps remain within each graph.Source: §2 · p. 3
  • For k ≥ 2, the paper uses oblivious k-WL on ordered k-tuples, with separate per-coordinate replacement; 1-WL is ordinary vertex color refinement.On finite simple graphs, 1-WL and 2-WL have the same graph-distinguishing power.Source: §2 · p. 3

3 Implicit Line-Graph WL

Implicit Line-Graph WL executes WL over root edges, since those edges are the vertices of the line graph. The section presents direct and global-edge forms, including a lower-storage arity-shifted formulation.

3 Implicit Line-Graph WL

  • Since V(L(G)) = E(G), k-WL on L(G) can be executed over root edges using relations derived from the root graph.The section presents first-order, direct higher-order, and arity-shifted global-edge forms.Source: §3 · p. 3

3.1 ILG-1-WL

  • ILG-1-WL is ordinary 1-WL on L(G), updating each root edge from the colors of other edges that share an endpoint.With shared initialization and maps, ILG-1-GNN and an MPNN on L(G) agree at every layer and at graph readout.Source: §3.1 · pp. 3–4

3.2 ILG-k-WL

  • For every graph and k ≥ 1, direct ILG-k-WL and k-WL on L(G) produce identical state partitions after each round, up to canonical color renaming.For k ≥ 2, direct ILG-k-WL applies the k-WL update to ordered root-edge tuples.Source: §3.2 · p. 4

3.3 Global-Edge Form with Θ(mk−1) Tuple-State Storage

  • For k ≥ 3, global-edge ILG-k-WL has the same graph-distinguishing power as k-WL on L(G), using Θ(m^(k−1)) rather than Θ(m^k) tuple states.Endpoint comparisons avoid storing line-graph adjacency without changing tuple-state or per-round update asymptotics.Source: §3.3 · p. 4

4 Expressivity Analysis

The comparison changes with dimension: ILG-k-WL is strictly weaker than root-domain k-WL for k = 1, 2, but strictly stronger for k = 3 on Whitney-general graphs. At k = 3, line-graph equivalence also transfers backward to the roots, with an extension to componentwise Whitney-general graphs.

4.1 First-Order: Loss at k = 1

  • For k = 1, 2, ILG-k-WL is strictly weaker than root-domain k-WL on Whitney-general graphs, including equal-order pairs separated by root 1-WL but not line-graph 1-WL.The first-order witness has different root degree multisets but line graphs with the same stable equitable quotient, with cells of sizes 2, 4, 4.Source: §4 · p. 4, §4.1 · pp. 4–5

4.2 Strictness at k = 3

  • One global pair-refinement round of ILG-3-WL determines the exact four-clique count on every finite simple graph, so equivalent graphs have the same count.The count follows from a factor-six double count.Source: §4.2 · p. 5
  • For k = 3, ILG-3-WL separates the Shrikhande and 4 × 4 rook graphs although root 3-WL does not.The co-parametric srg(16, 6, 2, 2) roots have 0 and 8 four-cliques, yielding ordered-pair color multiplicities 0 and 48.Source: §4.2 · pp. 5–6

4.3 Backward Transfer on Whitney-General Graphs at k = 3

  • On Whitney-general graphs, line-graph 3-WL equivalence implies root 3-WL equivalence, extending to componentwise Whitney-general roots with no isolated vertices.For connected graphs, the corresponding conclusion allows the Whitney exception {K3, K1,3}.Source: §4.3 · p. 6
  • Stable line-pair colors at k = 3 form a matrix algebra whose Gram identity recovers root endpoint data and stable ordered-pair coloring.The proof handles unequal endpoint profiles by orienting edges and equal profiles by a cancellation identity, then recovers remaining pair cells by induction on root distance.Source: §4.3 · p. 6
  • Root 4-WL and ILG-3-WL are incomparable even on connected Whitney-general simple graphs.Root 4-WL separates incidence graphs of nonisomorphic Steiner triple systems of order 13 that ILG-3-WL does not, while ILG-3-WL separates a compressed parity pair over K5 that root 4-WL does not.Source: §4.3 · p. 7

5 Higher-Order Neural Architecture

The higher-order architecture runs global-edge ILG-k-WL over ordered tuples of root edges. Under bounded-domain and finite-feature conditions, it can simulate the corresponding refinement, while its message-passing instances cannot distinguish graphs with identical refinement histories.

5 Higher-Order Neural Architecture

  • For k ≥ 3, the global-edge model stores one hidden state per ordered (k−1)-tuple of root edges and jointly encodes coordinate-wise replacements by each message edge.The k = 3 case uses ordered edge pairs.Source: §5 · p. 7
  • With bounded edge count and a finite edge-feature alphabet, choices of encodings and network maps let the GNN simulate any fixed number of global-edge ILG-k-WL rounds.Finite vertex labels may be included when encoded invariantly in the edge features.Source: §5 · p. 7
  • Graphs with identical refinement histories cannot be separated by these message-passing instances through an invariant readout.The evaluation table covers three substructure-counting witness pairs, all 105 SR25 pairs, and all 400 BREC pairs; its caption gives scope but not results.Source: §5 · p. 7, Table 1 · p. 8

6 Expressivity Evaluation

The evaluation compares deterministic refinements and neural realizations on witness pairs, SR25, and BREC. ILG-3-WL extends separations on key tests, and an untrained dense ILG-3-GNN reproduces its pairwise verdicts.

6 Expressivity Evaluation

  • The evaluation covers three substructure-counting witness pairs, 105 SR25 pairs, and 400 BREC pairs, using exact signatures and treating a pair as unseparated only after stabilization.The witness pairs contrast triangle, four-cycle, and four-clique counts; SR25 consists of 15 graphs with parameters srg(25, 12, 5, 6).Source: §6 · p. 8, §6.1 · p. 8

6.1 Deterministic Refinement

  • ILG-3-WL separates all three pattern-counting pairs and every SR25 pair, while root 3-WL misses Shrikhande/rook and assigns one signature to SR25’s 15 graphs.Root 3-WL separates the triangle and four-cycle pairs but not the four-clique pair.Source: §6.1 · p. 8
  • 139/140 BREC Regular pairs are separated by ILG-3-WL versus 50/140 by root 3-WL; both separate 60/100 CFI pairs and every Basic and Extension pair.ILG-3-WL separates 50/50 Simple Regular, 50/50 Strongly Regular, 20/20 4-Vertex Condition, and 19/20 Distance Regular pairs.Source: §6.1 · p. 8
  • The remaining 41 BREC pairs include 40 tested CFI pairs and one Distance Regular pair; the refinements agree on tested CFI blocks, with no claim about other CFI families.Both methods stabilize without separating the remaining Distance Regular pair.Source: §6.1 · p. 9

6.2 Neural Evaluation

  • 3/3 witness pairs, 105/105 SR25 pairs, and 359/400 BREC pairs are separated by ILG-3-WL, with matching verdicts from the untrained dense ILG-3-GNN.The neural model uses fixed parameters across each graph pair; separation requires a minimum cross-graph distance exceeding both within-graph diameters.Source: §6.2 · p. 9
  • Morris 3-GNN separates 0/105 SR25 pairs and 207/400 BREC pairs; its set-based refinement differs from the ordered-tuple 3-WL studied in this paper.It separates the triangle and four-cycle witness pairs but not the four-clique pair.Source: §6.2 · p. 9

7 Discussion and Conclusion

The discussion positions ILG-3-WL as more expressive than root-domain 3-WL on specified graph classes and evaluations. It also distinguishes this expressivity comparison from computational cost and leaves backward transfer for k ≥4 open.

7 Discussion and Conclusion

  • Root 4-WL is faster than ILG-3-WL on SR25 in the shared implementation, but the methods are incomparable in expressivity.ILG-3-WL distinguishes pairs that root 4-WL misses; the measurements show equal pair-state and per-round update costs for explicit and implicit line-domain refinement, with endpoint access avoiding stored line-graph structure.Source: §7 · p. 9
  • On Whitney-general graphs, ILG-k-WL is strictly weaker than root-domain k-WL for k = 1, 2, but strictly stronger for k = 3, including componentwise Whitney-general graphs.At k = 3, it counts four-cliques on every finite simple graph and separates more pairs than root 3-WL on SR25 and BREC’s Regular aggregate.Source: §7 · p. 9
  • The untrained dense ILG-3-GNN reproduces deterministic ILG-3-WL verdicts on the tested witness pairs, SR25, and BREC; this evaluates isomorphism expressivity rather than supervised prediction.The discussion notes that task performance in other line-graph networks may reflect useful representation, task-specific edge features, training, or model bias.Source: §7 · p. 9
  • Backward transfer for k ≥4 remains open; extending the k = 3 proof would require reconstructing higher-arity root tuple colors and simultaneous endpoint choices.The paper also identifies repeated line-graph transformation and its possible effect on 3-WL pair separation as future work.Source: §7 · p. 9

A Proof of the 3-WL Backward-Transfer Theorem

The proof derives the componentwise backward-transfer result from the connected Whitney-general core. Its central construction recovers the stable root pair algebra from the line-graph pair algebra.

A Proof of the 3-WL Backward-Transfer Theorem

  • The appendix proves the connected Whitney-general theorem first, then derives the componentwise extension using joint pair refinement.The notation keeps G and H for the roots and L(G) and L(H) for their line graphs.Source: A Proof of the 3-WL Backward-Transfer… · p. 12
  • Stable pair refinement is characterized through its coherent matrix algebra, which supplies the basis for recovering root-side structure from the line-graph algebra.The proof determines endpoint degrees and star and dart profiles, constructs root-side algebras and an induced isomorphism, then builds profile cells by distance.Source: A Proof of the 3-WL Backward-Transfer… · p. 12
  • The construction finishes the remaining root profile cells by induction on distance, yielding Hadamard-closed algebras and an isomorphism of stable root pair algebras.The appendix identifies the joint ordered-pair update as 2-FWL.Source: A Proof of the 3-WL Backward-Transfer… · p. 12

A.1 Coherent-algebra characterization of pair refinement

Stable joint pair refinement is characterized by a coherent matrix algebra: two graphs are equivalent exactly when their stable pair colors admit a bijection whose induced map preserves the specified matrix operations. The section also uses this framework to handle several small exceptional roots directly.

A.1 Coherent-algebra characterization of pair refinement

  • Pair-refinement equivalence holds exactly when a bijection between stable pair colors induces a map preserving identity, all-ones, the algebras, transpose, ordinary and Hadamard multiplication, and trace.The characterization is stated for the stable pair colors of the two graphs.Source: §A.1 · p. 13
  • The stable pair-relation span is a coherent matrix algebra, containing the identity and all-ones matrices and closed under transpose, ordinary multiplication, and Hadamard multiplication.The joint ordered-pair update is called 2-WL in the cited references and 2-FWL in the graph-learning terminology used here.Source: §A.1 · pp. 12–13
  • The converse recovers refinement rounds by preserving initial types and intersection numbers, then matching stable graph-level signatures.The proof inductively transports unions of stable relations and uses trace preservation to match color multiplicities.Source: §A.1 · p. 13
  • Finite Hadamard interpolation constructs indicators for joint entrywise level sets of transported matrices within the coherent algebra.The same polynomial is applied on both sides, so the construction is transported between the graphs.Source: §A.1 · p. 13
  • For Whitney-general roots K1, K2, the paw, and the diamond, 3-WL equivalence of line graphs implies root isomorphism.For the paw and diamond, line-graph degree multisets determine the line graphs; Whitney’s theorem then recovers the roots.Source: §A.1 · p. 14

A.2 Stable line data and root profiles

This section develops stable line-WL data and transports it into root-side algebras and profiles. It establishes correspondences for root-profile cells from diagonal and adjacent-relation structure through cells at every distance, connecting the line-algebra correspondence to the stable root algebras.

A.2 Stable line data and root profiles

  • Diagonal fibers fix transported unordered endpoint degrees, with the only line-degree multiset collision propagating to excluded Whitney-pair and paw cases.The line-degree multiset determines the endpoint degrees except for collision (A.3).Source: §A.2 · pp. 15–16
  • Every adjacent basis relation fixes its central degree and whether its wedges are open or closed, and these labels are transported.The only possible mixed case would force the excluded diamond configuration.Source: §A.2 · pp. 16–17
  • Diagonal fibers fix transported unordered endpoint star profiles, while each open adjacent relation fixes its central star profile.When no open relation leaves a fiber, a true-twin automorphism swaps the edge’s two wings and makes their profiles agree.Source: §A.2 · p. 17
  • Every adjacent basis relation fixes its central star profile, and star-profile class sizes are determined and transported.The class sizes are recovered from transported edge-fiber sizes.Source: §A.2 · pp. 17–18
  • Diagonal fibers fix transported unordered endpoint dart profiles, and every open adjacent relation fixes its source dart profile.When no open relation leaves the source fiber, a true-twin automorphism swaps the two wings and equates their profiles.Source: §A.2 · pp. 18–19
  • Each adjacent basis relation fixes and transports both its source and target dart profiles.The target-dart conclusion follows from the source-dart argument by transposition.Source: §A.2 · p. 19
  • Functionality and transport contradictions force both stable line parameters a and b to be positive.The argument rules out a = 0 (and symmetrically b = 0), with the cubic case leading to a cubic K4 root whose automorphic darts contradict x ≠ y.Source: §A.2 · pp. 19–20

A.3 The profile-oriented ordinary algebra

  • The profile-oriented root space is a unital, transpose-closed real algebra whose atomwise transport is an isomorphism preserving trace and carrying the identity, all-ones, and adjacency matrices.The construction uses root-profile projectors and incidence sandwiches formed from stable line-algebra matrices.Source: §A.3 · p. 21

A.4 Diagonal and root-edge profile cells

  • Diagonal extraction and equal-fiber cancellation establish transported diagonal structure and the identities needed to form root-profile cells.Diagonal extraction represents diagonal parts within the root algebra; equal-fiber cancellation annihilates adjacent-relation contributions in the stated identities.Source: §A.4 · pp. 22–24

G DiagV (G)(Z)BG

  • For every joint profile value, distance-zero and distance-one profile-cell matrices agree across the roots, including when either matrix is zero.The construction also gives a bijection between the nonzero cells at these distances.Source: §A.4 · p. 24, G DiagV (G)(Z)BG · p. 25

A.5 Induction on root distance

  • Strong induction on root distance constructs and transports every profile cell, including empty cells, using edge pairs that identify a unique endpoint pair at the current distance.A geodesic supplies a witness edge pair for each root pair at that distance.Source: §A.5 · pp. 25–27

A.6 Completion of the proof

  • The nonempty profile cells form a basis of the line-derived matrix space, making it Hadamard closed and supporting a correspondence with the stable root algebras.The proof establishes the required algebra inclusions and verifies a bijection between stable root-color relations.Source: §A.6 · p. 27

A.7 Componentwise extension to disconnected roots

Stable 3-WL equivalence of line graphs induces a componentwise matching that yields 3-WL equivalence of Whitney-general roots without isolated vertices. The section also characterizes a four-clique count through common line neighbors of disjoint edges.

A.7 Componentwise extension to disconnected roots

  • Stable 3-WL equivalence matches components of the graphs bijectively, and any such componentwise 3-WL equivalence implies equivalence of the whole graphs.The component matching is characterized in both directions.Source: §A.7 · p. 28
  • The backward containment extends to disconnected roots without isolated vertices when every component is Whitney-general.Stable 3-WL equivalence of their line graphs gives root-component matches, and componentwise 3-WL equivalence yields equivalence of the roots.Source: §A.7 · p. 28

B.1 Universal four-clique count

  • A pair of disjoint root edges has four common line neighbors exactly when their four endpoints induce a K4.Each K4 contributes six ordered pairs of opposite edges, and their endpoint union identifies the clique uniquely.Source: §B.1 · p. 28

B.2 Exact witnesses for comparison with root 4-WL

The witnesses show that root 4-WL and ILG-3-WL are incomparable, even on connected Whitney-general simple graphs. The accompanying Lean development formalizes the paper’s main refinement and neural-expressivity results.

B.2 Exact witnesses for comparison with root 4-WL

  • Root 4-WL separates the STS(13) incidence pair, while ILG-3-WL reaches equal stable signatures.The traces are 14 → 67 → 101 for root 4-WL and 3 → 5 → 7 → 7 for ILG-3-WL.Source: §B.2 · p. 29
  • ILG-3-WL separates the K5 compressed parity pair, while root 4-WL reaches equal stable signatures.The traces are 15 → 43 → 43 for root 4-WL and 3 → 8 → 46 for ILG-3-WL.Source: §B.2 · p. 29, Figure 4 · p. 30

C Machine Verification

  • The Lean 4 development formalizes the backward-transfer theorems, the Shrikhande–rook separation, and global-edge ILG-GNN expressivity bounds.It covers the k = 3 arity-shift instance used by the backward theorems; the general arity shift and cited k = 2 consequence are taken from the literature.Source: C Machine Verification · p. 30
  • Lean checks all modules containing the stated theorems, with no sorry, admit, or custom axiom declarations.A separate Lean file records the axioms used by the main results.Source: C Machine Verification · p. 30

D Proofs of ILG Equivalence and Expressivity Results

The appendix proves equivalences between edge-domain ILG procedures and line-graph refinement, analyzes first-order transfer and its limits, and specifies conditions for neural simulation and implementation. It also establishes permutation-invariant readouts under root-edge bijections and compares storage and per-round costs of root- and line-domain formulations.

D.1 ILG-1-GNN Equals MPNN on L(G)

  • Edge-only ILG-1-GNN and MPNN on L(G) have identical layerwise states and invariant readouts, up to ordering.The proof establishes layerwise equality by induction and extends it to order-invariant graph readouts.Source: §D.1 · p. 31

D.2 Atomic Types on the Line Graph

  • Line-graph tuple atomic types can be computed from root-edge endpoints, and for k = 2 the relation code distinguishes equality, adjacency, and non-adjacency.The code is determined by whether the edges are equal, share an endpoint, or are disjoint.Source: §D.2 · p. 32

D.3 Forward Transfer: 1-WL Equivalence Implies Line-Graph 1-WL Equivalence

  • If G and H are 1-WL equivalent, then L(G) and L(H) are also 1-WL equivalent.The proof transfers matched stable root-color classes and quotient numbers to equitable line-graph colorings.Source: §D.3 · p. 32

D.4 Equal-Order Failure of First-Order Backward Transfer

  • The equal-order example shows that line-graph 1-WL equivalence does not imply root 1-WL equivalence, despite matching stable color-class sizes and quotients.The line-graph partition has stable cells of sizes 2, 4, and 4.Source: §D.4 · p. 32

D.5 Equivalence of ILG-k-WL and k-WL on L(G)

  • ILG-k-WL and k-WL on L(G) produce the same graph-level distinctions for every k.Their tuple domains, initialization, and updates agree at every round.Source: §D.5 · p. 33

D.6 Equivalence of Global-Edge ILG-k-WL and k-WL on L(G)

  • For the pair-state process, global-edge replacement has the same stable graph-distinguishing power as the separate-coordinate 3-WL convention; for k = 2, adding rG(g, e) restores exactly 1-WL power.Without the relation code, the one-edge-state message contains no relation between g and the current edge and fails on P4 versus K1,3.Source: §D.6 · p. 33

D.7 Neural Simulation of the Tuple Refinement

  • On bounded-edge graph classes with a finite edge-feature alphabet, an ILG-3-GNN can simulate feature-labeled tuple refinement, whose indistinguishability forces identical network readouts.The construction uses injective encodings and bounded-size multiset aggregation.Source: §D.7 · pp. 34–35

D.8 Algorithmic Specification

  • The global-edge forward pass accesses endpoint relation codes on demand without constructing L(G); relabelings preserve those codes and intrinsically defined edge features.The endpoint table uses O(m) time and space, and each relation comparison takes O(1).Source: §D.8 · p. 35, §D.9 · p. 36

D.9 Permutation Equivariance and Invariance

  • A bijection between root edge sets preserves the multisets used by the graph readout, yielding equal invariant readouts.The readout sums over ordered edge pairs and edges; edge features are likewise preserved.Source: §D.9 · p. 37

D.10 Complexity Details

  • Direct ILG-k-WL stores k-tuples, while global-edge ILG-k-WL stores (k−1)-tuples; the latter matches explicit (k−1)-FWL on L(G) in per-round complexity.Global-edge ILG computes line-graph adjacency from root-edge endpoints rather than storing it; at k = 3, both formulations use O(m^2) total worst-case space.Source: §D.10 · p. 37
  • The deterministic refinement runner uses 128-bit digests for canonical signatures, so collisions are possible but highly unlikely.Discrete signatures are streamed one target tuple at a time, while the neural implementation uses target-tuple chunks of size C.Source: §D.10 · p. 37

E Empirical Cost and Scaling

The cost experiments compare explicit and implicit line-domain refinement with root-domain WL, examining scaling, structural storage, and stabilized SR25 costs. Endpoint-derived relations avoid storing the line graph, but the dense k = 3 tuple-state and replacement work remains.

E Empirical Cost and Scaling

  • Explicit and implicit line-domain refinement use the same dense pair-refinement implementation and return equal final signatures on every measured call.The explicit method retains E(L(G)); the implicit method derives the atomic relation from root-edge endpoints.Source: E Empirical Cost and Scaling · p. 37
  • The fixed-n sweep varies m across connected 25-vertex regular roots, while holding root-domain state and replacement counts fixed.It uses three fixed seeds per degree and times atomic initialization plus one complete refinement round; explicit line-graph construction is included.Source: E Empirical Cost and Scaling · pp. 37–38
  • 2.60: explicit line refinement and implicit ILG each have a log(time)-versus-log m slope of 2.60 for the six points with m ≥75.The measured regime is finite-range; the benchmark separately records exactly m^3 replacement entries per round, and line-domain runtime crosses root 4-WL between m = 100 and m = 150.Source: Table 3 · p. 38, E Empirical Cost and Scaling · p. 38
  • 0.409 ms and 0.130 MiB: endpoint preparation on the star contrasts with 454.7 ms and 59.0 MiB for explicit materialization.With pair refinement included at m = 150, implicit times are 1.38–1.46 s and explicit times are 1.41–1.76 s despite a 75-fold range in mL; the m^2 states and m^3 replacements dominate.Source: Table 4 · p. 38, E Empirical Cost and Scaling · pp. 38–39
  • 4.78 times slower: stabilized implicit ILG-3-WL takes 4.78 times the root 4-WL time on SR25, while both separate all 105 pairs.Implicit ILG uses 1.09 times the peak RSS; the cost comparison does not order expressivity, and the methods are incomparable.Source: E Empirical Cost and Scaling · p. 39, Table 5 · p. 39

F Neural Evaluation Protocols

This section specifies pair-trained neural baselines and an untrained ILG-3-GNN evaluation protocol, then reports their separation counts and controls.

F Neural Evaluation Protocols

  • Pair-trained baselines use a separate model for each graph pair and seed, with 32 relabeled copies and a BREC-threshold separation rule.For controls, substructure-counting pairs, SR25, and ILG-1-GNN BREC, at least two of seeds 0, 1, and 2 must pass both checks.Source: F Neural Evaluation Protocols · p. 39
  • None of the reported ILG-1-GNN pairs is separated, consistent with its upper bound by 1-WL on the line graph.Under the canonical edge/line-vertex identification, ILG-1-GNN is an MPNN on L(G).Source: F Neural Evaluation Protocols · p. 39
  • 207/400 BREC pairs are separated by Morris 3-GNN using the seed with the most separations.Pairs from different seeds are not combined, and the count is not reported as equality with a computed pairwise set-3-WL bound.Source: F Neural Evaluation Protocols · p. 39
  • 233/400 BREC pairs are separated by the PPGN result sourced from Wang and Zhang [25, Table 2].The SR25 and substructure-counting witness-pair cells are computed locally under the pair-trained protocol.Source: F Neural Evaluation Protocols · p. 40
  • The untrained ILG-3-GNN uses fixed parameters, dense ordered root-edge-pair states, and no parameter updates across the evaluations.Its fixed architecture and seed are reused; exact-color state compression, when used, preserves the same recurrence and supplies no features or readout coordinates.Source: F Neural Evaluation Protocols · pp. 39–40
  • ILG-3-GNN separation uses a direct-ℓ2 floor tied to the BREC covariance ridge and threshold, not the BREC RPC statistic.All four copies must support a reported separation; two copies may reject early, while nonfinite values and execution errors count as failures.Source: F Neural Evaluation Protocols · p. 40
  • 3/3 substructure-counting pairs, 105/105 SR25 pairs, and 359/400 BREC pairs are separated by untrained ILG-3-GNN, matching deterministic ILG-3-WL pairwise verdicts.The protocol does not separate the isomorphic C6 control or the Whitney pair K3, K1,3.Source: F Neural Evaluation Protocols · p. 40

GenAI Usage Statement

  • Generative AI assisted with related-work surveying, proof development, Lean 4 formalization, empirical-complexity evaluation, language editing, and code assistance.The author chose the research direction and proof strategy, reviewed AI-assisted material, and states responsibility for the paper and artifact.Source: GenAI Usage Statement · p. 40

Related papers

Loading 2609.16412v1…