Cluster-wise Graph Transformer with Dual-granularity Kernelized Attention

Summary

This paper proposed a novel attention method for graphs, focusing on different resolutions of nodes. Instead of attention calculation on the coarsened graph, it views the clustered nodes as sets, and calculates the attention between cluster and node level. Furthermore, it leverages the kernel method for more efficient attention calculation.

Strengths

- Overall, the writing is good and clear. - The methodology is clear, and the illustration is great. - The experiment results seem strong.

Weaknesses

- The only novelty is the dual granularity/resolution/hierarchy attention. The kernelization and the multi-kernel are already investigated. - The graph datasets in the experiments are small. Since the attention can be kernelized and is more efficient, there is no reason not to aim for larger graphs.

Questions

- How do you pick the number of clusters for metis algorithm? - What properties does the assignment matrix C hold? For example, do rows sum up to 1? - Intuitively I don't understand why the number of node queries is the same as the number of clusters, not number of nodes. In the illustration, why 3 qs not 9?

Rating

6

Confidence

4

Soundness

3

Presentation

4

Contribution

2

Limitations

As mentioned by the authors, the method relies on metis algorithm, which is not flexible enough. Ideally it should be compatible with any graph partitioning algorithms.

Summary

This paper considers graph transformers. In previous methods that consider cluster info, node clusters are pooled, which may lose node level information. This paper proposes node-to-cluster attention, where the nodes in the clusters are not compressed, and each cluster can interact with every node in other clusters. It proposed efficient formulation of node-to-cluster attention, and incorporated into the attention mechanism of a graph transformer. A comparison of the proposed method with existing benchmarks, both GCN and transformers, were conducted over 8 datasets, and the proposed method is shown to outperform.

Strengths

- Even though it is a complicated setup, the paper is well written and illustrated, and somewhat managed to get the setup across. - Experiment is comprehensive, with both GCN and graph transformer benchmarks, study of the necessity of combining cluster and node level info, and efficiency study. The performance seems good

Weaknesses

- Even though it may be unavoidable, the amount of notations make reading the paper somewhat difficult - Instead of using metis which is a partitioning algorithm, why not use a graph clustering algorithm? Is it because you like each partition to have an equal number of nodes?

Questions

- In addition to the node-to-cluster attention, should there also be cluster-to-node attention and cluster to cluster attention? - Figure 3: typo? “positinal”->”positional”

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

discussion in Appendix H.

Summary

The paper introduces the Node-to-Cluster Attention (N2C-Attn) mechanism, which captures both node and cluster-level information using multiple kernels. N2C-Attn can be implemented in the form of linear-time complexity by a cluster-wise message-passing framework. Based on N2C-Attn, the authors propose a Cluster-wise Graph Transformer (Cluster-GT), and demonstrate it outperforms baselines in graph-level benchmarks.

Strengths

This paper is easy to read, with a well-motivated and appropriately designed method to address the identified problem. Using kernelized attention effectively resolves the complexity issue associated with bi-level attention. The theoretical claim aligns well with the model's motivation and behavior. Extensive and diverse experiments demonstrate the model's superior performance and efficiency.

Weaknesses

- The paper emphasizes "without resorting to the graph coarsening pipeline," suggesting that the proposed method eliminates graph coarsening in their model pipeline. However, it actually employs a graph coarsening method (i.e., METIS). While it is true that the proposed method maintains clusters uncompressed, unlike traditional methods that typically coarsen each cluster into a single embedding, this statement might be misleading to readers. The authors should revise this expression to prevent any potential misunderstanding and avoid overselling the method. - I suggest authors discuss the existing research on GNNs with graph coarsening to capture broader structure information (e.g., higher-order structures or long-range dependencies). Representative models are listed below: 1. Fey, M., Yuen, J. G., & Weichert, F. (2020). Hierarchical inter-message passing for learning on molecular graphs. arXiv preprint arXiv:2006.12179. 1. Zhang, Z., Liu, Q., Hu, Q., & Lee, C. K. (2022). Hierarchical graph transformer with adaptive node sampling. Advances in Neural Information Processing Systems, 35, 21171-21183. 1. Liu, C., Zhan, Y., Ma, X., Ding, L., Tao, D., Wu, J., & Hu, W. (2023). Gapformer: Graph Transformer with Graph Pooling for Node Classification. In IJCAI (pp. 2196-2205). 1. Fu, D., Hua, Z., Xie, Y., Fang, J., Zhang, S., Sancak, K., ... & Long, B. (2024) VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections. In The Twelfth International Conference on Learning Representations. 1. Kim, D., & Oh, A. (2024) Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning. In Forty-first International Conference on Machine Learning.

Questions

- Can the authors rename RWSE to RWPE, following the original work?

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

The authors adequately addressed the limitations.

Summary

The paper proposes an attention-based methodology for supervised graph classification and regression. It adopts a pipeline similar to GraphViT, involving graph partition, cluster-wise representation learning, and aggregation. However, the core mechanism for learning cluster-wise representations is novel. Specifically, it introduces an inter-cluster attention and a cluster-to-node attention, using both attention maps to formulate the attention weights that aggregate node features into the query cluster's representation. This method is evaluated on eight graph classification/regression benchmarks, demonstrating promising results compared to the listed baselines.

Strengths

1. The paper presents a clear and well-supported motivation for the proposed methodology, with technical details that are thoroughly demonstrated. 2. The methodology is novel, and considering both the features of each node and the cluster it is affiliated with when calculating the attention weight is highly reasonable. 3. Experimental results demonstrate the effectiveness of the method. Additionally, the exploratory study on combination weights validates the significance of introducing the learnable bias of the affiliated cluster into the attention weights.

Weaknesses

1. The comparison with graph pooling methods misses MVPooL [1], a recent baseline that has achieved higher accuracy on these benchmarks. 2. Typo: the expression of the attention score between the $i$-th cluster and the $t$-th node in the $j$-th cluster should not contain the value $v_t$. 3. Suggestion: in Figure 2, combining Step 1 with Step 4 might provide a clearer illustration. Only with the presence of queries, keys, and values can the result of an attention operation be in the form of an aggregated representation; the result involving only keys and values is not well-defined. Additionally, combining Step 1 with Step 4 would better match the computation order of Equation 11. **Reference** [1] Zhang, Zhen, et al. "Hierarchical multi-view graph pooling with structure learning." IEEE Transactions on Knowledge and Data Engineering 35.1 (2021): 545-559.

Questions

1. Could the authors provide a heuristic explanation for why the cluster-level attention outperforms node-level attention on many benchmarks (as shown in Figure 5)? Cluster-level attention assigns the same weight to all nodes within a cluster, while node-level attention allows more flexible integration between cluster and node representations. It is not immediately clear why a more rigid approach would outperform a more flexible one.

Rating

7

Confidence

5

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Many thanks

Many thanks for your positive feedback. We are committed to further refining our work and making the necessary improvements to address any concerns. Thank you for the opportunity to enhance the quality of our research.