Research map / Learning theory and algorithms / Clustering

Signed Laplacians for Constrained Graph Clustering

ICML 2025 · Learning theory and algorithms › Clustering · approach: Spectral clustering algorithms

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes CC++, a spectral constrained graph clustering method that uses a Cheeger-type inequality and a signed Laplacian of the constraint graph (with an added negative self-loop) to solve a generalised eigenvalue problem for cut-ratio minimisation.

Problem

Constrained graph clustering: find a vertex subset minimising the cut ratio between a must-link graph G and a cannot-link graph H, which is NP-hard to approximate well in general and where standard spectral clustering ignores constraints.

Approach

Establishes a Cheeger-type inequality bounding the constrained cut ratio by λ2 of the generalised problem (Δ_G vs Δ_H) and λ2(Δ_H), then makes it efficient by scaling G, adding self-loops to equalise degrees, and inserting a negative self-loop in H so the signed Laplacian is invertible and Cholesky-based solving applies.

Key results

• On the SBM with n=1000, CC and CC++ keep ARI above 0.5 at q≈0.17 where SC drops to near 0.1 between q=0.16 and 0.18.
• On RGG data, SC's ARI falls to near zero for overlapping clusters while the generalised eigenvalue method keeps significantly higher ARI.
• On Brittany temperature data, CC++ achieves 79.16%/81.04%/77.95% correct separations versus SC's 63.30%/62.90%/62.63% (temperature/max/min).

Measured effects reported in the paper

Surprising findings

• CC++ with a negative self-loop performs comparably to the unmodified CC, suggesting the self-loop has little impact on results.

Limitations

• Theoretical bound relates to λ2 of the signed-Laplacian generalised problem; the self-loop replacement only gives an inequality via Lemma 3.4.
• Experiments are limited to small synthetic graphs and a single real-world temperature dataset.
• Real-world evaluation uses a proxy criterion (non-overlap of standard-error intervals) rather than ground-truth labels.

Experimental setup

Datasets: synthetic binary stochastic block model (n=1000) synthetic random geometric graphs (2x500 points) Brittany ground station temperature data (January 2014, Girault 2015)

Benchmarks: synthetic SBM clustering synthetic RGG cluster separation Brittany temperature station clustering

Metrics: Adjusted Rand Index mean execution time percentage of successful separation

Baselines: SPECTRAL CLUSTERING (SC) CONSTRAINED CLUSTERING (CC)

Builds on: Cheeger inequality spectral clustering Cucuringu et al. 2016 constrained cut bound Koutis et al. 2023 constrained conductance bound Wang et al. 2014 constrained spectral clustering

Closest papers by meaning

• Spectral Clustering of Signed Graphs via Matrix Power Means (ICML 2019 · similarity 0.90)
• Clustering Signed Networks with the Geometric Mean of Laplacians (NeurIPS 2016 · similarity 0.90)
• Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract) (AAAI 2024 · similarity 0.88)
• Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · similarity 0.87)
• Equivalence between Graph Spectral Clustering and Column Subset Selection (Student Abstract) (AAAI 2024 · similarity 0.87)
• Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.85)