Computing and Learning on Combinatorial Data

Simon Zhang

REVIEW 3 major objections 4 minor 300 references

Computing and Learning on Combinatorial Data

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

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

Pith's one-line read This dissertation claims that persistence computation is mostly local—not algebraic—and uses that locality to build fast GPU barcodes, near-linear Wasserstein approximations, and better graph and hypergraph learners.

desk verdict A credible dissertation that compiles five peer-reviewed papers; the new-to-this-document background contains a false proposition, and the headline GPU speedup claim rests on a plausible but unvalidated heavy-hitter condition. read the letter →

arxiv 2502.05063 v1 pith:P5SHM2YL submitted 2025-02-07 cs.AI cs.DMcs.DS

Simon Zhang This is my paper · ORCID

classification cs.AIcs.DMcs.DS MSC 55N3168T0568U0505C6568W10

keywords persistenthomologyVietoris-RipsfiltrationapparentpairsGPUparallelcomputation1-Wassersteindistancegraphrepresentationlearninghypergraphlinkpredictionsymmetrybreaking

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

Connectivity, not linear algebra, does most of the work in computing persistence. This dissertation claims that most persistence pairs in Vietoris-Rips filtrations are apparent pairs—pairings determined by which simplex is the oldest cofacet of another—so they can be found in parallel without any matrix reduction. It builds that idea into accelerated software for persistent homology, a near-linear-time approximation of the 1-Wasserstein distance between persistence diagrams, an extended-persistence graph classifier, and a symmetry-breaking hypergraph link predictor. If the claim is right, the practical bottleneck in topological data analysis shifts from sequential algebraic reduction to local neighbor search, which is exactly what GPUs do well.

What carries the argument

The load-bearing object is the apparent pair. In a Vietoris-Rips coboundary matrix ordered by simplex diameter, a pair $(s,t)$ is apparent when $t$ is the oldest cofacet of $s$ and $s$ is the youngest facet of $t$; equivalently, the matrix entry $(t,s)$ has zeros everywhere to its left and below. The Apparent Pairs Lemma shows such pairs are already persistence pairs, so they can be identified in parallel from local neighbor information, with no matrix reduction. Around this core, the dissertation deploys three supporting devices: $\delta$-condensation followed by well-separated pair decomposition to sparsify the min-cost flow network for the 1-Wasserstein distance; a virtual cone node in extended persistence to resolve graph cycles in subquadratic time; and hyperedge-based symmetry breaking that lowers the symmetry of a hypergraph viewed through its universal cover.

What would settle it

Take a point cloud engineered to defeat locality—for example, uniform samples in a high-dimensional space with metric perturbations that spread diameters—and measure the apparent-pair fraction as $n$ grows; if it does not stay bounded away from zero, the heavy-hitter condition fails and the advertised speedups would vanish.

Watch

Extended reading notes

Core claim

On its own terms, the discovery is that persistence, though defined over a causal sequence of homology vector spaces, has most of its output fixed by the neighboring connectivity of the filtration rather than by algebraic operations. The technical form is the heavy-hitter theorem for apparent pairs: under the uniform sampling condition, for large $n$ a constant fraction of all persistence pairs in a Vietoris-Rips filtration are apparent, with matching lower bounds. Those pairs are read off directly from the coboundary matrix, and only the residual non-apparent submatrix needs sequential reduction. The same connectivity-over-algebra stance yields a near-linear-time $(1+\epsilon)$-approximation of the 1-Wasserstein distance between persistence diagrams, with the diagonal handled exactly, and it informs the graph and hypergraph learning chapters.

Load-bearing premise

The load-bearing premise is that real point clouds inherit the locality that uniform sampling guarantees, so that a constant fraction of persistence pairs are apparent pairs; if a dataset's geometry makes most pairs non-local, the GPU speedups do not transfer.

Editorial extensions

If this is right

For Vietoris-Rips filtrations on large point samples, most barcode pairs are apparent, so GPU parallel enumeration plus a small CPU submatrix reduction replaces full sequential matrix reduction.
The 1-Wasserstein distance between persistence diagrams can be approximated within $(1+\epsilon)$ in near-linear time with the diagonal handled exactly, avoiding the factor-2 distortion of finite diagonal sampling.
Extended persistence gives graph neural networks access to cycle structure that ordinary persistence cannot express, and the virtual cone can be simulated in subquadratic time.
Breaking hypergraph symmetry by adding hyperedges lowers the symmetry of the generalized Weisfeiler-Lehman-1 (GWL-1) aggregator and improves transductive higher-order link prediction whenever the testing automorphism group has more entropy than the training group.

Reading between the lines

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

Beyond the paper: if the locality principle is generic, similar apparent-pair-style shortcuts should accelerate persistence computations for alpha-shape filtrations and graph filtrations, not just Vietoris-Rips complexes.
Beyond the paper: the $\delta$-condensation and well-separated pair decomposition treatment of the diagonal could be adapted to other ground metrics or to multiparameter persistence, where the diagonal is replaced by a higher-dimensional set of comparable points.
Beyond the paper: the hypergraph symmetry-breaking idea is a general design principle—adding controlled asymmetry to a learning problem can help when the test distribution has more symmetry entropy than the training distribution; this could be tested on graph and knowledge-graph link prediction as well.

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.

Desk Editor's Note

read the letter

You should know two things about this one. First, the real substance is the five published papers it compiles: HYPHA and Ripser++ for GPU persistent homology, PDoptFlow for near-linear 1-Wasserstein approximation, GEFL for graph learning, and the hypergraph symmetry-breaking work. Those are genuine, peer-reviewed contributions, and the abstract is honestly conditional about them. Second, what is actually new in this manuscript -- the long background chapter and the categorical persistence framing -- is where the trouble is. Proposition 2.4.29 claims complementary subspaces are unique; that is false, and the proof just cancels subspaces in an equation. It is in expository material, so it does not infect the chapter results, but it is a factual error in a dissertation and should be fixed.

The larger soft spot is the one the stress-test flags. The abstract's central claim -- that much of the algebraic computation depends only on neighboring connectivity -- is quantified in Chapter 5 as the heavy-hitter theorem: under a uniform-sampling condition, a constant fraction of persistence pairs are apparent pairs. That is proved for uniform distributions, and the empirical curves show the apparent-pair fraction depends on geometry and filtration order. The dissertation does not report apparent-pair fractions on non-uniform, clustered, or multi-scale real datasets, where the fraction can drop below any constant. This is not an internal contradiction; it is an unvalidated domain condition at the center of the main speedup claim. It needs to be checked empirically before the abstract's generalization is taken at face value.

Two smaller caveats: PDoptFlow's optimality is conditional on a stated but unnamed conjecture, and Chapter 8's symmetry-breaking benefit assumes the testing automorphism group has more entropy than the training group. Both are disclosed, but both are load-bearing assumptions.

Overall: this is a dissertation compiled from solid prior work. The new material is mostly background, and it contains one false claim. The heavy-hitter premise is plausible but under-validated. It deserves serious referee time -- a defense committee or a reviewer should engage with it, ask for the missing experiments on non-uniform data, and require a corrected background chapter. I would not desk-reject it, but I would not accept it as-is either.

Referee Report

3 major / 4 minor

Summary. The dissertation proposes and evaluates computational and learning methods for combinatorial data. The main chapters present HYPHA and Ripser++ for GPU-accelerated persistent homology, PDoptFlow for approximating the 1-Wasserstein distance between persistence diagrams, GEFL for graph classification via extended persistence, and a hypergraph symmetry-breaking method for higher-order link prediction. The abstract's central thesis is that much of the algebraic computation in persistence depends only on neighboring connectivity, which enables CPU-GPU hybrid algorithms. The dissertation is largely a compilation of the author's prior peer-reviewed work, with background chapters on logic, algebra, topology, statistics, and combinatorial data.

Significance. If the central claims hold, the contributions are significant: HYPHA and Ripser++ address real performance bottlenecks in persistent homology, PDoptFlow offers a practical near-linear-time approximation with an exact diagonal treatment, and the GEFL and hypergraph methods target expressivity limitations of standard graph neural networks. Strengths include open-source software, substantial experimental evaluations, and theoretical results on apparent-pair heavy hitters, Wasserstein approximation bounds, and a characterization of GWL-1. The main caveat is that the headline CPU-GPU speedup claim is established only under a uniform-sampling locality condition, while the abstract states it without qualification; additionally, the background chapter contains a demonstrably false linear-algebra proposition.

major comments (3)

[Abstract; §5.4.5, §5.4.7, §5.6.9–§5.6.11; Tables 5.2, 5.4] The abstract's claim that 'much of the algebraic computation only depends on the neighboring connectivity of the data' is load-bearing and is not established in the generality stated. The heavy-hitter theorem for apparent pairs is proved under a uniform sampling condition in Section 5.4.5, with lower bounds reported under that condition in Section 5.4.7, while Sections 5.6.9–5.6.11 construct distance assignments with apparent fractions near 1/3 and 1/2, showing that the fraction is geometry- and filtration-order-dependent. The empirical speedups in Tables 5.2 and 5.4 are reported on uniform-like benchmarks. To support the abstract's generalization, the paper should either restrict the claim to the uniform-sampling regime or validate apparent-pair fractions and speedups on non-uniform, clustered, and multi-scale point clouds.
[§2.4, Proposition 2.4.29] Proposition 2.4.29 is false as stated: a linear subspace U of a vector space V generally has many complementary subspaces (for example, in R^2, the x-axis is complemented by any line not equal to itself). The proof's step 'U + W = V = U + W' implies W = W'' is invalid. This is a background result, not the main theorem, but it is a genuine mathematical error in a foundational chapter and should be corrected or removed.
[Chapter 1; Chapter 8] The motivation for hypergraph symmetry breaking is stated in Chapter 1 as 'Assuming the testing automorphism group is smaller, meaning having more entropy, then it would be beneficial to break the symmetry of the training hypergraph.' Neither 'smaller' nor 'entropy' is defined for automorphism groups in this context, and the direction of the implication is not self-evident. Since the method's expected benefit is argued from this asymmetry, the manuscript should provide a precise formal statement of the assumption and, ideally, a direct empirical test of it.

minor comments (4)

[Throughout] The document contains numerous LaTeX/OCR artifacts and broken notation (for example, 'damb', '/parallel.alt1', '/slash.left', and incomplete cross-references). A careful copyedit is needed.
[§2.4, Proposition 2.4.38] Proposition 2.4.38 is true, but its proof is flawed: from v in S'_V \ S_V it does not follow that v is not in span(S_V), since v could be a linear combination of other basis vectors. The proof should be replaced with a standard exchange argument.
[Introduction; Chapters 4–8] The dissertation repeatedly cites the author's own prior papers [1]–[7] for the main results. This is not inappropriate, but the text should clearly indicate which theorems and experiments are fully contained in this document and which are quoted from those papers, especially for the heavy-hitter bounds and the GWL-1 characterization.
[Table 5.4] The apparent-pair percentages per dimension are reported without error bars or number of runs; if these are single runs, adding repetitions and standard deviations would strengthen the empirical claim.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the core algorithmic claims are supported by in-thesis proofs and external benchmarks; chapter self-citations are bibliographic pointers, not load-bearing reductions.

full rationale

This dissertation is a compilation of the author's previously published algorithms (HYPHA, Ripser++, PDoptFlow, GEFL, and hypergraph symmetry breaking), and the citations [1]-[7] are chapter-level pointers to those papers. That structure is self-citational but not circular in the sense used here: the load-bearing mathematical claims are not merely asserted via the author's own citations. The apparent-pairs heavy-hitter statement (Section 5.4.5) is presented with a proof section and lower bounds under an explicit uniform-sampling condition, and the dissertation itself reports adversarial distance assignments (Sections 5.6.9-5.6.11) where the apparent-pair fraction is lower, which would be impossible if the speedup claim were true by definition. The PDoptFlow approximation guarantee is argued from δ-condensation and well-separated pair decomposition error bounds rather than from fitted values, and the empirical comparisons are against external baselines (Ripser, PHAT, hera, graph neural networks). The GWL-1 characterization and symmetry-breaking guarantees have proof sections (8.10) and are used conditionally on an explicit assumption about testing versus training automorphism-group entropy. The main caveat, that real point clouds may violate the uniform-locality condition needed for the heavy-hitter theorem, is a domain-condition limitation rather than a circular reduction: it is explicitly acknowledged in the paper's own construction of low-apparent-fraction examples. No step was found where a fitted parameter is renamed as a prediction, where an ansatz is smuggled in solely by self-citation, or where a claimed derivation is equivalent to its inputs by construction.

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

The dissertation's central claims rest mostly on the author's prior papers and on domain conditions that are stated with varying care. The uniform-sampling and locality condition for apparent pairs, the 'smaller testing automorphism group' premise for symmetry breaking, and the conjectured hardness bound for Wasserstein approximation are the three load-bearing premises that the reader does not get to verify from first principles in this document. The background chapter also assumes standard mathematics, and one of its applications is incorrect.

free parameters (4)

Condensation threshold delta (PDoptFlow) = Dataset-specific (0.99-delta grid snapping)
Controls node sparsification in Section 6.3.1, trading accuracy against performance; chosen per experiment and affects the reported approximation behavior.
WSPD separation ratio s (PDoptFlow) = Chosen per experiment
Arc sparsification parameter in Section 6.3.5; determines spanner size and hence the form of the near-linear-time bound.
GEFL learned filtration parameters = Trained on each dataset
The neural-network filtration function in Chapter 7 is fit to training labels; it is a fitted function, not a closed-form constant, and its parameters are a free choice of the method.
Random apparent-pairs model parameters (Section 5.6.11) = Curve matched to empirical fraction
The 'random approximation model' is presented through a piecewise-linear interpolated curve that matches the shape of the empirical and theoretical apparent-fraction curves; it is calibrated to the data it explains.

assumptions (4)

standard math ZFC set theory, category theory, algebra, and topology as presented in Chapter 2
The persistence framework and all algorithms rely on these standard foundations; one application of them (Proposition 2.4.29) is incorrect, which weakens confidence in the background's reliability.
domain assumption Uniform-sampling and locality condition for apparent-pair heavy-hitters (Section 5.4.7)
The lower bound on apparent pairs for large point samples is proved under this condition; transferring the Ripser++ speedups to real data assumes real datasets satisfy the same locality.
domain assumption Testing automorphism group is smaller (more entropy) than the training hypergraph's group
The introduction of Chapter 8 states explicitly that symmetry breaking is beneficial 'assuming the testing automorphism group is smaller'; without this premise the method's advantage is ungrounded.
ad hoc to paper A (1+epsilon) approximate EMD between persistence diagrams cannot be computed in O(n^{1+o(1)-delta}) time for any delta > 0
The claimed optimality of the near-linear running time is conditional on this conjecture, stated inline in the abstract and Sections 6.4.2 and 6.5.2 without a named standard hardness hypothesis.

invented entities (1)

Diagonal super-node in the PDoptFlow transportation network independent evidence
purpose: Represents the infinite diagonal of a persistence diagram exactly, so matching-to-diagonal costs are encoded without the discretization distortion that earlier finite-sampling approaches suffer.
The cost from any diagram point to the super-node is exactly its projection distance to the diagonal by construction, and the empirical error tables (Table 6.6) provide a checkable handle outside the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Computing and Learning on Combinatorial Data." pith.science (2026). https://pith.science/paper/P5SHM2YL

@misc{pith2026250205063,
  author       = {Pith},
  title        = {Pith review of: Computing and Learning on Combinatorial Data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P5SHM2YL}},
  note         = {Machine review of arXiv:2502.05063}
}

read the original abstract

The twenty-first century is a data-driven era where human activities and behavior, physical phenomena, scientific discoveries, technology advancements, and almost everything that happens in the world resulting in massive generation, collection, and utilization of data. Connectivity in data is a crucial property. A straightforward example is the World Wide Web, where every webpage is connected to other web pages through hyperlinks, providing a form of directed connectivity. Combinatorial data refers to combinations of data items based on certain connectivity rules. Other forms of combinatorial data include social networks, meshes, community clusters, set systems, and molecules. This Ph.D. dissertation focuses on learning and computing with combinatorial data. We study and examine topological and connectivity features within and across connected data to improve the performance of learning and achieve high algorithmic efficiency.

Figures

Figures reproduced from arXiv: 2502.05063 by the authors.

**Figure 2.1.** The grammar of first order logic 2.2 Set Theory Foundational to the language of math is the concept of a set. Sets provide the building blocks of definitions that are usable in math. They are intimately tied to first order logic, providing a formalization to groupings of objects. Definition 2.2.1. A set is an unordered collection of objects called elements. A set can be denoted by enumerating its elements via the fo… view at source ↗

**Figure 2.2.** (a) A simplicial 2-dimension complex composed of 6 simplices. The points 0, 1, 2 are 0-simplices, the line-segments 3, 4, 5 are 1-simplices, and the triangle 6 is a 2-simplex. (b) The corresponding boundary matrix. In the matrix, a column representing a simplex is encoded by the simplices in its boundary, e.g., the triangle 6 has the boundary composed of line-segments 3, 4, and 5. The formal sum between two p-chains… view at source ↗

**Figure 3.1.** The painting Persistence of Memory presents a Surrealist example of the passage of time. (Salvador Dali, 1931) [28] We go over persistence theory here. Originally motivated by the decomposition theorem of Gabriel [29], we give a more general interpretation in terms of causality. We would like there to exist a global synchronized notion of time over the objects of a category. We can achieve this by simulating a simpl… view at source ↗

Figures from the paper (60 more)

**Figure 3.2.** Figure 3.2: An illustration of a sequence of composable maps es,s+1 ∶ vs → vs+1, ..., et−1,t ∶ vt−1 → vt in the context of the data representation functor and the independence/dependence Question being asked at index i, s < i ≤ t 3.1.2 Examples We go over here examples that illu…

**Figure 3.3.** Figure 3.3: The indecomposable intervals of the persistence module {H0(Ki) φi,j Ð→ H0(Kj)}i,j∶1≤i≤j≤4 In the commuting diagram of [PITH_FULL_IMAGE:figures/full_fig_p141_3_3.png]

**Figure 4.1.** Figure 4.1: A redrawing of [PITH_FULL_IMAGE:figures/full_fig_p164_4_1.png]

**Figure 4.2.** Figure 4.2: (a): Standard matrix reduction on the example in [PITH_FULL_IMAGE:figures/full_fig_p166_4_2.png]

**Figure 4.3.** Figure 4.3: Two examples of Spectral Sequence-based PH matrix reduction on the boundary matrix in [PITH_FULL_IMAGE:figures/full_fig_p169_4_3.png]

**Figure 4.4.** Figure 4.4: The column addition distribution in various datasets. high_genus_extended is from the PHAT benchmark datasets. mumford comes from a 4-skeleton of the Rips filtration with 50 random points from the Mumford dataset [73]. torus comes from an alpha shape filtration [74]…

**Figure 4.5.** Figure 4.5: The frameworks of existing work and HYPHA. compression, our framework identifies indices to clear and compress immediately from GPU scan for leveraging its results. With the identified leftmost 1s and the 0-addition columns, the clearing and compression phase can pot…

**Figure 4.6.** Figure 4.6: GPU scans an example boundary matrix. table itself can be used to speed up the column addition by applying multiple additions in parallel. Additionally, knowing which columns are unstable can reduce the number of memory accesses in the following phases, by performing…

**Figure 4.7.** Figure 4.7: The accumulated number of column additions in various datasets when using HYPHA, CHUNK and TWIST. SS and TWIST have the same column addition distribution. sequence in PHAT end up executing the same column additions, with SS in parallel and TWIST sequentially. Further…

**Figure 4.8.** Figure 4.8: Running time in seconds of SS+ and SS algorithms over dataset high_genus_extended, w/ and w/o clearing, using bit-tree or vector-of-vector as the underlying data structure. 186 [PITH_FULL_IMAGE:figures/full_fig_p186_4_8.png]

**Figure 4.9.** Figure 4.9: HYPHA GPU-scan vs. TWIST 0-additions sequential scan throughput, for fully reduced columns, normalized to the throughput of TWIST 0-additions column scanning. efficiency. On the dataset 18-sphere, we observe the highest improvement: HYPHA GPUscan has a factor of 106…

**Figure 4.10.** Figure 4.10: The speedups of various algorithms over the standard PH reduction algorithm implemented in PHAT. 0.2 0.4 0.6 0.8 1 1.2 1.4 Pre-processing + 0-additions Non-tail-additions Tail-additions Norm. Running Time PHAT-TWIST HYPHA-TWIST [PITH_FULL_IMAGE:figures/full_fig_p1…

**Figure 4.11.** Figure 4.11: The time breakdown of HYPHA-TWIST running over the dataset high_genus_extended, normalized to PHAT-TWIST. 4.5 Discussion Having made algorithmic and systems efforts in a holistic way, we show that the conventional "one-size-fits-all" approach does not often win. Th…

**Figure 4.12.** Figure 4.12: this illustrates Amdahl’s law on a hybrid system’s speedup by both GPU and multicore. 192 [PITH_FULL_IMAGE:figures/full_fig_p192_4_12.png]

**Figure 5.1.** Figure 5.1: A filtration on an example finite metric space of four points of a square in the plane. The 1-skeleton, or simplicial complex of only points and unordered pairs of points, at each diameter value where "birth" or "death" occurs is shown. The 1 dimensional Vietoris-Rip…

**Figure 5.2.** Figure 5.2: The full 1-skeleton for the point cloud of [PITH_FULL_IMAGE:figures/full_fig_p202_5_2.png]

**Figure 5.3.** Figure 5.3: (a) shows a high-level structure of Ripser, which processes simplices dimension by dimension. In each dimension starting at dimension 1, the filtration is constructed and the clearing lemma is applied followed by a sort operation. The simplices to reduce are further …

**Figure 5.4.** Figure 5.4: (a) A dimension 1 0-persistence apparent pair (s, t) on a single 2-dimensional simplex. s is an edge of diameter 5 and t is a cofacet of s with diameter 5. The light arrow denotes the pairing between s and t. (b) In the dimension d coboundary matrix, (s, t) is an app…

**Figure 5.5.** Figure 5.5: A dimension 1 coboundary matrix of the full Rips filtration of the 2-skeleton on 5 points with all simplices of diameter 1. The yellow highlighted entries above the staircase correspond to apparent pairs. Lower bound: The largest number of cofacets of a given d-dimen…

**Figure 5.6.** Figure 5.6: (a) is an example distance matrix with differing edge diameters assigned in decreasing order for increasing lexicographic order on simplices. The barcodes are equivalent up to scaling so long as the distance matrix entries are in the same order (see Observation 5.6.…

**Figure 5.7.** Figure 5.7: Geometric interpretation of the theoretical upper bound in Theorem 5.4.2. Edge distances are not to scale. (a),(b),(c) (constructed in this order) show the apparent pairs for d = 1 on the planar cone graph centered around the newest apex point: n0 − 1 for n0 = 3, 4,…

**Figure 5.8.** Figure 5.8: A set of 4 i.i.d. points {p1, p2, p3, p4} sampled from some common distribution whose pair of points form edges. All the edges with the same number of ticks have the same length d. The edges with more than one tick have length d ′ > d. The left figure has the sample …

**Figure 5.9.** Figure 5.9: After finding apparent pairs, we partition the coboundary matrix columns into apparent and nonapparent columns. The apparent columns are sorted by the coboundary matrix row (the oldest cofacet of an apparent column) and stored in an array of pairs; while the nonappa…

**Figure 5.10.** Figure 5.10: Two-layer data structure for persistence pairs. Apparent pair insertion to the second layer of the data structure is illustrated in [PITH_FULL_IMAGE:figures/full_fig_p244_5_10.png]

**Figure 5.11.** Figure 5.11: The Filtration Construction with Clearing Algorithm for Full Rips Filtrations 244 [PITH_FULL_IMAGE:figures/full_fig_p244_5_11.png]

**Figure 5.12.** Figure 5.12: A comparison of column discovery throughput of apparent pair discovery with Ripser++ vs. Ripser’s shortcut pair discovery. The time is greatly reduced due to the parallel algorithm of finding apparent pairs on GPU (see Algorithm 13) [PITH_FULL_IMAGE:figures/full_fi…

**Figure 5.13.** Figure 5.13: A breakdown of the speedup of Ripser++ over Ripser for computation beyond dimension 0 into the two stages: matrix reduction and filtration construction with clearing. 5.6.6 Experiments on the Apparent Pairs Rate in Dimension 1 We run extensive experiments to analy…

**Figure 5.14.** Figure 5.14: Three different curves of the apparent fraction for a 1- dimensional coboundary matrix as a function of the number of points. The theoretical upper bound is for the case of all diameters the same, but also can be achieved when all diameters are different. Interestin…

**Figure 5.15.** Figure 5.15: The deterministic greedy apparent fraction curve. Notice the theoretical lower bound of 0.3333 is confirmed experimentally by the experimental curve. The experiments show the apparent fraction stays within a neighborhood of 0.5 as n gets large enough. 5.6.11 A Rand…

**Figure 5.16.** Figure 5.16: Illustration of the "width" and "depth" of computation. The area of the triangle represents the total amount of work performed. Furthermore, the "width" divided by the "depth" quantifies the level of parallelism in computation. empirically in [PITH_FULL_IMAGE:figu…

**Figure 6.1.** Figure 6.1: Plot of the empirical time (log scale) against the number of nodes n. empirical error from our experiments. Other approximation algorithms [149, 151, 154] are incomparable in prediction accuracy though they run much faster. In [PITH_FULL_IMAGE:figures/full_fig_p279_…

**Figure 6.2.** Figure 6.2: Pareto frontier of 7 algorithms showing the time and prediction accuracy tradeoff amongst the algorithms from [PITH_FULL_IMAGE:figures/full_fig_p281_6_2.png]

**Figure 6.3.** Figure 6.3: (a) −5; (7, 12) means a supply of −5 units at point (7, 12). (b) Bi(A, B) with the nodes denoted by solid circles. (c) G(A, B), nodes are the solid outer boxes. Supplies in G(A, B) are set by the number of circles inside each box. In (b) and (c), barred-points e.g. (…

**Figure 6.4.** Figure 6.4: δ-condensation for (a) matched and (b) unmatched points. Points snapped to their nearest 0.99δ-grid point. Points are then perturbed in a 0.01( δ 2 ) neighborhood. Green dotted pairwise distances change to new purple dotted and dashed pairwise distances. 6.3.1 Conden…

**Figure 6.5.** Figure 6.5: Illustration of Algorithm 22: (a) δ-condensation for the example in [PITH_FULL_IMAGE:figures/full_fig_p293_6_5.png]

**Figure 6.6.** Figure 6.6: Some of the persistence diagrams; PD1 is in blue and PD2 is in red [PITH_FULL_IMAGE:figures/full_fig_p307_6_6.png]

**Figure 6.7.** Figure 6.7: Convergence of PDoptFlow for W1-distance against the parameter s [PITH_FULL_IMAGE:figures/full_fig_p309_6_7.png]

**Figure 6.8.** Figure 6.8: Pipelines for computing NN. Pipelining Approximation Algorithms: Following [151] and using a distance to compute a set of candidate nearest neighbors, we pipeline these algorithms in increasing order of their accuracy to find the 1-NN with at least 90% accuracy. A pi…

**Figure 6.9.** Figure 6.9: constructing WSPD in parallel for array from the split tree 6.9 More Algorithmic Details: Here we present the algorithmic and implementation details that are omitted in the main context of the paper. 6.9.1 WCD: We implement the WCD using the Observation in [149] that…

**Figure 6.10.** Figure 6.10: (a) Plot of no stalling case of the cumulative distribution of blocks searched for rips, mri and brain-heart datasets. (b) Plot of a stalling case for the mri dataset. block size= √ m 6.9.3 Representing the Transshipment Network: The data structure used to represent…

**Figure 6.11.** Figure 6.11: Plot of the total number of block pivot searches depending on the number of arcs. Furthermore, we have noticed empirically that repeated tie breaking of reduced costs during pivot searching results in a tendency to stall. In fact, most implementations simply repeate…

**Figure 6.12.** Figure 6.12: Plot of the empirical time (log scale) depending on the number of arcs of the sparsified transshipment network for each dataset. n is the number of nodes. These are not real persistence diagrams and are made up of points randomly distributed on the plane above the d…

**Figure 7.1.** Figure 7.1: Lower and upper filtrations for extended persistence and the resulting barcode for a graph. The green bar comes from a pairing of a green edge with a vertex in the lower filtration. Similarily the blue bar in the upper filtration comes from a vertex-edge pairing in …

**Figure 7.2.** Figure 7.2: The extended persistence architecture (bars+cycles) for graph representation learning. The negative log likelihood (NLL) loss is used for supervised classification. The yellow arrow denotes extended persistence computation, which can compute both barcodes and cycle …

**Figure 7.3.** Figure 7.3: Class 0: 2 triangles with pinwheel at each vertex [PITH_FULL_IMAGE:figures/full_fig_p355_7_3.png]

**Figure 7.5.** Figure 7.5: Class 0: A 15 node cycle and an 85 node cycle [PITH_FULL_IMAGE:figures/full_fig_p356_7_5.png]

**Figure 7.7.** Figure 7.7: Average speedup with std. dev. as a function of sparsity p and number of vertices n on Erdos Renyi graphs. function, when a connected component merges with another connected component, the connected component with the larger connected component root value has its ro…

**Figure 7.8.** Figure 7.8: Cycle length histograms of the cycle representatives output by the extended persistence algorithm on sampled Erdos-Renyi graphs We perform an experiment to determine the cycle length distribution of cycle representatives output by our algorithm on random Erdos-Renyi…

**Figure 7.9.** Figure 7.9: and [PITH_FULL_IMAGE:figures/full_fig_p364_7_9.png]

**Figure 7.11.** Figure 7.11: IMDB-MULTI learned filtration function 0.0884 0.1424 0.4732 0.1226 0.179 0.3139 0.0973 0.1416 0.1585 0.587 0.0663 0.1787 0.2679 0.1566 0.5308 0.4585 1.2602 1.2919 1.0393 1.0051 1.0986 1.449 [PITH_FULL_IMAGE:figures/full_fig_p366_7_11.png]

**Figure 7.12.** Figure 7.12: MUTAG learned filtration function 366 [PITH_FULL_IMAGE:figures/full_fig_p366_7_12.png]

**Figure 7.13.** Figure 7.13: An exhibit of oversmoothing in the filtration convolutional layers. Plot of the average accuracy with std. dev. as a function of the number of convolutional layers before the Jumping Knowledge MLP and the extended persistence readout. The Proteins and Mutag datasets…

**Figure 8.1.** Figure 8.1: An illustration of a hypergraph of recipes. The nodes are the ingredients and the hyperedges are the recipes. The task of higher order link prediction is to predict hyperedges in the hypergraph. A negative hyperedge sample would be the dotted hyperedge. The Asian ing…

**Figure 8.2.** Figure 8.2: An illustration of hypergraph symmetry breaking. (c,d) 3-regular hypergraphs C3 4 , C3 5 with 4 and 5 nodes respectively and their corresponding universal covers centered at any hyperedge (B˜ C3 4 )e∗,∗,∗ , (B˜ C3 5 )e∗,∗,∗ with universal covering maps pBC3 4 , pBC3 …

**Figure 8.3.** Figure 8.3: An illustration of Algorithm 29 for 1-GWL-1. In (a) a hypergraph is shown. Each node is labeled with a pair. The left part of the pair in Greek alphabet is its isomorphism class. The right part of the pair in Latin alphabet is its 1-GWL-1 class, which is determined b…

**Figure 8.4.** Figure 8.4: Experiment on the relationship between the sizes of connected components of equal GWL-1 node values and the communication between communities. 8.6.3 Empirical Observations on the Components Discovered by the Algorithm According to Proposition 8.5.7, we know that the …

**Figure 8.5.** Figure 8.5: An illustration of hypergraph symmetry breaking. (c,d) 3-regular hypergraphs C3 4 , C3 5 with 4 and 5 nodes respectively and their corresponding universal covers centered at any hyperedge (B˜ C3 4 )e∗,∗,∗ , (B˜ C3 5 )e∗,∗,∗ with universal covering maps pBC3 4 , pBC3 …

**Figure 8.6.** Figure 8.6: Correlation between components and number of nodes. As we are primarily concerned with symmetries in a hypergraph, we empirically measure the size and frequency of the components found by the Algorithm for real-world datasets. For the real-world datasets listed in Ap…

**Figure 8.7.** Figure 8.7: Critical difference diagrams of cat-edge-madison-restaurant-reviews 0.600 0.625 0.650 0.675 0.700 0.725 Ours (0.6) drop (0.69) (0.71) baseline HGNNP 0.55 0.60 0.65 0.70 0.75 0.80 baseline (0.57) drop (0.64) (0.79) Ours HGNN 0.55 0.60 0.65 0.70 0.75 drop (0.56) baseli…

**Figure 8.8.** Figure 8.8: Critical difference diagrams of cat-edge-vegas-bars-reviews 454 [PITH_FULL_IMAGE:figures/full_fig_p454_8_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

300 extracted references · 51 canonical work pages

[1]

Hypha: A framework based on separation of parallelisms to accelerate persistent homology matrix reduc- tion,

S. Zhang, M. Xiao, C. Guo, L. Geng, H. Wang, and X. Zhang, “Hypha: A framework based on separation of parallelisms to accelerate persistent homology matrix reduc- tion,” in Proceedings of the ACM International Conference on Supercomputing, ACM, 2019, pp. 69–81

2019
[2]

Gpu-accelerated computation of Vietoris-Rips persistence barcodes,

S. Zhang, M. Xiao, and H. Wang, “Gpu-accelerated computation of Vietoris-Rips persistence barcodes,” arXiv preprint arXiv:2003.07989 , 2020

arXiv 2003
[3]

GPU-accelerated computation of Vietoris-Rips persistence barcodes,

S. Zhang, M. Xiao, and H. Wang, “GPU-accelerated computation of Vietoris-Rips persistence barcodes,” in 36th International Symposium on Computational Geometry (SoCG 2020) , Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020

2020
[4]

Approximating 1-wasserstein distance between persis- tence diagrams by graph sparsiﬁcation,

T. K. Dey and S. Zhang, “Approximating 1-wasserstein distance between persis- tence diagrams by graph sparsiﬁcation,” in 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) , pp. 169–183. doi: 10.1137/1. 9781611977042.14 . eprint: https://epubs.siam.org/doi/pdf/10.1137/1.9781611977042. 14 . [Online]. A vailable: https://epu...

doi:10.1137/1 2022
[5]

Geﬂ: Extended ﬁltration learning for graph classiﬁcation,

S. Zhang, S. Mukherjee, and T. K. Dey, “Geﬂ: Extended ﬁltration learning for graph classiﬁcation,” in Learning on Graphs Conference , PMLR, 2022, pp. 16–1

2022
[6]

Expressive higher-order link prediction through hypergraph symmetry breaking,

S. Zhang, C. Xin, and T. K. Dey, “Expressive higher-order link prediction through hypergraph symmetry breaking,” arXiv preprint arXiv:2402.11339 , 2024

arXiv 2024
[7]

Expressive higher-order link prediction through hypergraph symmetry breaking,

S. Zhang, C. Xin, and T. K. Dey, “Expressive higher-order link prediction through hypergraph symmetry breaking,” Transactions on Machine Learning Research , 2024. [Online]. A vailable: https://openreview.net/forum?id=oG65SjZNIF

2024
[8]

S. J. Russell and P. Norvig, Artiﬁcial intelligence: a modern approach . Pearson, 2016

2016

Show all 300 references

[9]

Survey article: The real numbers–a survey of constructions,

I. Weiss, “Survey article: The real numbers–a survey of constructions,” 2015

2015
[10]

C. F. Gauss, Theoria residuorum biquadraticorum. Commentatio secunda . Typis Di- eterichchianis, 1832
[11]

K. H. Rosen and K. Krithivasan, Discrete mathematics and its applications . McGraw- Hill New York, 1999, vol. 6. 471

1999
[12]

General theory of natural equivalences,

S. Eilenberg and S. MacLane, “General theory of natural equivalences,” Transactions of the American Mathematical Society , vol. 58, no. 2, pp. 231–294, 1945

1945
[13]

Acyclic categories,

D. Kozlov, “Acyclic categories,” Combinatorial Algebraic Topology, pp. 151–178, 2008

2008
[14]

Quiver representations,

H. Derksen and J. Weyman, “Quiver representations,” Notices of the AMS , vol. 52, no. 2, pp. 200–206, 2005

2005
[15]

Ueber die theorie der algebraischen formen,

D. Hilbert, “Ueber die theorie der algebraischen formen,” Mathematische annalen , vol. 36, no. 4, pp. 473–534, 1890
[16]

D. S. Dummit and R. M. Foote, Abstract algebra. Wiley Hoboken, 2004, vol. 3

2004
[17]

Hoﬀman and R

K. Hoﬀman and R. Kunze, Linear algebra, engelewood cliﬀs , 1961

1961
[18]

P. R. Halmos, Finite-dimensional vector spaces . Courier Dover Publications, 2017

2017
[19]

Idealtheorie in ringbereichen,

E. Noether, “Idealtheorie in ringbereichen,” Mathematische Annalen , vol. 83, no. 1, pp. 24–66, 1921

1921
[20]

I. M. Gelfand, R. A. Silverman, et al. , Calculus of variations . Courier Corporation, 2000

2000
[21]

The group of isometries of a riemannian manifold,

S. B. Myers and N. E. Steenrod, “The group of isometries of a riemannian manifold,” Annals of Mathematics , vol. 40, no. 2, pp. 400–416, 1939

1939
[22]

Boyd and L

S. Boyd and L. Vandenberghe, Convex optimization . Cambridge university press, 2004

2004
[23]

G. M. Ziegler, Lectures on polytopes. Springer Science & Business Media, 2012, vol. 152

2012
[24]

Causal inference in statistics: An overview,

J. Pearl, “Causal inference in statistics: An overview,” 2009

2009
[25]

Pearl, Causality

J. Pearl, Causality. Cambridge university press, 2009

2009
[26]

Birkhoﬀ, Lattice theory

G. Birkhoﬀ, Lattice theory. American Mathematical Soc., 1940, vol. 25

1940
[27]

Schiﬄer, Quiver representations

R. Schiﬄer, Quiver representations. Springer, 2014, vol. 1. 472

2014
[28]

Steele, The Persistence of Memory (1931) by Salvador Dali (CC BY-NC-ND 2.0)

M. Steele, The Persistence of Memory (1931) by Salvador Dali (CC BY-NC-ND 2.0) . Nov. 2014. [Online]. A vailable: https : / / www . flickr . com / photos / 21022123 @ N04 / 15694508911

1931
[29]

Unzerlegbare darstellungen i,

P. Gabriel, “Unzerlegbare darstellungen i,” Manuscripta mathematica, vol. 6, pp. 71– 103, 1972

1972
[30]

Topological sorting of large networks,

A. B. Kahn, “Topological sorting of large networks,” Communications of the ACM , vol. 5, no. 11, pp. 558–562, 1962

1962
[31]

Representations of quivers,

M. Brion, “Representations of quivers,” 2008

2008
[32]

Morin, Quiver algebras , 2014

M. Morin, Quiver algebras , 2014

2014
[33]

Inﬁnite root systems, representations of graphs and invariant theory,

V. G. Kac, “Inﬁnite root systems, representations of graphs and invariant theory,” Inventiones mathematicae , vol. 56, no. 1, pp. 57–92, 1980

1980
[34]

Inﬁnite root systems, representations of graphs and invariant theory, ii,

V. G. Kac, “Inﬁnite root systems, representations of graphs and invariant theory, ii,” Journal of algebra , vol. 78, no. 1, pp. 141–162, 1982

1982
[35]

A multiprocessor system design,

M. E. Conway, “A multiprocessor system design,” in Proceedings of the November 12-14, 1963, fall joint computer conference , 1963, pp. 139–146

1963
[36]

A bridging model for parallel computation,

L. G. Valiant, “A bridging model for parallel computation,” Communications of the ACM, vol. 33, no. 8, pp. 103–111, 1990

1990
[37]

Dot: A matrix model for analyzing, optimizing and deploying software for big data analytics in distributed systems,

Y. Huai, R. Lee, S. Zhang, C. H. Xia, and X. Zhang, “Dot: A matrix model for analyzing, optimizing and deploying software for big data analytics in distributed systems,” in Proceedings of the 2nd ACM Symposium on Cloud Computing , 2011, pp. 1–14

2011
[38]

Mapreduce: Simpliﬁed data processing on large clusters,

J. Dean and S. Ghemawat, “Mapreduce: Simpliﬁed data processing on large clusters,” 2004

2004
[39]

The theory of multidimensional persistence,

G. Carlsson and A. Zomorodian, “The theory of multidimensional persistence,” in Proceedings of the twenty-third annual symposium on Computational geometry , 2007, pp. 184–193

2007
[40]

Invariants and metrics for multiparameter persistent homology,

A. L. Thomas, “Invariants and metrics for multiparameter persistent homology,” Ph.D. dissertation, Duke University, 2019. 473

2019
[41]

Stratifying multiparameter persistent homology,

H. A. Harrington, N. Otter, H. Schenck, and U. Tillmann, “Stratifying multiparameter persistent homology,” SIAM Journal on Applied Algebra and Geometry , vol. 3, no. 3, pp. 439–471, 2019

2019
[42]

Generalized persistence diagrams for persistence modules over posets,

W. Kim and F. Mémoli, “Generalized persistence diagrams for persistence modules over posets,” Journal of Applied and Computational Topology , vol. 5, no. 4, pp. 533– 581, 2021

2021
[43]

Computing generalized rank invariant for 2- parameter persistence modules via zigzag persistence and its applications,

T. K. Dey, W. Kim, and F. Mémoli, “Computing generalized rank invariant for 2- parameter persistence modules via zigzag persistence and its applications,” Discrete & Computational Geometry , vol. 71, no. 1, pp. 67–94, 2024

2024
[44]

T. K. Dey and Y. Wang, Computational topology for data analysis . Cambridge Uni- versity Press, 2022

2022
[45]

The structure of semi-simple algebras,

E. B. Dynkin, “The structure of semi-simple algebras,” Uspekhi Matematicheskikh Nauk, vol. 2, no. 4, pp. 59–127, 1947

1947
[46]

Fulton and J

W. Fulton and J. Harris, Representation theory: a ﬁrst course . Springer Science & Business Media, 2013, vol. 129

2013
[47]

Zigzag persistence,

G. Carlsson and V. De Silva, “Zigzag persistence,” Foundations of computational mathematics, vol. 10, pp. 367–405, 2010

2010
[48]

Strang, Linear algebra and its applications

G. Strang, Linear algebra and its applications . 2012

2012
[49]

Elder-rule-staircodes for augmented metric spaces,

C. Cai, W. Kim, F. Mémoli, and Y. Wang, “Elder-rule-staircodes for augmented metric spaces,” SIAM Journal on Applied Algebra and Geometry , vol. 5, no. 3, pp. 417– 454, 2021

2021
[50]

S. eilenberg homological algebra,

H. Cartan, “S. eilenberg homological algebra,” Princeton Math. Ser , vol. 19, 1956

1956
[51]

Topology and data,

G. Carlsson, “Topology and data,” Bulletin of the American Mathematical Society , vol. 46, no. 2, pp. 255–308, 2009

2009
[52]

Coverage in sensor networks via persistent homology,

V. De Silva and R. Ghrist, “Coverage in sensor networks via persistent homology,” Algebraic & Geometric Topology , vol. 7, no. 1, pp. 339–358, 2007. 474

2007
[53]

A topological paradigm for hippocampal spatial map formation using persistent homology,

Y. Dabaghian, F. Mémoli, L. Frank, and G. Carlsson, “A topological paradigm for hippocampal spatial map formation using persistent homology,” PLoS computational biology, vol. 8, no. 8, e1002581, 2012

2012
[54]

Finding the homology of submanifolds with high conﬁdence from random samples,

P. Niyogi, S. Smale, and S. Weinberger, “Finding the homology of submanifolds with high conﬁdence from random samples,” Discrete & Computational Geometry , vol. 39, no. 1-3, pp. 419–441, 2008

2008
[55]

A study on validating non-linear dimensionality reduction using persistent homology,

R. Paul and S. K. Chalup, “A study on validating non-linear dimensionality reduction using persistent homology,” Pattern Recognition Letters, vol. 100, pp. 160–166, 2017

2017
[56]

Deep learning with topological signatures,

C. Hofer, R. Kwitt, M. Niethammer, and A. Uhl, “Deep learning with topological signatures,” in Advances in Neural Information Processing Systems , 2017, pp. 1634– 1644

2017
[57]

A roadmap for the computation of persistent homology,

N. Otter, M. A. Porter, U. Tillmann, P. Grindrod, and H. A. Harrington, “A roadmap for the computation of persistent homology,” EPJ Data Science , vol. 6, no. 1, p. 17, 2017

2017
[58]

Javaplex tutorial,

H. Adams and A. Tausz, “Javaplex tutorial,” Google Scholar, 2011

2011
[59]

Phat–persistent homology algorithms toolbox,

U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner, “Phat–persistent homology algorithms toolbox,” Journal of symbolic computation , vol. 78, pp. 76–90, 2017

2017
[60]

Morozov, Dionysus software , 2017

D. Morozov, Dionysus software , 2017. [Online]. A vailable: http://www.mrzv.org / software/dionysus/

2017
[61]

Distributed computation of persistent homology,

U. Bauer, M. Kerber, and J. Reininghaus, “Distributed computation of persistent homology,” in Proceedings of the Meeting on Algorithm Engineering & Expermiments , Portland, Oregon: Society for Industrial and Applied Mathematics, 2014, pp. 31–38

2014
[62]

Bauer, Ripser: Eﬃcient computation of vietorisrips persistence barcodes , 2018

U. Bauer, Ripser: Eﬃcient computation of vietorisrips persistence barcodes , 2018. [Online]. A vailable: https://github.com/Ripser/ripser

2018
[63]

Matroid ﬁltrations and computational persistent ho- mology,

G. Henselman and R. Ghrist, “Matroid ﬁltrations and computational persistent ho- mology,” arXiv preprint arXiv:1606.00199 , 2016

2016 arXiv
[64]

A new data structure for cumulative frequency tables,

P. M. Fenwick, “A new data structure for cumulative frequency tables,” Softw. Pract. Exper., vol. 24, no. 3, pp. 327–336, Mar. 1994, issn: 0038-0644. 475

1994
[65]

Cramming more components onto integrated circuits,

I. Present, “Cramming more components onto integrated circuits,” Readings in com- puter architecture, vol. 56, 2000

2000
[66]

Design of ion-implanted mosfet’s with very small physical dimensions,

R. H. Dennard, F. H. Gaensslen, V. L. Rideout, E. Bassous, and A. R. LeBlanc, “Design of ion-implanted mosfet’s with very small physical dimensions,”IEEE Journal of Solid-State Circuits , vol. 9, no. 5, pp. 256–268, 1974

1974
[67]

Edelsbrunner and J

H. Edelsbrunner and J. Harer, Computational topology: an introduction . American Mathematical Soc., 2010

2010
[68]

Clear and compress: Computing persistent homology in chunks,

U. Bauer, M. Kerber, and J. Reininghaus, “Clear and compress: Computing persistent homology in chunks,” in Topological methods in data analysis and visualization III , Springer, 2014, pp. 103–117

2014
[69]

Persistent homology computation with a twist,

C. Chen and M. Kerber, “Persistent homology computation with a twist,” in Pro- ceedings 27th European Workshop on Computational Geometry , vol. 11, 2011

2011
[70]

Vines and vineyards by updat- ing persistence in linear time,

D. Cohen-Steiner, H. Edelsbrunner, and D. Morozov, “Vines and vineyards by updat- ing persistence in linear time,” in Proceedings of the twenty-second annual symposium on Computational geometry , ACM, 2006, pp. 119–126

2006
[71]

Parallel multi-scale reduction of persistent ho- mology ﬁltrations,

R. Mendoza-Smith and J. Tanner, “Parallel multi-scale reduction of persistent ho- mology ﬁltrations,” arXiv preprint arXiv:1708.04710 , 2017

2017 arXiv
[72]

E. H. Spanier, Algebraic topology. Springer Science & Business Media, 1989, vol. 55

1989
[73]

The nonlinear statistics of high-contrast patches in natural images,

A. B. Lee, K. S. Pedersen, and D. Mumford, “The nonlinear statistics of high-contrast patches in natural images,” International Journal of Computer Vision , vol. 54, no. 1-3, pp. 83–103, 2003

2003
[74]

Introduction to alpha shapes,

K. Fischer, “Introduction to alpha shapes,” Department of Information and Comput- ing Sciences, Faculty of Science, Utrecht University , vol. 17, 2000

2000
[75]

Loops skewing: The wavefront method revisited,

M. Wolfe, “Loops skewing: The wavefront method revisited,” International Journal of Parallel Programming , vol. 15, no. 4, pp. 279–293, 1986. 476

1986
[76]

Peerwave: Exploiting wavefront parallelism on gpus with peer-sm synchronization,

M. E. Belviranli, P. Deng, L. N. Bhuyan, R. Gupta, and Q. Zhu, “Peerwave: Exploiting wavefront parallelism on gpus with peer-sm synchronization,” in Proceedings of the 29th ACM on International Conference on Supercomputing , ser. ICS ’15, Newport Beach, California, USA: ACM, 2...

2015
[77]

Highly eﬃcient compensation- based parallelism for wavefront loops on gpus,

K. Hou, H. Wang, W.-c. Feng, J. S. Vetter, and S. Lee, “Highly eﬃcient compensation- based parallelism for wavefront loops on gpus,” in 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS) , IEEE, 2018, pp. 276–285

2018
[78]

The pareto, zipf and other power laws,

W. J. Reed, “The pareto, zipf and other power laws,” Economics letters, vol. 74, no. 1, pp. 15–19, 2001

2001
[79]

The tail at scale,

J. Dean and L. A. Barroso, “The tail at scale,” Communications of the ACM , vol. 56, no. 2, pp. 74–80, 2013

2013
[80]

Fibonacci heaps and their uses in improved network optimization algorithms,

M. L. Fredman and R. E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms,” J. ACM, vol. 34, no. 3, pp. 596–615, Jul. 1987, issn: 0004-

1987
[81]

The yin and yang of processing data warehousing queries on gpu devices,

Y. Yuan, R. Lee, and X. Zhang, “The yin and yang of processing data warehousing queries on gpu devices,” Proceedings of the VLDB Endowment, vol. 6, no. 10, pp. 817– 828, 2013

2013
[82]

Persistent cohomology and circular coordinates,

V. De Silva, D. Morozov, and M. Vejdemo-Johansson, “Persistent cohomology and circular coordinates,” Discrete & Computational Geometry , vol. 45, no. 4, pp. 737– 759, 2011

2011
[83]

Dualities in persistent (co) homology,

V. De Silva, D. Morozov, and M. Vejdemo-Johansson, “Dualities in persistent (co) homology,” Inverse Problems , vol. 27, no. 12, p. 124 003, 2011

2011
[84]

Austria, Phat (persistent homology algorithm toolbox), v1.5 , 2017

I. Austria, Phat (persistent homology algorithm toolbox), v1.5 , 2017. [Online]. A vail- able: https://bitbucket.org/phat-code/phat

2017
[85]

Custinger: Supporting dynamic graph algorithms for gpus,

O. Green and D. A. Bader, “Custinger: Supporting dynamic graph algorithms for gpus,” in High Performance Extreme Computing Conference (HPEC), 2016 IEEE , IEEE, 2016, pp. 1–6

2016
[86]

Accelerating dynamic graph analytics on gpus,

M. Sha, Y. Li, B. He, and K.-L. Tan, “Accelerating dynamic graph analytics on gpus,” Proc. VLDB Endow. , vol. 11, no. 1, pp. 107–120, Sep. 2017, issn: 2150-8097. 477

2017
[87]

Hornet: An eﬃcient data struc- ture for dynamic sparse graphs and matrices on gpus,

F. Busato, O. Green, N. Bombieri, and D. A. Bader, “Hornet: An eﬃcient data struc- ture for dynamic sparse graphs and matrices on gpus,” in 2018 IEEE High Perfor- mance extreme Computing Conference (HPEC) , IEEE, 2018, pp. 1–7

2018
[88]

Faimgraph: High performance management of fully-dynamic graphs under tight memory constraints on the gpu,

M. Winter, D. Mlakar, R. Zayer, H.-P. Seidel, and M. Steinberger, “Faimgraph: High performance management of fully-dynamic graphs under tight memory constraints on the gpu,” in Proceedings of the International Conference for High Performance Com- puting, Networking, Storage, a...

2018
[89]

Performance enhance- ment of a computational persistent homology package,

A. Hylton, J. Sang, G. Henselman-Petrusek, and R. Short, “Performance enhance- ment of a computational persistent homology package,” in 2017 IEEE 36th Inter- national Performance Computing and Communications Conference (IPCCC) , IEEE, 2017, pp. 1–8

2017
[90]

Morse theory for ﬁltrations and eﬃcient computation of persistent homology,

K. Mischaikow and V. Nanda, “Morse theory for ﬁltrations and eﬃcient computation of persistent homology,” Discrete & Computational Geometry , vol. 50, no. 2, pp. 330– 353, 2013

2013
[91]

GUDHI Editorial Board,

The GUDHI Project, GUDHI User and Reference Manual . GUDHI Editorial Board,
[92]

The compressed annotation matrix: An eﬃcient data structure for computing persistent cohomology,

J.-D. Boissonnat, T. K. Dey, and C. Maria, “The compressed annotation matrix: An eﬃcient data structure for computing persistent cohomology,” in European Symposium on Algorithms , Springer, 2013, pp. 695–706

2013
[93]

Computing topological persistence for simplicial maps,

T. K. Dey, F. Fan, and Y. Wang, “Computing topological persistence for simplicial maps,” in Proceedings of the thirtieth annual symposium on Computational geometry , ACM, 2014, p. 345

2014
[94]

Accelerating pathol- ogy image data cross-comparison on cpu-gpu hybrid systems,

K. Wang, Y. Huai, R. Lee, F. Wang, X. Zhang, and J. H. Saltz, “Accelerating pathol- ogy image data cross-comparison on cpu-gpu hybrid systems,” Proc. VLDB Endow. , vol. 5, no. 11, pp. 1543–1554, Jul. 2012, issn: 2150-8097

2012
[95]

Throughput-oriented gpu memory allocation,

I. Gelado and M. Garland, “Throughput-oriented gpu memory allocation,” in Pro- ceedings of the 24th Symposium on Principles and Practice of Parallel Programming , ACM, 2019, pp. 27–37

2019
[96]

Mega-kv: A case for gpus to maximize the throughput of in-memory key-value stores,

K. Zhang, K. Wang, Y. Yuan, L. Guo, R. Lee, and X. Zhang, “Mega-kv: A case for gpus to maximize the throughput of in-memory key-value stores,” Proceedings of the VLDB Endowment , vol. 8, no. 11, pp. 1226–1237, 2015. 478

2015
[97]

Persistence homology of networks: Methods and applications,

M. E. Aktas, E. Akbas, and A. El Fatmaoui, “Persistence homology of networks: Methods and applications,” Applied Network Science , vol. 4, no. 1, p. 61, 2019

2019
[98]

Computing persistent homology of directed ﬂag complexes,

D. Luetgehetmann, D. Govc, J. Smith, and R. Levi, “Computing persistent homology of directed ﬂag complexes,” arXiv preprint arXiv:1906.10458 , 2019

1906 arXiv
[99]

Proof of bijection for combinatorial number system,

A. B. Siddique, S. Farid, and M. Tahir, “Proof of bijection for combinatorial number system,” arXiv preprint arXiv:1601.05794 , 2016

2016 arXiv
[100]

D. E. Knuth, The art of computer programming . Pearson Education, 1997, vol. 3

1997
[101]

Pascal, Sopra una formola numerica

E. Pascal, Sopra una formola numerica . 1887
[102]

Topological persistence and sim- pliﬁcation,

H. Edelsbrunner, D. Letscher, and A. Zomorodian, “Topological persistence and sim- pliﬁcation,” in Proceedings 41st annual symposium on foundations of computer sci- ence, IEEE, 2000, pp. 454–463

2000
[103]

Ripser: Eﬃcient computation of vietoris-rips persistence barcodes,

U. Bauer, “Ripser: Eﬃcient computation of vietoris-rips persistence barcodes,” arXiv preprint arXiv:1908.02518 , 2019

1908 arXiv
[104]

The gudhi library: Simpli- cial complexes and persistent homology,

C. Maria, J.-D. Boissonnat, M. Glisse, and M. Yvinec, “The gudhi library: Simpli- cial complexes and persistent homology,” in International Congress on Mathematical Software, Springer, 2014, pp. 167–174

2014
[105]

Fast construction of the vietoris-rips complex,

A. Zomorodian, “Fast construction of the vietoris-rips complex,” Computers & Graph- ics, vol. 34, no. 3, pp. 263–271, 2010

2010
[106]

Distributed computation of persistent homology,

U. Bauer, M. Kerber, and J. Reininghaus, “Distributed computation of persistent homology,” in 2014 proceedings of the sixteenth workshop on algorithm engineering and experiments (ALENEX) , SIAM, 2014, pp. 31–38

2014
[107]

Henselman, Eirene: A platform for computational homological algebra , 2016

G. Henselman, Eirene: A platform for computational homological algebra , 2016

2016
[108]

Persistent and zigzag homology: A matrix factorization viewpoint,

G. Carlsson, A. Dwaraknath, and B. J. Nelson, “Persistent and zigzag homology: A matrix factorization viewpoint,” arXiv preprint arXiv:1911.10693 , 2019

1911 arXiv
[109]

A framework for the automatic vectorization of parallel sort on x86-based processors,

K. Hou, H. Wang, and W.-C. Feng, “A framework for the automatic vectorization of parallel sort on x86-based processors,” IEEE Transactions on Parallel and Distributed Systems, vol. 29, no. 5, pp. 958–972, 2018. 479

2018
[110]

Designing eﬃcient sorting algorithms for manycore gpus,

N. Satish, M. Harris, and M. Garland, “Designing eﬃcient sorting algorithms for manycore gpus,” in Proceedings of the 2009 IEEE International Symposium on Par- allel&Distributed Processing, ser. IPDPS ’09, Washington, DC, USA: IEEE Computer Society, 2009, pp. 1–10, isbn: 978-1...

2009
[111]

Fast parallel gpu-sorting using a hybrid algorithm,

E. Sintorn and U. Assarsson, “Fast parallel gpu-sorting using a hybrid algorithm,” J. Parallel Distrib. Comput. , vol. 68, no. 10, pp. 1381–1388, Oct. 2008, issn: 0743-7315. doi: 10.1016/j.jpdc.2008.05.012 . [Online]. A vailable: https://doi.org/10.1016/j.jpdc. 2008.05.012

2008 doi
[112]

Skeletonization and partitioning of digital images using discrete morse theory,

O. Delgado-Friedrichs, V. Robins, and A. Sheppard, “Skeletonization and partitioning of digital images using discrete morse theory,” IEEE transactions on pattern analysis and machine intelligence , vol. 37, no. 3, pp. 654–666, 2014

2014
[113]

Simba: An eﬃcient tool for approximating rips- ﬁltration persistence via simplicial batch collapse,

T. K. Dey, D. Shi, and Y. Wang, “Simba: An eﬃcient tool for approximating rips- ﬁltration persistence via simplicial batch collapse,” Journal of Experimental Alsgorith- mics (JEA) , vol. 24, no. 1, pp. 1–5, 2019

2019
[114]

Linear-size approximations to the Vietoris-Rips ﬁltration,

D. R. Sheehy, “Linear-size approximations to the Vietoris-Rips ﬁltration,” Discrete & Computational Geometry , vol. 49, no. 4, pp. 778–796, 2013

2013
[115]

A geometric perspective on sparse ﬁltrations,

N. J. Cavanna, M. Jahanseir, and D. R. Sheehy, “A geometric perspective on sparse ﬁltrations,” arXiv preprint arXiv:1506.03797 , 2015

2015 arXiv
[116]

On the shortest spanning subtree of a graph and the traveling salesman problem,

J. B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem,” Proceedings of the American Mathematical society , vol. 7, no. 1, pp. 48–50, 1956

1956
[117]

Sort vs. hash revisited: Fast join implementation on modern multi-core cpus,

C. Kim et al., “Sort vs. hash revisited: Fast join implementation on modern multi-core cpus,” Proc. VLDB Endow. , vol. 2, no. 2, pp. 1378–1389, Aug. 2009, issn: 2150-8097. doi: 10 . 14778 / 1687553 . 1687564 . [Online]. A vailable: https : / / doi . org / 10 . 14778 / 1687553.1687564

2009
[118]

The simplex tree: An eﬃcient data structure for general simplicial complexes,

J.-D. Boissonnat and C. Maria, “The simplex tree: An eﬃcient data structure for general simplicial complexes,” in European Symposium on Algorithms, Springer, 2012, pp. 731–742

2012
[119]

An Eﬃcient Representation for Filtrations of Sim- plicial Complexes,

J.-D. Boissonnat and C. Karthik, “An Eﬃcient Representation for Filtrations of Sim- plicial Complexes,” ACM Transactions on Algorithms , vol. 14, Sep. 2018. [Online]. A vailable: https://hal.inria.fr/hal-01883836 . 480

2018
[120]

Persistent homology for detection of objects from mobile lidar point cloud data in autonomous vehicles,

M. Syzdykbayev and H. A. Karimi, “Persistent homology for detection of objects from mobile lidar point cloud data in autonomous vehicles,” in Science and Information Conference, Springer, 2019, pp. 458–472

2019
[121]

Persistent homology analysis of brain artery trees,

P. Bendich, J. S. Marron, E. Miller, A. Pieloch, and S. Skwerer, “Persistent homology analysis of brain artery trees,” The annals of applied statistics , vol. 10, no. 1, p. 198, 2016

2016
[122]

Über eine besondere art von umkehrung der reihen.,

A. F. Möbius, “Über eine besondere art von umkehrung der reihen.,” 1832
[123]

Generalized persistence diagrams,

A. Patel, “Generalized persistence diagrams,” Journal of Applied and Computational Topology, vol. 1, no. 3, pp. 397–419, 2018

2018
[124]

Computing persistent homology,

A. Zomorodian and G. Carlsson, “Computing persistent homology,” in Proceedings of the twentieth annual symposium on Computational geometry , 2004, pp. 347–356

2004
[125]

The representation theorem of persistence revisited and generalized,

R. Corbet and M. Kerber, “The representation theorem of persistence revisited and generalized,” Journal of Applied and Computational Topology , vol. 2, no. 1, pp. 1–31, 2018

2018
[126]

T. K. Dey and Y. Wang, Computational topology for Data Analysis . Cambridge University Press, 2022. [Online]. A vailable: https : / / www . cs . purdue . edu / homes / tamaldey/book/CTDAbook/CTDAbook.html

2022
[127]

Stability of persistence diagrams,

D. Cohen-Steiner, H. Edelsbrunner, and J. Harer, “Stability of persistence diagrams,” Discrete & computational geometry , vol. 37, no. 1, pp. 103–120, 2007

2007
[128]

Wasserstein stability for persistence diagrams,

P. Skraba and K. Turner, “Wasserstein stability for persistence diagrams,” arXiv preprint arXiv:2006.16824 , 2020

2006 arXiv
[129]

Fuzzy c-means clustering for persistence diagrams,

T. Davies, J. Aspinall, B. Wilder, and L. Tran-Thanh, “Fuzzy c-means clustering for persistence diagrams,” arXiv preprint arXiv:2006.02796 , 2020

2006 arXiv
[130]

Large scale computation of means and clusters for persistence diagrams using optimal transport,

T. Lacombe, M. Cuturi, and S. Oudot, “Large scale computation of means and clusters for persistence diagrams using optimal transport,” in Advances in Neural Information Processing Systems, 2018, pp. 9770–9780

2018
[131]

K- means clustering on the space of per- sistence diagrams,

A. Marchese, V. Maroulas, and J. Mike, “K- means clustering on the space of per- sistence diagrams,” in Wavelets and Sparsity XVII , International Society for Optics and Photonics, vol. 10394, 2017, 103940W. 481

2017
[132]

Sliced wasserstein kernel for persistence dia- grams,

M. Carrière, M. Cuturi, and S. Oudot, “Sliced wasserstein kernel for persistence dia- grams,” in International conference on machine learning , PMLR, 2017, pp. 664–673

2017
[133]

Entropy partial transport with tree metrics: Theory and practice,

T. Le and T. Nguyen, “Entropy partial transport with tree metrics: Theory and practice,” arXiv preprint arXiv:2101.09756 , 2021

2021 arXiv
[134]

Perturbation robust representations of topological persistence diagrams,

A. Som, K. Thopalli, K. N. Ramamurthy, V. Venkataraman, A. Shukla, and P. Turaga, “Perturbation robust representations of topological persistence diagrams,” in Proceed- ings of the European Conference on Computer Vision (ECCV) , 2018, pp. 617–635

2018
[135]

TopoGAN: A topology-aware generative adversarial network,

F. Wang, H. Liu, D. Samaras, and C. Chen, “TopoGAN: A topology-aware generative adversarial network,”
[136]

Geometry helps to compare persistence diagrams,

M. Kerber, D. Morozov, and A. Nigmetov, “Geometry helps to compare persistence diagrams,” Journal of Experimental Algorithmics (JEA) , vol. 22, pp. 1–20, 2017

2017
[137]

Dionysus software,

D. Morozov, “Dionysus software,” Retrieved December, vol. 24, p. 2018, 2012

2018
[138]

C. T. Nathaniel Saul, Scikit-tda: Topological data analysis for python , 2019. doi: 10. 5281/zenodo.2533369 . [Online]. A vailable: https://doi.org/10.5281/zenodo.2533369

2019 doi
[139]

Burkard, M

R. Burkard, M. Dell’Amico, and S. Martello, Assignment problems: revised reprint . SIAM, 2012

2012
[140]

Deterministic decremental sssp and approximate min-cost ﬂow in almost-linear time,

A. Bernstein, M. P. Gutenberg, and T. Saranurak, “Deterministic decremental sssp and approximate min-cost ﬂow in almost-linear time,” arXiv preprint arXiv:2101.07149, 2021

2021 arXiv
[141]

The auction algorithm: A distributed relaxation method for the assignment problem,

D. P. Bertsekas, “The auction algorithm: A distributed relaxation method for the assignment problem,” Annals of Operations Research , vol. 14, no. 1, pp. 105–123, 1988

1988
[142]

Minimum cost ﬂows, MDPs, and l1 -regression in nearly linear time for dense instances,

J. v. d. Brand et al. , “Minimum cost ﬂows, MDPs, and l1 -regression in nearly linear time for dense instances,” arXiv preprint arXiv:2101.05719 , 2021

2021 arXiv
[143]

Improving the Hungarian assignment algorithm,

R. Jonker and T. Volgenant, “Improving the Hungarian assignment algorithm,” Op- erations Research Letters, vol. 5, no. 4, pp. 171–175, 1986

1986
[144]

Path ﬁnding ii: An /slash.right ˜ o (m sqrt (n)) algorithm for the minimum cost ﬂow problem,

Y. T. Lee and A. Sidford, “Path ﬁnding ii: An /slash.right ˜ o (m sqrt (n)) algorithm for the minimum cost ﬂow problem,” arXiv preprint arXiv:1312.6713 , 2013. 482

2013 arXiv
[145]

New eﬀective multithreaded matching algorithms,

F. Manne and M. Halappanavar, “New eﬀective multithreaded matching algorithms,” in 2014 IEEE 28th International Parallel and Distributed Processing Symposium , IEEE, 2014, pp. 519–528

2014
[146]

Understanding the topology and the geometry of the per- sistence diagram space via optimal partial transport,

V. Divol and T. Lacombe, “Understanding the topology and the geometry of the per- sistence diagram space via optimal partial transport,” arXiv preprint arXiv:1901.03048, 2019

1901 arXiv
[147]

Flamary and N

R. Flamary and N. Courty, POT python optimal transport library , 2017. [Online]. A vailable: https://pythonot.github.io/

2017
[148]

Better and simpler error analysis of the sinkhorn– knopp algorithm for matrix scaling,

D. Chakrabarty and S. Khanna, “Better and simpler error analysis of the sinkhorn– knopp algorithm for matrix scaling,” Mathematical Programming, pp. 1–13, 2020

2020
[149]

Approximation algorithms for 1-Wasserstein distance between persistence diagrams,

S. Chen and Y. Wang, “Approximation algorithms for 1-Wasserstein distance between persistence diagrams,” arXiv preprint arXiv:2104.07710 , 2021

2021 arXiv
[150]

Fast image retrieval via embeddings,

P. Indyk and N. Thaper, “Fast image retrieval via embeddings,” in 3rd international workshop on statistical and computational theories of vision , vol. 2, 2003, p. 5

2003
[151]

Scalable near- est neighbor search for optimal transport,

A. Backurs, Y. Dong, P. Indyk, I. Razenshteyn, and T. Wagner, “Scalable near- est neighbor search for optimal transport,” in International Conference on Machine Learning, PMLR, 2020, pp. 497–506

2020
[152]

Approximate nearest neighbors in the space of persistence diagrams,

B. T. Fasy, X. He, Z. Liu, S. Micka, D. L. Millman, and B. Zhu, “Approximate nearest neighbors in the space of persistence diagrams,” arXiv preprint arXiv:1812.11257 , 2018

2018 arXiv
[153]

Indexing point sets for approximate bottleneck distance queries,

B. Mumey, “Indexing point sets for approximate bottleneck distance queries,” arXiv preprint arXiv:1810.09482 , 2018

2018 arXiv
[154]

From word embeddings to doc- ument distances,

M. Kusner, Y. Sun, N. Kolkin, and K. Weinberger, “From word embeddings to doc- ument distances,” in International conference on machine learning , PMLR, 2015, pp. 957–966

2015
[155]

Sinkhorn distances: Lightspeed computation of optimal transport,

M. Cuturi, “Sinkhorn distances: Lightspeed computation of optimal transport,” in Advances in neural information processing systems , 2013, pp. 2292–2300. 483

2013
[156]

Fast parallel algorithms for euclidean min- imum spanning tree and hierarchical spatial clustering,

Y. Wang, S. Yu, Y. Gu, and J. Shun, “Fast parallel algorithms for euclidean min- imum spanning tree and hierarchical spatial clustering,” in Proceedings of the 2021 International Conference on Management of Data , 2021, pp. 1982–1995

2021
[157]

Matching point sets with re- spect to the earth movers distance,

S. Cabello, P. Giannopoulos, C. Knauer, and G. Rote, “Matching point sets with re- spect to the earth movers distance,” in European Symposium on Algorithms, Springer, 2005, pp. 520–531

2005
[158]

Persistence stability for geometric complexes,

F. Chazal, V. de Silva, and S. Oudot, “Persistence stability for geometric complexes,” Geometriae Dedicata, vol. 173, no. 1, pp. 193–214, 2014

2014
[159]

The earth mover’s distance as a metric for image retrieval,

Y. Rubner, C. Tomasi, and L. J. Guibas, “The earth mover’s distance as a metric for image retrieval,” International journal of computer vision , vol. 40, no. 2, pp. 99–121, 2000

2000
[160]

Emergence of scaling in random networks,

A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999

1999
[161]

Linear-complexity data-parallel earth movers distance approximations,

K. Atasu and T. Mittelholzer, “Linear-complexity data-parallel earth movers distance approximations,” in International Conference on Machine Learning , PMLR, 2019, pp. 364–373

2019
[162]

Parallel algorithms,

G. E. Blelloch and B. M. Maggs, “Parallel algorithms,” in Algorithms and Theory of Computation Handbook: Special Topics and Techniques , 2010, pp. 25–25

2010
[163]

Well-separated pair decomposition in linear time?

T. M. Chan, “Well-separated pair decomposition in linear time?” Information Pro- cessing Letters, vol. 107, no. 5, pp. 138–141, 2008

2008
[164]

Har-Peled, Geometric approximation algorithms

S. Har-Peled, Geometric approximation algorithms . American Mathematical Soc., 2011

2011
[165]

Approximation algorithms for shortest path motion planning,

K. Clarkson, “Approximation algorithms for shortest path motion planning,” in Pro- ceedings of the Nineteenth Annual ACM Symposium on Theory of Computing , 1987, pp. 56–65

1987
[166]

Approximating the complete euclidean graph,

J. M. Keil, “Approximating the complete euclidean graph,” in Scandinavian Workshop on Algorithm Theory , Springer, 1988, pp. 208–213. 484

1988
[167]

Fast greedy algorithms for constructing sparse geometric spanners,

J. Gudmundsson, C. Levcopoulos, and G. Narasimhan, “Fast greedy algorithms for constructing sparse geometric spanners,” SIAM Journal on Computing , vol. 31, no. 5, pp. 1479–1500, 2002

2002
[168]

Light euclidean spanners with steiner points,

H. Le and S. Solomon, “Light euclidean spanners with steiner points,” arXiv preprint arXiv:2007.11636, 2020

2007 arXiv
[169]

Cgal: The computational geometry algorithms library,

A. Fabri and S. Pion, “Cgal: The computational geometry algorithms library,” in Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems , 2009, pp. 538–539

2009
[170]

Local routing in WSPD- based spanners,

J.-L. De Carufel, P. Bose, F. Paradis, and V. Dujmovic, “Local routing in WSPD- based spanners,” Journal of Computational Geometry , vol. 12, no. 1, pp. 1–34, 2021

2021
[171]

A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential ﬁelds,

P. B. Callahan and S. R. Kosaraju, “A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential ﬁelds,” Journal of the ACM (JACM), vol. 42, no. 1, pp. 67–90, 1995

1995
[172]

Optimal parallel all-nearest-neighbors using the well-separated pair decomposition,

P. B. Callahan, “Optimal parallel all-nearest-neighbors using the well-separated pair decomposition,” in Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, IEEE, 1993, pp. 332–340

1993
[173]

Parallel preﬁx computation,

R. E. Ladner and M. J. Fischer, “Parallel preﬁx computation,” Journal of the ACM (JACM), vol. 27, no. 4, pp. 831–838, 1980

1980
[174]

Eﬃcient implementations of minimum-cost ﬂow algo- rithms,

Z. Király and P. Kovács, “Eﬃcient implementations of minimum-cost ﬂow algo- rithms,” arXiv preprint arXiv:1207.6381 , 2012

2012 arXiv
[175]

An eﬃcient implementation of the network simplex method,

M. D. Grigoriadis, “An eﬃcient implementation of the network simplex method,” in Netﬂow at Pisa , Springer, 1986, pp. 83–111

1986
[176]

G. B. Dantzig and M. N. Thapa, Linear programming 2: theory and extensions . Springer Science & Business Media, 2006

2006
[177]

New ﬁnite pivoting rules for the simplex method,

R. G. Bland, “New ﬁnite pivoting rules for the simplex method,” Mathematics of operations Research, vol. 2, no. 2, pp. 103–107, 1977

1977
[178]

Lemon–an open source c++ graph template library,

B. Dezs, A. Jüttner, and P. Kovács, “Lemon–an open source c++ graph template library,” Electronic Notes in Theoretical Computer Science , vol. 264, no. 5, pp. 23–45, 2011. 485

2011
[179]

Dynamic trees as search trees via euler tours, applied to the network simplex algorithm,

R. E. Tarjan, “Dynamic trees as search trees via euler tours, applied to the network simplex algorithm,” Mathematical Programming, vol. 78, no. 2, pp. 169–177, 1997

1997
[180]

A faster primal network simplex algorithm,

C. C. Aggarwal, H. Kaplan, and R. E. Tarjan, “A faster primal network simplex algorithm,” 1996

1996
[181]

Eﬃciency of the network simplex algorithm for the maximum ﬂow problem,

A. V. Goldberg, M. D. Grigoriadis, and R. E. Tarjan, “Eﬃciency of the network simplex algorithm for the maximum ﬂow problem,” Princeton Univ., Dept. Computer Science, Tech. Rep., 1988

1988
[182]

van den Brand et al

J. van den Brand et al. , A deterministic almost-linear time algorithm for minimum- cost ﬂow , 2023. arXiv: 2309.16629 [cs.DS] . [Online]. A vailable: https://arxiv.org/ abs/2309.16629

2023 arXiv
[183]

Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis,

V. Vassilevska Williams, “Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis,” in 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) , T. Husfeldt and I. Kanj, Eds., ser. Leibniz Interna...

2015 doi
[184]

On some ﬁne-grained questions in algorithms and complexity,

V. V. Williams, “On some ﬁne-grained questions in algorithms and complexity,” in Proceedings of the international congress of mathematicians: Rio de janeiro 2018 , World Scientiﬁc, 2018, pp. 3447–3487

2018
[185]

A near-linear time ε-approximation algorithm for geometric bipartite matching,

S. Raghvendra and P. K. Agarwal, “A near-linear time ε-approximation algorithm for geometric bipartite matching,” Journal of the ACM (JACM) , vol. 67, no. 3, pp. 1–19, 2020

2020
[186]

Deterministic, near-linear -approximation algorithm for geometric bipartite matching,

P. K. Agarwal, H.-C. Chang, S. Raghvendra, and A. Xiao, “Deterministic, near-linear -approximation algorithm for geometric bipartite matching,” in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , 2022, pp. 1052– 1065

2022
[187]

Conditional hardness of earth mover distance,

D. Rohatgi, “Conditional hardness of earth mover distance,” arXiv preprint arXiv:1909.11068, 2019. 486

1909 arXiv
[188]

Approximation and ﬁxed parameter sub- quadratic algorithms for radius and diameter in sparse graphs,

A. Abboud, V. V. Williams, and J. Wang, “Approximation and ﬁxed parameter sub- quadratic algorithms for radius and diameter in sparse graphs,” in Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete Algorithms , SIAM, 2016, pp. 377–391

2016
[189]

O. S. Center, Pitzer supercomputer, 2018. [Online]. A vailable: http://osc.edu/ark: /19495/hpc56htp

2018
[190]

Graph reconstruction by discrete Morse theory,

T. K. Dey, J. Wang, and Y. Wang, “Graph reconstruction by discrete Morse theory,” in Proceedings 34th International Symposium on Computational Geometry (SoCG) , 2018, 31:1–31:15

2018
[191]

7 Tesla MRI of the ex vivo human brain at 100 micron resolution,

B. L. Edlow et al., “7 Tesla MRI of the ex vivo human brain at 100 micron resolution,” Scientiﬁc data , vol. 6, no. 1, pp. 1–10, 2019

2019
[192]

Ripser. py: A lean persistent homology library for python.,

C. Tralie, N. Saul, and R. Bar-On, “Ripser. py: A lean persistent homology library for python.,” J. Open Source Software , vol. 3, no. 29, p. 925, 2018

2018
[193]

Paraview: An end-user tool for large data visual- ization,

J. Ahrens, B. Geveci, and C. Law, “Paraview: An end-user tool for large data visual- ization,” The Visualization Handbook , vol. 717, 2005

2005
[194]

An open, multi-vendor, multi-ﬁeld-strength brain mr dataset and analysis of publicly available skull stripping methods agreement,

R. Souza et al. , “An open, multi-vendor, multi-ﬁeld-strength brain mr dataset and analysis of publicly available skull stripping methods agreement,” NeuroImage, vol. 170, pp. 482–494, 2018

2018
[195]

Eﬃcient and generalizable statistical models of shape and appearance for analysis of cardiac mri,

A. Andreopoulos and J. K. Tsotsos, “Eﬃcient and generalizable statistical models of shape and appearance for analysis of cardiac mri,” Medical Image Analysis , vol. 12, no. 3, pp. 335–357, 2008

2008
[196]

Array programming with NumPy,

C. R. Harris et al. , “Array programming with NumPy,” Nature, vol. 585, no. 7825, pp. 357–362, Sep. 2020. doi: 10.1038/s41586-020-2649-2 . [Online]. A vailable: https: //doi.org/10.1038/s41586-020-2649-2

2020 doi
[197]

Similarity-based classiﬁcation: Concepts and algorithms.,

Y. Chen, E. K. Garcia, M. R. Gupta, A. Rahimi, and L. Cazzanti, “Similarity-based classiﬁcation: Concepts and algorithms.,” Journal of Machine Learning Research , vol. 10, no. 3, 2009

2009
[198]

Content-based multimedia information retrieval: State of the art and challenges,

M. S. Lew, N. Sebe, C. Djeraba, and R. Jain, “Content-based multimedia information retrieval: State of the art and challenges,” ACM Transactions on Multimedia Com- puting, Communications, and Applications (TOMM) , vol. 2, no. 1, pp. 1–19, 2006. 487

2006
[199]

Parallel algorithms for nearest neighbor search problems in high dimensions,

B. Xiao and G. Biros, “Parallel algorithms for nearest neighbor search problems in high dimensions,” SIAM Journal on Scientiﬁc Computing , vol. 38, no. 5, S667–S699, 2016

2016
[200]

A simple algorithm for nearest neighbor search in high dimensions,

S. A. Nene and S. K. Nayar, “A simple algorithm for nearest neighbor search in high dimensions,” IEEE Transactions on pattern analysis and machine intelligence , vol. 19, no. 9, pp. 989–1003, 1997

1997
[201]

Finding the positive nearest-neighbor in rec- ommender systems.,

A. M. Roumani and D. B. Skillicorn, “Finding the positive nearest-neighbor in rec- ommender systems.,” in DMIN, 2007, pp. 190–196

2007
[202]

The (new) Yale sparse matrix package,

S. C. Eisenstat, H. C. Elman, M. H. Schultz, and A. H. Sherman, “The (new) Yale sparse matrix package,” in Elliptic Problem Solvers , Elsevier, 1984, pp. 45–52

1984
[203]

Parallel merge sort,

R. Cole, “Parallel merge sort,” SIAM Journal on Computing , vol. 17, no. 4, pp. 770– 785, 1988

1988
[204]

GPU accelerated pivoting rules for the simplex algo- rithm,

N. Ploskas and N. Samaras, “GPU accelerated pivoting rules for the simplex algo- rithm,” Journal of Systems and Software , vol. 96, pp. 1–9, 2014

2014
[205]

Fast unbalanced optimal transport on tree,

R. Sato, M. Yamada, and H. Kashima, “Fast unbalanced optimal transport on tree,” arXiv preprint arXiv:2006.02703 , 2020

2006 arXiv
[206]

A faster strongly polynomial minimum cost ﬂow algorithm,

J. B. Orlin, “A faster strongly polynomial minimum cost ﬂow algorithm,” Operations research, vol. 41, no. 2, pp. 338–350, 1993

1993
[207]

Learning representations of persistence barcodes.,

C. D. Hofer, R. Kwitt, and M. Niethammer, “Learning representations of persistence barcodes.,” J. Mach. Learn. Res. , vol. 20, no. 126, pp. 1–45, 2019

2019
[208]

Topo- logical graph neural networks,

M. Horn, E. De Brouwer, M. Moor, Y. Moreau, B. Rieck, and K. Borgwardt, “Topo- logical graph neural networks,” arXiv preprint arXiv:2102.07835 , 2021

2021 arXiv
[209]

Extending persistence using poincaré and lefschetz duality,

D. Cohen-Steiner, H. Edelsbrunner, and J. Harer, “Extending persistence using poincaré and lefschetz duality,” Foundations of Computational Mathematics , vol. 9, no. 1, pp. 79–103, 2009

2009
[210]

Link prediction with persistent homology: An interactive view,

Z. Yan, T. Ma, L. Gao, Z. Tang, and C. Chen, “Link prediction with persistent homology: An interactive view,” in International Conference on Machine Learning , PMLR, 2021, pp. 11 659–11 669. 488

2021
[211]

Graph ﬁltration learn- ing,

C. Hofer, F. Graf, B. Rieck, M. Niethammer, and R. Kwitt, “Graph ﬁltration learn- ing,” in International Conference on Machine Learning , PMLR, 2020, pp. 4314–4323

2020
[212]

The reduction of a graph to canonical form and the algebra which appears therein,

B. Weisfeiler and A. Leman, “The reduction of a graph to canonical form and the algebra which appears therein,” NTI, Series , vol. 2, no. 9, pp. 12–16, 1968

1968
[213]

Deep sets,

M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, and A. J. Smola, “Deep sets,” Advances in neural information processing systems , vol. 30, 2017

2017
[214]

What graph neural networks cannot learn: Depth vs width,

A. Loukas, “What graph neural networks cannot learn: Depth vs width,” arXiv preprint arXiv:1907.03199 , 2019

1907 arXiv
[215]

How powerful are graph neural net- works?

K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural net- works?” arXiv preprint arXiv:1810.00826 , 2018

2018 arXiv
[216]

A comprehensive survey on graph neural networks,

Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” IEEE transactions on neural networks and learning systems, vol. 32, no. 1, pp. 4–24, 2020

2020
[217]

Inductive representation learning on large graphs,

W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017, pp. 1025–1035

2017
[218]

Semi-supervised classiﬁcation with graph convolutional networks,

T. N. Kipf and M. Welling, “Semi-supervised classiﬁcation with graph convolutional networks,” arXiv preprint arXiv:1609.02907 , 2016

2016 arXiv
[219]

Power and limits of the weisfeiler-leman algorithm,

S. Kiefer, N. Immerman, P. Schweitzer, and M. Grohe, “Power and limits of the weisfeiler-leman algorithm,” Fachgruppe Informatik, Tech. Rep., 2020

2020
[220]

Identity-aware graph neural networks,

J. You, J. Gomes-Selman, R. Ying, and J. Leskovec, “Identity-aware graph neural networks,” arXiv preprint arXiv:2101.10320 , 2021

2021 arXiv
[221]

Weisfeiler and leman go neural: Higher-order graph neural net- works,

C. Morris et al. , “Weisfeiler and leman go neural: Higher-order graph neural net- works,” in Proceedings of the AAAI Conference on Artiﬁcial Intelligence , vol. 33, 2019, pp. 4602–4609

2019
[222]

Weisfeiler and lehman go cellular: Cw networks,

C. Bodnar et al. , “Weisfeiler and lehman go cellular: Cw networks,” Advances in Neural Information Processing Systems , vol. 34, 2021. 489

2021
[223]

Topology-aware graph pooling networks,

H. Gao, Y. Liu, and S. Ji, “Topology-aware graph pooling networks,” IEEE Transac- tions on Pattern Analysis and Machine Intelligence , vol. 43, no. 12, pp. 4512–4518, 2021

2021
[224]

Self-attention graph pooling,

J. Lee, I. Lee, and J. Kang, “Self-attention graph pooling,” in International conference on machine learning , PMLR, 2019, pp. 3734–3743

2019
[225]

Gated graph sequence neural networks,

Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel, “Gated graph sequence neural networks,” arXiv preprint arXiv:1511.05493 , 2015

2015 arXiv
[226]

Hierarchical graph representation learning with diﬀerentiable pooling,

Z. Ying, J. You, C. Morris, X. Ren, W. Hamilton, and J. Leskovec, “Hierarchical graph representation learning with diﬀerentiable pooling,” Advances in neural information processing systems, vol. 31, 2018

2018
[227]

Graph pooling for graph neural networks: Progress, challenges, and opportunities,

C. Liu et al. , “Graph pooling for graph neural networks: Progress, challenges, and opportunities,” arXiv preprint arXiv:2204.07321 , 2022

2022 arXiv
[228]

Dist2cycle: A simplicial neural network for homology localization,

A. D. Keros, V. Nanda, and K. Subr, “Dist2cycle: A simplicial neural network for homology localization,” Proceedings of the AAAI Conference on Artiﬁcial Intelligence, vol. 36, no. 7, pp. 7133–7142, Jun. 2022. doi: 10.1609/aaai.v36i7.20673 . [Online]. A vailable: https://ojs.aa...

2022 doi
[229]

Topological feature extraction and visualization of whole slide images using graph neural net- works,

J. Levy, C. Haudenschild, C. Barwick, B. Christensen, and L. Vaickus, “Topological feature extraction and visualization of whole slide images using graph neural net- works,” in BIOCOMPUTING 2021: Proceedings of the Paciﬁc Symposium , World Scientiﬁc, 2020, pp. 285–296

2021
[230]

Can neural networks learn persistent homology features?

G. Montúfar, N. Otter, and Y. Wang, “Can neural networks learn persistent homology features?” arXiv preprint arXiv:2011.14688 , 2020

2011 arXiv
[231]

Neural approximation of extended persistent homology on graphs,

Z. Yan, T. Ma, L. Gao, Z. Tang, Y. Wang, and C. Chen, “Neural approximation of extended persistent homology on graphs,” CoRR, vol. abs/2201.12032, 2022. arXiv: 2201.12032 . [Online]. A vailable: https://arxiv.org/abs/2201.12032

2022 arXiv
[232]

Persistence enhanced graph neural network,

Q. Zhao, Z. Ye, C. Chen, and Y. Wang, “Persistence enhanced graph neural network,” in Proceedings of the Twenty Third International Conference on Artiﬁcial Intelligence and Statistics , S. Chiappa and R. Calandra, Eds., ser. Proceedings of Machine Learn- ing Research, vol. 108...

2020
[233]

Cycle representation learning for in- ductive relation prediction,

Z. Yan, T. Ma, L. Gao, Z. Tang, and C. Chen, “Cycle representation learning for in- ductive relation prediction,” in ICLR 2022 Workshop on Geometrical and Topological Representation Learning, 2022

2022
[234]

de Surrel et al

T. de Surrel et al. , Ripsnet: A general architecture for fast and robust estimation of the persistent homology of point clouds , 2022. doi: 10.48550/ARXIV .2202.01725 . [Online]. A vailable: https://arxiv.org/abs/2202.01725

2022 doi arXiv
[235]

Peano and G

G. Peano and G. Peano, Sur une courbe, qui remplit toute une aire plane . Springer, 1990

1990
[236]

Sagan, Space-ﬁlling curves

H. Sagan, Space-ﬁlling curves . Springer Science & Business Media, 2012

2012
[237]

Sur le probleme des courbes gauches en topologie,

C. Kuratowski, “Sur le probleme des courbes gauches en topologie,” Fundamenta mathematicae, vol. 15, no. 1, pp. 271–283, 1930

1930
[238]

Three-dimensional graph drawing,

R. F. Cohen, P. Eades, T. Lin, and F. Ruskey, “Three-dimensional graph drawing,” in Graph Drawing: DIMACS International Workshop, GD’94 Princeton, New Jersey, USA, October 10–12, 1994 Proceedings 2 , Springer, 1995, pp. 1–11

1994
[239]

Edelsbrunner, Algorithms in combinatorial geometry

H. Edelsbrunner, Algorithms in combinatorial geometry . Springer Science & Business Media, 1987, vol. 10

1987
[240]

Matouek, A

J. Matouek, A. Björner, G. M. Ziegler, et al., Using the Borsuk-Ulam theorem: lectures on topological methods in combinatorics and geometry . Springer, 2003, vol. 2003

2003
[241]

Building powerful and equivariant graph neural networks with structural message-passing,

C. Vignac, A. Loukas, and P. Frossard, “Building powerful and equivariant graph neural networks with structural message-passing,” Advances in Neural Information Processing Systems, vol. 33, pp. 14 143–14 155, 2020

2020
[242]

Repre- sentation learning on graphs with jumping knowledge networks,

K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka, “Repre- sentation learning on graphs with jumping knowledge networks,” in International conference on machine learning , PMLR, 2018, pp. 5453–5462

2018
[243]

Beyond homophily in graph neural networks: Current limitations and eﬀective designs,

J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra, “Beyond homophily in graph neural networks: Current limitations and eﬀective designs,” Advances in Neural Information Processing Systems , vol. 33, pp. 7793–7804, 2020

2020
[244]

Tackling over-smoothing for general graph convolutional networks,

W. Huang, Y. Rong, T. Xu, F. Sun, and J. Huang, “Tackling over-smoothing for general graph convolutional networks,” arXiv preprint arXiv:2008.09864 , 2020. 491

2008 arXiv
[245]

Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks,

K. Oono and T. Suzuki, “Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks,” Advances in Neural Information Processing Systems , vol. 33, pp. 18 917–18 930, 2020

2020
[246]

Deterministic parallel list ranking,

R. J. Anderson and G. L. Miller, “Deterministic parallel list ranking,” Algorithmica, vol. 6, no. 1, pp. 859–868, 1991

1991
[247]

Can graph neural networks count sub- structures?

Z. Chen, L. Chen, S. Villar, and J. Bruna, “Can graph neural networks count sub- structures?” arXiv preprint arXiv:2002.04025 , 2020

2002 arXiv
[248]

An end-to-end deep learning archi- tecture for graph classiﬁcation,

M. Zhang, Z. Cui, M. Neumann, and Y. Chen, “An end-to-end deep learning archi- tecture for graph classiﬁcation,” in Proceedings of the AAAI conference on artiﬁcial intelligence, vol. 32, 2018

2018
[249]

Generalization and representational limits of graph neural networks,

V. Garg, S. Jegelka, and T. Jaakkola, “Generalization and representational limits of graph neural networks,” in International Conference on Machine Learning , PMLR, 2020, pp. 3419–3430

2020
[250]

Tu- dataset: A collection of benchmark datasets for learning with graphs,

C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann, “Tu- dataset: A collection of benchmark datasets for learning with graphs,” arXiv preprint arXiv:2007.08663, 2020

2007 arXiv
[251]

Fast graph representation learning with pytorch geomet- ric,

M. Fey and J. E. Lenssen, “Fast graph representation learning with pytorch geomet- ric,” arXiv preprint arXiv:1903.02428 , 2019

1903 arXiv
[252]

Pytorch: An imperative style, high-performance deep learning li- brary,

A. Paszke et al. , “Pytorch: An imperative style, high-performance deep learning li- brary,” Advances in neural information processing systems , vol. 32, 2019

2019
[253]

Adversarial graph augmentation to im- prove graph contrastive learning,

S. Suresh, P. Li, C. Hao, and J. Neville, “Adversarial graph augmentation to im- prove graph contrastive learning,” Advances in Neural Information Processing Sys- tems, vol. 34, 2021

2021
[254]

Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization,

F.-Y. Sun, J. Hoﬀmann, V. Verma, and J. Tang, “Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization,” arXiv preprint arXiv:1908.01000 , 2019

1908 arXiv
[255]

Sets2sets: Learning from sequential sets with neural networks,

H. Hu and X. He, “Sets2sets: Learning from sequential sets with neural networks,” in Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining , 2019, pp. 1491–1499. 492

2019
[256]

Distance encoding: Design provably more powerful neural networks for graph representation learning,

P. Li, Y. Wang, H. Wang, and J. Leskovec, “Distance encoding: Design provably more powerful neural networks for graph representation learning,” Advances in Neural Information Processing Systems , vol. 33, pp. 4465–4478, 2020

2020
[257]

On weisfeiler-leman invariance: Subgraph counts and related graph properties,

V. Arvind, F. Fuhlbrück, J. Köbler, and O. Verbitsky, “On weisfeiler-leman invariance: Subgraph counts and related graph properties,” Journal of Computer and System Sciences, vol. 113, pp. 42–59, 2020

2020
[258]

On the combinatorial power of the weisfeiler-lehman algorithm,

M. Fürer, “On the combinatorial power of the weisfeiler-lehman algorithm,” in Inter- national Conference on Algorithms and Complexity , Springer, 2017, pp. 260–271

2017
[259]

Open graph benchmark: Datasets for machine learning on graphs,

W. Hu et al. , “Open graph benchmark: Datasets for machine learning on graphs,” arXiv preprint arXiv:2005.00687 , 2020

2005 arXiv
[260]

Hatcher, a. algebraic topology (cambridge university press, 2002), 556 pp., 0 521 79540 0 (softback),č 20.95, 0 521 79160 x (hardback),č 60,

S. MERKULOV, “Hatcher, a. algebraic topology (cambridge university press, 2002), 556 pp., 0 521 79540 0 (softback),č 20.95, 0 521 79160 x (hardback),č 60,” Proceedings of the Edinburgh Mathematical Society , vol. 46, no. 2, pp. 511–512, 2003

2002
[261]

Slink: An optimally eﬃcient algorithm for the single-link cluster method,

R. Sibson, “Slink: An optimally eﬃcient algorithm for the single-link cluster method,” The computer journal , vol. 16, no. 1, pp. 30–34, 1973

1973
[262]

An improved equivalence algorithm,

B. A. Galler and M. J. Fisher, “An improved equivalence algorithm,” Communications of the ACM , vol. 7, no. 5, pp. 301–303, 1964

1964
[263]

A data structure for dynamic trees,

D. D. Sleator and R. E. Tarjan, “A data structure for dynamic trees,” in Proceedings of the thirteenth annual ACM symposium on Theory of computing , 1981, pp. 114–122

1981
[264]

Self-adjusting binary search trees,

D. D. Sleator and R. E. Tarjan, “Self-adjusting binary search trees,” Journal of the ACM (JACM), vol. 32, no. 3, pp. 652–686, 1985

1985
[265]

Measuring and relieving the over-smoothing problem for graph neural networks from the topological view,

D. Chen, Y. Lin, W. Li, P. Li, J. Zhou, and X. Sun, “Measuring and relieving the over-smoothing problem for graph neural networks from the topological view,” in Proceedings of the AAAI Conference on Artiﬁcial Intelligence , vol. 34, 2020, pp. 3438– 3445

2020
[266]

Recommender systems,

L. Lü, M. Medo, C. H. Yeung, Y.-C. Zhang, Z.-K. Zhang, and T. Zhou, “Recommender systems,” Physics reports, vol. 519, no. 1, pp. 1–49, 2012. 493

2012
[267]

Hypergraph neural networks,

Y. Feng, H. You, Z. Zhang, R. Ji, and Y. Gao, “Hypergraph neural networks,” in Proceedings of the AAAI conference on artiﬁcial intelligence , vol. 33, 2019, pp. 3558– 3565

2019
[268]

Link prediction in social networks based on hyper- graph,

D. Li, Z. Xu, S. Li, and X. Sun, “Link prediction in social networks based on hyper- graph,” in Proceedings of the 22nd international conference on world wide web , 2013, pp. 41–42

2013
[269]

Unignn: A uniﬁed framework for graph and hypergraph neural networks,

J. Huang and J. Yang, “Unignn: A uniﬁed framework for graph and hypergraph neural networks,” arXiv preprint arXiv:2105.00956 , 2021

2021 arXiv
[270]

Improving graph neural network expressivity via subgraph isomorphism counting,

G. Bouritsas, F. Frasca, S. Zafeiriou, and M. M. Bronstein, “Improving graph neural network expressivity via subgraph isomorphism counting,” IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 45, no. 1, pp. 657–668, 2022

2022
[271]

Random features strengthen graph neural networks,

R. Sato, M. Yamada, and H. Kashima, “Random features strengthen graph neural networks,” in Proceedings of the 2021 SIAM international conference on data mining (SDM), SIAM, 2021, pp. 333–341

2021
[272]

Invariant and equivariant graph networks,

H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman, “Invariant and equivariant graph networks,” arXiv preprint arXiv:1812.09902 , 2018

2018 arXiv
[273]

Higher order learning with graphs,

S. Agarwal, K. Branson, and S. Belongie, “Higher order learning with graphs,” in Proceedings of the 23rd international conference on Machine learning , 2006, pp. 17– 24

2006
[274]

Structural equivalence of individuals in social networks,

F. Lorrain and H. C. White, “Structural equivalence of individuals in social networks,” The Journal of mathematical sociology , vol. 1, no. 1, pp. 49–80, 1971

1971
[275]

Hypergraph isomorphism computation,

Y. Feng, J. Han, S. Ying, and Y. Gao, “Hypergraph isomorphism computation,” arXiv preprint arXiv:2307.14394 , 2023

2023 arXiv
[276]

Hnhn: Hypergraph networks with hyperedge neurons,

Y. Dong, W. Sawin, and Y. Bengio, “Hnhn: Hypergraph networks with hyperedge neurons,” arXiv preprint arXiv:2006.12278 , 2020

2006 arXiv
[277]

Hypergcn: A new method for training graph convolutional networks on hypergraphs,

N. Yadati, M. Nimishakavi, P. Yadav, V. Nitin, A. Louis, and P. Talukdar, “Hypergcn: A new method for training graph convolutional networks on hypergraphs,” Advances in neural information processing systems , vol. 32, 2019. 494

2019
[278]

Hgnn+: General hypergraph neural networks,

Y. Gao, Y. Feng, S. Ji, and R. Ji, “Hgnn+: General hypergraph neural networks,” IEEE Transactions on Pattern Analysis and Machine Intelligence , 2022

2022
[279]

Learning over families of sets-hypergraph representation learning for higher order tasks,

B. Srinivasan, D. Zheng, and G. Karypis, “Learning over families of sets-hypergraph representation learning for higher order tasks,” in Proceedings of the 2021 SIAM International Conference on Data Mining (SDM) , SIAM, 2021, pp. 756–764

2021
[280]

You are allset: A multiset function framework for hypergraph neural networks,

E. Chien, C. Pan, J. Peng, and O. Milenkovic, “You are allset: A multiset function framework for hypergraph neural networks,” in International Conference on Learning Representations, 2022. [Online]. A vailable: https : / / openreview . net / forum ? id = hp BTIv2uy_E

2022
[281]

Beyond link prediction: Predicting hy- perlinks in adjacency space,

M. Zhang, Z. Cui, S. Jiang, and Y. Chen, “Beyond link prediction: Predicting hy- perlinks in adjacency space,” in Proceedings of the AAAI Conference on Artiﬁcial Intelligence, vol. 32, 2018

2018
[282]

Principled hyperedge prediction with structural spectral features and neural networks,

C. Wan, M. Zhang, W. Hao, S. Cao, P. Li, and C. Zhang, “Principled hyperedge prediction with structural spectral features and neural networks,” arXiv preprint arXiv:2106.04292, 2021

2021 arXiv
[283]

Hyper-sagnn: A self-attention based graph neural network for hypergraphs,

R. Zhang, Y. Zou, and J. Ma, “Hyper-sagnn: A self-attention based graph neural network for hypergraphs,” arXiv preprint arXiv:1911.02613 , 2019

1911 arXiv
[284]

A survey on hyperlink prediction,

C. Chen and Y.-Y. Liu, “A survey on hyperlink prediction,” arXiv preprint arXiv:2207.02911, 2022

2022 arXiv
[285]

A theoretical comparison of graph neural net- work extensions,

P. A. Papp and R. Wattenhofer, “A theoretical comparison of graph neural net- work extensions,” in International Conference on Machine Learning , PMLR, 2022, pp. 17 323–17 345

2022
[286]

Nested graph neural networks,

M. Zhang and P. Li, “Nested graph neural networks,” in Advances in Neural In- formation Processing Systems , M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., vol. 34, Curran Associates, Inc., 2021, pp. 15 734–15 747. [Online]. A vailable: https://proc...

2021
[287]

Local vertex colouring graph neural networks,

S. Li, D. Kim, and Q. Wang, “Local vertex colouring graph neural networks,” 2023

2023
[288]

Substructure aware graph neural networks,

D. Zeng, W. Liu, W. Chen, L. Zhou, M. Zhang, and H. Qu, “Substructure aware graph neural networks,” in Proceedings of the AAAI Conference on Artiﬁcial Intelligence , vol. 37, 2023, pp. 11 129–11 137. 495

2023
[289]

A new perspective on

A. Wijesinghe and Q. Wang, “A new perspective on" how graph neural networks go be- yond weisfeiler-lehman?",” in International Conference on Learning Representations , 2021

2021
[290]

Rethinking the expressive power of gnns via graph biconnectivity,

B. Zhang, S. Luo, L. Wang, and D. He, “Rethinking the expressive power of gnns via graph biconnectivity,” arXiv preprint arXiv:2301.09505 , 2023

2023 arXiv
[291]

Cycle to clique (cy2c) graph neural network: A sight to see beyond neighborhood aggregation,

Y. Y. Choi, S. W. Park, Y. Woo, and U. J. Choi, “Cycle to clique (cy2c) graph neural network: A sight to see beyond neighborhood aggregation,” in The Eleventh International Conference on Learning Representations
[292]

Cell attention networks,

L. Giusti, C. Battiloro, L. Testa, P. Di Lorenzo, S. Sardellitti, and S. Barbarossa, “Cell attention networks,” arXiv preprint arXiv:2209.08179 , 2022

2022 arXiv
[293]

Improving out-of-distribution robustness via selective augmentation,

H. Yao et al. , “Improving out-of-distribution robustness via selective augmentation,” in International Conference on Machine Learning , PMLR, 2022, pp. 25 407–25 437

2022
[294]

A group-theoretic framework for data augmen- tation,

S. Chen, E. Dobriban, and J. H. Lee, “A group-theoretic framework for data augmen- tation,” Journal of Machine Learning Research , vol. 21, no. 245, pp. 1–71, 2020

2020
[295]

Smote: Synthetic minority over-sampling technique,

N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, “Smote: Synthetic minority over-sampling technique,” Journal of artiﬁcial intelligence research , vol. 16, pp. 321–357, 2002

2002
[296]

Mocl: Data-driven molecular ﬁngerprint via knowledge-aware contrastive learning from molecular graph,

M. Sun, J. Xing, H. Wang, B. Chen, and J. Zhou, “Mocl: Data-driven molecular ﬁngerprint via knowledge-aware contrastive learning from molecular graph,” in Pro- ceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining , 2021, pp. 3585–3594

2021
[297]

Variational graph auto-encoders,

T. N. Kipf and M. Welling, “Variational graph auto-encoders,”arXiv preprint arXiv:1611.07308, 2016

2016 arXiv
[298]

Data augmenta- tion for graph neural networks,

T. Zhao, Y. Liu, L. Neves, O. Woodford, M. Jiang, and N. Shah, “Data augmenta- tion for graph neural networks,” in Proceedings of the aaai conference on artiﬁcial intelligence, vol. 35, 2021, pp. 11 015–11 023

2021
[2015]

A vailable: http://gudhi.gforge.inria.fr/doc/latest/

[Online]. A vailable: http://gudhi.gforge.inria.fr/doc/latest/
[5411]

[Online]

doi: 10.1145/28869.28874 . [Online]. A vailable: https://doi.org/10.1145/28869. 28874

Pith tools

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

[1] [1]

Hypha: A framework based on separation of parallelisms to accelerate persistent homology matrix reduc- tion,

S. Zhang, M. Xiao, C. Guo, L. Geng, H. Wang, and X. Zhang, “Hypha: A framework based on separation of parallelisms to accelerate persistent homology matrix reduc- tion,” in Proceedings of the ACM International Conference on Supercomputing, ACM, 2019, pp. 69–81

2019

[2] [2]

Gpu-accelerated computation of Vietoris-Rips persistence barcodes,

S. Zhang, M. Xiao, and H. Wang, “Gpu-accelerated computation of Vietoris-Rips persistence barcodes,” arXiv preprint arXiv:2003.07989 , 2020

arXiv 2003

[3] [3]

GPU-accelerated computation of Vietoris-Rips persistence barcodes,

S. Zhang, M. Xiao, and H. Wang, “GPU-accelerated computation of Vietoris-Rips persistence barcodes,” in 36th International Symposium on Computational Geometry (SoCG 2020) , Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020

2020

[4] [4]

Approximating 1-wasserstein distance between persis- tence diagrams by graph sparsiﬁcation,

T. K. Dey and S. Zhang, “Approximating 1-wasserstein distance between persis- tence diagrams by graph sparsiﬁcation,” in 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) , pp. 169–183. doi: 10.1137/1. 9781611977042.14 . eprint: https://epubs.siam.org/doi/pdf/10.1137/1.9781611977042. 14 . [Online]. A vailable: https://epu...

doi:10.1137/1 2022

[5] [5]

Geﬂ: Extended ﬁltration learning for graph classiﬁcation,

S. Zhang, S. Mukherjee, and T. K. Dey, “Geﬂ: Extended ﬁltration learning for graph classiﬁcation,” in Learning on Graphs Conference , PMLR, 2022, pp. 16–1

2022

[6] [6]

Expressive higher-order link prediction through hypergraph symmetry breaking,

S. Zhang, C. Xin, and T. K. Dey, “Expressive higher-order link prediction through hypergraph symmetry breaking,” arXiv preprint arXiv:2402.11339 , 2024

arXiv 2024

[7] [7]

Expressive higher-order link prediction through hypergraph symmetry breaking,

S. Zhang, C. Xin, and T. K. Dey, “Expressive higher-order link prediction through hypergraph symmetry breaking,” Transactions on Machine Learning Research , 2024. [Online]. A vailable: https://openreview.net/forum?id=oG65SjZNIF

2024

[8] [8]

S. J. Russell and P. Norvig, Artiﬁcial intelligence: a modern approach . Pearson, 2016

2016