Cluster-wise Graph Transformer with Dual-granularity Kernelized Attention
Authors: Siyuan Huang
Yunchong Song
Jiayue Zhou
Zhouhan Lin
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Graph Based Learning
Primary area: graph_neural_networks
TL;DR: We introduce the Cluster-wise Graph Transformer (Cluster-GT) with a novel Node-to-Cluster Attention (N2C-Attn) mechanism, utilizing a dual-granularity kernel to capture information at both node and cluster levels.

Abstract: In the realm of graph learning, there is a category of methods that conceptualize graphs as hierarchical structures, utilizing node clustering to capture broader structural information. While generally effective, these methods often rely on a fixed graph coarsening routine, leading to overly homogeneous cluster representations and loss of node-level information. In this paper, we envision the graph as a network of interconnected node sets without compressing each cluster into a single embedding. To enable effective information transfer among these node sets, we propose the Node-to-Cluster Attention (N2C-Attn) mechanism. N2C-Attn incorporates techniques from Multiple Kernel Learning into the kernelized attention framework, effectively capturing information at both node and cluster levels. We then devise an efficient form for N2C-Attn using the cluster-wise message-passing framework, achieving linear time complexity. We further analyze how N2C-Attn combines bi-level feature maps of queries and keys, demonstrating its capability to merge dual-granularity information. The resulting architecture, Cluster-wise Graph Transformer (Cluster-GT), which uses node clusters as tokens and employs our proposed N2C-Attn module, shows superior performance on various graph-level tasks. Code is available at https://github.com/LUMIA-Group/Cluster-wise-Graph-Transformer.

Cluster-wise Graph Transformer with Dual-granularity Kernelized Attention
Siyuan Huang 1.2
Yunchong Song' Jiayue Zhou?
Zhouhan Lin'+
LUMIA Lab, Shanghai Jiao Tong University
Paris Elite Institute of Technology, Shanghai Jiao Tong University
siyuan_huang, jj tu@outlook.... ycaonges edu.
lin. www.zhhhhan@ggaii.comm
Abstract
In the realm of graph learning, there is a category of methods that conceptual- ize graphs as hierarchical structures, utilizing node clustering to capture broader structural information. While generally effective, these methods often rely on a fixed graph coarsening routine, leading to overly homogeneous cluster repre- sentations and loss of node-level information. In this paper, we envision the graph as a network of interconnected node sets without compressing each clus- ter into a single embedding. To enable effective information transfer among these node sets, we propose the Mode-to-Cluster Attention (N2C-Attn) mecha- nism. N2C-Attn incorporates techniques from Multiple Kernel Learning into the kernelized attention framework, effectively capturing information at both node and cluster levels. We then devise an efficient form for N2C-Attn using the cluster-wise message-passing framework, achieving linear time complexity. We further analyze how N2C-Attn combines bi-level feature maps of queries and keys, demonstrating its capability merge tual-granularity information. The resulting architecture, Cluster-wise Graph Transformer (Cluster-Gi) which uses node clusters tokens and employs our proposed N2C-Attn module, shows su- perior performance on various graph-level tasks. Code is available at https: h//ggcabb.ccomm/MMMA-a--aaoa http://oooo/OMMAAArrrrr/////CCC
wise-wweeeee-e----- Graph- Teaph-Transformet
Introduction
Graph learning represents a rapidly evolving field. Techniques like Graph Neural Networks (GNNs) and Graph Transformers (GT) demonstrate impressive performance across range of tasks [27
36
55
such as social networks 339 37), time series [22 30 traffic flow [54 6 and drug discovery [15
45 These methods enhance performance by promoting message propagation at the node level and
calculating attention between node pairs, thereby concentrating on node-level interactions.
Recent advancements have extended beyond node-level message propagation, adopting approaches that treat the graph as hierarchical structure [53 20]. capturing information multiple levels of the graph [55). For instance, node clustering pooling segments the graph into multiple clusters [17] [50]. Each cluster is then independently pooled, preserving the structural information of the hierarchical graph. Drawing inspiration from Vision Transformers 7 Graph VIT [8] treats subgraphs as tokens and computes attention among them, which enables the model capture long-distance dependencies and reduces the overall computational complexity compared to node-level Graph Transformers.
However, existing methods based node clustering rely fixed graph coarsening routine [32] This routine involves partitioning the graph into several clusters and subsequently pooling each cluster into a single node to generate coarsened version of the original graph. While generally
'Zhouhan Lin is the corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

effective, research has shown that compressing each cluster into a single embedding can lead to overly uniform cluster representations, which may not accurately reflect the diversity within each cluster [34] Furthermore, these methods typically simplify the interactions between clusters to basic vertex-level interactions on the coarsened graph. This oversimplification overlooks the rich node-level information contained within each cluster, thereby limiting the potential for richer cluster-wise interactions.
In this work, we propose a different strategy for enhancing cluster-wise interaction. Instead of reducing each cluster to single node through coarsening, we envision the graph as a network of interconnected node sets. To enable message propagation among these node sets, we develop a method termed Mode-to-Cluster Attention (N2C-Attn). N2C-Attn incorporates techniques from Multiple Kernel Learning (MKL) [16] into the kernelized attention framework [46]. By combining kernels at two different granularity levels, N2C-Attn effectively captures hierarchical graph structural information at the cluster level while also preserving node-level details within each cluster.
We propose treating the graph as interconnected node clusters without coarsening, which inherently increases computational complexity. To mitigate this issue, we employ the technique of kernelized softmax (24) to reduce the computational complexity to linear. Consequently, the computation process of N2C-Attn can be viewed a cluster-wise message propagation: each cluster gathers internal keys and values, then propagates them along weighted edges to the queries of other clusters.
We present a further amalysis of how N2C-Attn synthesizes new queries and keys by merging inputs from both node and cluster levels. We consider two scenarios: 1) using the product of kernels and 2) using the convex sum of kernels. The former implicitly conducts tensor product of the feature maps from both the node-level and cluster-level queries (and keys), adopting this product as the new query (or key) for N2C-Attn. The latter concatenates node and cluster-level feature maps with learnable weights, maintaining their independence and allowing the model to adjust their relative significance. We also demonstrate that cluster-level attention can be regarded special case of N2C-Attn.
Our resulting architecture, Cluster-wise Graph Transformer (Cluster-GT), leverages our proposed N2C-Attn module in conjunction with simple graph partitioning algorithm, Metis (23]. We conduct extensive evaluations of Cluster-GT across eight graph-level datasets, varying in size and domain. Cluster-GT outperforms existing Graph Transformers and graph pooling methods that employ more intricate graph partitioning algorithms, which highlights the effectiveness of enhancing inter-cluster interactions and preserving information both granular levels. We further analyze the relative weights of the combined kernel, finding that Cluster-GiT pays more attention to cluster-level information when handling graphs in the social network domain compared to graphs in the biological domain.
2 Background
Consider a graph G represented by the multi-tuple (N, E, X, A). N denotes the set of n nodes, denotes the set of m edges. X E Rnxd is the feature matrix and A E Raax the adjacency matrix. We use the superscript P to indicate the cluster-level (coarsened) graph: (AP, ,.P,, XP, PP)). where APP represents clusters of nodes, and 8 denotes the edges connecting these clusters.
Node Clustering Pooling and Cluster Assignment Matrix Node clustering pooling captures hierarchical structural information by partitioning and iteratively coarsening the graph to smaller This process involves two main steps. Initially, Cluster Assignment Matrix (CAM) C E R is generated using carefully designed strategy, where n represents the number of original nodes, and m indicates the number of clusters. Once the Cluster Assignment Matrix is obtained, it is used to perform graph coarsening, i.e., pooling each cluster into single node:
size
32
1 33
x x²=: CT
(I)
where x xg and A" E pmmxm are the new node features and adjacency matrix, defining the post-coarsening graph structure. C.ý thus represents the weight of the s-th node in the j-th cluster.
Beyond node clustering pooling, methods exist that leverage node clusters to enhance graph atten- tion [8 3 GiT [8] utilizes Metis (23 to partition the graph into multiple subgraphs. It then applies mean pooling to each subgraph, treating the pooled clusters as tokens for further attention computation. Despite promising results, GraphViT still adheres to the graph coarsening pipeline, which leads to overly similar cluster representations (34 and the loss of node-level information.

---

Generalized Self-attention and Kernelized Softmax attention mechanism through the lens of kernel methods 446
Numerous studies suggest reevaluating the
24 The generalized formulation of self-attention utilizes non-negative kernel function ((:;-) Rd x RR4 - R+, which can be represented with a corresponding feature map d. The self-attention mechanism can expressed as:
k(q, kg)) 2 r(g, kig.)
Attn(X); Σ
2/
where kj, 9t. and oy are the corresponding keys, queries, and values. By expressing k with feature map k(g,, kg) <(g:)² ((k)))((()) the computation simplifies to:
Φ(q:) E (kt)
Attn(X), (():) プソ= (k₂)
(3)
where the sums Σÿ- (k and Σ ok;))² )T shared across all nodes and need to be computed only once, thus reducing computational complexity to ((N) (2]). Various choices of feature maps are shown effective, such as the RBF kernel [6 and Positive Random Features [5]
Multiple Kernel Learning The selection of an optimal kernel function k(t,)) :) is critical for en- hancing the performance of kernel-based learning methods. Multiple Kernel Learning (MKL) methods [56 44] leverage combination of kernel functions to integrate various features from different perspectives. The resultant kernel, Kag mathematically defined as:
Key ((x")MMM Jm=1 my m==))= fn(ttm (x"", "xs".." )
where fy AR R can be cither a linear nonlinear function. Each Km P.. P. R is RR=,, with Dm representing the dimensionality of each feature. There are various strategies for combining kernels, which represent a dynamic area of research. [6]
valid kernel for vectors x , E
In this work, we concentrate on the pairwise scenario, where M = 2. We note the two input spaces as X' and X". For constructing pairwise kernels when elements of each pair belong to different input spaces, we select two fundamental strategies: the tensor product of kernels and the convex linear combination of kernels, which are commonly used on the product space X' X'.
Given two kernels K1 X x X + and K2 X" x 2" TR, the tensor product method defined as:
Kig ((x,, (v. v/)) Ki (x. y) Ka(a",
where (x, x'), (y. 3/) are pairs of objects from X X² While the convex linear combination method is defined as:
(,, (u v)) ( v) - 8xz(2' ,y')
(6)
where a; B 2 and a + = 1. a and 3 are coefficients that balance the contribution of each kernel.
3 Node-to-Cluster Attention
In this section, present the Node-to-Cluste Attention (N2C-Attn) mechanism. We begin in Section[..]bb defining the concept of N2C-Attn. We then proceed to Section [32, where we devise an efficient form of N2C-Attn with the message-passing framework. In Section 3.3 we re-examine N2C-Attn, focusing on the integration of feature maps of queries and keys across two granularities.
3.1 Definition of Node-to-Cluster Attention
Node-to-Cluster Attention marks departure from the graph coarsening pipeline that typically coarsens each cluster into a single embedding. Instead, as shown in Figure 1] we maintain the clusters uncompressed and use N2C-Attn to propagate messages among the inter-connected node clusters. The definition of N2C-Attn based on the Cluster Assignment Matrix C, which can be obtained through various graph partitioning methods [32]. N2C-Attn focuses on the "post-clustering" phase.

---

Input Graph A)
Node Clustering
cluxtaring
Graph Conmeninng Pipatoe
X C
GNN Graph Transfomer...
Choke Auaggronn
Graph Cowrsening Pipaline:
Our method!
Apprcaimotely homogenous uster rop esoriaatoos
firegranne
Method:
Adaptive level node- (suboection
View the grazh or interoonncceed nodo sets
Chuslerwis atraioon Node An Cluster Attention
complesliyy
(Q.vai)
(Qbval
NzC-Attn(X)
Bi-tevel Q K
Clusteniivel Al:
Node-evel Rty
(Kg.h (Kg (Kiii))
L AC E, A
clusders
Qu, Qu, 4b
9t. 9b-43
Eg (R
Kaype of modlee
K,, Ky, Kg
As, No, As. Ar.
where Kig in bidecol
Xx
[Gsvaol
(ag (Rg
Figure 1: Definition of Node-to- to-Cluster Attention (N2C-Attn). N2C-Attn perceives the graph as interconnected node sets instead of coarsening each cluster into a single node. integrates multiple kernel learning methods into the kernelized attention framework facilitate message propagation among node clusters, simultaneously capturing both the node-level and cluster-level information.
Bi-level Query and Key A key observation is that after node clustering, each node possesses two tiers of information: 1) individual node feature and 2) the collective feature of its cluster. effective attention mechanism needs to accommodate these two distinct levels of information. Thus, the 1-th node in the j-th cluster is characterized by a bi-level pair of keys: {K,, k,) Xo x XN:
k = Wahe, Ky = W' Coplis
(7)
where h2 is the feature the t-th node. h E XN is the node-level key, which solely derived from the embedding of f-th node, and K₃ E Xc represents the cluster-level key, which depends on all nodes within the j-th cluster. Wa and W'. are two different projections to X' and X', respectively.
Since we are considering the attention between clusters and nodes, each cluster needs to provide a corresponding bi-level query. Thus, the i-th cluster is characterized by bi-level pair of queries:
9: W. Σ CCsth)) Q. = W. C
(8)
where Qs denotes the cluster-level query, qi denotes the node-level query. W. o and W two different projections to X'y and X', respectively. The bi-level query is thus {Q q E de Xx.
Note that we use uppercase letters to represent cluster-level queries and keys, e.g. (Q:, Ký). and lowercase letters to represent node-level queries and keys, e.g., (4,, ).
General Definition of Node-to-Cluster Attention Having obtained the bi-level queries and keys, we consider how use kernels to measure their similarity. We denote valid kernel in the cluster- level space Ae as ric, and a valid kernel in the node-level space N'x as KN. We now consider how to construct kernel Kg on the tensor product space Xe x XN. KB stands for Bi-level kernel.
Given {Qu, ). the bi-level query for the i-th node cluster, and {Ky, k2 ). the bi-level key for the t-th node in the j-th node cluster, the general Node-to- Node-to-Cluster Cluster Attention for the i-th cluster is defined as:
E, E, CyyKE((Q 4.), kc)) N2C-Attn(X): Σ, E, CiyKC (1Q., 4). (Ky,ke)
Equation 9 depicts the process of the i-th cluster gathering information from nodes of all con- nected clusters. The attention score between the i-th cluster and the 1-th node in the j-th cluster is A. (, Σ, A., I, (G)ea((Q.a)))
Kn plays a pivotal role in integrating information across cluster and node levels. described in Section 2 we mainly consider two options for Kip: the tensor product method and the linear combination method. Next, we introduce these two different implementations.

---

Step oviiyy
Stap ofpe")
Stop d: Brer
Step of wiea"
waal
Uk
epprosate)
sacrdnng bulle Choike foo pereni
Cade ta rronege peosage on snang choker
and bage Gata Stap
hop on vintur will our waar.
Hlel" E, K.) D, CuplAdo
(())" (e(Q...)) E, Gustkl
Win) L, K. E. Cattiin Waal Me L. CaNEE)
Plail Σ, K.l E, Cyliklnn
Cuplk)
#ay E, Rj (ua(k)
Viel A. L Cupth)
An efficient implementation of N2t-Attn-T with the message- framework. |N'I| denotes the number of clusters and | denotes the number of edges between clusters. The com- putation can be decomposed into 4 steps: 1) aggregation of node-level keys and values within each cluster, 2) computation of gate each edge with the cluster-level kernel, 3) message propagation among clusters, 4) dot product of aggregated value with the node-level query of each cluster.
Figure 2:
Mode-to-Clusted Attention with Tensor Product of Kernels (N2C-Attn-T) Equation 5 we can define the bi-level kernel KB as:
With the help of
KB (fQi, v)), (K,, nc (Qi, K2)NNNN(KNNN ( k2)
(10)
We can thus rewrite the Node-to- Cluustrrrrrrrrrree Attention defined in Equation 9 as:
N2C-Attn-T(X), A E, Cijiic Kj) (gs: ke) E, E, CyjNo( K2) (gts ki)
(11)
N2C-Attn- -T stands for Node-to-Cluster Attention with Tensor Product of Kernels. By performing the product between Kic and KN. this construction enables interaction across all dimensions of the feature vectors different granular levels, thereby capturing the dependencies within the combined feature space. We offer a more detailed explanation in in|subeection 3.3
Mode-to-Cluster Attention with Convex Linear Combination of Kernels (N2C-Attn-I.)
With
the help of Equation 6. also define the bi-level kernel KB as:
KB(iQi, 7. {K5, ke }) = (Q Ky) + BEx (g;, kt)
(12)
where 3 2 0 are learnable parameters and a + 3 = 1. We can thus rewrite Equation 9 as:
N2C-Attn-L(X); E, A E. (ani K2) + Bay kz) Σj A E. (aj(ar (Q;, K₃) + 3.N k.))
(13)
N2C-Attn-L stands for Node-to-Cluster Attention with Convex Linear Combination of Kernels. By combining the kernels Ky and KN with coefficients a and B, this construction allows for flexible integration of the similarities measured in Xe and Xx, letting the combined kernel adaptively scale the influence of the cluster-level and node-level information on the overall similarity measure.
3.2 Efficient Implementation of Node-to-Cluster Attention
N2C-Attn requires the computation of similarity between queries and keys at two different levels of granularity. Normally, this necessitates a computational complexity of ((NN))V))) where [W] denotes the number of nodes and I denotes the number of clusters. To speed up this process, we devise a linear algorithm using the feature map and the message- subsection, focus on the efficient implementation of N2C-Att-T. Following similar method, can also develop an efficient implementation for N2C-Aut-LL which detailed in AAppnddxx A
framework. In this
To accelerate Eqquation 11 key observation is that kg is correlated to the edges between clusters, serving as the gates on the edges. While KN involves queries of clusters and keys of nodes. Therefore, propose separating the node-level and cluster-level computation of KN. and then turning the computation of N2C-Attn-T into a cluster-wise message propagation. We represent KN using the corresponding feature map: KN (g;, kz) ('(g)) T (Az). Thus, Equation 11 can be rewritten as:
N2C-Aun-T(X)): v(a:)* E3 Af (0 A Qu, K2) E. C.jeb(ke)uz "(gh)² Σ, Af (Q,
(14)
(Q,, K,) Cepb((k))
5

---

With|Equation 14 we observe that the computation of N2C-Attn-T can be encompassed within the message-passinng framework. Figure showws the complete process, which contains four steps: 1) aggregating node-level keys and values within each cluster, 2) calculating the gate on each edge using the cluster-level kernel, 3) propagating messages among clusters, and 4) computing the dot product of the aggregated value with the node-level query for each cluster. N2C-Attn-T can thus be seen as form of cluster-wise message propagation. Each cluster acts as a sender, propagating the packaged keys and values of its internal nodes; it also acts as a receiver, using its own query to interpret the information from the received keys and values. The overall time complexity is thus reduced to linear.
3.3 Equivalent Feature Maps of Bi-level Kernels
In this subsection, we delve into how the toicstte- Attention mechanism integrates information across cluster and node levels through the lens of feature maps. We note @B as the feature map of Kg: KB ( (fQi, ), {K &e) } = ( (Qii. 9: }), BB ( KK ke))) where (:--) represents the inner product in the corresponding feature space. [Equation 9 caa thus be expressed as:
N2C-Attn(X); = Σ, A, E, (B)( 9.)), PD (B(( Ke) Σ, A E. Ci (on (:) (n([ kx)
(15)
LB (Qi, q:) represents the feature vector of the newly formulated bi-level query, while D (K,, ke) rep- resents the feature vector of the newly formulated bi-level key. We are interested in their relationship with the original queries and keys {Qi, qt Kj, k.). We establish the following relationships:
If kcc (Qi Kj) = (o())), o(₃)) and KN ky k2) = (v(a)) (ke)), where & and vi are feature maps for the respective kernels, then the Node-to- to--to---CCrrrr Attention with the tensor product kernel implies the following equivalent feature map:
Proposition 1
(BQ,,, )) ((Q.) @ ((g)); &B((K,,ki)) o(K)) & (ki)
(16)
where & represents the outer product of the node-level and cluster-level feattrr feature maps. Conversely, the Node-to-Clann Cluutt---rrrr-tt Attention with the convex sum implies the following equivalent feature map:
BB(1Qr, va)(Q.) @ (Bbl(.); DD((K,, ke)) Vab(K;) @ BBb(k)
(17)
where @ represents the concatenation of the weighted node-level and cluster-level featerr feature maps.
This proposition provides an intuitive understanding of N2C-Attn: by integrating queries and keys from both node-level and cluster-level, N2C-Attn synthesizes new queries and keys enriched with bi-level information. Specifically, using the product of kernels, as detailed in Equation 16, N2C-Attn- T implicitly performs a tensor product between the feature maps of the node-level query (key) and the cluster-level query (key), and finally using the product the new query (key). This resulting equivalent feature map thus extends into a higher-dimensionn bi-level information. It's worth noting that we do not need to actually compute the tensor product between the cluster-level and node-level queries or keys, which requires high spatial complexity.
space, offering a feature fusion of
While employing the convex sum of kernels, as detailed in Equation 17 can be regarded as concatenation of the feature maps of the original node-level and cluster-level queries (keys), appending learnable weights. This approach preserves the independence of queries (keys) different levels, empowering the model to adjust their relative significance. Besides, we can leverage this point to design an efficient implementation method for N2C-Attn-L. We introduce it in detail in Anpppeddix A
We offer further analysis by comparing the assigned attention scores between N2C-Attn and previous cluster-level attention methods. We prove that the attention mechanism used in Graph ViT (18), which based on the graph coarsening pipeline and serves as cluster-level attention mechanism, can be seen as special case of our proposed N2C-Attn. More details can be found in Appendix B
4 Cluster-wise Graph Transformer
In this section, we introduce simple yet performant architecture named Cluster-wise Graph Trans- former (Cluster-GT) which takes node clusters tokens and utilizes N2C-Attn defined in Section to propagate information among clusters. Cluster-GT can be divided into three main modules: 1) a node-level convolution module, 2) graph partition module, and 3) cluster-wise interaction module.
3

---

Chaternee Atwetton Propapation
Pro processing Module
Resesstio
Cettooun Coreeae Kay
Mells Graph Partition
9. Ai3
Positional Encading
NZC-Altn Module
Cluster-GT
CAN Module
Graph
NOC--N Aac-AAmm Module
Modale
Pooling
Architecture of Cluster-wit Graph Transformer (Cluster-GT), which can be decomposed into three main modules: 1) a node-wise convolution module with GNN, 2) a graph partition module with Metis, and cluster-wise interaction module with N2C-Attn.
Figure 3:
3 presents the overall architecture of our proposed Cluster-GT. We begin with a node-level con- volution module to capture the local structural information. We try two common options, GCN [27]
and GIN [49], during our implementation. We also utilize two graph positional encoding strategies, random-walk structural encoding (RWSE) [9] and Laplacian eigenvector encodings [8) to enhance
the perception of the graph structure. More details can be found in Appendix D For the graph relatively simple graph partition algorithm, Metis [23]. to assign nodes
partition module,
to different clusters. After node clustering assignment, we introduce our proposed N2C-Attn as the cluster-wise interaction module, which propagates information among clusters. This process is divided into two steps: we first calculate the corresponding bi-level keys and queries, and then execute the efficient algorithm of N2C-Attn introduced in subsecttion 3.2 which outputs single embedding for each cluster. We finally perform average pooling to obtain the graph-level embedding.
The choice of kernel and feature map is not the main focus of our work. In our implementation, use the common exp-dot-product exp Q as KC- For the feature map of KN, we try two basic
options: (x)) = Elu(x) + [40] and (x)) = Relu(x) [24]. which we set as a hyperparameter.
Gluster-GT, in conjunction with N2C-Attn, is designed to enhance information exchange between node clusters after the graph partitioning. This process can be viewed
"post-pane poott-prtittooingg phase, which is a key distinction from many other mode-clustering-e based methods that primarily focus on optimizing the graph partition itself. In our implementation, we utilize a non-learnable and rigid graph partitioning algorithm, Metis. Notably, the Graph Partition module in Cluster-GT can be replaced with other learnable or flexible graph partitioning strategies, allowing for potential enhancements.
5 Evaluation
To evaluate the performance of Cluster-GT, we compare against two categories of methods: Graph Pooling and Graph Transformers. We conduct experiments on eight graph classification datasets from different domains, including social networks and biology. We further visualize the weight coefficients of the cluster-level and node-level kernels in N2C-Attn-L to observe how the model focuses different information granularities across different datasets. Additionally, we perform an ablation study, restricting the attention mechanism different granularities, to demonstrate the benefits of integrating both levels of information. We finally carry out an efficiency study of Cluster-GT. All experiments conducted NVIDIA RTX 3090s with 24GB of RAM. Detailed dataset information is available in Appendix and more details of the implementation are provided in Appendix F
5.1 Comparison with Graph Pooling Methods
Given the close relationship between Cluster-Gi GT and node clustering methods, we compare Cluster- GT with mainstream Graph Pooling methods:two well-known GNN baselines: GCN 27), GIN
49
six hierarchical pooling approaches: DiffPool [53], SAGPool(H) (2), TopKPool 13, ASAP
42
MinCutPool 4 SEP [50) and five global pooling techniques: Set2Set [48] SortPool 57 SAG-
Pool(G) 29 StructPool (55), GMT 2 We test Cluster-GT on six TU datasets [3:] IMDB-BINARY.
COLLAB, MUTAG, PROTEINS, and D&D. The first three datasets are in the field
7

---

Table Comparison with Graph Pooling Methods on six TU datasets, The shown accuracies (%) are mean and standard deviation over 10 different runs. We highlight the best results.
Model
IMDB- BINARY IMDB-MULT COLLAB
MUTAG
PROTEINS
D&D
GCN
73.2610.
50.39
80.59 0.27
19.5
73.24 L0.73
72.05
GIN
72. 72.7820.86
48. 48.13
78.19_0.63
81.39
71.46_1.06
70.79+1.17
Set2Set
72.90=0.75
50.1940.50
79.55_0.39
69.89+1.94
73.27=0.85
71.9440.54
SortPool
72. 12.12
48.18+a..5
77.87
71.94
73.17 =0.98
75.58
G
72.16=0.88
49.47 +0.00
78.85
76.78+2.12
72.02=1.01
71.54+0.11
StructPool
72.06
20.2331...5 50.53
=0.27
79.50
75.16
78.45
GMT
73.48 10.76
50.66..082
80.74_o.54
83.4411.33
75.09.0.55
78.7210.59
DifiPool
73.14.0.77
51.31 10.72
78.68L0.44
79.22 1.002
73.03 11.00
77.56
SA
12.55
50.23
78.03
73.67
71.56
74.72:
TopKPool
71.5820.95
20.5
77.58_0.85
67.61
70.48_1.01
73.63 23.555
ASAP
+0.51
50.78+0.75
78.64=0.50
77.83+1.49
73.92=0.6a
76.58+1.04
MinCutPool
72.63=0.76
51.0440.70
80.87=0.34
19.17+1.64
74.72=0.48
78.22 +0.64
SEP-G
74.1220.56
11.53
81.28
85.5611.09
77 17.9810.87
Cluster-GT
75.10=0.84
52.13
80.4320.52
87.11+1.87
76. 76.48=0.88
79. 15.0088
Table 2: Comparison with Graph Transformers on ZINC and MolHIV over 4 different runs of different seeds. We highlight the best results. Missing values from literature are indicated as '-',
Sold Niwak
N
MCD ExE Netano
Model
(MAE J) MolHIV (ROCAUC 1)
COLLO (Socil bateott
GT
0.226=0.0114
(tevrssmaks
GraphiT
0.20220.0m1
tevirmato
NU366 (Beinomaaal
Graphommer
0.122 006
GPS
0.070 004
0. 0.0000
SAN+LapPE
0.139 000
0.7775
Graph MLP-Mixer
0.073 001
0.7997 0.799710.0102 10.0102
Figure 4: Visualization of a (weight of the cluster- level kernel) during the training process. N2C-Attn learns to pay more attention to cluster-level infor- mation in social networks than in bioinformatics.
Graph VIT
0.085
0.7792:0.0140
Cluster-GT
0.071#0.004
0.8093+:00038
of social networks, while the latter three are in the field of biology. For a fair comparison, we strictly follow the experimental setup of [5]] Table IJshows the results, indicating that Cluster-GT outperforms all baselines on most datasets, even though it employs a relatively simple graph par- titioning algorithm compared to other node clustering pooling methods. This result highlights the effectiveness of the N2C-Attn module and shows the importance of the interaction between clusters in the "post-partitioning" phase, which is often oversimplified by other node clustering pooling methods.
5.2 Comparison with Graph Transformers
To assess the effectiveness of Cluster-GT within the context of Graph Transformers, we com- pare Cluster- GT with a range of existing Graph Transformers, including GT [8) GraphiT [35].
Graphormer 52]. GPS [41] SAN+LapPE (28]. SAN+RWSE (28), Graph MLP-Mixer [18 and
Graph ViT [8] We conduct the experiment on two datasets: ZINC from Benchmarking GNNs
[19]. For a fair comparison, we strictly follow the experimental setup of [8]. The result shown Figure demonstrates that Cluster-GT surpasses most existing Graph Transformers, underscoring the importance of integrating information both the cluster and node levels and showcasing the potential of using node clusters as tokens attention mechanisms.
and Mol-HIV from OGB
5.3 Visualization of a in N2C-Attn-L.
In this subsection, we present the dynamic changes in the weight coefficient during the training process N2C-Attn-L. a quantifies the contribution of cluster-level information the combined kernel, whereas B 1 quantifies the node-level information. By enabling the model to
8

---

(Baseline)
N2C-ABInTT
ClusterLevel Attn
Node-Level-ABee
MIDB-BINARY
IMDB-MULTI
PROTEINS
D&D
80
80
78
78
Acairacy
Acauracy
Accurace
Acauracy
42
74
76
22
70
48
70
Figure 5: Comparison of different attention strategies. We restrict the attention module in Cluster- to focus on different granularities. N2C-Attn T and N2C-Attn-L represent schemes that integrate information at both the node and cluster granularities. Cluster-Level-Atti focuses solely on cluster- level information, i.e., a = 1, while -ete-Leeel-Attn focuses solely on node-level information, i.e., O. We provide detailed description of the methods compared here in subsection F3
autonomously learn these coefficients, it dynamically adjusts to the varying importance of information at different granularities. We plot the evolution of a across training steps for six diverse datasets, as shown in Figure 4] We observe that the model automatically adjusts the weights assigned to the two levels of granularity. Notably, for social network datasets, Cluster-GT shows a preference for cluster-level information, whereas, for biology datasets, Cluster-GT balances its attention more equally between both granularities. This result indicates that N2C-Attn has a stronger inclination towards cluster-level information in the social networks domain compared to the biology domain.
5.4 Necessity of Combining Cluster-level and Node-level Information
In this subsection, we explore the necessity of fusing kernels of dual granularities within the N2C-Atth module. We analyze four variants: the first two are N2C-Attn-T T and N2C-AttnLL, which are the attention schemes utilized in Cluster-GT. N2C-Attn-T deeply integrates cluster-level and node-level information, whereas N2C-Attm-L autonomously adjusts the balance between these two granularities. Then, we create two additional variants that specifically focus on the node level or the cluster level by setting a in N2C-Attn-L. to O (exclusively focusing on the node-level kernel) and 1 (exclusively focusing on the cluster-level kernel). We provide detailed description of the methods compared here in lsuusecction F.3 Figure 5) shows the experimental results. We find that the variants that combine attention from both levels significantly surpass those that do not, with N2C-Attn-T leading marginally. This highlights the effectiveness of N2C-Attn's 's multiple kernel learning approach in integrating diverse levels of information. We reference the performance of GCN from Table as a baseline.
Other Methods Involving Graph Coarsening
In this section, we will briefly introduce some existing research on GNNs with graph coarsening to capture broader structural information, aside from the node clustering pooling introduced in secttiioon 2
12 utilizes dual- graph structure, employing hierarchical message passing strategy between molecular graph and its junction tree to facilitate a bidirectional flow of information. This concept of interaction between the coarsened graph (clusters) and the original graph (nodes) is similar to our N2C-Attn. However, the difference lies in [2]'s approach to propagating messages between clusters and nodes, whereas N2C-Attn integrates cluster and node information directly in the attention calculation using multiple-kernel method. (58) introduces a novel node sampling strategy as an adversarial bandit problem and implements hierarchical attention mechanism with graph coarsening to efficiently address long-range dependencies. [31] uses graph pooling to coarsen nodes into fewer representatives, focusing attention on these pooled nodes to manage scalability and computational efficiency. [2.5] introduces the Subgraph-To- Tode (S2N) translation method, coarsening subgraphs into nodes improve subgraph representation learning. [14 introduces HIGH-PPI, a double-viewed
hierarchical graph learning model that uses a hierarchical graph combining protein-protein interaction networks and chemically described protein graphs to accurately predict PPIs and interpret their molecular mechanisms. Despite achieving good results in their respective downstream tasks, these methods still follow the graph coarsening pipeline, whereas our work attempts to break this limitation and has demonstrated effectiveness on various graph-level tasks.

---

7 Conclusion
Our Node-to-Cluster Attention mechanism leverages the strengths of both node-level and cluster-level information processing without succumbing to the limitations of the graph coarsening pipeline. By conceptualizing the graph as interconnected node sets and integrating kernelized attention with multiple kernel learning, we effectively bridge the gap between cluster-level and node-level spaces, capturing the hierarchical structure of graphs as well as the node-level information. We develop an efficient form of N2C-Attn using the message-passingg softmax. Our Cluster-wise Graph Transformer, empowered by a straightforward partitioning strategy and the N2C-Attn module, demonstrates robust performance across diverse graph datasets. Extensive experiments have demonstrated the effectiveness of our Cluster-GT and N2C-Attn modules. We offer further discussion on the current limitation and potential impact in Appendix H andd Appendix I
framework and techniques of kernelized
Acknowledgement
This work was sponsored by the National Key Research and Development Program of China (No. 20232D0121402) and National Natural Science Foundation of China (NSFC) grant (No.62106143).
References
[1] D. Bacciu and L., D. Sotto. A non-negative factorization approach to node pooling in graph convolutional neural networks. In M. Alviano. G. Greco, and F. Scarcello, editors, II 2019 Advances in Artificial Intelligence XVIIIth International Conference of the Itaiian Association for Artificial Intelligence, Rende, Italy, November 19-22. 2019, Proceedings, volume 11946 of Lecture Notes in Computer Science, pages 994-306- Springer. 2019.
[2] Back, M. Kang, and S. Hwang. Accurate learning of graph representations with graph multiset pooling. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OvenReview.net, 2021.
[3] S. Bandyopadhyay, M. Aggarwal, and M. N. Murty. Robust hicrarchical graph classification with subgraph attention. CORR, abs/2007. 10908, 2020.
[4] F. M. Bianchi, D. Grattarola, and C. Alippi. Spectral clustering with graph neural networks for graph pooling. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 874-883 PMLR, 2020.
[5] K. M. Choromanski, V. Likhosherstov, D. Dohan, X. Song, A. Gane, T. Sarlós, P. Hawkins, J. Q. Davis, A. Mohiuddin, L. Kaiser, D. B. Belanger, L. J. Colwell, and Weller. Rethinking attention with performers. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[6] A. Derrow-Pinion. She, Wong, Lange, Hester, L. Perez, Nunkesser. S. Lee, X. Guo, P. W. Y. Li, and P. Veličković, Traffic Prediction with
Battaglia, V. Gupta, A. Li, Z. Xu, A.
Graph Neural Networks in Google Maps. 2021.
[7] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, Min- derer, Heigold, Gelly, J. Uszkoreit, and N. Houlsby. An image is worth 16x words: Transformers for image recognition at scale. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[8] V. P. Dwivedi, C. K. Joshi, A. T. Luu,, T. Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. J. Mach. Learn. Res., 24:43:1-43:48, 2023.
V. P. Dwivedi, A. T. Luu, T. Laurent, Y. Bengio, and X. Bresson. Graph neural networks with learnable struc- tural and positional representations. The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022, OpenReview.net, 2022.
[10] F. Errica, M. Podda. D. Bacciu, and A. Micheli. A fair comparison of graph neural networks for graph classification. 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[11] M. Fey and J. E. Lenssen. Fast graph representation learning with pytorch geometric. CoRR, abs/1993.02444 0000020228, 2019.
[12] M. Fey, J. Yuen, and F. Weichert. Hierarchical inter message passing for learning molecular graphs. CoRR, abs/2006. 12179, 2020.
10

---

[13] H. Gao and S. Ji. Graph u-nets. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach. California. USA, volume 97 of Proceedings of Machine Learning Rexearch, pages 2083-2092. PMLR, 2019.
[14] Z. Gao, C. Jiang. J. Zhang. X. Jiang. L. Li, P. Zhao, H. Yang, Y. Huang. and J. Li. Hierarchical graph learning for protein protein interaction. 14(1):1093.
[15] T. Gaudelet, B. Day, A. R. Jamasb, J. Soman, C. Regep, G. Liu, J. B. Hayter, R. Vickers, C. Roberts, Tang, et al. Utilising graph machine learning within drug discovery and development. arXiv preprint WwXiv2002.007//8 2020.
[16] M. Gönen and E. Alpaydin. Multiple kernel learning algorithmss J. Mach. Learn. Res., 12:2211-222 1-2268.
2011.
[17] D. Grattarola, D. Zambon, F. M. Bianchi, and C. Alippi. Understanding pooling in graph neural networks. IEEE Trans. Neural Networks Learn. Syst., 35(2):7088-27188 2024.
[18] X. He, B. Hooi, T. Laurent, A. Perold, Y. LeCun, and X. Bresson. A generalization of vit/mlp-mixer to graphs. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt. S. Sabato, and J. Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolula, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 17724-12745, PMLR, 2023.
[19] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 2020, virtual, 2020.
[20] W. Hu, X. Zhan, and M. Tong. Parsing netlists of integrated circuits from images via graph attention network. Sensors, 24(1):227, 2024.
[21] S. Huang, Song. J. Zhou, and Lin. Tailoring self-attention for graph via rooted subtrees. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
[22] M. Jin, H. Y. Koh, Q. Wen, D. Zambon, C. Alippi, G. I. Webb, I. King, and S. Pan. survey on graph neural networks for time scries: Forecasting, classification, imputation, and anomaly detection. CoRR, abs/2307.03759 2023.
[23] G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1) 3559-332, 1998.
[24] A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 5156-5165. PMLR, 2020.
[25] D. Kim and A. Oh. Translating subgraphs to nodes makes simple gnns strong and efficient for subgraph representation learning. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.nes 2024.
[26] D. P. Kingma and Ba. Adam: A method for stochastic optimization. In Y. Bengio and Y. LeCun, editors. 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[27] T. N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Truck Proceedings. OpenReview.nel 2017.
[28] D. Kreuzer, D. Beaini, W. L.. Hamilton, V. Létourneau, and P. Tossou. Rethinking graph transformers with spectral attention. In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6- 14, 2021, virtual, pages 21618-21629, 2021.
[29] J. Lee, I. Lee, and J. Kang. Self-attention graph pooling. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 3734-3743. PMLR, 2019.
[30] Y. Li, R. Yu, C. Shahabi, and Y. Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018
[31] C. Liu, Y. Zhan, X. Ma. L. Ding, D. Tao, Wu, and Hu. Gapformer: Graph transformer with graph pooling for node classification. In Proceedings of the Shirty-Secone International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 2196-2205. ijcai.or.. 2023.

---

[32] C. Liu, Y. Zhan, J. Wu, Li, B. Du, W. Hu, T. Liu, and D. Tao. Graph pooling for graph neural networks: Progress, challenges, and opportunities. In Proceedings of the Secood- International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 6712-6722. ijcai.org, 2023.
[33] N. Liu, S. Jian, D. Li, Y. Zhang, 7. Lai, and H. Xu. Hierarchical adaptive pooling by capturing high-order dependency for graph representation learning. IEEE Trans. Knowl. Data Eng., 35(4)33952-333 3965, 2023.
[34] D. P. P. Mesquita, A. H. S. Jr., and S. Kaski, Rethinking pooling in graph neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neurul Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[35] G. Mialon, D. Chen, M. Selosse, and J. Mairal. Graphit: Encoding graph structure in transformers. CoRR, abs/2106.056677 2021.
[36] E. Min, R. Chen, Y. Bian, T. Xu, K. Zhao, W. Huang, P. Zhao, J. Huang, S. Ananiadou. and Y. Rong. Transformer for graphs: An overview from architecture perspective. CoRR, abs/2202.08455, 2022.
[37] F. Monti, F. Frasca, D. Eynard, D. Mannion, and M. M. Bronstein, Fake news detection on social media using geometric deep learning. arXiv preprint arXiv: 190.006790000673. 2019.
[38] C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. CoRR, abs/2007. 20s//2007.08663, 2020.
[39] A. Pal. C. Eksombatchai, Y. Zhou, B. Zhao, C. Rosenberg. and J. Leskovec. Pinnersage: Multi-modal user embedding framework for recommendations at pinterest. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2311-2320, 2020.
[40] Z. Qin, W. Sun, H. Deng, D. Li, Y. Wei, B. Lv, J. Yan, L. Kong, and Y. Zhong, cosformer: Rethinking softmax in attention. In The Tenth International Conference Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReviow.net, 2022.
[41] I.. Rampásek, M. Galkin,
Dwivedi, A. T. Luu, G. Wolf, and D. Beaini, Recipe for a general, powerful, scalable graph transformer. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA. USA, November 28- December 2022, 2022.
[42] E. Ranjan, S. Sanyal, and P. P. Talukdar. ASAP: adaptive structure aware pooling for learning hierarchical graph representations. In The Toirty-Fourth AAAI Conference on Artifcial Intelligence, AAAI 2020, The Shirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 5470 5477. AAAI Press, 2020.
[43] H. Shirzad, A. Velingker, B. Venkatachalam, D. J. Sutherland, and A. K. Sinop. Exphormer: Sparse transformers for graphs. In A. Krause, E. Brunskill. K. Cho. B. Engelhardt, S. Sabato, and J. Scarlett, editors, International Conference Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 31613-31632. PMLR, 2023.
[44] S. Sonnenburg, G. Rätsch, C. Schäfer, and B. Schölkopf. Large scale multiple kernel learning. J. Mach. Learn. Res., 7:1531-1565, 2006.
[45] J. M. Stokes, K. Yang, K. Swanson, W. Jin, A. Cubillos-Ruiz, N. M. Donghia, C. R. MacNair, S. French, L. A. Carfrac, Z. Bloom-Ackermam,, et al. A deep lcarning approach to antibiotic discovery. Cell, 180(4):688-700 702, 2020.
[46] Y. H. Tsai, S. Bai, M. Yamada, L. Morency, and R. Salakhutdinov. Transformer dissection: An unified understanding for transformer's attention via the lens kernel. K. Inui, Jiang. V. Ng. and X. Wan. editors, Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNL.P-IJCNI 2019, Hong Kong, China, November 3-7, 2019, pages 4343-4352. Association for Computational I. Linguistics, 2019.
[47] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. In I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5998-6008. 2017.
[48] O. Vinyals, S. Bengio, and M. Kudlur. Order matters: Sequence to sequence for sets. In Y. Bengio and Y. LeCun, editors, 4th International Conference on Learning Representations ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
[49] X. Wang and M. Zhang. How powerful are spectral graph neural networks. In K. Chaudhuri, S. Jegelka, L. Song. C. Szepesvári, G. Niu, and S. Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of P Proceedings of Machine Learning Research, pages 23341- -23362. PMLR, 2022.
12

---

[50] J. Wu, X. Chen, K. Xu, and S. Li. Structural entropy guided graph hierarchical pooling. In K. Chaudhuri. S. Jegelka, L. Song, C. Szepesvári. G. Niu, and S. Sabato, editors, International Conference on Machine Learning, JCML 2022, 17-23 July 2022, Baltimare, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 24017 7-22030. PMLR, 2022.
[51] Z. Wu, S. Pan, F. Chen, G. Long. C. Zhang, and P. S. Yu. A comprehensive survey on graph neural networks. JEEE Trans, Neural Networks Learn. Syst., 32(1):4 24, 2021.
[52] C. Ying. T. Cai, S. Luo, S. Zheng, G. Kc, D. Hc, Y. Shen, and T. Liu. Do transformers really perform badly for graph representation? In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 28877-28888, 2021.
[53] Z. Ying. J. You, C. Morris, X. Ren, W. L. Hamilton, and J. Leskovec. Hierarchical graph representa- tion learning with differentiable pooling. In S. Bengio, H. M. Wallach, H. Larochelle, K. Grauman, N. Cesa- Basa-Bianchh, and Garnett, editors. Advances in Neural Information Processing Systems 31: An- nual Conference on Neural Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pages 4805-484 4815,885,22 2018
[54] B. Yu, Н. Yin, and Z. Zhu. Spatio-temporaa graph convolutional networks: A deep learning framework for traffic forecasting. In J. Lang, editor, Proceedings of the Twenty- International Joint Conference on A Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pages 3634-364) ijcai.org, 2018.
[55] H. Yuan and S. Ji. Structpool: Structured graph pooling via conditional random fields. Interna- tional Conference on Learning Representations, ICLR 2020, Addis Ababa, Eshiopia, April 26-30, 2020. OpenReview.net, 2020.
[56] Н. Zhang and M. Xu. Graph neural networks with multiple kernel ensemble attention. Knowl. Based Syst., 229:107299, 2021.
[57] M. Zhang, Z. Cui, M. Neumann, and Y. Chen. An end-to-end deep learning architecture for graph classification. In S. A. Mcllraith and K. Q. Weinberger, editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAA--8), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 4438 4445. AAAI Press, 2018.
[58] Z. Zhang, Q. Liu, Q. Hu, and C. Lec. Hicrarchical graph transformer with adaptive node sampling. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 2022, 2022.
13

---

A Efficient implementation of Node-to-Cluster Attention with Convex Linear Combination of Kernels
In this section, we will devise an efficient form for the Node-to-Cluster Attention with Convex Linear Combination of Kernels:
N2C-Attn-LXX;; = ΣjA
A E. Ciylaric (Q; K2) + BnN kE Σj A E, Cuslancc(iii Qu. K2) + 3kx(
(18)
We introduce the corresponding feature map: (c, K2) Bx(gi,h k2) = (bb(g:), (k,)) According to Prop.1 we have BB 9:b) Vao(Q) (Q.) +
(o(Q)), o (K3) and
(....
BBblg:; Db((K,, ki)) Vao(K;) @ BBb(k)) Thus we can rewrite Equation 18 as:
N2C-Attm-L(X), = Ej A E, Ct (vāσ(1i) v (Ba())))) (Voo(K)) @ vBy((s:)
Σ, A E. C5 (Q.) @ (Bv())) [Vao(K)) @ BBb()))]
(ao(Qi) @ (Bbla)) T E, A E. C. (ao((K) @ vBb(())) et (Qi)) @ (By(a)) Σ, A Σ. Cy [Vāo(K)) @ BBb(())]
(19)
where (Vao(Q:) @ [bb(4))) is the weighted concatenation of the feature map of bi-level queries, while Vaol K2) + (ke) is the weighted concatenation of the feature map of bi-level keys.
Equation allows us to implement N2C-Attn-L with message- message-passing framework, which is similar to the implementation that we have devised in subsection 3.2, We can first calculate the equiv- alent feature map of the bi-level query [Vap( Q2) + (B)( for each cluster, and the equiva- lent feature map of the bi-level key (Va((K)) @ (k)) for each node. Then we aggregate the keys of nodes within every cluster respectively to get Σ. Ct [Vāő(K,) @ BBb(()) ir and E. Cj [Vaø(K) (Kj) @ (k))] After getting these two aggregated "messages", we perform message passing according the adjacency matrix of the coarsened graph A And finally, unpack the aggregated information by calculating the dot product with the feature map of the bi-level query (V @ vBv(1)) T In summary, by using the corresponding feature map and this cluster-level message propagation, we can achieve an implementation method for N2C-Attn-L. with linear computational complexity.
(
B Relationship between Graph VIT and N2C-Attn mechanism
In this subsection, we present a detailed justification for why the attention mechanism used in ViT (18) can be regarded this section, we mainly focus on the similarities and differences in attention computation between ViT and N2C-Attn. While Graph also enhances its performance and expressive power through the use of various positional encodings, residual connections, and normalization techniques, these modules not the primary focus of this section and therefore will not be discussed.
special case of our proposed N2C-Attn. Please note that in
Graph VIT first uses Metis to partition the graph (with overlapping nodes), and then performs average pooling within each partition. We denote the embedding of the clusters as X.". GraphViT then per- forms the Graph-base based Hadamard Attention: G-Hadamard-Attm (X to capture the dependencies
between the clusters, where G- G-Haaamard-AAe is defined as (A softmax
(QR" Vaa )) V.
We denote the node set if the p-th cluster as Vp, then the average pooling process can be written as: Tp V.. Eiey, Ti,p. where Ti is the embedding of the i-th node within the p-th cluster, and xp is the embedding of the p-th cluster. And we denote the connected clusters (cluster-wiss neighbors) of
14

---

the i-th cluster as M,. Then the Hadamard Attention used in Graph ViT ViT can be written as:
EYVi,N A/e (Q;,
G-Hadamard-Aunn();
EjNNN, Aig x (Qi,
EYMEEN, A.e kQ K2) Eiev, [V]]
(20)
EYySEN, Alg 1. (Qi,, (Qi,K)) EiEV, [V5]
ENNEEN, Abg Enev, 1s (Qi, K2) |oj Ut
ΣY.YYEN, Ale Eiev, n (Q;, K₃) [V,]
Va ( Q and K can be cluster-level queries and keys.
where K (Qi, (Q,, exp
Now, check the corresponding form of N2C-Attn in this case. Since the Metis graph partitioning algorithm, which divides the graph into several separate subgraphs and produces a hard cluster Assignment Matrix:
the n-th node is the m-th cluster
Metis nm
(21)
0
otherwise
With the help of Equation 21
we can rewrite Equation
I as:
N2C-Attn-T(X)): EnNYeN, Ahe Eve,, Ni ko(,,, K)) (g ke)er EjNYEN, Aie Exev, KC ko K2) )N (qi,hit)
(22)
Comparing Equation 20 and Equation 22 if we set ko (Qi. K2) = K (Q,, K2) = exp 2 then
the only difference between these two tormulas lies in the coefficient before vt.. In fact, Equation 20 can be seen as a special case Equation 22 where KN (gi, k2)
From our analysis above, the difference between the cluster-level attention used in Graph and N2C-Attn is follows: the former assigns the same weight to all nodes within each cluster [P.7 while the latter allows different attention weights for the nodes within each cluster and uses node-level kernel Ky to learn these weights.
For simplicity, only prove that the cluster-level attention used in Graph ViT can be considered a special case of Node-to-Cluster Attention with Tensor Product of Kernels (N2C-Attn-T) in this section. In fact, we can similarly argue that the cluster-level attention used in Graph is a special case of Node-to-Cluss -luuterrrrrrr Attention with Convex Linear Combination of Kernels (N2C-Attn-L). Their most important difference that Graph still follows the graph coarsening pipeline and only uses cluster-level kernels for attention calculation, whereas N2C-Attn integrates both cluster-level and node-level kernels to perform the attention computation.
C Proof of Proposition
C.1 Proof of Equation 16
In this subsection, we offer a detailed proof for Equation 16
If Qi,K, are d -imeensional vectors from the cluster-level space X and qi ky are d -imeensiona vectors from the node-level space X'y. Consider two kernel functions ric, KN from the cluster- level space Xc and the nove-level space XN respectively, with the corresponding feature map: (o, K2) = (o(Q,), ((;))) and k kt) = (q:).. (k()).
Now we consider the case of Node-to-Cluster Attention with Tensor Product of Kernels, where we use the product of the kernels Kc; EN to construct the bi-level kernel: AB *B((Q; g:). [K,, [Kj,k,)] k.)) =
(Q,, K2) N (gi, ke) where KB is the bi-level kernel from the tensor product of two original spaces
15

---

Ne x Av. Then, for all (Q,, E X and (4, kb) E AN we have: KKN KN (qi, kt) (o(Q))) ( (K₃)) (wb()), (b+)))
Su(fQi.9) (K, - kc(Qi, K
de
xx
pm @m (m((:))m((K) Σ
(23)
dc d
(om (Qi))) (0m (K)))n
m
Thus, we can construct the following feature map:
Th (u)x/(2 (v) Φi (1))2((()))
BB(u, v) = (22(4)(111)
= ( @ (vv)
(24)
where dB is d feature map. For each pair (i,j). (B, v) = (1) where
1 S < d and S d. This composite feature map 4B corresponds the kernel Am.
With the composite feature map BB, we can rewrite Equation 23 as:
d d²
(a(1) (K,,)) =
T B(m,n) (Qi, B(), (Kj, (25)
= (Q (:), p (n(K,,k))
which proves Equation
C.2 Proof of Equation 17
In this subsection, we offer a detailed proof for the Equation 17
Again, we use kc, KN to denote the two kernel functions from the cluster-level space X' and the node- level space Xx respectively, with the corresponding feature map: kc(Qi, Kj) (o(Qs), o(K))) and Hx k2) = (x)(4) (kx)).
Now consider the case of Node-to-Cluster Attention with Convex Linear Combination of Kernels, where we use the convex linear combination of kernels Ki; AN to construct the bi-level kernel: and
kn (ii,, 3: {K, ke)) (xc(Qi, K2) + BNN (gi, k.) where a, 0 and + 3 are coefficients that balance the contribution of each kernel. Then, for all (Qu, K2) e X2 and (ge, k.) E 22 we have:
KB ( (Qi, 4), (K,, kx)) = anc(Qi, K2) + (a,((; ks)
a(o(Qi), ((K,) + (()()
(Voo(Qi), vod( (K₂)) + (VBb((a)) BBb(()))
(26)
Σ Vadm (aomm(ii)aaon (asmm(()Vaemm(k))) + Σ (Bu..
m
Thus, construct the following feature map:
Φn v) Vap(u) @ (Bb(v)
(27)
where Up is weighted concatenation of the feature maps and v. In other words, if the feature maps and vi have dC and d coordinates respectively, then Φn has dc d coordinates; for any pair (u,v) E Xe x Xx. the first dc coordinates of & (u, v) are fadi (u), Vapy(u)... (u),..., .a...,vooo vod (u) and the remaining dN coordinates @B (u, v) are (B))(u)) / (B), (Bbax())
With the composite feature map QB. we can rewrite Equation 26 as:
KB (B(( 4.. (Ky, ke)) = (4b(Qn, 9)) & k.)
(28)
which proves Equation 17
16

---

Table Summary statistics of datasets
Dataset
#Graphs
Avg. #Nodes
Avg. #Edges
Task
Metric
IMDB BINARY
1000
19,8
96.5
binary classif.
Accuracy
IMDB-MULTI MULTI
1500
13,0
66.0
3-class classif.
Accuracy
COLLAB
5000
74.49
2457.8
3-class classif.
Accuracy
MUTAG
188
17.93
19.8
hinary classif.
Accuracy
PROTEINS
1113
39.1
72.8
binary classif.
Accuracy
D&D
1178
284.3
715.7
binary classif.
Accuracy
ZINC
12,000
23.2
24.9
regression binary classif.
MAE
MolHTV
41,127
25.5
54.9
ROCAUC
D More Details of Cluster-GT
Positinal Encoding Positional encoding in graphs plays crucial role in providing spatial context to nodes. Following [8. we adopt two different strategies: random-walk structural encoding (RWSE) (9] and Laplacian eigenvector encodings [8]. We concatenate the positional encoding with node features as the model input. Additionally, we have tried the patch-wise positional encoding proposed by [88 and set it as hyperparameter for the Cluster-GT architecture.
our Cluster-GT framework, we have experimented with incorporating GCN (27) and GIN [49] the node-wise convolution modules, setting the choice between them hyperparameter to optimize performance. GIN is particularly notable for its ability to improve model expressiveness, which is crucial in distinguishing different graph structures. Moreover, the design of our Cluster-Gi GT framework is modular, allowing the node-wise convolution module to be freely replaced by any other method.
Node-wise Convolution
Bi-level Queries and Keys After the node clustering assignment, we obtain various node clusters.
When generating cluster-level queries or keys, we have tried two options: 1) using DeepSets, 2) aggregating the queries and keys within a cluster. We set these two options as a hyperparameter for the model architecture. In experiments, Additionally, we find that having the same cluster-level and node-level queries does not affect the model's performance, long as the bi-level keys remain different. Therefore, we whether the queries at the two levels are identical as an optional hyperparameter.
find that these options have similar performance.
Other details Just like other Transformer structures 44 incorporate residual connections between the attention layers and MLP, along with layer normalization to enhance training stability. In N2C-Attn, after outputting representations at each cluster level, we ultimately obtain a graph-level representation through average pooling. For N2C-Attn-T and N2C-Attn-L, we use the efficient algorithms introduced in subsecttion 3.2 and Appendix A in our implementation, respectively.
E
Dataset Information
Our experiments employ variety of benchmark datasets commonly used in graph learning research. These datasets are chosen their distinct characteristics and relevance in testing graph classification algorithms. The summary statistics of datasets are shown in Table 3
E.1 Datasets used in subsection 5.1
We organize the datasets into categories based on their application domains. Social Networks: and
are derived from the Internet Movie Database (IMDB) and include graphs representing the ego-networks of different movie genres. In BMDB-BINARY, each graph is labeled as either Action or Romance. IMDB-MULTI includes three genres: Comedy, Romance, or Sci-Fi. Nodes represent actors, and edges are placed between nodes the actors have co-starred in a movie. These datasets are used to evaluate the capability of graph classification models in social network analysis. Scientific Collaboration Networks: COLLAB represents the ego-collaboration networks of researchers from three fields: High Energy Physics, Condensed Matter
17

---

Physics, or Astrophysics. Nodes represent scientists, and edges are drawn between scientists who have co-authored papers. COLLAB tests the model's ability to recognize different collaborative patterns in scientific domains. Biochemical Molecules: For the biochemical domain, we have chosen three datasets: MUTAG, PROTEINS and D&D. MUTAG comprises 188 chemical compounds represented as graphs, where nodes symbolize atoms and edges denote chemical bonds. Each graph is labeled based on its mutagenic effect on bacteria, serving as a benchmark for bioinformatics applications in predicting chemical properties. PROTEINS consists of protein structures, where each graph corresponds to a protein, nodes to secondary structure elements (SSEs), and edges connect nodes if they are adjacent either in the amino acid sequence or in 3D space. Proteins are classified into enzymes or non-enzymes, providing a basis for studying complex biological structures. D&D includes protein structures with nodes representing amino acids and edges based on spatial closeness. Graphs are labeled according to whether the protein is associated with a disease, challenging the algorithms decode intricate biological interactions. These datasets collectively provide a comprehensive suite for evaluating across different real-world scenarios.
E.2 Datasets used in subsection 5.2
Here, we select two datasets used in biochemical molecule and drug discovery research: Biochem- ical Molecules: The ZINC dataset is collection of chemical compounds that are representative of real-world molecular data. This dataset is utilized predominantly for regression tasks such as predicting the scalar measure of molecular solubility. Each compound is represented nodes are atoms and edges are chemical bonds, making it crucial for testing the accuracy of models in predicting molecular attributes. Drug Díscovery: The MolHIV dataset is part of the MoleculeNet suite, specifically designed for binary classification tasks related to HIV drug activity. Graphs in this dataset represent molecular structures where nodes are atoms and edges correspond to bonds. The task is to predict whether a molecule inhibits the HIV virus, which is vital for speeding up the discovery of potential therapeutic agents.
graph where
F Implementation Details
F1 Introduction of baselines
Baselines for |suseectionn 5.1
Initially, we utilize two well-known GNN architectures for compar- Subsequently, we incorporate six hierarchical pooling approaches as baselines: DoffPool [33] SAGPool(H) 229]. TopoPPol [I3], ASAP [2). MinCutPool 4 and
ison: GCN (2] and GIN [49].
SEP [50) In addition to these hierarchical pooling methods, considerable attention has been given to global pooling strategies for graph classification. Therefore, we also evaluate five global pooling tech-
niques: Set2Se [48, SortPool SAGPool(G) 229] StructPool [55), and GMT 2 for comparative
analysis.
Baselines for jsuussscttion 5.2] Next, we compare Cluster-GT against popular Graph Transformers with SOTA results, including GT 8 GraphiT (35), Graphormer (52), GPS [41) SAN+LapPE (28).
SAN+RWSE (28] These models represent cutting-edge advancements in graph neural network technology, each introducing unique methods to handle graph-structured data effectively.
F22 Experimental Details
The model is implemented using PyTorch and PyG (1]. Experiments are conducted on NVIDIA RTX 3090 GPUs. For optimization, the Adam (26 optimizer utilized, adhering to the default settings of 3 0.9, B2 0.999, and le 8.
The model's performance is assessed using a 10-fold vols-validotion approach, with dataset splits adhering the standard established training/test partitions [50]. Moreover, 10 percent of the training data is allocated as validation data to ensure a fair comparison, as per [10. The initial feature inputs are aligned with the fair comparison setting (10] An early stopping criterion is implemented, halting training if there is no improvement in validation loss over 50 epochs. The training process capped at a maximum of 500 epochs. The average performance on the test sets is reported after conducting the experiments 10 times.
Experimental Details of subsection 5.1
18

---

Experimental Details of subssecctin 5.2
Each experiment is run with four different seeds, and the averaged results are reported from the epoch that achieved the best validation metric. We use a batch size of 64. We utilize standard train/validation/test dataset split following [18]
F.3 Attention strtegies compared in subsection 5.4
In this section, we provide detailed introduction the four different node-to-clustering attention strategies: "N2C-Attn-T", NNC-AA-L A "Cluster-Leel--Ate ablation study. Note that for these four variants, simply replaced the attention mechanism in Cluster-GT without modifying any other parts of the model.
NNodeettt 'Node-Level-Attni compared in the
N2C-AttmTT
12C-Att-T(XX), = E, Afe E. CQjic(Qi, Ky) (1ir ) E, A. E. Ciyko(Q,, Kr ke)
(29)
N2C-AtIn-L:
E, A E, Caj(ari (Qi, Kj) Ba ka) Ej A E, Ctj Caj(a (Qi, K2) + BEN (gingggiii kt))
N2C-Attn-L(X);
(30)
Cluster-Level-Aun:
E, P E. Ci Kz) E, A. E. (Q; K2)
Chuste--LevelAAtm((1]
(31)
Node-Level-Altn:
E, A E. CySEN (g. Node-Level-Attu(X)] = Σ, A E. Ci
(32)
worth noting that Cluster-Leve-AAtt is a special case of N2C-Amt-L when the cluster-level coefficient a while Node-Level-Attn is also special case of N2C-Attn-L when the node-level coefficient 3 = 1 - 1.
G On the Naming Issue Between RWSE and RWPE
We the term "Random Walk Positional Encoding (RWPE)" in this work. this section, we will briefly discuss the naming issue between RWSE and RWPE. In the original paper that introduced RWPE [9, the term "Random Walk Positional Encoding (RWPE)" was proposed. This paper utilized the self-landing probability of nodes in random walk to capture neighborhood structural information.
Subsequently, influential work in the graph transformer domain [4] made clear distinction between two types of encodings for structure and position, naming them Positional Encoding (PE) and Structural Encoding (SH). Positional encodings are intended to provide understanding of node's 's position within the graph, while structural encodings aim to embed the structure of graphs or subgraphs, enhancing the expressivity and generalizability of GNNs.
Interestingly, 41 argues that the Random Walk Positional Encoding (RWPE) proposed in 9 actually serves Structural Encoding (SE). Based
investigation, it is likely that [1] began using the term RWSE instead of RWPE. Many subsequent studies, likely influenced by [41), such as [43][8]] have also adopted RWSE over RWPE. In our work, also use RWSE, the widely accepted term.
In conclusion, both RWSE and RWPE are widely recognized and used interchangeably in the academic community to refer to the same PE method (diagonal of the k-steps random- manoo--walk matrix).
H Limitations
We employ Metis in conjunction with the N2C-Attn module for Cluster-GT. However, Metis non-learnable graph partitioning algorithm that provides hard assignments for node clustering.
19

---

This poses limitation as it restricts the flexibility of node groupings, potentially impacting the adaptability of the model in dynamic or complex network scenarios. For future enhancements. exploring combinations of N2C-Attn with other learnable graph partitioning algorithms capable of generating soft assignments may be an interesting direction. Additionally, aspects such as robustness and explainability also warrant further investigation to ensure reliability in real-world settings.
I Potential Impacts
The proposed Node-to- tottttt- Attention mechanism introduces novel approach to information exchange between node clusters. Our research underscores the importance of incorporating diverse strategies for interactions at both the node and cluster levels. This perspective can be integrated with many existing node muustering-baser graph learning methods, enhancing their efficacy and adaptability. Moreover, our experimental validations reveal that the method of interaction between clusters significantly impacts model performance. While current research primarily focuses how partition clusters within graphs, our findings suggest promising direction for future work: optimizing the methods of interaction between clusters. Such advancements could unlock new possibilities for cluster-level graph learning, potentially leading to more robust and sophisticated models that better capture the complexities of large-scale networks.
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims mentioned in the abstract and introduction are further explained and proved in the main text.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We provide discussion of current limitations in Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
21

---

Justification:
We provide the proof of our claims in Appendix B and Appendix C
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We describe the architecture clearly and fully and provide the corresponding
code.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
22

---

Answer: [Yes]
Justification: We provide the corresponding code for our proposed model and the reproduc- tion of experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
wwweeeeeeeeoeSbubmmimooe ssicnpolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide detailed description of the experimental settings in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We repeated the experiments multiple times with different seeds and reported the standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
23

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We offer an introduction of the computational resource used in our experiment section 3
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our research has no adverse socictal impact and strictly adheres to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We offer a discussion on the potential impacts in Appendix
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The graph learning scenarios we study do not involve such risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: In our experiments, we used datasets that are all open-source and widely utilized.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
25

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not introduce new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We did not involve any Human Subjects in our experiments.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We did not involve any Human Subjects in our experiments.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "ZuPTKylSGF", "reviewer": "Reviewer_azHs", "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.", "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.", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents a clear and well-supported motivation for the proposed methodology, with technical details that are thoroughly demonstrated.\n\n2. 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.\n\n3. 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.\n\n2. 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$.\n\n3. 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.\n\n**Reference**\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's feedback. We provide details to clarify the reviewer's major concerns.\n\n> **Q1. The comparison with graph pooling methods misses MVPooL [1], a recent baseline that has achieved higher accuracy on these benchmarks.**\n\nWe appreciate the reminder from the reviewer. MVPooL [1] is a compelling method in the domain of graph pooling. Although the datasets involved in the experiments of [1] partially overlap with those used in our work, we did not reference the results from MVPooL in our paper due to differences in experimental settings.\n\nWe conduct a comparison of MVPooL under the same experimental setup as described in Section 5.1. (due to time limits, we did not conduct a hyperparameter search and instead used the default hyperparameters provided in the code from [1]). ClusterGT achieved relatively superior results on 5 out of the 6 datasets. \n\n| Model|IMDB-BINARY|IMDB-MULTI|COLLAB|MUTAG|PROTEINS|D&D|\n|-|-|-|-|-|-|-|\n| MVPool     | 72.87±0.69    | 51.04±0.79    | 80.88±0.34    | 82.73±1.21    | 75.15±0.70    | 77.32±0.49    |\n| Cluster-GT | 75.10±0.84    | 52.13±0.78    | 80.43±0.52    | 87.11±1.37    | 76.48±0.86    | 79.15±0.63    |\n\n\n\n\n> **Q2. 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.**\n\nThank you for pointing out this typo. Indeed, the attention score between the $i$-th cluster and the $t$-th node in the $j$-th cluster should be:$\n\\frac{\\mathbf{A}\\_{i, j}^P \\mathbf{C}\\_{tj} \\kappa\\_{\\mathrm{B}}(\\\\{Q\\_i, q\\_i\\\\},\\\\{K\\_j, k\\_t\\\\})}{\\sum\\_j \\mathbf{A}\\_{i, j}^P \\sum\\_t \\mathbf{C}\\_{tj} \\kappa\\_{\\mathrm{B}}(\\\\{Q\\_i, q\\_i\\\\},\\\\{K\\_j, k\\_t\\\\})}\n$ . We will make the necessary corrections.\n\n> **Q3.  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.**\n\nWe thank for the reviewer's suggestion. However, there might be a slight misunderstanding here. In fact, the result involving only keys and values **is well-defined** (i.e $\\sum_t\\psi(k_t) v_t$ in the paper, where $\\psi(k_t)\\in \\mathbb{R}^{d_k\\times1}$ and $v_t\\in\\mathbb{R}^{1\\times d_v}$). The kernelized softmax trick aggregates keys and values first, and then computes them with queries to reduce computational complexity (e.g. [2,3,4]).\n\nTherefore, Step 1 and Step 4 can be separated. During our implementation, we follow the sequence of Step 1, 2, 3, and 4 as illustrated in Fig. 2, which aligns with the computational process introduced in Section 3.2 and Equation 14.\n\n\n> **Q4.  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.**\n\nWe appreciate the reviewer for highlighting this interesting point.\n\nFirstly, we would like to clarify that: cluster-level attention does not always outperform node-level attention. In fact, as shown in Figure 5, among the four datasets analyzed, cluster-level attention performs better only on IMDB-Binary and IMDB-Multi, whereas node-level attention excels on PROTEINS and D&D. In summary, both cluster-level and node-level attentions have their merits: cluster-level attention is more suitable for social network datasets, while node-level attention fits better with bioinformatics datasets. This may be attributed to the structured nature in social network datasets like IMDB where cluster-level patterns are more pronounced.\n\nMoreover, although node-level attention is indeed more flexible than cluster-level attention, this does not necessarily mean that it outperforms the latter. Cluster-level attention effectively utilizes the auxiliary information of node cluster assignment. Despite being coarser in granularity compared to node-level information, this cluster-level information can be helpful and less noisy, particularly for the graph-level tasks we study in this paper.\n\nLastly, this issue can also be analyzed from the perspective of the impact of introducing additional constraints on model regularization: while cluster-level attention is not as flexible as node-level attention, the additional constraint within cluster-level attention might help prevent overfitting, enhancing its robustness and generalization capabilities.\n\n\n[1] Zhang et al. Hierarchical multi-view graph pooling with structure learning. IEEE TKDE 2021.\n\n[2]. Katharopoulos et al. Transformers are rnns: Fast autoregressive transformers with linear attention. ICML 2020.\n\n[3]. Wu et al. NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification. NeurIPS 2022.\n\n[4]. Huang et al. Tailoring Self-Attention for Graph via Rooted Subtrees. NeurIPS 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yPqycsnpAJ", "reviewer": "Reviewer_Tre7", "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.", "questions": "- Can the authors rename RWSE to RWPE, following the original work?", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "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.\n- 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:\n  1. Fey, M., Yuen, J. G., & Weichert, F. (2020). Hierarchical inter-message passing for learning on molecular graphs. arXiv preprint arXiv:2006.12179.\n  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.\n  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).\n  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.\n  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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's comments and suggestions. Here are our detailed responses to your main concerns.\n\n> **Q1. 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.**\n\nWe thank the reviewer for pointing out this issue. Indeed, the METIS algorithm includes the coarsening (and uncoarsening) process. Thus, strictly speaking, there is a coarsening operation during the partition phase in our implemented cluster-GT.\n\nThe point we wish to emphasize is that our work primarily focuses on the post-partition phase (line 227), while the methods used in the partition phase are not our central focus. We can replace Metis with other methods that do not involve coarsening. The proposed approach itself (i.e. N2C-Attn) achieves the objective of \"without resorting to the graph coarsening pipeline\". \n\nWe thank for the reviewer's suggestion. We will revise our manuscript to clarify this point and avoid any potential overstatement.\n\n\n> **Q2. 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:**\n>\n>[5]. Fey et al. Hierarchical inter-message passing for learning on molecular graphs. arXiv:2006.12179.\n>\n>[6]. Zhang et al. Hierarchical graph transformer with adaptive node sampling. NeurIPS 2022.\n>\n>[7]. Liu et al. Gapformer: Graph Transformer with Graph Pooling for Node Classification. IJCAI 2023.\n>\n>[8]. Fu et al. VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections. ICLR 2024.\n>\n>[9]. Kim et al. Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning. ICML 2024.\n\nThank you for your suggestion and the provided references. Here, we briefly discuss the literature you mentioned and will include a more comprehensive discussion on related work in our paper.\n\n[5] utilizes a dual-graph structure, employing a hierarchical message passing strategy between a molecular graph and its junction tree to facilitate a bidirectional flow of information. This concept of interaction between the coarsened graph (clusters) and the original graph (nodes) is similar to our N2C-Attn. However, the difference lies in [5]'s approach to propagating messages between clusters and nodes, whereas N2C-Attn integrates cluster and node information directly in the attention calculation using a multiple-kernel method.\n\n[6] introduces a novel node sampling strategy as an adversarial bandit problem and implements a hierarchical attention mechanism with graph coarsening to address long-range dependencies efficiently. [7] uses graph pooling to coarsen nodes into fewer representatives, focusing attention on these pooled nodes to manage scalability and computational efficiency. Nonetheless, [6,7] still follow a graph coarsening pipeline, i.e., computing attention on the pooled graph.\n\n[8] focuses on challenges in mini-batch training, proposing to rewire graphs by introducing multiple types of virtual connections through structure- and content-based super nodes. This approach differs from our study, which deals with information propagation between different clusters in the whole graph. [9] introduces the SubgraphTo-Node (S2N) translation method, coarsening subgraphs into nodes to improve subgraph representation learning. While innovative for subgraph classification, it follows the graph coarsening pipeline and does not align directly with the broader graph-level tasks targeted in our research.\n\n> **Q3. Can the authors rename RWSE to RWPE, following the original work?**\n\nWe appreciate the reviewer's attention to this interesting detail. Here, we provide a brief investigation into the naming of RWPE.\n\nIn the original paper that introduced RWPE [1], the term \"Random Walk Positional Encoding (RWPE)\" was proposed. This paper utilized the self-landing probability of nodes in a random walk to capture neighborhood structural information.\n\nSubsequently, an influential work in the graph transformer domain [2] made a clear distinction between two types of encodings for structure and position, naming them Positional Encoding (PE) and Structural Encoding (SE). Positional encodings are intended to provide an understanding of a node's position within the graph, while Structural encodings aim to embed the structure of graphs or subgraphs, enhancing the expressivity and generalizability of GNNs.\n\nInterestingly, [2] argues that the Random Walk Positional Encoding (RWPE) proposed in [1] actually serves as a Structural Encoding (SE). Based on our investigation, it is likely that **[2] began using the term RWSE instead of RWPE**. Many subsequent studies, (likely influenced by [2],) such as [3, 4], have also adopted RWSE over RWPE. In our work, we also use RWSE, the widely accepted term.\n\nIn conclusion, both RWSE and RWPE are widely recognized and used interchangeably in the academic community to refer to the same encoding method (Diagonal of the $m$-steps random-walk matrix). We will include this brief investigation on the evolution of the term RWPE(RWSE) in our paper.\n\n[1]. Dwivedi et al. Graph Neural Networks with Learnable Structural and Positional Representations. ICLR 2022.\n\n[2]. Rampášek et al. Recipe for a General, Powerful, Scalable Graph Transformer. NeurIPS 2023.\n\n[3]. Shirzad et al. Exphormer: Sparse Transformers for Graphs. ICML 2023.\n\n[4]. He et al. A Generalization of ViT/MLP-Mixer to Graphs. ICML 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mDSSsjCE9V", "reviewer": "Reviewer_2taa", "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.", "questions": "- In addition to the node-to-cluster attention, should there also be cluster-to-node attention and cluster to cluster attention?\n\n- Figure 3: typo? “positinal”->”positional”", "limitations": "discussion in Appendix H.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Even though it is a complicated setup, the paper is well written and illustrated, and somewhat managed to get the setup across.\n\n- 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\n\n- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the reviewer's comments and suggestions. Below, we provide detailed responses to address the main concerns.\n\n> **Q1. Even though it may be unavoidable, the amount of notations make reading the paper somewhat difficult.**\n\nWe fully understand the reviewer's concern about the number of notations, and we acknowledge that it might make the reading experience challenging. But given the complexity of the algorithm setup, these notations are essential for conveying the technical details accurately.\n\nThe idea of our approach, however, is straightforward: we integrate multiple kernel learning within the kernelized attention framework, which facilitates effective information transfer at both cluster and node levels among clusters without resorting to the graph coarsening pipeline.\n\nTo enhance readability, we have included visual representations of the methodology in Figures 1, 2, and 3 in the paper. Additionally, we provide here a list of notation and the corresponding description. \n\n| Notation | Description |\n|-|-|\n| $(\\mathcal{N}, \\mathcal{E}, \\mathbf{X}, \\mathbf{A})$ | Multi-tuple representing the graph: nodes ($\\mathcal{N}$), edges ($\\mathcal{E}$), node features ($\\mathbf{X}$), adjacency matrix ($\\mathbf{A}$). |\n| $(\\mathcal{N}^P, \\mathcal{E}^P, \\mathbf{X}^P, \\mathbf{A}^P)$ | Cluster-level (coarsened) graph components. \n| $\\mathbf{C}$ | Cluster Assignment Matrix, used to map nodes to clusters, obtained from graph partitioning methods.  |\n| $\\mathcal{X}_C, \\mathcal{X}_N$| Feature space for cluster-level and node-level attributes. |\n|$k_t$| Node-level key, derived from the $t$-th node's embedding: $k\\_t = \\mathbf{W}\\_k h\\_t$, where $h_t$ is the feature of the $t$-th node.   |\n| $K_j$| Cluster-level key, representing collective features of the $j$-th cluster: $K\\_j = \\mathbf{W}'\\_k (\\sum\\_{s}\\mathbf{C}\\_{sj}h\\_{s})$. |\n|$q_i$| Node-level query for the $i$-th cluster interacting with the node-level key: $q\\_i = \\mathbf{W}\\_q (\\sum\\_{s} \\mathbf{C}\\_{si} h\\_{s})$. |\n|$Q_i$| Cluster-level query for the $i$-th cluster interacting with the cluster-level key: $Q\\_i = \\mathbf{W}'\\_q (\\sum\\_{s} \\mathbf{C}\\_{si} h\\_{s})$. | \n|$\\kappa_B$| Bi-level kernel used in both N2C-Attn-T and N2C-Attn-L. Combines node and cluster level kernels.  |\n|$\\kappa_C$| Cluster-level kernel function comparing cluster-level queries and keys. |\n|$\\kappa_N$| Node-level kernel function comparing node-level queries and keys. |\n|$\\alpha, \\beta$| Learnable parameters in N2C-Attn-L, weighting the influence of cluster-level and node-level kernels, respectively. |\n|$\\Phi_\\mathrm{B}$| Feature map corresponding to the bi-level kernel $\\kappa_B$|\n|$\\phi, \\psi$| Feature maps corresponding to kernel functions for cluster-level and node-level, respectively.  |\n|$v_t$| Node-level values used in the attention computation. |\n|$\\langle \\cdot, \\cdot \\rangle$| Inner product|\n|$\\otimes, \\oplus$| Operators for the outer product and concatenation|  \n\n> **Q2. 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?**\n\nOur choice of Metis over other graph clustering algorithms was not due to a specific preference (e.g. each partition to have an equal number of nodes); indeed, any method that generates a cluster assignment matrix could substitute Metis. We acknowledge this interchangeability in line 229 of our paper and in the limitation section. \n\nThe main reasons for using Metis in our work are:\n\n1. We selected Graph-ViT [1] as a primary baseline, which employs Metis for subgraph partitioning. To ensure a fair comparison, we followed this setup.\n2. Metis is a well-established graph partitioning algorithm [2], recognized for its efficient implementations and applications in graph learning (e.g. [3]).\n3. Unlike other works that focus on optimizing partitions, our study concentrates on the post-partition phase. Therefore, we preferred a straightforward and common partitioning approach to highlight our advancements in post-partition optimization.\n\n> **Q3. In addition to the node-to-cluster attention, should there also be cluster-to-node attention and cluster to cluster attention?**\n\nThis is an intriguing question. We address it in two parts:\n\n- **Cluster-to-cluster attention** already exists. In our paper, we refer to techniques that consider only the aggregate information of clusters as cluster-to-cluster attention, such as GraphViT. A more detailed explanation is provided in Appendix B.\n\n- Regarding **cluster-to-node attention**, this would involve each node aggregating information at the cluster level during its representation update. The viability of this approach depends on whether the information from the cluster is useful for node-level tasks. Given that node-level tasks often require finer-grained information than what clusters provide, this assumption may not always hold, warranting further experiments and analysis.\n\n\n> **Q4. Figure 3: typo? “positinal”->”positional”**\n\nThank you for pointing out this typo. We will make the necessary corrections.\n\n[1]. He et al. A Generalization of ViT/MLP-Mixer to Graphs. ICML 2023.\n\n[2]. Karypis et al. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM 1998.\n\n[3]. Chiang et al. Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. KDD 2019.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "POeomTuytE", "reviewer": "Reviewer_7EZb", "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.", "questions": "- How do you pick the number of clusters for metis algorithm? \n- What properties does the assignment matrix C hold? For example, do rows sum up to 1?\n- 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?", "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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- Overall, the writing is good and clear.\n- The methodology is clear, and the illustration is great.\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable questions. We provide the following detailed responses to your major concerns.\n\n> **Q1. The only novelty is the dual granularity/resolution/hierarchy attention. The kernelization and the multi-kernel are already investigated.**\n\nWe acknowledge the reviewer's comment regarding the familiarity of kernelization and multi-kernel methods. However, we would like to further elucidate the novelty of our approach:\n1. **Motivation**: In the context where most node clustering-based methods utilize a graph coarsening pipeline—which has its limitations (as illustrated in Fig. 1)—we propose a novel approach for propagating messages between clusters without compressing them. This method allows for deeper interactions between cluster-level and node-level information (as shown in Sec. 3.3).\n2. **Application of Multi-Kernel Learning (MKL)**: While multi-kernel learning is a mature mathematical tool, we are the first to apply the MKL approach to integrate node-level and cluster-level information.\n3. **Implementation**: While kernelization is commonly used to accelerate attention computations, our approach integrates kernelization with a message-passing framework. accelerating the attention computation by propagating the keys and values among the clusters (as illustrated in Fig. 2).\n\nIn summary, while each mathematical tool has been extensively studied before, our application of these mathematical tools is novel and addresses a previously suboptimal aspect of the graph pooling process.\n\n> **Q2. 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.**\n\nIn this paper, our focus is on optimizing clustering-based graph pooling for graph-level tasks. Unlike node-level tasks, graph-level tasks naturally involve graphs of relatively smaller sizes. However, in terms of the number of graphs, the datasets we selected are not \"small-scale.\" (For instance, the OGB MolHIV dataset we used contains 41,127 graphs, which is a considerable size.)\n\nWe chose these datasets because they align with the datasets used in the two most relevant baseline works [1,2] that we compare against, ensuring a fair and consistent evaluation of our method.\n\n> **Q3. How do you pick the number of clusters for metis algorithm?**\n\nIn our experiments, we set the number of clusters for metis as a hyperparameter from $\\\\{4, 8, 16, 32\\\\}$. While this approach of pre-selecting the number of clusters may seem inflexible (as noted in the limitation section), many works in graph pooling (e.g. [1,2,3]) also preset the cluster numbers. \n\nMeanwhile, there are methodologies capable of dynamically adjusting the number of clusters through learning (e.g. [8]). As mentioned in the limitation section, integrating these methods with our N2C-Attn model represents a promising direction for future work.\n\n> **Q4. What properties does the assignment matrix C hold? For example, do rows sum up to 1?**\n\nWe clarify that the concept of cluster assignment matrix $\\boldsymbol{C}$ is not originally defined in this paper but is instead adopted from reference [4]. It is common for the rows of $\\boldsymbol{C}$ to sum up to 1, which can be ensured through a row-wise softmax operation, e.g. [3, 5, 6]. However, configuration where the rows of $\\boldsymbol{C}$ do not sum to 1 is also possible, e.g. [7].\n\nRegarding the properties of $\\boldsymbol{C}$, there are two main points: Firstly, its shape corresponds to [#Num of nodes, #Num of clusters]. Secondly, the element $\\boldsymbol{C}_{ij}$ represents the weight of node $i$ in cluster $j$. These characteristics allow the computation involving $C$, the feature matrix $\\boldsymbol{X}$, and the adjacency matrix $\\boldsymbol{A}$ to simulate the process of graph coarsening (i.e.  $\\boldsymbol{X}^{P} = \\boldsymbol{C}^T \\boldsymbol{X} ;\\quad \\boldsymbol{A}^{P} = \\boldsymbol{C}^T \\boldsymbol{A} \\boldsymbol{C}$).\n\n> **Q5. 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?**\n\nWe understand the reviewer's concern and offer further clarification here. In the N2C-Attn framework, each node is responsible for providing a pair of keys, and similarly, each cluster supplies a pair of queries (line 121, 128). Thus, a natural setup is to have **the number of keys align with the number of nodes** and **the number of queries align with the number of clusters**.\n\nHowever, N2C-Attn considers both cluster-level and node-level information. For nodes within the same cluster, their cluster-level information should be identical (line 119). Therefore, the number of cluster-level keys should be equal to the number of clusters.  Thus we have:\n| Type | # Num |\n|-|-|\n| node-level key| Number of nodes\n| cluster-level key| Number of clusters\n| node-level query | Number of clusters\n| cluster-level query | Number of clusters\n\nIt's important to note that **node-level** or **cluster-level** specifically indicate the belonging to different feature spaces, $\\mathcal{X_N}$ and $\\mathcal{X_C}$, respectively. **Node-level queries** are provided by each **cluster**, not by individual nodes. We hope this clears up any confusion for the reviewer.\n\n\n[1]. He et al. A Generalization of ViT/MLP-Mixer to Graphs. ICML 2023.\n\n[2]. Wu et al. Structural entropy guided graph hierarchical pooling. ICML 2022.\n\n[3]. Bianchi et al. Spectral clustering with graph neural\nnetworks for graph pooling. ICML 2020.\n\n[4]. Liu et al. Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities. IJCAI 2023.\n\n[5]. Ying et al. Hierarchical Graph Representation Learning with Differentiable Pooling. NeurIPS 2018.\n\n[6]. Khasahmadi et al. Memory-based graph networks. ICLR 2020.\n\n[7]. Bacciu et al. A Non-Negative Factorization approach to node pooling in Graph Convolutional Neural Networks. AIIA 2019.\n\n[8]. Song et al. Graph Parsing Networks. ICLR 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We extend our sincere gratitude to the reviewers for their insightful feedback. 

We are delighted to see the comments regarding the paper's **presentation**: "The paper is well written and illustrated" (Reviewer 2taa), its **motivation**: "The paper presents a clear and well-supported motivation for the proposed methodology" (Reviewer azHs), its **theoretical analysis**: "The theoretical claim aligns well with the model's motivation and behavior." (Reviewer Tre7), and its **experimental setup**: "Extensive and diverse experiments demonstrate the model's superior performance and efficiency." (Reviewer Tre7).

We would like to reiterate the main contributions of our work here:
1. **Motivation:** Current clustering-based graph pooling methods primarily follow a graph coarsening pipeline, which has its limitations (as illustrated in Fig. 1). We propose a method that facilitates information propagation between clusters without compressing them. This approach allows for a deep interaction between cluster-level and node-level information (as shown in Sec. 3.3).
2. **Technical Contribution:** We enhance the kernelized attention framework by integrating Multi-Kernel Learning (MKL), allowing for a more nuanced merging of information at both cluster-level and node-level granularities. Additionally, leveraging kernelization techniques, we implement an efficient attention computation method by propagating the aggregated keys and values among clusters.

In the following individual responses, we have addressed the main concerns raised by the reviewers. We are grateful for the reviewers' detailed suggestions. If there are any further questions or comments you wish to discuss, please do not hesitate to reach out.

Meta-review: The paper proposes a new attention mechanism which captures information at both node and cluster levels. The proposed mechanism is novel and it performs well in practice.
Decision: Accept (spotlight)