- 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
-
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.
-
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.
-
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.
-
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
-
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.
-
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.
-
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.
-
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.
-
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
-
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?
-
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?
-
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.
-
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?
-
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
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!
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) 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=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 k and over r until each hard pair is separated, counting failed attempts. Raising k 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 r is never stronger than (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 k, 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.