acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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%.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Face Clustering

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_LTy4OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

In my view, the main contribution of this paper is to establish a new state of the art method, DiGSA, a more efficient and differentiable attention framework for large-scale face clustering, primarily improving upon Diff-Cluster, with fewer parameters, better performance, and faster inference. Although the proposed design is sufficiently clever and technically well-motivated, I believe its broader impact on the field is relatively limited. The authors provide enough evidence for readers to gain a reasonable understanding of the effectiveness of the proposed method. However, the empirical presentation is relatively conservative, with limited additional analysis or visualization to further demonstrate why and how the individual components are effective.

From my personal perspective, I would have preferred a more systematic discussion and evaluation of the proposed design. For example, beyond the current ablations, it would be helpful to provide a more thorough sensitivity analysis of key design choices, clearer qualitative visualizations showing how the proposed components affect the learned graph or attention structure, and a more explicit discussion of failure cases and the conditions under which each component is expected to be beneficial. Such analyses would make the empirical contribution more convincing and provide deeper insights beyond the reported performance gains.

Critical strengths

One clear strength is that the methodological motivation is coherent. Each design choice directly targets a specific limitation of Diff-Cluster: hard Top-K masking is replaced with differentiable sparsity, while sequence-oriented positional encoding is replaced with graph-aware structural encoding.

Another positive aspect is that the paper improves accuracy, efficiency, and model size simultaneously. DiGSA achieves slightly better results than Diff-Cluster across all five MS1M scales while using fewer parameters and less computation.

The paper also includes reasonable component-level ablations for DASA, GSDA, GraphPE, and the learnable temperature, which helps verify that the proposed components contribute positively to the final performance.

In addition, the appendix contains several useful supplementary analyses, including run-to-run stability, the roles of the primary and secondary GSDA maps, controlled similarity perturbation, and cross-dataset / cross-architecture transfer.

Critical weaknesses

The main concern is not the empirical performance, as the proposed method achieves state-of-the-art results while substantially reducing computational cost and model complexity. In fact, obtaining comparable or better accuracy with fewer parameters, lower FLOPs, and higher throughput is one of the strongest aspects of this work.

My main concern instead lies in the degree of conceptual novelty and the depth of the analysis. The proposed framework is carefully designed, but several of its key ingredients are built upon established techniques: DASA relies on entmax-based sparse normalization with a learnable temperature, while GraphPE uses degree statistics and random-walk positional encodings. GSDA provides a more task-specific contribution, but the overall framework can still be viewed as a well-engineered integration and adaptation of existing ideas to improve Diff-Cluster.

Therefore, while the empirical contribution is strong, I find the methodological contribution relatively incremental. The paper demonstrates that the proposed design is effective, but provides relatively limited insight into why these components are particularly suitable for face clustering beyond the specific baseline being improved.

I would also have preferred a more systematic analysis of the proposed components. For example, the paper could further investigate the learned sparsity patterns and per-head temperatures in DASA, the sensitivity to KNN graph density or subgraph size, and the conditions under which GSDA provides the largest benefit. Such analyses would help establish broader insights beyond the reported efficiency and accuracy improvements.

Questions for authors

DiGSA is largely built upon Diff-Cluster, which itself adopts the differential attention mechanism from Differential Transformer. One aspect I am particularly interested in is the system-level efficiency and deployment implications of retaining differential attention as the core design.

My understanding is that differential attention requires computing two attention distributions and subsequently subtracting them. While efficient implementations such as FlashAttention are possible for Differential Transformer, this computation does not necessarily map as directly to the standard single-attention SDPA execution path, and its practical efficiency may depend substantially on the underlying kernel implementation and hardware backend. Therefore, parameter count, FLOPs, and even isolated model latency may not fully characterize the actual deployment efficiency. In other words, lower FLOPs or lower measured latency does not necessarily imply proportionally better end-to-end deployment efficiency.

This is particularly relevant here because the paper emphasizes efficiency improvements over Diff-Cluster through reductions in parameters, FLOPs, latency, and increased throughput, while the reported measurements mainly characterize the relation model itself.

I would therefore like to better understand the authors' principled rationale for building DiGSA around differential attention. In particular:

  1. Is differential attention fundamentally necessary for face clustering, or could the proposed graph-structured sparsity and graph-aware biases be incorporated into a conventional single-attention formulation with potentially simpler deployment?
  2. What practical trade-offs does differential attention introduce in terms of memory traffic, kernel fusion, peak memory usage, and compatibility with commonly used optimized attention backends?
  3. Have the authors considered or benchmarked end-to-end deployment efficiency across different hardware (it is optional if the rebuttal period is limited for authors) or attention backends, rather than relying primarily on parameters, FLOPs, and model-level latency?
  4. If my understanding regarding the implementation or deployment limitations of differential attention is inaccurate, I would appreciate clarification on how these issues are handled in the current implementation.

This is probably the question I am most interested in regarding the paper. A convincing explanation of why differential attention is essential here, together with evidence that its system-level costs are properly addressed, would substantially strengthen my view of the work, and I would consider increasing my score. Otherwise, I would likely maintain my current rating and would not recommend acceptance.

3 comments

We sincerely thank you for your recognition of our work and for your valuable time and constructive comments. We fully agree with you that the practical efficiency of a model may depend heavily on the underlying kernel implementation and hardware backend, and that the number of parameters and FLOPs may not fully reflect real-world deployment efficiency. Following your suggestions, we have conducted additional experiments to answer your questions and address your concerns. We hope our responses will resolve your concerns.

  1. Is differential attention fundamentally necessary for face clustering, or could the proposed graph-structured sparsity and graph-aware biases be incorporated into a conventional single-attention formulation with potentially simpler deployment?

Thank you for this fundamental and insightful question. Differential attention is indeed necessary for our task, as verified by the following ablation study:

MethodAttentionFPFBNMI
Diff-ClusterSingle Attention94.2592.7398.05
Diff-ClusterDiff Attention95.0593.5998.30
DiGSASingle Attention94.4393.0298.18
DiGSADiff Attention95.6094.1498.46

As shown in the table, replacing differential attention with a conventional single-attention formulation consistently degrades the performance of both methods: for Diff-Cluster, FP/FB/NMI drop from 95.05/93.59/98.30 to 94.25/92.73/98.05; for our DiGSA, they drop from 95.60/94.14/98.46 to 94.43/93.02/98.18 (-1.17 FP, -1.12 FB, -0.28 NMI). The consistent results on both Diff-Cluster and DiGSA demonstrate that the differential mechanism, which subtracts the secondary attention map from the primary one to separate same-community evidence from cross-community noise, is the fundamental source of the performance gains rather than an incidental benefit of a specific implementation. Differential attention is therefore necessary.

Moreover, as shown in the last two rows of the table in Response 2, after kernel-level optimization the latency gap between Single Attention (3.94 ms) and Diff Attention (4.15 ms) is less than 0.3 ms on an A6000 GPU, while Diff Attention brings significant performance gains, making it clearly more cost-effective. In Response 3, we also conducted experiments on a Samsung Galaxy Z Fold 8 (5.50 ms vs. 5.74 ms), and the conclusion is identical to that on the A6000 GPU.

  1. What practical trade-offs does differential attention introduce in terms of memory traffic, kernel fusion, peak memory usage, and compatibility with commonly used optimized attention backends?

Thank you for this question, your observation on deployment details is very accurate. Compatibility with existing optimized attention backends is indeed problematic for our method: FlashAttention supports neither the adjacency-guided biases (+βhA+\beta_h A and −γhA-\gamma_h A) in GSDA nor entmax (α=1.5); AdaSplash supports entmax (α=1.5) but not the adjacency-guided biases in GSDA. Since neither FlashAttention nor AdaSplash supports the adjacency-guided biases, we first attempted to solve this problem with PyTorch's FlexAttention: FlexAttention allows modifying every attention score, and the adjacency-guided biases are exactly additive correction terms on each score, so we injected the bias into FlexAttention's callback in the form of "score + coefficient × bias". Since all 16 attention heads share the same adjacency matrix and differ only in their per-head coefficients, we pass "one matrix + 16 coefficients" instead of replicating the matrix 16 times, thereby avoiding extra memory overhead. However, when addressing the support for entmax (α=1.5), we found that FlexAttention does not support it either. To thoroughly resolve both problems, we wrote a dedicated Triton kernel from scratch, which fuses bias injection, entmax normalization, and the differential subtraction into a single pass, avoiding explicit materialization of intermediate attention maps and thus reducing peak memory usage and memory traffic.

The experimental results are summarized in the table below (batch size = 32, NVIDIA A6000)

KernelMethodbs=32 Latencybs=32 Throughput
PyTorchDiff-Cluster (Top-k softmax, diff attention)26.01 ms1,230/s
PyTorchOur DiGSA (entmax α=1.5, w/ bias, diff attention)12.80 ms2,500/s
FlashAttentionOur DiGSA (softmax, w/o bias, diff attention)3.84 ms8,328/s
AdaSplashOur DiGSA (entmax α=1.5, w/o bias, diff attention)5.21 ms6,137/s
FlexAttentionOur DiGSA (softmax, w/ bias, diff attention)4.65 ms6,884/s
Our Triton kernelOur DiGSA (entmax α=1.5, w/o bias, diff attention)3.97 ms8,068/s
Our Triton kernelOur DiGSA (entmax α=1.5, w/ bias, diff attention)4.15 ms7,714/s
Our Triton kernelOur DiGSA (entmax α=1.5, w/ bias, single attention)3.94 ms8,119/s

As shown in the table: Diff-Cluster suffers from a high inference latency of 26.01 ms due to its MoE and Top-K operations, whereas the PyTorch implementation of our DiGSA takes only 12.80 ms, a 2.03× speedup; our Triton kernel further reduces the latency to 4.15 ms, a 3.08× speedup over the PyTorch baseline (12.80 ms), raising the throughput from 2,500/s to 7,714/s; this latency is comparable to FlashAttention (3.84 ms), which supports neither bias nor entmax, and is faster than AdaSplash (5.21 ms) and FlexAttention (4.65 ms). In summary, the system-level overhead introduced by differential attention can be effectively eliminated through kernel-level optimization, and our method achieves high practical deployment efficiency.

  1. Have the authors considered or benchmarked end-to-end deployment efficiency across different hardware (it is optional if the rebuttal period is limited for authors) or attention backends, rather than relying primarily on parameters, FLOPs, and model-level latency?

Thank you for your suggestion. Since DiGSA adopts exactly the same KNN graph construction method and clustering algorithm as Diff-Cluster, with the only difference lying in the node-relation prediction network, we focus our comparison on the inference speed of the relation prediction network across different hardware. It is worth noting that face clustering is a fundamental application in mobile photo albums (e.g., the face grouping feature on Samsung smartphones), so on-device deployment efficiency is of direct practical value. Following your suggestion, we not only benchmarked the inference latency of different kernels but also conducted on-device tests on a Samsung Galaxy Z Fold 8:

PlatformMethodAvg. LatencyPeak Memory
Samsung Z Fold 8Diff-Cluster (diff attention)216.82 ms93.99 MB
Samsung Z Fold 8Our DiGSA (diff attention)5.74 ms86.91 MB
Samsung Z Fold 8Our DiGSA (single attention)5.50 ms84.23 MB

As shown, on the mobile device Diff Attention (5.74 ms) and Single Attention (5.50 ms) have nearly identical inference times, whereas Diff-Cluster requires 216.82 ms, while our method achieves a 37.8× speedup with lower peak memory (86.91 MB vs. 93.99 MB). This further confirms that our DiGSAdifferential attenti introduces almost no additional overhead in real-world deployment.

  1. If my understanding regarding the implementation or deployment limitations of differential attention is inaccurate, I would appreciate clarification on how these issues are handled in the current implementation.

Thank you for your patience and your careful attention to implementation details. We hope our Responses 1–3 have clarified how these implementation and deployment limitations are handled in our current implementation. In brief: (i) the incompatibility with existing attention backends has been fully resolved by our dedicated Triton kernel; (ii) after optimization, differential attention runs at nearly the same latency as single attention. If you have any further questions or concerns, please feel free to let us know, because your suggestions are highly valuable to us.

  1. This is probably the question I am most interested in regarding the paper. A convincing explanation of why differential attention is essential here, together with evidence that its system-level costs are properly addressed, would substantially strengthen my view of the work, and I would consider increasing my score. Otherwise, I would likely maintain my current rating and would not recommend acceptance.

Thank you for focusing on this core question, which is indeed central to our work. Regarding "why differential attention is essential": as shown in Response 1, for both Diff-Cluster and our DiGSA, differential attention consistently and significantly outperforms single attention, demonstrating that the differential mechanism, which subtracts the secondary attention map from the primary one to cancel cross-community noise, is the fundamental source of the performance gains. Regarding "evidence that its system-level costs are properly addressed": as shown in Responses 2 and 3, with our dedicated Triton kernel, the inference latency of Diff Attention is nearly identical to that of Single Attention (4.15 ms vs. 3.94 ms on the A6000; 5.74 ms vs. 5.50 ms on the Z Fold 8), reaching a speed comparable to FlashAttention while consuming less memory. In summary, differential attention delivers consistent performance gains at almost no additional system cost, and the two goals are achieved simultaneously. We hope the above experimental evidence and explanations can address your concerns, and we would be grateful if you would take them into account in your evaluation. Thank you again for your valuable comments!

Reviewer_rPDVOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary
  • Large-scale face image clustering is one of the fundamental problems in face recognition. This paper conducts an in-depth investigation into large-scale face image clustering and identifies two weaknesses remaining in Diff-Cluster, the current state-of-the-art clustering method: non-differentiable discrete support selection that blocks gradient flow, and sequence-centric positional encodings that fail to capture local graph topology. To address both bottlenecks, this paper proposes Differentiable Adaptive Sparse Attention (DASA). DASA replaces hard Top-K heuristics with continuous entmax sparse distributions, and injects degree and multi-hop random-walk encodings into queries and keys. Meanwhile, it applies opposite adjacency-guided biases to the primary and secondary attention maps, encouraging the subtraction operation to separate same-community evidence from cross-community noise.
  • The paper presents detailed analysis and proofs for the two proposed modules, with solid theoretical evidence and sound arguments.
  • Furthermore, the effectiveness of the proposed method is verified on multiple datasets. In particular, the results in Table 1 sufficiently demonstrate the superiority of your approach.
Critical strengths
  1. The proposed method resolves the non-differentiable issue present in Diff-Cluster, representing a significant technical advance.
  2. The paper is well-structured overall, and the method section is written with exceptional clarity and readability.
  3. Experimental results in Table 1 verify the improvements brought by the proposed method, showing consistent gains across all reported metrics. The supplementary experiments are also clearly presented.
Critical weaknesses
  1. In Section 4.1, there is no description of face embedding details. Face embeddings serve as base data and can affect clustering results. The lack of explanations about face embeddings may hinder readers’ understanding of this work.
  2. As mentioned above, face embeddings have an impact on clustering performance. I recommend the authors add further discussions or additional experiments regarding face embeddings.
  3. In Section 4.2, the authors analyze the advantages of their method over classical approaches. Since these classical baselines are relatively weak, this analysis may not be necessary.
Questions for authors

to see above weaknesses

2 comments

We sincerely thank you for your thorough review, positive evaluation, and recognition of our work. Below, we provide our detailed responses to your questions and present new experimental results conducted according to your insightful suggestions.

  1. In Section 4.1, there is no description of face embedding details. Face embeddings serve as base data and can affect clustering results. The lack of explanations about face embeddings may hinder readers’ understanding of this work.

Thank you very much for this important suggestion. We fully agree that the choice of face embeddings plays a fundamental role in face clustering and that clearly documenting their source is essential for reproducibility.

To ensure a fair and consistent comparison with existing face clustering methods, we followed the established benchmark protocol and adopted the face embeddings provided by LTC (Yang et al., 2019), which have been widely used in prior face clustering studies. This allows us to evaluate improvements attributable to our proposed clustering framework while keeping the input representations consistent with previous methods.

Following your helpful suggestion, we will revise Section 4.1 to explicitly clarify the source of the face embeddings and their role in our experimental setup. We sincerely appreciate you for bringing this omission to our attention.

  1. As mentioned above, face embeddings have an impact on clustering performance. I recommend the authors add further discussions or additional experiments regarding face embeddings.

We sincerely appreciate your insightful suggestion and fully agree that the quality of face embeddings can substantially influence clustering performance. Motivated by your valuable suggestion, we have conducted additional experiments using two face recognition models from InsightFace: buffalo_l (ResNet50) and buffalo_s (MobileFaceNet). These models provide face representations with different levels of discriminative capability, allowing us to investigate the robustness and effectiveness of DiGSA across different embedding qualities.

For comparison, we evaluate both direct Infomap clustering (Rosvall et al., 2009) and DiGSA-enhanced Infomap clustering using the same embeddings. The additional results are summarized below.

Face EmbeddingsMethodFPFBNMI
buffalo_l (ResNet50)Infomap96.7196.0698.97
buffalo_l (ResNet50)DiGSA + Infomap99.0498.6499.67
buffalo_s (MobileFaceNet)Infomap91.3489.7297.40
buffalo_s (MobileFaceNet)DiGSA + Infomap97.1796.6099.07
LTC (ResNet50) (Yang et al., 2019)Infomap93.9892.4098.00
LTC (ResNet50) (Yang et al., 2019)DiGSA + Infomap95.6094.1498.46

The additional results demonstrate that face embedding quality significantly influences clustering performance, with buffalo_l achieving better results than buffalo_s. More importantly, DiGSA consistently improves FP, FB, and NMI across all three embedding configurations, demonstrating its effectiveness with different face representations. Notably, DiGSA combined with buffalo_l achieves an FP of 99.04, substantially outperforming the 95.60 obtained with the original benchmark embeddings. We sincerely appreciate your valuable suggestion, which has helped us strengthen our experimental evaluation.

  1. In Section 4.2, the authors analyze the advantages of their method over classical approaches. Since these classical baselines are relatively weak, this analysis may not be necessary.

We couldn't agree more with you. We will follow your suggestion to reduce the comparative analysis with classical baselines and add the comparison and analysis of recent works.

Thank you very much for your clarification. My concerns have been resolved.

Reviewer_cjEDOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3(+1)
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This paper studies relation modeling for large-scale face clustering. It proposes DiGSA, which replaces the attention core of a sparse differential clustering model with two components. Differentiable Adaptive Sparse Attention (DASA) uses entmax-1.5 with learnable per-head temperatures instead of hard Top-K truncation. Graph-Structured Differential Attention (GSDA) incorporates degree statistics and random-walk return probabilities into queries and keys, while applying oppositely signed adjacency biases to the two differential attention maps. Experiments cover five MS1M evaluation scales, MSMT17, and plug-in evaluations on MS1M and DeepFashion. The paper reports modest accuracy improvements over Diff-Cluster together with reductions in parameters, FLOPs, and inference latency.

Critical strengths
  1. A practically relevant accuracy–efficiency trade-off. DiGSA improves Pairwise F-score over Diff-Cluster at all five MS1M scales, with gains of 0.14–0.38 percentage points, while BCubed F-score is approximately maintained or slightly improved. The reported reductions of approximately 14% in parameters, 33% in FLOPs, and 29% in latency could be consequential for large-scale clustering. Although the accuracy gains are modest, achieving them with lower computational cost would constitute a useful contribution.

  2. Reasonable component-level validation and evaluation breadth. Experiments examine the main modules, normalization choices, learnable temperature, positional encoding, and adjacency bias. Additional evaluations include three random seeds, MSMT17, and integration into a second clustering framework. These experiments support the usefulness of the overall design and several constituent choices, even though they do not fully establish the proposed mechanisms.

Critical weaknesses
  1. The novelty and contribution boundaries could be clarified. Adaptive sparse attention and graph-informed attention biases have been explored in prior work. The paper would benefit from more explicit ablations and comparisons showing the specific contribution of each component and the practical advantage of their combination over related approaches.

  2. Under-validated graph-bias mechanism. The claim that graph information acts only as a soft and recoverable constraint is plausible, but erroneous graph edges may still be amplified by positive structural biases. Controlled graph-corruption experiments and ablations of same-sign versus opposite-sign biases are needed to support this argument.

  3. Some efficiency and analytical claims require clarification. The reported speedups are not fully attributed to sparse computation, removal of the MoE structure, or other implementation choices. The paper should clarify whether sparse kernels and graph-construction costs are included. In addition, the interpretation of the equal P/S attention-mass ratio and the claims about gradient recovery under entmax need more precise justification.

Questions for authors

What specific advantage does DiGSA provide over existing adaptive sparse attention and graph-aware attention methods? Please include controlled ablations or comparisons that isolate the contribution of each component.

How robust is DiGSA to incorrect or missing graph edges? Could you report graph-corruption experiments and compare same-sign versus opposite-sign structural biases?

How are the reported efficiency gains measured? Please clarify the contribution of sparse computation, MoE removal, graph construction, and entmax, and precisely define the P/S attention-mass ratio and gradient-recovery claim.

The paper provides limited discussion and comparison with several key face-clustering baselines, including NASA (Learn to Cluster Faces with Better Subgraphs, ICASSP 2024), Confidence-GCN (Face Clustering via Graph Convolutional Networks with Confidence Edges, ICCV 2023), and MoCo-ANA (MoCo-Like Adaptive Neighbor Aggregation for Face Clustering, PRICAI 2025). How does DiGSA differ from these methods, and can the authors report a controlled comparison under the same experimental protocol?

6 comments

We sincerely thank you for your careful review and for the positive assessment of our accuracy-efficiency trade-off and component-level validation. Following your suggestions, we have conducted additional controlled experiments, and we provide more precise definitions of the efficiency measurement protocol, the P/S attention-mass ratio, and the gradient-recovery mechanism. Point-by-point responses follow.

  1. What specific advantage does DiGSA provide over existing adaptive sparse attention and graph-aware attention methods? Please include controlled ablations or comparisons that isolate the contribution of each component.

We sincerely thank you for this insightful and constructive suggestion. We fully agree that adaptive sparse attention and graph-aware attention have both been extensively explored. We would like to clarify that DiGSA's contribution is not proposing either technique in isolation, but unifying them in a complementary design that addresses the structural limitations of Diff-Cluster for noisy face clustering: (i) To address the non-differentiable hard Top-K mask of Diff-Cluster, whose boundary decisions cannot be corrected by gradients, DASA implements adaptive sparse attention via entmax-1.5 without a fixed support size, making support selection itself part of the optimized objective; (ii) To address that Diff-Cluster's two attention maps share the same Top-K mask and thus lack any role division, GSDA applies oppositely signed adjacency biases (+β_h A and -γ_h A) to the two maps, guiding them to learn complementary structural evidence, so that the subtraction retains differential evidence while canceling the common-mode structural response; (iii) To address that Diff-Cluster applies RoPE to arbitrarily ordered KNN neighbor lists and thus cannot encode graph topology, GraphPE encodes the graph structure with degree and random-walk statistics; (iv) This unified design also simplifies the multi-branch MoE structure, which Diff-Cluster introduces to hedge boundary misclassifications, into a single sparse attention branch, reducing parameters by 14% and FLOPs by 33% (Table 5). The efficiency gains are verified on both GPU and mobile devices: on NVIDIA A6000, Diff-Cluster takes 26.01 ms per batch, whereas our optimized DiGSA takes only 4.15 ms with the dedicated Triton kernel, a 6.3× speedup; on a Samsung Galaxy Z Fold 8 mobile device, Diff-Cluster takes 216.82 ms, whereas DiGSA takes only 5.74 ms, a 37.8× speedup:

PlatformDiff-ClusterDiGSASpeedup
NVIDIA A6000 (bs=32)26.01 ms4.15 ms6.3×
Samsung Galaxy Z Fold 8 (bs=1)216.82 ms5.74 ms37.8×

Compared with existing methods, this unified design differs in two essential ways: (i) existing adaptive sparse attention methods (e.g., entmax) only learn a sparse attention distribution, whose support selection is unaware of the graph topology, and standard entmax uses a fixed global temperature that places all heads in the same sparsity regime; DiGSA's learnable per-head temperature adapts the sparsity of each head to the graph structure, and the support selection is directly guided by the adjacency biases, which is directly visible in the ablation table: fixed-temperature entmax-1.5 reaches only 95.46 FP (#8), whereas the learnable per-head temperature raises it to 95.60 (#9, +0.14). (ii) Existing graph-aware attention methods (e.g., Graph Transformers with structural encodings) only inject structural information as additional inputs into the attention computation, so structural and content responses are entangled and cannot be separated; DiGSA instead turns the structural bias into a differential quantity: the oppositely signed biases on the primary and secondary maps make the common-mode structural response explicitly canceled by the subtraction, so that only differential evidence contributes to the final relation prediction, which is also confirmed by the ablation table: without any adjacency bias the FP is 95.55 (#4), applying only the primary or only the secondary bias brings no gain (95.54/95.55, not exceeding #4), and only the oppositely signed pair raises it to 95.58 (#7), showing that structural biases translate into gains only when they exist as a differential pair. To our knowledge, no prior work realizes such an integrated, differentiable design of "adaptive support selection + topology-guided denoising" within a single differential attention core.

The ablations in the paper already provide initial validation of each module: removing DASA drops FP from 95.60 to 95.50, and removing GSDA drops it to 95.55 (Table 2); learnable-temperature entmax-1.5 outperforms the fixed-temperature variant (95.60 vs. 95.48, Table 3); GraphPE improves FP over RoPE (95.57 vs. 95.55), and adding adjacency biases further raises it to 95.60 (Table 4).

Beyond these single-component ablations, to further isolate the standalone contribution of each component, we conducted a cumulative controlled experiment that starts from the Diff Transformer and adds one component at a time (identical protocol: LTC embeddings, K=80 KNN, same clustering backend, MS1M 584K):

#ConfigurationFPFB
1Diff Transformer (no DASA, no GSDA, no GraphPE)95.5094.04
2+ DegreePE95.5594.11
3+ RandomWalkPE95.5594.10
4+ DegreePE + RandomWalkPE95.5594.12
5+ DegreePE + RandomWalkPE + attn_primary bias only (+βhA+β_h A)95.5494.07
6+ DegreePE + RandomWalkPE + attn_secondary bias only (−γhA-γ_h A)95.5594.08
7+ DegreePE + RandomWalkPE + attn_primary + attn_secondary biases (full GSDA)95.5894.12
8+ DegreePE + RandomWalkPE + attn_primary + attn_secondary biases + DASA (entmax-1.5, fixed temperature)95.4694.05
9+ DegreePE + RandomWalkPE + attn_primary + attn_secondary biases + DASA (entmax-1.5, learnable temperature), i.e., full DiGSA95.6094.14

The results reveal three findings: (i) GraphPE is effective: adding degree and random-walk encodings on top of the Diff Transformer raises FP from 95.50 to 95.55 (#1→#4); (ii) opposite-sign complementarity is a prerequisite for GSDA: applying only the primary bias (#5) or only the secondary bias (#6) yields no gain (95.54/95.55, not exceeding #4 without biases), and only the oppositely signed pair (#7) raises FP to 95.58, showing that differential denoising relies on the role division between the two maps rather than on the bias itself; (iii) the learnable temperature is necessary for DASA to take effect: fixed-temperature entmax (#8, 95.46) even falls below #7 without DASA (95.58), whereas the learnable per-head temperature (#9) achieves the best 95.60/94.14 overall, indicating that the sparsity regime must adapt to the graph structure. Moreover, the boundary-error diagnostics in the paper show that DiGSA retains 2–4× more within-identity active entries and recovers same-identity support truncated by hard Top-K, directly quantifying the standalone contribution of differentiable support selection at the edge level. We will include this ablation table and an explicit comparison with related sparse/graph attention methods in the revision.

  1. How robust is DiGSA to incorrect or missing graph edges? Could you report graph-corruption experiments and compare same-sign versus opposite-sign structural biases?

Thank you for pointing out this key experimental gap, it is the most direct test of the graph-bias mechanism. The controlled similarity-perturbation experiment in Appendix B.3 of the paper (Figure 3) already provides partial evidence: on MS1M 584K, when 0–40% of the relation-matrix entries are randomly selected and their similarities are increased before renormalization, DiGSA remains above Diff-Cluster and the Vanilla Transformer on FP/FB/NMI at every perturbation ratio, and stays stable at the 40% ratio (FP 95.70), while the Vanilla Transformer drops from 94.93 to 94.20. However, this experiment is not sufficient to fully address your question: (i) the intervention increases the similarities of randomly selected entries before renormalization, which may also strengthen some same-identity relations, so it is not a pure false-positive-edge injection and does not cover missing edges (false negatives), the paper explicitly states this limitation; (ii) it does not include the same-sign versus opposite-sign comparison of structural biases. We therefore conducted the following targeted experiments.

Experimental setup. On the candidate KNN graph of MS1M 584K (K=80, following the paper's protocol), we designed two edge-level corruptions that simulate "incorrect edges" and "missing edges" respectively: (i) Rewire, which replaces the neighbor with a new node uniformly sampled from all N nodes (resampling if the node itself is drawn), and recomputes the inner-product distance of the new edge with the features to keep the graph internally consistent, simulating cross-identity false-positive edges; (ii) Delete, which replaces the neighbor with the node itself (a self-loop), which is skipped during clustering and is thus equivalent to an invalidated neighbor slot, simulating same-identity false-negative edges. Each corruption is applied to 10%/20%/30%/40% of the candidate edges. Under the same settings we compare (a) same-sign biases on both attention maps (+βhA+β_h A and +γhA+γ_h A) and (b) +βhA+β_h A on the primary map and −γhA-γ_h A on the secondary map (opposite-sign, our method). Results on MS1M 584K (Pairwise F-score):

Noiseopposite-signsame-sign
0% (clean)95.6095.51
rewire 10%94.9994.87
rewire 20%93.8293.62
rewire 30%92.1391.93
rewire 40%90.1589.94
delete 10%95.5695.42
delete 20%95.2195.11
delete 30%94.7294.59
delete 40%94.1393.96

The results support three conclusions: (i) DiGSA is highly robust to missing edges: even with 40% of the neighbor slots deleted, the opposite-sign FP only drops from 95.60 to 94.13 (-1.47 points); (ii) incorrect edges have a larger impact but remain controllable: at 40% rewiring the FP drops to 90.15 (-5.45 points), indicating that cross-identity false-positive edges do inject misleading information, yet the degradation is smooth without collapse; (iii) opposite-sign consistently outperforms same-sign under every condition, and the advantage widens as corruption increases (+0.09 on the clean graph, +0.21 at 40% rewire, +0.17 at 40% delete), verifying that oppositely signed biases cancel the common-mode structural response in the subtraction.

Mechanistically, opposite-sign biases turn the structural bias into a common-mode component: an erroneous edge receives opposite biases in the two maps, so the subtraction cancels the shared structural response and only differential evidence survives; with same-sign biases, bias-dominated components survive the subtraction and may even be amplified, making erroneous edges more prone to reinforcement by positive structural biases. This is consistent with the P/S asymmetry analysis in Table 8 of the paper. Two further clarifications address the concern that erroneous edges might be amplified: (i) the structural bias does not directly determine edge participation: entmax's exact-zero probabilities guarantee that out-of-support edges never contribute to value aggregation, and the bias only indirectly affects support selection through the scores; (ii) the differential subtraction further suppresses the common-mode structural response, so erroneous edges are not unboundedly amplified. We will add these experiments and the analysis to the revision.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.