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

Spectral clustering, a widely-used technique for graph-based data partitioning, faces a severe computational bottleneck due to its $O(n^{3})$ time complexity. While anchor-based approximations reduce the complexity to $O(nm^{2})$ ($m \ll n$), they often yield degenerate solutions 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. Our model simultaneously promotes cohesive clusters and enforces soft lower and upper bounds on cluster sizes, thus avoiding trivial or highly unbalanced partitions. To solve the resulting non-convex optimization problem efficiently, we develop an \textbf{Iteratively Re-weighted (IRW)} optimization scheme, which sequentially linearizes the objective and solves each subproblem via a \textbf{Double-Bounded Optimal Transport (DB-OT)} solver based on the \textbf{Sinkhorn--Knopp} algorithm. This approach guarantees convergence while maintaining scalability. Extensive experiments on benchmark datasets demonstrate that SC-FAGC consistently achieves state-of-the-art performance in terms of accuracy, purity, and recall, while strictly satisfying the prescribed cluster-size constraints. Thus the proposed method offers a principled and scalable solution for large-scale graph clustering with controllable partition structure.