SC-FAGC: Size Constrained Fast Anchor-based Graph Clustering

Spectral clustering is hindered by its $O(n^{3})$ time complexity, and although anchor-based approximations reduce this to $O(nm^{2})$ ($m \ll n$), they often yield degenerate or unbalanced partitions in the absence of explicit cluster-size control. To address this limitation, we propose \textbf{SC-FAGC (Size-Constrained Fast Anchor Graph Clustering)}, a unified formulation that integrates entropy regularization and bilateral cardinality constraints within an anchor-based spectral clustering framework, enforcing user-specified lower and upper bounds on anchor-level cluster sizes to avoid trivial or highly unbalanced solutions. To solve the resulting non-convex problem efficiently, we develop an \textbf{Iteratively Re-weighted (IRW)} optimization scheme that linearizes the objective and solves each subproblem via a \textbf{Double-Bounded Optimal Transport (DB-OT)} solver based on the \textbf{Sinkhorn--Knopp} algorithm, guaranteeing convergence while maintaining scalability. Extensive experiments on benchmark datasets demonstrate that SC-FAGC consistently achieves state-of-the-art performance across six standard clustering metrics while strictly enforcing the prescribed anchor-level constraints. Moreover, it induces effective data-level size control after label transmission, offering a principled and scalable solution for large-scale graph clustering with controllable partition structure.

Grouping data points into meaningful clusters is a core task in data analysis, with applications ranging from image organization to document categorization. A well-known approach called spectral clustering delivers high-quality groupings by exploiting the geometric structure of data, but it becomes prohibitively slow as the dataset grows large. Existing fast approximations address the speed problem by working on a small set of representative points, yet they frequently produce severely unbalanced groups—for instance, one giant cluster containing almost all the data and several nearly empty ones—which limits their practical utility. This paper introduces SC-FAGC, a method that retains the speed advantage of these approximations while explicitly preventing unbalanced outcomes. The key idea is to let the user specify acceptable minimum and maximum group sizes, and then build those requirements directly into the clustering process. To solve the resulting optimization problem efficiently, we develop an iterative algorithm that breaks the problem into a sequence of simpler subproblems, each solved using a fast transport-based routine. The size control applied at the representative-point level naturally propagates to the full dataset after cluster assignments are determined. Experiments across a broad range of benchmark datasets show that SC-FAGC consistently matches or surpasses existing methods in clustering quality while reliably respecting the prescribed size constraints, making it a practical and principled tool for large-scale data grouping.