DiGSA: Differentiable Graph-Structured Sparse Attention for Large-Scale Face Clustering

Large-scale face clustering relies on -nearest-neighbor (KNN) graphs that are corrupted by false-positive (FP) edges linking visually similar yet distinct identities, as well as false-negative (FN) disconnections that fragment single identities. The strongest existing denoising method, Diff-Cluster, subtracts attention distributions and applies hard Top- masks, but this design introduces two structural bottlenecks: non-differentiable discrete support selection that blocks gradient flow and necessitates multi-branch mixture-of-experts (MoE) compensation, and sequence-centric positional encodings that fail to capture local graph topology. To address both bottlenecks, we present DiGSA, a Differentiable Graph-Structured Sparse Attention framework comprising two coupled modules. For the first bottleneck, Differentiable Adaptive Sparse Attention (DASA) replaces hard Top- heuristics with continuous entmax sparse distributions controlled by learnable per-head temperature, making support selection score-adaptive and piecewise differentiable while consolidating multi-branch MoE routing into a single branch. For the second, Graph-Structured Differential Attention (GSDA) injects degree and multi-hop random-walk encodings into queries and keys while applying opposite adjacency-guided biases to the primary and secondary attention maps, encouraging the subtraction to separate same-community evidence from cross-community noise. Across MS1M (584K–5.21M faces), MSMT17, and DeepFashion, DiGSA matches or consistently exceeds the strongest sparse differential baseline, while consolidating the multi-branch mixture-of-experts into a single branch that reduces parameters by 14% and FLOPs by 33%.