- 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 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 input ball maps exactly onto the ordered 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 and a replayed graph counterexample at each upper endpoint.
Critical strengths
-
Correct, clean, constructive exactness result with an operational payoff.
-
Rigorous and transparent verification and evaluation methodology.
Critical weaknesses
-
The core theorem has limited topological significance. Under the declared filtration (one-dimensional preterminal complex, all deaths at 1), the ordered lifetimes are just 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 , is 1,953 of the 2,016 sorted edge weights. The experiments are consistent with this: sorted-all-edges MLP gets 76.81%, the 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.
-
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
-
On the EEG models, what are the certified lower bounds and BCA$_{\text{open}}(.01)$ if verification uses the unordered enclosure box instead of ? If the gap is small, please explain what the exact-image theorem buys beyond counterexample construction.
-
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.
-
Under your filtration, 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?
-
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
W1: significance of the theorem
The description is correct; the conclusion does not follow. 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:
| Feature | Always a preimage at exactly the feature distance? |
|---|---|
| All edge weights, sorted | Yes, in every (classical) |
| 1D profile alone | Yes in (Theorem 1); no in |
| 0D and 1D profiles together | No in , 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): distance .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 of the barcode of a graph is the barcode of a graph within 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 . 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 in profile space and in input space, for any : the gap can be half the weight range, and the ratio is unbounded as .
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 .)
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.
We thank the reviewer for their careful reading and thoughtful critique.
Summary of our reply
The reviewer's description is correct: L 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:
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.
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 L 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.
If a claim still reads as overstated, we would be grateful if the reviewer pointed to it.