acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, Weisfeiler-Leman hierarchy, iterated line graphs, graph isomorphism, GNN expressivity, line graph transformations

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.25 over 4 reviews, above 96% of the others.
Reviewer_uXR3OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how iterated line graph transformations can increase the expressive power of the Weisfeiler-Leman (WL) test and higher-order graph neural networks. The authors prove that every pair of non-isomorphic finite simple graphs can be distinguished by 3-WL at some finite line graph transformation depth. They further establish a strict expressivity hierarchy with increasing transformation depth, while showing that no fixed depth is sufficient for all graphs. Based on these theoretical results, the authors propose a general adapter for 3-WL-equivalent GNNs that combines representations of the original and final iterated line graphs, and extend the implicit line graph neural network (ILG-3-GNN) to multiple transformation depths. Experiments on BREC show that iterated line graph transformations improve graph-pair discrimination, with PPGN++ and the native ILG model matching exact 3-WL separation on 399 of 400 pairs through depth three. The paper also examines computational costs, showing that shallow transformations can be more efficient than higher-dimensional WL refinement for certain sparse graph families, while deeper transformations may introduce substantial computational overhead.

Critical strengths
  1. Originality and theoretical contribution. The paper addresses an interesting question about whether graph transformations can increase expressive power without increasing the WL dimension or fundamentally changing the underlying GNN architecture. The main theoretical result, showing that 3-WL can eventually distinguish every pair of non-isomorphic finite simple graphs through iterated line transformations, is potentially significant. The strict depth hierarchy and the proof that no fixed transformation depth is universally sufficient provide a useful characterization of the relationship between transformation depth and graph expressivity.

  2. Connection between graph theory and GNN expressivity. An important strength is the connection between classical graph-theoretic results, WL refinement, counting logic, and graph representation learning. The treatment of exceptional cases, including the Whitney triangle–claw ambiguity and the disappearance of path components, is particularly useful. The result showing that the original and final graph signatures are sufficient to preserve the distinguishing power of intermediate depths is also an interesting contribution, since it provides a more compact formulation for the proposed adapter.

  3. Practical adaptation of existing higher-order GNNs. The proposed adapter can be applied to existing 3-WL-equivalent model families without changing their underlying update rules. The evaluation with PPGN++, G$^2$N$^2$, and the extended ILG model provides evidence that the theoretical gains from line graph transformations can also appear in finite neural architectures. I particularly appreciate the comparison between exact WL refinement and neural graph-pair separation, since this helps distinguish the theoretical expressivity of the model family from what a finite implementation actually achieves.

  4. Clear theoretical organization and experimental analysis. The paper is generally well organized, with the theoretical results presented before the model construction and experiments. The appendix contains detailed proofs, supporting lemmas, numerical ablations, and computational analysis. The authors also acknowledge important limitations, including the absence of a universal fixed depth, numerical instability in finite models, and the rapid growth of iterated line graphs. The computational experiments considering graph size, density, and degree variation provide useful context for understanding when the proposed transformation may be practical.

Critical weaknesses
  1. Universal expressivity does not necessarily translate into practical graph identification (Sections 3.2-3.4; Appendix E.3). The central theorem guarantees that every non-isomorphic graph pair can be distinguished at some finite transformation depth, but it does not provide a generally practical bound on the required depth. In fact, the paper establishes that no fixed depth is sufficient and that certain CFI graph families may require depths growing with graph size, leading to extremely large iterated graphs. Therefore, the theoretical universality may be difficult to exploit computationally, especially for graph families requiring deeper transformations. A clearer characterization of the depth needed for meaningful graph classes would strengthen the practical implications of the result.

  2. The theoretical guarantee for GNN families is stronger than what is established for finite neural models (Sections 4-5). The adapter's expressivity guarantee relies on a 3-WL-equivalent model family with suitable parameters, width, and number of layers. However, this does not guarantee that a particular finite GNN can realize the required separation at increasing line depths. The BREC experiments use fixed-width, five-layer models, and G$^2$N$^2$ fails to distinguish 15 pairs that exact 3-WL separates at depth three, with substantial variation across relabeled inputs. This raises questions about the numerical stability and representational capacity required to translate the theoretical results into reliable neural implementations. More systematic experiments varying model width, depth, and initialization would strengthen this connection.

  3. Experimental validation is limited to BREC graph identification (Section 5; Appendix D). Although the paper provides extensive theoretical results, the neural experiments are restricted to graph-pair discrimination on BREC. This benchmark is useful for evaluating expressivity, but it does not establish whether iterated line graph transformations improve predictive performance or generalization on graph learning tasks. Moreover, the most challenging depth-three neural experiments use only one random seed, and the final depth-six pair is certified theoretically rather than evaluated using a neural model. Experiments on additional challenging graph families and graph-level prediction tasks would help demonstrate the broader usefulness of the approach.

  4. Computational comparisons do not fully characterize the cost of graph identification (Section 6; Appendix E). The computational experiments compare time and memory for individual WL refinement rounds, whereas graph identification requires constructing the relevant line graphs and potentially performing several refinement rounds until stabilization. For a pair whose separating depth is unknown, intermediate transformations and refinement costs may also be unavoidable. Although Appendix E.2 discusses total refinement complexity, the empirical comparison focuses mainly on individual rounds. An end-to-end evaluation measuring graph transformation, refinement until convergence, and total identification time would provide a more realistic comparison against higher-dimensional WL methods.

  5. Limited applicability to attributed graph learning (Section 7). The theoretical analysis focuses on finite uncolored simple graphs and graph-level identification. However, many practical graph learning problems involve node features, edge attributes, and predictions associated with the original graph. Iterated line graph transformations change the entities represented by vertices and edges, making feature propagation and prediction mapping less straightforward. Although the authors acknowledge this limitation, the absence of an attributed-graph formulation restricts the immediate applicability of the proposed adapter. A concrete feature-mapping strategy or a preliminary experiment on attributed graphs would help establish its relevance to practical GNN tasks.

Questions for authors
  1. Practical transformation depth and graph size (Sections 3.2-3.4; Appendix E.3). The universal graph identification theorem (Theorem 2) guarantees a finite separating depth for every non-isomorphic pair, but this depth may grow substantially with graph size. Is it possible to derive more informative upper bounds for relevant graph families, such as bounded-degree, bounded-tree-width, or sparse graphs? Could the authors also discuss whether the required transformation depth can be predicted or estimated from structural properties of the input graphs?

  2. Realizing theoretical expressivity with finite GNNs (Sections 4-5; Appendix D). The theoretical expressivity guarantee applies to a 3-WL-equivalent model family rather than a particular network with fixed width and depth. What conditions on neural width, number of layers, parameterization, or numerical precision are needed to achieve the additional separations at larger line depths? In particular, can the depth-three failures of G$^2$N$^2$ be resolved by increasing network capacity or modifying numerical settings?

  3. Generalization beyond BREC (Section 5). The neural experiments focus entirely on BREC, with each remaining pair evaluated at the first depth where exact 3-WL distinguishes it. Could the authors test the approach on additional challenging graph families or graph-level prediction tasks? It would be especially useful to know whether the improvements persist when the transformation depth is selected without knowledge of the exact separating depth of each evaluation pair.

  4. End-to-end computational efficiency (Section 6; Appendix E.2). The runtime comparisons are mainly based on individual refinement rounds. Could the authors report the total cost required to distinguish graph pairs, including line graph construction, refinement until stabilization, and any intermediate transformations? How does the overall cost compare with higher-dimensional WL methods when both are evaluated until separation or stabilization?

  5. Transformation depth vs. WL dimension (Section 6; Appendix E.1). The paper establishes that increasing line depth can provide additional expressivity without changing the WL dimension. However, the relative advantage over directly increasing WL dimension remains unclear for general graph families. Can the authors characterize the minimum line depth and minimum WL dimension required to distinguish representative graph pairs, together with their computational costs? This would help explain when iterated line transformation provides a more efficient route to stronger expressivity.

3 comments

Thank you for the detailed review and for recognizing the theoretical contribution. Your five questions cover the five weaknesses, so we answer them in order.

Q1. Depth and graph size. We agree that Theorem 2 only shows existence. Theorem 4 rules out a fixed depth that works for all graphs, and bounded degree does not help: the hard pairs are 3-regular, and for some CFI families the depth grows linearly with the number of vertices (Proposition 52). For bounded treewidth, depth zero is enough for treewidth at most two (Kiefer & Neuen, 2022). On BREC, the strongly regular and distance-regular pairs need depth one or two, and the hard CFI pairs three or six. Section 7 of the revision now lists these depths. Bounds for further graph classes, and predicting the depth from structural properties, might belong to future work.

Q2. Finite networks. Corollary 5 concerns a model family, and a fixed network can do less. In our paper, BREC mainly serves to show that the theoretical limit can be realized by 3-WL-equivalent models, rather than to test how well they learn. It can be realized: PPGN++ goes from 270 to 399 pairs, native ILG from 359 to 399 and G$^2$N$^2$ from 270 to 384. We chose sin⁡(5x)\sin(5x) and FP64 on purpose to favor separation. The 15 G$^2$N$^2$ misses come from numerical spread between relabeled copies. Which width and precision would remove them remains open (Section 7).

Q3. Beyond BREC. The gains do not depend on knowing the separating depth. At the fixed depth r=1r=1, on the final graph only, all three networks separate the 359 pairs that exact 3-WL separates there. Beyond BREC, one line step separates all 105 pairs of SR25 (Yang, 2026). Pair 354 needs depth six, which is too large for a network, so we certify it exactly (Appendix D.6). We do not add prediction tasks. This work focuses on the theoretical understanding of iterated line graphs and on the upper limit of their expressivity, and most benchmark graphs are already separated by 1-WL (Zopf, 2022, "1-WL Expressiveness Is (Almost) All You Need"), so accuracy there would not test our theorems. For attributed graphs, one mapping gives each line vertex the attribute of its edge and the pair of its endpoint labels. Extending the theorems to attributed graphs is future work.

Q4. End-to-end cost. We added two measurements that include line-graph construction (Section 6, Appendices E.5 and E.6). First, we refined the grid of Figure 4 until stable. Every test stabilizes within three to five rounds, one line step is faster than 4-WL in all 24 settings (1.7 to 15.5 times), and two steps only at mean degree two or, for regular graphs, three. Second, we searched over kk and over rr until each hard pair is separated, counting failed attempts. Raising kk is cheaper on the CFI pairs and on the dense regular families, by a median of 9 times on strongly regular and 77 times on four-vertex-condition pairs. One line step is 4 times cheaper on a pair that needs 5-WL.

Q5. Depth versus WL dimension. In our work, we show that depth rr is never stronger than (3r+3)(3r+3)-WL on the original graphs. We have not shown that this is the least dimension, and we have no bound on the depth in terms of kk, so we do not claim that line depth is the more efficient route in general. The two target different hard pairs. One line step separates every strongly regular pair we tested, while the hard CFI pairs of BREC need three or six steps and are reached sooner by raising the dimension. Table 6 gives the minimum dimension, the minimum depth and the time to separation for representative pairs.

We appreciate your detailed review. If this reply resolves your concerns, we would kindly ask you to consider raising your rating. We are happy to answer any further questions.

I thank the authors for their detailed rebuttal and clarifications. Most of my concerns have been adequately addressed, and I appreciate the additional explanations and experimental evidence. I am therefore inclined to increase my score.

Thanks for the recommendation for acceptance!

Reviewer_RzcMOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The article is concerned with the expressive power of 3-WL on repeated line graphs. The main results shows that any two non isomorphic graphs can be distinguished by 3-Wl with a finite number of repeated line graph transformations. Furthermore they show (i) that every additional transformation separates previously indistinguishable graph pairs, (ii) that the first and last transformation depths suffice, and (iii) that there exists no constant number of such transformations which can distinguish all graphs. The authors utilise this result by plugging the line graphs into 3-Wl powerful GNN models and test them on BREC. The experimental results are consistent with their theory showing that PPGN++ indeed distinguishes all pairs that can be distinguished with 3-WL up to 3 line graph transformations.

Critical strengths

The proposed results are elegant and non-trivial. I found it quite original and refreshing to see WL work that does not follow the usual path of trying to push k in k-WL to increase expressivity, but instead considers a whole new axis. This sheds some new light on WL expressivity, showing that a fixed dimension can already suffice.

The paper is carefully written and easy to follow. Even though the theory under the hood is quite heavy, the authors do a good job at presenting their work. I have, however, not checked all results in detail.

Critical weaknesses

A weakness I can see is that the paper contains very little learning. The experimental section is based on untrained models, which however suffice for the point being made, but it remains open whether the results have any ML implications. Some experiments in this direction would be nice, though I can see how it is out of scope.

The results of this paper are mostly of theoretical interest, since the line graphs can get so large that increasing k in k-Wl seems to be cheaper. I don’t see this as a major issue for a theory-focused contribution, though.

Questions for authors
  • Do the results also hold for colored/attributed graphs?
  • As the size of the iterated line graphs grow rapidly with r, did the authors consider some reduction step, possibly a heuristic that at least works in practice?
3 comments

Thank you for the careful reading. We are glad that the line graph axis came across, and we are genuinely excited to share these results in this work.

We agree with both of your remarks. The contribution is mainly theoretical, and whether the new separations matter for learning is beyond this paper. Deep line graphs can also cost more than raising kk. We have added new cost results (Section 6, Appendices E.5 and E.6) that make this concrete: one line step is cheaper than 4-WL on sparse graphs, and raising kk is cheaper on dense graphs and on CFI pairs.

Colored and attributed graphs. These are beyond the scope of this work. Attributes can be carried to the line graph, for example by giving each line vertex the attribute of its edge and the pair of its endpoint labels. But our theorems are proved for uncolored graphs. Backward transfer for colored graphs is a natural direction for future work.

Reduction. The growth is real, however we currently do not have a general and effective remedy. We attempted three exact savings.

  • By Theorem 3 only the original and the final graph are encoded, so intermediate depths are never refined.
  • We adopt the implicit setting of Yang (2026) and generalize it to arbitrary depth rr: the adjacency of the final line graph is read from shared endpoints without being stored.
  • At depth three we store one feature for all pairs that are equal under the automorphisms of the graph. This needs 6 to 79 times fewer features on the CFI pairs we evaluate (Appendix C.3).

The third saving needs symmetry and does not really help on graphs with few automorphisms. Heuristics such as sampling line vertices may work in practice, but they give up the identification guarantee, so we did not pursue them here.

Thank you very much for addressing my points. I continue to support acceptance.

Thank you!

Reviewer_ccDDOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies 3-Weisfeiler–Leman test (that quantify expressive power of GNNs) under line graph transformation. More specifically, it proves that non-isomorphic graphs are distinguished by 3-WL under finite transformation depth. Leveraging this result they propose a universal line adapter to extend equivalent representation learning frameworks to iterated line graphs. Studies reveal that compared to 4-WL on the true graphs, shallow transformations reduces the memory and time complexities.

Critical strengths

Strengths:

1: Theoretical findings supporting that 3-WL distinguishes every pair of non-isomorphic graphs under line graph transformations.

2:Universal line adapter to transform for appying 3-wl families.

3: Study on memory and time complexities

Critical weaknesses

Weakness

W1: What is the formal expressivity relationship with simplicial or clique lifted equivalent variants?

W2: Which results demonstrate an advantage beyond what SWL (Simplicial Weisfeiler Leman) already captures?

W3:How is the partial tuple construction transported without choosing named vertices?

W4:Why does the counting-logic interpretation preserve the stated variable budget?

Questions on experiments.

1: Can you identify a prediction task where the additional distinctions improve performance? Specifically, when should a practitioner prefer line-graph transformation over increasing model order, and how should transformation depth be selected without access to exact WL separation results?

2: The larger experiments rely on symmetry-based compression. How well does the approach scale on graphs with less symmetry, and what fraction of the reported efficiency depends on compression?

3: Evaluate scalability on larger CFI graph pairs and demonstrate supervised generalization on held-out hard graph families using a shared encoder? Report performance across transformation depths together with total preprocessing, training/inference time, peak memory, and compression overhead, comparing against root 3-WL-equivalent models and SWL. An attributed graph-prediction benchmark would additionally help establish practical relevance, provided the attribute-lifting procedure is specified.

Questions for authors

Please refer weakness

3 comments

Thank you for the review and the detailed questions. Sorry for the deleted comment. It was due to an organisation error of the comments.

Here we answer them in the following:

W1. Neither method contains the other at a fixed depth, and in the limit line depth contains SWL by Theorem 2. On a triangle-free graph the clique complex is the graph itself, so SWL separates exactly the pairs that 1-WL separates (Proposition 53). In the other direction, SWL counts cliques of every size, which no fixed WL dimension can do (Neuen, 2024). Since depth rr is bounded by (3r+3)(3r+3)-WL on the original graphs, every fixed depth misses some pair that SWL separates. The revision adds this comparison (Section 1, Appendix E.7).

W2. By Proposition 53, SWL misses the CFI pairs of BREC and the 3-regular hard pairs of Theorem 4, which are all separated at a finite depth. On BREC, exact SWL separates 238 pairs, all among the 359 separated with one line step. It separates none of the 100 CFI pairs, and line depth separates 99 of them by depth three (Appendix E.7).

W3. The construction never names a vertex. It works with matrix expressions in II, JJ and the adjacency matrix of an iterate, and 3-WL equivalence carries each expression from GG to HH. Adding an entry to the tuple uses only the distance δ\delta between two representatives, and "all pairs at distance δ\delta" is again such an expression (Lemma 30). The prescribed tuple only selects these distances and, at the end, shows that a diagonal expression FGF_G is nonzero. Then FHF_H is nonzero too, and any nonzero entry gives an isomorphism (Lemma 32).

W4. A vertex of Lr(G)L^r(G) is coded by one of finitely many tree shapes and r+1r+1 vertices of GG (Lemma 41), so qq variables become q(r+1)q(r+1). The formulas for valid, equal and adjacent codes are quantifier-free, and the shapes are handled by tagging (Lemma 42). A vertex can have several codes, so counting vertices means counting classes of a definable equivalence, which the interpretation theorem allows within the same budget (Otto, 1997). The revision adds this explanation to Appendix B.10.

Q1. This work focuses on the theoretical understanding of iterated line graphs and on the upper limit of their expressivity, so we do not have a prediction task where the new distinctions help. Most benchmark graphs are already separated by 1-WL (Zopf, 2022, "1-WL Expressiveness Is (Almost) All You Need"), so accuracy there would not test our theorems.

Current results suggest that the line-graph transformation is particularly useful for 3-WL on strongly regular graphs. 3-WL separates none of the 105 pairs of SR25 and none of the 50 strongly regular pairs of BREC, and one line step separates all of them (Yang, 2026). In BREC, one line step also separates the 20 four-vertex-condition pairs and 19 of the 20 distance-regular pairs. A practitioner who uses a 3-WL-equivalent model can keep it and add one line step when the graphs have such highly regular structure.

For the depth, we would recommend choosing by the available computational resources. This work shows a strict hierarchy of expressive power in depth (Theorem 1), and with the original graph retained a larger depth never loses a separation (Corollary 5). At the fixed depth r=1r=1, without any exact WL result, all three networks separate 359 pairs. The depth that gives the best learning result will also depend on the training configuration, which we do not study here.

Q2. Compression is not part of the method. We use it only at depth three due to computational constraints and the symmetry of CFI graphs. On 39 CFI pairs whose line graphs have up to 109,156 vertices, it stores 6 to 79 times fewer features without changing the output (Section 5, Appendix C.3). The exact WL results and the cost comparisons with 4-WL use no compression. Graphs with few symmetries are not compressed. Strongly regular graphs can have trivial automorphism groups, and we ran them densely at depth one.

Q3. Neural evaluation will not scale to larger CFI families: the first separating depth can grow linearly, and the line graph at that depth has 2Ω(n2)2^{\Omega(n^2)} vertices (Proposition 52). Time and memory per depth are now in Table 4, including the same networks on the original graphs. Table 7 gives the pairs separated by SWL (238) and by 3-WL on the original graphs (270).

In this paper, we do not add supervised or attributed benchmarks, for the reason under Q1: BREC serves here to show that the theoretical limit can be realized by 3-WL-equivalent models, not to measure learning. Extending the theorems to attributed graphs is future work.

We appreciate your careful review. If this reply resolves your concerns, we would kindly ask you to consider raising your rating. We are happy to answer any further questions.

Dear Authors,

Thank you for the detailed response. I am convinced by the arguments on SWL. As a suggestion, I would encourage you to add a future directions section discussing potential dataset curation or downstream tasks where the approach would be most beneficial. I have increased my score and will support acceptance.

Thanks again for the review and recommendation for acceptance! We agree that highly expressive models, even beyond the proposed ILG-3-GNN, might benefit from a hard yet practical dataset. We would be sharing our discussion and insights on this as future direction on this work.

Reviewer_WmkqOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies how the iterated line graph transformation Lr(G)L^r(G) interacts with the Weisfeiler–Leman hierarchy, using the oblivious convention, so that 3−WL≡2−FWL3-WL ≡ 2-FWL. Building on the one-step results of Yang (2026), it makes four theoretical claims:

  • Theorem 1 (strict hierarchy): For every r≥1r ≥ 1, the stable 3-WL signature at depth r+1r+1 strictly refines the one at depth r on connected non-path graphs. This also holds at r=0r = 0 if the claw is excluded, and remains strict on connected regular graphs of degree ≥3≥ 3. On all finite simple graphs, the cumulative signature satisfies S≤r≺S≤r+1S_{≤r} ≺ S_{≤r+1}.
  • Theorem 2 (universal identification): For every pair of non-isomorphic finite simple graphs, 3-WL separates Lr(G)L^r(G) and Lr(H)L^r(H) at some finite depth rr.
  • Theorem 3 (first and last depths suffice): The signatures at depths 0 and rr, or equivalently the counts of claw and path components plus the depth-r signature, determine all intermediate signatures.
  • Theorem 4 (no fixed depth suffices): No fixed depth separates all pairs, even among connected 3-regular graphs. The proof combines a counting-logic translation with uncolored 3-regular CFI graphs.

From these, the paper defines a backbone-agnostic "line graph adapter": f(G)⊕f(Lr(G))f(G) ⊕ f(L^r(G)) for general graphs, or f(Lr(G))⊕∣V(G)∣f(L^r(G)) ⊕ |V(G)| for connected graphs. Corollary 5 states that the adapter has exactly the S≤rS_{≤r} expressivity for any 3-WL-equivalent family. The paper also extends ILG-k-GNN to arbitrary depth and tests k=3k = 3.

Empirically, exact or certified 3-WL on BREC separates 270, 359, 360 and 399 pairs cumulatively at depths 0–3, and all 400 at depth 6. Untrained PPGN++ and G$^2$N$^2$ networks are first run on all 400 root pairs, and native ILG on all 400 pairs at depth 1. Every remaining pair is then evaluated only at its first exact separating depth, using the output on Lr(G)L^r(G) alone. PPGN++ and native ILG reach 399; G$^2$N$^2$ reaches 384. In addition, Section 6 compares the per-round cost of ILG-3-WL and ILG²-3-WL with root 4-WL on synthetic graphs with n≤64n ≤ 64. It expresses n2n_2 through the mean and variance of the degrees and finds that shallow transformation gains most on sparse graphs with similar degrees.

Critical strengths

[S1] Clean, precisely stated theory with a non-obvious positive result. Theorem 2 shows that a fixed-dimension test (3-WL) combined with a deterministic, isomorphism-invariant transformation separates every non-isomorphic pair at some finite, pair-dependent depth. Theorem 4 shows that this cannot be achieved uniformly. All expressivity statements are made against a precise reference: Section 2 fixes the oblivious k-WL convention, the 2-FWL implementation in Eq. (1), and the relations ⪯⪯ and ≺≺ on signatures. Section 2 also separates family-level from model-level separation ("It need not be separated by every such model"), which keeps the GNN claims honest. The paper explains why 1-WL cannot benefit, using the triangular prism vs. K3,3K_{3,3} at every depth (Section 3.1). The counting-logic argument also places the line-depth hierarchy inside the WL hierarchy (S≤r⪯(3r+2)−FWL(S_{≤r} ⪯ (3r+2)-FWL, Section 6). [S2] Theorem 3 is a useful structural result. It reduces the "keep every intermediate depth" construction to two model evaluations. Together with Eq. (3) and Corollary 5, it reduces to one evaluation plus ∣V(G)∣|V(G)| on connected graphs. The edge cases are handled carefully: the Whitney pair, paths becoming empty, and the P2/P3P_2/P_3 example in Section 3.3 showing that dropping isolated vertices does not help.

Critical weaknesses

[W1] The positioning within GNN expressivity research is thin, and key premises come from recent preprints.

  • Issue: The main text attributes each imported ingredient inline. ILG-k-WL and ILG-k-GNN come from Yang (2026), a recent preprint. So do one-step backward transfer (stated with its conditions at the start of Section 3.1 and used as "Theorem 9" in the proof of Theorem 1), one-step strictness (Shrikhande vs. 4×4 rook), preservation of 1-WL indistinguishability, and the incomparability of ILG-3-WL with root 4-WL. The loss of strong regularity comes from Yang & Huang (2026). The Contributions list in Section 1 identifies the new results. However, there is no related-work section in the main text, and the ML positioning is thin: 7 of the 23 references are ML-venue papers. Two further points affect how the delta should be read:
    • Theorem 1's containment comes from backward transfer, and its strictness from Theorems 2 and 4. The new technical weight therefore sits in Theorems 2–4.
    • Two premises are arXiv preprints. Backward transfer (Yang, 2026), or a generalization of it, underlies Theorem 1, the converse direction of Theorem 3 and Corollary 5. The uncolored CFI result (Chen et al., 2025) underlies Theorem 4.
  • Why it matters: Readers need to know how much of the proof machinery is new, and whether the submission is self-contained while its key premises are not yet peer reviewed. ML readers also cannot place the work among other transformations that raise expressivity, or among other routes to universality.

[W2] The neural experiments test networks at oracle-chosen depths, without training, rather than the proposed adapter at a fixed depth.

  • Issue: Each non-root pair is evaluated only at the first depth where exact 3-WL separates it. This is oracle information that a deployed model does not have. The adapters in Eqs. (2)–(3) are not evaluated; Section 5 says so explicitly. All networks are untrained and use sin(5x)sin(5x) activations in FP64. The depth-3 rows use a single seed. The paper is transparent about each of these choices, but together they mean the experiments support a narrower claim than the adapter's.
  • Why it matters
    1. A practical adapter uses one fixed r for all graphs. The statement "every model distinguishes more pairs after transformation" is cumulative over oracle depths, and, as the paper notes, persistence at greater depths is untested. Theorem 3 guarantees persistence at the family level when the root branch is retained. Finite-network behaviour is what the experiments are meant to probe, and G$^2$N$^2$'s relabeling spread at depth 3 shows it is not automatic.
    2. As I understand BREC (Wang & Zhang, 2024), it was designed to measure the realized expressiveness of trained models. The untrained experiment answers a different but still useful question: whether a fixed, small random network (width 16, five layers) realizes the family-level separation on large iterates. The family-level theorem does not guarantee this, as the G$^2$N$^2$ misses show. The experiment says nothing about learnability.
    3. Practitioners care whether models trained with standard activations and precision realize these gains. Section 5 points to activation and precision ablations in Appendix D.2, which I could not assess from the main text.
Questions for authors
  1. The Contributions list and inline citations make clear which statements are new. Which proof techniques in Theorems 2 and 3 are new relative to Yang (2026)? In particular, is the step used for Theorem 3, that the signature of L(G)L(G) determines that of GG once the numbers of isolated vertices and claw components are known, a new generalization or taken from Yang (2026)? Is "Theorem 9" the backward-transfer theorem of Yang (2026), and does the appendix give a self-contained proof of it? Which statements does the Lean formalization assume as "published premises"? Candidates include backward transfer, Whitney's theorem, Hartke & Higgins, Cai–Fürer–Immerman, and Chen et al. (2025). These points are not verifiable from the main text.
  2. What do zgenz^\text{gen} and zconz^\text{con} at fixed r=1r = 1 (and r=2r = 2) achieve on all 400 pairs? Do trained models in FP32 with a standard activation still separate the 89 depth-1 pairs? What do the activation and precision ablations in Appendix D.2 show?
  3. How are the "classes of vertex pairs whose features remain equal throughout the network" computed: from automorphism orbits, from an exact WL partition, or by another method? If an exact WL partition is used, is the neural evaluation independent of the exact test? If the compressed representation does not depend on vertex labels, do the 32 isomorphic relabeling controls still test numerical invariance? What does computing the classes cost, and which Table 1 rows relied on compression? Given Section 7's remark about less symmetric graphs, how would depth-2 or depth-3 evaluation scale to graphs with trivial automorphism groups? (Not verifiable from the main text.)
1 comment

Thank you for the careful review and thorough understanding of the paper’s theoretical construct. We hope this reply clarifies your concerns.

Q1. Theorem 2 is not only an iteration of the one-step result, which only says that a separation is never lost. It adds a new statement: at a sufficient depth, 3-WL recovers all vertices of GG and their adjacencies from the line graph, so equivalence there forces an isomorphism (Appendices B.3 to B.8).

The step behind Theorem 3 is a new generalization. Yang (2026) proves the one-step implication only for graphs without isolated vertices, triangle or claw components. Our Theorem 35 holds for all simple graphs: given L(G)≡L(H)L(G)\equiv L(H), we have G≡HG\equiv H exactly when the numbers of isolated vertices and of claw components agree.

Theorem 9 is the backward-transfer theorem of Yang (2026), which according to the first page of its arXiv version has been accepted at LoG 2026. Appendix B.2 states it without repeating the proof, which is machine-checked in our Lean supplement. In Lean, Theorem 2 assumes Whitney's theorem and the degree growth of Hartke and Higgins. Theorem 4 assumes the interpretation theorem for counting logic, its correspondence with 3-WL, and CFI hardness (Cai, Fürer and Immerman; Chen et al., 2025).

Chen et al. (2025) is still a preprint. We use it for one step: the original CFI graphs remain non-isomorphic and equally hard when their colors are forgotten, which keeps the hard pairs 3-regular and small. Without it, the classical gadget construction still gives uncolored hard pairs, so only the regular statements and the bound of Proposition 52 depend on it.

For the positioning within GNN expressivity research, Section 1 of the revision now relates the work to higher-order models, other universal models and simplicial lifts.

Q2. We agree that a fixed depth is worth testing, and we have run it. At r=1r=1, using only the output on L(G)L(G), exact 3-WL separates 359 of the 400 pairs. Native ILG separates the same 359 in all ten seeds. PPGN++ and G$^2$N$^2$ separate the same 359 and none of the other 41 (seed 100 for the 311 added pairs). All 270 root separations therefore persist at depth one, in networks that do not see the original graph.

The two graphs of a BREC pair have the same order, so zconz^{\mathrm{con}} separates the same 359 pairs, and zgenz^{\mathrm{gen}} at least these. For the exact test with the original graph retained, the fixed-depth counts at r=1,2,3r=1,2,3 are 359, 360 and 399.

We agree with your reading of BREC, which trains one network per pair. This work focuses on the theoretical understanding of iterated line graphs and on the upper limit of their expressivity. In our paper, BREC mainly serves to show that this theoretical limit can be realized by 3-WL-equivalent models, rather than to test whether they learn effectively in generic training settings. Line graphs let a network with only 3-WL expressivity separate pairs that 3-WL cannot separate on the original graphs. For this, one random network that passes the test and its control is enough, since it already shows that separating parameters exist.

We have not added a trained FP32 run on the 89 depth-one pairs, for the same reason: BREC serves here to show that the limit can be realized, not to measure learning in generic training settings. Appendix D.2 does train on the original graphs with BREC's procedure. With ReLU and FP32, the best seed reaches 234, 206 and 209 of the 270 separable pairs for PPGN, PPGN++ and G$^2$N$^2$. With sin⁡(5x)\sin(5x) and FP64 it reaches 267, 270 and 270. Standard numerics therefore already fall short of 3-WL on the original graphs.

Q3. Networks of this type store one feature for every pair of vertices, which does not fit in memory at depth three for the GPU we had. CFI graphs are highly symmetric, and two pairs of vertices that a symmetry maps to each other have the same feature in every layer, so we store one feature per group of such pairs. The groups come from the automorphisms of the graph, not from a WL coloring (now stated in Section 5 and Appendix C.3), so the network does not rely on the WL test. Exact 3-WL only chooses the depth. The output is the same as for the full network (Proposition 49), with 6 to 79 times fewer features.

The relabeling controls remain meaningful: each relabeled copy in the 32 tests and 32 controls is run separately, and G$^2$N$^2$ outputs on copies of one graph deviate from their mean by up to 3.0, so they are not identical by construction.

Only the depth-three row of Table 1 uses compression, and preparing the groups takes a median of 13 seconds per pair. Graphs without symmetries cannot be compressed in this way, and depth three would not fit for them (Section 7).

Thank you again for recommending weak acceptance. If our reply addresses your concerns, we would be grateful if you would consider further raising your rating.

Comments on the paper

1 comment

We thank all reviewers for the careful reviews and the constructive comments. We reply to each review in its own thread. Here we summarize the main points that were raised and how we responded. All changes in the revised paper are marked in blue, and the scripts and records of the new measurements are included in the supplementary material.

Experiments beyond BREC. Several reviewers asked for prediction tasks, trained networks or attributed graphs. This work focuses on the theoretical understanding of iterated line graphs and on the upper limit of their expressivity. We decided not to add prediction benchmarks, because the paper did not focus on discussion on iterated line graph's impact on learning, the performance on these tasks would not support or disprove the theoretical construct of this paper. Most benchmark graphs are already separated by 1-WL (Zopf, 2022, "1-WL Expressiveness Is (Almost) All You Need"), so 1-WL expressivity is sufficient there. In our paper, BREC mainly serves to show that the theoretical limit can be realized by 3-WL-equivalent models.

Computational cost. Reviewers asked how line depth compares with raising the WL dimension when the line graphs grow. We added measurements of refinement until the coloring is stable (Appendix E.5) and of the time to separate hard pairs by each route (Appendix E.6), with a summary in Section 6. We also report the time and memory of the neural evaluations (Appendix D.8). One line step is faster than 4-WL on the sparse graphs we tested, and raising the dimension is faster on dense regular graphs and on CFI pairs. We do not claim that either route is more efficient in general.

Additional analysis. We added a comparison with simplicial WL (Appendix E.7). It separates 238 BREC pairs, and all of them are also separated with one line step. Section 1 now relates the work to higher-order models, other universal models and simplicial lifts. Section 7 lists cases where the required depth is known. Appendix B.10 explains the variable budget of the counting-logic bound, and Section 5 and Appendix C.3 state where compression is used.

We hope the replies and the revision address your concerns. We are happy to answer any further questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.