acceptodds
Withdrawn from ICLR 2027

Empool: Collapse via Discrete Morse Theory for Representation Learning

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Despite their success on non-Euclidean data, Message Passing Neural Networks (MPNNs) face fundamental depth and expressivity limitations rooted in topological bottlenecks, notably over-smoothing and over-squashing. To address these structural constraints, we propose Empool, an end-to-end differentiable graph pooling framework grounded in discrete Morse theory. By modeling graphs as Lefschetz complexes, Empool learns a discrete Morse function through a parameterized multi-layer perceptron that governs a Forman reduction, progressively collapsing the graph topology into a compact set of critical cells while rigorously preserving its homology. The resulting sparse representation mitigates the topological bottlenecks responsible for information degradation in deep networks. Extensive experiments on established node- and graph-prediction benchmarks demonstrate competitive and robust performance relative to state-of-the-art architectures.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Message Passing Neural Networks, Graph Pooling, Neighborhood Explosion, Discrete Morse Theory

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_17n5OpenReview ↗
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 E={[ab,bc,ca,cd,da]}E=\{ [ ab,bc,ca,cd,da ]\} and f(a)=0,f(b)=1,f(c)=2,f(d)=3f(a)=0,f(b)=1,f(c)=2,f(d)=3. The original graph has β1=2\beta_1=2, 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 β1=0\beta_1=0 if self-loops are removed, or β1=1\beta_1=1 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
  1. 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?

  2. 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 β1=2\beta_1=2 , but the binary pooled graph does not preserve its homology?

  3. 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?

  4. 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?

  5. 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?

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

The paper proposes a novel hierarchical pooling operation for graph neural networks, using discrete Morse theory to map graphs to Lefschetz complexes, and proposing a pooling operation on these complexes. Performance is evaluated on 3 node-level prediction and 3 graph classification tasks compared to three baseline methods, showing that Empool reaches comparable performance to baseline GNNs.

Critical strengths

Novelty: This work does as far as I am aware propose a novel construction of a new graph pooling method using Morse theory, which has not previously been discussed in relation to graph pooling operations.

Mathematically interesting: The construction of the pooling operation is interesting and does seem to be mathematically sound, while also being clearly explained.

Critical weaknesses

Comparison with further pooling methods: The paper would benefit from discussing related work on graph pooling methods in more detail to clarify exactly why the proposed pooling operation advances upon existing pooling methods. Just because we can apply Morse theory to develop a pooling operator, further discussion on why existing pooling operators might fail to preserve graph topology in specific settings would be useful. Further, the paper would greatly benefit from evaluating a wider selection of pooling methods as currently only 2 other pooling methods are evaluated on the graph classification tasks, and no other pooling methods are evaluated on the node prediction tasks.

Weak experimental evaluation: Overall, based on the main empirical results in Table 1, it remains unclear whether Empool does provide a tangible empirical benefit in terms of performance over the evaluated baseline methods. It would be of interest to report performance across a wider range of further datasets, including standard benchmark datasets from e.g. TU datasets, or more recent tasks from GraphBench, but also potentially considering further ablations and novel applications beyond standard tasks that could show the benefits of Empool in practice. As it stands, considering uncertainty, Empool performs comparatively to the evaluated baseline methods on the limited number of evaluated tasks, showing no clear empirical advantage. This limited experimental advantage of Empool thus is the main weakness of the presented work. Further, no additional experiments or ablations are shown beyond this main performance comparison in Table 1 that could demonstrate the utility of Empool in practice. I believe that addressing the weaknesses in the empirical evaluation and providing stronger empirical results on the utility of Empool would require major additional experiments beyond the scope of rebuttals.

Computational Complexity: While runtime is given as a limitation, the computational complexity and computational costs of Empool are not evaluated in practice compared to baseline models. Further empirical evaluation would clarify the computational limitations of the proposed method, which might pose notable constraints in practice.

Questions for authors
  • Could you evaluate a random version of your Empool operator? Similar to the ablations reported in “Rethinking pooling in graph neural networks” by Mesquita et al. (2020), it would be interesting to evaluate a randomised version of your algorithm that instead of learning which vertex to collapse, collapses a random vertex.
  • Could you report performance across a larger number of graph datasets and comment on which types of graph datasets your methods ?
  • Could you report performance across a larger number of pooling layers, for example as implemented in the tgp (Torch Geometric Pool)?
  • Could you evaluate computational complexity in practice?
Reviewer_jZ9NOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Empool groups vertices based on score-based clustering and paths of steepest descent until the same sinks are reached. The theory behind the approach is discrete Morse theory, with the homology-preserving property being the primary theory claim.

Critical strengths

Using a descent field to define pooling assignments is a good concept. The assignments are sparse, and predictions are made at both node and graph levels.

Critical weaknesses
  1. Appendix B.1 removes self-loops from the pooled graph. On a triangle with scores 0, 1, and 2, all three vertices reach the score-0 sink. The edge joining scores 1 and 2 is an unmatched critical 1-cell in the Morse reduction and should survive as a loop. The implementation deletes it, changing the first Betti number from 1 to 0. I don't see how Theorem 2 applies to the graph returned by the layer.

  2. Theorem 4 assumes that the hard sink minimizes the squared score difference used by the straight-through surrogate. The descent rule does not guarantee this. On the path 0–5–6–4, the vertex scored 5 descends to 0, while the surrogate favors 4. The paper does not report how often these assignments disagree in training.

  3. Empool is slightly below GCN on all three node benchmarks. On MUTAG, it beats GIN by less than one percentage point (90.00 vs. 89.12), smaller than the contribution of a single graph in a roughly 19-graph test split. I also missed comparisons with Graph U-Net, which the approach builds on, and EdgePool.

Minor Comments

I'd put a before/after homology check ahead of another dataset. Accuracy against compression ratio, ablations over the pointer-jumping steps and regularizers, and a long-range task for the over-squashing motivation would help.

Questions for authors
  1. Where does the triangle's critical 1-cell go after the self-loop is removed? If exact homology preservation is not the guarantee of the returned graph, what can be guaranteed?

  2. How often do the hard sink and surrogate assignments disagree on the evaluated datasets?

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

Related papers

Discussion (0)

Sign in to comment.