Learning Invariant Representations of Graph Neural Networks via Cluster Generalization
Authors: Donglin Xia
Xiao Wang
Nian Liu
Chuan Shi
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph neural networks
network representation learning
deep learning
TL;DR: This paper proposes a Cluster Information Transfer mechanism to help GNNs learn invariant representations in the presence of  structure shift problem.

Abstract: Graph neural networks (GNNs) have become increasingly popular in modeling graph-structured data due to their ability to learn node representations by aggregating local structure information. However, it is widely acknowledged that the test graph structure may differ from the training graph structure, resulting in a structure shift. In this paper, we experimentally  find that the performance of GNNs drops significantly when the structure shift happens, suggesting that the learned models may be biased towards specific structure patterns. To address this challenge, we propose the Cluster Information Transfer (\textbf{CIT}) mechanism, which can learn invariant representations for GNNs, thereby improving their generalization ability to various and unknown test graphs with structure shift. The CIT mechanism achieves this by combining different cluster information with the nodes while preserving their cluster-independent information. By generating nodes across different clusters, the mechanism significantly enhances the diversity of the nodes and helps GNNs learn the invariant representations. We provide a theoretical analysis of the CIT mechanism, showing that the impact of changing clusters during structure shift can be mitigated after transfer. Additionally, the proposed mechanism is a plug-in that can be easily used to improve existing GNNs. We comprehensively evaluate our proposed method on three typical structure shift scenarios, demonstrating its effectiveness in enhancing GNNs' performance.

Learning Invariant Representations of Graph Neural Networks via Cluster Generalization
Donglin Xia', Xiao Wang"*, Nian Liu', Chuan Shi!*
BBeijing University of Posts and Telccommunications
"Behhang University
fdonglin.xia xia, nianliu, (axchuanSSbupp edu. cn, siio__aan@hbiue edu,
Abstract
Graph neural networks (GNNs) have become increasingly popular in modeling graph-structured data due to their ability to learn node representations by aggregat- ing local structure information. However, it widely acknowledged that the test graph structure may differ from the training graph structure, resulting a structure shift. In this paper, experimentally find that the performance of GNNs drops sig- nificantly when the structure shift happens, suggesting that the learned models may be biased towards specific structure patterns. To address this challenge, we propose the Cluster Information Transfer (CIT) mechanism which can learn invariant representations for GNNs, thereby improving their generalization ability various and unknown test graphs with structure shift. The CIT mechanism achieves this by combining different cluster information with the nodes while preserving their cluster-independent information. By generating nodes across different clusters, the mechanism significantly enhances the diversity of the nodes and helps GNNs learn the invariant representations. We provide theoretical analysis of the CIT mechanism, showing that the impact of changing clusters during structure shift can be mitigated after transfer. Additionally, the proposed mechanism is a plug-in that can easily used to improve existing GNNs. We comprehensively evaluate our proposed method on three typical structure shift scenarios, demonstrating its effectiveness enhancing GNNs' performance.
Introduction
Graphs are often easily used to model individual properties and inter-individual relationships, which ubiquitous in the real world, including social networks, e-commerce networks, citation networks. Recently, graph neural networks (GNNs), which are able to effectively employ deep learning on graphs to learn the node representations, have attracted considerable attention in dealing with graph data
13 24 32 36 9 [ So far, GNNs have been applied to various applications and achieved remarkable
performance, e.g., node classification 13 32
link prediction 33 14
and graph classification 6 34
Message-passing mechanism forms the basis of most graph neural networks (GNNs) [3] 24 5
That is, the node representations are learned by aggregating feature information from the neighbors in each convolutional layer. So it can be seen that the trained GNNs are highly dependent on the local structure. However, it is well known that the graph structure in the real world always changes. For instance, the paper citations and areas would go through significant change as time goes by in citation network [II]. In social networks, nodes represent users and edges represent activity between users, because they will be changed dynamically, the test graph structure may also change [7]. This change in the graph structure form of distribution shift, which refer graph structure shift. So
"Corresponding authors. "Code available https//gghhhlccomm//UU.GCGAAAAA
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the question naturally arises: when the test graph structure shift happens, can CNNs still maintain stability in performance?
We present experiments to explore this question. We generate graph structure and node features. Subsequently we train GNNs on the initially generated graph structure and gradually change the structures to test the generalization of GNNs (more details are in Section Clearly, the performance consistently declines with changes (shown in Figure D. implying that the trained GNNs are severely biased to one typical graph structure and cannot effectively address the structure shift problem.
This can also be considered performance, most GNNs require the training and test graphs to have identically distributed data. However, this requirement cannot always hold in practice. Very recently, there are some works on graph OOD problem for node classification. One idea assumes knowledge of the graph generation process and derives regularization terms to extract hidden stable variables 288 g However, these methods heavily rely on the graph generation process, which is unknown and may be very complex in reality. The other way involves sampling unbiased test data to make their distribution similar to that of the training data [37]. However, it requires sampling test data beforehand, which cannot be directly applied the whole graph-level structure shift, e.g., training the GNNs on a graph while the test graph is another new one, which is a very typical inductive learning scenario 24 17
problem (OOD) graph. To ensure good
Therefore, it is still technically challenging to learn the invariant representations which is robust to the structure shift for GNNs. Usually, the invariant information can be discovered from multiple structure environments (28). while we can only obtain one local structure environment given a graph. To avoid GNNs being biased to one structure pattern, directly changing the graph structure, e.g., adding or removing edges, may create different environments. However, because the graph structure is very complex in the real world and the underlying data generation mechanism is usually unknown, it is very difficult to get the knowledge on how to generate new graph structures.
In this paper, we propose to learn the invariant representations of GNNs by transferring the cluster information of the nodes. First, we apply GNNs to learn the node representations, and then combine it with spectral clustering to obtain the cluster information in this graph. Here, we propose a novel Cluster Information Transfer (CIT) mechanism, because the cluster information usually captures the local properties of nodes and can be used to generate multiple local environments. Specifically, characterize the cluster information using of cluster, and transfer the nodes to new clusters based on these two statistics while keeping the dlustrrinndeenndee information. After training GNNs on these newly generated node representations, we aim to enhance their generalization ability across various test graph structures by improving the generalization ability on different clusters. Additionally, we provide insights into the transfer process from the embedding space and theoretically analyze the impact of changing clusters during structure shift can be mitigated after transfer. The contributions of our work are summarized as follows:
statistics: the mean of cluster and the variance
We study the problem of structure shifts for GNNs, and propose a novel CIT mechanism to improve the generalization ability of GNNs. Our proposed mechanism is friendly plug-in, which can be casily used to improve most of the current GNNs.
Our proposed CIT mechanism enables that the cluster information can be transferred while preserving the innseer-nddeeendent information of the nodes, and we theoretically analyze that the impact of changing clusters during structure shift can be mitigated after transfer.
We conduct extensive experiments on three typical structure shift tasks. The results well demonstrate that our proposed model consistently improves generalization ability of GNNs on structure shift.
2 Effect of structure distribution shift on GNN performance
In this section, we aim to explore the effect of structure shift on GNN performance. In the real world, the tendency of structure shift is usually unknown and complex, so we assume a relatively simple scenario to investigate this issue. For instance, we train the GNNs on graph with two community structures, and then test the GNNs by gradually changing the graph structures. If the performance of GNNs drops sharply, it indicates that the trained GNNs are biased to the original graph, and cannot be well generalized the new test graphs with structure shift.

---

We generate network with 1000 nodes and di- vide all nodes into two categories on average, that is, 500 nodes are assigned label O and the other 500 nodes are assigned label 1. Meanwhile, node features, each of 50 dimensions, are generated by two Multivariate Gaussian distributions. The node features with same labels are generated by same Gaussian distribution. We employ the Stochas- tic Blockmodel (SBM) [2) to generate the graph structures. We set two community and set the gen- eration edges probability on inter- ciler-community is 0.5% and intro-community is 0.05%. We ran- domly sample 20 nodes per class for training, and the rest are used for testing. Then we train GCN [33 and GAT (4) this graph. The test graph structures are generated as follows: we decrease the inter-community edge probability from 0.5% to 0.25% and increase the intra-community probability from 0.05% to 0.3%.
0.95
APPNP
GCNI
Accurscy
0:85
0.80
0.70
0.5 0.05
0.45
0.1
0.4
0.15
0.95 0.
0.3 0.25 0.5 0.3
Probabiiity of edges
Figure 1: GCN, GAT, APPNP and GCNII on generated data with structure shift. The x-axis is probability of edges (%).
The node classification accuracy of
The accuracy is shown in Figure I The x-axis is the probability of edges, where the first number is the edge probability of inter-communnty and the second number is the edge probability of intro- community. As significantly. It shows that once the test graph pattern shifts, the reliability of GNNs becomes compromised.
see, because of the structure shift, the performance of GNN declines
3 Methods
Let = (A, X) represent training attributed graph, where A E R"x* is the symmetric adjacency matrix with n nodes and X E Rxd is the node feature matrix, and d is the dimension of node features. Specifically, Au = I represents there is an edge between nodes i and j. otherwise, AÚ O. We suppose each node belongs to one of C' classes and focus on semi-supervised node classification. Considering that the graphs always change in reality, here we aim learn the invariant representations for GNNs, where the overall framework is shown in Figure and the whole algorithm shown in A.1
Notations:
3.1 Clustering process
We first obtain the node representations through GNN layers:
n o (D AD Z
1/2 11/2
1/2 (1
GNN).
(1-1)
(I)
where ( is the node representations from the 1-th layer, ( = = is the degree
matrix of A, is a non-linear activation and WGNN is the trainable parameters of GNNs. Eq. I implies that the node representations will aggregate the information from its neighbors in each layer, so the learned GNNs are essentially dependent the local structure of each node. Apparently, if the structure shift happens in the test graph, the current GNNs may provide unsatisfactory results. Therefore, it is highly desired that the GNNs should learn the invariant representations while structure changing. so as to handle the structure shift in test graphs.
One alternative way is to simulate the structure change and then learn the invariant representations from different structures, which similar as domain generalization 266 33 Motivated by this, we consider that the local properties of node represents its domain information. Meanwhile, different clusters can capture different local properties in a graph, so we can consider cluster information as domain information of nodes. Based on this idea, we first aim to obtain the cluster information using spectral clustering (2). Specifically, we compute the cluster assignment matrix S of node using a multi-layer perceptron (MLP) with softmax on the output layer:
S = Softmax W WMLPZ + b).
(2)
3

---

Graph Neural Networks
Input
2
2
4 by + dgh
Cluster Information Transfer (CIT) mechanism
Every & epochis
Ly b. Po
Spectral clustering
Transfer claster
New represcntations
Figure 2: The overall framework of our proposed CIT mechanism on GNNs consists two parts: the traditional GNNs and Cluster Information Transfer (CIT) mechanism. After getting node representa- tions from GNNs, we conduct CIT mechanism on node representations before the last layer of GNNs, which transfers the node to another cluster to generate new representations for training.
where W WLLP and are trainable parameters of MLP. For assignment matrix S E R and m the number of clusters. Sij represents the weight that node belongs cluster The softmax activation of the MLP guarantees that the weight 8iy E [0, 1] and S I 1x.
For S, we want to cluster strongly connected nodes. So we adopt the cut loss which evaluates the mincut given by S:
Tr(S"
C.
Tr(S" DS)
where Tr is the trace of matrix. Minimizing Le encourages the nodes which are strongly connected to be together.
However, directly minimizing f. will make the cluster assignments are equal for all nodes, which means all nodes will be in the same cluster. So in order to avoid the clustering collapse, we can make the the clusters to be of similar size, and we use orthogonality loss to realize
C. = S
IM M
(4)
S
where || indicates the Frobenius norm, M is the number of clusters. Notably, when S = Ias the orthogonality loss L. will reach O. Therefore, minimizing it can encourage the cluster assignments to be orthogonal and thus the clusters can be of similar size.
Overall, optimize the clustering process by these two losses:
L, = L. + A1
(5)
where A₁ is a coefficient to balance the mincut process and orthogonality process. After obtaining the assignment matrix S, we can calculate cluster representations H by average the node representations Z (
H = OT
(6)
3.2 Transfer cluster information
Now we obtain the cluster representations H., and each cluster captures the information of local properties. Originally, given graph, node can be only in one domain, i.e., one cluster. Next, we aim transfer the node to different domains. Specifically, the cluster information can characterized by two statistics, i.e., the center of the cluster (H") and the standard deviation of the cluster (o (o)))))

---

H V
8ik (Z H Di=
(7)
where H is the representation of the k-th cluster and z is the representation of node i.
Then we can transfer the node in the k-th cluster to the j-th cluster as follows:
H H
(8)
where & the cluster that node belongs to, and is the cluster which randomly selected from the remaining clusters.
Here, we explain the Eq. (8) in more details.
shown in Figure 3 the center of cluster k is H and node belongs this cluster, where the rep- resentation of node is _ It can be seen that Hg is obtained by aggregating and averaging the local structure information, which captures the cluster information. Therefore, z, H. repre- sents the cluster-independent information. Then, the CIT mechanism can be seen we trans- fer the node to a new position from embedding space. The standard deviation is the weighted distance of nodes from the center, which is the aggregating scope of the clusters. After the transfer, the target node surrounds new cluster with new cluster information, while keeping the cluster-independent information.
Pj
tranker prosess
We show two parts one graph. The orange and green points represent two clusters in one graph. The circle aggregating scope of clus- ter. And the red point represents the target node we transfer from orange cluster to green cluster.
Figure 3:
The above process only transfers the nodes on the original domain. Moreover, in order improve the robustness of the model for unknown domain, we increase the uncertainty and diversity of model 16 21.. Based this, we add Gaussian perturbations to this process. The whole transfer becomes:
H
( (oHH) + 6 E.
(H) + EpE
(9)
(H
The statistics of Gaussian is determined by the whole features:
6 ~ (N,, ~ ((0,
(10)
3 = (0 23 - Here, with the Gaussian perturbations, we can generate new clusters based on the original one and the nodes can be further transferred to more diverse domains.
(11)
The proposed transfer process offers solution overcome the limitations of changing graph structures when generating nodes in different domains. Traditional approaches require changing the graph structure by adding or deleting edges, which can be challenging due to the lack of prior knowledge on how the changes in graph structure may affect the domain. Here, our proposed CIT mechanism addresses this challenge by directly transferring a node to another domain through the manipulation of cluster properties of nodes in the embedding space. The CIT method is implemented before the classifier in GNNs training, making it backbone agnostic and compatible with any GNN last layer.
3.3 Objective function
With CIT mechanism, we have the generated representation z,(0) in other clusters for node i. In traditional GNNs training, we input the representation Z where the i-th row vector represents the representation of node i, to the cross-entropy loss [3] Here, we randomly select part of nodes, and obtain the new representation matrix (1) and optimize the cross-entropy loss based on it as follows:
replace original representation ( with the generated representation z,(1) Then
C, (z Y),
(12)
5

---

where Le is cross- eross-y loss function, fo is the classifier, and Y is the labels. Finally, the overall optimization function is follows:
L f + X2hu,
(13)
where X2 is a coefficient to balance the classification process and clustering process. In the optimiza- tion process, randomly select p nodes and then conduct Eq. (9) every k epochs.
3.4 Theoretical analysis
In this section, we theoretically analyze our CIT mechanism from the perspective of domain adoption theory. Since the Eq. (8) is the cornerstone of our CIT mechanism and Eq. (9) is an extending from it,
we use Eq. (8) to represent our CIT mechanism in the following proof for convenience.
We analyze that the classifier using the new generated representation z Eq. (8) has better generalization the structure shift. As mentioned before, cluster information can capture local properties nodes, so we convert this problem to analyzing the classifier has better generalization on cluster shift. To achieve this, following [3T], we take the binary classification task the example, and analyze the relationship between the decision boundary with cluster information. For analysis, follow [II using& fisher classifier and analyse the relationship between them. According to Fisher's 's linear discriminant analysis 23,33, the decision boundary fisher classifier depends on two statistics Var Var(2 ()) and Cov Y).
Theorem 1. The decision boundary of fisher classifier is affected by the cluster information.
The proof is given in Appendix A.3 where we calculate the mathematical expression of the classifi- cation boundary. Theorem indicates that the cluster information will "help" the classifier to make decisions. But when the graph structure changes, the cluster information the nodes also changes. Therefore, the classifier using cluster information to make decisions is not reliable.
Theorem 2.
Let R represent the node representations in cluster R. Assume that there are percent of nodes are transferred from cluster R to cluster D by Σp Zu-ua + u.D. After the transfer, the impact of changing clusters during structure shift can be miligated.
F.R
The proof given in Appendix A.4 Comparing the expression of classifier before and after our CIT mechanism, we can find that we mitigate the impact of changing clusters during structure shift, enhancing the robustness of the model against such changes.
Experiment
Datasets and baselines. To comprehensively evaluate the proposed CIT mechanism, use six
diverse graph datasets. Cora, Citeseer, Pubmed [20), ACM, IMDB [27 and Twitch- Twitch-Explicit [I7].
Details of datasets in Appendix [.. Our CIT mechanism can be used for any other GNN backbones. We plug in four well-known graph neural network methods, GCN [33, GAT (24). APPNP 9 and GCNII (5). Meanwhile, we compare it with graph OOD methods which also used for code-llassffication, SR-GNN (37 and EERM (28. We combine them with four methods mentioned before. Meanwhile, added.
CIT-GNN(W/O) to indicate that no Gaussian perturbations
Experimental setup. For Cora, Citeseer and Pubmed, we construct structure shift by making perturbations on the original graph structure. For ACM and IMDB, we test them using two relation structures. For Twitch-Expi Explicit, network to validate and the rest networks to test. So we divide these datasets into three categories: perturbation graph structures, Multiplex networks and Multigraph. The implementation details are given Appendix B.
six different networks. We take network to train, one
4.1 Perturbation on graph structures data
In this task, we use Cora, Citeseer and Pubmed datasets. We train the model on original graph. We create new graph structures by randomly adding 50%, 75% and deleting 20%, 50% edges of original graph. To comprehensively evaluate our model random structure shift, we test model on the

---

Table 1: Quantitative results (%to) node classification for perturbation graph structures data while the superscript refers to the results of paired t-test between original model and CIT-GNN (* for 0.05 level and ** for 0.01 level).
ADD
Method
Corn
Clesser
Puhmed
Macro-11
Acc
Macro-TI
Acc
Macro-T1
GCN
76.1240.91
74,9520.88
65,4320.68
63.02=0.59
71.841100
SR-GCN
75.7010.90
74.35a0.85
66.03&1.30
62.67.0.80
72.15a1.80
70.6341.9
HERM-
75.33+0.87
74.39+0.89
04.0540.49
60.97=0.11
(FFG)N((W7)
76.8816.54
73.63.0.37
06.67166.5"
64.2120.47
7283:033
12.01-0.21
GTT
76.9819.49
75.88+0.44"
67.6540.44
64.42=0.10"
73.7620.40"
72.94=0.30
GAT
77.0430.30
76.1520.40
64,4230.41
61.742030
71.3030.22
70.80:0.43
SR GAT
77.3540.75
76.4910.77
8040.92
61.98.0.11
71.5540.52
70.7910.64
EERM-GAT
76.1520.38
75.32=0.29
62.0550.79
59.01=0.65
77.37+0.57
76.73=0.47
66 23:0.58
63,3020.67
719250088
2102-0336
CTT-GAT
77,23+0.42
76.26+0.28
66.33+0.24"
63.07=0.37
72.50=0.74
71.57=0.82
APPNP
79,54+0.50
77.69#0.70
66 96
08440.66
75 75.880881
75.37=0.66
SR-APPNP
80.00#0.70
78.5620.87
65 20
62.77=0,36
75.85=0.55
75,43=0.58
BERM-APPNZ
78.1010.73
76.72+0.69
36.3010.91
63.0820.77
C]FAPPNN(W/))
79. 79.7990.40
71.5=0032
68 06:0.52
65. 30=0.32
15,23=0037
CTT-APPNP
80.50:0.39"
78.86=0.24"
68.54:0.71
65.51=0.45
76.6420.40"
75.89=0.48'
GCNII
76.9860992
74.92=0997
63.16:1 222
61.1420.78
74.03=1.10
13.37=0.75
SR GCNH
77.5540.211
75.09:0.41
64.74+1.86
1.544=1.53
75. 10.1040.78
74.36=0.95
79.05+1.10
76.62+1.23
10+0.64 64
62.02=0.76
CIT GCN](
77.6410.63
75.22a0.61
65 8740.80
63.3620.75"
75.0030.47
74.70=0.54
CIT-GCNII
78.2840.88
75.82=0.73
66.12+0.97
67.17.0
75.95#0.63
75.47=0.76
0.5
GCN
72.3750.55
7100920.36
63.3420.60
61.0950.54
12.4820.31
71.0620.58
SR BR-GON
72.70&1.10
12.1911.20
62.7241.80
59.5812.10
70.35a2.10
69. 19.14
HERM-GCN
72.3040.21
71.68+0.47
61 6540..54
58.55=0.68
CTFGCN(W])
72.9010.53"
71.7010.77
64.8310:79
62.3320.56
75:0010:46
72,3020.36
CTT-GCN
74.44+0.75'
73.37=0.86"
64.80+0.65'
62.52+0.46'
73.20=0.36
72.33+0.41"
GAT
73.86+0044
72.79=0.47
63.4241.00
61.3550.79
70.88=0.67
69.9750.64
SR-GAT
74,28+0.28
73.4620.43
64.27#1
62.04=0.90
70.3620.69
69.24=0.88
EERM-GAT
72.6210.43
72.28+0.30
02.0010.43
60.30=0.50
74.6440.77
73.76=0.87
63 8330.79
62,35-0.50
700000777
69730=0036
CTT-GAT
74.75:0.40"
73.67=0.58'
64.74+0.67
62.23+0.77'
71.90:0.89
70.88=0.67
APPNP
75.86:0.84
73.97=0.87
71:1100011
83.65
74.33+0.77
73.99=0.8 80
SR-APPNP
76.00#0.30
73.98=0.40
64.80+0.37
62, 02.7820.21
75 75.4020.58
74.30=0.06
HERM-APPNP
75.30+0.65
74.87+0622
64.90+0.99
62.32+0.60
CTT APPNP(O))))
77.5340.67
75.6610.54
67 01.0010..81
64.7810.73
76.0520.87
75.91
CIT-APPNP
78.02+0.56'
76.53+0.78"
66.06:40.95'
63.11=0.58
75. 75.7044.41
75.88=0.83
GCNII
73.16EL05
11.011.399
62,481122
60.0000.40
15.7810.58
15.1510.61
SR GUNI
75.0340.50
72.28=0.93
60.0042.1 10
59.00= 80
75.98+1.10
75.79=0.90
BERM-GCNII
75,50+1
73.60+1.30
40:0.97
59.11=0.81
CIT GCN)I(w/))
74.6440.63
72.84.0.87
64.5840.87
62.4720.69
75.78
74.20=1.10
CIT-GCNII
77.08+1.22"
75.15+1.45"
65.82+1.04"
63.27=0.73"
76.13+1.12
75.99=1.17
new graphs. We follow the original clasiiiassiiiiation settings (13 and use the common evaluation metrics, including Macro-Fl and classification accuracy. For brief presentation, we show results of deleting edges in Appendix B.2
The results are reported in Table From the table we can see that the proposed CIT-GNN generally achieves the best performance in most cases. Especially, for Acc and Macro-fl, our CIT-GNN achieves maximum relative improvements of 5.35% and 4. 1% respectively on Sitesser-Add-O.. The results demonstrate the effectiveness of our CIT-GNN. We can also see that CIT-GNN improves the four basic methods, so the results show that our method can improve the generalization ability of the basic models. Mcanwhile, level, which can be used for any GNN backbones.
mechanism is to operate the node representation at the embedding
4.2 Multiplex networks data
In this task, we use Multiplex networks datasets ACM and IMDB to evaluate the capabilities of our method on different relational scenarios. Both of them have two relation structures. We construct structure shift by taking the structure of one relation for training and the other for testing respectively. The partition of data follows (27] The results are reported in Table and the relation structure shown in the table is the training structure. Different from the first experiment, the structure shift is not random, which more intense because the new graph is not based on the original graph. As can be seen, our proposed CIT-GNI improves the four basic methods in most cases, and outperforms
7

---

Table 2: Quantitative results (%to) node classification for multiplex networks data and the relation
in table is for training, while the superseript refers to the results of paired t-test between original model and CIT-GNN (* for 0.05 level and ** for 0.01 level).
ACM
IMDB
Metho
MDM
Acc
Macro-fl
Acc
Macro-f1
Acc
Macre-f1
Aec
Macro-f1
GCN
61.651191
60.662188
80.261 98
79,7121
52. 3621.00
48 15.55.
58.98E1.1
17.01
SR-GON
67.75a1.220
68.51
81.88&2.33
91.9470.97
50.7620.85
39.84a108
18.21
BERM-GCN
66.8811.87
67 07.84-1.54
82.16+1.88
82.16+1 57
$4.07=1833
80=1.62
57.21+1.90 13
56.52=1.66
CN-GGNNWAO
67 53.5521.52
65 32:1.95
31.3011.88
30.98+1 82
55,6751.79
30.7131.56
57,93+1.32
56,2361.24
68.0621.33
68.79.1.27
82.67.1.55'
82.5611.66
52.75a1.65"
56.6841445
$4.664197
GAI
66 36.352188
64:2322.25
82.4811.73
82,5011 165
$1.3111.13
48.2621.27
58.441187
57.7221.94
SR-GAT
1..20=1.87
67 13
84.61+1.34
84.4941 .65
50.81 1.92
16.62=1.73
59.05a1.57
57.42a1.84
79,25+1.00 1.27
50.86-1.35
57.25=1.50
67 15:1.25
44
83,4541.9
X3.01 46
53.91 20.96
51.90
S7.18+1 35
56.82:1.22
CIT-GAT
68. 1..32
68.15.1.39
85.75&1.76"
85.64:1.32
52. 86.0669
11.06.1.01
59.5141.73
18.40:1.46
APPNP
18 39
19.0021.56
86.76E
86.74E1
51.7821.01
46.5721.22
62.01
61,3421.30
SR-APPNP
77.8021
76.25
86. 162
164
$5.02&1.96
$1.74a2.03
60.70
60.14
EERM-APPNP
80 8921
80.43:1.65
83.5841158
83.464 84
54.3220.90
11.03:107
61.27a1.75
60.30
API-APPR)
66
81335:1011
96,008098
86.5240.87
56.37:1.411
54.13:1.78
6038:11:00
CIT APPNP
816021477
87.1911.21
87.16:1.022
55 1.55
$2.32a1.73
62.50:1445
62.00:1.54
GCNII
17.9211.64
16.73=1.77
81,88+ 085
81,21
52.71=1.86
17.08
52.45+2011
47.61=2.35
SR-GUNII
18.11
78.77:1.76
84.32+0
83,22+1
13.52=1.56
49.87=1.36
54,2042.5
49,00=1.0
BERM-GCNII
78.8221.23
79.2121.76
838111121
83.6111 02
53.5621.25
50.27:1.42
54.32:1.98
49.70:187
78. 10: 1.54
84884141
62t11
33.42-2001
52,30+1
48.01=2.10
CIT-OCNII
79.73=1.61
79.26=1.32"
85,23&1.93"
85, 85.06&1.89
54.20
50.91a1.95
53.6911.80 89
48.8422.01
Original
ROc AUC
ROc-AII
Roc
(a) DE
(b) ENGB
ES
(d) RU
Figure 4: ROC-AUC on Twitch where we compare different GNN backbones.
SR-GNN and EERM, implying that our CIT-GNN can improve the generalization ability of the basic models.
4.3 Multigraph data
In this task, we use Multigraph dataset Twitch-Explicit, and its each graph is collected from particular region. this dataset, the node features also change but they still share the same input feature space and output space. The graphs are collected from different regions. So different structures are determined by different regions. To comprehensively evaluate our method, we take the FR for training, TW for validation, and test our model on the remaining four graphs (DE, ENGB, RS, EU). We choose ROC-AUC score for evaluation because is a binary classification task. Since SR-GNN not suitable for this dataset, only the base model and EERM are compared. The results are reported in Figure 4 Comparing the results on four graph, our model makes improvement in most cases, which verifies the effectiveness about generalizing on multigraph scenario.
4.4 Analysis of hyper-parameters
Analysis of p. The probability of transfer determines how many nodes to transfer every time. It indicates the magnitude of the CIT mechanism. We vary its value and the corresponding results are shown in Figure 5] With the increase of the performance goes up first and then declines, which indicates the performance benefits from an applicable selection of p.
Analysis of k. We make transfer process every k epochs. We vary & from to 50 and and plot the results Figure 6 Zero represents the original model accuracy without out CIT mechanism. Notably, the performance remains consistently stable across the varying values of k. indicating the robustness of the model to this parameter.
8

---

CIFGCN
CITAPAIP DINGEN
CIT-CON CIF-CX
CIRARPMP
CITGCN
CITAPAN CINGENI
CIT-GEN
CTEAPPP
CISOOI
Pobobiiity turoker
Probuaiity trenaner
The Cox-timo
The Esosteaess
(a) cora-add-0.5
(b) citeseer-add-0.3
(a) cora
(b) citeseer
Figure 5: Analysis of the probability transfer.
Figure 6: Analysis the epochtimes.
Analysis of m. The number of clusters is the most important parameter in the clustering pro- cess. We choose silhouette coefficient to mea- sure the clustering performance and vary m from 20 to 100 unevenly. Then we calculate the accuracy and Silhouette Coefficient. The corresponding results are shown in Figure 7 As we can see, accuracy changes synchronously with silhouette coefficient. We infer that the performance of our model is related the clus- tering situation, and when the clustering process performs well, our model also performs well.
Aconnty
3.70
3.60
3.75
3.55
0.2
626
615
645
3.2
6:10
3.22
000
0.5
20
160
FUrTECT cholocs
clulico
(a)
(b) citeseer
Figure The number of clusters is varying on cora and citeseer. The accuracy corresponds to the right vertical axis, while the Silhouette Coefficient values correspond to the left vertical axis.
Related work
Graph neural networks. Recently, Graph Neural Networks have been widely studied. GCN proposes to aggregate the node features from the one-hop neighbors. GAT [24] designs an attention mechanism to aggregate node features from neighbors. PPNP [9] utilizes PageRank's node propagation way to aggregate node features and proposes an approximate version. GCNII [5] extends GCN by introducing two effective techniques: initial residual and identity mapping, which make the network deeper. This is fast growing research field, and more detailed works can be found in
13
4 (2).
OOD generalization of GNNs. -i--ttiiitiiittiion (OOD) on graph has attracted considerable [8] shows node selection bias drastically
attention from different perspectives. For affects the performance of GNNs and investigates it from point view of causal theory. [37] explores the invariant relationship between nodes and proposes framework account for distributional differences between biased training data. 28 handles by minimizing the mean and variance of risks from multiple environments which are generated by adversarial context generators. For graph classification, [15] proposes to capture the invariant relationships between predictive graph structural information and labels in mixture of latent environments. (29 [8] find invariant subgraph structures from a causal perspective to improve the generalization ability of graph neural networks. [10] builds graph OOD bench mark including node-level and graph-level methods and two kinds of distribution shift which are covariate shift and concept shift.
Graph clustering with graph neural networks. As graph neural networks continue to perform better in modeling graph data, some GNN- based graph clustering methods have been widely applied. Deep attentional embedded graph clustering (25] uses attention network capture the importance of the neighboring nodes and employs the KL-divergence loss in the process graph clustering. 2 achieves the graph clustering process by obtaining the assignment matrix through minimizing optimizing its spectral objective. [19] uses a new objective function for clustering combining graph spectral modularity maximization and new regularization method.
Conclusion
In this paper, we explore the impact of structure shift on GNN performance and propose CIT mechanism help GNNs learn invariant representations under structure shifts. We theoretically analyze that the impact of changing clusters during structure shift can be mitigated after transfer.

---

Moreover, the CIT mechanism is friendly plug-in, and the comprehensive experiments well demonstrate the effectiveness on different structure shift scenarios.
Limitations and broader impact. One potential limitation lies its primary focus on node-level tasks, while further investigation is needed to explore graph-level tasks. Although CIT mechanism demonstrates significant advancements, certain theoretical foundations remain to be fully developed. Our work explores the graph from the perspective of the embedding space, thereby surpassing the limitations imposed by graph topology, and offers a fresh outlook on graph analysis.
Acknowledgments and Disclosure of Funding
This work is supported in part by the National Natural Science Foundation of China (No. U20B2045, 62192784, U22B2038, 62002029, 62172052, 62322203).
References
[1] Theodore Wilbur Anderson. An introduction to multivariate statistical analysis. Technical report, Wiley New York, 1962.
[2] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International Conference on Machine Learning, pages 874-883. PMLR, 2020.
[3] T Tony Cai and Linjun Zhang. A convex optimization approach to high-dimensional sparse quadratic discriminant analysis. The Annals of Statistics, 49(3)1537-1158, 2021.
[4] Hongxu Chen, Hongzhi Yin, Tong Chen, Quoe Viet Hung Nguyen, Wen-Chih Peng, and Xue Li. Exploiting centrality information with graph convolutions for network representation learning. In 2019 IEEE 35th International Conference on Data Engineering (ICDE), pages 590-601. IEEE, 2019.
[5] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pages 1725-1735. PMLR, 2020.
[6] Federico Emrica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. arXiv preprint
2019.
[7] Shobeir Fakhraei, James Foulds, Madhusudana Shashanka, and Lise Getoor. Collective spammer detection in evolving multi-relational social networks. In Proceedings of the 21 acm sigkdd international conference on knowledge discovery and data mining, pages 1769-1778, 2015.
[8] Shaohua Fan, Xiao Wang, Chuan Shi, Kun Kuang, Nian Liu, and Bai Wang. Debiased graph neural networks with agnostic label selection bias. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[9] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint axXiv://100005997, 2018.
[10] Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji. Good: A graph out-of-distribution benchmark. arXiv preprint arXiv:2206.00455 2022.
[11] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 03:22118-22 1211138, 2020.
[12] Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical review E, 83(1):016107, 2011.
[13] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional 2016.
networks. arXiv preprint
10

---

[14] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016.
[15] Haoyang Li, Ziwei Zhang, Xin Wang. and Wenwu Zhu. Learning invariant graph representations for out-of -fittr-diittibttionn generalization. In Advances in Neural Information Processing Systems, 2022.
[16] Xiaotong Li, Yongxing Dai, Yixiao Ge, Jun Liu, Ying Shan, and Ling- Yu Duan. Uncertainty modeling for
generalization. arXiv preprint arXiv:2202.03958, 2022.
[17] Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non-homophilous graphs. arXiv preprint arXiv:2 (00:22204.1404, 2021.
[18] Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In International Conference on Machine Learning, pages 15524-15544 PMLR, 2022.
[19] Emmanuel Müller. Graph clustering with graph neural networks. Journal of Machine Learning Research, 24:1-21, 2023.
[20] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. magazine, 29(3):93 93, 2008.
the [21] Yichun Shi and Anil K Jain. Probabilistic face embeddings. In Proceedings the IEEE/CVF International Conference on Computer Vision, pages 6902-6911, 2019.
[22] Damien Teney, Lingqiao Liu, and Anton van Den Hengel. Graph- strpc-str representations for visual question answering. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1-9, 2017.
[23] T Tony Cai and Linjun Zhang. High dimensional linear discriminant analysis: optimality, adap- tive algorithm and missing data. Journal of the Royal Statistical Society: Series (Statistical Methodology), 81 (14))675--755 2019.
[24] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 17 10. 10903, 2017.
[25] Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chengqi Zhang. Attrbuueed graph clustering: A deep attentional embedding approach. arXiv preprint arXiv: arXiv:/906.00 1906.0633, 2019.
[26] Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Tao Qin, Wang Lu, Yiqiang Chen, Wenjun Zeng, and Philip Yu. Generalizing to unseen domains: A survey on domain generaliza- tion. IEEE Transactions on Knowledge and Data Engineering, 2022.
[27] Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. Het- erogeneous graph attention network. In The world wide web conference, pages 2019.
[28] Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective. arXiv preprint arXiv:2202.02466, 2022.
[29] Ying-Xin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. arXiv preprint arXiv:2201. 2022.
[30] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi supervsee learning with graph embeddings. In International conference machine learning, pages 40-48. PMLR, 2016.
[31] Huaxiu Yao, Yu Wang, Sai Li, Linjun Zhang, Weixin Liang, James Zou, and Chelsea Finn. Im- proving out-of-distribution robustness via selective augmentation. In International Conference on Machine Learning, pages 25407-25437. PMLR, 2022.
[32] Jiaxuan You, Zhitao Ying, and Jure Leskovee, Design space for graph neural networks, Advances in Neural Information Processing Systems, 33: 17:17, 2020.

---

[33] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems. 31, 2018.
[34] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
[35] Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy. Domain generalization 2021.
in vision: A survey. arXiv preprint
[36] Meiqi Zhu, Xiao Wang. Chuan Shi, Houye and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In Proceedings of the Web Conference 2021, pages 1215-1226, 2021.
[37] Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi Shift-robust gnns: Overcoming the limitations of localized graph training data. Advances in Neural Information Processing Systems, 34:27965-27999 2021.
12


Reviews:
[{"review_id": "pPaZJpBXWF", "reviewer": "Reviewer_QyZE", "summary": "The paper introduces a novel Cluster Information Transfer (CIT) mechanism to enhance the generalization capability of Graph Neural Networks (GNNs) in the presence of structural shifts. The authors provide theoretical analysis, showing that the impact of cluster information on the classifier diminishes during transfer. They demonstrate that the CIT mechanism can be easily incorporated into existing models and showcase its effectiveness through extensive experiments. Overall, the paper highlights the value of the CIT mechanism in improving GNN generalization and supports its claims with comprehensive empirical evidence.", "questions": "- In Section 2, the authors focus on presenting results specifically for the GCN and GAT models, but they do not mention the evaluation of other GNN models. It would be beneficial for the authors to clarify if they have considered or conducted experiments with other GNN models as well.\n- The authors introduce different structure shifts in their experiments, but it would be helpful to provide a clearer distinction between their approach and the OOD graph benchmarks proposed in [1]. Additionally, the paper could benefit from providing standard settings for structure shifts and including information on the label rate used in training the models.\n- There are several typos in the paper, such as \"less affect\" in line 321, \"bulids\" in line 315, and \"Initial residual and Identity mapping two effective techniques on GCN\" in line 305. These errors should be addressed to improve the clarity and accuracy of the paper.\n\n[1] Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji. Good: A graph out-of-distribution benchmark. arXiv preprint arXiv:2206.08452, 2022.", "limitations": "The authors have discussed the limitation and potential negative societal impact.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The paper includes both theoretical analysis and numerical results, providing a well-rounded evaluation of the proposed approach.\n- The idea presented in the paper is clear and well-motivated, addressing an important problem.\n- The experiments conducted in the paper are extensive and provide convincing evidence to support the claims made by the authors.", "weaknesses": "- The experiments in section 2 are not sufficient.\n- The descriptions of the experimental settings are unclear and could benefit from more detailed and precise explanations.\n- There are some typos present in the paper that should be addressed for improved clarity and readability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. > Q1：More GNN results\n\nThanks for the suggestion. We evaluate another two popular GNNs (APPNP [2] and GCNII [3]), where the results are shown as follows.\n\n|       | 0.5 0.05 | 0.45 0.1 | 0.4 0.15 | 0.35 0.2 | 0.3 0.25 | 0.25 0.3 |\n|-------|----------|----------|----------|----------|----------|----------|\n| GCN   | 97.37    | 92.34    | 90.1     | 86.45    | 81.04    | 76.88    |\n| GAT   | 97.41    | 92.08    | 88.33    | 81.77    | 76.59    | 69.58    |\n| APPNP | 97.8     | 93.22    | 90.21    | 89.58    | 83.33    | 80.72    |\n| GCNII | 98.54    | 95.41    | 91.39    | 87.89    | 84.2     | 81.35    |\n\n The numbers in the table headers represent the edge generation probabilities for inter-community and intra-community, and the experimental setup remains consistent with that described in Section 2 (for details, please refer to Section 2). Building upon the original foundation, we conducted experiments involving APPNP and GCNII. From the experimental results, it can be observed that with the changes in structure, the performance of these GNNs has experienced varying degrees of decline, which shows that once the test graph pattern shifts, the reliability of GNNs becomes compromised. We will show them together in our paper.\n\n2. > Q2：Difference with Good\n\nWhile both our work and the Good benchmark [1] address graph OOD problems, the reasons for causing the distribution shift that we focus on are distinct, which leads to differences in our data partitioning as well. Good presents OOD problem according to two distinct formulations of distribution shift, namely covariate shift and concept shift. The former refers to scenarios where the input distributions exhibit variance between training and testing data, formally described as $P_{train}(X) \\ne P_{test}(X), P_{train}(Y|X) = P_{test}(Y|X)$. In contrast, the concept shift refers to instances where the conditional distribution experiences variation, expressed formally as $P_{train}(X) = P_{test}(X), P_{train}(Y|X) \\ne P_{test}(Y|X)$.  Thus the data sampling and partitioning of Good are performed based on these two shifts. The investigation in our paper concentrates on the unique OOD phenomenon triggered by graph structure shifts which are exclusive to graph data formalized as $P_{train}(A) \\ne P_{test}(A)$. This shift opens up two potential conditional distribution: $P_{train}(Y|X, A) = P_{test}(Y|X, A), P_{train}(Y|X, A) \\ne P_{test}(Y|X, A)$. What we focus on is structure shift, and data partitioning is done based on the differences in structure. Therefore, the data partitioning of Good is not applicable to our problem.\n\n3. >Q2：Standard settings and label rate\n\n According to [4, 5],  test graphs differ in numerous structural aspects - such as size, edge density, and degrees - compared to their training graphs, which can be seen as structure shifts. We focus on three primary scenarios: perturbations in graph structures, Multiplex networks, and Multigraph data. In the case of perturbations in graph structures, random edge additions and deletions are implemented. For multiplex networks, varied relationships among nodes are considered. As for multigraph data, we utilize graphs drawn from diverse regions.\nData partitioning for cora, citeseer, and pubmed follows the methodology detailed in [6], while for ACM and IMDB, we follow the approach presented in [7]. As for Twitch-Explicit, we base our data division on the methods proposed in [4]. A comprehensive statistical analysis of structure shifts in graph data and label rates is included in global response Table 1. \n\n4. >Q3：Typos\n\nThanks for pointing this out, and we will correct these typos.\n\n[1] Gui S, Li X, Wang L, et al. Good: A graph out-of-distribution benchmark[J]. Advances in Neural Information Processing Systems, 2022, 35: 2059-2073.   \n[2] Gasteiger J, Bojchevski A, Günnemann S. Predict then propagate: Graph neural networks meet personalized pagerank[J]. arXiv preprint arXiv:1810.05997, 2018.  \n[3] Chen M, Wei Z, Huang Z, et al. Simple and deep graph convolutional networks[C]//International conference on machine learning. PMLR, 2020: 1725-1735.   \n[4] Wu Q, Zhang H, Yan J, et al. Handling Distribution Shifts on Graphs: An Invariance Perspective[C]//International Conference on Learning Representations. 2021.  \n[5] Wu Q, Chen Y, Yang C, et al. Energy-based Out-of-Distribution Detection for Graph Neural Networks[C]//The Eleventh International Conference on Learning Representations. 2022.  \n[6] Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[J]. arXiv preprint arXiv:1609.02907, 2016.  \n[7] Wang X, Ji H, Shi C, et al. Heterogeneous graph attention network[C]//The world wide web conference. 2019: 2022-2032.  "}, {"review_id": "KNDZY8SCZC", "reviewer": "Reviewer_nmEc", "summary": "The paper tackles an important question of learning invariant representations of GNNs. The authors show that once the test graph pattern shifts, the reliability of GNNs becomes compromised. Then they propose the cluster information transfer mechanism, which can be easily combined with current GNNs to improve their robustness on structure shift. The authors present numerical experiments that suggest that the proposed mechanism is effective.", "questions": "It would be beneficial to answer the questions in weakness.", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1.\tI enjoyed reading the paper. The presentation is clear and mostly easy to follow. \n\n2.\tClear results on different scenarios, well-backed by experiments.\n\n3.\tThe CIT mechanism is interesting and with technical analysis.\n", "weaknesses": "1.\tIn section 2, why GAT performs worse than GCN?\n\n2.\tIn fig.2, the model uses the node representation learned by GNNs to obtain clusters, so does the representation learned by different layers affect the clustering process?\n\n3.\tThe authors mentioned that the graph OOD benchmark is built, so why the datasets used in the experiments are still the traditional graphs?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. > W1： In section 2, GAT performs worse than GCN\n\nWe consider that the attention mechanism of GAT is a potential catalyst for the observed phenomenon. Existing research [1, 2] suggests that the attention mechanism is easily influenced by the distribution of neighbor characteristics. In Section 2, we design experiments to demonstrate the effect of structure shift on GNN performance. We set up two classes and generate features through Multivariate Gaussian distributions. In generating the test set graph structure, we changed the probability of edges between inter-class and intra-class. In this case, the homophily of node neighbors decreases, and heterophily increases. Thus the parameters of GAT learned based on the attention of the original neighbors are no longer applicable to the new neighbors, which exacerbates the decline in GAT's performance.  However, GCN does not have this attention mechanism, so in this scenario, the parameters learned by GCN are relatively more robust, resulting in a less drastic performance decline.\n\n2. > W2：Does the representation learned by different layers affect the clustering process?\n\nWe believe that the representations learned by different layers affect cluster processing.  Given the message-passing mechanism on GNNs, multilayer networks are capable of aggregating information from multiple top neighbors. \nSo theoretically, the representations learned from deep layers will aggregate more information and also be more conducive to the clustering process. However, in the real scenarios, due to the impact of over-smoothing, GNNs like GCN and GAT often consist of only two layers. Moreover, in GNNs, the final layer frequently serves as a classifier. Therefore, we employ the representations learned from the first layer for clustering. For networks that can be deeper, such as GCNII, we utilize representations learned before the final layer for clustering purposes.\n\n3. > W3： Why the datasets used in the experiments are still the traditional graphs?\n\nThe traditional graphs we used in our work are also used in Good benchmark [3], with the distinction that the data has been partitioned based on various out-of-distribution problems.  Meanwhile, our work focuses on structure shift poblems that differ from Good benchmark.  Good presents OOD problem according to two distinct formulations of distribution shift, namely covariate shift and concept shift,  and data sampling and partitioning are performed based on these two shifts, which is not suitable for our problem. What we focus on is structure shift, and data partitioning is done based on the differences in structure.\n\n[1] Veličković P, Cucurull G, Casanova A, et al. Graph attention networks[J]. arXiv preprint arXiv:1710.10903, 2017.  \n[2] Brody S, Alon U, Yahav E. How attentive are graph attention networks?[J]. arXiv preprint arXiv:2105.14491, 2021.  \n[3] Gui S, Li X, Wang L, et al. Good: A graph out-of-distribution benchmark[J]. Advances in Neural Information Processing Systems, 2022, 35: 2059-2073.  \n"}, {"review_id": "zofeK4Mfvg", "reviewer": "Reviewer_Nbx4", "summary": "This paper focuses on the invariant learning of graph neural networks and proposes a cluster information transfer mechanism with two statistics: the mean of cluster and the variance of cluster. The authors prove that with CIT mechanism, the model is able to capture the cluster independent information, so as to improve the generalization ability across different structure shifts. Experiments on different graph benchmarks show promising results of CIT mechanism.", "questions": "1. It seems that most of the graphs used here are not large enough, so what is the time complexity of the proposed model?\n3. The authors design several experiments to evaluate the model, e.g., perturbate edges, multiplex graphs. Do all these changes belong to the structure shift? Can the authors provide more discussions on what changes can be considered as structure shift?\n4. The paper proves that with CIT mechanism, the cluster information has less influence on the classifier, but what if the cluster information is related with the labels? \n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Introduction and background parts are clearly written and motivate this study well. The research problem is important, the ideas are clearly clarified and all the technical steps are easy to follow. The paper provides the comprehensive experiments on different kinds of graphs to evaluate the performance of the proposed model.\n", "weaknesses": "No specific discussions on structure shift. Time complexity analysis is not provided. The CIT mechanism is not explained sufficiently. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. > Q1：The time complexity of the proposed model\n\n Our CIT mechanism has two parts of computation: Clustering process and Cluster Information Transfer process. Let $N$ represent the number of nodes, and $K$ represent the number of clusters. The computational complexity of clustering process is $\\mathcal{O}(N^2K+NK^2)=\\mathcal{O}(NK(N+K))$.  Since the adjacency matrix is usually sparse, the computational complexity can be reduced to $\\mathcal{O}(EK)$, where $E$ is the number of non-zero edges in the adjacency matrix. The computational complexity of Cluster Information Transfer process is $\\mathcal{O}(pN)$, where $p$ is the probability of transfer. So the computational complexity is $\\mathcal{O}(K(E+NK)+pN)$.  The space complexity which depends on the dimension of the assignment matrix is $\\mathcal{O}(NK)$.  And we will add this in appendix.    \n\nOur primary contribution lies in proposing a concise and effective CIT mechanism to tackle the structure shift problem, and we have validated its effectiveness.  Actually, it is easy for our model to further lower the computational complexity of the clustering process by replacing spectral clustering with other large-scale graph clustering. For instance, [1] proposes DMoN which uses a new objective function for clustering combining graph spectral modularity maximization and a new regularization method, and the computational complexity of this method is  $\\mathcal{O}(d^2N)$. So with the method like this, the computational complexity of our CIT mechanism will reduce to  $\\mathcal{O}((d^2+p)N)$, enabling its application on large graphs. Therefore how to extend it to larger graphs is not the focal point of our attention and can be considered as future work.\n\n2. > Q2：Discussions about structure shift\n\n According to [2,3],  test graphs differ in numerous structural aspects - such as size, edge density, and degrees - compared to their training graphs, which can be seen as structure shifts. We focus on three primary scenarios: perturbations in graph structures, Multiplex networks, and Multigraph data. In the case of perturbations in graph structures, random edge additions and deletions are implemented. For multiplex networks, varied relationships among nodes are considered. As for multigraph data, we utilize graphs drawn from diverse regions.  A comprehensive statistical analysis of structure shifts in graph data and label rates is shown in global response Table 1. It can be observed that the experiments we have set up are all based on structure shift.   \n\n With regard to structure shift in graph data, there is a prevalent discourse surrounding out-of-distribution (OOD) graph classification, such as molecular scaffold [4, 5]. Conversely, node classification discussions remain relatively sparse and need to be explored. In the context of a node classification task, we think that local properties of nodes, including neighbor information under the message-passing mechanism, are crucial determinants of nodes representation learning. Therefore, a structure shift might correlate to a shift in these local properties of a node, which could manifest as variations in node degree, edge density, graph size, or homophily.\n\n1. > Q3：What if the cluster information is related with the labels?\n\n In this work, we aim at learning the cluster-invariant information with CIT mechanism. Therefore, when the structure shifts happen, the model can make stable predictions under different structures. As for the correlation between the cluster information and the labels, this assumption may work well with no distribution shifts, however, if the distribution shifts happen, which is the scenario that we focus on in this paper, the assumption may not hold. \nIn this situation, the CIT mechanism simulates structure shift by altering the cluster information of nodes, allowing nodes to exist in different domains.  So the model learns cluster-invariant information by training on nodes from multiple clusters. So, to be more precise, we have demonstrated that the CIT mechanism can mitigate the impact of changing clusters during structure shift, enhancing the robustness of the model  against such changes.\n \n [1] Müller E. Graph clustering with graph neural networks[J]. Journal of Machine Learning Research, 2023, 24: 1-21.  \n[2] Wu Q, Zhang H, Yan J, et al. Handling Distribution Shifts on Graphs: An Invariance Perspective[C]//International Conference on Learning Representations. 2021.  \n[3] Wu Q, Chen Y, Yang C, et al. Energy-based Out-of-Distribution Detection for Graph Neural Networks[C]//The Eleventh International Conference on Learning Representations. 2022.    \n[4] Li H, Zhang Z, Wang X, et al. Learning invariant graph representations for out-of-distribution generalization[J]. Advances in Neural Information Processing Systems, 2022, 35: 11828-11841.   \n[5] Miao S, Liu M, Li P. Interpretable and generalizable graph learning via stochastic attention mechanism[C]//International Conference on Machine Learning. PMLR, 2022: 15524-15543.     "}, {"review_id": "fIw3G93ZBL", "reviewer": "Reviewer_5H2e", "summary": "The paper introduces a new mechanism called Cluster Information Transfer (CIT) to improve the generalization ability of GNNs to various and unknown test graphs with structure shift. The CIT mechanism enhances the diversity of nodes by combining different cluster information with the nodes, which helps GNNs learn invariant representations. The paper presents experimental results on several benchmark datasets, demonstrating that the proposed CIT-GNN model outperforms existing GNN models in terms of accuracy and macro-F1 score. ", "questions": "- The method considers the embedding space only. Thus, it seems that the method can be extended to other domains, e.g., for images. If that is the case, are there any graph-specific properties that make this solution remains on the graph domain rather than other general domains?\n- What's the method's performance when removing/adding 5%, 20% edges and not removing/adding any edges? Does the improvement of the method decline with the decreasing ratios?", "limitations": "The authors discussed the limitations on the fact that the method could only apply to node-level tasks directly and the theory remain to be fully developed, as well as the limitation that the transfer remains on embedding space but graph topology.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is easy to understand.\n- While the theory analysis is straightforward, it provides theoretically support for the proposed method.\n- The experiments are extensive and the results look promising.\n", "weaknesses": "- **Fair Novelty:** The proposed method is essentially an embedding transformation function that aims to eliminate the statistic variance between clusters that causes bias and hinders generalization. The novelty comes from the clustering mechanism and the augmented training using adjusted node embeddings. However, the spectral clustering mechanism has been introduced previously, and the transformation is relatively straightforward.\n- **Assumptions and scope of the solution:** My second concern is about the assumptions of this paper. The paper generally assumes that there exist cluster / structural shifts between training and testing datasets. While structure could change across environments, the node labels remain invariant. The paper also implicitly assumes the node embeddings in different clusters are subject to Multivariate Gaussian distributions. These assumptions should be made explicit and formal. Moreover, the scope of structural shifts needs to be clarified. I understand that the variant of graph density or node degree can be one factor, but do other factors, e.g., edge homophily, also contribute to the shifts? A more general scope should be discussed in order to ensure its applicability.\n- **More validation about the claim:** The examples in the introduction considers the shifts between sparse and dense graphs. One simple baseline to mitigate it is to augment the datasets or clusters via DropEdge and AddEdge compared to modifying node embeddings. While I understand that the graph structure is complex in the real world, as the authors claimed (Line 57-59), it would be good to experimentally validate the effectiveness of the method with a simple baseline that modifies the graph structure.  \n- **Lack of real datasets with natural shifts**: The experiments are somewhat synthetic in the sense that the training and testing sets are splitted with strong structural shifts. I wonder the performance of this method on datasets with more natural shifts, e.g., ogbn-arxiv, where the training and testing sets are splitted based on the time difference.\n- **Missing Related Works:** It is unclear how the proposed clustering objective differs from the existing group clustering methods, e.g., Zhou et al. [1].\n\n**Minor:**\n\n- I feel Section 2 is not very informative since the setting is simple and the conclusion is not surprising. It would be good to demonstrate the structural shifts in more real settings or just combine this section to the introduction.\n- In Line139 and 149, $m$ and $M$ are both used to indicate the number of clusters. It's better to make it consistent.\n\nIn general, the angle of mitigating structure shifts is interesting. However, several things above should be solved or clarified to understand its generality and effectiveness.\n\n\n[1] Towards Deeper Graph Neural Networks with Differentiable Group Normalization. Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, Xia Hu.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. >W1, Q1： Fair Novelty\n\nWe agree that the spectral clustering mechanism has been introduced previously, however, in this work, our main contribution resides in the development of the CIT mechanism and spectral clustering is just one component of it. The CIT mechanism is a flexible and succinct approach compatible with different GNN backbones, which has not been discussed in this way at present. Despite our CIT mechanism is relatively simple, we think that \"simple yet effective\" is actually our final goal in practice.\n\nDespite our model considers the embedding space only, it is actually technically challenging to reasonably model domain information. First, given graph structure, how to capture the domain information of a node is not well explored. Usually, for images, we can consider the background information as the domain information [8]. For graph data, we just know the structure which lacks semantic information and is very unintuitive. Here, we initially consider utilizing clustering information as local information. Given the message-passing mechanism in GNNs, the local properties of nodes are determinants of representation learning. Therefore, a structure shift might correlate to a shift in these local properties of a node. Coincidentally, the cluster information typically encapsulates the local attributes of nodes and can be harnessed to generate various local properties. \n\n2. > W2： Scope of the solution\n\n With regard to structure shift in graph data, there is a prevalent discourse surrounding out-of-distribution (OOD) graph classification, such as molecular scaffold [2, 3]. Conversely, there is relatively less discussion regarding node classification and it needs to be explored. In the context of a node classification task, we think that local properties of nodes, including neighbor information under the message-passing mechanism, are crucial determinants of node representation learning. Therefore, a structure shift might correlate to a shift in these local properties of a node, which could manifest as variations in node degree, edge density, graph size, or homophily.\n\n3. > W2：Assumptions\n\nThe first assumption you said is our structure shift problem setting. \nRegarding the second assumption, we follow [4,5] and consider the structure as the environment.   Meanwhile, referencing the theory of invariant learning [6], we learn invariant representations by maintaining label invariant across different structures.\nAs for the third assumption pertaining to Gaussian distribution, it's important to clarify that we do not make this assumption in our model. In Section 2, we employ multivariate Gaussian distribution to generate nodes' features to establish a binary classification setting, which is a very common operation [7], facilitating the observation of experimental phenomena. Meanwhile, we introduce Gaussian perturbations to enhance the diversity of cluster information in embedding space. Therefore, we do not posit that the cluster distribution is subject to Multivariate Gaussian distributions.  \n\n4. > W3：Simple baselines\n\nThanks for the suggestion. We conducted experiments involving the use of the DropEdge and AddEdge techniques on the GNN backbones we employed, and the experimental results are shown in global response Table 2. \nThe experimental results indicate that even simple techniques like AddEdge and DropEdge can enhance the performance of the original GNN. This also validates the correctness of our approach to learn invariant information by altering node domains to address structure shift. \n\n5. > W4：Natural shifts \n\nActually we applied our model to real datasets with natural shifts. For Multiplex networks, we select two datasets, ACM and IMDB, which have two relation structures, and we train on one relation structure and test on another. For example, in the case of the ACM network, we train on PAP relation where edges represent that two papers have the same author and test on PSP relation where edges represent that two papers belong to the same subject. All these relations naturally exist.\nFor Multigraph data, we follow [4] and select Twitch-Explict dataset. Twitch datasets contain several networks and each network is collected from a particular region. Therefore these are natural shift.\n\n6. > W5：Related Works\n\nFirstly, the purpose of the clustering process between [1] and ours is different.\n[1] employs clustering in order to group nodes with consistent labels and utilizes cluster information to alleviate over-smoothing issues on the graph. During this process, node labels will be utilized for clustering. However, our clustering aims to group similar nodes to model local properties through clustering information, without leveraging label information. \nSecondly, our technical approach is also different. Our work utilizes spectral clustering and the purpose of operating in the embedding space is to transform clusters. [1] achieves clustering by optimizing two distances and normalizing cluster representation in the embedding space. And we will cite it.\n\n7. > Q2：Improvement of the method decline with the decreasing ratios\n\nWe conducted experiments and the results are shown in global response Table 3, and we can see the improvement becomes less pronounced as the magnitude of perturbation decreases.\n\n[2] Li H, Zhang Z, Wang X, et al. Learning invariant graph representations for out-of-distribution generalization[J].\n\n[3] Miao S, Liu M, Li P. Interpretable and generalizable graph learning via stochastic attention mechanism[C].\n\n[4] Wu Q, Zhang H, Yan J, et al. Handling Distribution Shifts on Graphs: An Invariance Perspective[C].\n\n[5] Zhang Z, Wang X, Zhang Z, et al. Dynamic graph neural networks under spatio-temporal distribution shift[J].\n\n[6] Chang S, Zhang Y, Yu M, et al. Invariant rationalization[C].\n\n[7] Wang X, Zhu M, Bo D, et al. Am-gcn: Adaptive multi-channel graph convolutional networks[C].\n\n[8] Zhou K, Yang Y, Qiao Y, et al. Domain generalization with mixstyle[J]."}, {"review_id": "VSIIOIS085", "reviewer": "Reviewer_uNQ9", "summary": "This paper aims to handle the structure shift problem in GNN. The paper proposed a novel approach -- Cluster Information Transfer (CIT) to address this challenge. CIT first computes cluster center representation during training. CIT then extract the cluster center from the node embedding to retrieve the cluster-independent information. Finally CIT transfers the cluster-independent information to another random cluster center, allowing the model to learn structure-independent knowledges.", "questions": "Q1：What is the relationship between invariant representations and cluster information and why is transferring a node to another cluster reasonable ?\nQ2: Can CIT possibly be scaled to larger graphs? ", "limitations": "The reviewer does not see potential negative social impact of the work.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "+ Previous works like EERM, SR-GNN majorly focus on data distribution shifts on graphs, while this paper focus on graph structural shift which is of potential research interest.\n+ The method proposed in the paper can be applied on various existing GNN backbones, the method can also fit into different type of tasks and graphs.\n+ This paper is well-written and is easy to follow.", "weaknesses": "- The CIT method proposed in the paper is not well supported by theorem.  Theoretical analysis only shows that CIT weakens the affect of cluster information. However, the paper still need to answer why it is necessary to transfer nodes across clusters using Eq.8 (If the cluster information is harmful, why not just remove it?) and why can the model learn invariant representations from this process. \n- The method introduces a lot of additional hyper-parameters which are sensitive to the results, which are all tuned by grid-search according to the experiments settings. Finally, the accuracy improvements in the experiments is not remarkable compared with other baselines.\n- The method is only evaluated on small graphs with several thousand nodes, making it unknown whether the method can be applied to larger graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. > W1, Q1：Learning process and theoretical explanation \n\nFirst, we don't think that cluster information is harmful. The correlation between cluster and labels does help us make predictions. However, this assumption holds when the cluster information does not change, i.e., the structure shifts do not happen. When the structure shifts happen, relying on the original cluster information may lead to mistakes. Therefore, what we need to do is not to remove the cluster information, but learn the cluster-invariant information by simulating cluster changing, so that the model can provide stable predictions under structure shift scenarios. So, to be more precise, we have demonstrated that the CIT mechanism can mitigate the impact of changing clusters during structure shift, enhancing the robustness of the model against such changes. The learning process is similar to the theory of invariant learning [1, 2]. During the process of invariant learning, we train the model to acquire domain-invariant information by generating data of the same sample in different domains. Therefore, similar to our learning process, we employ the CIT mechanism to generate nodes from different clusters to train the model and learn cluster-invariant information. \nWe acknowledge that our current explanation may be somewhat unclear and confusing, and we are committed to rectifying these issues in the paper.\n\n2. > W2：Hyper-parameters analysis and limited accuracy improvement\n\nOur CIT mechanism only consists of three main hyperparameters. $p$ is the probability of transfer. $k$ is the epochtimes of every transfer. $m$ is the number of clusters. As shown in our paper Section 4.4 Analysis of hyper-parameters, the $k$ is consistently stable, and the performance benefits from the applicable selection of $p$ and $m$.    \nOur CIT mechanism is a plug-in part that works for different GNN backbone. Therefore, to check the effectiveness of our model, we can see the results of the base model with and without our CIT mechanism. As shown in Table1 and Table2 in our paper,  we conducted significance testing on the experimental results and found that the improvement is significant. For example, in the case of GCNII on Cora dataset, the CIT mechanism improves its accuracy from the original 73.16% to 77.08% with a significance level of 0.01. In the case of APPNP, the CIT mechanism improves its accuracy from the original 75.86% to 78.02% with a significance level of 0.01. Besides, we believe that if we apply CIT to other advanced GNNs and other methods in theory, e.g. SR-GNN, their performance in OOD scenarios can be further improved.\n\n3. > W3, Q3：Larger graphs\n\n Our CIT mechanism has two parts of computation: Clustering process and Cluster Information Transfer process. Let $N$ represent the number of nodes, and $K$ represent the number of clusters. The computational complexity of clustering process is $\\mathcal{O}(N^2K+NK^2)=\\mathcal{O}(NK(N+K))$.  Since the adjacency matrix is usually sparse, the computational complexity can be reduced to $\\mathcal{O}(EK)$, where $E$ is the number of non-zero edges in the adjacency matrix. The computational complexity of Cluster Information Transfer process is $\\mathcal{O}(pN)$, where $p$ is the probability of transfer. So the computational complexity is $\\mathcal{O}(K(E+NK)+pN)$.  The space complexity which depends on the dimension of the assignment matrix is $\\mathcal{O}(NK)$.  And we will add this in appendix.    \nOur primary contribution lies in proposing a concise and effective CIT mechanism to tackle the structure shift problem, and we have validated its effectiveness.  Actually, it is easy for our model to further lower the computational complexity of the clustering process by replacing spectral clustering with other large-scale graph clustering. For instance, [1] proposes DMoN which uses a new objective function for clustering combining graph spectral modularity maximization and a new regularization method, and the computational complexity of this method is  $\\mathcal{O}(d^2N)$. So with the method like this, the computational complexity of our CIT mechanism will reduce to  $\\mathcal{O}((d^2+p)N)$, enabling its application on large graphs. However how to extend it to larger graphs is not the focal point of our attention and can be considered as future work.\n\n\n[1] Chang S, Zhang Y, Yu M, et al. Invariant rationalization[C]//International Conference on Machine Learning. PMLR, 2020: 1448-1458.  \n[2] Arjovsky M, Bottou L, Gulrajani I, et al. Invariant risk minimization[J]. arXiv preprint arXiv:1907.02893, 2019.  \n[3] Müller E. Graph clustering with graph neural networks[J]. Journal of Machine Learning Research, 2023, 24: 1-21."}]

Author rebuttal:
We sincerely thank all the reviewers for your careful reading and suggestions. Due to character constraints, we have uploaded the experimental results in this PDF.

Meta-review: The paper introduces a new mechanism called Cluster Information Transfer (CIT) to improve the generalization ability of GNNs in the presence of structure shifts. The CIT mechanism enhances the diversity of nodes and helps learn invariant representations by combining different cluster information with the nodes. The CIT mechanism can be easily incorporated into existing models. A theoretical analysis is presented, showing that the impact of cluster information on the classifier diminishes during transfer.  Overall the paper proposes a practical solution that addresses an important problem.
Decision: Accept (poster)