Reproduce “Spectral Clustering with Graph Neural Networks for Graph Pooling” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Filippo Maria Bianchi, Daniele Grattarola, Cesare Alippi

MinCutPool introduces a GNN-based graph pooling operator that leverages a continuous relaxation of the normalized minCUT problem, overcoming the computational and differentiability limitations of traditional spectral clustering. This method consistently outperforms existing pooling techniques in unsupervised node clustering, graph information retention, and supervised graph classification and regression tasks by combining theoretical grounding with learnability.

Key insights

  • MinCutPool successfully integrates the theoretical rigor of spectral clustering (normalized minCUT problem) with the adaptive and differentiable capabilities of Graph Neural Networks for hierarchical graph representation learning.
  • The proposed unsupervised loss function, combining a cut loss with an orthogonality loss, is crucial for preventing degenerate solutions often seen in heuristic-based learnable pooling methods, leading to robust and balanced clusters.
  • Formulating graph clustering as an optimization problem solvable by a GNN avoids the computationally expensive eigendecomposition of traditional spectral clustering, achieving a complexity of O(K(E + NK)) and enabling scalability.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.