- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper proposes Empool, a graph pooling method motivated by discrete Morse theory. The authors represent graphs as Lefschetz complexes and learn a scalar function on vertices, which is used to construct a discrete gradient through a steepest-descent procedure. The resulting gradient is then used to identify representative vertices and construct a reduced graph through a sink-assignment matrix.
The main theoretical claim is that this graph reduction preserves the homology of the original graph, relying on results from Forman's discrete Morse theory. The authors also introduce a differentiable relaxation of the pooling operation to make the method trainable end-to-end.
The method is evaluated on six datasets for node- and graph-prediction tasks, with comparisons against standard GNN architectures and existing graph pooling methods.
Critical strengths
The main strength of the paper is the idea of using discrete Morse theory for graph pooling. If the proposed reduction could preserve the topological information of the original graph while reducing its complexity, this would be an interesting contribution to graph representation learning.
The authors also try to integrate this construction into an end-to-end trainable architecture and evaluate it on both node- and graph-prediction tasks. I appreciate that the paper includes implementation details in the appendix.
Critical weaknesses
1. The theoretical guarantees do not seem to apply to the actual pooling operation.
My main concern with the paper is that I could not find a clear mathematical justification connecting the proposed pooling operation to the discrete Morse theory results used by the authors.
The problem is how the paper goes from the constructed discrete gradient to the graph obtained after pooling, and why this graph should preserve homology.
In discrete Morse theory, an acyclic matching can be used to construct a reduced Morse complex whose chain groups are generated by the critical cells. The boundary operators of this complex are determined by the original complex and the matching. This reduced complex has the same homology as the original one [1, 2].
However, in Empool, the authors construct the reduced graph using the sink-assignment matrix. This operation identifies vertices according to their gradient assignments and merges multiple edges between the same clusters. I could not find a proof showing that the chain complex associated with this binary graph quotient is the Morse complex induced by the original acyclic matching.
This distinction is important because the homology-preservation guarantee applies to the Morse reduction, not automatically to every graph constructed from the matching.
In particular, Theorem 2 claims that the graph formed by identifying vertices along gradient paths preserves homology under valid elementary collapses. However, its proof in Appendix B.1 mainly invokes Forman's theorem [3] and states that the proposed vertex identifications correspond to elementary collapses. It does not establish this correspondence mathematically or construct the boundary operators of the resulting Morse complex.
For instance, consider two triangles sharing an edge, with and . The original graph has , and the resulting acyclic matching has one critical vertex and two critical edges. However, Empool assigns every vertex to the same cluster, producing a binary graph with if self-loops are removed, or if one self-loop is retained as a 1-cell.
This raises what I consider the most fundamental question about the paper: if the proposed pooling operation does not preserve homology, what is actually gained from discrete Morse theory?
The main motivation for discrete Morse reduction is precisely that it provides a principled simplification of a complex while preserving its topological information. If the actual pooling operation does not inherit this property, then the method seems much closer to a graph clustering procedure based on a learned scalar function and local minima than to a genuine Morse reduction. So the paper main title is not contained or well motivated (the paper could exist without discrete morse theory it seems since the homotopy/homology is not preserved).
2. The experiments do not sufficiently validate the theoretical claims.
There is no experiments verifying homology preservation, such as comparing Betti numbers before and after pooling. Comparisons with simpler clustering or pooling methods are also needed to understand the contribution of discrete Morse theory.
The predictive improvements are limited. Empool does not outperform all baselines on any node-prediction dataset, while the differences in empirical means on MUTAG and COLLAB are only 0.88 and 0.01 percentage points, respectively. I also found the presentation of the results somewhat strange. In Section 5, the authors emphasize that the rankings "should not be interpreted as evidence of statistical significance", and Table 1 repeats that the highlighted means "do not imply statistical significance" (which is already very strange for a paper to have in its results section). However, the conclusion still describes the results as "highly competitive and robust", despite the limited differences and considerably higher variability on ogbg-molhiv.
Similarly, Section 4.3 emphasizes a SHA-256 seed schedule and "100 independent training runs" on four datasets. but Section 4.1 explains that MUTAG and COLLAB use the same fixed 80/10/10 split across all runs. Thus, the 100 runs measure just weights initialization random/stochasticiness from what I understood but not robustness to different data partitions. I found this emphasis on the experimental protocol disproportionate with what is standard in the graph machine learning literature.
Finally, despite the motivation concerning computational and memory bottlenecks about morse matchings expensivenness there is no runtime experiments showing the improvements in scalability while using this proposed pooling.
References
[1] D. N. Kozlov. Discrete Morse Theory for Free Chain Complexes. Comptes Rendus Mathématique, 2005.
[2] E. Sköldberg. Morse Theory from an Algebraic Viewpoint. Transactions of the American Mathematical Society, 2006.
[3] R. Forman. Morse Theory for Cell Complexes. Advances in Mathematics, 1998.
Questions for authors
-
What exactly is the Morse complex associated with the discrete gradient constructed by Empool? How are the critical cells, particularly critical edges, and the corresponding boundary operators represented in the actual pooling operation?
-
How does the graph constructed through the sink assignments correspond to a valid discrete Morse reduction? Could the authors address the counterexample described in the weaknesses, where the original graph has , but the binary pooled graph does not preserve its homology?
-
If the proposed pooling operation does not generally preserve homology, what specific role does discrete Morse theory play in the method beyond providing a way to cluster vertices around local minima? What distinguishes this construction from simpler graph pooling approaches?
-
Could the authors provide direct experimental evidence of homology preservation, such as comparing Betti numbers before and after pooling? Also, why were 100 independent training runs used with fixed data splits on MUTAG and COLLAB, instead of evaluating it across different splits?
-
Considering that computational and memory efficiency are central motivations of the paper, could the authors provide runtime and peak-memory comparisons against the current baselines and other more recent graph pooling baselines?