Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 

**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?

A few more items: 
p3, l87: "only identifiable up to a unitary transformation;" please add a reference or explanation

p3 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

p4,l136: can you expand on the theoretical difficulty? Where would the trivial bound come from?

p4, l168: mismatch between capital D and lowercase d?

p4, 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.

p4, 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.

p4, 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. 

**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$?

**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.

**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. 


[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).

[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.

[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.
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_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a method for calculating (or rather *estimating*)
the null space of the $k$th Laplacian. This enables the analysis of the
geometry of $k$th homology embedding, making it possible to factorise
such an embedding into different subspaces corresponding to individual
prime factors of a given manifold. The proposed method also turns out to
be applicable to improve loop homology generators, leading to geometrically
more concise ('localised') representations of such loops.

The new method is showcases on a variety of data sets, demonstrating its
overall utility for loop localisation and geometric decompositions.

main_review: # Summary of the Review

This paper deals with a highly interesting and intriguing subject,
namely the utility of higher-order Laplacian operators (or Hodge
Laplacians in general) for data analysis. I am excited to see more
papers discussing these concepts in a machine learning context.

That being said, I am a little bit on the fence when it comes to
publishing this paper; the current write-up is very 'dense' and
necessitates knowledge about a lot of additional topics that are not yet
part of the common machine learning canon. Thus, it is possible that the
results of this paper will remain inaccessible to a non-expert audience.
At the same time, I also empathise with efforts of proposing frameworks
that are hitherto unknown; getting the proverbial 'foot in the door' is
no simple endeavour.

I therefore currently lean towards *accepting* this paper, on the
proviso that the paper is rewritten to improve clarity and the logical
flow of the exposition. Please see below for more in-depth comments.

## Detailed Comments on Clarity

- The vector space perspective for $\mathcal{H}_k$ is justified, but
  not necessarily in line with standard topology textbooks, which seem
  to prefer the group perspective, i.e. they are typically referring to
  $\mathcal{H}_k$ as the $k$th homology group. I would suggest to at
  least clarify this distinction briefly.

- In TDA, one typically extracts more than just the ranks of the
  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))
  for more details.

- The choice of orientation should not matter for the subsequent
  definition of the Hodge Laplacian, as far as I understand. If so, this
  could be briefly discussed in the text.

- $\mathbf{\omega}_k$ needs a better definition; I found this to be hard
  to understand on my first read of the paper; the definition given in
  l. 53 looks tautological at first glance.

- When introducing the orientations in a boundary matrix, the term
  $\mathbf{B}_2$ in l. 64 appears twice; I think the second term should
  use $y, x$ instead of $x, y$.

- Overall, this discussion could be shortened; I would suggest to either
  provide a brief (graphical) example here instead.

- Is the discussion of continuous operators (in l. 89--) pertinent for
  this manuscript? I appreciate this link but it slightly detracts from
  the overall logical flow of this section. Please consider moving it
  somewhere else (or relegating it to an extended discussion section).

- When discussing the connected sums of manifolds, I would mention that
  this decomposition is unique *up to homeomorphism*.

- When discussing the connected sum representation of manifolds, readers
  with an ML background might appreciate a link to 'disentangled
  representations' here; while 'disentanglement' is a more general
  concept, I think the connection to such a sum will be apparent and
  help build some intuition.

- When discussing definitions, it would sometimes be helpful to explain
  what the assumptions are. For instance, in l. 116, I would start the
  definition with 'Given data $\mathbf{X}$ sampled from a manifold' or
  'We assume that we have...' or something like this.

- In terms of terminology, I am wondering whether the notation with an
  additional hat is really required; does the additional superscript not
  characterise the relevant terms here? In other words, does
  $\mathcal{L}^{(i)}_k$ not suffice to indicate the Laplacian of some
  manifold $\mathcal{M}_i$?

  (feel free to disregard this comment; I merely want to stress that any
  simplifications or updates to the terminology will surely be
  appreciate by readers; there are no *errors* in here, just a lot of
  concepts to keep track of)

- Figure 1 should be shown more prominently; in its present size,
  differences are very hard to grasp.

- What is meant by the 'geometric structure of $\mathcal{H}_k$?
  A priori, these homology groups do not have any geometric structure
  because they are defined in a purely combinatorial manner. All the
  geometrical information requires linking the respective simplicial
  complex to a point cloud etc.

- How strong of an assumption is the condition described in l. 189? The
  subsequent sentences describe this partially, but I was wondering
  about the practical implications here.

- The notation in Assumption 3 cold be explained; I think the main idea
  is to select certain subsets from a matrix, is this correct?

- I fail to understand the discussion on sparsely-connected manifolds.
  Is this related to the sampling density of the manifold? This
  discussion should be improved; I am in particular wondering what the
  meaning of this would be in the point cloud setting.

- Please provide all definitions required to understand Theorem 1 in the
  main text. The main text should be as self-contained as possible.

- Is the bound in Equation (2) tight?

- Please provide more details for the algorithm; I really appreciate the
  pseudo-code here as it serves to demonstrate the practical utility of
  the proposed framework. Nevertheless, maybe the exposition could be
  tipped in favour of explaining the algorithmic details, relegating
  some of the more advanced concepts to a section that addresses readers
  that are more familiar with this background.

- When classifying 2-manifolds, typically, higher-dimensional homology
  groups are employed. The torus is easily distinguished from the circle
  by $\mathcal{H}_2$. The discussion in l. 285 should take this into
  account.

- Proposition 4 could be relegated to the supplements; it does not seem
  to be directly connected to the proposed applications.

- Why are the loops in Figure 2 (k), (l) so localised? Is there
  a preference for a certain basepoint in the algorithm?

- The loop detection seems to be of independent interest and *not* tied
  to a specific decomposition. It might be worth expanding on this.

## Language & Style

The writing in this paper is very goods and flows very well; some of the
formulations are slightly terse, but this can be easily rectified in
a revision. Here are some formulations that I stumbled over upon reading
this paper for the first time:

- 'as a perturbation to the direct sum' --> should this be rephrased as 'as a perturbation of the direct sum'?

- 'theoretical analysis in $\mathbf{Y}$' --> 'the theoretical analysis of $\mathbf{Y}$'

- '$\mathrm{SC_2}$ = [...] commonly used' --> '$\mathrm{SC_2}$, which is commonly used'

- 'choosing an orientation to' --> 'choosing an orientation for'

- 'simplexes' --> 'simplices' (I think both spelling are fine, but
  please ensure consistent use)

- l. 84: 'homology class' --> 'homology classes'

- l. 114: 'how $\mathbf{Y}$ relates to that of each prime manifold':
  what does 'that' refer to here? Is this a reference to the local
  homology embedding of each manifold $\mathcal{M}_i$?

# Update (rebuttal phase)

In 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. 
limitations_and_societal_impact: Limitations are partially addressed; a more in-depth discussion of
complexity would be beneficial, in particular since the proposed method
for loop localisation is compared favourably to existing algorithms. One
necessary restriction wrt. the dimension $k$ should also be discussed;
it seems that the decomposition generalises to arbitrary $k$, while the
loop localisation does not. Is this correct?

Being of a primarily theoretical nature, I foresee no adverse societal
effects arising from this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
It 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. 
Building 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. 
This has applications in particular in homologous loop detection (detecting the shortest generating element in H1), as showcased on both synthetic and real datasets.

main_review: 
Clarity:
Overall, 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. 

Significance: 
This 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. 

Questions:
- 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?


Minor remarks and suggestions:
- Perhaps including an illustration of the notions introduced in Section 2 (background) would be helpful, if there is enough room. 
- (line 64) (typo) I think it should be $B2_{[yz]}(x,y,z) = 1$ the second time. 
- (line 85) (typo) $[y_1, ..., y_{beta_1}]$ should be _beta_k. A similar typo occurs in other places. 
- (line 119) Talking about the k-Laplacian ``"of M'' is somewhat confusing as those notions/notations are introduced for discrete objects.
- (line 120) (suggestion) Perhaps using \widehat would help readability. 
- (line 169) (typo) I think M should be in $\mathbb{R}^D$ (not $\mathbb{R}^{n \times D}$). 
- (line 183) (typo) "the the".
- (*) For your information, I tried to run the code. However, I got the following error: 
```
  File "..../laplacians.py", line 181, in coboundary_map
    indptr = np.arange(simplices.shape[0]+1, dtype=int) * simplices.shape[1]
IndexError: tuple index out of range
```
after data generation. I may have done something wrong though. 
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_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: 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. 
main_review: Major problems,

1)	The 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”! 

2)	The 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, 

Feng, Xin, and Yiying Tong. "Choking loops on surfaces." IEEE transactions on visualization and computer graphics 19.8 (2013): 1298-1306.

Dey, 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.

Chambers, Erin W., Jeff Erickson, and Amir Nayyeri. "Minimum cuts and shortest homologous cycles." Proceedings of the twenty-fifth annual symposium on Computational geometry. 2009.

Dey, 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.

Chao Chen, Daniel Freedman: "Hardness results for homology localization", in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010

T. 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)

Oleksiy 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

Pengxiang 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

In 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. 

3)	In fact, homology spaces and their applications have been extensively studied through Hodge decomposition.  To name only a few, 

Jiang, Xiaoye, Lek-Heng Lim, Yuan Yao, and Yinyu Ye. "Statistical ranking and combinatorial Hodge theory." Mathematical Programming 127, no. 1 (2011): 203-244.

Zhao 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.   

The authors are suggested to add more discussions about these progresses.   

Minor problems,
1)	The 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.

2)	Page 2, line 64, typo in the equation for boundary matrix.

3)	Page 3, line 86, only $y_1$ eigenvector is used in the expression? I guess it should be a typo.

4)	Recently, 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!

Rui Wang, Duc D Nguyen and Guo-Wei Wei, Persistent spectral graph, International Journal for Numerical Methods in Biomedical Engineering, 36(9), e3376  (2020). 

Zhenyu Meng and Kelin Xia, "Persistent spectral based machine learning (PerSpect ML) for protein-ligand binding affinity prediction", Science advances, 7(19), eabc5329, 2021

limitations_and_societal_impact: None
review_title: null

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)