Pith. sign in

REVIEW 3 major objections 5 minor 17 references

Line Graph Vietoris-Rips Persistence Diagram for Topological Graph Representation Learning

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2412.17468 v1 pith:VCSQQNZQ submitted 2024-12-23 cs.LG cs.AImath.AT

Jaesun Shin , Eunjoo Jeon , Taewon Cho , Namkyeong Cho , Youngjune Gwon This is my paper · ORCID
classification cs.LGcs.AImath.AT MSC 55N3168R1005C60
keywords graphneuralnetworkspersistencediagramstopologicaldataanalysisedgefiltrationlineWeisfeiler-LehmantestVietoris-Ripsrepresentationlearning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Section 5.3, Theorem 13, and Algorithm 1] 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.
  2. [Lemma 12 proof] 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.
  3. [Corollary 18(3)] 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.
minor comments (5)
  1. [Abstract / Introduction] The word "Topologcial" appears in the introduction; it should be "Topological."
  2. [End of Section 5.3] The phrase "is inejctive" should be "is injective."
  3. [Section 6.2.2 and Table 3] The notation "C-L VGR" appears inconsistently; the framework is named "C-LGVR" elsewhere. Please unify the two names throughout the paper.
  4. [Theorem 13 statement] 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.
  5. [Algorithm 1 and Appendix A] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the expressivity claims are conditional on an injective edge filtration and are checked against the external WL test; the unproven injectivity of the learned filtration is a correctness gap, not circularity.

full rationale

I find no circular step. The main expressivity chain is non-circular. TED's Lemmas 8 and Theorem 9 are conditional statements: for any injective edge filtration ef_C, if node-color multisets differ, or if the WL test distinguishes the graphs, then the persistence diagrams differ. The proof compares against the external WL test and an explicit pair of graphs in Figure 3. LGVR transfers this expressivity via Theorem 13, whose premise is Lemma 12's existence of an injective phi under countability, plus the assertion that later layers maintain injectivity. That assertion is unproved, and Algorithm 1's training objective LLGVR, which pushes real-edge values toward 0, may destroy injectivity; but this is a missing-support or correctness issue, not a case where a fitted parameter is renamed as a prediction or where a theorem is equivalent to its input by construction. No load-bearing self-citations occur: the cited results (Xu et al. Lemma 5, Hornik's universal approximation, Zaheer et al.) are standard external supports for multiset encoding and MLP approximation, not author-specific uniqueness claims. The experiments are on standard public benchmarks and are not derived from the theory's fitted values. Therefore no circularity step can be exhibited, and the paper's conditional theoretical arguments are self-contained with respect to their stated assumptions.

Assumptions & free parameters 4 free parameters · 4 assumptions · 1 invented entities

The central theoretical claims rest on the existence of an injective edge filtration, which is guaranteed only under the countable-universe axiom and a constructed map φ; the practical algorithm introduces learnable parameters and a hand-chosen scale range that affect whether the theoretical guarantees carry over to the implemented models.

free parameters (4)
  • ε (integration scalar) = learned
    Learnable scalar in Equation (8) for C-LGVR+; its existence is proven in Corollary 16, but the value is fitted during training.
  • η (perturbation scalar) = learned
    Learnable scalar in the map φ in Section 5.1; controls the perturbation added to node features to make φ injective.
  • filtration scale range [0, 0.5] = 0.5 threshold
    Chosen by hand in Appendix B because the node classifier outputs values in [0,1] and meaningful edges are close to 0; this is a modeling choice not derived from theory.
  • λ (LGVR loss weight) = hyperparameter
    Weight balancing task loss and LGVR loss in Section 6.2.3; tuned per dataset.
assumptions (4)
  • domain assumption The node coloring universe χ is countable
    Needed for Lemma 12 to construct an injective φ; in practice node features are finite-dimensional floats, so this is mild.
  • domain assumption Degree Assumption (Definition 7): C(u)=C(v) implies deg(u)=deg(v)
    Used in Lemma 8 and the proof of Theorem 9; holds for WL colorings and for generic GNN colorings, but not for all possible node colorings.
  • ad hoc to paper The edge filtration ef_C is injective
    TED is only defined for injective edge filtrations; the entire expressivity argument depends on injectivity, which the algorithm attempts to achieve but does not guarantee after training.
  • standard math Universal approximation theorem for MLPs
    Invoked in the proof of Theorem 13 to argue the learned φ can approximate the injective map from Lemma 12; approximation does not imply exact injectivity.
invented entities (1)
  • Virtual edges
    purpose: Edges added to make a complete graph K_G so the line graph node classifier can distinguish real edges from fake ones (Appendix A)
    A training device; the edge values on real edges are pushed toward 0 and virtual edges toward 1, which risks collapsing the injectivity that the theory requires.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Line Graph Vietoris-Rips Persistence Diagram for Topological Graph Representation Learning." pith.science (2026). https://pith.science/paper/VCSQQNZQ

@misc{pith2026241217468,
  author       = {Pith},
  title        = {Pith review of: Line Graph Vietoris-Rips Persistence Diagram for Topological Graph Representation Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VCSQQNZQ}},
  note         = {Machine review of arXiv:2412.17468}
}
read the original abstract

While message passing graph neural networks result in informative node embeddings, they may suffer from describing the topological properties of graphs. To this end, node filtration has been widely used as an attempt to obtain the topological information of a graph using persistence diagrams. However, these attempts have faced the problem of losing node embedding information, which in turn prevents them from providing a more expressive graph representation. To tackle this issue, we shift our focus to edge filtration and introduce a novel edge filtration-based persistence diagram, named Topological Edge Diagram (TED), which is mathematically proven to preserve node embedding information as well as contain additional topological information. To implement TED, we propose a neural network based algorithm, named Line Graph Vietoris-Rips (LGVR) Persistence Diagram, that extracts edge information by transforming a graph into its line graph. Through LGVR, we propose two model frameworks that can be applied to any message passing GNNs, and prove that they are strictly more powerful than Weisfeiler-Lehman type colorings. Finally we empirically validate superior performance of our models on several graph classification and regression benchmarks.

Figures

Figures reproduced from arXiv: 2412.17468 by the authors.

Figure 1
Figure 1. An overview of node filtration and edge filtration of WL coloring. For graphs [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. The difference in subgraph construction between two types of filtrations: node [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. An example of a pair of non-isomorphic graphs that are not distinguishable by [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: An overall framework of Algorithm 1. Note that the map [PITH_FULL_IMAGE:figures/full_fig_p015_4.png]
Figure 5
Figure 5. Figure 5: Two model frameworks: C-LGVR and C-LGVR+. Note that ENC component refers to the process of extracting node coloring from the message passing graph neural network (or coloring) C as described in Section 6.2 and 6.3. Proof We first prove the case when |I| = 2. Since χ1 a…
Figure 6
Figure 6. Figure 6: Improvement percentages of two filtrations compared to GIN. The performances [PITH_FULL_IMAGE:figures/full_fig_p025_6.png]
Figure 7
Figure 7. Figure 7: Standard deviations of GIN type models: GIN, GFL, GFL [PITH_FULL_IMAGE:figures/full_fig_p026_7.png]
Figure 8
Figure 8. Figure 8: An architecture of our set encoder. Note that Elementwise MLP means performing [PITH_FULL_IMAGE:figures/full_fig_p030_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 4 canonical work pages

  1. [5]

    Z. Chen, L. Chen, S. Villar, and J. Bruna. Can graph neural networks count substructures? arXiv preprint arXiv:2002.04025 ,

    arXiv 2002

  2. [6]

    B. L. Douglas. The weisfeiler-lehman method and graph isomorphism testing.arXiv preprint arXiv:1101.5211,

    arXiv

  3. [9]

    M. Horn, E. De Brouwer, M. Moor, Y. Moreau, B. Rieck, and K. Borgwardt. Topological graph neural networks. arXiv preprint arXiv:2102.07835 ,

    arXiv

  4. [13]

    Maron, H

    H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman. Provably powerful graph networks. arXiv preprint arXiv:1905.11136 ,

    arXiv 1905

  5. [15]

    K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826, 2018a. K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pages 5453–5462. PMLR, 2018b. P. Yanardag and S...

    arXiv

  6. [1979]

    Balcilar, G

    M. Balcilar, G. Renton, P. H´ eroux, B. Gauzere, S. Adam, and P. Honeine. Bridging the gap between spectral and spatial domains in graph neural networks. arXiv preprint arXiv:2003.11702,

    arXiv 2003

  7. [1992]

    D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980,

    arXiv

  8. [2002]

    Deep Learning with Topological Signatures

    C. Hofer, R. Kwitt, M. Niethammer, and A. Uhl. Deep learning with topological signatures. arXiv preprint arXiv:1707.04041 ,

    work page Pith review arXiv

Show all 17 references
  1. [2014]

    T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv:1609.02907 ,

    arXiv

  2. [2015]

    R. Ying, J. You, C. Morris, X. Ren, W. L. Hamilton, and J. Leskovec. Hierarchical graph representation learning with differentiable pooling. arXiv preprint arXiv:1806.08804 ,

    arXiv

  3. [2016]

    Kondor, H

    R. Kondor, H. T. Son, H. Pan, B. Anderson, and S. Trivedi. Covariant compositional networks for learning graphs. arXiv preprint arXiv:1801.02144 ,

    arXiv

  4. [2017]

    Weisfeiler and A

    B. Weisfeiler and A. Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction, nauchno–technicheskaja informatsia, 9 (1968), 12–16,

    1968

  5. [2018]

    Zhao and Y

    Q. Zhao and Y. Wang. Learning metrics for persistence-based summaries and applications for graph classification. arXiv preprint arXiv:1904.12189 ,

    1904 arXiv

  6. [2019]

    F. Chen, S. Pan, J. Jiang, H. Huo, and G. Long. Dagcn: dual attention graph convolutional networks. In 2019 International Joint Conference on Neural Networks (IJCNN) , pages 1–8. IEEE,

    2019

  7. [2020]

    Balcilar, P

    M. Balcilar, P. H´ eroux, B. Ga¨ uz` ere, P. Vasseur, S. Adam, and P. Honeine. Breaking the limits of message passing graph neural networks. arXiv preprint arXiv:2106.04319 ,

    arXiv

  8. [2021]

    Bouritsas, F

    33 Shin, Jeon, Cho, Cho, and Gwon G. Bouritsas, F. Frasca, S. Zafeiriou, and M. M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.09252,

    2006 arXiv

  9. [2022]

    Fey and J

    M. Fey and J. E. Lenssen. Fast graph representation learning with pytorch geometric.arXiv preprint arXiv:1903.02428,

    1903 arXiv

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.