acceptodds
Under review as a conference paper at ICLR 2027

TopoNeSy: Exact Lifetime-Space Verification for Graph-Topological Queries

Abstract

Feature-space robustness verification can be conservative when candidate feature perturbations have no admissible input realization at the claimed distance. TopoNeSy studies this question for a fixed graph with independently perturbed edge-birth times, a one-dimensional preterminal filtration, and completion at time one. Our main theoretical result is an exact image-and-lift theorem: every clipped input ball maps exactly to the ordered ball of the same radius around the global lifetime vector, and every target has a constructive input preimage at its distance from the nominal lifetime vector. This strengthens forward stability from an enclosure to exact realizability. Consequently, any frozen lifetime-only query has the same exact flip radius in input and lifetime space. The reduction also permits exact elimination of unused lifetime coordinates. TopoNeSy instantiates the resulting verification interface with jointly trained affine predicates and Boolean DAGs under a no-bypass architecture, deployed with exact rational semantics. Controlled experiments validate reconstruction and computational reduction. On measured EEG connectivity graphs, a frozen full- DAG attains 76.11% balanced accuracy and 67.78% open-ball certified balanced accuracy at edge radius , averaged over three seeds. All 720 model/window cases have verified radius intervals of width at most after refinement, with actual graph counterexamples at their upper endpoints. The guarantees concern the stated stored-edge domain, not raw EEG perturbations. Code: https://anonymous.4open.science/r/toponesy-75FF/

Primary area:
learning on graphs and other geometries & topologies
Keywords:
persistent homology, topological data analysis, certified robustness, formal verification, graph verification, neuro-symbolic AI, inverse persistence

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_WDZaOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies robustness verification for classifiers that read only the global H1H_1 lifetimes of a fixed graph whose edge-birth times are perturbed independently, under a one-dimensional preterminal filtration with all deaths at time 1. The main result (Theorem 1) shows that a clipped ℓ∞\ell_\infty input ball maps exactly onto the ordered ℓ∞\ell_\infty ball of the same radius in lifetime space. It also gives a constructive lift that realizes any ordered target at exactly its lifetime-space distance. As a consequence, exact flip radii coincide in input and lifetime space, and coordinates the query does not read can be eliminated exactly. The authors start this with a jointly trained head of affine predicates and a Boolean DAG, exported with exact rational semantics and verified via checked Boolean–linear refinement. Controlled experiments show computational savings over raw graph-variable SMT. On EEG eyes-open/closed classification, the head reaches 76.11% BA and 67.78% certified BA at radius 0.01, with all 720 certified intervals of width at most 10−510^{-5} and a replayed graph counterexample at each upper endpoint.

Critical strengths
  1. Correct, clean, constructive exactness result with an operational payoff.

  2. Rigorous and transparent verification and evaluation methodology.

Critical weaknesses
  1. The core theorem has limited topological significance. Under the declared filtration (one-dimensional preterminal complex, all deaths at 1), the ordered H1H_1 lifetimes are just 1−1- the sorted non-spanning-forest edge weights. The authors acknowledge this in F.5, where the result is stated for any matroid nullity profile. The forward bound is standard order-statistic stability, and the lift is a short monotone-assignment argument. On K64K_{64}, L(x)L(x) is 1,953 of the 2,016 sorted edge weights. The experiments are consistent with this: sorted-all-edges MLP gets 76.81%, the H1H_1 DAG gets 76.11%, and named edges reach 88.33%. The settings where PH genuinely differs from sorting, such as early 2-cells or variable deaths, are exactly the ones the theorem excludes. This limits both the novelty and the relevance of the main result, and it is the main reason for my recommendation.

  2. The practical benefit is not demonstrated, and key baselines are missing. The only gap between the trivial forward-stability enclosure and the exact image is the ordering constraint. The paper never measures how much this constraint changes certified radii on EEG. In addition, the competing heads are never certified on the same ordered domain with standard verifiers: the linear SVM is exactly verifiable by a single LP, and the MLP could use α,β-CROWN or MILP. The only robustness comparison is against the tree and min/max heads, which are weak. As a result, the claimed robustness advantage of the Boolean DAG is not established. The threat model, independent ±0.01 perturbations of each coherence value, is also non-physical.

Questions for authors
  1. On the EEG models, what are the certified lower bounds and BCA$_{\text{open}}(.01)$ if verification uses the unordered enclosure box {z:∥z−L(x)∥∞≤ϵ}∩[0,1]β\{z:\|z-L(x)\|_\infty\le\epsilon\}\cap[0,1]^\beta instead of Cβ\mathcal{C}_\beta? If the gap is small, please explain what the exact-image theorem buys beyond counterexample construction.

  2. Can you report certified BCA on the same ordered domain for the linear SVM/logistic regression (exact via LP) and for the MLP (via a standard complete or incomplete verifier)? Without this, the claimed robustness advantage of the DAG is only relative to weak heads.

  3. Under your filtration, LL equals the sorted non-spanning-forest edge weights. Can you state clearly what is topological about the contribution beyond the graphic-matroid nullity profile? Is there any setting covered by your theory, rather than only by the counterexamples in A.4/F.3, in which PH carries information not captured by this sorting?

  4. Subjects 86–109 are described as unopened. Since all modeling choices are frozen, why not report the final evaluation on them? The current cohort is described as a development cohort, and the eyes-open/closed label is confounded with run.

9 comments

We thank the reviewer for their careful reading and thoughtful critique.

Summary of our reply

The reviewer's description is correct: LL is one minus the sorted edge weights outside the spanning forest. What does not follow is that this "limits both the novelty and the relevance of the main result". The claim of the paper is exactness (forward stability strengthened "from an enclosure to exact realizability"), and exactness is a property of this map, not of sorting:

  1. It fails for the 0D and 1D profiles read together, also sorted lists of the same weights, on every graph with a cycle and one more edge (Q3).
  2. It holds in ℓ∞\ell_\infty and fails in ℓ2\ell_2 already on a triangle; for a plain sorted vector it holds in every ℓp\ell_p (W1).
  3. On the EEG graphs, the target "every cycle birth lowered by .01" cannot be reached at that distance without moving spanning-forest edges, in all 528 windows; the opposite shift needs no such change (W1).

The feature is not ours: it is the 1D barcode of the graph filtration, in published use on brain connectivity, including at ICLR (Songdechakraiwut et al., 2022). Prior work has the decomposition and a stated forward bound; we know of no statement of the converse.

  • Q1. At ε = .01 the box loses 2 of 720 and 6 of 864 DAG cases and up to 23 of 240 windows for a logistic head; a single-pass MLP verifier certifies 23.33% of cases on the box and 42.50% on the exact image (subjects 66–85). Exactness adds completeness: on subjects 66–85, each of the 62 correct DAG cases not certified on the box is certified on graphs (2) or refuted by a graph (60).
  • Q2. A table for every head on both cohorts. The frozen linear heads have certified accuracy 0%; two post hoc references, a regularised logistic head and a one-threshold query, are above the DAG on subjects 86–109; the MLP there, verified for this reply, lies in [54.98, 56.02]%. The DAG is not the most robust head, and the paper does not claim it is.
  • Q3. Nothing beyond the nullity profile. The counterexample of F.3 becomes an "if and only if" classification. The excluded clique setting, measured on the same EEG graphs, is less accurate for every head on subjects 66–85, and its stability certificate certifies no window for the heads analysed.
  • Q4. On subjects 86–109 the DAG has BA 67.59% and BCA(.01) 54.17%; the run confound remains.
  • W2. The threat model is not physical; we give the scale of the radii against measured variation.

Theorem 1, its proof, the verifier, the models and the 720 certificates are unchanged. The final version adds the tables of Q1, Q2 and Q4, says in the abstract that LL is the sorted non-forest edge weights, cites the graph-filtration literature, points from Section 2 to F.6–F.8, replaces the counterexample of F.3 by the classification, and restricts the D.3 sentence on robustness to the tree and min/max heads.

What the paper claims after these changes. An exactness theorem for a persistent-homology feature in published use, with its boundary located on both sides (the joint 0D/1D profile; clique filtrations), and a verification interface that runs from a measured graph to a certificate replayed in exact arithmetic at β=1,953\beta=1{,}953.

If a claim still reads as overstated, we would be grateful if the reviewer pointed to it.

W1: significance of the theorem

The description is correct; the conclusion does not follow. 1−L(x)1-L(x) is the sorted vector of edge weights rejected by Kruskal's pass (Section 2.1, F.5; the abstract will say it). If the theorem were the sorting fact, it would hold wherever sorting does:

FeatureAlways a preimage at exactly the feature distance?
All edge weights, sortedYes, in every ℓp\ell_p (classical)
1D profile aloneYes in ℓ∞\ell_\infty (Theorem 1); no in ℓ2\ell_2
0D and 1D profiles togetherNo in ℓ∞\ell_\infty, on every graph with a cycle and one more edge (Q3 reply)

All three are sorted lists of the same weights, so exactness belongs to this map and this metric and is lost one step further.

Why the sorting argument is not enough. Which edges are rejected depends on the weights.

  • Triangle. Weights (.2, .5, .6), cycle birth .6. To reach birth .4, at profile distance .2, lowering the rejected edge gives (.2, .4, .5), whose birth is .5; a forest edge must move too, to (.2, .4, .4): ℓ∞\ell_\infty distance .2, ℓ2\ell_2 distance .224.
  • EEG. For the target "every cycle birth lowered by .01", no graph within .01 that keeps the spanning-forest weights has that profile, in all 528 windows (the upward shift needs no such change). In 1,490 of the 1,584 counterexample graphs behind the certified radii, reassigning the rejected edges in sorted order gives a different profile. The lift of Theorem 1 moves forest and rejected edges together, keeps Kruskal's decisions and never exceeds the profile distance.

The feature is an established one. It is the 1D barcode of the graph filtration of brain-network analysis (Lee et al., 2012, who study its connected components): the barcode splits the edge weights into maximum-spanning-tree weights (0D) and the rest (1D) (Songdechakraiwut & Chung, 2023, Theorem 1). Songdechakraiwut et al. (ICLR 2022) view the thresholded network as a 1-skeleton, "in contrast to well-known Rips (Ghrist, 2008) and clique complexes (Otter et al., 2017)", and apply the barcode to 8–12 Hz connectivity of ten-second resting-state intracranial EEG segments, the band and window length of our Section 4.2; they compare its 0D and 1D parts jointly, in 2-Wasserstein (Lee et al.: dendrograms, in Gromov–Hausdorff distance). Graph learning treats cycles the same way, born with an edge and never dying (Rieck et al., ICML 2019, on edge weights; Horn et al., ICLR 2022; Immonen et al., NeurIPS 2023; reply to Reviewer Ph5m, W1). The submission cites only Immonen et al.; the final version cites this line. The precedent shows that the feature is in use; the theorem is not in these works.

Forward statements are known; the converse is not. Prior work has the decomposition and a stated forward bound: close graphs have close barcodes (Songdechakraiwut & Chung, 2023, Section 2.5; the derivation is not included there); the certificate through a persistence layer known to us (Agerberg et al., 2024, point clouds) is forward too. We know of no statement of the converse: every barcode within rr of the barcode of a graph is the barcode of a graph within rr of it. Descriptions of persistence fibers (Leygonie & Tillmann, 2022; Section 3 of the paper) give neither the nearest preimage nor its distance.

What the converse is for. Without it a stability certificate is sound with unknown slack, because a feature-space counterexample need not be a graph. Theorem 1 shows that the slack is zero (on EEG: our Q1 reply).

We claim no predictive advantage over sorted or named edges (Tables 6–7), and do not argue that the profile should be preferred on EEG: only that a model reading this published feature can be verified in feature space without loss.

References. H. Lee et al., IEEE TMI 31(12), 2012. T. Songdechakraiwut et al., ICLR 2022. T. Songdechakraiwut, M. K. Chung, Ann. Appl. Stat. 17(1), 2023. J. Agerberg et al., NeurReps workshop at NeurIPS 2024 (extended abstract), arXiv:2501.10876.

Q3: what is topological, and is any covered setting beyond sorting?

Literal answers. Nothing beyond the nullity profile: under the graph filtration, H₁ persistence is the nullity profile of the graphic matroid, and the contribution is an exactness property of an existing invariant. And no: in every setting of the paper the feature is this sorted profile, and we have no setting with pairing information in which the transfer is exact without conditions.

A classification in place of the counterexample of F.3 (a triangle with a bridge: feature distance .6, nearest preimage at .7).

Proposition 9′ (joint profile). In the setting of Theorem 1, read the full sorted 0D and 1D profiles together, in coordinate ℓ∞\ell_\infty. Every input and every attainable target admit a preimage at exactly the profile distance if and only if the graph is a forest or its non-isolated part is a single simple cycle. On every other graph there are an input and two-threshold queries whose flip radius is η\eta in profile space and a+ηa+\eta in input space, for any 0<η<a≤1/20<\eta<a\le 1/2: the gap can be half the weight range, and the ratio is unbounded as η↓0\eta\downarrow 0.

A proof sketch is in the next comment; the full proof goes into F.3. No number in our reply depends on this proposition; without it, the third row of the table in our W1 reply rests on the single instance of F.3.

What this says about the claim of the paper. The joint profile is also "sorted weights": two sorted lists that partition the same edges. For one list a stability certificate has no slack (Theorem 1; F.1, Theorem 2); for the two together it can be conservative by an arbitrary factor. Exactness therefore does not come from sorting: the paper locates where feature-space verification of this barcode is complete. (The literature of our W1 reply reads the joint profile in 2-Wasserstein; Proposition 9′ is in coordinate ℓ∞\ell_\infty.)

The excluded setting, measured. For Reviewer Ph5m (Q1) we ran the clique filtration, with its variable deaths, on the same EEG graphs (better of two descriptors, subjects 66–85):

  • accuracy: 59.6–67.5% for the five heads of Tables 6–7, against 71.7–76.3% for the same heads on the profile of the paper (on subjects 86–109 it is behind for four of the five);
  • certification: only a stability box remains, and it certifies no window for the heads analysed there. Graphs inside the ball refute 288 of the 473 correct cases of a DAG trained on these features, so its certified accuracy at ε = .01 is at most 25.7%, with the other 185 cases open. Under the graph filtration it is 67.78%, a value.

Where the inverse problem is not a sort (already in the submission, F.6–F.8). With conserved flows the exact image is strictly smaller than the ordered box, and the nearest preimage is a minimum-cost assignment (Proposition 15). With block-indexed targets the lift is polynomial; without the indices, attainability of a global ordered target is NP-complete (Corollary 4, Proposition 17). Under a declared polytope of admissible inputs the preimage is computed exactly over spanning-tree regions (Propositions 12–14). These are restricted results, and the main text will point to them: realizability stops being trivial once the inputs are coupled.

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

This paper studies exact robustness verification for classifiers operating on global H1H_1 persistent homology lifetimes of edge-weighted graphs under ℓ∞\ell_\infty edge-birth perturbations. Assuming vertices are born at 00, no 22-simplices enter before t=1t=1, and the complex completes to a full simplex at t=1t=1, Theorem 1 proves that the image of a clipped ℓ∞\ell_\infty input ball B(x,ϵ)⊆[0,1]mEB(x,\epsilon) \subseteq [0,1]^{m_E} under the sorted H1H_1 lifetime map LL is the ordered ℓ∞\ell_\infty ball in Cβ={z∈[0,1]β:z1≥⋯≥zβ}C_\beta = \{z \in [0,1]^\beta : z_1 \ge \dots \ge z_\beta\}, with an O(mE+β)O(m_E + \beta) minimum-distance preimage lift. The authors pair this reduction with a jointly trained affine-predicate Boolean DAG deployed in exact rational arithmetic, evaluating synthetic DNF workloads and 64-channel EEG coherence graphs (K64K_{64}).

Critical strengths
  • Correct, tight lift with matching implementation
  • Unusually honest scoping, The appendix states its own limits: the variable-death counterexample (A.4), joint H0/H1H_0/H_1 non-isometry (Proposition 9), and strong non-PH baselines (Tables 6–7).
Critical weaknesses
  • The "topology" collapses to sorting non-MST edge weights, and it is the weaker representation. Because no 2-simplex enters before t=1t=1, 1−L(x)1-L(x) is just the sorted weights of the β\beta chords rejected by Kruskal. The authors' own counterexample (A.4) shows the result fails once triangles have variable deaths, i.e. for clique/Vietoris–Rips filtrations commonly used on connectivity graphs. On K64K_{64}, β=1,953\beta = 1{,}953 of 2,0162{,}016 edges (96.9%96.9\%); sorting all edges without PH gives 76.81%76.81\% BA (MLP, Table 6) versus 76.11%76.11\% for the H1H_1 DAG (Table 7), while named edges (88.33%88.33\%) or 64 alpha-power features (85.28%85.28\%) are clearly better.

  • Verification machinery is not exercised where it matters, and is expensive. Corollary 2 is a headline contribution, yet in the only learned models every one of the 1,9531{,}953 coordinates has a nonzero coefficient in at least one predicate (Appendix B.4), so it eliminates nothing; its 55.2%55.2\% speedup comes from synthetic s=2s=2 formulas (Section 4.1). Certifying 720720 EEG cases costs 164,099164{,}099 s of summed task time (≈228\approx 228 s/case, Table 10), whereas a linear SVM on the same features (76.25%76.25\%) reduces to single-predicate extrema (Proposition 4). The certified perturbations are independent edge changes that need not be valid coherence matrices (D.8).

Questions for authors
  • On K64K_{64} the H1H_1 births are the 1,9531{,}953 non-MST edge weights, and sorted raw edges match the H1H_1 DAG (76.81%76.81\% vs. 76.11%76.11\%, Tables 6–7). What evidence shows that the H1H_1 representation carries signal beyond the sorted edge-weight distribution, and does any guarantee survive a clique filtration with variable deaths (Appendix A.4)?

  • Appendix B.4 reports that the union of predicate supports covers all 1,9531{,}953 coordinates, so Corollary 2 removes nothing on EEG. Did you try sparsity-constrained predicates (e.g. ℓ1\ell_1 or fixed fan-in on aja_j), and how do accuracy, certified radius and the 164,099164{,}099 s cost (Table 10) change?

  • Can you release the three frozen rational exports and all 720720 certificate/witness records so the exact intervals in Tables 2 and 8 can be replayed without retraining?

8 comments

We thank the reviewer for their careful assessment and constructive questions.

Summary of our reply

All three questions are answered with completed work, and four statements of the review are answered by the paper itself or by new measurements.

The questions.

  • Q1. Under a clique filtration the exact result holds verbatim for H₀, and a sound certificate with a factor 2 holds for H₁; exactness is lost. On the EEG graphs the clique filtration predicts worse than the profile of the paper (59.6–67.5% against 71.7–76.3%), and the certified accuracy of a DAG trained on it can only be bracketed: [0, 25.7]%, where the DAG of the paper has the exact value 67.78%. The paper claims no predictive signal beyond the sorted weights and does not rest on one: the feature is a published one (point 1 below).
  • Q2. Run with a shared support of 32, 128 or 512 coordinates, ten seeds each. Accuracy stays within 1.5 points, certified accuracy at ϵ=.01\epsilon=.01 falls from 69% to 45–55% (the three seeds of the paper: 67.78%), and Corollary 2 becomes active: with the unread coordinates eliminated, the same function is decided in a median of 0.9 s instead of 15 s per case (dense models: 1.6 s).
  • Q3. Yes: the full replay takes about five minutes, and the exports, the graphs and all 720 certificate/witness records are at https://drive.google.com/file/d/1KBgKMKnp74BxLM7RGb9yLBN1-w4j2y6J/view?usp=sharing

Four points we ask the reviewer to weigh.

  1. The feature is not ours. "Sorted non-MST edge weights" is the 1D persistence barcode of the graph filtration (Songdechakraiwut & Chung, 2023, Theorem 1), used on EEG connectivity (Songdechakraiwut et al., ICLR 2022); graph learning treats cycles the same way (Rieck et al., ICML 2019; Horn et al., ICLR 2022; Immonen et al., NeurIPS 2023).
  2. The theorem is not a sorting fact. It is the converse of stability, and it fails for other sorted readings of the same weights: in ℓ2\ell_2 on a triangle, and in ℓ∞\ell_\infty for the 0D and 1D profiles read together.
  3. Corollary 2 is claimed only where coordinates are unread. Section 2 states that "No reduction is claimed when all coordinates are read", and the abstract will say so too; the corollary is now exercised on learned EEG models at β=1,953\beta=1{,}953.
  4. The certified accuracies are cheap. The 164,099 s locate all 720 radii to 10−510^{-5}; the certified accuracies of the abstract need 3.7 s per case on average (median 1.6 s). The cheap linear radius is exact in graph space by Theorem 1.

Theorem 1, its proof, the verifier, the models and the 720 certificates are unchanged.

W1 and Q1 (first part): a published feature, a new theorem

Main point. "Sorted non-MST edge weights" is the 1D persistence barcode of a published filtration, and the theorem about it is the converse of stability, which no sorting argument gives.

The feature is the published graph-filtration barcode. In the graph filtration of brain-network analysis (nested thresholded networks of nodes and edges only; Lee et al., 2012, who study its connected components) the persistence barcode splits the edge weights into the maximum-spanning-tree weights (0D) and the remaining weights (1D) (Songdechakraiwut & Chung, 2023, Theorem 1). The 1D part is our vector, up to the direction of the filtration. "Sorted non-MST edge weights" is therefore the known form of an established persistent-homology descriptor, not a degeneracy of our setting. Songdechakraiwut et al. (ICLR 2022) apply this barcode, its 0D and 1D parts compared in a Wasserstein metric, to 8–12 Hz connectivity of ten-second intracranial EEG segments, the band and window length of our Section 4.2, and view the network as a 1-skeleton "in contrast to well-known Rips (Ghrist, 2008) and clique complexes (Otter et al., 2017)". Graph learning treats cycles the same way: a cycle is born with an edge and never dies (Rieck et al., ICML 2019; Horn et al., ICLR 2022; Immonen et al., NeurIPS 2023). The final version cites this line.

What is new is the converse of stability. Prior work has the decomposition and a stated forward bound: close graphs have close barcodes. Theorem 1 proves the converse, which we have not found stated: every profile within rr of the profile of a graph is the profile of a graph within rr of it. This is not a fact about sorting, because it fails for other sorted readings of the same weights:

FeatureAlways a preimage at exactly the feature distance?
All edge weights, sortedYes, in every ℓp\ell_p (classical)
1D profile aloneYes in ℓ∞\ell_\infty (Theorem 1); no in ℓ2\ell_2
0D and 1D profiles togetherNo in ℓ∞\ell_\infty, unless the graph is a forest or a single cycle (F.3; reply to Reviewer WDZa, Q3)

The rows differ because which edges are rejected depends on the weights. A triangle with weights (.2, .5, .6) has cycle birth .6; to reach birth .4 a tree edge must move too, to (.2, .4, .4): ℓ∞\ell_\infty distance .2, as Theorem 1 states, but ℓ2\ell_2 distance .224. On the EEG graphs the naive lift, which moves only the rejected edges, fails in all 240 windows of subjects 66–85 for the target "every cycle birth lowered by .01". Exactness is thus a property of this map and this metric, not of sorting. Its consequence for the paper: a counterexample found in lifetime space is a graph, so each certified accuracy is a value, not a bound.

Q1, first part: signal beyond the sorted weights. The paper claims none and does not need one. This filtration and similar ones are used as persistent homology in the literature above, and the question of the paper is whether a model that reads such a feature can be verified without loss; D.2 states that "the stronger named-edge results limit any claim of predictive superiority of global PH". Note that 76.81 against 76.11 compares an MLP with a DAG. With the head held fixed (the four heads that Tables 6–7 train on both features, frozen; balanced accuracy in %, subjects 66–85):

HeadH₁ profileAll edges, sortedDifference [95% interval]
Logistic regression71.6766.25+5.4 [+1.3, +9.6]
Linear SVM76.2567.08+9.2 [+2.9, +15.0]
Gradient boosting74.5873.33+1.3 [−4.6, +6.7]
MLP75.4276.81−1.4 [−4.3, +1.4]

The sign depends on the head, and for the SVM on the solver (dual fit: +2.5 [−1.3, +6.3]); the four comparisons are uncorrected, and we read no signal into them. Similar accuracies are to be expected on K64K_{64}, where the profile is the sorted edge vector without its 63 spanning-tree entries.

References. H. Lee et al., IEEE TMI 31(12), 2012. T. Songdechakraiwut et al., ICLR 2022. T. Songdechakraiwut, M. K. Chung, Ann. Appl. Stat. 17(1), 2023. B. Rieck, C. Bock, K. Borgwardt, ICML 2019. M. Horn et al., ICLR 2022. J. Immonen, A. H. Souza, V. Garg, NeurIPS 2023.

Q1 (second part): what survives a clique filtration, and what it gives on the EEG graphs

Main point. For H₀ nothing is lost. For H₁ the clique filtration keeps a factor-2 certificate and loses exactness, and on the EEG graphs this costs both accuracy and the certified number.

What survives. Let a head read the clique (Vietoris–Rips) filtration of the same weighted graph, where a triangle enters at its largest edge.

  1. 0D: the exact result, verbatim. H₀ depends only on vertices and edges, so Theorem 2 (F.1) applies unchanged: exact image, isometric lift, equal radii.
  2. 1D: a sound certificate with a factor 2. Moving the edges by at most δ\delta moves the diagram by at most δ\delta in bottleneck distance and the sorted lifetimes by at most 2δ2\delta. A query that is constant on the lifetime ball of radius 2ϵ2\epsilon is certified at edge radius ϵ\epsilon (for persistence landscapes the constant is 1).
  3. 1D: no exactness, and the factor 2 is attained. Join two vertices by three paths of length two born at 0 and by one edge born at tt, with 4ϵ≤t<1/24\epsilon\le t<1/2. The edge fills three triangles at once, so both cycle classes die together and the profile is (t,t)(t,t). Within edge distance ϵ\epsilon the second lifetime can fall by 2ϵ2\epsilon, so the constant is attained. The target (t+ϵ, t−ϵ)(t+\epsilon,\,t-\epsilon) is at profile distance ϵ\epsilon but needs edge distance 2ϵ2\epsilon, so exactness is lost: a query that separates the two is certified at radius ϵ/2\epsilon/2 while its true radius is 2ϵ2\epsilon. This is the mechanism of A.4 in an actual clique filtration.

What is lost with exactness.

Graph filtration (Theorem 1)Clique filtration (stability only)
Input radius from a feature radius ρ\rhoexactly ρ\rhoat least ρ/2\rho/2; slack unknown
A counterexample found in feature spaceis a graph at the same distanceneed not be attained by any graph in the ball
A correct case that is not certifiedhas a graph counterexample"not robust" or an artefact of the enclosure: feature space cannot tell

Table 3 and A.4 name this as the boundary of the claim; we will add statements 1–3 there.

On the EEG graphs. We computed H₁ of the clique filtration of the measured graphs (a median of 29 classes per window) and trained the heads of Tables 6–7 on it with the same protocol. Sorted lifetimes, fixed first, stayed near chance (50–56%): a lifetime is a difference of two edge values and does not see the level of connectivity. Persistence landscapes (Bubenik, 2015), which keep it, were then added and selected on the validation participants. Balanced accuracy (%), subjects 66–85:

HeadGraph filtration (paper)Clique, landscapes
Logistic regression71.6760.42
Linear SVM76.2559.58
Gradient boosting74.5867.50
MLP75.4262.22
Boolean DAG76.1165.69

Certified accuracy of a DAG, % of all cases:

ϵ\epsilonDAG of the paper (graph filtration)DAG on clique landscapes
.0167.78[0.00, 25.69]
.0260.56[0.00, 10.97]

The excluded setting is 7–17 points behind for each of the five heads of Tables 6–7 (paired intervals exclude zero for four of them), and the certified accuracy of its DAG is at most 25.7%, against the exact 67.78% of the DAG of the paper; where it lies below that bound cannot be decided. The upper end is firm: graphs inside the ball refute 288 of the 473 correct DAG cases at ϵ=.01\epsilon=.01. The lower end is 0: the stability bound certifies no window, for the DAG as for the logistic and SVM heads, because it is a coordinate-wise box, and a tighter set needs knowledge of the image, which is what Theorem 1 supplies for the graph filtration. The other 185 cases stay open, with no certificate and no counterexample, and we do not count them as fragile. Under the graph filtration every correct case ends, at the same ϵ\epsilon, with a proof (488) or a counterexample graph (60).

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

The paper studies input realizability for persistent-homology features on graphs under a specific, one-dimensional preterminal filtration in which all H1 intervals die at time one and edges have independent, bounded birth-time perturbations. The main theoretical result proves an exact image identity for ordered H1 lifetimes: the ℓ∞ ball in input edge-birth space maps exactly to the ordered ℓ∞ ball around the nominal lifetime vector, and every target has a constructive input preimage at the same distance. This yields an exact reduction of robustness verification for any frozen lifetime-only query to a purely ordered-lifetime problem, with a constructive lift back to input graphs. The paper instantiates a verification interface with jointly learned affine predicates and a hard Boolean DAG, evaluates controlled reductions, and demonstrates certified verification with tight intervals and explicit counterexamples on EEG connectivity graphs.

Critical strengths
  1. Establishes an exact image identity and minimum-distance lift for ordered H1 lifetimes under a precise filtration and metric contract (preterminal dimension ≤ 1, completion at 1, uniform ℓ∞ clipping). This strengthens standard stability bounds (enclosures) to exact realizability with constructive witnesses.

  2. The reduction shows that, for frozen lifetime-only queries, the exact input flip-radius equals the exact lifetime-space flip-radius; thus graph variables can be eliminated from the verification search without loss in this contract.

  3. Controlled experiments (TopoLogic) isolate the reduction and compare ordered-domain verification to raw-input SMT, quantifying timeouts and bounds, and showing agreement with independently replayed input counterexamples.

  4. Input realizability for topological features is a central, under-explored issue in certified robustness; showing exact reduction and constructive preimages under a natural graph-filtration contract is impactful.

Critical weaknesses
  1. The exact identity relies on strong assumptions: preterminal dimension ≤ 1, completion at time 1 (all H1 deaths at 1), uniform ℓ∞ clipping, and independent edge-birth perturbations; more general filtrations (e.g., variable deaths, higher-dimensional complexes) or nonuniform per-edge budgets may break exactness.

  2. Baselines are limited to ordered/raw SMT and enumeration; comparisons to mainstream certification techniques (e.g., convex relaxations or randomized smoothing adapted to this domain) are not attempted, though the authors correctly note threat-model differences.

Questions for authors
  1. The EEG verification budgets are substantial. Which parts dominate (SMT vs rational LP refinements vs replay), and what engineering changes (e.g., caching the sorted order and forest pass across bisection calls) most reduce runtime?

  2. What is the precise role of triangles in practice? You state preterminal dimension ≤ 1 is the theorem’s assumption and triangle-freeness is an implementation control; do the conclusions still hold if triangles are allowed but treated as unfilled (i.e., a one-skeleton up to time 1), and how would early two-simplices (preterminal deaths) break the argument?

6 comments

Summary of our reply

We thank the reviewer for the careful reading. The theorem, the verifier, the frozen models and the 720 certificates are unchanged by this discussion. All new numbers count misclassified cases in the denominator, and we report those that do not favour our models.

  1. W1, assumptions. Each assumption has one job in the lift, and the submission states for each how far exactness extends and where it fails (Table 3, Proposition 10, A.4, F.6–F.8). Relative budgets and uniform balls after Fisher's z are co-ordered (shown in that comment), so Proposition 10 covers them exactly; budgets tied to the identity of an edge are not covered.
  2. W2, mainstream certification. Bound propagation, branch-and-bound and attacks run inside the reduction, and Theorem 1 turns every counterexample they find into a graph: the DAG's 67.78% is an exact value, and the MLP lies in [64.72, 66.11]%. Randomized smoothing, run on both cohorts: on the same DAG, exact verification certifies at least 16.7 points more on subjects 66–85 and 10.2 on 86–109; heads trained under noise and smoothed reach the DAG's level on 66–85 and exceed it on 86–109. We claim no robustness advantage of the paper's models.
  3. Q1, runtime. LP work dominates, not SMT: LP feasibility and exact rational dual arithmetic take 48% of the timed records (predicate bounds 25%, replay 6%, Boolean SAT 0.1%). Deciding each threshold instead of locating every radius takes 3,887 s for all 720 cases at both thresholds, replay included, instead of 164,099 s, and certifies the same cases (one and three correct cases that the paper refutes stay undecided at 120 s; the hosts differ).
  4. Q2, triangles. Yes: unfilled triangles are covered, and the EEG complex on K64K_{64} is of this kind (Section 2.1, A.1). Early 2-simplices make the image identity false, not only its proof (A.4); a sound certificate survives.

The feature is in published use for brain connectivity, including at ICLR 2022 (Songdechakraiwut et al.), and graph learning reads cycles of graph filtrations the same way: born with an edge, never filled (Rieck et al., ICML 2019; Horn et al., ICLR 2022; Immonen et al., NeurIPS 2023). Prior work states a forward bound (Songdechakraiwut & Chung, 2023); we know of no statement of the converse.

The paper contributes an exactness theorem for a persistent-homology feature in published use, with its boundary located on both sides (the joint 0D/1D profile; clique filtrations), and a verification interface that runs from a measured graph to a certificate replayed in exact arithmetic at β=1,953\beta=1{,}953.

For the final version: a third column for Table 3 and budget examples in F.4 (W1); the verifier and smoothing tables in Appendix D (W2); the stage breakdown and both cost regimes in Table 10 and D.7 (Q1); the "what survives" table in A.4 and one sentence each in Section 2.1 and A.2 (Q2, Q1).

We would be glad to address any remaining concern before the discussion closes.

W1: the assumptions of the exact result

Each assumption has one job in the proof, and for each the submission states how far exactness extends and where it fails (Table 3).

Why they appear. Kruskal's pass in nominal edge order rejects β edges; their births are the profile. The lift sets every edge to the running maximum of its lower endpoint and the target births at earlier rejected positions (proof sketch after Theorem 1). This gives a graph in the ball with the target profile because (i) one edge order is valid on the whole ball, which uniform clipping provides, and so do co-ordered intervals; (ii) every lifetime is one minus a birth, which dimension ≤ 1 before one and completion at one provide; and independent coordinates let each edge move to its running maximum.

AssumptionExactness extends toFails; what remainsWhere
Preterminal dimension ≤ 1any graph with unfilled triangles (EEG: K64K_{64})2-cells before one: our Q2 reply§2.1, A.1
All H₁ deaths at one—variable deaths: identity false, target (2/5, 0); coordinatewise enclosure soundA.4
Uniform clipped ℓ∞ ballco-ordered intervals, e.g. relative budgetsbudgets tied to an edge's identity: identity false (three paths); enclosure soundProp. 10, §2.1
ℓ∞ metric—ℓ₂: false already on a triangle (.224 against .2)reply to WDZa, W1
Independent edge birthsdeclared polytopes of inputs; conserved flows—F.6–F.8
One H₁ profilethe H₀ profile alone (Theorem 2)H₀ and H₁ jointly: false (F.3); classification in our reply to WDZa, Q3F.1–F.3

Every entry is a proved extension or an explicit counterexample: the boundary of exactness is located, not assumed.

Non-uniform budgets are largely covered. Proposition 10 needs only both endpoint sequences to be nondecreasing in one edge order. Every budget whose two endpoints are nondecreasing functions of the edge value qualifies, under any tie-breaking: relative budgets [xe(1−r), min⁡(1,xe(1+r))][x_e(1-r),\,\min(1,x_e(1+r))], or a uniform ball after Fisher's z or any increasing reparametrisation, mapped back and clipped. The exact image is again an ordered interval set. An exact rational check on 3,200 random boxes of these kinds over graphs with up to eight vertices (for Fisher's z and the logit, on endpoints rounded from floating point, and again in floating point), about 1.7 million forward and converse checks, found no violation. Not covered: budgets tied to the identity of an edge, such as a noise level per electrode pair; the enclosure stays sound there.

Coupled inputs: sound, and exact where declared. A certificate on the independent ball holds on every admissible subset of it: independence costs completeness, not soundness. For a declared polytope of inputs the nearest preimage is computed exactly over spanning-tree regions (F.6–F.7; for K4K_4, 96 regions instead of 720 orders); under flow conservation the exact image is strictly smaller than the ordered box (F.8, Proposition 15).

We will add the third column to Table 3 and the budget examples to F.4.

W2: mainstream certification methods

Bound propagation, branch-and-bound and attacks are not alternatives to the reduction: they run inside it, and Theorem 1 turns every counterexample they find into a graph.

A certificate on the profile ball holds for every graph in the edge ball (forward stability, standard). A counterexample on the ordered profile ball, the exact image, is the profile of a graph at the same ℓ∞ distance, built in linear time after one sort (A.2). A complete lifetime-space verifier is therefore complete for graphs, and every upper bound below is a statement about graphs; with forward stability alone it would concern feature vectors that need not be profiles of any graph.

Verifiers of increasing strength on each frozen head; 720 cases (three seeds × 240 windows, subjects 66–85), misclassified cases in the denominator. Box is the stability box {z:∥z−L(x)∥∞≤ϵ}∩[0,1]β\{z:\|z-L(x)\|_\infty\le\epsilon\}\cap[0,1]^\beta, all that forward stability gives a standard verifier; exact image is the same verifier inside the reduction:

MLP of Table 7, ε = .01Box (standard input)Exact image (reduction)
Global Lipschitz bound0.00%0.00%
Linear ReLU relaxation (CROWN-style)23.33%42.50%
+ optimised slopes55.69%62.92%
+ branch-and-bound on ReLU signs61.11%64.72%
Upper bound from verified counterexamples65.42%66.11%
Boolean DAGε = .01 / .02
Lipschitz bound: no predicate can flip33.61% / 10.42%
Relaxation RBoolR_{\rm Bool} (Table 11), box, 30 s≥ 65.97% / ≥ 52.64%
Complete search, box67.50% / 59.44%
Complete search, exact image (paper)67.78% / 60.56%
  • Verifier strength matters most: at ε = .02 the four DAG rungs certify 75, ≥ 379, 428 and 436 of 548 correct cases. The relaxation rung is already part of the paper's pipeline: RBoolR_{\rm Bool} runs on every case (the "Boolean-bound preparation" row of Table 10).
  • The domain matters most for cheap relaxations: the exact image adds 138 MLP certificates to the single-pass relaxation and 26 after branch-and-bound; for the complete DAG search, 2 and 8 (see our reply to Reviewer WDZa, Q1).
  • The theorem closes the gap rather than enlarging radii. The ordering itself is elementary, since every profile is sorted; what Theorem 1 adds is that no tighter domain exists, since every point of the ordered ball is a graph. So the DAG's 67.78% is an exact value (each correct case it does not certify is refuted by a graph in the ball), and the MLP's 10 open cases are verifier incompleteness alone.

The MLP verifier is our implementation of these standard techniques, every bound recomputed in integer arithmetic. Randomized smoothing does not run inside the reduction; it is in the next comment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.