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 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 Iteratively Re-weighted (IRW) optimization scheme that linearizes the objective and solves each subproblem via a Double-Bounded Optimal Transport (DB-OT) solver based on the 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.