The decomposition of the higher-order homology embedding constructed from the $k$-Laplacian
Authors: Yu-Chia Chen
Marina Meila
Venue: NeurIPS 2021 Oral (2021)
Keywords: homology embedding
Hodge Laplacian
unsupervised learning
spectral method
topological data analysis

Abstract: The null space of the $k$-th order Laplacian $\mathbf{\mathcal L}_k$, known as the {\em $k$-th homology vector space}, encodes the non-trivial topology of a manifold or a network. Understanding the structure of the homology embedding can thus disclose geometric or topological information from the data. The study of the null space embedding of the graph Laplacian $\mathbf{\mathcal L}_0$ has spurred new research and applications, such as spectral clustering algorithms with theoretical guarantees and estimators of the Stochastic Block Model. In this work, we investigate the geometry of the $k$-th homology embedding and focus on cases reminiscent of spectral clustering. Namely, we analyze the {\em connected sum} of manifolds as a perturbation to the direct sum of their homology embeddings. We propose an algorithm to factorize the homology embedding into subspaces corresponding to a manifold's simplest topological components. The proposed framework is applied to the {\em shortest homologous loop detection} problem, a problem known to be NP-hard in general. Our spectral loop detection algorithm scales better than existing methods and is effective on diverse data such as point clouds and images. 

The decomposition of the higher-order homology embedding constructed from the k-Laplacian
Yu-Chia Chen
Marina Meilä Department of Statistics University of Washington Seattle, WA 98195 mmp2@uw.. edu
Electrical & Computer Engineering University of Washington Seattle, WA 98195
yuchaz@uw. edu
Abstract
The null space of the k-th order Laplacian Ls. known as the k-th homology vector space, encodes the non-trivial topology of manifold network. Understanding the structure of the homology embedding can thus disclose geometric or topolog- ical information from the data. The study of the null space embedding of the graph Laplacian Lo has spurred new research and applications, such as spectral clustering algorithms with theoretical guarantees and estimators of the Stochastic Block Model. In this work, we investigate the geometry of the k-th homology embedding and focus on cases reminiscent of spectral clustering. Namely, we analyze the connected sum of manifolds as a perturbation of the direct sum of their homology embeddings. We propose an algorithm to factorize the homol- ogy embedding into subspaces corresponding to a manifold's 's simplest topological components. The proposed framework applied to the shortest homologous loop detection problem, a problem known to be Narhard in general. Our spectral loop detection algorithm complements existing methods topological data analysis. It scales better than existing methods with no assumptions on the structure of data and effective on diverse data such as point clouds and images.
Motivation
The k-th homology vector space Hy provides rich geometric information on manifolds/networks. For instance, the zeroth, the first, and the second homology vector spaces identify the connected components, the loops, and the cavities in the manifold, respectively. Topological Data Analysis (TDA) [24,, 58] (as well as other early works in this field) has found wide use in analyzing biological [BI, A7 human behavior [II. 644,, or other complex systems [58]. Even though they easily generalize to k 2 1, additional efforts are needed to extract topological features (e.g., instances of loops) besides ranks due to the combinatorial complexity of the structures that support them.
Spectral methods based on k-Laplacians (Cx), by contrast, investigate H4 in a linear algebraic manner, abundant geometric information can extracted from the homology embedding Y (the null space eigenvectors of L*) of H4. Analysis of the eigenfunctions (of Ho) [14] 37, An, g[y]] of the graph Laplacian Co is pivotal in providing guarantees for spectral clustering and community detection algorithms in well-separated datasets. Recent advances in this field [RL 12, [Σ] extend the existing spectral algorithms based on Co to 2 1; however, the theoretical analysis of of He, unlike spectral clustering, is less developed, in spite of intriguing empirical results by [2I]]. Here, we put these observations on a formal footing based on the concepts of connected sum and prime decomposition of manifolds (Section D and C). We examine these operations through the lens of the (subspace) perturbation to the homology embedding of the discrete k-Laplacian La (an estimator of the continuous k- k-Hodge Laplacian operator A₂) finite samples (Section H.) This framework
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

finds applications in, i.c., identifying the shortest homologous loops (Section DD. Lastly, we support our theoretical claims with numerous empirical results from point clouds and images.
2 Background in Hodge theory and topology
Simplicial and cubical complex. An abstract complex is natural extension of a graph designed to capture higher-orde relationships between its vertices. A simplicial k-complex (used when the data are point clouds or networks) is a tuple SC& = (Zo.... ,Ex), with E, being a set of di- mensional simplices, such that every face of simplex E Eg is in Σe-1 for l S k. As side note, graph = (V, F)) is an SC₁; and SC₂ = (V, F, T), which is commonly used in edge flow learning [T22 I is obtained by adding set of 3-cliques (triangles) T of G. This procedure extends to defining Dg as the set of all f-cliques of G. with the resulting complex called a clique complex of the graph G. This complex is also known as a Vietoris-Rips (VR) complex if G is the e-radius neighborhood graph used in the manifold learning literature [I22. 11, 53), The cubical k-complex K3) is complex widely used with image data. The difference between this complex and the SC₃ is that a CB₃ is a collection of sets of E-cubes, for < k. Note that we write Eo Kn V the vertex set and Σ, K1 E the edge set. Σg T and K2 R are the triangle and rectangle set, respectively. Additionally, we define ny = [Ex| (or = |Kg) ) to be the cardinality of the ?-dimensional cells and let no for simplicity. For more information about building various complexes on different datasets please refer to Otter et al. 43
CB₃ (Ko,
k-cochain. By choosing orientation for every k-simplex oki E Σg (or Kg), one can define finiteddimensional vector space Cs (k-cochain space An element Wi L: (on,,)) E Ca is called a k-cochain; one can further express W/ as = (w.,1," Wk,my, E IR by identifying each Th with the standard basis vector e, E ER",, Functions on nodes and edge flows, for example, elements of Co and C1. respectively.
Boundary matrix. The k-th boundary matrix B₁ [3S]] maps a k-cochain of k-cells (sim- plices/cubes) d to the (k - 1--cchhiin of its faces, i.e., B C. + Ca-1- B₁ E {0, [ xnx is a sparse binary matrix, with the sign of the non-zero entries 0k-1, og given by the orientation of og w.r.t. its face a Hence, different SC or CB will induce different B,. For k = 1 on either the SC or CB, the boundary map is the graph incidence matrix, i.e., (B1) = 1, (B1) = -1, and zero otherwise; for k = 2, each column of B2 contains the orientation of a triangle/rectangle w.r.t. its edges. Specifically, for an SC, (B2) [e.ll..... = (B2) v.e.la..e
1, (B2) = -1, and 0 otherwise; for a CB, (B2) [.y.s..) = (B2) (.el, =
= 1, 11, and 0 otherwise. Simplex Tk+1 is a coface of or iff o is face of 0 let coface(ak) be the set of all cofaces of ag. The (k- - 1)-th coboundary matrix BJ (adjoint of B&) maps -- as (k- -occhain, to the k-cochain of coface(ox-1).
(B2) [x..,,.,
k-Hodge Laplacian. Let We be a diagonal non-negative weight matrix of dimension ny, with [We]o,o representing the weight of the Ł-simplex/cube and w. + (iag. The weighted k-Hodge Laplacian [26] is defined as
Cs = A A, + A 1+1: where A W W. W. for 8 k
(1)
The weights capture combinatorial or geometric information and must satisfy the consistency rela- tion we(as) = = ( (e+1() (in matrix form: w, = | We+1) for f. k, h:
Hence A& can be seen as normalized boundary matrix. To determine the weight for the (A + 1)- simplices, one can selected Wk+1 be constant [[]] or based on (a product of) pairwise distance kernel (for k = 0, 1) so that the large sample limit exists [12), DE]] The first and second terms of ( are called respectively the down (C = A A&) and up (C = A A k+1) Laplacians. For 0, the down component disappears and the resulting C, is the symmetric normalized graph Laplacian used in spectral clustering [555] and Laplacian Eigenmap [S]]
I We use chain and cochain interchangeably, see Lim [G5] for the distinction hetween them.
In this paper. these matrices also called the k- k-Laplacian for simplicity.

---

k-th homology vector space and embedding. The homology vector space Hr is subspace of Cs (loop space) such that every k-cycle (expressed as a k-cochain) in Hr is not the boundary of any (A: + -coochain. In mathematical terms, Hr == ker(An ( //m (A++1). The rank of the subspace is called the k-th Betti number 3x dim (Hz), which counts the number of "loops" (homology classes) in the SC. H2 is equivalent to the null space of C3 [355 B8]: therefore, a basis of HHg can be obtained by the cigenvectors Y = [y,.... ya. E I X of Cx with eigenvalue O. The homology embedding maps k-simplex o to Yo..: oz = [y (o)), Yo, (o*)] < R Note that the basis Y is only identifiable up a unitary transformation; hence, individual homology embedding coordinates might change with a different basis Y.
Continuous operators on manifolds. The k-cochains are the discrete analogues of k-forms [59] For k 1, the following path integral [5인]] (along the geodesic 7(1) connecting x and y) relates a 1-cochain w to a I I-form v (vector field): w([x; vl) = f v((((())) (t)di. To estimate a vector field from w, one can solve least-squares problem [122], which is the inverse operation of the path integral (e.g., the vector fields in Figure are estimated from Y). Similarly, one can define the differential and codifferential ó operators which are analog to B and B₁, respectively. The (continuous) k-Hodge Laplacian operators, which act on k-forms, can be defined for manifolds too, i.e. by 4 dR-1ôş + 6 The homology group (the continuous version of H&) defined as the null of AІ. Its elements are harmonic k-forms Sk. computed by solving A&Ca O with proper boundary conditions; they represent the continuous version of the discrete homology basis Y.
Connected sum and manifold (prime) decomposition. The connected sum [G:]]] of two d di- mensional manifolds M = .i MM, iuM2
is built from removing two d dimensional "disks" from each
manifold MM. M2 and gluing together two manifolds at the boundaries (technical details in [35).. The analog of the connected sum for the abstract complexes will be defined in Section The connected sum is a core operation in topology and is related to the concept of manifold (prime) decomposition. Informally speaking, the prime decomposition aims to factorize a manifold M into smaller building blocks (M- = connected sum of other manifolds. The well-known classification theorem of surfaces [Gi states that any oriented and compact surface is the finite connected sum of manifolds homeomorphic to either a circle S' a sphere S?, or a torus T Classification theorems for d > 2 are currently unknown; for- tunately, the uniqueness of the prime decomposition for d = 3 (up to homeomorphism) was shown (Kneser-Milnor theorem ( Recently, Bokor et al. [*] (Corollary 2.5) showed the existence of factorizations of manifolds with d 2 5, even though they might not be unique.
so that each M, cannot be further expressed as
In this paper, we are interested in the following: given finite samples from M, which is k-fold connected sum of M, can this decomposition be recovered from the discrete homology embedding Y of M? Namely, we would like to understand how Y relates to the homology embedding of each prime manifold M;.
3 Definitions, theoretical/agooithmii aims, and prior works
Definitions. We assume that the data X is sampled from a d-dimensional oriented manifold M that can be decomposed into x prime manifolds (M- = M1 ..ft.... ..M.). Let I, be an index set of the data points in X sampled from Mi, for i I,... k. Denote by SCk, Cv. (M(M), and 3g the simplicial complex, the k-Laplacian, the k-homology space, and the k-th Betti number of X
sampled from M. Furthermore, let SC (E())
(10) 2x Ha,,),,, (aM;)) be the same (18)
quantities for manifold M, (supported on I, for S k). SC₁ and Ex (without superseript i) are the comparable notations for the disjoint manifolds M,'s, i.e. SC = SC" = (So. ... Ex) with En = 5( for f < k, and 2 is a block diagonal matrix with the i-th block being 2 (1)) Additionally, let Y and Y (both in R=*x0e) be the homology basis of Ca and Zx. respectively. Let S, be the index set of columns of Y corresponding to homology subspace HM,,M,). with S.ns, =
for i * j. S, = (M,). and S₁ UUS, = {1, [..). Since Y is the homology embedding of (ti)
block diagonal matrix Lx we choose it so that [Y]o,. cquals the homology embedding of 2, if
3

---

E 5.00 5 with column m E S and is zero otherwise. Namely, Y lies in the direct sum of subspaces (M) for i S k.
Theoretical aim. We are interested in the geometric properties of the null space eigenvectors Y. and specifically in recovering the homology basis Y of the prime manifolds. Hence, we aim to bound the distance between the spaces spanned by Y and Y. Under a small perturbation, one can provide analogous argument to the orthogonal cone structure [ : in spectral clustering (the zeroth homology embedding). The main technical challenge is that the connected sum of manifolds is highly localized perturbation; namely, most cells not affected all, while those involved in the gluing process gain or lose (1) (co)faces. Without properly designing C and Cxs one might get a trivial bound.
1st coonlintte
2nd coandinate
3rd
4th
conrdinate
Algorithmic aim. We exemplify the algo- rithmic aim using k 1, d 2, and x 2, particularly the genus-2 surface shown in Fig- M. The null space basis Y of Cs is only identifiable up to unitary matrix due to the multiplicity of the zero eigenvalues. For in- stance. the top and bottom rows of Figure II are both valid bases for the harmonic edge flows in Hi. However, the basis vector fields in the second row of Figure II more inter- pretable than those in the top row because Y (the first row) is linear combination of Z (the second row), with each basis (column in the figure) corresponding to a single homology class (loop). There- fore, here we propose data-driven approach to obtain the optimal basis Z such that the coupling from other manifolds/subspaee can support numerous applications (more in Section 5); however, it is difficult to design criterion for finding the optimal without knowing the geometric structure of the embedding of H4-
Figure 1: Harmonic vector fields obtained by solv- ing a squares [122] with Y (top) and (bottom).
as weak as possible, Being able to obtain Z from an arbitrary Y
Prior work. The shape of the embedding by the principal eigenvectors of the graph Laplacian Co is pivotal for showing the guarantees of spectral clustering algorithms for point cloud data or the inference algorithms for the stochastic block model. The analyses used either the matrix perturbation theory [HO, 555, 56] or assume a mixture model [[9]. For the higher-order k- k-Laplacian, it is reported empirically that the homology embedding is approximately distributed on the union (directed sum) of subspaces [2T]]; subspace clustering algorithms [0 were applied to partition edges/triangles under their framework.
On the application side, the eigen-embeddingg of C. is used implicitly or explicitly in graph signal processing [27, 94, g5] and in learning algorithms utilizing Hodge decomposition [12), 28, 62). They use the gradient/eurl cochains (which correspond to the images of cdown and C respectively) in addition to the homology embedding (ker( (C))); hence, our framework is intrinsically different from these works.
4 Main result: connected sum as a matrix perturbation
In this section, we analyze the geometric structure of Y by viewing the operation of connected sum through the lens of matrix perturbation theory [D]]]. We show that, under certain conditions, the homology embedding Y of the joint Laplacian L. is approximated by Y for the simplices in Σg n Σx. In matrix terms, we show that Y YO (Theorem M1 with O a unitary transformation.
We first prepare our assumptions suited for SC built from point clouds. Most of the assumptions (except Assumption II for which the connected sum might not be defined) can be extended to the clique complex (for networks) or cubical complex (for images) without too many modifications.
Assumption 1. The point cloud X E RaxD is sampled from a d-dimensional oriented and com- pact manifold M C RR,, the homology vector spaces Ha formed by the simplicial complex constructed from X are isomorphic to the homology group H4 (M) of M, i.e Hx(SC) ~ Hy(M).
Furthermore, assume that M -M1.... .. MMM and that Hd HSC Hy (M..)) 1, .....,

---

This assumption is the minimal assumption needed for the analysis of the embedding of the Ca; it states that any procedure to construct the simplicial complex or weight function for C is accepted as long as the isomorphic condition holds. The construction of the SC from the point cloud is out of the scope of this manuseript (see, e-g.. Chen et al. [[22] for building C1 from X with an analyzable limit and Latschev's 's theorem [+]]] on VR complexes). The last condition requires that the manifold M can be decomposed: this is most likely true, except for the known hard case of M with = discussed in Section E Note that Assumption M is similar to those used in the multi-manifold clustering [[-l], where they required the manifold to be constructed by a k-fold union M = M U.... .... U UM. The goal of our framework is to analyze the homology embedding of k-Laplacian. By contrast, Trillos et al. [544] are interested in identifying each manifold with the notion of clustering (Ho).
Assumption I1 is for points sampled from manifold M only. To make this assumption hold for networks or images, one can require that the Cs constructed from these two datasets can be roughly factorized into block-diagonal entries. Below we provide two other assumptions that are valid for both SC and CB (with some modifications): the first one controls the eigengap and the second one ensures a small perturbation in the spectral norm of Ls 2, By construction, C is positive semi- definite; since are interested in the stability of its null space, we define, for any matrix L 7 0, the eigengap as the smallest non-zero eigenvalue of L and denote it Amin (L).
We denote the set of con-intersecting simplices be My == = n Ex. Let the set of destroyed and created k-simplices during connected sum by Dj and Es, respectively; they are defined by Ex= == Ex>90, (2 and D) = Ex) ggg. We have: (1) no k-homology class is created
Assumption 2.
during the connected sum process, i.e., BsCS Ei=1 Bx(C") ( (2) The eigengaps of c D.0 and C D.D are bounded away from the eigengaps of (((f), i.e. min (Amin (C Amnin (2x }} > min(f),..... ,5x}. where 8, is the eigengap of (.
The first condition requires that the intersecting simplices D₁ U Cg do not create or destroy any k-th homology class; this holds, for instance, when the manifold . has dimension d > k. Under this condition, we have MM) = He()) @ (22 [33]. A counterexample for this condition is, e.g., inspecting the cavity space (k- = 2) of a genus-2 surface built from gluing two tori together. That is. 32 of a genus-2 surface is 1, while the sum of 32 of two tori is 2. The second condition requires that the principal submatrix of La described by the block of C. U Dr has large eigengap. This happens, e.g., when C₁ and Da. are cliques and are contained in small balls.
Assumption 3 (Informal). Let W. = B [9,, (R2+1]/Wae or k 1, we have max (wr(a)) //p((()) 1} S eg, maxagm, (ūr(a)/ - 1] es, and max / (=( - 1 S cg- Assumption ISD is the formal version of this assumption.
WR-1 = BB R F k
For A = 1, it states that not too many triangles are being created or destroyed during connected sum. For this assumption hold, the sampling density in the connected sum region should be smaller than in other regions, i.e., the manifold . should be sparsely connected (e.g.. Figure Za). Empirically, we observed that the perturbation small even when M is not sparsely connected (more discussions in Section B). Note also that é < eg. for e/ represents the net change in the degree after connected sum. It might be possible to obtain tighter bound fully by é/'s, which do not depend on the relative density between the connected sum region and the remaining manifolds; we leave it as future work.
Theorem 1. Lei DiffL diffLdown
down (DiffL UP) be the modified difference (defined in Supplement Ell of L Cdown and Cx (respectively C and 2 Under Assumptions 7-B with notations defined as before
down
and d 1 + 2, if DiffLdown || s (2V
down
2 V +4 X and (I+ (1+
|DiifL 12 < [2 ck + 2es + Avex] X2z then there exists a unitary matrix O R x9x such that
8,3g ||Dim down| ||
|
2
ou: - Y me.
min min(. (ō1," .5,)
The proof (in Supplement Al is based on bounding the error between Ls and 2. with Es (the Laplacian after removal of k-simplices during connected sum), the use of a variant of the Davis-
5

---

Kahan theorem [6]]] and the bound of the spectral norm of C3 for simplicial complex, i.c., || S A k [26]]
The LHS of (2)) contains only the simplices in N. because Y is not defined on Dx (similar for Y and Ex). Nonetheless, (2) makes sure that the (unbounded) perturbations in the embedding of Cx U DR do not propagate the rest of the simplices. The bound in (2) can be extended to CB (Corollary 2 by changing the d value from 2k+ to 2. The 2k 2 term here is the maxi- mum eigenvalue of the C3 built from any cubical complex (Proposition (3).
Algorithm 1: Subspace identification
Input :SC, k, weights WK+1
1 BR, Bx+1 BOUNDARYMAPS(SC,.R
> Algorithm
2 for l k. k do
3
We f- [ W min
A4+1 t W." 1/2 1/2 BB+1
B
W// 1/2
4
4+1
5 Ls A + A A R+1
Corollary 2 (For Ls built from a CB). Under As-
6 Y E RT + NULLSPACE( (+))
sumptions D-G with DiffLy up as well as DiffL DiffLdown down k
7 Z + ICANOPREWHITE(Y)
defined in Theorem 0 and X 2k + 2, there exists a unitary matrix O such that (2) holds.
Return Independent basis Z
Subspace (M, identification. We propose to approximately recover Ý from the columns of the coupled basis Y by blind source separation, as described by Algorithm D. Specifically, the independent basis Z is obtained by Infomax ICA [X] on Y of Cx, with modification (Line W that preserves the necessary properties of harmonic cochains (i.e., they are divergence-fre and curl-free, see also Proposition B). Algorithm II works for CB as well by using the appropriate B;, B construction method (Line M.. Each column of the obtained Z is now approximately supported on a single prime manifold MM;
5 Applications: homologous loops detection, clustering, and visualization
Homologous loop detection. In ad- dition to the rank information, one might find it beneficial to extract the
Algorithm 2: Spectral homologous loop detection
Input :Z = =[z1,- ..,,... zz,.).
V. E, edge distance
shortest cycle of the corresponding Hy generator. This application is found useful in domains including finding minimum energy trajectories in molecular dynamics datasets, tra- jectory inference in RNA single-cell
for i 1,..... do
E ((s,tt) (s,t) e E and
[z, (s,t) > 0} (s.1)) < 0}
E, < ((tts): (s, E E and
T x PERCENTILE( ([2)), 1 1/31)
5
E feE U. : l|z.lel <T}
sequencing [B6], and segmenting cir- cular structures in medical images [S0]] We propose spectral short- est homologous loop detection algo- rithm (Algorithm 2 based on the shortest path algorithm (Dijkstra) as follows: for each dimension 1....,8, the algorithm reverses ev- ery edge e having negative (z,]e to generate weighted digraph G; = (V, E,) (Lines D-D, with the weight of edge = (i.j') E E; equal to the Euclidean distance [d](.5) = |x, - 122 The algorithm finds a shortest (in terms of d) loop on this weighted digraph for each i and outputs it the homologous loop representing the i-th class. We present the following proposition (with the proof in Supplement B) to support Algorithm P: implies that if each coordinate of Z extracted from Algorithm II corresponds to a homology class, then the detected homologous loop for each homology class is the shortest.
E E.tE,t SJU,,VE,
G + -V, E,), with weight of e E Eg being [d].
dmin = inf
for e = (1, s0) E F& do
10
p=.d" + -UUKSTRA(G, from=so to=t)
> Note that P = [so, $1, ...
11
if dd < dunn then
L C; + 11, 80, 81,
12
Return: C1.-.. Co..
B1 be the i-th homology basis that corresponds to the i-th homology class. For every i = 1.... Br, (1) there exist at least one cycle in the digraph G, such that every vertex u E can traverse back to itself (reachable); (2) the corresponding cycle will enclose at least one homology class (no chort-cireuiting).
Proposition Lei zı for i 1,.

---

Since every vertex is reachable from itself, we are guaranteed to find a loop for any starting/ending pair (Lines B-T2). Additionally, there will be no abort-circuiting for any loop; each loop we found from Dijkstra is guaranteed to be non-trivial. However, there is one caveat from the second property: even though the i-th loop is non-trivial, might not always be corresponding to the i-th homology class due to the noise in small [z.]e- Namely, loops that do not represent i-th homology class can be formed with edges e having small [zi]e. resulting in the instability and the (possible) duplication of the identified loops. To address the issue, we propose a heuristic thresholding. by which we keep the /1/3, edges with the largest absolute value in [zilel (Lines BH-5). We chose to keep ni 0 by treating each homology class equally, i.., each class has roughly n1/31 edges. Unlike Theorem M or Algorithm II Algorithm / cannot be extended to the case when k 2 2 because the Dijkstra algorithm is employed. We leave its generalization to extract higher- cavities as future work.
Compared with the previous approach that finds the shortest loops [TG]] combinatorially, our ap- proach has better time complexity; specifically, the algorithm by Dey et al. [166] has time complexity Onn) + n2f whereas Algorithm @ runs in time On1 + f6m; + Binjn log n)) The first, second, and third terms correspond to the time complexity of eigendecomposition of C1. the Info- max ICA, and the Dijkstra algorithm on every digraph G, respectively. Note that if the simplicial complex is built from point clouds, the number of triangles 12 may be large; this dependency on n2 makes the algorithm [[66] hard to scale. On the other hand, our framework requires that z; are each supported
homology class; therefore, loops only be correctly identified using Algorithm 2 if the manifold is sparsely connected (Assumptions M B). Additional comparisons between our algorithm and other methods that pose special requirements the analyzed data can be found in Supplement D422
Classifying any 2-dimensional manifold. The Betti number 81 of a torus is 2, which is equal to that of two disjoint circles; hence one cannot distinguish these two manifolds only by rank informa- tion. Fortunately, they can be categorized using the homology embedding Z. By the classification theorem [E]], any 2D surface is the connected sum of circles S and tori Th: therefore, Theorem II indicates that embedding lies approximately in the directed sum of homology subspace of S and/or T2. The homology embedding of s' is line since it is in I On the other hand, any loop in torus can be a convex combination of the two homology classes, implying that the intrinsic dimension of the homology embedding is 2. It is hard to obtain Z of any arbitrary torus; we present the homology embedding of the flat m-torus below by expressing the null space basis (1-cochains) as the path integrals of the corresponding harmonic 1-forms [T22 [59]
Proposition 4. The envelope of the first homology embedding (I-cochain) induced by the harmonic 1-form on the flat m-torus T is an m-dimensional ellipsoid.
The proof (in Supplement BD) is straightforward thus is omitted here. Proposition E and the classifi- cation theorem suggest that the first homology embedding is either a line, a disk, or a combination of the two (with replacement). See example for the genus-2 surface in Figures Dij and STI
Note that is possible to classify any 2- 2-manifold with higher- digee--dimensional homology groups; for instance, one can distinguish I from S pSa by the second homology group. However, our approach scales better in computation or memory usage since inspecting Hl needs at least the calculation and storage of tetrahedrons from the neighborhood graph.
Other applications. As pointed out earlier, one can visualize the basis of the harmonic vector fields (of Ha) by overlaying the columns of Y onto the original dataset (Figure W. Being able to successfully extract decoupled basis Z increases the interpretability of Hg, as shown in the second row of Figure Theorem II also supports the use of subspace clustering algorithm in the higher-order simplex clustering framework [[1].
6 Experiments
We demonstrate our approach by computing Y, Z and the shortest loops for five synthetic mani- folds: two of them are prime manifolds (TORUS torus, 3-TORUS three-torus) and three (PUNCTPLANE punciured plane with two holes, GENUS-2 genus-2, and TORI-CONCAT concatenation of 4 tori) are factorizable manifolds. Furthermore, five additional real point clouds (ETH and MDA from chemistry, PANCREAS from biology, 3D-GRAPH from 3D modeling, and ISLAND from oceanography) are ana-
7

---

(a)
(b) (c)
o5
(e)
(4)
Figure 2: (a) The first homology embedding of PUNCTPLANE. The harmonic vector fields overlaid on the data in the inset plots: green, blue, red, and yellow arrows correspond to Y1. V2. Z1. and z2, respectively. (b). (c), (c), (i), and (1) are the detected loops using Dijkstra Z for PUNCTPLANE (colors are in (a)), TORUS, 3-TOUS, GENUS-2, and TORI -COCAT, respectively. (g) and (k) represent the identified loops the coupled embedding Y for GENUS-2 and TORI-CONCAL respectively. (d), (f), (h), and (j) present the embeddings used to detect loops in (c), (e), (g), and (i), respectively.
lyzed under this framework. For all the point clouds, we build the VR complex SC from the CKNN kernel [X] so that the resulting L1 is sparse and the topological information is preserved. Note that other methods for building an SC from X can also be used as long as Hy is successfully identified non-nos non-manifold data: RETINA
(Assumption M). Lastly, we illustrate the efficacy of our framework from medical imaging. Please refer to Supplement D for detailed discussions on procedures to gen- erate, preprocess, and download these datasets. All experiments are replicated more than five times with similar results. We perform our analysis on desktop running Linux with 32GB RAM and an 8-Core 4. 4.20GHz Intel@ Core 17-7700K CPU; every experiment completes within minutes (1-2 minutes on eigendecomposition of L,, and around 30 seconds on both ICA and Algorithm D).
Synthetic manifolds. The results for the synthetic manifolds are in Figure 21 Figure Za (the har- monic embedding of PUNCTPLANE) confirms Theorem @I that is approximately distributed on two subspaces (yellow and red), with each loop parametrizing single hole (inset of Figure Ea). As discussed previously in Figure the harmonic vector bases (green and blue) are mixtures of the separate subspaces; therefore, these bases have poor interpretability compared with the independent subspace Z identified by Algorithm MI The shortest loops (Figure (b) corresponding to z (yellow), Z2 (red) are obtained by running Dijkstra on the digraphs induced by Z₁ and Z2 separately (Algo- rithm D) Figures 2 Df show the results the two simple prime manifolds: TORUS and 3 3-TORUS. The harmonic embeddings of TORUS (Figure Zkd and 3-TORUS (Figure Dl a two-dimensional disk and a finee-dimensional ellipsoid, respectively; this confirms the conclusion from Proposition A The shortest loops obtained from Algorithm 2 for these two datasets in Figures De and Die, showing that these loops travel around the holes in TORUS (or 3-TORUS). Note that we plot 3-TORUS in the intrinsic coordinate because a three torus can not be embedded in 3D without breaking neigh- borhood relationships. Three lines in Ze are indeed loops due to the periodic boundary condition, i... 2x, the intrinsic coordinate. Figures Zh and Zj show the embedding of the coupled harmonic basis (Y) and that corresponding to the independent subspace (Z) obtained by Algorithm Compared with Y, each coordinate of corresponds GENUS-2, 2, and does not couple with other homology generators. Z is thus union of two 2D disks, with each disk approximating the harmonic embedding of a torus (see Figure ST for more detail). Compared with the loops obtained by running Algorithm D on Y (Figure Dlg), each loop in Figure D identified from Z parameterizes the corresponding homology generator without being homologous to other loops. Similar results on TORI-CONCAT are in Figures Ek and 21, which correspond to the
subspace, i.e., the left right handle of

---

THOOH (blue)
Tccco (blue)
TOCCH (green) (a)
Tocoe (green)
(b)
(c)
(d)
(e)
(9)
(h)
Figure 3: (a) and (b) are the detected loops of ETH using Dijkstra Z (in (c)) in the torsion space (inset of (a)) and in the PCA space, respectively. (f)-(f) are the results for MDA that are similar to those for ETH in (a)-(c). (g)-() show the identified loops using Z for PANCREAS, 3D-GRAPH, ISLAND, and RETINA, respectively.
loops obtained from Y and Z, respectively. The pairwise scatter plots of the eight-dimensional Z (or Y) are in Figure S of Supplement [I Note that PUNCTPLANE is example of sparsely connected manifold (see the low-density area the middle), with 6 = 0.035 and co ze 0.038. Manifolds of other synthetic/real datasets might not be sparsely connected due the (approximately) constant sampling densities; nevertheless, the perturbations to the subspaces remain small for these datasets.
Small molecule data [13]] Figures BacBkc and Rd- show our analysis on ETH and MDA, respec- tively. These two small molecule datasets, whose ambient dimensions are D 102 and D 98, are suggested to be noisy non-uniformly sampled tori [52]]; the harmonic embeddings of these two datasets (Figures Ge and Br confirm this idea. Finding the minimum trajectories corresponding to a specific bond torsion is of interest in chemistry; in these two molecular dynamics systems, this problem be translated into finding the homologous loops in the point cloud. The homologous loops found by Algorithm D overlaid on the first three principal components (PCs) for these two datasets can be found in Figures Ab (for ETH) and Be (for MDA). The same homologous loops plotted in the bond torsion space (with definition in the insets) based on our prior knowledge are in Figures E and Bd. Similar the discussion for 3-TORUS (Figure Dke,, the yellow/red trajectories form loops due to the periodic boundary condition of the bond torsions.
RNA single-cell sequencing data [Z]. The trajectory inference methods [46] for analyzing the RNA single-cell sequencing datasets aim to order the cells (points in digh-diimesional expression space) along developmental trajectories, which are inferred from the structure of the point clouds. Identifying loops in the dataset can serve a building block for delineating a correct trajectory, especially for determining cell cycle and cell differentiation. To illustrate the idea, we compute the I-Laplacian on the CkNN kernel [8] constructed on the UMAP [[66 embedding (Algorithm MI.. Figure Big shows the identified loops from Algorithm A with the green loop being the cycle of ductal cells and yellow/red loops representing trifurcation (endocrine cell differentiation).
Additional point cloud datasets. 3D-GRAPH [ISS] is a 3D model of a Buddha statue with a pre- computed triangulation. We treat the 3D model as point cloud and subsample 3000 farthest points from the original dataset; C, obtained from the VR complex of the CkNN kernel. Note that with this small sample size, two smaller loops near the waist of the statue are not detectable. Hence, the number of zero eigenvalues of C, 3, with the corresponding homology generators shown Fig- ure Kh. ISLAND [ which contains ocean buoys around the Tasman is the other point cloud in

---

our analysis. The estimated 31 is 3, with the detected loops being the North Island of New Zealand, the South Island of New Zealand, and the main island of Tasmania (Figure Gi).
Non-manifold dataset. Our framework for identifying subspaces is still valid for cubical com- plexes built from images (by Corollary D). We demonstrate the idea on RETINA, medical retinal image [25]. The cubical complex is constructed by intensity thresholding (also called the sub-level set method in TDA [БX]] and then applying morphological closing on the binary image remove small cavities. The weight for every rectangle w2(a) is set to I; the estimated null space dimension of the L1 built from CB is $1 12, with the identified homologous loops in Figure Eij. The result
shows the robustness of the proposed framework even for large $1.
7 Conclusion and broader impact
Our contributions in the emerging field of spectral algorithms for k-Laplacians Cx [122 211, 65), Bsl
are summarized as follows. (i) We extend the study of the homology embedding of vertices by the graph Laplacian Lo (spectral clustering) to those of higher-order simplices by Lx. Specifically, the k-th homology embedding can be approximately factorized into parts, with each corresponding to a prime manifold given small perturbation (small 6 and c for l = k. k- 1). (ii) The analysis is made possible by expressing the x-fold connected sum as a matrix perturbation. This convenient property of the homology embedding supports (iii) the use of ICA to identify each decoupled subspace and motivates (iv) the application to the shortest homologous loop detection problem. The proposed explore. For instance, one can extend
framework opens up numerous future directions for our framework to investigate the generalization of the loosely connected clusters, i.e., when the null space H₂ eigenvalues are not strictly zero; it applies to the case when analyzing the noisy topological structures in the data manifold. Moreover, the connections of our framework to the recent advances in spectral TDA and representation learning can be further explored; they include the persistent spectral method [38, 57] and the disentanglement of representation [6:3] in generative modeling.
Broader impact. Our analysis provides insight into the structure of the k-th harmonic embedding. This framework can inspire researchers in developing spectral topological data analysis algorithms (e.g.. visualization, clustering, tightest higher-order cycles for k 2 [20, B2)) similar to those that were inaugurated by spectral clustering two decades ago. These applications are especially beneficial to scientists (chemists, biologists, oceanographers, etc.) who use high-dimensional data analysis techniques for studying complex systems. Similar to the limitation of other unsupervised learning algorithms. practitioners without solid understandings of both the analyzed datasets and the used algorithm might draw controversial conclusions (see, e.g., discussions in [2, []].. Possible ap- proaches to mitigate the negative consequences are to design proper validation and causal inference algorithms for this framework; we leave them as potential directions we will explore.
Acknowledgements
The authors acknowledge partial support from the U.S. Department of Energy's 's Office of Energy Efficiency and Renewable Energy (EERE) under the Solar Energy Technologies Office Award Num- ber DE-EE0008563 and from the National Science Foundation award DMS 2015272. They thank Alexandre Tkatchenko, Jim Pfaendtner, Stefan Chmiela, and Chris Fu for providing the molecular dynamics data as well as for many hours of brainstorming and advice.
Disclaimer
The views expressed herein do not necessarily represent the views of the U.S. Department of Energy or the United States Government.
References
[1] Saad Ali, Arslan Basharat, and Mubarak Shah. Chaotic Invariants for Human Action Recog- nition. 2007 IEEE I 11th International Conference on Computer Vision, pages 1-8, October 2007. doi: 10. ww..109//CCV.2007.440000000 4409046.
10

---

[2] Jose Alquicira-Hemaande,, Joseph Powell, and Tri Giang Phan. No evidence that plasmablasts transdiffereeniate into developing neutrophils in severe COVID-19 disease. bioRxiv, 2020.
[3] Mark Anthony Armstrong. Basic Topology. Springer Science & Business Media, 2013.
[4] Sergio Barbarossa and Stefania Sardellitti. Topological signal processing over simplicial com- plexes. IEEE Transactions on Signal Processing, 68:2992-3007, 2020.
[5] Mikhail Belkin and Partha Niyogi. Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, 15(6):1333-1396 June 2003. ISSN 0899-7667. doi: 10.1 10.116/08997660322779933
[6] Anthony Bell and Terrence Sejnowski. An informattoon-maxiiizziooo approach blind separation and blind deconvolution. Neural computation, ((9):112--119, 1995.
[7] Volker Bergen, Marius Lange, Stefan Peidli, F. Alexander Wolf, and Fabian J. Theis. General- izing RNA velocity to transient cell states through dynamical modeling. Nature biotechnology. 38(12): 1408 1414, 2020.
[8] Tyrus Berry and Timothy Sauer. Consistent manifold representation for topological data anal- ysis. Foundations of Data Science, 1(1):1, 2019. doi: 10.1994//tdds2219000..
[9] Imre Bokor, Diarmuid Crowley, Stefan Friedl, Fabian Hebestreit, Daniel Kasprowski, Markus Land, and Johnny Nicholson. Connected sum decompositions of high-dimensional manifolds. 1909 02668 [math], September 2020.
[10] Oleksiy Busaryev, Sergio Cabello, Chao Chen, Tamal K. Dey, and Yusu Wang. Annotating simplices with homology basis and its applications. In Scandinavian Workshop on Algorithm Theory, pages 189-200. Springer, 2012.
[11] Erin W. Chambers, Jeff Erickson, and Amir Nayyeri. Minimum cuts and shortest homologous cycles. In Proceedings of the Twenty- Eienty-Fiftth Annual Symposium on Computational Geometry, pages 377-385, 2009.
[12] Yu-Chia Chen, Marina Meilä, and loannis G. Kevrekidis. Helmholtzian Eigenmap: Topologi- cal feature discovery & edge flow learning from point cloud data. arXiv:2103.00662) [stat.ML.]. March 2021.
[13] Stefan Chmiela, Alexandre Tkatchenko, Huziel E Sauceda, Igor Poltavsky, Kristof T Schütt, and Klaus-Robert Müller. Machine learning of accurate energy-conserving molecular force fields. Science advances, 36))e1603015, 2017.
[14] Ronald R. Coifman and Stéphane Lafon. Diffusion maps. Applied and Computational Har- monic Analysis, 21(1):5-30, July 2006. ISSN 1063-5203. doi: 10. wtofjjaaca..006044...000
(15) Brian Curless and Mare Levoy. A volumetric method for building complex models from range images. In Proceedings of the 23rd Anmual Conference on Computer Graphics and Interactive Techniques, pages 303-312, 1996.
[16] Tamal K. Dey, Jian Sun, and Yusu Wang. Approximating loops shortest homology basis from point data. In Proceedings of the Twenty-Sixth Annual Symposium on Computational Geometry, pages 166-175, 2010.
[17] Tamal K. Dey, Anil N. Hirani, and Bala Krishnamoorthy. Optimal Homologous Cycles, Total Unimodularity, and Linear Programming. SIAM Journal on Computing. 10(4):0026-1044 January 2011 ISSN 0097-5397. doi: 10. 10/11137108800245.
[18] Tamal K. Dey, Fengtao Fan, and Yusu Wang. An efficient computation of handle and tunnel loops via Reeb graphs. ACM Transactions on Graphics (TOG), 320 2013.
[19] Tamal K. Dey, Tao Hou, and Sayan Mandal. Persistent l-cycles: Definition, computation, and its application. International Workshop on Computational Topology in Image Context, pages 123-136 Springer, 2019.

---

[20] Tamal K. Dey, Tao Hou, and Sayan Mandal. Computing minimal persistent cycles: Polynomial and hard cases. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2587-2606. SIAM, 2020.
[21] Stefania Ebli and Gard Spreemann. A Notion of Harmonic Clustering in Simplicial Complexes. 2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA), pages
December 2019. doi: 10. 1 119////MM...00..000011.
[22] Xin Feng and Yiying Tong. Choking loops on surfaces. IEEE transactions on visualization and computer graphics, 19(8):1288-1366, 2013.
[23] Gary Froyland and Kathrin Padberg-Gehle. rough-and-ready cluster-based approach for extracting finite-time coherent sets from sparse and incomplete trajectory data. Chaos: An Interdisciplinary Journal of Nonlinear Science, 25(8):087406, July 2015. ISSN 1054-1500.
doi: 10. 4926377..
[24] Felix Hensel, Michael Moor, and Bastian Rieck. A Survey of Topological Machine Learning Methods, Frontiers in Artificial Intelligence, 4:52, 2021.
[25] Adam Hoover and Michael Goldbaum. Locating the optic nerve in retinal image using the fuzzy convergence of the blood vessels. IEEE transactions on medical imaging, 22(8):951- 958, 2003.
[26] Danijela Horak and Jürgen Jost. Spectra of combinatorial Laplace operators simplicial complexes, Advances in Mathematics, 244:303-336, September 2013. ISSN 0001-8708. doi: 1.1016/..im.2013.05.00
[27] Junteng Jia, Michael T. Schaub, Santiago Segarra, and Austin R. Benson. Graph-based Semi- Supervised & Active Learning for Edge Flows. In KDD, 2019. doi: 10.1145/3292500. 3330872.
[28] Xiaoye Jiang. Lek-Heng Lim, Yuan Yao, and Yinyu Ye. Statistical ranking and combinatorial Hodge theory. Mathematical Progrumming, 127(1):203-244, March 2011. ISSN 1436-4646. doi: 10.1007//10107-000004411
[29] Dominique Joncas, Marina Meila, and James McQueen. Improved Graph Laplacian via Ge- ometric Self-Consistency. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems Curran Associates, Inc., 2017.
30, pages 4457-4466.
[30] Karin Kailing, Hans-Peter Kriegel, and Peer Kröger. Density- subspace clustering for high-dimensional data. In Proceedings of the 2004 SIAM International Conference on Data Mining, pages 246-256. SIAM, 2004.
[31] Violeta Kovacev-Nikolic, Peter Bubenik, Dragan Nikolić, and Giseon Heo. Using persistent homology and dynamical distances to analyze protein binding. Statistical applications in ge- netics and molecular biology, 15(1):19-38 2016.
[32] Janko Latschev. Petoris-Rips complexes of metric spaces near a closed Riemannian manifold. Archiv der Mathematik, 77(6):522-522 2001.
[33] John M. Lee. Introduction to Smooth Manifolds. In Introduction to Smooth Manifolds, pages 1-31. Springer, 2013.
[34] Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 424-433. IEEE, 2014.
[35] Lek-Heng Lim. Hodge laplacians graphs. Siam Review, 62(3):685-715, 2020.
[36] Leland McInnes, John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:1802.034222 2018.
[37] Marina Meilä and Jianbo Shi. random walks view of spectral segmentation. In International Workshop Artificial Intelligence and Statistics, pages 203-208, PMLR, 2001.
12

---

[38] Zhenyu Meng and Kelin Xia. Persistent spectral- based machine learning (PerSpect ML) for pootein-ligadd binding affinity prediction. Science Advances, 7(19)xebb:5329, 2021.
[39] John Milnor. unique decomposition theorem for 3-manifolds. American Journal of Mathe- matics, 84(1):1-7, 1962.
[40] Andrew Y. Ng. Michael I. Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 2:849-856, 2002.
[41] John Novembre and Matthew Stephens. Interpreting principal component analyses of spatial population genetic variation. Nature genetics, 40(5):644666) 64166669,, May 2008. ISSN 1061-4036.
doi: 10. 10.1038/ng.11
[42] Ippei Obayashi. Volume Optimal Cycle:
Tightest representative cycle of a generator on persis- tent homology. arXiv: 1712.05 [cs, math), December 2017.
[43] Nina Otter, Mason A. Porter, Ulrike Tillmann, Peter Grindrod, and Heather A. Harrington. A roadmap for the computation of persistent homology. EPJ Data Science, 6(1):17, December 2017. ISSN 2193-1127. doi: 10. 1
[44] T. Mitchell Roddenberry and Santiago Segarra. HodgeNet: Graph Neural Networks for Edge Data. In 2019 53rd Asilomar Conference on Signals. Systems, and Computers, pages 220-224.
IEEE, 2019.
[45] T. Mitchell Roddenberry, Nicholas Glaze, and Santiago Segarra. Principled simplicial neural networks for trajectory prediction. In International Conference on Machine Learning, pages 9020-9022 PMLR, 2021.
[46] Wouter Saelens, Robrecht Cannoodt, Helena Todorov, and Yvan Saeys, A comparison of single-cell trajectory inference methods. Nature biotechnology, 37(5):447-554, 2019.
[47] Manish Saggar, Olaf Sporns, Javier Gonzalez-Castille Peter A. Bandettini, Gunnar Carlsson, Gary Glover, and Allan L. Reiss. Towards a new approach to reveal dynamical organization of the brain using topological data analysis. Nature communications, 9(1):1-14 2018
[48] Michael T. Schaub, Austin R. Benson, Paul Horn, Gabor Lippner, and Ali Jadbabaie. Random walks on simplicial complexes and the normalized Hodge I-Laplacian. SIAM Review, 62(2): 353 391, 2020.
[49] Geoffrey Schicbinger, Martin J. Wainwright, and Bin Yu. The geometry of kernelized spectral clustering. Annals of Statistics, (13(()):199844))) April 2015. ISSN 0090-5364, 2168-8966. doi: 10.1214/14-A0S128.
[50] Nikhil Singh, Heather D. Couture, J. S. Marron, Charles Perou, and Marc Niethammer. Topo- logical descriptors of histology images. In International Workshop on Machine Learning in Medical Imaging, pages 231-239. Springer, 2014.
[51] G. W. Stewart, J. W. Stewart, and Ji-guang Sun. Matrix Perturbation Theory. Elsevier Science, July 1990. ISBN 978-0- 12-670230-9.
[52] Michael Tabor. Chaos and Integrability in Nonlinear Dynamics: An Introduction. Wiley, 1989.
[53] Daniel Ting, Ling Huang, and Michael Jordan. An Analysis of the Convergence of Graph Laplacians. In Proceedings of the 27th International Conference on Machine Learning (ICML), 2010.
[54] Nicolas Garcia Trillos, Pengfei He, and Chenghui Li. Large sample spectral analysis of graph- based munti-manifold clustering. arXiv preprint arXiv:2107.13610 2021.
[55] Ulrike von Luxburg. A Tutorial on Spectral Clustering. arXiv:0711.018) [cs], November 2007.
[56] Yali Wan and Marina Meila. class of network models recoverable by spectral clustering. In NIPS, pages 3285-3293, 2015.
13

---

[57] Rui Wang, Duc Duy Nguyen, and Guo-Wei Wei. Persistent spectral graph. International journal for numerical methods in biomedical engineering. 36(9):e3376, 2020.
[58] Larry Wasserman. Topological data analysis. Anmual Review of Statistics and Its Application, 5:501-533 2018.
[59] Hassler Whitney. Geometric Integration Theory. Dover Publications, Mineola, N.Y, December 2005. ISBN 978-0 0-486--44583-.
[60] Pengxiang Wu, Chao Chen, Yusu Wang. Shaoting Zhang, Changhe Yuan, Zhen Qian, Dimitris Metaxas, and Leon Axel. Optimal topological cycles and their application in cardiac trabeculae restoration. In International Conference on Information Processing in Medical Imaging, pages 80-92. Springer, 2017.
[61] Yi Yu, Tengyao Wang, and Richard J. Samworth. A useful variant of the Davis- theorem for statisticians. Biometrika, 102(2):315-3)) 1-115,--3,,32 2015.
[62] Rundong Zhao, Menglun Wang. Jiahui Chen, Yiying Tong, and Guo-Wei Wei. The de Rham-Hodge Analysis and Modeling of Biomolecules. Bulletin of mathematical biology, 82 (8):1-38, 2020.
[63] Sharon Zhou, Fric Zelikman, Fred Lu, Andrew Y. Ng, Gunnar Carlsson, and Stefano Ermon. Evaluating the disentanglement of deep generative models through manifold topology. arXiv preprint arXiv:2006. 200:2000003680, 2020.
[64] Xiaojin Zhu. Persistent Homology: An Introduction and New Text Representation for Natu- ral Language Processing. In Twwent-Third International Joint Conference on Artificial Intelli- gence, June 2013.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you deseribe the limitations of your work? [Yes] See Section !
(c) Did you discuss any potential negative societal impacts your work? [Yes] See
Section Ø
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] In Supplement
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] In Supplement
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] In Supplement D
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A] Do not have error bars to report; all experiments are ran least five times, and we observe similar results.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Section f
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] In Supplement D
(b) Did you mention the license of the assets? [Yes] In Supplement D
14

---

(c) Did you include any new assets either in the supplemental material or as URL? [Yes] New codes are attached the supplemental material codes. zip; they can also be found at datasets.
emb, We do not create new
(d) Did you discuss whether and how consent was obtained from people whose data you re using/curating? [Yes] In Supplement D
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A] Datasets do not contain personal identi- fiable information.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] No crowdsourcing data nor conducted research with human sub- jects
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A] No crowdsourcing data nor conducted research with human subjects
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A] No crowdsourcing data nor conducted re- search with human subjects
15


Reviews:
[{"review_id": "f2uj83qvgqS", "reviewer": "Reviewer_szyP", "summary": "This paper studies $k$-th homology vector spaces through the lens of $k$-Laplacian, a generalization of the usual graph Laplacian to higher order combinatorial structures. \nIt studies in particular the (fairly general) context of decomposable manifold as a sum of prime manifolds, showing (losely speaking) that under some assumptions (sparse connections), the homology space of a manifold can be obtained as the sum of the homology spaces of the corresponding prime manifolds. \nBuilding on Independent Component Analysis technique, it then provides a way to identify the subspaces of the homology basis computed on the whole manifold to recover the basis of the corresponding prime manifolds. \nThis has applications in particular in homologous loop detection (detecting the shortest generating element in H1), as showcased on both synthetic and real datasets.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nClarity:\nOverall, the paper is well written. It manages to remain concise while preserving mathematical rigor (required due to the theoretical content of the paper), and give enlightening interpretations through the paper. \n\nSignificance: \nThis paper addresses important questions (understanding/representation of higher-order homology vector spaces ; computation of homologous loops...). It provides mathematical analysis, practical algorithms and their implementation (*), and showcase the approach on different datasets in a fairly convincing way. \n\nQuestions:\n- The paper claims better algorithmic complexity (line 277) for shortest loop computation. Is it reflected in practical running time? I noticed that a running time of ~30sec is mentioned for Alg 2 (line 319), how does the approach developed in [15] performs there?\n\n\nMinor remarks and suggestions:\n- Perhaps including an illustration of the notions introduced in Section 2 (background) would be helpful, if there is enough room. \n- (line 64) (typo) I think it should be $B2_{[yz]}(x,y,z) = 1$ the second time. \n- (line 85) (typo) $[y_1, ..., y_{beta_1}]$ should be _beta_k. A similar typo occurs in other places. \n- (line 119) Talking about the k-Laplacian ``\"of M'' is somewhat confusing as those notions/notations are introduced for discrete objects.\n- (line 120) (suggestion) Perhaps using \\widehat would help readability. \n- (line 169) (typo) I think M should be in $\\mathbb{R}^D$ (not $\\mathbb{R}^{n \\times D}$). \n- (line 183) (typo) \"the the\".\n- (*) For your information, I tried to run the code. However, I got the following error: \n```\n  File \"..../laplacians.py\", line 181, in coboundary_map\n    indptr = np.arange(simplices.shape[0]+1, dtype=int) * simplices.shape[1]\nIndexError: tuple index out of range\n```\nafter data generation. I may have done something wrong though. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper discusses some of its limitations/important requirements (e.g. having access to a Simplicial Complex with the correct homology, etc.). I did not identify any significant potential social impact the paper could have, aside (as mentioned by the paper) from the risk (of any ML algorithms) of being used without proper understanding of it (leading to misinterpretation, etc.).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "f-Agh3bbi61", "reviewer": "Reviewer_viBo", "summary": "This paper presents a method for calculating (or rather *estimating*)\nthe null space of the $k$th Laplacian. This enables the analysis of the\ngeometry of $k$th homology embedding, making it possible to factorise\nsuch an embedding into different subspaces corresponding to individual\nprime factors of a given manifold. The proposed method also turns out to\nbe applicable to improve loop homology generators, leading to geometrically\nmore concise ('localised') representations of such loops.\n\nThe new method is showcases on a variety of data sets, demonstrating its\noverall utility for loop localisation and geometric decompositions.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Summary of the Review\n\nThis paper deals with a highly interesting and intriguing subject,\nnamely the utility of higher-order Laplacian operators (or Hodge\nLaplacians in general) for data analysis. I am excited to see more\npapers discussing these concepts in a machine learning context.\n\nThat being said, I am a little bit on the fence when it comes to\npublishing this paper; the current write-up is very 'dense' and\nnecessitates knowledge about a lot of additional topics that are not yet\npart of the common machine learning canon. Thus, it is possible that the\nresults of this paper will remain inaccessible to a non-expert audience.\nAt the same time, I also empathise with efforts of proposing frameworks\nthat are hitherto unknown; getting the proverbial 'foot in the door' is\nno simple endeavour.\n\nI therefore currently lean towards *accepting* this paper, on the\nproviso that the paper is rewritten to improve clarity and the logical\nflow of the exposition. Please see below for more in-depth comments.\n\n## Detailed Comments on Clarity\n\n- The vector space perspective for $\\mathcal{H}_k$ is justified, but\n  not necessarily in line with standard topology textbooks, which seem\n  to prefer the group perspective, i.e. they are typically referring to\n  $\\mathcal{H}_k$ as the $k$th homology group. I would suggest to at\n  least clarify this distinction briefly.\n\n- In TDA, one typically extracts more than just the ranks of the\n  homology groups; please see a recent survey ([Hensel et al., A Survey of Topological Machine Learning Methods](https://www.frontiersin.org/articles/10.3389/frai.2021.681108/full))\n  for more details.\n\n- The choice of orientation should not matter for the subsequent\n  definition of the Hodge Laplacian, as far as I understand. If so, this\n  could be briefly discussed in the text.\n\n- $\\mathbf{\\omega}_k$ needs a better definition; I found this to be hard\n  to understand on my first read of the paper; the definition given in\n  l. 53 looks tautological at first glance.\n\n- When introducing the orientations in a boundary matrix, the term\n  $\\mathbf{B}_2$ in l. 64 appears twice; I think the second term should\n  use $y, x$ instead of $x, y$.\n\n- Overall, this discussion could be shortened; I would suggest to either\n  provide a brief (graphical) example here instead.\n\n- Is the discussion of continuous operators (in l. 89--) pertinent for\n  this manuscript? I appreciate this link but it slightly detracts from\n  the overall logical flow of this section. Please consider moving it\n  somewhere else (or relegating it to an extended discussion section).\n\n- When discussing the connected sums of manifolds, I would mention that\n  this decomposition is unique *up to homeomorphism*.\n\n- When discussing the connected sum representation of manifolds, readers\n  with an ML background might appreciate a link to 'disentangled\n  representations' here; while 'disentanglement' is a more general\n  concept, I think the connection to such a sum will be apparent and\n  help build some intuition.\n\n- When discussing definitions, it would sometimes be helpful to explain\n  what the assumptions are. For instance, in l. 116, I would start the\n  definition with 'Given data $\\mathbf{X}$ sampled from a manifold' or\n  'We assume that we have...' or something like this.\n\n- In terms of terminology, I am wondering whether the notation with an\n  additional hat is really required; does the additional superscript not\n  characterise the relevant terms here? In other words, does\n  $\\mathcal{L}^{(i)}_k$ not suffice to indicate the Laplacian of some\n  manifold $\\mathcal{M}_i$?\n\n  (feel free to disregard this comment; I merely want to stress that any\n  simplifications or updates to the terminology will surely be\n  appreciate by readers; there are no *errors* in here, just a lot of\n  concepts to keep track of)\n\n- Figure 1 should be shown more prominently; in its present size,\n  differences are very hard to grasp.\n\n- What is meant by the 'geometric structure of $\\mathcal{H}_k$?\n  A priori, these homology groups do not have any geometric structure\n  because they are defined in a purely combinatorial manner. All the\n  geometrical information requires linking the respective simplicial\n  complex to a point cloud etc.\n\n- How strong of an assumption is the condition described in l. 189? The\n  subsequent sentences describe this partially, but I was wondering\n  about the practical implications here.\n\n- The notation in Assumption 3 cold be explained; I think the main idea\n  is to select certain subsets from a matrix, is this correct?\n\n- I fail to understand the discussion on sparsely-connected manifolds.\n  Is this related to the sampling density of the manifold? This\n  discussion should be improved; I am in particular wondering what the\n  meaning of this would be in the point cloud setting.\n\n- Please provide all definitions required to understand Theorem 1 in the\n  main text. The main text should be as self-contained as possible.\n\n- Is the bound in Equation (2) tight?\n\n- Please provide more details for the algorithm; I really appreciate the\n  pseudo-code here as it serves to demonstrate the practical utility of\n  the proposed framework. Nevertheless, maybe the exposition could be\n  tipped in favour of explaining the algorithmic details, relegating\n  some of the more advanced concepts to a section that addresses readers\n  that are more familiar with this background.\n\n- When classifying 2-manifolds, typically, higher-dimensional homology\n  groups are employed. The torus is easily distinguished from the circle\n  by $\\mathcal{H}_2$. The discussion in l. 285 should take this into\n  account.\n\n- Proposition 4 could be relegated to the supplements; it does not seem\n  to be directly connected to the proposed applications.\n\n- Why are the loops in Figure 2 (k), (l) so localised? Is there\n  a preference for a certain basepoint in the algorithm?\n\n- The loop detection seems to be of independent interest and *not* tied\n  to a specific decomposition. It might be worth expanding on this.\n\n## Language & Style\n\nThe writing in this paper is very goods and flows very well; some of the\nformulations are slightly terse, but this can be easily rectified in\na revision. Here are some formulations that I stumbled over upon reading\nthis paper for the first time:\n\n- 'as a perturbation to the direct sum' --> should this be rephrased as 'as a perturbation of the direct sum'?\n\n- 'theoretical analysis in $\\mathbf{Y}$' --> 'the theoretical analysis of $\\mathbf{Y}$'\n\n- '$\\mathrm{SC_2}$ = [...] commonly used' --> '$\\mathrm{SC_2}$, which is commonly used'\n\n- 'choosing an orientation to' --> 'choosing an orientation for'\n\n- 'simplexes' --> 'simplices' (I think both spelling are fine, but\n  please ensure consistent use)\n\n- l. 84: 'homology class' --> 'homology classes'\n\n- l. 114: 'how $\\mathbf{Y}$ relates to that of each prime manifold':\n  what does 'that' refer to here? Is this a reference to the local\n  homology embedding of each manifold $\\mathcal{M}_i$?\n\n# Update (rebuttal phase)\n\nIn light of the detailed responses by the authors, which helped clarify aspects in the paper tremendously, I am happy to raise my score accordingly. I am sure that this publication will make an excellent contribution to NeurIPS. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are partially addressed; a more in-depth discussion of\ncomplexity would be beneficial, in particular since the proposed method\nfor loop localisation is compared favourably to existing algorithms. One\nnecessary restriction wrt. the dimension $k$ should also be discussed;\nit seems that the decomposition generalises to arbitrary $k$, while the\nloop localisation does not. Is this correct?\n\nBeing of a primarily theoretical nature, I foresee no adverse societal\neffects arising from this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "aRXoaxzZYYZ", "reviewer": "Reviewer_auuC", "summary": "This paper studies the kernel of the higher-order combinatorial Laplacian, which equivalently amounts to a study of higher-order homology. In particular, given finite samples from a manifold with a ground truth decomposition into a connected sum of smaller (\"prime\") manifolds, they study the question of when it is possible to computationally recover a \"nice\" homology basis such that the basis vectors are resolved into independent components contributed from each of the prime manifolds. In this sense, the theoretical aim is quite nice and fundamental. The authors are able to provide a positive answer to their question in the setting where the prime manifolds are connected over a small, sparsely connected region. The proof technique is similar to that for obtaining bounds in spectral graph theory, but is carefully implemented because the problem has lots of block matrices floating around. Finally, the authors propose algorithmic applications of this method to the problem of detecting shortest loops in data, and exemplify their constructions on several point cloud and image datasets. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**: I believe this paper makes an important, foundational step in the study of \"spectral topological data analysis\" by obtaining recovery guarantees for a nice homology basis as described in the summary. The underlying theoretical problem seems to have been hinted at by reference [17], but I am not aware of works beyond [17] that have taken a close look at this problem. The connection to the geometry of spectral clustering (i.e. the orthogonal cone structure, ref. [36]) provides very nice theoretical motivation. \n\n**Clarity**: Much of the paper is extremely well-written, with careful descriptions as well as adequate explanation and intuition behind assumptions and results. However, I have a few concerns. The mixing of chains/co-chains/cycles/boundaries/coboundaries starts in page 2 and propagates throughout, and thus the reader finds lines that simultaneously talk about cycles and cochains, as well as cochains and boundary matrices (as opposed to coboundary matrices). This gets quite confusing, and occasionally I'm not sure if the paper is talking a particular operator or its adjoint. Page 2 introduces cochains in a boldface definition, but the rest of the paper talks about homology (as opposed to cohomology). The authors put a footnote saying that they use chains/cochains for simplicity, but I feel that mixing terminology between a space and its dual actually makes things complicated. Ref. [17] seems to stick only to chains/boundaries--why not adopt a similar approach, which would save confusion as well as space?\n\nA few more items: \np3, l87: \"only identifiable up to a unitary transformation;\" please add a reference or explanation\n\np3 Definitions: I am a little confused: L_k is defined to be the k-Laplacian of M, but later L_k is used as a matrix, which suggests that the underlying space is finite. Should L_k be defined in relation to the data set X? Also, the rest of the definitions here don't refer to the actual data X either\n\np4,l136: can you expand on the theoretical difficulty? Where would the trivial bound come from?\n\np4, l168: mismatch between capital D and lowercase d?\n\np4, Latschev has a theorem stating that if X is a sufficiently fine sample of M, then a particular complex (the Vietoris-Rips complex) will be homotopy equivalent to M. Perhaps this reference can be used to support Assumption 1.\n\np4, l185: In the definition of $\\mathfrak{N}$, i.e. the non-intersecting simplices, I was confused to see that one $\\Sigma$ has a hat while the other doesn't. This was clarified in the supplementary materials, but it should be explained in the main text, perhaps in the Section 3 Definitions.\n\np4, Where are the notions of \"destroying\" or \"creating\" simplices defined? Section 2 relegates the definition of connected sum in the case of simplicial complexes to Section 3, but it seems to have been left out from the final version. Also, the notion of \"intersecting simplices\" is not explained---is this just the union of \"created\" and \"destroyed\" simplices, as suggested by p5, l189? Later in the reading process I found more explanations in the supplementary materials, but I would request that the authors be very explicit in setting up these definitions in the main text, as they are crucial for understanding the setup of the main results. \n\n**Quality**: The overall theoretical question and its resolution are both quite nice, and I appreciate the algorithmic aspects that the authors exemplified on multiple datasets. However, some claims may need to be adjusted. In p1, l20: \"Topological Data Analysis... aims to extract the dimension of $\\mathcal{H}_k$ and has found wide use in analyzing biological...\" creates ambiguity about the purpose of the field and the importance of extracting the dimension of $\\mathcal{H}_k$. Certainly not all TDA techniques are interested in homology (ref 34 is out of place here, as it purely relies on the Mapper algorithm), and among those that are, perhaps the flagship tool is persistent homology, which goes much beyond simply computing the rank of the homology vector space. In the abstract, the authors write \"Our spectral loop detection algorithm scales better than existing methods\", and this is true in the context of the complexity of ref. [15] reported in page 6, but what about comparing to the results in ref. [16]? Furthermore, the experiments do not appear to compare runtimes to existing baselines, which I think is a bit of a missed opportunity. I am also curious about the true cost of the eigendecomposition of $\\mathcal{L}$. P6L282 suggests that the number of triangles can grow very quickly and pose a challenge to other methods -- doesn't this also affect the computation of $\\mathcal{L}_1$, which needs the computation of boundary matrix $B_2$?\n\n**Significance**: Overall, I liked the paper, and I think it has the ingredients of a nice publication. However, I think that the authors could better connect to the ML papers that have come out of graph signal processing research. For instance, reference [A] provided below seems to have some latent connection, in that it utilizes edge flows to cluster a graph and find bottlenecks, which may perhaps be related to the places where prime manifolds connect in the current paper. References [B,C], while less related, relate to useful learning tasks, and connecting to such literature would be helpful for an ML audience.\n\n**Conclusion**: In summary, I like the paper and its theoretical results, but I think it is affected by a few issues of clarity and a somewhat tenuous connection to learning tasks. \n\n\n[A] Jia, J., Schaub, M. T., Segarra, S., & Benson, A. R. (2019, July). Graph-based semi-supervised & active learning for edge flows. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (pp. 761-771).\n\n[B] Roddenberry, T. M., & Segarra, S. (2019, November). HodgeNet: Graph neural networks for edge data. In 2019 53rd Asilomar Conference on Signals, Systems, and Computers (pp. 220-224). IEEE.\n\n[C] Roddenberry, T. M., Glaze, N., & Segarra, S. (2021, July). Principled simplicial neural networks for trajectory prediction. In International Conference on Machine Learning (pp. 9020-9029). PMLR.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe that the authors have addressed the societal impact quite nicely. I have some concerns about the limitations that I have described above in the \"Quality\" section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "Nf2URndFhtD", "reviewer": "Reviewer_R3gu", "summary": "In this manuscript, the authors study the decomposition of the homology spaces from Hodge Laplacian matrices, and propose a new algorithm for the detection of the shortest homology generators. In their model, the direct sum of homology embedding or spaces from Hodge Laplacian is approximated by connected sum of manifolds. More specifically, the homology space is decomposed into subspaces with simple topological components. An algorithm is designed to detect shortest homology loops in the structure. The approach to use homology spaces for clustering and detection of shortest loops is very novel and interesting. It expands the area of topological data analysis, and will have a great impact for various data modelling and analysis. ", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Major problems,\n\n1)\tThe claim that “Analysis of the eigenfunctions of H0 of the graph Laplacian L0 is pivotal in providing guarantees for spectral clustering and community detection algorithms” is not proper at all! In MOST (not all) spectral clustering and community detection problems, their graphs are well-connected and the corresponding L0 matrices have only one zero-eigenvalue (with a trivial eigenvector). In these models, the clustering and community are determined by the eigenvectors from the smallest non-zero eigenvalues. Note that only in some special cases, graphs are not well-connected and separated into individual subgraphs and  “eigenfunctions of H0” is “pivotal”! \n\n2)\tThe authors need to provide more tests and comparisons to support their claim that “Our spectral loop detection algorithm scales better than existing methods and is effective on diverse data such as point clouds and images”. In fact, “Shortest homologous loop” is a very interesting and important topic that has been actively studied in computational geometry/topology. There are a lot of existing works in this area. To name only a few, \n\nFeng, Xin, and Yiying Tong. \"Choking loops on surfaces.\" IEEE transactions on visualization and computer graphics 19.8 (2013): 1298-1306.\n\nDey, Tamal K., Fengtao Fan, and Yusu Wang. \"An efficient computation of handle and tunnel loops via Reeb graphs.\" ACM Transactions on Graphics (TOG) 32.4 (2013): 1-10.\n\nChambers, Erin W., Jeff Erickson, and Amir Nayyeri. \"Minimum cuts and shortest homologous cycles.\" Proceedings of the twenty-fifth annual symposium on Computational geometry. 2009.\n\nDey, Tamal K., Tao Hou, and Sayan Mandal. \"Persistent 1-cycles: Definition, computation, and its application.\" International Workshop on Computational Topology in Image Context. Springer, Cham, 2019.\n\nChao Chen, Daniel Freedman: \"Hardness results for homology localization\", in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010\n\nT. K. Dey, A. Hirani, and B. Krishnamoorthy.   \"Optimal homologous cycles, total unimodularity, and linear programming.\" SIAM J. Computing, Vol. 40, pp 1026--1044. Prelim. version in 42nd ACM Sympos. Comput. Theory (STOC 2010)\n\nOleksiy Busaryev, Sergio Cabello, Chao Chen, Tamal K. Dey, Yusu Wang: \"Annotating simplices with a homology basis and its applications\", in Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2012\n\nPengxiang Wu, Chao Chen, Yusu Wang, Shaoting Zhang, Changhe Yuan, Zhen Qian, Dimitris Metaxas, Leon Axel:  \"Optimal Topological Cycles and Their Application in Cardiac Trabeculae Restoration\", in Information Processing in Medical Imaging (IPMI), 2017\n\nIn this manuscript, the authors only compare their model with the one in Ref 15 (even though they have mentioned Ref 16 in their paper) and claim that their models “scales better than existing methods”. The authors are suggested to add more discussions and comparisons to these existing models. \n\n3)\tIn fact, homology spaces and their applications have been extensively studied through Hodge decomposition.  To name only a few, \n\nJiang, Xiaoye, Lek-Heng Lim, Yuan Yao, and Yinyu Ye. \"Statistical ranking and combinatorial Hodge theory.\" Mathematical Programming 127, no. 1 (2011): 203-244.\n\nZhao R, Wang M, Chen J, Tong Y, Wei GW. The de Rham–Hodge Analysis and Modeling of Biomolecules. Bulletin of mathematical biology. 2020 Aug;82(8):1-38.   \n\nThe authors are suggested to add more discussions about these progresses.   \n\nMinor problems,\n1)\tThe term “k-Laplacian” used in this paper is not very proper. It should be k-th combinatorial Laplacian or Hodge Laplacian. There are various definitions of Laplacian matrixes, such as Graph Laplacian, Hodge Laplacian, Tarski Laplacian, path Laplacian, etc. The authors need to be more precise to avoid confusion.\n\n2)\tPage 2, line 64, typo in the equation for boundary matrix.\n\n3)\tPage 3, line 86, only $y_1$ eigenvector is used in the expression? I guess it should be a typo.\n\n4)\tRecently, there are great advancements in persistent spectral models from Hodge Laplacian. With persistent eigen-information (both eigenvalue and eigenvectors), Persistent spectral based machine learning models outperform ALL existing machine learning models (>40) in common benchmark dataset, demonstrating the great advantage and significance of Hodge Laplacian models in real application!\n\nRui Wang, Duc D Nguyen and Guo-Wei Wei, Persistent spectral graph, International Journal for Numerical Methods in Biomedical Engineering, 36(9), e3376  (2020). \n\nZhenyu Meng and Kelin Xia, \"Persistent spectral based machine learning (PerSpect ML) for protein-ligand binding affinity prediction\", Science advances, 7(19), eabc5329, 2021\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20 "}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates the reconstruction of a connected sum of (prime) manifolds from finite samples. It exploits the connection between the null space of the combinatorial Laplacian and the homology of a manifold, in order to recover the homological basis corresponding to the prime manifolds. Theoretical results are proven as to when will the reconstruction be successful. The method is applied to the computation of the shortest homologous cycle problem, and results were shown on various datasets. 

All reviewers highly rated the paper. They considered it original, well written, providing strong theoretical results, and delivering inspiring connections between topological data analysis and spectral analysis. 
Decision: Accept (Oral)