acceptodds
Under review as a conference paper at ICLR 2027

Binary Measure Sketches for Persistent Homology: All-Scale Interleavings and Memory Lower Bounds

Abstract

Persistent homology summarizes geometry across scales, but computing it from a compressed representation requires knowing which geometric information must survive compression. For distribution-sensitive filtrations, this question concerns both distances and the masses they organize, rather than the number of distinct distance values alone. We introduce binary measure sketches that aggregate a sample into weighted cells and replace representative coordinates by calibrated binary geometry. For finite distance-to-a-measure weighted Vietoris–Rips persistence, we show that mass-preserving aggregation and uniform distance distortion compose into an all-scale interleaving with error \(2\rpart+\eta\), separating partition loss from coding loss without an additional penalty for the scale axis or homological degree. A complementary packing of degree-zero persistence diagrams gives a topology-specific memory lower bound, showing that the information required by the topological output cannot in general be eliminated by quantizing distances. Experiments examine the resulting error decomposition and the utility of the retained representation. Together, these results connect the geometry a sketch preserves to the persistence it can recover, providing a principled basis for allocating representative and coding budgets.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
persistent homology, distance-to-a-measure, Vietoris--Rips 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_ZpRtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The authors introduce a way of encoding a dataset into a weighted binary sketch and then using that sketch to compute persistence over the dataset. From what I understand, it consists of four steps: (1) The dataset gets mapped to a weighted sparse representation (2) the weighted representation gets mapped to a weighted binary representation (3) Compute the Rips complex over this new binary representation using Hamming distance (4) Use the Max-DTM Rips Filtration to compute persistence. The authors show several associated theoretical results as well, namely, that this new persistence diagram is stable w.r.t. the persistence diagram generated via max-DTM-Rips for the original dataset (in terms of bottleneck distance). They also show that the two persistence diagrams are ϵ\epsilon-interleaved where ϵ\epsilon depends on the maximum distance between any xx and its assigned cell.

Critical strengths
  1. The theorem statements seem reasonable and I skimmed through the proofs in the appendix (although I did not read them carefully). I could find no error.
  2. I found the experiments helpful in increasing my understanding of their theoretical results. In particular, I found figure 2D helpful in understanding how their theorem bound works in practice, it is interesting that the authors observe something in practice that is much better than what their theory predicts.
Critical weaknesses

I think the writing could use some work and the authors could do a better job of contextualizing why their results are important. While topological data analysis is nothing new at ICLR, I think a majority of the ICLR audience is unfamiliar with the concepts in TDA. At several points in the paper, the authors directly use terminology without briefly first explaining the concept. For instance, they do this with DTM throughout the introduction before explaining the concept and why it would be important in the related work.

Furthermore, I still do not fully understand why one would be interested in a binary measure sketch. It seems like one could just directly compute persistence over the weighted representatives instead of taking the extra step of finding a binary sketch.

Questions for authors
  1. Can the authors clarify why it is necessary to go through the binary encoding step?
  2. Is there any dependence on dimension in their bounds? For instance, does rpartr_{\mathrm{part}} change as dimension increases?
1 comment

We thank the reviewer for the review and positive assessment of soundness.

A1: We revised Section 1 to explain motivation and terminology first: recovering components and loops after coordinates cannot be retained or transmitted. DTM is the root mean square distance to the nearest β\beta fraction of probability mass. Together with pairwise distances, it determines filtration entry times, so compression must preserve masses and control geometry. Before the theorems, Figure 1 explains sample → mass-weighted representatives → binary geometry → persistence, and BMS is defined at first use.

A2: We clarified the storage benefit in Section 1 and Section 6: coordinates require Md values, while BMS uses Mb geometry bits, with masses and metadata accounted for separately. Savings can retain more representatives. The state also supports recomputing DTM and persistence for a chosen β\beta after discarding coordinates. Angular or unit-sphere chordal targets need codes and masses; general Euclidean targets additionally need radial information. Figure 2B, main-text Table 2, and the table below give direct evidence: at 4 KiB on Fashion-MNIST, BMS retains M=102, b=256; int8 fits at most five representatives. E7 selects int8 M=1 among all M=1–5 using development error. BMS/int8 mean joint errors are 0.0638/0.3336, with BMS lower in all ten evaluations. The joint-error improvement at this cap directly demonstrates the storage value of binary geometry for the declared topology target. Table R5. Actual allocations and errors on Fashion-MNIST at the 4 KiB cap.

MethodMbActual bytes BMean joint E
BMS1022564,0960.0638
FPS-F64N/A—N/AN/A
FPS-F161—1,5920.3336
FPS-INT81—8160.3336

A3: Dimension enters through coverage and storage; perturbation coefficients do not explicitly depend on ambient dimension. At fixed M, isometric embedding preserves rpartr_{\mathrm{part}}, while increased intrinsic complexity can worsen coverage. We added rpart≤2D(C/M)1/sr_{\mathrm{part}}\leq 2D(C/M)^{1/s} under a covering model in Section 6 and Section N.10, exposing covering dimension s. Figure 11 and Figure 12 separate coordinate growth from changed geometry; Figure 2 adds real high-dimensional data. Coordinate count d can increase storage without changing intrinsic distances, and construction/encoding costs can still depend on d.

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

The paper proposes binary measure sketches (BMS). A sample is partitioned into M cells with exact aggregated masses, and the representatives are encoded as b-bit sign codes. Max-DTM–Rips persistence is then computed from the codes and masses alone. Theorem 2 shows that a uniform distance distortion η gives an η-interleaving at all scales and in all degrees. Theorem 4 combines this with a mass-preserving fibre quotient to give an end-to-end bound of 2r_part + η. Theorem 6 gives an H0H_0 lower bound. Experiments cover a synthetic circle, two JavaPlex point clouds and graph classification under byte caps.

Critical strengths
  • Clean deterministic guarantees. The error splits into a partition term (2r_part) and a coding term (η). A single uniform distortion event certifies all scales and degrees. With fixed masses there is no β^{-1/2} loss, and Theorem 2 does not need the triangle inequality for the reconstructed dissimilarity.
  • Careful scope and evaluation. The paper is clear about memory accounting and construction cost. The lower bound holds for any decoder. The graph study uses grouped CV, corrected tests and Holm adjustment, and reports inconclusive results as such.
Critical weaknesses
  • Limited novelty, and related work is missing. Each ingredient is standard: sign hashing with Hoeffding plus a union bound, sup-norm stability of filtration values, the triangle inequality, and contiguity. The main text should state precisely what is new. Work on compressing the DTM with a small weighted point set (witnessed k-distance, the k-PDTM) and sparse weighted DTM filtrations (Buchet et al.) is not compared against.
  • The certificate gives little practical guidance. r_part is a worst-case radius, so it is sensitive to outliers, which is at odds with the robustness motivation for the DTM. The certificate is about well above the observed error. There is no model of r_part(M) in terms of n or dimension.
  • Limited experiments and presentation. The data are small: d=2, 8 and 25, with M=128. In the graph study, the caps never bind for BMS (maximum 2,344 bytes vs. caps ≥32 KiB), and BMS is well below simple degree-histogram baselines.

The paper is 57 pages and dense, and the main text relies heavily on the appendix. A journal or a much tighter conference version may suit it better.

Questions for authors
  • Which results are new, as opposed to direct applications of existing stability results? Has binary hashing or binning been used for Rips persistence before?
  • At equal bytes, how does BMS compare with exact FPS using fewer representatives, and with 8-bit or float16 coordinates?
  • How do these comparisons change as the ambient dimension grows? Is there a crossover dimension?
2 comments

We thank the reviewer for the review and specific questions.

A1: We revised Section 1 to separate our results from standard proof tools. First, exact fibre masses give Fx,dˉ,u(r)=Fπ(x),dC,a(r)F_{x,\bar d,u}(r)=F_{\pi(x),d_C,a}(r). Fixed projection and section maps yield a persistence-module isomorphism compatible across scales. Stability of recomputed DTM weights then gives the original-input-to-sketch bound 2rpart+η2r_{\mathrm{part}}+\eta in Theorem 4, simultaneously across scales and degrees. Decoded dissimilarities need not satisfy the triangle inequality; actual H₀ diagrams attain coefficient one on η\eta in Theorem 2. Second, under its stated η,β,ϵ\eta, \beta, \epsilon conditions, Theorem 6 constructs 2q2^q actual H0H_0 diagrams separated by at least 4$\epsilon$. Any deterministic encoding guaranteeing error at most ϵ\epsilon requires q bits, regardless of decoder. Different distance matrices may have identical persistence, so geometric reconstruction packing cannot replace this output-level argument. Random hyperplanes, stability, and contiguity are tools; the exact mass quotient, recomputed-weight guarantee, and output-level information constraint are the specific conclusions.

A2: We added and expanded these comparisons in Section 2. Discretized Rips geometry has precedents: shifted integer lattices provide grid approximations [6], while Adamaszek–Adams study an already-Hamming hypercube [5], rather than random hashing of arbitrary samples. Our claim concerns a probability-mass-preserving binary state approximating finite max-DTM–Rips, not binary representation or binning itself. Section N.11 compares targets, weights, retained states, and guarantees. Witnessed k-distance and k-PDTM approximate ambient distance functions using weighted barycenters or power balls [1,2]; Buchet et al. study weighted and sparse Rips for measures [3]; Anai et al. provide a max-form weighted rule [4]. Our cell probability masses determine recomputed DTM radial distributions and differ from power/variance weights. The decodable state after coordinates are discarded and the output-level bit bound provide further distinctions. These comparisons specify the problem solved by our results and distinguish it from prior guarantees.

A3: We clarified in Section 7.2 that 2rpart+η2r_{\mathrm{part}}+\eta certifies compression of a given measure; DTM stability under changing the measure addresses another comparison. Outliers enlarging poorly covered regions do not contradict that stability. With Δ=2rpart+η\Delta=2r_{\mathrm{part}}+\eta, every finite bar longer than 2$\Delta$ has a counterpart with endpoint errors at most Δ\Delta. If 2rpart≥τ2r_{\mathrm{part}}\geq\tau, increasing b alone cannot certify error below τ\tau.

At 10.16% contamination and b=100, increasing M from 16 to 64 reduces mean total error from 0.6752 to 0.1483 (table below). See Table 10 and Figure 13. Table R2. Coverage investment at fixed code length.

Realized outliers %Mrpartr_{\mathrm{part}}η2rpart+η2r_{\mathrm{part}}+\etaTotal E
0160.22390.26490.71270.2953
0320.12400.28410.53210.1347
0640.06440.30030.42900.0836
01280.00000.30790.30790.0735
10.15625160.72600.88142.33330.6752
10.15625320.19750.88231.27730.2413
10.15625640.08230.89021.05490.1483
10.156251280.00000.89020.89020.1229

A4: We added actual-byte-cap comparisons to Section 7.1. Figure 2A/B and the table below report every cap. BMS has lower mean joint error E=max⁡{dB(H0),dB(H1)}E=\max\{d_{\mathrm B}(H_0),d_{\mathrm B}(H_1)\} in 19/20 feasible dataset–cap–baseline comparisons. BMS/int8 errors are 0.0653/0.2513 on Digits at 2 KiB and 0.0638/0.3336 on Fashion-MNIST at 4 KiB, with BMS lower in all ten pairs for both. Table R3. All byte caps after optimizing coordinate representative counts.

DataCap KiBBMSFPS-F64FPS-F16FPS-INT8
Digits10.18540.34270.34270.3427
Digits20.06530.34270.34270.2513
Digits40.06140.34270.25050.1140
Digits80.04120.34270.10770.0393
Fashion-MNIST10.1824N/AN/A0.3336
Fashion-MNIST20.0829N/A0.33360.3336
Fashion-MNIST40.0638N/A0.33360.3336
Fashion-MNIST80.05440.33360.33360.3336
See details in Section 7.1; Figure 2A/B (joint error), C/D (H₁); Section N.2, Section N.6, and Section N.7.

A5: We clarified Section 7.4: the graph study tests predictive utility. Its 2,344 B maximum is below the smallest 32 KiB cap and cannot establish a binding-budget curve. The graph figure now appears in Appendix M (Figure 9); Figure 2A/B directly tests actual-cap fidelity to the same target diagrams.

A6: We added a covering-number model to Section 6, proved in Section N.10. If N(X,r)≤C(D/r)s)and�0�and(dB≤4D(C/M)1/s+ηN(X,r)\leq C(D/r)^s) and �0� and (d_{\mathrm B}\leq 4D(C/M)^{1/s}+\eta; M=n gives rpart=0r_{\mathrm{part}}=0 [7]. The general theorem uses measurable finite-sample coverage and applies to arbitrary finite metric measures. A rate requires the additional geometric assumption: s describes coverage difficulty, while increasing n alone need not improve fixed-M coverage.

A7: The crossover depends on budget and geometry. Added E2 separates isometric circle embeddings (Figure 11) from uniform-sphere samples (Figure 12).

Table R4. Isometric-circle H₁ error at 8 KiB, including every tested dimension.

Dimension dBMSFPS-F64FPS-F16FPS-INT8
20.01280.00000.00010.0021
80.00840.00080.00010.0015
250.03340.00950.00010.0011
640.00760.41840.00720.0013
1280.01200.71310.06200.0074
2560.00750.71310.41840.0625

A8: We reorganized the main text around what retained state permits certified topology recovery after coordinates are discarded. Section 1 now explains persistence, DTM, and BMS before the mass quotient, coding stability, and output-level bound; Section 2 clarifies prior work. Experiments now lead with actual-cap fidelity (Figure 2), distinguishing joint gains from degree-specific results.

[1] Guibas, L. J., Morozov, D., and Mérigot, Q. Witnessed k-Distance. Discrete & Computational Geometry 49(1):22–45, 2013.

[2] Brécheteau, C. and Levrard, C. A k-points-based distance for robust geometric inference. Bernoulli 26(4):3017–3050, 2020.

[3] Buchet, M., Chazal, F., Oudot, S. Y., and Sheehy, D. R. Efficient and Robust Persistent Homology for Measures. Computational Geometry 58:70–96, 2016.

[4] Anai, H., Chazal, F., Glisse, M., Ike, Y., Inakoshi, H., Tinarrage, R., and Umeda, Y. DTM-Based Filtrations. SoCG 2019, LIPIcs 129, 58:1–58:15.

[5] Adamaszek, M. and Adams, H. On Vietoris–Rips complexes of hypercube graphs. arXiv:2103.01040, 2021.

[6] Choudhary, A., Kerber, M., and Raghvendra, S. Improved Approximate Rips Filtrations with Shifted Integer Lattices. ESA 2017, LIPIcs 87, 28:1–28:13.

[7] González, T. F. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science 38:293–306, 1985.

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

The manuscript targets persistent homology, which aims to compress a metric dataset while maintaining expressiveness, specifically in combination with distribution-sensitive filtrations. The authors call their approach "Binary Measure Sketch". The weighted datapoints are partitioned into representatives, while maintaining their geometry information. These representatives are placed into a temporary coordinate system, which is afterwards encoded into a hamming binary code to compress that information. The resulting representation is then turned into persistent modules and processed using standard filtration techniques. The authors provide bounds for the geometric loss induced by the radius during the first step as well as for the distortion from the binary sketch during the third step and proof them exact masses are preserved. Additionally the article derives a lower bound for the necessary memory as well as analyze the necessary compute and memory in general. This is followed by an empirical evaluation on two different experiments with a few baselines, where quite a few number of aspects are considered.

Critical strengths
  • the article is well-written and understandable, albeit very dense at times
  • the approach seems to relevant and how datapoints from measurements can be "compressed" while still maintaining enough expressiveness for analysis is a relevant topic in my opinion
  • reasonable evaluation with two different experiments with a comparison with a few baselines and detailed analysis as well as theoretical observations and proofs
Critical weaknesses

I have not identified directly any weaknesses, however my knowledge in this area is very limited, so this might be more of a reflection on myself than the manuscript. From my understanding, the approach does not seem to scale well, so it is unclear how practical the proposed approach is, which is however not necessarily a hindrance for publication. I choose conservatively a weak accept, because of my little knowledge of the area, so I am not that confident. I would not object to a accept instead.

minor:

  • If I understand correctly BMS is the name used during the evaluation for the approach in question. This should probably made clear in the main body as well not just the appendix.
Questions for authors
  • What does "representative set does not change between bits" (line 161) mean?
  • How practical is proposed compression solution and where could it be applied? From what I understand from the appendix, the used datasets have a few thousands datapoints, so it seems the solution does not scale that well as already acknowledged in the main article. Do you have any notion how scalability can be improved or is this an inherent limitation of the proposed approach?
2 comments

We thank the reviewer for recognizing the soundness and relevance of the work. We clarify the representation and use full-input experiments to explain scalability and intended applications.

A1: We revised Section 1 to define binary measure sketches (BMS) at first use, explain persistence through components, loops, and voids, and introduce DTM as the root mean square distance to the nearest β\beta fraction of probability mass. It now asks what compressed state permits certified topology recovery after coordinates are discarded. Figure 1 presents sample → mass-weighted representatives → binary geometry → persistence, establishing the method and motivation before the technical details.

A2: We clarified Section 3.2: once the partition and M representatives are fixed, each bit is a new random-hyperplane measurement of those same representatives. Their locations, partition, and masses remain unchanged. Increasing b improves probabilistic control of coding error η\eta while leaving 2rpart2r_{\mathrm{part}} fixed; realized errors need not decrease monotonically. The text now distinguishes this operation from jointly allocating M and b under a byte cap.

A3: BMS separates input size n from retained topology-computation size M, supporting storage or transmission of weighted geometry. Added E4 constructs sketches from two complete 15,000-point JavaPlex inputs and computes representative-level H₀/H₁. At M=128, b=100, retained payload is 2,640 B; optical/range construction takes 0.069/0.158 s and coded persistence takes 0.337/0.303 s on average (table below; Section N.5). Input size is therefore not limited to a few thousand.

Table R1. Full-input construction and representative persistence.

DataInput nPayload BBuild sPH sCoding E
optical15,0002,6400.0690.3370.085
range15,0002,6400.1580.3030.111

E4; M=128, b=100; means over three repetitions. E is measured against exact diagrams of the same weighted representatives; payload bytes are not peak working memory. All settings: Table 11.

Thank you for the revised manuscript and the clarifications. After reading the answers, the main body of the revised manuscripts and the other reviews, I will maintain my score as it is already higher then the other scores.

minor note: In the ethical statement, the abbreviation TDA is used, but it is never introduced (topological data analysis).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.