Relieving the Over-Aggregating Effect in Graph Transformers

Thank you very much for your support and insightful suggestions that improved our manuscript. We hope our response can adequately address your concerns. The discussion will be added to the revision.

W1: Differences between over-smoothing and over-aggregating.

Response:

• Over-smoothing and over-aggregating have different influences on graph learning.
  • Over-smoothing indicates low-pass filtering among the locally connected nodes.
  • Over-aggregating indicates low-pass filtering among the query-key similar nodes.
  • For instance, consider a high-entropy case where a subset of nodes (set a) receives zero attention, and the rest (set b) are assigned uniform attention weights. In this case, the node representations are averaged over set b, leading to feature smoothing. However, if the nodes in set b are not adjacent in the input graph, the actual locally connected nodes will not be smoothed, and there will not be a low-pass filtering effect on the input graph.
• Solutions for over-smoothing cannot tackle over-aggregating. Designing high-pass filters can tackle over-smoothing. Conversely, even when a high-pass behavior is desired during over-aggregating, the optimization of attention weights may still be hindered by the overwhelming number of source nodes. One must tackle this issue regarding the input node volumes.
• L156-157. Thank you for pointing this out. The low-pass filtering in L157 refers to the local smoothing effect on the input graphs. To avoid confusion, we revised L157 as 'does not necessarily imply a low-pass filtering effect among the locally connected nodes as over-smoothing.'

W2&W3: The use of Algorithm 1 and ablation on the center selection methods.

Response: Thank you very much for enlightening us to discover a better center selection method!

• Algorithm 1 is applied to the target nodes before each attention-based aggregation during training, and thus, there will be different centers in different layers.
• To ensure computing efficiency, we did not apply the iterative clustering process in the Wideformer but only initiated the centers based on query features via a K-means++-like algorithm. The selection process is based on the node representations.
• Following your suggestions, we study whether applying clustering iterations will improve the performance.
  • Setting: We compare the simple initiating choice with (1) Multi-step iteration clustering and (2) directly modeling centers as parameters. The results are averaged on amazon-ratings, questions, CoauthorCS, and AmazonPhoto.
  • Results in Tab.R1 show that further applying clustering iterations can achieve better results, indicating the efficiency-performance trade-offs. We also discovered that directly modeling centers as parameters can address this trade-off, which does not require clustering iterations and achieves the best results.

W4: Results on larger graphs.

Response: Following your suggestion, we conducted experiments on ogbn-products and ogbn-proteins [R1] in Tab.R2. Results show that Wideformer can constantly benefit the backbones on these larger datasets (with more nodes or edges), further demonstrating its effectiveness.

W5 (Q): The use of $C$ in Alg.1.

Response: Thank you for bringing this to our attention.

• The 'update centers' step in algorithm 1 is a concatenation operation. Therefore, after the first concatenation, $C$ becomes a matrix.
• To avoid potential confusion, we revise the description of the algorithm by initiating $C$ as an all-zero $m\times d$ matrix and updating centers by assigning the $t$-th center to the $t$-th row. This ensures that $C$ is a matrix of the same shape throughout the algorithm.

[R1] Open Graph Benchmark: Datasets for Machine Learning on Graphs.

Thank you very much for your support and valuable suggestions that further broaden the potential application of our method to other tasks. We hope our response can adequately address your concerns. The discussion will be added to the revision.

Quality 1&Q1&Q2: More results for different tasks.

Response: We further evaluate backbones with Wideformer for graph classification on peptides-func [R1] and CIFAR10 [R2], and for graph regression on peptides-struct [R1] in Tab.R1. Results show that Wideformer can consistently benefit backbones on these tasks.

Quality 2&Q3-1: Statistical significance of gains.

Response: Thank you for your suggestion, which enables us to prove the significance of our performance gains statistically. We compute the performance gains between backbones with Wideformer and backbones only, and then compare the gains with zero. Paired t-tests on all backbones consistently give rise to p-values smaller than 0.05, and the confidence interval results do not contain 0, demonstrating the statistical significance of our gains.

Quality 3&Originality 2: Ablation on center selection methods.

Response: Thank you very much for enlightening us to discover a better center selection method!

• Setting: Following your suggestions, we studied the trade-off between computing efficiency and model performance. In the manuscript, to ensure computing efficiency, we did not apply the iterative clustering process in the Wideformer but only initiated the centers via a K-means++-like algorithm. Therefore, we only evaluated whether applying clustering iterations results in better performance during the rebuttal, instead of considering more complex clustering strategies. Specifically, we compare the simple initiating choice with (1) Multi-step iteration clustering and (2) directly modeling centers as parameters. The results are averaged on amazon-ratings, questions, CoauthorCS, and AmazonPhoto.
• Results in Tab.R2 show that further applying clustering iterations can achieve better results, indicating the efficiency-performance trade-offs. We also discovered that directly modeling centers as parameters can address this trade-off, which does not require clustering iterations and achieves the best results.

Clarity&Q3-2&Q4: Legend description, tiny fonts, and typos.

Response: Thank you for your suggestions. We fixed these problems in the revision by increasing the font size, correcting the typos, adding legend description to Fig.6 (The shape of the points indicates the model types, where '.' denotes the whole model and '*' denotes the Wideformer part. The color of the points indicates the number of the clusters $m$), and adding descriptions to Fig.4 (The informative source node ratio denotes the ratio of nodes assigned to the cluster with the highest attention score relative to the total number of graph nodes).

Significance 1: Comparison with sparse attention and cluster pooling.

Response: Thank you for your suggestions. We have added the discussion to the revision.

• Sparse attentions approximate fully-connected message passing via sparse connections. These methods shrink the receptive fields of the target nodes, which leads to sub-optimal message pathways for downstream tasks. In contrast, Wideformer maintains the global receptive field for target nodes. The importance of maintaining a global receptive field can be supported by the results in Tab.1-3, where combining global attentions with Wideformer gives rise to better performances than sparse attentions.
• Cluster pooling methods focus on learning hierarchical features of input graphs. They can collect global information by stacking multiple layers. In contrast, Wideformer can collect global information in a single layer, giving rise to shallow architectures for large graphs.

Significance 2: Performance on low-entropy scenario.

Response: Wideformer can also achieve statistically significant gains on small-scale graphs (Cora and Citeseer in Tab.3 in the original manuscript), which typically have lower attention entropy. This demonstrates the effectiveness of Wideformer across different node scales.

Originality 1: Comparison with uniform-attention phenomena.

Response: Our work differs from previous uniform-attention phenomena by providing

• Proof as a common issue: Different from the occasional observation of the uniform attention in previous works [R3], we discovered that uniform attention with high attention entropy consistently exists across different global graph attention methods in different datasets.
• Systematical study: We termed this phenomenon as over-aggregating, providing quantitative, theoretical root-cause, and influence analysis systematically.
• Effective solution: We also proposed Wideformer to tackle over-aggregating, which is tailored for large-scale graphs and achieves consistent performance gains for different backbones on different datasets.

Q5: Definition and example for over-smoothing.

Response: Thank you for your suggestion. We will rewrite this part with a concise definition and examples.

• Cause: Over-smoothing occurs when applying low-pass filtering to aggregate messages on the input graphs, such as the adjacent matrix with self-loops. In contrast, over-aggregating is caused by the large number of nodes blocking the optimization of the attention scores.
• Solution: Designing high-pass aggregating functions can tackle over-smoothing. Conversely, for over-aggregating on graph transformers, even when a high-pass behavior is desired, the optimization of attention weights may still be hindered by the overwhelming number of source nodes involved in aggregation. One must tackle this issue regarding the input node volumes.

[R1] Long Range Graph Benchmark. NeurIPS'22

[R2] Benchmarking Graph Neural Networks. JMLR'23

[R3] Scratching Visual Transformer's Back with Uniform Attention. ICCV'23

Thank you very much for your valuable suggestions that help us improve our paper. We hope our response can adequately address your concerns. The discussion will be added to the revision.

W1: Lower bound of the attention entropy.

Response:

• Tight lower bound of Theorem 3.1: We would like to clarify that Theorem 3.1 is not based on the trivial lower bound of 0, but a non-trivial, tighter lower bound derived in Appendix A. This bound increases with the number of aggregated nodes.
• Lower bound monotonicity: Theorem 3.1 characterizes the monotonicity of the attention entropy lower bound to the number of nodes, rather than the monotonicity of the actual learned attention entropy.
  • Regarding Fig.1(b): The overall trend of Fig.1(b) aligns with the theoretical prediction, where a higher lower bound makes it more likely for the learned attention scores to exhibit higher entropy given more aggregated nodes.
  • Regarding Line 126: We agree that the original phrasing may be misleading. We will revise the statement to “more likely to have higher entropy” to better reflect the theoretical prediction.

W2&Q1&Q2: Relation between attention entropy and model generalizability.

Response: Thank you for your suggestions, which help us to better understand the working mechanics of Wideformer.

• Reduction of attention entropy relates to better generalization
  • Regularizing entropy improves model performance: In Tab.S5 in the manuscript, we show that directly reducing the attention entropy during training can achieve better model performance.
  • Reduced entropy results in smaller generalization gap: We further analyze the performance gap between the training set and the test set with different weights on the entropy regularization term. Results are averaged on GraphGPS, SGFormer, and Polynormer across amazon-ratings, questions, AmazonPhoto, and CoauthorCS. Tab.R1 shows that reduced entropy can reduce the performance gap between training and inference. This confirms the positive relation between the reduction of attention entropy and better generalizability.
  • Attention entropy should be compared within the same architecture: Due to distinct design principles, different architectures inherently prioritize different attention patterns for optimal representation learning. While high attention entropy consistently indicates over-aggregating, the optimal entropy level varies across models. Thus, although Polynormer exhibits the most severe entropy reduction, this may still fall short of what is needed for its optimal performance, explaining why its gain is not superior to the other two.
• Statistical analysis demonstrates the significance of performance gains: Following the suggestions of reviewer j4ry, we compute the performance gains between backbones with Wideformer and backbones only, and then compare the gains with zero. Paired t-tests on all backbones consistently give rise to p-values smaller than 0.05, and the confidence interval results do not contain 0, demonstrating the statistical significance of our gains.

W3: Differences between Wideformer and previous clustering-based methods.

Response: The main difference between Wideformer and previous clustering-based methods is that Wideformer is tailored to tackle over-aggregating.

• Node division tailored for message dilution in over-aggregating:
  • Tackling over-aggregating requires distinguishing informative source nodes from less informative ones.
  • Selecting the truly informative sources for the targets requires the modeling of the source-target relations.
    • Previous methods fail by focusing solely on either target nodes (query) or source nodes (key).
    • We learn from the relation by selecting cluster centers among the targets and assigning source nodes based on their similarity to the target centers. This strategy enables effective discrimination of informative nodes while avoiding excessive computational overhead.
• Attention guiding tailored for uniform attention in over-aggregating: To enable target nodes focusing on the informative clusters, cluster aggregation results are further weighted with cluster attention.

Except for these model-level differences, we also showed in the manuscript that over-aggregating is a common issue across different global graph attention methods in different datasets, and systematically studied its root cause and influence with different numbers of nodes.

Q3: Information loss during the over-aggregating.

Response: The information loss refers to message dilution in over-aggregated attention, where signals from informative nodes are overwhelmed by noisy or irrelevant inputs.

• Quantitative measure: We can measure this loss by summing the attention scores assigned to informative nodes. Ideally, if all attention is allocated to the informative nodes, the sum equals 1. A sum < 1 indicates message dilution, i.e., some attention is "wasted" on uninformative nodes, leading to loss of useful information.
• Wideformer reduces information loss via aggregation division
  • Dividing the aggregation reduces the total number of nodes being aggregated.
  • Fewer nodes, better optimization: Based on the derivation in sec 3.2, fewer source nodes benefit the optimization of the attention scores.
  • Better optimization, more focused attention: The optimization empowers the target nodes to focus on the informative nodes, where informative nodes get larger attention scores and thereby reduce information loss.
• Reduced attention entropy demonstrates the reduced information loss: Reduced attention indicates that target nodes successfully select their informative source nodes and assign large attention scores to these nodes. Therefore, the sum of the attention scores assigned to informative nodes becomes large, demonstrating less information loss.

Thank you for your feedback! We are happy to provide further empirical results. Due to the memory overhead of explicitly computing the attention matrix during training, we can only choose small-scale datasets, including Cora, Citeseer, AmazonPhoto, and minesweeper.

Q1: Does 3~5 minimize the overall attention entropy?

Response: Thank you for your suggestions! Following your guidance, we compared the attention entropy of the models with different numbers of clusters. Average results across GraphGPS, SGFormer, and Polynormer are presented in Tab.R5. We can see that the minimal entropy values are gained in the 3~5 range.

Q2: Can you plot the attention entropy against the test performance during training on different types of datasets?

Response: Due to the strict prohibition on uploading figures during rebuttal, we present the training results of SGFormer with Wideformer in Tab.R6. Results show that the training process can reduce the entropy across different types of datasets.

Q3: Can you compare the entropy reg to SOTA sparse GAT methods with standard deviation? Is the reason behind the effectiveness of entropy reduction the concentration of attention on a small portion of nodes?

Response:

• Results in Tab.R7 show that entropy regularization can benefit backbones on these datasets. Exphormer and GAT are selected as the best-performing sparse methods. The best results among the three backbones GraphGPS, SGFormer, and Polynormer are reported due to character limitations.
• Why is entropy reg effective for benefiting backbones? Entropy regularization indeed helps target nodes to assign large attention scores to a small ratio of nodes. However, the better performance of the original global method compared to the sparse method shows that maintaining a global receptive field is also important. Therefore, we need to design a method that can both maintain global receptive fields for target nodes and reduce the volume of nodes for each aggregation.

Thanks.

Response to Q1: I apologize for the misleading counterexample (I did overlook the inter-cluster part). Let me rephrase. You mentioned in the penultimate comment that when m is around 35 the performance is good. Does 35 minimize the overall attention entropy? Can you plot the attention entropy against the test performance during training on different types of datasets? I wonder if that is a decreasing shape or not.

Response to Q2: I think experiments of entropy reg is acceptable. But the reg results seem marginal (on whatever dataset you pick). To evaluate the effectiveness of the reg, can you do several datasets with standard deviation? Moreover, can you also compare the entropy reg to SOTA sparse GAT methods? I ask for this since I think that the reason behind the effectiveness of entropy reduction is the concentration of attention to small portion of nodes.

Dear Reviewer,

We would like to provide an update regarding the implementation of your suggestions.

To address the out-of-memory (OOM) issue associated with the entropy regularization baseline, we developed a solution that divides the target nodes into mini-batches of size $b$. Each batch is sequentially processed on the GPU to compute attention scores with the source nodes. This approach reduces the peak memory overhead to $O(bn)$, enabling us to evaluate entropy regularization on most of the datasets in the paper (though the training time for large-scale graphs is significantly increased). Experiments on ogbn-arxiv and twitch-gamer encounter OOM even when setting b to 10.

The results are presented in Table R8. The best results among the three backbones, GraphGPS, SGFormer, and Polynormer, are reported due to character limitations. Full results will be included in the revision. We can see that entropy regularization improves performance on small-scale datasets (< 30k nodes), confirming that high attention entropy can hinder model performance. However, for larger graphs, the performance gains are marginal. This is consistent with our analysis in Section 3.2: since entropy regularization does not divide the aggregation process, aggregating over a large number of source nodes still suffers from optimization challenges.

Based on these results, the advantages of Wideformer over entropy regularization are summarized as follows:

• Lower memory overhead: Wideformer requires $O(nm)$ memory, where $m \ll n$. In contrast, entropy regularization incurs $O(n^2)$ memory, making it less scalable and forcing a trade-off between memory and time.
• Better mitigation of message dilution: Wideformer separates the aggregation into parallel processes. Each process only involves a small ratio of the source nodes to be aggregated, preventing the dilution of the key messages. In contrast, entropy regularization still aggregates over all source nodes, leading to attenuated optimization signals and the risk of over-aggregating on large graphs.

Thank you again for your valuable suggestions, which help us to provide a more comprehensive evaluation of our method and validate the necessity of the specific design. We will follow your suggestions to revise our manuscript and incorporate the results into the revision.

Thank you very much for your feedback. We are happy to have addressed most of your concerns. For your remaining two concerns:

Point 1: Employing entropy regularization results instead of Theorem 3.1 as a motivation for our proposed method. (L122-126)

Response: Thank you for your suggestions. Regarding entropy regularization results, we will add the results to the manuscript to show that over-aggregating with higher entropy does harm the model performance. This can be employed as direct evidence to complement the analysis in Sec 3.2.

While the entropy regularization results provide direct empirical evidence that high entropy can hurt performance, they do not reveal what factors cause the entropy to increase. We aim to provide a more complete picture by combining these results with Theorem 3.1 and Sec 3.2, which highlights the relationship among entropy, the number of aggregated nodes, and the attenuated optimization process.

Regarding Theorem 3.1, we understand that placing Theorem 3.1 early in the paper (L122–126) may have created the impression that it serves as a direct motivation. We will revise this part to clarify that Theorem 3.1 only provides a theoretical insight into why attention entropy tends to increase with the number of aggregated nodes, complementing the empirical findings in Fig.1(b). The actual architectural design of Wideformer to reduce the number of nodes being aggregated is motivated by the analytical insights in Sec 3.2.

Point 2: Employing entropy regularization on larger datasets.

Response: We have attempted to apply entropy regularization to the remaining datasets, but encountered out-of-memory issues due to its $O(n^2)$ memory cost. Such memory overhead, along with the relatively marginal gains, suggest that entropy regularization is not a viable solution. In contrast, Wideformer achieves more substantial improvements while avoiding quadratic memory overhead.

Thank you again for your patient guidance throughout the process. We sincerely appreciate your time and your valuable suggestions.

We greatly appreciate your valuable suggestions that help us revise our manuscript, and hope our response can adequately address your concerns. The discussion will be added to the revision.

W1: Differences between over-aggregating and over-squashing/smoothing/dilution.

Response: Thank you for bringing over-dilution to our attention. We would like to confirm that our understanding is correct, that the reviewer is referring to the over-dilution discussed in [R1]. If this is not the case, we kindly ask the reviewer to clarify. We have added the differences between over-dilution and over-aggregating to the existing discussion in sec 3.3.

• Over-smoothing
  • Different graph structures: Over-smoothing occurs on the input graph structures, while over-aggregating occurs on the attention graph.
  • Different causes: Over-smoothing stems from the low-pass filtering of the aggregation function, while over-aggregating is caused by the attention optimization issue when the number of source nodes becomes large.
  • Different solution: Designing high-pass filters can tackle over-smoothing. Conversely, even when a high-pass behavior is desired during over-aggregating, the optimization of attention weights may still be hindered by the overwhelming number of source nodes. One must tackle this issue regarding the input node volumes.
• Over-squashing
  • Different causes: Over-squashing stems from the imbalance between the volumes of a node’s input and output messages, whereas over-aggregating is only associated with its input volume.
  • For instance, consider an attention matrix where edge weights are uniformly distributed across the fully-connected attention graph.
    • This case reflects the most severe form of over-aggregating, where the attention entropy reaches its maximum (i.e., logn).
    • Over-squashing does not arise where each node in such a graph has perfectly balanced input and output volumes.
• Over-dilution
  • Intra-node dilution focuses on the volumes of the node features, while over-aggregating focuses on the volumes of the input nodes.
  • Inter-node dilution focuses on whether a node's own information is preserved during aggregation, whereas over-aggregating emphasizes the preservation of messages from the informative nodes, regardless of whether that includes the node itself.

W2: Runtime and memory cost.

Response: Thank you for your suggestion. Based on our analysis of model complexity (sec 5.3.2) and cluster ablation (sec 5.3.3), Wideformer results in

• Efficiency-accuracy trade-off regarding the number of clusters $m$.
  • Wideformer time/space complexity: T+$O(nm)$. T is the complexity of the backbone, and $n$ is the number of graph nodes.
  • A larger $m$ value ($m\le8$) gives rise to higher accuracy, but increases the memory and runtime costs linearly.
• Affordable increase in time and memory cost: Fig. 7 shows that Wideformer achieves the largest gains with a small number of clusters $m$ in {3, 4, 5}. The average cost increase ratio (calculated as [cost(m=4)-cost(m=1)]/cost(m=1)) across different numbers of graph nodes is presented in Tab.R1. We can see that the additional costs are relatively minor, amounting to only ~30% of the original time cost and less than 11% of the memory cost.

W3: Differences with previous works.

Response: Thank you very much for bringing these interesting works to us. The major differences between our work and previous works are that,

• Novel phenomenon: We discovered the novel over-aggregating phenomenon as a common issue across different global graph attention methods in different datasets, and systematically studied its root cause and influence with different numbers of nodes.
• Novel solution: To specifically mitigate over-aggregating, we propose Wideformer as a plug-and-play solution, including
  • Node division tailored for message dilution in over-aggregating:
    • Tackling over-aggregating requires distinguishing informative source nodes from less informative ones.
    • Selecting the truly informative sources for the targets requires the modeling of the source-target relations.
      • Previous methods fail by focusing solely on either target nodes (query) or source nodes (key).
      • We learn from the relation by selecting cluster centers among the targets and assigning source nodes based on their similarity to the target centers. This strategy enables effective discrimination of informative nodes while avoiding excessive computational overhead.
  • Attention guiding tailored for uniform attention in over-aggregating: To enable target nodes focusing on the informative clusters, cluster aggregation results are further weighted with cluster attention.
• Effective solution: Wideformer can effectively tackle the over-aggregating effect, while previous work cannot. (Indicated in Tab. R1 and R2)

Specifically to the works you mentioned in the review, the differences can be summarized as:

• [1][4] validate the prerequisite of our work: These works and other sparse attention methods prove the prerequisite of our work, that not all source nodes are informative to the target nodes. As a result, large attention entropy in graph transformers leads to indiscriminate aggregation and information loss.
  • Why not sparse attention? Wideformer maintains the global receptive field for target nodes, while sparse attention shrinks the receptive fields, leading to sub-optimal message pathways for downstream tasks. This is supported by the results in Tab.1-3, where global attentions with Wideformer give rise to better performances than sparse attentions.
• [2][3] study other issues in attention: [2] reformulates the weight matrix to tackle the training instability of transformers with lower attention entropy, and [3] decomposes the transformer forward pass into an ensemble of successive attention heads to tackle the attention collapsing.
• [6] cannot be applied to graph transformers: [6] requires explicitly computing the whole attention matrix, which demands a space complexity of $O(n^2)$ and is not scalable to large graphs.
• [5] cannot effectively address over-aggregating:
  • Methodology:
    • Awareness of source-target relation: [5] clusters the source nodes based on their own features, while Wideformer clusters nodes based on the source-target relation, which better enables the selection of the informative sources for the targets.
    • Finer-level aggregation: [5] only applies attention aggregation at the cluster level, while Wideformer also applies attention aggregation at the node level within each cluster. Node-level aggregation allows the model to adjust the attention scores at a finer level and capture the node feature distribution within each cluster.
  • Experiment:
    • We implemented ENACT [5] in graph transformers by directly clustering source nodes based on their own features, and only applying cluster-level attention aggregation.
    • By comparing Wideformer with ENACT in terms of the resulting attention entropy (Tab.R2) and node classification performance (Tab.R3), we can see that ENACT cannot effectively tackle over-aggregating and gains worse performance than Wideformer. This demonstrates the effectiveness of our method in tackling over-aggregating and benefiting backbone performance.

[R1] Understanding and Tackling Over-Dilution in Graph Neural Networks. KDD'25