Research map / Graph learning / Graph algorithms and clustering

Online Sparsification of Bipartite-Like Clusters in Graphs

ICML 2025 · Graph learning › Graph algorithms and clustering · approach: Neural and local graph clustering

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.

Gives nearly-linear-time, online random-sampling sparsifiers for undirected and directed graphs that preserve k bipartite-like clusters (cuts between vertex sets A_i and B_i), and speeds up local clustering algorithms on SBM and real migration/dispute data.

Problem

Local and global algorithms for finding bipartite-like clusters (pairs of vertex sets densely connected to each other) are slow on large graphs; sparsifiers used for cut or spectral preservation do not preserve the cut between paired sets A_i and B_i, and most are not defined for directed graphs.

Approach

Sample each edge with probability derived from endpoint degrees and the spectral gap 2-λ_{n-k} so that cuts w(A_i,B_i) are preserved in expectation with bounded variance; for digraphs, reduce to an undirected semi-double cover, sparsify it, and map back via a reverse semi-double cover. The sampling is local, so it runs online alongside local clustering algorithms.

Key results

• On the MIDs dataset, the sparsified pipeline ran in about 0.004 s versus about 0.034 s for MS from USA as seed, with bipartiteness 0.285 vs 0.292.
• On US migration data with Maricopa County as seed, the sparsified ECD ran in 13.434 s vs 20.661 s for ECD with flow ratio 0.417 vs 0.414.
• The paper claims nearly-linear time and that cluster structure is preserved with high probability, but the reported experiments use only 10 runs on modest synthetic graphs of up to 2,500 vertices per side.

Measured effects reported in the paper

Surprising findings

• On the Lithuania seed in the MIDs experiment, the sparsified bipartiteness ratio dropped to 0.165 versus 0.303 for MS, a large deviation from the others.
• In the migration experiment with Virginia Beach as seed, the sparsified flow ratio rose to 0.621 from 0.546, so the output was not uniformly similar.

Limitations

• Experiments are small-scale (SBM with up to 2,500 vertices per side) and run on a single laptop; no large-scale evaluation.
• Several theorems rely on assumptions such as rho-bar(k) >= 1/log n or rho-bar(k) = 1 - o(1/k) and constants hidden in the O-notation.
• Results on the real datasets show mixed quality: some seeds lose bipartiteness or flow ratio.

Experimental setup

Datasets: Stochastic block model synthetic graphs Dyadic Militarised Interstate Disputes Dataset (v3.1) US Migration Dataset (county-level, 1995-2000)

Benchmarks: SBM synthetic graphs Militarised Interstate Disputes US county migration

Metrics: running time bipartiteness ratio flow ratio

Baselines: LocBipartDC (MS) EvoCutDirected (ECD)

Builds on: higher-order dual Cheeger inequality local bipartite clustering (LocBipartDC) EvoCut directed local clustering

Closest papers by meaning

• Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs (NeurIPS 2021 · similarity 0.89)
• Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.88)
• A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.87)
• Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract) (AAAI 2024 · similarity 0.86)
• Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.86)
• Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.86)