InterpGNN: Understand and Improve Generalization Ability of Transdutive GNNs through the Lens of Interplay between Train and Test Nodes
Authors: Jiawei Sun
Kailai Li
Ruoxin Chen
Jie LI
Chentao Wu
Yue Ding
Junchi Yan
Venue: ICLR 2024 poster (2024)
Keywords: Graph Neural Networks
Generalization bounds
PAC-Bayesian
Structural imbalance
Graph Global Workspace
Primary area: learning on graphs and other geometries & topologies

Abstract: Transductive node prediction has been a popular learning setting in Graph Neural Networks (GNNs). It has been widely observed that the shortage of information flow between the distant nodes and intra-batch nodes (for large-scale graphs) often hurt the generalization of GNNs which overwhelmingly adopt message-passing. Yet there is still no formal and direct theoretical results to quantitatively capture the underlying mechanism, despite the recent advance in both theoretical and empirical studies for GNN's generalization ability. In this paper, the $L$-hop interplay (i.e., message passing capability with training nodes) for a  $L$-layer GNN is successfully incorporated in our derived PAC-Bayesian bound for GNNs in the semi-supervised transductive setting. In other words, we quantitatively show how the interplay between training and testing sets influence the generalization ability which also partly explains the effectiveness of some existing empirical methods for enhancing generalization. Based on this result, we further design a plug-and-play ***Graph** **G**lobal **W**orkspace* module for GNNs (InterpGNN-GW) to enhance the interplay, utilizing the key-value attention mechanism to summarize crucial nodes' embeddings into memory and broadcast the memory to all nodes, in contrast to the pairwise attention scheme in previous graph transformers. Extensive experiments on both small-scale and large-scale graph datasets validate the effectiveness of our theory and approaches.

Published as a conference paper at ICLR 2024
UNDERSTAND AND IMPROVE GEN- ERALIZATION ABILITY OF TRANSDUCTIVE GNNS THROUGH THE LENS OF INTERPLAY BETWEEN TRAIN AND TEST NODES
INTERPGNN:
Jiawei Sun', Kailai Li', Ruoxin Chen', Jie Li Chentao Wu', Yue D Junchi Yan
DDppartment of Computer Science and Engineering. Shanghai Jiao Tong University
Moo Key Lab of AI, Shanghai Jiao Tong University
Yancheng Blockchain Research Institute
4 Youtu Lab, Tencent
{ncels jw, kai kailailii, lijiecs, wuct, yanjunchijjsssuunnuuuu edu. cusmochen@tencent.com com
ABSTRACT
Transductive node prediction has been a popular learning setting in Graph Neural Networks (GNNs). It has been widely observed that the shortage of information flow between the distant nodes and out-of-batch nodes (for large-scale graphs) often hurt the generalization of GNNs which overwhelmingly adopt message- passing. Yet there is still formal and direct theoretical results to quantitatively capture the underlying mechanism, despite the recent advance in both theoretical and empirical studies for GNN's generalization ability. In this paper, the L-hop in- terplay (i.e., message passing capability with training nodes) for an L-layer GNN is successfully incorporated in our derived PAC-Bayesian bound for GNNs in the semi-supervised transductive setting. In other words, we quantitatively show how the interplay between training and testing sets influence the generalization ability which also partly explains the effectiveness of some existing empirical methods for enhancing gencralization. Based on this result, we further design a plug-and- play Graph Global Workspace module for GNNs (InterGGNN-GW) to enhance the interplay, utilizing the key-value attention mechanism to summarize crucial nodes' embeddings into memory and broadcast the memory to all nodes, in con- trast to the pairwise attention scheme in previous graph transformers. Extensive experiments on both small-scale and large-scale graph datasets validate the effec- tiveness of our theory and approaches.
INTRODUCTION
Graph Neural Networks (GNNs) have shown success in learning both node and graph representa- tions, with applications in node/graph classification (Kipf & Welling, 2017; Veličković et al., 2018; Xu al., 2019), link prediction (Du al., 2019b; Yang al., 2022), etc. Current GNNs mainly use the message-passing paradigm (Gilmer et al., 2017), updating nodes at each layer by aggregat- ing their embeddings with neighboring nodes',
particular, recent empirical studies show that the effective interplay between train and test nodes either from the structure (Lukovnikov & Fis- cher, 2021; Rusch et al., 2022) or by implicit connection e.g., graph transformers (Wu et al., 2022; 2023) can effectively boost the generalization performance of GNNs for transductive node predic- tion which the common setting in existing GNNs and is also the focus of this paper. Yet there still lacks quantitative results the impact of graph structure especially that between train and test nodes on GNNs generalization ability, despite the abundant studies (Garg et al., 2020; Scarselli al., 2018; Garg al., 2020; Liao et al., 2021; Du al., 2019a) on theoretical GNN generaliza- tion error using different tools e.g., Rademacher complexity. VC dimension, and PAC-Bayesian. Table shows that previous derived bounds are related to different sxph-ssecific information for the transductive setting. including graph diffusion (Esser et al., 2021), disparity in aggregated node
"Corresponding author

---

Published as a conference paper at ICLR 2024
Table 1: Massage-passingg based GNNs' generalization error bounds. Note that we are the first to establish the generalization error via the structure interplay between training and test sets. In fact, the interplay has been empirically verified as an effective way for improving generalization in Lukovnikov& & Fischer (2021); Rusch et al. (2022).
Works
Analysis framework
Setting
i.d.'
Task
Graph-specific information
Scarselli al. (2018)
VC dimension
Inductive
binary node cls.
number of nodes eigenvalue graph filter
Verma Zhang (2019)
algoriítmic stability
Inductive
multiclass node
Garg al. (2020)
Rutemaccer complexity
Incuctive
hinury gruph
maximum mode degree none graph diflusioo none
Oono & Suzuki (2020)
Rademacher complexity
Transductive
binary node cls.
Esser et (2021)
Rademacher complexity
Transduciive
binary mode cls.
et al. (2019n)
Neural Tangent Kernel
Inductive
hinury graph cls.
Liao et al. (2021)
PAC-Baycsian
Inductive
binary graph cls.
maximum node degree
Ma al. (2021)
PAC- Bayesian
Transductive
X
multiclass mode cls.
dispurity in uggregated leatures
Maskey et al. (2022)
Convergence speed
Inductive
multiclass graph cls.
average nümber of nodes
InterpGNNN (Ours)
PAC-Bayesian
Transductive
multiclass node
interplay
1i.dd means examples are drawn from an identical and independent distribution.
feature (Ma et al., 2021), yet the results concerning graph structure is missing and cannot support the empirical finding on its importance Lukovnikov & Fischer (2021); Wu et al. (2022).
Theory perspective: we derive generalization error bound for GNNs (Theorem I with details in Section 2.2) using the tool of FAC-Bayesian (McAllester, 1998). Its novelty lies in the direct connection to the interplay between the train and test nodes (as depicted by Eq. 8). Specifically, for an I--laer GNN, we define I-hop (1 S L) interplay I' (formally in Definition 1) as the proportion of test nodes that can interact with training nodes after I-times message passing, i.e., those test nodes whose minimum path length to any training node is I. As summarized in Table 1, to our best knowledge, our derived bound is the first directly show that more information interaction between neighboring test and training nodes can lead to smaller generalization error and interpret the structural imbalance phenomenon for homophilic graphs.
Informed by the above theory, increasing the interaction between distant training and test nodes can reduce generalization error. One direct way is deepening the GNN. This is because a GNN with L se- quentially stacked layers can utilize up to L-hop neighbors for node feature updates. However, most GNNs achieve peak performance with shallow depth, and their performance degrades with increas- ing layers due to common issues like over-smoothing (Chen et al., 2020a) and over-squashing (Alon & Yahav, 2021). Another way is implicit connections, such as graph transformers (Wu et al., 2023) assign attention scores the weights of implicit edges between any pair of nodes. The challenge is further pronounced with the fact that current scalable GNNs (Chiang et al., 2019; Zeng et al., 2020) mainly employ mini-batch training protocol, where nodes from different batches are isolated.
Technical perspective: we propose a plug-and-play module called Graph Global Workspace (InterPGNN-GW) for GNNs. The so-called global workspace is composed of memory slots that can store the aggregated embeddings of important nodes. The raw node features are first transformed into embeddings using any GNN (Kipf & Welling, 2017; Hamilton et al., 2017), and vandom-walk, based techniques like node2vec (Grover & Leskovec, 2016) serve positional encoding for nodes. Key-value attention is then used to select important node embeddings to write into the workspace, leveraging topological information in positional encoding for coordination across the entire graph. Memory updates employ gated approach to achieve persistence. Finally, memory contents stored in the global workspace are broadcast to all nodes. Compared to the graph transformers (Wu et al., 2022; 2023) based on inner-batch pair-wise attention, the global workspace can provide global con- sistency. The contributions are as follows:
1) New theory: We derive PAC-Bayesian bound for pressage-passingg GNN in the transductive node classification, which is the dominant setting for graph learning. The bound associates the generalization error with the topological interplay between training and test sets, i.e., whether test nodes can obtain the features of training nodes through message passing. The bound theoretically interpret the structure imbalance phenomenon observed in transductive node classification.
2) Plug-in method: Based on the derived bound, we propose the Graph Global Workspace (InterpGNN-GW to enhance the interplay between distant and out-of-batch nodes. Nodes with positional encoding compete to write to and read from the global workspace via key-value attention.
3) Strong results: Experiments on small- and large-scale graph datasets show InterpGNN-GW's superior performance on node classification compared to scalable GNNs and graph transformers.
2

---

Published as a conference paper at ICLR 2024
2
GENERALIZATION ERROR BOUND VIA PAC-BAYESIAN ANALYSIS
2.1 PROBLEM SETUP AND PRELIMINARIES ON PAC-BAYESIAN
Transductive node classification. We consider semi -umeevipee transductive K-class node clas- sification which is commonly studied in the graph learning community. Let G (V. E) represent an undirected graph, where V denote the node set with size N, and E denote the edge set. Let X denote the node features, that for each node i, its label is generated by true but unknown distribution D conditioned on node features and neighbors. Denote the set of training nodes as S and the set of test nodes as U. In the transductive node classification task, classifier f(A, X) is learned using the labels of training set Ys, the features of both training and test nodes X = [Xs, Xtr), and the adjacency matrix A. The objective is to classify the unlabeled nodes in U. The classification of the i-th node is:
denote the node labels and A represent the adjacent matrix. Assume
U: arg max f(A, (i,
kE(
where S(A, ()(,,) k] means the (i, k-tth element of the obtained matrix.
y-margin ramp loss. We use the y-margin ramp loss following Bartlett et al. (2017); Zhang et al. (2019); Koltchinskii & Panchenko (2002). First define the margin operator of hypothesis f for a labeled node as My wi) f(A, X) yi] maxk f(A, { k]. Given the set of training
nodes S, the empirical error of on S is defined as:
Rf, = S
(MM(((,,i)),
(1)
ES
where the ramp loss (-) is defined as:
S a
t (a)
1
a/y
0 < S Y. a 0.
(2)
Additionally, we use (a) = 16 * yl to denote the 0-1 classification loss and its correspond- ing empirical error (f. since the marginal ramp loss transitions to classification loss as y ap- proaches zero. Similarly we can define the empirical error on the test set U as Ru,y. The excepted error on training and test set are defined as:
(f) = E [R),(f)] ru,)(f)= = E (RU, yoD
(3)
ynD
PAC-Bayesin background. PAC-Bayesian (McAllester, 1998; 1999) provides tool to analyze the generalization performance of randomized predictors. Consider training set S, true yet unknown tubel-generation distribution D from which samples are drawn, hypothesis class H of classifiers, a prior distribution P over H. and a posterior distribution Q over H. The prior P encodes our prior about the model before seeing any training data; the posterior is learned by learning data. As opposed to common learning paradigm which learns a single deterministic predictor, PAC- Bayesian studies the distribution of models, and the error measure on test set is extended as,
training
(U)
TF f~Q
(f),, (Q) f-Q
E. [ru,)(f))
(4)
The error measurement on the training set uses a similar definition for Rs. (Q) and rs.- (Q). The aim of PAC-Bayesian is to bound the gap between (Q) and (u, with high probability. The PAC-Bayesian typically first associates the generalization bound with the discrepancy between any possible prior P and posterior Q, measured with the KL divergence Dx (Q) Then the concrete bounds are obtained by constructing specific priors and posteriors. Although PAC-Bayes is gener- ally founded stochastic models, McAllester (2003b); Neyshabur et al. (2017) provide standard techniques for obtaining the generalization bounds of deterministic models. We refer readers to tutorials (Guedj, 2019; Alquier, 2021) for more details on PAC-Bayesian.
2.2 THE DERIVED STRUCTURE-AWARE PAC-BAYESIAG BOUND OF GCN
PAC- AAC-Bayesian bound for Transductive Learning. The following lemma with proof in Ap- pendix B.1 introduces PAC-Bayesian bound for general transductive learning.
3

---

Published as a conference paper at ICLR 2024
Lemma 1 (PAC-Bayesian bound for transductive learning) Given full set V with N examples, for any training set S of size m and test set U, for any prior distribution P on the hypothesis space of classifier HH (not necessarily GNN). for any 6 E (0, 11. with probability at least 1 6, we have,
DKL(QI P)+ In 2m + D(P)
(Q) - (Q)+
5
(5)
2(m-1)
where D(P) = In E 220
quantifies the expected loss discrepancy between
f-r
the training and test set. Lemma is a natural adaptation of PAC-Bayesian in Germain et al. (2009) from inductive learning to transductive learning. Using lemma 1 as a tool for PAC-Bayesian, the generalization bounds can be obtained by upper-bounding the term D(P). For GNNs, given that embedding can be propagated to neighbors, we need to consider the impact of structure on the bound of (PP) in comparison to general transductive learning.
PAC-Bayesian bound for GCN. We now incorporate the node correlation induced by the graph structure into Lemma 1. We first denote that the 12-norm of node features are bounded by Ba. and the no-mo of weights for each layer, for any classifier is bounded by B... We analyze GCN (Kipf & Welling, 2017). The derived bound can be easily generalized to any GNNs following the message- passing and aggregation paradigm such as GraphSAGE (Hamilton et al., 2017), SGC (Wu et al., 2019). The 1-th layer of GCN is defined as:
(6) where (-) is ReLU non-linear activation function, W, is the trainable weight matrix, H2 are node embeddings of the 1-th layer with Ho = X, Á = A + I, and I is the identity matrix. The max- imum number of hidden units across all layers is denoted h. A path between node i and node j is denoted as sequence of successively connected nodes: p(i.j) = (E,,... (e,,...,,y))) with the path length w(p(i,j) defined as the count of edges along The shortest path length denoted by s(i,j) = min ((in(((((i))))
H 0 (A Wt),
For the first time to our best knowledge, to explore the impact of
structural correlation between training and test sets on generalization error, we define the I--hop interplay between training and test nodes.
Definition 1 (L-hop interplay) For graph G (V. F.) with training S V and test set U U.V, W, the L-hop interplay It between S and U is defined as:
El_ (L- 1) IPr]
I
| where P, = (ii,])i S,j E s(. r represents training-test node pairs with the shortest path length of
We now derive the following generalization bounds of L-layer GCN by associating the upper bound of D(P) with the L-hop interplay. The complete derivation is given in Appendix B.2. The proof is in two steps: 1) bounding D(P) based on the premise that embedding exchange among connected nodes leads to closer output logits, 2) bounding D (x P) as per Neyshabur et al. (2017); Ma et al. (2021).
Theorem (PAC-bayes bounds with L-hop interplay for transductive GCN) Let f E H be an L-layer GCN with parameters (W for any Bgg B 0, L, K 2 1, and any 8, y O. with probability at least 8 over a training set S of size m we have,
B3 12 IT + In Lm
2I,
TU,o()) < Rs.,()++ O
K2 13
y²
(8)
72m
dmaz
where II -IT Wall and E ==
EE
|ill
are product and sum of spectral norm of weights, Will
dmaz is the maximum node degree.
Theorem interpret the structure imbalance phenomenon. Grouping test nodes based on their distance with training nodes, the impact of topological structure on generalization is presented in Fig. with further elaboration in Appendix C. For test nodes exhibiting stronger interplay with training nodes, the generalization error is smaller. Theorem 1 theoretically interprets this experi- mental observation. Considering Tang et al. (2020); Liu et al. (2023) connect generalization ability modify the grouping criterion to node degree, revealing a similar trend (Fig. 2).
with node degree, We attribute this to nodes with smaller degrees engage in fewer interactions with training nodes. The generalization of above theorem on heterophilic graphs please see in Appendix G.3
3 ENHANCING GENERALIZATION VIA THE GRAPH GLOBAL WORKSPACE
4

---

Published as a conference paper at ICLR 2024
GAT
SAGI SOC
Aggraa (a
SOC
Grogge
Caolge
Grang
(a)
Cora
(h) Citeseer
(c) Pubmed
Figure 1: Accuracy on different subset grouped by interplay. Lower index implies higher interplay.
GCN
GUN
GATT
GAT
CAT
SALE:
SAGE
Catage
CHIRE
Catigg
(c) Pubmed Figure 2: Accuracy different subset grouped by nodes degree. Lower index implies higher degree.
(a) Cora
(b) Citeseer
Intuition. Building upon previous investigations, exploring ways to en- hance the interplay between dis- tant nodes is worth researching. We propose plug-and-play module for GNNs, inspired by the Global Workspace Theory (Baars, 2005; VanRullen & Kanai, 2021; Goyal al., 2022), to enhance long-range node interplay and reduce complex- ity. Nodes use the key-value attention mechanism to competitively write their embeddings into the workspace, and subsequently retrieve informa- tion from the workspace. Distant test nodes can indirectly interplay with training nodes through information stored in the workspace. For large- scale graphs trained mini-batch, in- terplay among out-of-batch nodes is feasible. This section elucidates the three steps of our method.
Wardspurz
Rew Fostere
Pottkea cocndde
GNN
sode2vec
M
M
X 7m
Banch
t
CAfe
Figure 3: InterpGNN-GW consists of three steps: 1) ex-
tract initial feature embedding and positional encoding. 2) Nodes compete for writing access to the global workspace. 3) Nodes retrieve information from the global workspace. The right part shows step two, where attention selects nodes and updates 7hn memory slots using the gate mechanism, with H and M' current node embeddings and memory.
Initial feature embedding and positional encoding. We first employ a graph neural network to encode raw node features into n dimmessional feature embeddings. For small-scale graph = (V, E, A) with node feature matrix X, employ single-layer GCN to initially encode the feature matrix to hidden embedding matrix = a (AXW,) For a large-scale graph, we adopt the mini- batch training method. We the graph clustering method such METIS (Karypis & Kumar, 1998) to partition G into subgraphs {G. = Ex]) where V. the node set of the c-th subgraph, and E. contains edges among nodes in V.. The feature matrix X and labels Y can also be partitioned into (X,) and (Ya)C-- In each epoch, we randomly select subgraph G. and obtain the embeddings for nodes in V. with H. (A Wo). The GCN encoder can be replaced with other GNNs such as GAT (Veličković et al., 2018), GAS (Fey et al., 2021). Node2vec is trained on the entire graph, producing diy-dimesioonal embedding employed as positional encoding. The 2ode2vec embeddings capture the structural properties of the graph by assigning similar embeddings close nodes. The positional encoding and clusters are generated only with the adjacency matrix which is accessible during training for transductive learning. For the rest of this section, we focus on approach for large-scale graphs since full-batch training on small-scale graph can be considered as having single partitioned subgraph (C 1).
e=
Nodes compete to write into the workspace. The workspace selects important nodes via attention mechanisms and stores their embeddings. The global workspace is composed of n.m memory slots,
5

---

Published as a conference paper at ICLR 2024
each of which is vector of length in- denoted as M [m1.-.. m.ml Keys and Values obtained by multiplying node embeddings with two different linear layers, i.e., K H. W w.k and V w = H. W w.n- Similarly,
obtain the Query matrix with memory Qn. = M'W way- The attention scores of the workspace w.r.t the nodes are obtained by applying Softmax to the dot- product of Query and Key. The product of the attentions scores and Value updates the workspace,
( ddz (Vda
M'' w.. ( (H. W w..kk
M softmax
V. softmax
He W w0,01
vdg
The gated approach (Santoro et al., 2018) is used to update the workspace for dynamic persistence.
Nodes reload information from the workspace. Utilizing the attention mechanisms again, the information within the workspace is broadcast to all nodes in Ve to update their embeddings. In this step, node embeddings construct queries Q+ -H.Wra r.g. and memory slots are utilized build keys and values, K, M r, V, =M++WW. r,k- The attention score of nodes each
memory slots is calculated by softmax Q. Thus, the information received by each node from val.
all memory slots weighted by attention score is:
H. H., (M
H softmax
M
(10)
vdz
The embeddings from the workspace contain partial information from all subgraphs. After incor- porating the information reloaded from the workspace into the node embeddings, we perform an additional passage-passinng to obtain the final node embeddings:
H = (A.A(HL @ W.)))..
(11)
where the @ be tensor addition or concatenation operations. In the next epoch, a new subgraph drawn and the process returns to the first step. This procedure iterates until the model converges or reaches the maximum training epochs. The training algorithm is described in Appendix E.
4 EXPERIMENTS
4.1 PROTOCOL AND SETUPS
Task and datasets. We conduct experiments semi-supervised transductive node classification on both small-scale and large-scale graphs, adopting full-batch and mini-batch training, respectively. The five small graph datasets include: CoraFull, Wiki-CS, AmazonPhoto, AmazonComputer, and Flickr, and the three large-scale graphs are AMiner-CS, Reddit, Amazon2M. Details are in Ap- pendix F.I. We use 60%/20%/20%
train/validation/eest random split for all datasets.
Implementation details of our approach. Firstly, we utilize GCN to encode the initial node fea- tures into embeddings with dimension na, which is selected from (32, 64, 128, 256). The dimension of the positional encoding is selected from {32, 128}. For the global workspace module, the num- ber of memory slots is selected from {8, 16, 32). and their dimensions can be opted within range of 32-1022 A multi-head dot product attention mechanism is utilized to govern the reading and writing of node embeddings within the global workspace. The above implementation is denoted as InterpGCN-GW We additionally use the historical embeddings in GNNAutoScale (Fey et al., 2021) and denote this implementation as InterpGAS-GW. We repeat the experiment for 10 times with dif- ferent initialization and record the mean and standard deviation. All experiments are conducted on a Titan 2080Ti with 11GB memory. More implementation details are Appendix F.2.
Baselines. We compare three groups of GNNs: 1) Full-batch GNNs: GCN (Kipf & Welling, 2017), GAT (Veličković et al., 2018), APPNP (Klicpera ct al., 2019). 2) Scalable GNNs; Clus- terGCN (Chiang et al., 2019), GraphSAINT (Zeng et al., 2020), GRAND+ (Feng et al., 2022), and GNNAutoScale (Fey et al., 2021). 3) (Scalable) graph transformers: SAN (Kreuzer et al., 2021), GraphGPS (Rampášek et al., 2022), Graphormer (Ying et al., 2021), and the recent scalable ANS- GT (Zhang et al., 2022b), NAGphormer (Chen et al., 2023) and NodeFormer (Wu et al., 2022). For large graphs, we only compare with scalable GNNs/graph transformers. The reported numbers are quoted from the papers given the same setting otherwise we run authors' code to produce the results.
4.2 MAIN RESULTS
Results on small graphs (ranging from 2k to 100k nodes). For small graphs, we use full-batch training, and the results are presented in Table 3. InterpGNN-GW outperforms all baselines, which

---

Published as a conference paper at ICLR 2024
Table 2: Comparison of scalable GNN and scalable graph transformers for large-scale node classi- fication with mini-batch training, Our approach lowers the O(IVa)) P) memory complexity of graph
transformers' pair-wise attention matrix to ([VV
mm))
Mathash
Mas Mis-baacbsasppc
Trae compleskyy
Measue coaplesit!
Oul-tlaachomm hrerpday cizancnecel
Prodiceal Pooticeal
CogpsAANT (Zeng atal, 2070
Randvn wotk
Grandi (Fou 2022)
Handoon
0 2-33 32
of Qikk A Add
Raxion poppazation
GaNoaasdeale they et 20211
METIS
oiik] - LNG E.B
o K. d)
Hitoiial cabol
ANS dinuse cia.., 30220)
MAB-tawei
OIJVss,,, n2 (KP))
DiS, By IKIP [KG df)
Pab-nisc aliasio
Prouinity encoding
[KM
cemesaiiiy Lapluizn Digrnsivve
NArghormer otar 2023)
OgiiciN 1P)
InarpCON (Doms)
MITTES
O]j +
O1 (KK]e-))
Glotsl ourtquuez
Sacn intortaat rodes Nodelwee
Time and memory for a mini-batch, G. = [V. En) is the sampled subgraph for current butch. Assume that both the impul and output dimensions of the embesldings hood. Af in Grand+ is the number of augmented feature matrices. o,, "y and in ANS-GT GT denote number of super-nodes, global nodes. and angmentations. For memory complexity, (V is attention matrix, [Vijd is mode embesldings, and of on linear layers.
fu method is the number of memory slots. in NAGphoener denotes the hop neighhor-
Table 3: Node classification on scale graphs (% + std). OOM: out of memory. Best in bold.
Darasets
CoraFull
Wiki-Cs
Computer
Photo
Flickr
Full bull-batch GNNs
GCN (Kipf & Welling, 2017)
68.94+ 0:23
79.82 1.02
89.34 + 0.82
93 - 0.27
49.65 + 0.15 48.20 (1.21 50.13
GAT (Velidkovid al., 2018)
67.51
0.19
80.56 0.82
90.24
0.25
83 0.33
APPNP (Kliepera et al. 2019)
67.01 2 0.27
80.98 + 0.80
90.81 1 0.21
91.51 = 0.23
= 0.36
Scalable GNNs
CCusterGCN (Chiang et al., 2019)
69.21
0.32
81.23 0.51
90:51 0.31
94.24 00.45
48.23 -0.49
GmphSAINT (Zeng et al. 2020)
71.32
0.13
81.65 29
90:91
0.55
84
0.24
51.01
0.11
Grand+ (Fong el al. 2022)
71.89
0.40
82.11 0.51
89.31
0.22
$1.81
0.12
61.31
0.31
GNNAutoScale (Pay el al. 2021)
71.08 0:36
82.78 0:39
88.92
0.34
95
0.42
49.31
0.44
Scalable GT
SAN (Kreuzer al. 2021)
78.25
89.33 0.26
93.
0.29
GraphGPS |Rampšskk 2021)
2022)
65.62
OOM
0.45
OOM
71.51 00M
00M
COM
U33 61
00.32
0DM
NACiphomer al. 2022)
78.62
(2 0:14
0.11
51.71
NodeFormer (Wu al., 2022)
65.38 0.91
80,69
1.19
88.49
1.07
93.
0.16
19.81
0.78
IntepGGN-GGW (ours)
71.72 0.337
82.92 0.18 83.31 + 0.26
92.10
0.23
05.46 0.15
52.41 0.22 63.05 + 0.32
InterpeGAS-GWW (ours)
71.31 + 0:31
91.27 + 0.37
96.
0.20
Table 5: Non-rigorous inductive node classifications (% + std).
Table 4: Node classification on large graphs (% + std).
Datosees
Reddic
AMines-C
Amazon2
Scalable GNN
CoraFull
Wiki-CS
ClusterGCN (Chiang et al., 2019)
92.00 + 0.19
65.73
:: 0.28
$6.32 : 0.28
ClusterGGNN
64.54 0.29
75.74 + 0.57
GopeSAINT (Zeng all 2020)
91 81.80 + 0.17
05.64
0.30
85.64
+
GRAND+
67.15 0.221
77.95 + 0.49
GNNAutoScale (Pay ot al, 2021)
Grand+ (Feng et al., 2022)
93.11 + 0.19
92.81 4: 0.27
66.19
67.11
0.41
0.31
86.32
56,01
1: 0.52
0.25
InterpGCN-GW
NodeFormer
68.78 + 0.34
65,90
81.49 + 0.29
76.49 0.76
Scalable GTs
ANS-GTT (Zhang al., 2022b)
87.61 0.31
Amazon2M
Aminer-CS
Reddit
NACphoomer (Chen al., 2023)
NodeFommer (Wu
2022)
92.87 1: 01.36
01.28
64.54 01.35
60.92 0.41
86,20 1: 0.39
0.29
83.85 = 0.27
61.59
0.37
89.77 = 0.35
84.12 + 0.18
62.48
0.36
92.05
0.23
IatepGIA GW (ours)
InterpGUNNGGW (ours)
93.35 + 0.20 92.75 0..23
69.01 1: 0.22
188 76
+ 0.31
89. 11
88.59 1: 0.19
0.14
88.13 + 0.24
84.25 + 0.41
67.85
62.12
+000-00:0 0.24
0.19
92.79 + 0.19
90.75 + 0.25
can be attributed to the global workspace preserving the important training node embeddings and conveying them remote test nodes during inference. For scalable graph transformers including NAGphomer and NodeFormer, which utilize the node-pair attention mechanism, InterpGNN- surpasses them notably. While the vanilla graph transformers such as GraphGPS, and Graphomer are infeasible on some small graphs due to out-of- -il-ooofomory errors. The introduction of historical embedding on small graphs does not guarantee performance improvement.
Results on large graphs (ranging from 200k to 2M nodes). Like ClusterGCN, our methods also use METIS (Karypis & Kumar, 1998) to partition the graph into clusters. For the other two compared baselines GraphSAINT and Grand+, we keep using their own partition method as sug- gested by the authors. It is worth noting that, InterpGNN-GW outperforms other baselines more notably than in small graph experiments, suggesting its effectiveness in mini-batch training where the massang between disparate batches is hindered. While in InterpGNN-GW, nodes from distinct batches can still exchange messages through the shared memory in the global workspace in a persistent way. InterpGAS-Gri GW outperforms InterpGCN-GY on some large graphs, indicating that historical embeddings can enhance the expressiveness of global workspace for mini-batch training. See Appendix G.1 for detailed memory comparison.
4.3 FURTHER STUDY AND DISCUSSION
Results on non-rigorous inductive learning. In order to further demonstrate the advantages of InterpGNN- GW, we conducted experiments in a non-rigorous inductive setting, where the model during training has access only to the feature of the training nodes. but not feature of the test nodes. Our method is capable of broadcasting the workspace to test nodes, even when these nodes still unseen during the training process. Thus, InterpGNN can efficiently convey information of training
7

---

Published as a conference paper at ICLR 2024
Acurary (%)
Accuma (%)
mn
Acturayy
#mmmayy slots
#inemor Slots
mEmOY langth
money length
(a) AMiner-CS
(b) Amazon2M
(a) AMiner-CS
(b) Amazon2M
Figure 4: Study the number of memory slots.
Figure 5: Study the length of memory slots.
Damni mods
IntpOONNG
web
GASHPE
Laplcian digmmcctuss
cxntrality
72-
12-
72
84
Accurac (%)
71
89
Acouaay
71-
@B
82
70
88
70
80
87
AmtratCS
CoraPull
WildCs
Redkit
Amazra2M
Figure 7: Comparison with dummy-nodes methods.
Figure 6: Ablation study on positional encoding.
Table 6: Comparison between InterpGCN-GW and GNNAutoScale (GAS) Fey et al. (2021) in terms of accuracy, GPU memory, and average training time per epoch
Reddit
AMiner-C'S
(#nodes per cluster=39, #edges/#nodes=49.8)
(#nodes per clusters=990, 1odges/#hodes=10.4))
Batch size
InterGGN--GW
GNNAutoScale
InterGGCN-GW
GNNAutoScale
32
91.7% M/5 4s
91.5%/2537MM6.
64. 1/3023M/2.5 3s
63.5/2207M/1 4s
64
0159//809M/66 Is
11.8%/3341M 68
65, 3/53///3 M/2.7 7s
64.9/2729M/11 8s
128
92.4%/27033//
92.3% Ss
66.4/8503M/3.58
65.8/5145M/3.1
256
13.0%/5171M/7 6is
92.8%/891 7M/7 6s
68.0/9021 M/4.5s
66.6/7543M/4. 94
512
03.45%/6989M/8..
93.19/1048877.46
67 07.2/10619M/6 99/6.66
66.5/9325M/7. 8s
1024
93.5%/8067M/10.
0OM
68. 68.2/10221M77.8
67.1/1061 3M/8.
nodes to test nodes during the test phase. Unlike other methods that exhibit significant performance degradation in inductive settings compared to transductive ones, InterpGCN-GW experiences only minor decrease in performance in this non-rigorous inductive setting, closely mirroring its trans- ductive results. The experimental outcomes are detailed in Table 5.
Ablation on the ability of memory persistence across nodes. Table 10 shows an ablation study, in which memory slots in the global workspace are initialized in each batch to store only the node information within the current batch. reveals that removing persistence negatively impacts perfor- mance both large and small graphs, especially for large graphs. We also conducted comparison on whether to use a gate mechanism when updating the memory, with results Table 10.
Ablation on positional encoding. Table compares the variants without positional encoding or using alternatives e.g. Laplacian eigenvectors in Kreuzer et al. (2021); Chen et al. (2023), and degree centrality in Ying et al. (2021). Removing node2vec positional encoding, which serves as positioning in memory read/write processes, leads to significant performance drop. The greater gain large graphs reveals the importance of relative topological information for non-interacting nodes in separate batches. Deterministic positional embeddings calculated directly from the adja- cency matrix, are less effective coordinating nodes than adaptive node2vec embeddings trained on graph structure, especially on large graphs. Additionally, the better performance of InterpGCN-GW compared to GAS+PE indicates the superiority of global workspace over historical embedding.
Study on number and size of memory slots. Fig. 4 and Fig. 5 examine the impact of memory slot number (nm) and length (Im) on large-scale datasets. Due to 2080Ti's IIBB memory constraints, we test up 64 slots. With relatively small number of memory slots (n S 16), the model's performance improves as 7m increases. Beyond that, further increments in memory slots yield modest performance enhancements. The trend in the length of the memory is similar the number of memory slots. However, an excessively large memory length decreases the accuracy for Aminer- CS. Meanwhile, the best results for Amazon2M is obtained when the memory size 512.
Comparison with GNN variants using historical embeddings. Our method shows greater im- provements on large graphs, as the workspace stores summaries of previous batches. Likewise, GN- NAutoScale (Fey et al., 2021) stores historical embeddings in the CPU and transfers out-of-batch
8

---

Published as a conference paper at ICLR 2024
1-hop neighbors' embeddings to the GPU during batch training. We evaluated global workspace and historical embedding efficiency on dense (Reddit) and sparse (AMiner-CS) datasets with vary- ing batch sizes (Table 6). Both methods improve with increasing batch size, but historical embedding occupies more memory on dense datasets and less on sparse ones. Global workspace has two ad- vantages: 1) It requires fixed extra memory, while historical embeddings' GPU memory depends on graph structure, causing more out-of-batch neighbors to be swapped from the CPU in dense datasets. 2) Historical embedding confined to fetching I-hop neighbors from the CPU, limiting the enhancement of long-distaen dinttiit node interplay.
Comparison with GNN variants using dummy nodes. In Zhang et al. (2022a); Liu et al. (2022), global dummy nodes are introduced and connected to all nodes for graph structure learning, Our global workspace method has advantages over dummy node-based methods: 1) Dummy nodes are compelled to receive information from all nodes, potentially causing over-squashing (Alon & Yahav, 2021). Global workspace, on the other hand, uses attention to selectively accept embeddings from few crucial nodes. 2) In mini-batch training, dummy nodes fail to facilitate message-passing among out-of-batch nodes, whereas InterpGCN-GW effectively summarizes nodes from previous batches using memory. The performance comparison between dummy nodes and global workspace on CoraFull and AMiner-CS datasets is shown in Fig. 7.
Improvement in fairness. Graph structure-induce un- fairnsss is worth studying, e.g., in social recommenda- tion systems where most training samples from one com- munity may lead to weaker generalization in another iso- lated communities. We explore structural unfairness by comparing the mean difference between the distribution of two node groups: those with direct connections to the training set and those without paths to the training set. We use faimess metric demographic parity
Table 7: Improvement in structure fair- ness. Smaller ASp, Ago indicate higher fairness.
Coma
Wiki-CS
Method
Agp
Ano
Agp
Aro
GCN
0.195
0.177
0478
0.432
InterpGCN-GW
0.158
0.164
0.451
0.402
A DP and equal opportunity AEO following Liu et al. (2023) with results in Table 7,
ADP Ener |Pr (ύ: = y/i E Vo) Pr (ū: - g/i Vi)
ABO = K EyEY Pr (f+- = ylu = y. E Vo) Pr (0:- = yly = Vi)
Our results indicate that introducing a global workspace enables isolated/distant nodes to access training node information, reducing structural unfairness compared to GCN. Experiments are con- ducted on small graphs due to the computational impracticability of calculating the node-pair dis- tance matrix on graphs with millions of nodes.
Results on heterophilic graph datasets. We have conducted experiments on heterophilic graph datasets, using official GitHub implementations with default hyperparameters for the baselines. The results are in Table 11. Observations on heterophilic graphs include: i) InterpGCN surpasses GCN on all three datasets, showing that enhancing distant node interplay via global workspace improves GCN's performance on heterophilic graphs. ii) As a plug-and-play module, our method combines well with other GNNs designed for heterophily, achieving improvements these models. iii) Our method's performance is reliant on the base feature extractor. For instance, on the Squirrel dataset, where GCN actually performs better than other heterophilic GNNs, our GCN-baser implementa- tion also outperforms implementations based on other models. Detailed discussions heterophilic graphs can be seen in Appendix G.3.
5 CONCLUSION AND FURTHER DISCUSSION
We derive PAC-Bayes bound for message-passing GNNs in semi-supervised transductive learning. The bound associates the generalization error with the interplay between test and training nodes. We then propose the Graph Global Workspace method to enhance the interplay among distant nodes and out-of-batch nodes. Experimental results show the superiority on both small and large graphs
Limitations. Based on our theoretical results, there could be more alternative techniques to enhance the generalization ability beyond our current technique. Also our work only covers the massage- passing scheme and there could emerge other forms of GNNs. Broader Impact. The proposed h-h interplay can also be integrated into more frameworks for analyzing generalization bounds. Our theory may inspire more works on novel design for GNNs for both accuracy and fairness.

---

Published as a conference paper at ICLR 2024
6 ACKNOWLEDGEMENTS
This work has been partially supported by the National Key R&D Program of China No. 2020YFB1710900 and No. 2020YFB1806700, NSFC Grants 61932014 and 62232011.
REFERENCES
S. Abu- Abu-aa-Haija, B. Perozzi, A. Kapoor, N. Alipourfard, K. Lerman, H. Harutyunyan. Greg Ver S., and A. Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neigh- borhood mixing. In ICMI, 2019.
Uri Alon and Eran Yahav, On the bottleneck of graph neural networks and its practical implications. In ICLR, 2021.
Pierre Alquier. User-friendly introduction to pac-bayes bounds. arXiv preprint 10.i::2100.1122 2021.
Bernard Baars. Global workspace theory of consciousness: toward a cognitive neuroscience of human experience. Progress in brain research, 2005.
Peter I. Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalized margin bounds for neural networks. NrurIPS, 2017.
Cristian Bodnar, Francesco Giovanni, Benjamin Chamberlain, Pietro Liò, and Michael Bronstein. Neural sheaf diffusion: A topological perspective heterophily and oversmoothing in gnns. In NeurIPS, 2022.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsuper- vised inductive learning via ranking. In ICLR, 2018.
Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and locally connected networks on graphs. In ICLR, 2014.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In AAAI, 2020a.
Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. NAGphormer: tokenized graph transformer for node classification in large graphs. In ICLR, 2023.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICML, 2020b.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In SIGKDD, 2019.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In NAACI, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Mathhis Minderer, Georg Heigold, Sylvain Gelly, al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint 2rXiv:2010.11929. 2020.
Simon Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang. and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. NeurIPS, 2019a.
Xingbo Du, Junchi Yan, and Hongyuan Zha. Joint link prediction and network alignment via cross- graph embedding. In IJCAI, 2019b.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:20/2.09699 2020.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In UAI, 2017.
10

---

Published as a conference paper at ICLR 2024
Pascal Esser, Leena Chennuru Vankadara, and Debarghya Ghoshdastidar. Learning theory can (sometimes) explain generalisation in graph neural networks. In NeurIPS, 2021.
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Tang. Graph random neural networks for semi-supervised learning on graphs. NeurlPS, 2020.
Wenzheng Feng, Yuxiao Dong, Tinglin Huang, Ziqi Yin, Xu Cheng, Evgeny Kharlamov, and Jie Tang. Grand+: Scalable graph random neural networks. In WWW, 2022.
Matthias Fey, Jan E Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. In ICML, 2021.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In ICML, 2020.
Pascal Germain, Alexandre Lacasse, François Laviolette, and Mario Marchand. Pac-bayesian learn- ing of linear classifiers. In ICML, 2009.
Pascal Germain, Alexandre Lacasse, François Laviolette, Mario Marchand, and lean-Franchs Roy. Risk bounds for the majority vote: from a pac-bayesian analysis to a learning algorithm. JMLR, 2015.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In ICML,
Anirudh Goyal, Aniket Rajiv Didolkar, Alex Lamb, Kartikeya Badola, Nan Rosemary Ke, Nasim Rahaman, Jonathan Binas, Charles Blundell, Michael Curtis Mozer, and Yoshua Bengio. Coordi- nation among neural modules through a shared global workspace. ICLR, 2022.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In SIGKDD, 2016.
Benjamin Guedj. A primer on pac-bayesian learning. arXiv preprint 1 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In NeurlPS, 2017.
Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sam- pling. ICML, 2020.
Wassily Hoeffding. Probability incqualities for sums of bounded random variables. The collected works of Wassily Hoeffding, 1994.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. arXiv preprint arXiv:2005.00687 2020.
Johan Ludwig William Valdemar Jensen. Sur les fonctions convexes et les inégalités entre les valeurs moyennes, Acta mathematica, 1906.
Di Jin, Zhizhi Yu, Cuiying Huo, Rui Wang, Xiao Wang, Dongxiao He, and Jiawei Han. Universal graph convolutional networks. In NeurlPS, 2021.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal on scientific Computing. 20(1):359-392, 1998.
Amir Hosein Khasahmadi, Kaveh Hassani, Parsa Moradi, Leo Lee, and Quaid Morris. Memory- based graph networks. In ICLR, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLRR 2017.
11

---

Published as a conference paper at ICLR 2024
Johannes Kliepera, Aleksandar Bojchevski, and Stephan Gunnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
Vladimir Koltchinskii and Dmitry Panchenko. Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, 30(1):1-50, 2002.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. In NeurlPS, 2021.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In ICCV, 2019.
Renjie Liao, Raquel Urtasun, and Richard S. Zemel. A pac-bayesian approach to generalization bounds for graph neural networks. In ICLR, 2021.
Xiaorui Liu, Jiayuan Ding, Wei Jin, Han Xu, Yao Ma, Zitao Liu, and Jiliang Tang. Graph neural networks with adaptive residual. NeurIPS, 2021.
Xin Liu, Jiayang Cheng, Yangqiu Song, and Xin Jiang. Boosting graph structure learning with dummy nodes. In ICML, 2022.
Zemin Liu, Trung-Kien Nguyen, and Yuan Fang. On generalized degree fairesss in graph neural networks. arXiv preprint arXiv:2302.04 0302003881, 2023.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint
1rXiv:1711.05101, 2017.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. In NeurlPS, 2022.
Sitao Luan, Chenqing Hua, Minkai Xu, Qincheng Lu, Jiaqi Zhu, Xiao Xino-Wen Chang, Jie Fu, Jure Leskovec, and Doina Precup. When do graph neural networks help with node classification: In- vestigating the homophily principle on node distinguishability. arXiv preprint urXiv:2304. 14274, 2023.
Denis Lukovnikov and Asja Fischer. Improving breadth-wise backpropagation in graph neural net- works helps learning long-range dependencies. /CML, pp. 7180-7191, 2021.
Chen Ma, Liheng Ma, Yingxue Zhang, Jianing Sun, Xue Liu, and Mark Coates. Memory augmented graph neural networks for sequential recommendation. In AAAI, 2020.
Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup generalization and faimeess of graph neural networks. NeurIPS, 2021.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? In ICLR, 2022.
Haitao Mao, Zhikai Chen, Wei Jin, Haoyu Han, Yao Ma, Tong Zhao, Neil Shah, and Jiliang Tang. Demystifying structural disparity in graph neural networks: Can one size fit all? arXiv preprint arXiv:2306.01333 2023.
Sohir Maskey, Ron Levie, Yunseok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. In NeurlPS, 2022.
Andreas Maurer. A note on the pac bayesian theorem. arXiv preprint cs/04/ 1099, 2004.
David A McAllester. Some pac-bayesian theorems. In COLT, 1998.
David A McAllester. Pac-bayesian model averaging. In COLT, 1999.
David A McAllester. Pac-bayesian stochastic model selection. Machine Learning, 2003a.
David A. McAllester. Simplified pac-bayesian margin bounds. COLT, 2003b.
Péter Mernyei and Cätälina Cangea. Wiki-cs: A wikipedia-based benchmark for graph neural net- works. arXiv preprint 2rXin22007.02901, 2020.
12

---

Published as a conference paper at ICLR 2024
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to 2017.
margin bounds for neural networks. arXiv preprint arXiv:170700966,
Kenta Oono and Taiji Suzuki. Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. In NeurlPS, 2020.
Myle Ott, Sergey Edunov, Alexci Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: A fast, extensible toolkit for sequence modeling. In NAACL, 2019.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. In NeurIPS, 2022.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In ICLR, 2020.
Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bron- stein. Graph-coupled oscillator networks. In JCML, 2022.
Adam Santoro, Ryan Faulkner, David Raposo, Jack Rae, Mike Chrzanowski, Theophane Weber, Daan Wierstra, Oriol Vinyals, Razvan Pascanu, and Timothy Lillicrap. Relational recurrent neural networks. NeurIPS, 31, 2018.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The cherin-chervonnnkis dimension of graph and recursive neural networks. Neural Networks, 108:248 259,, 2018.
Matthias Seeger. Pac-bayesian generalisation error bounds for gaussian process classification.
JMLR, 2002.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint
2018
Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu Aggarwal, Prasenjit Mitra, and Suhang Wang. Investigating and mitigating degree-related biases in graph convoltuional networks. In CIKM, 2020.
Joel Tropp User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 2012.
Leslic G Valiant. A theory of the learnable. Communications of the ACM, 1984.
Rufin VanRullen and Ryota Kanai. Deep learning and the global workspace theory. Trends in Neurosciences, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. NeurIPS, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural net- works. In SIGKDD, 2019.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In ICML, 2019.
Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. NeurIPS, 2022.
Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. DIFFormer: Scalable (graph) transformers induced by energy constrained diffusion. In ICLR, 2023.
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. In NeurIPS, 2021.
13

---

Published as a conference paper at ICLR 2024
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In ICDM, 2022.
Cheng Yang, Chunchen Wang, Yuanfu Lu, Xumeng Gong, Chuan Shi, Wei Wang, and Xu Zhang. Few-shot link prediction in dynamic networks. In WWW, 2022.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In ICML, 2016.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? In NeurIPS, 2021.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Raigopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In ICLR, 2020.
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kan- nan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. NeurIPS, 2021.
Shaofeng Zhang. Feng Zhu, Junchi Yan, Rui Zhao, and Xiaokang Yang. Dotin: Dropping task- irrelevant nodes for gnns. arXiv preprint arXiv:2204. 13429, 2022a.
Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan. Bridging theory and algorithm for domain adaptation. In ICML, 2019.
Zaixi Zhang, Qi Liu, Qingyong Hu, and Chee-Kong Lee. Hierarchical graph transformer with adaptive node sampling. In NeurlPS, 2022b.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. ICLR, 2020.
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv:2202.07062 0700020000022. 2022.
Jiong Zhu, Yujum Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily graph neural networks: Current limitations and effective designs. In NeurlPS, 2020.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka. Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI conference on artificial intelligence, 2021.
14


Reviews:
[{"review_id": "ClTGXpxT3o", "reviewer": "Reviewer_mAhi", "summary": "This paper aims to propose a theory to derive a PAC-Bayesian bound for message-passing GNN in the transductive node classification and interpret the structure imbalance phenomenon. Based on the theory, authors propose the InterpGNN-GW to enhance the interplay between distant and intra-batch nodes via an attention-based global workspace mechanism.", "questions": "See Weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The derived bound in this paper shows that more information interaction between test and training nodes can lead to smaller generalization errors and interpret the structural imbalance phenomenon.\n2. To address the problem, the authors proposed a new method called InterpGNN-GW which leverages the attention mechanism to global workspace.\n3. Sufficient experiments on different graph datasets have been conducted. The proposed InterpGNN-GW outperforms many baseline methods both on small-scale graphs and large-scale graphs.\n4. The paper presentation is good and the organization is clear and easy to follow.", "weaknesses": "1. In the ‘Theorem 1 interpret the structure imbalance phenomenon.’ part, authors claim that stronger interplay with training nodes brings small generalization error, and nodes with smaller degrees engage in fewer interactions with training nodes thus having the trend in Fig2. However, it seems like a mistake according to the authors' theory. Nodes with smaller degrees engage in fewer interactions with training nodes should have bigger generalization error, while in fig2 nodes with fewer degrees have better performance.\n2. The Experiment part mainly concentrates on node classification performance and ablation study. It would be better to design experiments to show how InterpGNN-GW increases the interplay between training and test nodes, which also strengthens the claims in theory and interprets the structure imbalance phenomenon.\n3. Lack the motivation to concatenate positional encoding. Authors may add motivation such as position embedding containing the interplay with training and test nodes.\n4. It would be more convincing if authors could provide full ablation study results on all datasets instead of separating ablated models to Tab 5 and Fig 6 and using different datasets.\n5. Can InterpGNN-GW be used in a non-rigorous inductive setting? If yes, what about performance? For example, train InterpGNN-GW on the training nodes and broadcast the workspace to test nodes with test nodes still unseen to the training process. It should be similar to interplaying among out-of-batch nodes mentioned in the intuition part.\n6. Why does InterpGNN-GW fail to outperform some baselines on CoraFull, any in-depth or intuitive analysis?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "AsMo4IbH9w", "reviewer": "Reviewer_wkbK", "summary": "This paper focuses on understanding and improving the generalization ability of Transductive Graph Neural Networks (GNNs) by enhancing the interplay between training and test nodes. The authors address the problem of information flow shortage between distant nodes and intra-batch nodes in GNNs, which hampers their generalization ability. They propose incorporating the L-hop interplay for an L-layer GNN in a PAC-Bayesian bound to quantitatively analyze the influence of the interaction between training and testing sets on generalization ability. Additionally, they introduce a plug-and-play module called InterpGNN-GW, which enhances the interplay between distant and intra-batch nodes using a Graph Global Workspace and key-value attention mechanism. The authors validate their theory and approaches through experiments on small-scale and large-scale graph datasets.", "questions": "1. \"results concerning graph structure is missing\". Homophily/Heterophily is one of the most important properties of the graph structure, but is missed in this paper[1-4].\nSee [4] for a study with PAC-Bayesian generalization bound.\n2. \"more information interaction between test and training nodes can lead to smaller generalization error\" I doubt the correctness of this claim on heterophilic graphs, see [3].\n3. Compared to the graph transformers based on inner-batch pair-wise attention, the global workspace can provide global consistency.\" The idea of building global consistency is interesting.\n4. \"Implicit connection\" [5] estabilsh graph rewiring method to rebuild some implicit connection between nodes.\n5. \"the labels of training set $S_Y$ , the features of both training and test nodes $X = [S_X,U_X]$\". The notations are wierd. I suggest \"$S_Y$\" --> \"$Y_S$\", \"$X = [S_X,U_X]$\" --> \"$X = [X_S,X_U]$\".\n6. \"premise that embedding exchange among connected nodes leads to closer output logits\" This premise is invalid for heterophilic graphs. See examples in [1-3].\n7. \"Theorem 1 interpret the structure imbalance phenomenon.\" How does theorem 1 interpret the structure imbalance phenomenon? You need to elaborate it in the main paper. You only test on homophilic datasets (Cora, CiteSeer, PubMed). To make claims about grouping effect, you need also test on heterophilic datasets.\n8. Ablation study on memory and the gate control of memory doesn't show the effectiveness of memory and the gate control. The proposed models doesn't show statistically better performance than SOTA. Again, the model needs to be tested on heterophilic graphs.\n\nAlthough missing lots of related works and analysis on heterophilic graphs, I still find this paper interesting. I will consider raising my score if the authors address my concerns well.\n\n\n[1] Is Homophily a Necessity for Graph Neural Networks?. In International Conference on Learning Representations 2022.\n\n[2] Revisiting heterophily for graph neural networks. Advances in neural information processing systems, 35, 1362-1375.\n\n[3] When do graph neural networks help with node classification? Investigating the impact of homophily principle on node distinguishability. arXiv preprint arXiv:2304.14274.\n\n[4] Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?. arXiv preprint arXiv:2306.01323.\n\n[5] Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2021.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Solid theoretical analysis and interesting idea.", "weaknesses": "See below", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "cAHmk9yTy8", "reviewer": "Reviewer_kZmE", "summary": "In this paper, the authors derive transductive PAC-Bayesian bounds for GNNs, by which they reveal that the interplay between training and testing nodes effects the generalization ability of GNNs. With this observation in mind, they design a plug-and-play module to enhance this interplay. This module maintains a memory bank of node embedding and adopts key-value attention mechanism to update the embedding and the model weights. Their framework is validated on both small- and large-scale graph datasets.", "questions": "- The experiments show that the proposed module could also reduce structural unfairness. Can you provide a further explanation for this phenomenon? If the reason is the interplay between training and testing nodes induced by attention mechanism, I guess that graph transformer models can also reduce structural unfairness.\n- Graph Transformer models (e.g., GraphGPS) could also enhance the interplay between training and testing nodes more or less. Why these methods perform inferior to the proposed method?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The theoretical results are interesting and provide new insights to the generalization of GNNs.\n- The proposed module is reasonable, and the experimental results are sufficient to demonstrate its effectiveness.", "weaknesses": "- There is a discrepancy between theory and practice. The ''transductive'' or ''semi-supervised'' setting the authors adopt is the same as that in [1], where the randomness come from the labels of nodes. However, in real-world applications, including the experiments of this paper, both nodes features and their labels are fixed, and the randomness come from the random partition of training and test nodes [2,3,4]. Therefore, I think that the authors should use the results in literatures [5,6], e.g., Corollary 7 in [6] to derive similar results as Lemma 1. This can be done by incorporating the techniques in works [7,8]. Otherwise, the authors should conduct some synthetic experiments that treating labels as random variables to verify their theoretical results.\n- The authors claim that the proposed module is plug-and-play, which means that it can be applied on any GNNs. However, they only equip GCN with this module. Performing more experiments that applying this module to other type of GNNs is encouraged.\n\n[1] Ma et al, Subgroup generalization and fairness of graph neural networks. NeurIPS 2021.\n\n[2] Oono et al, Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. NeurIPS 2020.\n\n[3] Esser et al, Learning theory can (sometimes) explain generalisation in graph neural networks. NeurIPS 2021.\n\n[4] Cong et al, On provable benefits of depth in training graph convolutional networks. NeurIPS 2021.\n\n[5] Derbeko et al, Explicit learning curves for transduction and application to clustering and compression algorithms. JAIR 2004.\n\n[6] Begin et al, PAC-Bayesian theory for transductive learning. AISTATS 2014.\n\n[7] Neyshabur et al, A PAC-Bayesian approach to spectrally-normalized margin bounds for neural networks. ICLR 2018.\n\n[8] Liao et al, A PAC-Bayesian approach to generalization bounds for graph neural networks. ICLR 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "wLZfw4TCRu", "reviewer": "Reviewer_fk5N", "summary": "In this paper, the authors derive a PAC-Bayesian bound specifically tailored for message-passing Graph Neural Networks (GNNs) within the context of transductive node classification. They present a novel approach called Graph Global Workspace (InterpGNN-GW), designed to enhance the interaction between nodes both within and across batches. In this method, nodes equipped with positional encoding engage in a competitive process, allowing them to write to and read from a shared global workspace using key-value attention mechanisms. The results of their experiments, conducted on both small- and large-scale graph datasets, reveal the remarkable effectiveness of InterpGNN-GW in node classification tasks when compared to other scalable GNNs and graph transformers. This signifies a noteworthy advancement in the field of graph-based machine learning.", "questions": "1.\tIn Figure 2, the criteria for grouping based on node degree are somewhat confusing. For example, what do the numerical values on the x-axis in the figure represent? I assume these values are simply categories for grouping, rather than actual node degrees. I believe the authors could provide a clearer explanation of the grouping criteria.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThey have introduced a PAC-Bayes bound for message-passing Graph Neural Networks (GNNs) in the context of semi-supervised transductive learning. This bound sheds light on the quantifiable relationship between test and training nodes and its impact on the generalization capacity of GNNs in node classification tasks, making it a noteworthy contribution.\n\n2.\tTheir approach demonstrates superior performance over advanced baseline methods in node classification tasks across a range of dataset scales, thereby highlighting its efficacy and scalability. Moreover, the article exhibits a well-structured and in-depth exploration of the background and related research concerning the generalization bounds of Graph Neural Networks (GNNs). Remarkably, the authors skillfully integrate the utilization of the graph global workspace with the PAC-Bayes bound they have developed in practical applications, offering a significant advantage in terms of global consistency compared to conventional graph transformers.\n\n3.    The comparative experiments are well thought out, taking into account factors such as GNN variants with the inclusion of dummy nodes and historical embeddings.", "weaknesses": "1.\tThe idea of the Global Workspace is intriguing, but it has already been extensively explored in previous research mentioned by authors, diminishing the novelty of this work.\n2.\tSome concepts lack a comprehensive explanation, such as W_{r,k} in Eq. (10). Further refinement is needed for these elements, including a clearer explanation of the dimensions of linear layers, which would enhance the clarity of the paper.\n3. Table 5 does not provide standard deviations.\n4. Results provided in table 3 and 4 are limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "HnJTYvGnMw", "reviewer": "Reviewer_qP57", "summary": "This paper proposes a PAC-Bayesian generalization error bound for GNNs and shows the influence of the interplay between training and testing sets on the generalization ability. Based on the theoretical analysis, the authors design a plug-and-play Graph Global Workspace module to enhance the generalization capability.", "questions": "1. In equation 7, why do you need max operation since $L-r+1>0$ always holds?\n\n2. In Figures 1 and 2, the group 2 usually have the higher accuracy and smaller generalization error. Do you have any explanation for this observation?\n\n3. In the experiment on comparison with GNN variants using Dummy nodes, what is the method (denoted as Dummy nodes in Figure 7) used for comparison? This experiment is confusing.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The PAC-Bayesian generalization error bound for GNNs is interesting and it shows how the interplay between training and testing sets influences the generalization ability.\n\n2. The proposed method outperforms most baseline methods across multiple graph datasets.\n\n3. The presentation of this paper is good and the paper is easy to follow.", "weaknesses": "1. Although the authors derive PAC-Bayesian bound for GNNs in the transductive setting and show how the interplay between training and testing sets influences the generalization ability, I fail to see the strong connection between the theoretical analysis and the proposed method. The proposed method seems to simply adopt the idea of the self-attention mechanism from the transformer and apply it to the graph. It's not clear to me how the proposed method enhances the generalization for the distant nodes.\n\n2. My major concern about the proposed method is the graph partition as partitioning the graph usually leads to information loss. Though node2vec is used for positional encoding purposes, it only encodes the local topological structure, and it cannot compensate for the lost information between different subgraphs. Based on algorithm 1 in Appendix E, there is no information exchange between different subgraphs. The nodes in a subgraph can only receive the information from other nodes within this subgraph and these nodes are isolated from the nodes from other subgraphs. The performance seems to highly depend on the quality of the graph partition algorithms. However, it's unclear whether different graph partitions will influence the performance of the proposed method or not.\n\n3. Some experimental setups are not quite clear. See questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)