SFi-Former: Sparse Flow induced Attention for Graph Transformer

1. The paper is quite hard to read, the overall writing needs to be improved.
2. The new self-attention mechanism seems to be independent with graphs.
3. The experimental results are not convincing enough.

• Clarity and Expression: The paper’s presentation is hindered by complex and dense mathematical explanations, which may be difficult for readers to follow. Clearer explanations, diagrams, or more intuitive descriptions of the energy-based optimization and sparse attention would improve the paper’s accessibility.
• Comprehensive Analysis: The discussion of the model’s strengths and weaknesses is lacking. The paper should more thoroughly analyze the performance variations across different datasets and tasks, and provide insights into where the model excels and where it may fall short. This would provide a more balanced and holistic view of the contribution.
• Conclusion and Future Directions: The conclusion section is relatively brief and does not fully explore future research directions or practical applications. A more detailed discussion on the model’s potential use cases and limitations would strengthen the paper’s impact.

1. The motivation is not sufficiently justified. While the abstract highlights the method’s design to address “weak inductive bias, overfitting, and over-globalizing problems,” there is little follow-up or comprehensive experimentation to demonstrate these effects.
2. The authors argue that their model learns sparser attention scores. But how the l1-norm can induce sparse attention is not well-explained. It seems that the sparsity is archived by a simple "hard" threshold. There is no experiment is to show the sparsity of the learned attention scores either.
3. In Section 3.1, the authors model the attention with circuit. Thus, it is very confusing in Section 3.2 that the author introduce friction. Thus I challenge the motivation and interpretation behind the proposed method.
4. In Section 3.3, how to compute the SFi-Attn $\boldsymbol{Z}^{*} (\boldsymbol{R}^h(\boldsymbol{X}), \boldsymbol{F}^h(\boldsymbol{X}))$ is not clear.
5. The ablation study is only conducted on three datasets. The authors are encouraged to show ablation studies on all the datasets. Meanwhile, the components show significant improvements on some dataset, while show little improvements on other datasets. The authors are encouraged to analyze this result. Beside, the sensitivity test on hyper-parameters is not enough.
6. There some typos in the paper. For example, in the equation of the attention in line 147 and line 148, the query and key should be swapped.

Weaknesses:

1. The motivation is not sufficiently justified. While the abstract highlights the method’s design to address “weak inductive bias, overfitting, and over-globalizing problems,” there is little follow-up or comprehensive experimentation to demonstrate these effects. Although a subsection in the experiments discusses reducing overfitting, the gap of 20%-30% remains quite large, and the authors should explain this discrepancy.
2. The authors assert that their model learns sparser attention scores, yet no experiments (such as statistical analysis or case studies) are provided to verify this claim.
3. Section 3.2 is difficult to follow. The introduction of friction in the context of electric energy is confusing, and the purpose of the “Soft” function design is unclear.
4. Section 3.3 also lacks clarity. The roles of Z, R(X), F(X), and Z(R(X),F(X)) in attention, as well as the computation of this attention, are not adequately explained.
5. In Table 2, the proposed method underperforms a baseline across most datasets. The authors should clarify the factors behind these results and specify conditions where their method performs better. Without such insight, the effectiveness of the proposed approach is questionable.
6. There some typos in the paper. For example, in the equation of the attention in line 147 and line 148, the query and key should be swapped.

1. The paper suggests limited prior research on energy-based models in graph transformers; however, existing work such as DIFFormer [1] and SGFormer [2] has explored similar energy-constrained frameworks.

2. While the paper presents a theoretical explanation of its sparse attention mechanism, it omits consideration of the adjacency matrix and message-passing components in this framework. Many recent theoretical studies [1, 2, 3, 4] on GNNs and GTs employ energy-function-based models. Linking the proposed framework with established theoretical insights in this area would enhance the theoretical contribution.

3. An additional ablation test excluding the friction parameter, while maintaining sparse constraints on Z, would clarify its specific role. Additionally, the paper could benefit from further discussion on issues of weak inductive bias, overfitting, and over-globalizing within the experimental results.

4. The paper suggests that its sparse attention can replace attention modules in existing graph transformers. However, comparisons of model performance before and after substituting with sparse attention are currently not provided. It would also be beneficial to test if simple sparsity regularization techniques (e.g., L1, L2, or entropy regularization) on attention coefficients in existing models achieve similar gains.

5. The performance gains in the second experiment are minimal and within random variation, which may raise questions regarding the method’s effectiveness on GNN benchmark datasets.

6. Although the authors acknowledge that addressing GTs' computational bottleneck is beyond the scope, a brief analysis of the model's complexity and computational cost would be useful. This analysis would help assess the trade-offs between performance improvements and the associated computational overhead.

[1] Difformer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion, ICLR 2023.

[2] Simplifying and Empowering Transformers for Large-Graph Representations, NeurIPS 2023.

[3] Elastic Graph Neural Networks, ICML 2021.

[4] Interpreting and Unifying Graph Neural Networks with An Optimization Framework, WWW 2021.