{"id":"64ed0482-62fd-42e8-9cb7-2af6c432b3f6","arxiv_id":"2412.17468","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"An edge-filtration persistence diagram built on line graphs (TED/LGVR) is proven to retain node coloring information and beat the Weisfeiler-Lehman test in expressive power, with GNN variants showing benchmark gains.","lead":"Samsung SDS and POSTECH researchers propose a new way to encode graph structure for machine learning: instead of filtering nodes, they filter edges and use a line graph to compute a persistence diagram. They prove this representation keeps node information and can distinguish graphs that the Weisfeiler-Lehman test cannot, and they show gains on several graph benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"LGVR's edge filtration is not shown injective: Algorithm 1 trains all real-edge values to 0, so Theorem 13's premise is unverified; a trained-model injectivity check should decide.","rationale":"Good-faith reading: the ideal TED construction is mathematically plausible; Lemma 8/Theorem 9 hold if an injective edge filtration exists, and existence is trivial for stable WL coloring. The reader's verdict CONDITIONAL is reasonable. In stress-testing where the central claim actually breaks, I kept coming back to the same joint: Algorithm 1's fCφ must be injective for Theorem 13, but neither Lemma 12 nor the training procedure guarantees it. The LLGVR loss is not just a missing proof; its optimum actively destroys injectivity on real edges (all targets 0). Thus LGVR's practical expressivity claim is unsupported as written. The paper's theoretical TED contribution survives, so REJECT would be too harsh; a CONDITIONAL verdict with a request to verify or repair injectivity is appropriate. A post-training value-collision test is the cheapest decisive experiment. If the released code happens to produce well-separated real-edge values despite the loss, the concern is empirically retired; if not, the paper needs a changed objective (e.g., contrastive/orthogonality terms or a provably injective readout) before the LGVR=TED claim can stand.","tokens_in":29710,"tokens_out":7928,"duration_ms":85776,"concrete_test":"Run the released LGVR code on a small benchmark (e.g., MUTAG) with the paper's hyperparameters and then, with the trained model frozen, compute the multiset of real-edge filtration values {AC_G[e] : e ∈ E(G)} for each test graph. Report (a) the number of distinct values up to 1e-6 tolerance divided by |E(G)|, and (b) the median absolute deviation of real-edge values. If either the distinct-value ratio is far below 1 or the MAD is below ~1e-3, the edge filtration is effectively non-injective and the Theorem 13 premise fails in the deployed model; the paper would need a loss term or architecture that provably separates real-edge values.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's expressivity transfer from TED to LGVR (Theorem 13) hinges on the claim that Algorithm 1's edge filtration fCφ is injective. That claim is not established. Lemma 12 only shows existence of an injective φ under a countability assumption; the practical φ, P1, and P2 are arbitrary learned GIN/MLP maps, and the sentence \"the subsequent steps also maintain the injectivity\" (end of Section 5.3) is asserted without proof. Worse, the training objective LLGVR in Algorithm 1 explicitly regresses fCφ(l) to 0 for every node of LG (i.e., every real edge of G) and to 1 for virtual edges. Appendix A acknowledges that classifying only LG collapses all values to 0 and tries to fix it with virtual edges, but the real-edge targets are still all 0. At or near the loss minimum, the multiset {AC_G[e] : e ∈ E(G)} is therefore nearly constant, so the distance matrix AC_G is not injective and the persistence diagram sees all real edges simultaneously at ε ≈ 0. That violates the precondition of Lemma 8/Theorem 9 and breaks the claimed LGVR=TED equivalence. Additionally, the proof of Lemma 12 applies equation (3) to x1 + y1 − x2 − y2, but χ is only assumed to contain 0, not to be closed under differences; this is a separate gap in the existence argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Topological Edge Diagram (TED), an edge-filtration-based persistence diagram defined through a Vietoris-Rips filtration on the 1-skeleton of a graph, and proves that TED preserves arbitrary node coloring information and is strictly more expressive than the Weisfeiler-Lehman (WL) test under an injective edge filtration. To make this practical, the authors propose the Line Graph Vietoris-Rips (LGVR) algorithm, which builds an edge filtration matrix by mapping a colored graph to a colored line graph, adding virtual edges, and training node classifiers on the line graph. The paper then defines two model frameworks, C-LGVR and C-LGVR+, applies them to GIN and PPGN, and claims these models are strictly more powerful than WL-type colorings. The empirical section reports results on seven graph classification benchmarks and the QM9 regression benchmark, comparing against GIN, PPGN, and node-filtration baselines.","tokens_in":30056,"tokens_out":3933,"duration_ms":38238,"significance":"The theoretical core of the paper, Lemma 8 and Theorem 9, appears mathematically sound and offers a conceptually clean way to incorporate edge information into persistence-diagram representations: TED provably retains node coloring information and can distinguish some WL-indistinguishable graphs such as the pair in Figure 3. If the LGVR algorithm indeed implemented an injective edge filtration, the claimed expressivity transfer to GNNs would be a valuable contribution to topological graph representation learning. The paper also provides explicit code and relatively extensive experiments across many benchmarks, which is a strength. However, the central claim that the trained LGVR models inherit TED's expressivity rests on an unproven injectivity assertion for the entire learned pipeline, and the training objective actively pushes real-edge values together. This gap, together with a separate gap in the proof of Lemma 12 and the unsupported derivation of the PPGN-LGVR+ 3-WL claim, means the paper's headline results for the implemented algorithms are not yet established.","major_comments":[{"comment":"The claim that LGVR has the same expressivity as TED is not established. Lemma 12 only proves existence of an injective map phi on multisets of countable features, but the actual pipeline in Algorithm 1 composes phi with learned neural networks P1 and P2 and then maps to edge values fCphi. The sentence immediately after Lemma 12, \"since the subsequent steps also maintain the injectivity,\" is asserted without proof. Moreover, the LGVR loss LLGVR in Algorithm 1 regresses every real edge to 0 and every virtual edge to 1; at or near the loss minimum the multiset {AC_G[e] : e in E(G)} is nearly constant, so the distance matrix AC_G is not injective and the persistence diagram sees all real edges at essentially the same scale. This violates the injectivity precondition of Lemma 8 and Theorem 9 and therefore breaks the claimed LGVR=TED equivalence. I ask for either a rigorous injectivity theorem for the full trained pipeline under explicit architectural assumptions, or an empirical injectivity check (e.g., the minimum separation between distinct real-edge values on test graphs) together with a training procedure that provably preserves injectivity.","section":"Section 5.3, Theorem 13, and Algorithm 1"},{"comment":"The proof of Lemma 12 is incomplete. After assuming equality of the two phi values, the argument applies equation (3) to x1 + y1 - x2 - y2 = epsilon*(f^N(x2)+f^N(y2)-f^N(x1)-f^N(y1)). However, equation (3) only states that certain sums of signed elements from a multiset in M_chi(d) intersect chi in {0}; the left-hand side x1 + y1 - x2 - y2 is not guaranteed to belong to that set, because chi is only assumed to contain 0 and is not assumed to be closed under addition or subtraction. The conclusion that both sides of the displayed equality must be zero is therefore unjustified. The proof should be repaired by either strengthening the assumption on chi or by choosing f and epsilon so that differences of this form are excluded from the relevant set.","section":"Lemma 12 proof"},{"comment":"The claim that PPGN-LGVR+ is at least as powerful as the 3-WL test is unsupported. The proof states that it \"follows from Corollary 16 and Remark 17,\" but no derivation is provided. In particular, ENC(PPGN) extracts only the diagonal of the node tuple matrix, i.e., node colorings, while PPGN's 3-WL expressivity comes from the full tuple colorings. The argument would need to show that the lossless integration of the diagonal node colorings plus the LGVR topological information is enough to simulate 3-WL; this is not obvious and cannot be read off from the cited statements.","section":"Corollary 18(3)"}],"minor_comments":[{"comment":"The word \"Topologcial\" appears in the introduction; it should be \"Topological.\"","section":"Abstract / Introduction"},{"comment":"The phrase \"is inejctive\" should be \"is injective.\"","section":"End of Section 5.3"},{"comment":"The notation \"C-L VGR\" appears inconsistently; the framework is named \"C-LGVR\" elsewhere. Please unify the two names throughout the paper.","section":"Section 6.2.2 and Table 3"},{"comment":"The second part of Theorem 13 states merely that there exists a pair (G,H) with LGVR(G,C) != LGVR(H,C), but omits the important qualification that this pair is not distinguishable by the WL test. This should be added to match Theorem 9.","section":"Theorem 13 statement"},{"comment":"The loss function LLGVR in Algorithm 1 references fCphi, but the definition of fCphi and the construction of the matrix AC_G are deferred to a supplementary block. Consider moving this material into the main text or clearly labeling it as part of Algorithm 1, since it is essential to understanding the method.","section":"Algorithm 1 and Appendix A"}],"recommendation":"major_revision","confidential_remarks":"The manuscript has a solid theoretical core in Sections 4, but the gap between the theoretical TED and the implemented LGVR is the central issue. The paper would benefit from a reviewer with TDA expertise, since the injectivity condition is the linchpin of the expressivity transfer. I do not see evidence of deliberate overclaiming, but the headline statements about the implemented models currently outrun the proofs."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea is genuinely new: use edge filtration on the line graph to get persistence diagrams that preserve node-coloring information, which node-filtration methods like Hofer et al. and Horn et al. cannot do. Lemma 8 and Theorem 9 are real theorems: with an injective edge filtration, TED recovers WL colorings and strictly exceeds WL on an explicit example pair. That is the paper's genuinely valuable part, and it reads as correct to me, modulo some minor bookkeeping about isolated nodes.\n\nThe problem is the bridge from TED to the implemented LGVR. Theorem 13 needs the learned edge filtration to be injective. That is not shown. Lemma 12's proof applies equation (3) to x1+y1−x2−y2, but χ is only assumed to contain 0, not to be closed under differences, so the conclusion that both sides vanish does not follow. And the sentence \"the subsequent steps also maintain the injectivity\" (end of Section 5.3) is asserted without proof; P1 and P2 are generic GIN/MLP layers, and no argument shows they preserve injectivity. More concretely, the LGVR loss in Algorithm 1 regresses every real edge to 0 and every virtual edge to 1. At or near convergence the real-edge values are nearly constant, which destroys the injectivity that Theorem 9 requires. The paper acknowledges the collapse problem in Appendix A and adds virtual edges to avoid it, but the real-edge targets are still all 0. So the practical algorithm's expressivity is not established by the paper's theorems. The PPGN/3-WL claim (Corollary 18(3)) is also under-derived: extracting only the diagonal of PPGN's node-tuple output does not obviously preserve 3-WL expressivity, and the proof is a one-line reference to Corollary 16.\n\nThe abstract TED results are conditional on an injective edge filtration, which is a clean assumption and standard in the field; those survive. What the paper overclaims is that the neural-network implementation inherits that guarantee. The experimental results are okay but not decisive, and the mean-accuracy gaps are small. The right fix is to prove injectivity for the actual loss, or change the loss so that edges are forced to have distinct values, or weaken the claims to conditional/heuristic.\n\nMy recommendation: send to peer review, but explicitly ask for a proof or a corrected objective for LGVR injectivity and a real derivation of the 3-WL claim. The conceptual framework is novel and the TED analysis is worth publishing, but the current form needs major revision to close the algorithmic gap.","headline":"Novel TED theory is sound, but the LGVR implementation does not inherit the injectivity needed for the expressivity theorems; the paper deserves review but needs major revision.","tokens_in":30526,"tokens_out":8721,"would_cite":true,"duration_ms":81479,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["55N31","68R10","05C60"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper argues that a persistence diagram built on edge filtration can preserve all node-embedding information and add topological structure that the Weisfeiler-Lehman test cannot see, giving graph neural networks strictly more…","keywords":["graph neural networks","persistence diagrams","topological data analysis","edge filtration","line graph","Weisfeiler-Lehman test","Vietoris-Rips filtration","graph representation learning"],"falsifier":"Train the published GIN-LGVR model on any dataset, extract the edge filtration matrix from Algorithm 1, and test whether two non-isomorphic colored edge pairs ever receive exactly the same filtration value within numerical precision; if any two distinguishable edge types collide, the injectivity premise fails and the theorem's conclusion that LGVR distinguishes the corresponding graphs no longer follows from the proof.","tokens_in":29550,"feed_emoji":"🕸️","tokens_out":4840,"duration_ms":45246,"temperature":0.7,"pith_summary":"The paper argues that node-filtration-based topological graph methods lose expressiveness because they discard node-coloring information, and that moving the filtration to edges fixes this. It defines the Topological Edge Diagram (TED), a persistence diagram of the Vietoris-Rips filtration on the graph's node set whose distance matrix is supplied by an injective edge filtration. The paper proves that TED preserves arbitrary node-coloring information under a mild degree assumption, and that for stable Weisfeiler-Lehman colorings TED is strictly more powerful than the Weisfeiler-Lehman test. It then implements TED with a neural algorithm, LGVR, that builds an injective edge filtration by passing through the line graph, and proves that the resulting models GIN-LGVR and GIN-LGVR+ are strictly more expressive than their base message-passing GNNs. Experiments on graph classification and regression benchmarks support the claim that edge filtration helps GNNs use both node and edge information.","feed_headline":"Edge-based persistence diagrams out-see the Weisfeiler-Lehman test","feed_subtitle":"New TED diagrams preserve node embeddings and add topology, making GNNs strictly more expressive than 1-WL.","key_machinery":"The load-bearing construction is the injective edge filtration: a positive real-valued function on the multiset of colored edges $\\{\\{C(u),C(v)\\}\\}$, used as the distance matrix for a Vietoris-Rips filtration on the graph's own nodes. Injectivity is what lets a single edge value carry the full identity of the pair of node colors, so the $0$- and $1$-dimensional persistence diagrams of the 1-skeleton retain both node-color information and cycle structure. The paper's implementation passes through the line graph: nodes of the line graph represent edges of the original graph, and a map $\\phi$ sends an unordered pair of node features to a pair $(\\text{sum}, |\\text{difference}|)$ of perturbed features, with a countability argument proving that an injective realization exists. A neural network then classifies real versus virtual edges to assign filtration values, and the persistence diagram of the resulting matrix is the LGVR diagram.","core_discovery":"The central claim is that edge-filtration persistence can encode the full multiset of node colors while adding topological invariants that the Weisfeiler-Lehman (WL) test cannot detect. Concretely, for any node coloring satisfying the degree assumption (equal-colored nodes have equal degree), an injective edge filtration produces a pair of persistence diagrams, the $0$- and $1$-dimensional persistent homology of the Vietoris-Rips 1-skeleton, from which the multiset of node colors can be recovered, because each colored edge is born at its own filtration value and either closes a component or creates a cycle. For the stable WL coloring with identical initial colors, the paper proves TED distinguishes every pair of graphs the WL test distinguishes and additionally distinguishes a specific pair of non-isomorphic graphs on which WL fails. The algorithm LGVR aims to realize this injective edge filtration by mapping each graph to its line graph and assigning node features to line-graph nodes via a learnable injective map on unordered pairs of colors.","pith_inferences":["If injectivity holds in trained networks, the same edge-filtration construction could be extended to higher-dimensional persistent homology to separate graphs beyond the $3$-WL barrier, since the distance matrix is already available.","The reliance on countable feature spaces suggests a potential failure mode under continuous learned features; a practical check is whether trained filtration values for distinct edge types remain separated.","The line-graph construction ties expressiveness to edge colorings, so a similar diagram could be built for hyperedges or attributed edges, potentially yielding analogous topological summaries for hypergraphs.","The reported lower variance across data splits, if it replicates, suggests that topological summaries act as a regularizer rather than only an accuracy boost."],"forward_implications":["Any message-passing GNN $C$ whose node colorings satisfy the degree assumption can be upgraded to $C$-LGVR without losing the coloring's distinguishing power.","$C$-LGVR+ integrates the GNN's pooled node representation with the topological diagram, so the combined model is at least as expressive as each component.","GIN-LGVR and GIN-LGVR+ are strictly more powerful than the $1$-WL test; in particular they separate graphs that WL cannot distinguish.","PPGN-LGVR+ is at least as powerful as the $3$-WL test.","The empirical results indicate that the gains over the base GNN are largest when initial node features are uninformative, since topology then carries much of the signal."],"supporting_citations":[{"why":"Provides the node-filtration baseline GFL that the paper compares against and whose loss of coloring information motivates edge filtration.","marker":"Hofer et al. (2020)"},{"why":"States the node-filtration expressivity result that requires all node features to be distinct, the limitation TED overcomes.","marker":"Horn et al. (2021)"},{"why":"Defines GIN and proves that message-passing GNNs match the WL test; also supplies the multiset-injectivity lemma used in the integration technique.","marker":"Xu et al. (2018a)"},{"why":"Defines PPGN, the higher-order baseline whose node-tuple colorings are used in the PPGN-LGVR+ framework.","marker":"Maron et al. (2019)"},{"why":"Introduces the WL test, the expressivity benchmark against which TED and LGVR are compared.","marker":"Weisfeiler and Lehman (1968)"},{"why":"Supplies the persistence-theory background including persistence diagrams and Vietoris-Rips filtrations used in the definitions and proofs.","marker":"Oudot (2017)"},{"why":"Provides the universal approximation theorem used to argue that the injective map phi can be realized by a multilayer perceptron.","marker":"Hornik (1991, 1992)"},{"why":"Supports the computational-topology complexity claim of $O(m\\alpha(m))$ for computing persistence in dimensions 0 and 1.","marker":"Edelsbrunner and Harer (2022)"}],"fun_headline_variants":["Edge filtration gives GNNs a topological upgrade beyond WL","TED: edge persistence that preserves node embeddings and outdoes WL","Line graph persistence diagrams trump Weisfeiler-Lehman for GNNs","Edge-based persistence: strictly more expressive than 1-WL"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole expressivity guarantee relies on the LGVR edge filtration being injective, meaning each distinct pair of node colors must end up with its own unique filtration value; the paper asserts that the neural network layers preserve injectivity but does not prove it, and the training loss pushes real-edge values toward zero, which could collapse distinct edges to the same value.","fun_headline_variants_meta":{"raw":{"variants":["Edge filtration gives GNNs a topological upgrade beyond WL","TED: edge persistence that preserves node embeddings and outdoes WL","Line graph persistence diagrams trump Weisfeiler-Lehman for GNNs","Edge-based persistence: strictly more expressive than 1-WL"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000173,"raw_usage":{"total_tokens":1279,"prompt_tokens":943,"completion_tokens":336,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":559,"completion_tokens_details":{"reasoning_tokens":262}},"tokens_in":559,"tokens_out":336,"duration_ms":3678,"temperature":1.0,"reasoning_tokens":262,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:28:06.445803+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train the published GIN-LGVR model on any dataset, extract the edge filtration matrix from Algorithm 1, and test whether two non-isomorphic colored edge pairs ever receive exactly the same filtration value within numerical precision; if any two distinguishable edge types collide, the injectivity premise fails and the theorem's conclusion that LGVR distinguishes the corresponding graphs no longer follows from the proof.","supporting_citations":[],"review_version":1}