Graph Classification via Reference Distribution Learning: Theory and Practice
Authors: Zixiao Wang
Jicong Fan
Venue: NeurIPS 2024 poster (2024)
Keywords: graph neural networks
graph classification
Primary area: graph_neural_networks

Abstract: Graph classification is a challenging problem owing to the difficulty in quantifying the similarity between graphs or representing graphs as vectors, though there have been a few methods using graph kernels or graph neural networks (GNNs). Graph kernels often suffer from computational costs and manual feature engineering, while GNNs commonly utilize global pooling operations, risking the loss of structural or semantic information. This work introduces Graph Reference Distribution Learning (GRDL), an efficient and accurate graph classification method. GRDL treats each graph's latent node embeddings given by GNN layers as a discrete distribution, enabling direct classification without global pooling, based on maximum mean discrepancy to adaptively learned reference distributions. To fully understand this new model (the existing theories do not apply) and guide its configuration (e.g., network architecture, references' sizes, number, and regularization) for practical use, we derive generalization error bounds for GRDL and verify them numerically. More importantly, our theoretical and numerical results both show that GRDL has a stronger generalization ability than GNNs with global pooling operations. Experiments on moderate-scale and large-scale graph datasets show the superiority of GRDL over the state-of-the-art, emphasizing its remarkable efficiency, being at least 10 times faster than leading competitors in both training and inference stages.

Graph Classification via Reference Distribution Learning: Theory and Practice
Zixiao Wang Jicong Fan"
School of Data Science
The Chinese University of Hong Kong. Shenzhen
zixiaowang@link. cuhk. edu. fanjicong@cuhk. edu.
Abstract
Graph classification is a challenging problem owing to the difficulty in quantify- ing the similarity between graphs representing graphs vectors, though there have been a few methods using graph kernels or graph neural networks (GNNs). Graph kernels often suffer from computational costs and manual feature engineer- ing, while GNNs commonly utilize global pooling operations, risking the loss of structural semantic information. This work introduces Graph Reference Distri- bution Learning (GRDL), an efficient and accurate graph classification method. GRDL treats each graph's 's latent node embeddings given by GNN layers as a discrete distribution, enabling direct classification without global pooling, based on maximum mean discrepancy adaptively learned reference distributions. To fully understand this new model (the existing theories do not apply) and guide its configuration (e.g., network architecture, references' sizes, number, and reg- ularization) for practical use, we derive generalization error bounds for GRDL and verify them numerically. More importantly, our theoretical and numerical results both show that GRDL has stronger generalization ability than GNNs with global pooling operations. Experiments on moderate-scall and large-scale graph datasets show the superiority of GRDL over the state-of-the-arr, emphasizing its remarkable efficiency, being at least 10 times faster than leading competitors in both training and inference stages. The source code of GRDL is available at https: //github. com/ commjiccongfii an/ CRe//GRDL--R GRDDGGRDLahahhaa Graph Classification
1 Introduction
Graphs serve as versatile models across diverse domains, such as social networks Wang et al. 2018
biological compounds (Jumper et al.) [021]. and the brain [Ktena et al.) 2017]. | There has been
considerable interest developing learning algorithms for graphs, such as graph kernels Gärtner
et al. [200 [Shervashidze et al. [001 Chen et al. 2002b) and graph neural networks (GNNs) Kipp
and Welling 2016]
2016 Gilmer al. [017]. GNNs have emerged as powerful tiie-oofthheart performance various graph prediction tasks Veličković et al.
et al.
tools, showcasing
2017 Gilmer et al. 2017 Hamilton et al.) 2017 Xu et al. 2018 Sun et al. 2019 You et al. 20221
Ying al. 202 Liu et al. 2022b Chen et al. 2022a Xiao et al. 2022 Sun et al. 2023 Sun and Fan
2024 Sun et al. 2024]. Despite the evident success of GNNs in numerous graph-relate applications,
their potential remains underutilized, particularly in the domain of graph-level classification.
Current GNNs designed for graph classification commonly consist two components: the embedding of node features through message passing [Gilmer et al.) 2017) and subsequent aggregation by some permutation invariant global pooling (also called readout) operations [Xu et al. [2088.. The primary purpose of pooling is to transform graph's 's node embeddings, matrix, into single vector.
"Corresooning author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Empirically, pooling operations play crucial role in classification (Yng et al. 2018). However, these pooling operations tend to be naive, often employing methods such as simple summation or averaging. These functions collect only first-order statistics, leading to loss of structural or semantic information. addition to the conventional sum or average pooling, more sophisticated pooling operations have shown improvements in graph classification [Li et al., [013] Ying et al. 20188] Lee cct al., 2019 2021 Buterez et al., 2022 Yu et al., 2024). but they still carry the inherent risk of information loss.
Different from graph kernel methods and existing GNN methods, we propose novel GNN method that classifies the nodes' embeddings themselves directly, thus avoiding the global pooling step. In our method, we treat the nodes' latent representations of each graph. learned by neural network, as a discrete distribution and classify these distributions into K different classes. The classification is conducted via measuring the similarity between the latent graph 's distributions and K discriminative reference discrete distributions. The reference distributions can be understood as nodes' embeddings of representative virtual graphs from K different classes, and they are jointly learned with the parameters of the neural network in an end-to-end manner. To evaluate our method, we analyze the generalization ability of our model both theoretically and empirically. Our contributions are two-fold.
We propose novel graph classification method GRDL that is efficient and accurate.
GRDL does not require any global pooling operation and hence effectively preserves the information of node embeddings.
Besides its high classification accuracy, GRDL is scalable large graph datasets and is at least ten times faster than leading competitors in both training and inference stages.
We provide theoretical guarantees, e.g. generalization error bounds, for GRDL.
The result offers valuable insights into how the model performance scales with the properties of graphs, neural network structure, and reference distributions, guiding the model design. For instance, the generalization bounds reveal that the references' norms and numbers have tiny impacts on the generalization, which is also verified by the experiments. More importantly, we theoretically prove that GRDL has stronger generalization ability than GNNs with global pooling operations.
The rest of this paper is organized as follows. We introduce our model in Section 2 and analyze the generalization ability in Section 3 Related works are discussed in Section Section 5 presents the numerical results on 11 benchmarks in comparison to 12 competitors.
2 Proposed Approach
2.1 Model Framework
Following convention, we denote a graph with index i by G, (V, where V, and E, are the vertex (node) set and edge set respectively. Given a graph dataset where ys E 21. K} is the associated label of G, and (Gn,NN)) (G.......,,.uu
{(G1,81). (G2,32),.... v2)....,
yi k means G, belongs to class the goal to learn classifier from that general- izes well to unseen graphs. Since in many scenarios, each node of a graph has feature vector and the graph is often represented by an adjacency matrix A, we also write G, (A,, X,) for convenience, where A; RR.x,., X; E RRn. n4 [V/] is the number of nodes of graph i, and dy denotes the number of features. We may alternatively denote the graph dataset as G [[(([((A))))) X1), y1), ((Ag, X2), y2)..... ((AN, XN), JN)).
Our approach is illustrated in Figure [ For graph classification, we first use a GNN, denoted as fc. to transform each graph to a node embedding matrix H, E Raxdd that encodes its properties, i.e., (1)
H fG, fc(A,, X,),
where fo E FG and Fe denotes hypothesis space. The remaining task classify H, without global pooling. Direct classification of node embeddings is difficult due to two reasons:
Different graphs have different numbers of nodes, i.e. in general, n4 n, if i $ The node embeddings of each graph are permutation invariant, namely, PH, and H, represent the same graph for any permutation matrix P.
However, the two properties are naturally satisfied we treat the node embeddings of each graph as discrete distribution. Specifically, each H, is a discrete distribution and each row of H. is an

---

D1 E R
E(H,, D1)
fG
fD
Big
y/pedd
H; E R
G = (A,
{HH, Dx)
D E R Rmd
Figure 1: The GRDI. framework. Classification involves using GNN fa to encode a graph's information into a node embedding distribution. The similarities between the node embeddings and K reference distributions calculated by the reference module fD. The graph is assigned the label of the reference that exhibits the highest similarity.
outcome of the distribution. There is no order between the outcomes in each distribution. Also, different distributions may have different numbers of outcomes. Before introducing method in detail, we first give toy example where the commonly used mean and max pooling operations fail.
Example 2.1. Suppose two graphs Gi and G2 have self-looped adjacency matrices Á [1 1 0; 0 1;1 0 1;0 1 1] and A2 [1 0:0 0:0 1 0,0 0 0 1] respectively, and have one one- dineemimnio node features X₁ 6369 12 and X₂ [6699] respectively. Let A, be the normalized adjacency matrices, iee. A, = diag (A,1) 1/2 diag (Aai(i(AA1)) (A,1) 1/2 Performing the neighbor aggregation H; = i 1,2, we obtain H1 = 96789] and H2 = 7.5 T We see that mean (H, mean(H2) 7.5 and max(H,) max(H2) 9. This means the simple mean and max pooling operations failed to distinguish the two graphs. In contrast, our method treats Hj and H2 as two different discrete distributions and hence able to distinguish the two graphs. Note that incorporating learnable parameter W, i.e. H, A,X,W, W, or performing multiple times of neighbor aggregation does not change the conclusion.
We propose to classify the discrete distributions {H, H H....... HN) A H. by reference layer fo- The classification involves measuring the similarity between H. and reference discrete distributions [D1, D2..... D k & DD that are discriminative. Each Dj xd can be understood as node embeddings of virtual graph from the k-th class, [K]. We make mi _... mn for convenience. Letting & be a similarity measure between two discrete distributions, then
Sik == EHH, DR), ie [N], k E [K].
(2)
This forms a matrix [s S2...., sN] where
(D, [s.1, 8/2 ................................ sik] R²
(3)
Jn E FD and Fn denotes hypothesis space induced by the reference layer. References in D parameters of the reference layer and are jointly learned with node-embedding network parameters in end-to-end manner. Now combining Equation (I) and Equation (3), we arrive at
S; = (D(((C)))) [N].
fD o fa calculates s,, representing similarities between G, and all references. We get G,'s 's label by
Uprod, = arg max Sik. k
(5)
To train the model, we first use the softmax function to convert s; to a label vector y; [ūa...., 0ik] where
exp (xp()i)
Úsk
[K].
(6)
ΣØn exp (Rir)"
3

---

Using the cross-entropy loss, we minimize
N
K
LCE
log Dik-
N
Intuitively, the reference distributions D should be different from each other to ensure discrimina- tiveness. Therefore, we also consider the following discrimination loss:
Dis
Σ & W/g
Σ
Dkr).
(8)
Then we solve the following problem:
min FoEFe.DDED
Lce + ALDis
(9)
where 2 hyperparameter. We call (9) Graph Classification via Reference Distribution Learning (GRDL). Specific designs of Fo and Fo are detained in the next section.
2.2 Design of FG and FD
We get GRDL's network F by concatenating the node embedding module and the reference module:
F FD o FG.
(10)
Design of Fg We an L-layer message passing network our node embedding module Fe:
Fo F o Fl
(11)
Fl is the I-th message passing layer (e.g. a GIN layer et al. 2018 that updates the representation of node by aggregating representations of its neighbors, meaning
= AGGREGATE()) ((---1) : E (
h COMBINE (nQ-2), .a!)
(12)
where () the feature vector of node v produced by the I-th layer F!. Different GNNs have different choices of COMBINE(()) and AGGREGATE")))
Design of FD Based on 3 the hypothesis space defined by the reference layer is
FD HH: + s; E ERK 8i2 E(H,, D&), E RRdd
(13)
In our work, we choose ((,)) be the negative squared Maximum Mean Discrepancy (MMD). Initially used for two-sample tests, MMD is now widely used to measure the dissimilarity between distributions (rretton et al. 2012a]. For an embedding H nuxd and a reference D E mxx
E(H, D) = MMD (H, D)
((h)
(d,)
2
o (h))
Td(d))
(b)) (bb))
o(d,)
o(d,y)
n
m
1=1
1=1'=
(14)
where is some feature map. h is the i-th row of H, and d is the j-th row of D. The MMD in (I4) is known as biased MMD [Gretton et al. 2012a| and its performance is almost the same as the unbiased one, in our experiments. Therefore we only present (14) here. Using kernel trick kxxx = (xx) (xx'), we obtain from (14) that
2
72
1
T
X76
{HH
k(h; d,)
k(,, h2)
dy)
mn
n
m
7==1
j=1
In this work, we employ the Gaussian kernel, i.e.,
k(x,x') exp (-0lix x'113)
(15)

---

where 0 >> O is a hyperparameter. The Gaussian kernel defines an infinite-order polynomial feature map o, covering all orders of statisties of the imput variable. Consequently, MMD with the Gaussian kernel characterizes the difference between two distributions across all moments. Actually, we found that, in GRDI,, the Gaussian kernel often outperformed other kernels such as the polynomial kernel.
Several other statistical distances are available for measuring the difference between distributions, including Wasserstein distance and Sinkhorn divergence (Peyré and Cuturi 2020). However, their computational complexity is prohibitively high, making the model impractical for large-scale graph datasets. We also find, through experiments, that our method, the classification performance of MMD is better than that of Wasserstein distance and Sinkhorn divergence as shown later in Table [] These explain why we prefer MMD.
2.3
Algorithm Implementation
The 0 in the Gaussian kernel (T) plays a crucial role in determining the statistical efficiency of MMD. Optimally setting of 0 remains open problem and many heuristics are available [Gretton et al.
2012b]. To simplify the process, we make learnable in our GRDL and rewrite as Eo. Our empirical results in Appendix DD5 show that GRDL with learnable 0 performs better. For convenience, denote all the parameters of Ja as w and let SW,D,0 = .n o Sa. Then we rewrite problem (9) as
exp (fw.).o(G:)))
min W,D,0
Yik log
+ A E (D Dw).
(16)
Σj= exp (fw, D.0 (G.)))
k'
The (mini-batch) training of GRDL model is detailed in Algorithm |
(see Appendix C
3 Theoretical Analysis
In this section, we provide theoretical guarantees for GRDL,, due to the following motivations:
As the proposed approach is novel, is necessary to understand thoroughly using theoretical analysis, e.g., understand the influences of data and model properties on the classification. It is also necessary to provide guidance for the model design to guarantee high accuracy in inference stages.
3.1 Preliminaries
We construct big matrices X, A and D, where X = X :..... x RCC, md)xd. A Biag(Ai, ..,, AN)
Matrix constructions
m=x ni) is block diagonal matrix, D DD..D....... DR] K E Kmxd The adjacency matrix with self-connectivity is À A + I. The
huge constructed graph is denoted by G (Å, X). This construction allows us to treat all graphs in dataset G as a whole and it is crucial for our derivation.
Neural network Previously, for deterministic network f F. its output after feeding forward single graph is fG.). However, we mainly deal with the huge constructed graph G in this section, and notation will be overloaded to (G) = S E N matrix whose i-th row J(G.))
We instantiate the message passing network as Graph Isomorphism Network (GIN) (Xu et al. 2018 We choose focus on GIN for two reasons. Firstly, the analysis on GIN currently limited, most of the current bounds for GNNs don't 't apply for GIN [Garg et al. 2020 Liao et al. |02 Tang and Liu 2023]. The other reason is that GIN is used as the message-passing network in our numerical experiments. Notably, our proof can be easily adapted to other pressage-passingg GNNs (e.g. GCN Kipp and Welling 2016)). GIN updates node representations as
h = MLP(!)
(1+ (1+
+ Σ 1!-11) uEN(()
(17)
where (2) denotes the node features generated by 1-th GIN message passing layer. Let e() = 0 for all layers and suppose all MI.s have r layers, the node updates can be written in matrix form as
H (1) = a (...o (...o(AAH')) ((AHU-!) w()). ...)) w
(18)
5

---

where ! (Ro2, x is the weight matrix, and H is the matrix of node features with H x.
a the non-linear activation function. Let F be the function space induced by the I-th message passing layer, meaning
F ((AH H w E ,
,ie [r]]
(19)
where T is constraint set the weight matrix w and H is given by 18 The L-layer GIN function space FG is the composition of F¹ for / [4], i...
Fo F rt-l o............................... F = (G (- (
(20)
Letting 8sk -MD (H! (L) D&),, the reference layer defines the following function space
FD (H - S S D2 R ke {K]).
(21)
Our proposed network (GRDL) is essentially F = FG.
Loss Function Instead of the cross entropy loss 77). we consider a general loss function 1y (::) satisfying 0 S Ly S to quantify the model performance. Importantly, this loss function is not restricted to the training loss because our generalization bound is gejimization-indeeendae instance, the loss function can be the ramp loss that is commonly used for classification tasks [Bartlet] al. 2017 Mohri al., 2018). Given a neural network F, we want upper bound the model population risk of graphs and labels from an unknown distribution &' x y
For
E L,(()= = (G,y)~xx) x (L( v))]
(22)
Given the observed graph dataset g sampled from X' V, the empirical risk is
L.(f) N Σ L(((G))..)
(23)
of which 7 is just special case. Appendix provides more details about the setup and our idea.
3.2 Main Results
For convenience, similar [Bartlett et al. 2017 Ju al. 2023
make the following assumptions.
Assumption 3.1. The following conditions hold for F, == {(G y) + (,(()), : E
(i) The activation function a(-) is I-Lipschitz (e.g. Sigmoid, ReLU).
(ii) The weight matrices satisfy w E ((5) = (w(). |/(
lla - n (1)
| 22.1 S (
(iii) The constructed reference matrix satisfy |D S bp.
(iv) The Gaussian kernel parameter 0 is fixed.
(v) The loss function (-)))= R- + R is y-Lipschitz w.r.| || ||2 and 0 S 1 S.
Theorem 3.2 (Generalization bound of GRDL). Letn min, n. || and d = max, d."
(0)) E. ( 2/3/3 For graphs ([Gs: yi) ) druwn iidd from any probubility distribution over x (I....,K)) K} and references [D D2 mxd with probability at least 1 - 5, every loss function by and network f E F under Assumption 3.7 satisfy
Denote RG == 2 (2d)
(f( s L.(f) 3/V
(2/8) 2N
+ 22 may In 24 Naalnns
N
640K Rep where U1
n U22 Kmd, and U/
24VUNbpR
vm
The bound shows how the properties of the neural network, graphs, reference distributions, etc. influence the gap between training error and testing error. A detailed discussion will be presented in Section Some interesting corollaries Theorem 3.2 e.g., misclassification rate bound, can be found in Appendix F.7 Besides small generalization error (f) - L,, (f). good model should have small empirical risk (f). The empirical risk (f) is typically surrogate loss of misclassification

---

2N x rate of training data and lower misclassification rate implies smaller (f). We now provide a guarantee for the correct classification of training data, namely small (f).
Notably, the node embeddings H; from the k-th class as well as the reference distributions D; are essentially some finite samples from underlying continuous distribution Pt. One potential risk is that, although the continuous distributions Pi, "1.IP...... ..., Px are distinet, we can only observe their finite samples and may fail to distinguish them from each other with MMD. Specifically, suppose node embedding H; is from the le-th class, although O = MMD(P,, k. Px) < MMD((Px; P2)) for any j * k. it is likely that MMD (H,, D&) MMD(H, D,) for some j o k. The following theorem provides the correctness guarantee for the training dataset G:
Theorem 3.3. All graphs in the training set 9 are classified correctly with probability at least 1 - 5 if
min MMD(PP.P,) YFY
> + + 4 4 log
Theorem 3.3
implies that larger reference distribution size m benefits the classification accuracy of training data, resulting in lower (J). Moreover, a larger miniyj MM,(P.,,) also makes correct classification easier according to the theorem, justifying our usage of discriminative loss (8)
3.3 Bound Discussion and Numerical Verification
Let R- maxi,1 (9) b max dn
( and suppose 8 is large enough, we simplify Theorem 3.2 as
L,U S L() 6 ( ((
pbllx (un JoK/n
Kmd
N
+ 7V
I. Dependence graph property One distinctive feature of our bound is its dependence on the spectral norm of graphs adjacency matrix. The large adjacency matrix A is a block-diagonal matrix, so its spectral norm = || max4e[N] ||A,|| By Lemma F.8 incorporating cf is sufficient for any L-step GIN message passing. This result aligns with Ju et ar. 2023], who achieved this conclusion via PAC-Bayesian analysis. Our derivation, based on the Rademacher complexity, provides an alternative perspective supporting this result. Notably, Liao et al. [2021] and Garg et al. 2020) proposed bounds scaling with graphs maximum node degree, which is larger than the spectral norm of the graphs' adjacency matrix (Lemma F.18). Consequently, our bound is tighter.
II. Use moderate-size message passing GIN The bound scales with the size of the message passing GIN, following ( (Lr) Empirical observations reveal R > 1, and we prove that >> 1 (refer to Lemma F.20). Therefore, when the message-passing GNN has sufficient expressive power (resulting in small (f)), a network with a smaller L and r may guarantee a tighter bound on the population risk compared to larger one. Therefore, a promising strategy is to use moderate-size message passing GNN. This is empirically supported by FigureSJor Appendix [D77
III. Use moderate-size references The bound scales with the size of reference distributions as Ó(ym). When m is smaller, the bound tends to be tighter. However, rn is too small, the model's expressive capacity is limited, potentially resulting in a large empirical risk (f), and consequently, large population risk. Therefore, using moderate-size references is promising choice, as supported by our empirical validation results in Appendix D.3 (see Figure
IV. Regularization on references norm barely helps Regularizing the norm of references || ie.. reducing bp, might be considered to enhance the model's generalization. However, is important to note that bD only influences the term iy (in logarithm) in Theorem 3.2 and has a tiny influence on the overall bound. Conversely, such regularization constrains the model's expressive capacity, potentially leading to large (f) and increasing the population risk. This observation is empirically supported by experiments in Appendix D.7
( (see Table I0).
V. GRDL has a tighter bound than GIN with global pooling Appendix A
we provide the generalization error bound, i.e., Theorem A. for GIN with global pooling and compare it with Theorem 3.2 The result shows that our GRDL has stronger generalization ability than GIN, which
is further supported by the numerical results in Table 4
7

---

Table 1: Classification accuracy (%). Bold text indicates the top mean accuracy.
DATASRT
МЕTHOо
AVERAGE
MUTAG
PROTEINS
NCII
IMDB-B
IMDB-M
PTC-MR
BZR
COLLAB
PATCHY-SAN
92.6.4.2
75.1
76.9-2.3
62.9.1.99
45.912.5
60.014.8
85.613.7
73.1-2.7
71.5
GIN
89.4=5.6
76.242.8
82.2=0.8
64.343.1
50.921.7
64.627.0
82.623.5
79.3=1.7
73.6
DROPGIN
90,4=7.0
76.944.3
81.9=2.5
66.3+4.5
51.6+3.2
66.3+8.6
77.8+2.6
80.1=2.8
73.9
DIFFPOOL
89.4=4.6
76.2+114
80.9=0.7
61.123.0
45.821.4
60.025.2
79.823.6
80.8=1.6
71.8
SEP
89.4=6.1
76,4+00.4
78.4=0.6
74.1=0.6
51.5+0.7
68.5+5.2
86.9=0.8
81.3-0.2
75.8
89.9-4.2
75.140.6
79.9-04
73.5+0.8
50.740.8
70.2+6.2
85.6+-088
80.7-0.5
75.7
MINCUTPOOL
90,6=4.6
74.7+0.5
74.3=0.9
72.7+0.8
51.0+0.7
68.3+4.4
87.2+1.0
80.9=0.3
75.0
ASAP
87,4-5.7
73.940.6
71.5-04
72.8+0.5
50.840.8
64.6+6.8
85.3+1.3
78.6-0.5
73.1
WITTOPOPOOL
89.415.4
80.0.1..2
7..9
72.6.1188
52.910.8
64.6.6.8
87.8.2.44
10.1
75.9
OT GNN
91.61..6
76.614.00
82
67.513.55
$2.113.0
68.017.55
85.913.3
80.7-2.9
75.7
WEGL
91.0=3.4
73.7419
75.5=144
66.442.1
50.3+1.0
66.226.9
84.424466
79.6=0.5
73.4
FGW ADJ
8.26-7.2
72.414.7
74.422.1
7..
4..9
8..3
86.911.0
80.6-1.5
71.5
FGW SP
84.4-7.3
74.343.3
72.8-1.5
65.0+4.77
47.8+3.8
55.5+7.00
86.9+1.0
77.8-2.4
70.6
WL
5.44
74.412.6
85.6 1.2
67.544.0
48.4144.
56.04-3.9
81.31.0.6
78.5-1.7
72.4
WWL
86.317.9
73.11114
8..7
7164338
52.613.0
52.616.8
87.610.6
81.4-2.1
73.9
SAT 92.6-4.3
77.7::3.2
82.5=0.8
70.02113
47.313.2
68.324.9
91.7=22.1
80.6-0.6
76.1
GRAPHORMER
89.6=6.2
76.3:2.7
78.6=2.1
70.3+0.9
48.9+2.00
71.425.2
85.3+2.3
80.3=1.3
75.1
GRDL.
92.1-5.9
82.6+11.2
80.4-0.8
74.8+2.0
$2.9+1188
68.34-5.4
92.0+1111
79.8-0.9
77.9
GRDL-W
90,8=4.6
82.1+-0.9
80.9=0.8
72.2+3.1
53.1+0.9
68.5+3.2
90.6+1.5
80.4=1.1
77.3
GRDL-S
90.6-5.7
81.1+1.4
81.2-1.5
72.443.3
52.5+1.1
64.243.2
91.6+1.3
78.6-1.3
76.5
Remark 3.4. Currently, we use K reference distributions for classification (one for each class). One natural approach to enhancing the model's expressive power is increasing the number of references for each class. However, counterintuitively, our empirical observations, supported by Theorem B. suggest that having only one reference per class is optimal. We discuss this further in Appendix B
Related Work
Various sophisticated pooling operations have been designed to preserve the structural information of graphs [Bianchi et al. 2020, Ranjan et al. 2020 Baek et al., 2021 Chen and Gel, 2023] Yu et al..
2024
For instance, DIFFPOOL, designed by Ying et al. [2018], learns differentiable soft cluster assignment for nodes and maps nodes to a set of clusters to output a coarsened graph. Another method
by Lee et al. [2019] utilizes a self-attention mechanism distinguish nodes for retention removal, and both node features and graph topology are considered with the self-attention mechanism.
A recent research direction focuses preserving structural information by leveraging the optimal transport (OT) [Peyré and Cuturi 2020]. OT-GNN, proposed by Chen et al. [202]], embeds graph to vector by computing Wasserstein distances between node embeddings and some "learned point clouds". TFGW, introduced by Vincent-Cuaz et al.] [0022]. embeds a graph to a vector of Fused Gromov- Wasserstein (FGW) distance [Vayer al.] 2018
set of "template graphs". . OT distances have also been combined with dictionary learning to leamn graph vector embedding in an unsupervised
way (GDL) [Liu al. 2022a Vincent-Cuaz al. 2021 Zeng et al. 2023]
Similar to the "learned point clouds" in OT-GNN, "template graphs" TFGW, and dictionaries in GDL, our GRDL preserves information in node embeddings using reference distributions. To the best of the authors' knowledge, we are the first to model a graph's 's node embeddings as a discrete distribution and propose classify it directly without aggregating it into vector, marking novel contribution. Additionally, our work stands out as the first to analyze the generalization bounds for this type of model, adding theoretically grounded dimension to the research. By the way, method is much more efficient than OT-GNN and TFGW. Please see Figure and Table g
Numerical Experiments
5.1 Graph Classification Benchmark
We leverage eight popular graph classification benchmarks [Moriis et al. 2020 com- prising five bioinformatics datasets (MUTAG, PROTEINS, NCII, PTC-MR, BZR) and three social network datasets (IMDB-B, IMDB-M, COLLAB). We also use three large-scale imbalanced datasets (PC-3, MCF-7, and ogbg-molhis (Hu al. 2020
Datasets
A summary of data statistics is in Table 6
8

---

Baselines Our approach is benchmarked against four groups of state-of-the-an base-
Table AUC-ROC scores of large imbalanced data classification. Bold text indicates the best.
lines: 1) GNN models with global or so- phisticated pooling operations, including PATCHY-SAN [Niepert et al. 2016), DIFF-
DATASET
METHOD
PC-3
MCF-7
OGBG-MOLHIV
POOL Ying et 2018), GIN [Xu et al.
GIN DIFFPOOL PATCHY-SAN
84,6:11.4
80.6+1.5
7..811.3
2018). DropGIN Papp et al. 2021], SEP
13.2+1.9
1..
73.7+1.8
Wu et al. 2022 GMT Back et al. 2021], MonCutPool [Bianchi al. 2020], ASAP
80.7.1..1
78.913.1
70.212.1
GRDL
85.111.66
81.411.3
79.8+1.0
Ranjan et al.
2020 and Wot-TopoPool
Chen and Gel
2023 2) Optimal transport based models such WEGL Kolouri et al. 2020 and
OT-GNN [Chen et al. 2021 : 3) Kernel-based approaches including FGW (Titouan et al. [019
operating on adjacency (ADJ) and shortest path (SP) matrices, the WL subtree kernel [Shervashidze et at.
at 10 and the Wasserstein WL. kernel [Togninalli et al. 2019]; 4) Graph transformers including
Graphormer (Ying al. 2021] and SAT [Chen al. 2022a We also show the results of two variations of our GRDL: GRDL using Sinkhorn divergence (GRDL-S) and GRDL using Wasserstein distance (GRDL-W), For large imbalanced datasets, we only benchmark our GRDL against PATCHY- SAN, GIN, and DIFFPOOL because other methods are too costly. Details about the initialization and hyper-parameters setting can be found in Appendix D.3
Experiment Settings Due to the page limitation, please refer to Appendix D.2
Classification Results Table shows the classification results. The AUC-ROC scores of experiments
results on the three large imbalanced datasets are reported in Table 2 Our method has top classification performance over baselines in almost all datasets. Our GRDI,, GRDL-W and GRDL-S have close performance. However, as shown later in Figure 2 our original GRDL has significantly lower time costs and thus is preferable for practical use. Graph transformers also have competitive performance, but they have significantly larger amount parameters and much higher time costs than our model, shown by Table 13 in Appendix D.8.
5.2 Time Cost Comparison
We compare the time cost of our GRDL with two models that leverage optimal transport distances discussed in Section 4 OT-GNN (Chen et al. [021] and TFGW (Vincent-Cuaz al. 2022). Compared with them, our model has significantly lower time costs. We present empirical average training time per epoch in Figure 2
and average prediction time per graph Table in Appendix D44 Experiments were conducted on CPUs (Apple MI) using identical batch sizes, ensuring fair comparison. It's noteworthy that the OT solver employed in TFGW and OT-GNN is currently confined to CPU, influencing the choice of hardware for this evaluation. We analyzed the theoretical time complexity Appendix D.4 (see Table R).
Table 3: Comparison of time cost (second) per epoch with Wit- Wit-TopoPool and MSGNN.
MUTAG
PROTEINS
NCI
IMDB-B
IMDR-M
PTC-MR
BZR
COLLAR
SYN-100
SYN-300
SYN-500
GRDL (OURS)
0.4
3.4
12.6
2.4
3.5
0.8
1.2
16.3
26.6
45.8
88.7
WITTOPOPOOL
0.4
2.
21.4
2.4
2.6
1.0
1.3
39.1
32.9
50.8
97.5
MSGNN 45,2
75.5
135.3
We also compare training time with two latest pooling methods including Wit-TopoPool [Chen and Gel 2023) and MSGNN [Lv al. 2023) on eight real datasets and three synthetic datasets. The three 300(SYN-300) and 500KS per graph, respectively. The edge number is 0.1n² where the number of nodes. The empirical training time per epoch is shown in Table 3 where empty of MSGNN means it takes more than 200 seconds train a single epoch, which is too costly. As can be seen, our method is the most efficient among these three methods.
synthetic datasets have 2000 graphs with 100(S
nodes
5.3 Graph Visualization
We use t-SNE [Van der Maaten and Hinton 2008 to visualize the distributions of graphs' node embeddings given by our GRDL model, which is equivalent to visualizing each graph in 3-D coordinate system. Firstly MMD to calculate distance matrix C I (N+K))(N++K) between

---

MUTAS
PROTEINS
Time Cost Crecond)
Time Cost (record)
25
GROL
GRDL-3
07-0NN
Trow
GRDE
GRCL- W
GROU-5
TrOW
CROL
GROV
or-ONN
IMB-6
IMDB-M
PTC-Mh
Time Corn becomdd)
Time Cosn (ocondd)
D7
1
GNGG-9
TPOW
W
GROUL5
07-G0N
TYGW
GRDL
GRD w
GROX.6
CT -7--00
TROW
BZR
COLLAB
Average
Time Cast (vecond)
Time Cost Soocondd
GRDZ
WW
GR33-3
OF-CWN
Iraw
GROL-5
07-6WN
17OW
GROL
GRDX-W W
GRDL-5
Or-oWN
mPWW
Figure 2: Average training time per epoch. GRDL is 10 times faster than OT-GNN and TFGW.
the node embeddings (H, N and the reference distributions {D The 3-D visualization given by t-SNE using C is presented in Figure 3 The graphs are located around the references. means that the learned references represent realistic graphs' latent node embeddings from the data.
5.4 More Numerical Results
Class
The ablation study, influence 0, generalization comparison with GIN in Appendices D.5 D.6
Class 1
Reference 0 Reference
and A respectively.
1.0
Conclusions
0.0
We proposed GRDL,, novel framework for graph classification without global pooling operations and hence effectively preserve the information of node embeddings. What's 's more, we theoretically analyzed the generalization ability of GRDL, which provided valuable insights into how the generalization ability scales with the properties of the graph data and net- moderate-
-1.0
1.5
2
-4
0
2
work structure. Extensive experiments scale and large-scale benchmark datasets verify the effectiveness and efficiency of GRDL in comparison to baselines. However, on some benchmark datasets (c.g. NCII), model does not outperform the base- line, which may be a limitation of our work and re- quires further investigation in the future.
-4
Figure 3: T-SNE visualization of MUTAG embeddings and reference distributions given by GRDL. Each dot denotes graph and each square denotes reference distribution.
10

---

Acknowledgments
This work was supported by the National Natural Science Foundation of China under Grant No.62376236, the Guangdong Provincial Key Laboratory of Mathematical Foundations for Artificial Intelligence (2023B1212010001), Shenzhen Science and Technology Program ZDSYS222336260910000 100266609900006 1302006, Shenzhen Stability Science Program 2023, and Hetao Shenzhen- Hong Kong Science and Technology Innovation Cooperation Zone Project W...HZQSWS-KKCYY. 2024016). The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
The authors appreciate the reviewers and area chair of the paper.
References
Jinheon Baek, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling. arXiv preprint arXiv:2102.1 1533, 2021.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally normaalized margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Yoshua Bengio and Yves Grandvalet. No unbiased estimator of the variance of k-fold cross-validation. Advances in Neural Information Processing Systems, 16, 2003.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International conference machine learning, pages 874-883. PMLR, 2020.
David Buterez, Jon Paul Janet, Steven J Kiddle, Dino Oglic, and Pietro Liò. Graph neural networks with adaptive readouts. Advances in Neural Information Processing Systems, 19799766-19758,
2022.
Benson Chen, Gary Bécigneul, Octavian-Bugen Ganea, Regina Barzilay, and Tommi Jaakkola. Optimal transport graph neural networks, 2021.
Dexiong Chen, Leslie O' O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In Proceedings of the 39th International Conference on Machine Learn- ing (ICMI), Proceedings of Machine Learning Research, 2022a.
Samantha Chen, Sunhyuk Lim, Facundo Mémoli, Zhengchao Wan, and Yusu Wang. Weisfeiler- lehman meets gromoy-wasserstein In International Conference Machine Learning, pages 3371-3416. PMLR, 2022b.
Yuzhou Chen and Yulia R. Gel. Topological pooling on graphs. In Proceedings of the Thirty- Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifih Conference on Innovative Applications of Artificial Intelligence and Thirleenth Symposium on Educational Advances in 2023.
Artificial Intelligence, AAAA223/AAA/23//AAA..
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. International Conference on Machine Learning, pages 3419-3430. PMLR, 2020.
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLI/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pages 129-143. Springer, 2003.

---

Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR, 2017.
Arthur Grettonn, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012a.
Arthur Gretton, Dino Sejdinovic, Heiko Strathmann, Sivaraman Balakrishnan, Massimiliano Pontil, Kenji Fukumizu, and Bharath K Sriperumbudur. Optimal kernel choice for large-scale two-sample tests. Advances in neural information processing systems, 25, 2012b.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs Advances in neural information processing systems, 30, 2017.
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. arXiv preprint arXiv:2005.006877 2020.
Haotian Ju, Dongyue Li, Aneesh Sharma, and Hongyang Zhang. Generalization in graph neural networks: Improved pac- bayesian bounds on graph diffusion. In Proceedings of The 26th Interna- tional Conference on Artificial Intelligence and Statistics, volume 206, pages 1344-334, PMLR, 27 Apr 2023.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek. Anna Potapenko, al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-588) 2021.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1412.6991 2014.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 10900916, 2016.
Soheil Kolouri, Navid Naderializadeh, Gustavo K Rohde, and Heiko Hoffmann. Wasserstein embed- ding for graph learning. arXiv preprint mmXiv:2006.09430 2020.
Sofia Ira Ktena, Sarah Parisot, Enzo Ferrante, Martin Rajchl, Matthew Lee, Ben Glocker, and Daniel Rueckert. Distance metric learning using graph convolutional networks: Application to functional brain networks. In Medical Image Computing and Computer Assisted Intervention- MICCAI 2017: 20th International Conference, Quebec City, QC, Canada, September 11-13, 2017, Proceedings, Part 20, pages 469-477. Springer, 2017.
Dongha Lee, Su Kim, Seonghyeon Lee, Chanyoung Park, and Hwanjo Yu. Learnable structural semantic readout for graph classification. In 2021 IEEE International Conference Data Mining (ICDM), pages 1180-1185. IEEE, 2021.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International conferee on machine learning, pages 3734-3743. PMLR, 2019.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph scquence neural networks. arXiv preprint arXiv:1511.05493 2015.
Renjie Liao, Raquel Urtasun, and Richard Zemel. A PAC-Bayesian approach generalization bounds for graph neural networks. In International Conference on Learning Representations, 2021.
Weijie Liu, Jiahao Xie, Chao Zhang, Makoto Yamada, Nenggan Zheng, and Hui Qian. Robust graph dictionary learning. In The Eleventh International Conference on Learning Representations, 2022a.
Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and S Yu Philip. Graph self- supervised learning: A survey. IEFE Transactions on Knowledge and Data Engineering, 35):): 5879-5900, 2022b.
12

---

Yiqin Lv, Zhiliang Tian, Zheng Xie, and Yiping Song. Multi-scale graph pooling approach with adaptive key subgraph for graph representations. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, CIKM '23. Association for Computing Machinery, 2023.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL
WWW graphlearning... 10
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference on machine learning, pages 2014-2023, PMLR, 2016.
Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the expressiveness graph neural networks. Advances in Neural Information Processing Systems, 34:21997-220099 2021.
Gabriel Peyré and Marco Cuturi. Computational optimal transport, 2020.
Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. Asap: Adaptive structure aware pooling for learning hierarchical graph representations. In Proceedings of the AAAI conference artificial intelligence, volume 34, pages 5470-5477, 2020.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lemman graph kernels. Journal of Machine Learning Research, 12(9). 2011.
Fan-Yun Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. arXiv preprint 100i:09908.01000 2019.
Yan Sun and Jicong Fan. MMD graph kernel: Effectivv metric learning for graphs via maximum mean discrepancy. In The Tweifth International Conference on Learning Representations, 2024. URL https:://ppenreviee www.:eeeoooomiiiddddaaaaaaa..aa
Ziheng Sun, Chris Ding, and Jicong Fan. Lovász principle for unsupervised graph representation learning. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Ziheng Sun, Xudong Wang, Chris Ding, and Jicong Fan. Learning graph representation via graph entropy maximization. In Forty-first International Conference on Machine Learning, 2024.
Huayi
Tang and Yong Liu. Towards understanding generalization of graph neural networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning. volume 202 of Proceedings of Machine Learning Research, pages 33674-33719, PMLR, 23-29 Jul 2023.
Vayer Titouan, Nicolas Courty, Romain Tavenard, Chapel Lactitia, and Rémi Flamary. Optimal transport for structured data with application on graphs. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2275-62844 PMLR, 09-15 Jun 2019.
Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-LLópez, Bastian Rieck, and Karsten Borgwardt. Wasserstein weisfeiler-lehman graph kernels. Advances in neural information processing systems, 32, 2019.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
13

---

Titouan Vayer, Laetita Chapel, Rémi Flamary, Romain Tavenard, and Nicolas Courty. Fused gromov- wasserstein distance for structured objects: theoretical foundations and mathematical properties. 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arxiv: 2017.
Cédric Vincent-Cuaz, Titouan Vayer, Rémi Flamary, Marco Corneli, and Nicolas Courty. Online graph dictionary learning. In International conference machine learning, pages 10564-10574. PMLR, 2021.
Cédric Vincent-Cuaz, Rémi Flamary, Marco Corneli, Titouan Vayer, and Nicolas Courty. Template based graph neural network with optimal transport distances. Advances Neural Information Processing Systems, 35:1 1800-11814, 2022.
Zhouxia Wang. Tianshui Chen, Jimmy Ren, Weihao Yu, Hui Cheng, and Liang Lin. Deep reasoning with knowledge graph for social relationship understanding. In Proceedings of the Twenty-Seventh International Joint Conference Joint Conferences on Artificial Intelligence Organization, 7 2018. doi: 10.24963//jcai.201.35 URL https://doi.orgg
Artificial Intelligence, IJCAI-18, pages 1021-1028, International
24963/293211 ijcai. 2018/142
Junran Wu, Xueyuan Chen, Ke Xu, and Shangzhe Li. Structural entropy guided graph hierarchical pooling. In International conference on machine learning, pages 24017-24030. PMLR, 2022.
Teng Xiao, Zhengyu Chen, Zhimeng Guo, Zeyang Zhuang, and Suhang Wang. Decoupled self- supervised learning for graphs. Advances in Neural Information Processing Systems, 35:620-634, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint vrXiv:/810.000 2018.
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? Advances in neural information processing systems, 34:28877 28888, 2021.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hier- archical graph representation learning with differentiable pooling, Advances in neural information processing systems, 31, 2018.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In International Conference on Machine Learning, pages 12121-12132 PMLR, 2021.
Jiajun Yu, Zhihao Wu, Jinyu Cai, Adele Lu Jia, and Jicong Fan. Kernel readout for graph neural networks. In Kate Larson, editor, Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24, pages 2505-2514, International Joint Conferences on Artificial Intelligence Organization, 2024. doi: 10.24963/iccai220244777. URL htLLhtt//:///o oro//i0org/1000 Main Track.
24963/ijcato http://jaaaa.222///22// 2074/277
Zhichen Zeng, Ruike Zhu, Yinglong Xia, Hanqing Zeng, and Hanghang Tong. Generative graph dictionary learning. In International Conference on Machine Learning, pages 40749 40769. PMLR, 2023.
14

---

Appendix
Table of Contents
A Generalization Comparison to GIN with Global Pooling
16
Theory and Experiments of GRDL with Multiple Reference Distributions
16
Detailed Training Algorithm of GRDL,
D
More Experiments
18
Dataset Statistics
18
D.2
Experiment Settings
19
D.3
Hlpee--parameter Settings and Parameter Initializations
19
D.4
Time Complexity
20
D.5
Ablation Study.
21
Influence of
21
D.7
Experiments The Generalization Error Bound
22
D.8
Parameter Number and Time Cost Comparison with Graph Transtormers
22
E
Proof Setups
23
Proof for Theorems, Corollaries, and Lemmas
24
F.
Correctness Analysis
24
F2
Lipschitz properties
25
F3
Covering number
26
F4
Proof of Lemma E.2
31
E5
Proof of Lemma P.8
32
F6
Proof of Theorem
33
F7
Corollary of Theorem 3.2
34
F8
Adjacency matrix spectral norm
35
Generalization of MMD used Section 1.10
F10
Proof Lemma F2
37
F1
Proof of Theorem
37
15

---

A Generalization Comparison to GIN with Global Pooling
To see the advantage of our GRDL, we compare with GIN. The only difference between GRDL and GIN is that GRDL uses reference layer while GIN uses readout. We add an r' r'-layer MLP the classifier after message- passagg-passing modules in the GIN. The following theorem gives an upper bound of GIN's generalization error:
Theorem A.1 (Generalization bound of GIN). Let min, na
|| o. and d = max,,1 d!"
Denote Rg := e22 [ In(2d)) & (IE
Ei (
2/3 3 For graphs
{[G,; ,.) _| drawn ii.d from any probability distribution over X {I...., K}. with probabiliiy at least 1 8, GIN network with mean readout satisfies
N
L,(f) L.( + 33V
In (2/8)
8y424
R4 (2(11)) Ro R In
2N
where R'G = 2 X 1n
III (30
C E
and C2 = E E (1 )
This bound is derived using the same techniques our GRDL bound Theorem 3.2 these two bounds, we only need to compare the following two terms:
To compare
QGRDI = 24 + 02 In N + 24h Nu2 In
(Theorem 3.2
QGIN == 24p II K2 (2)1))
RG + InN
(Theorem A.1
where 11
640Kg² Rc. U2 Kmd, and 03 24v0NbDH, Our observations are follows.
Vm
K The in iı can be absorbed into ( and {D&) Since n >>>>>> K, we conclude that 648K is smaller than in practice. Therefore, V1 S p²² RG..
n
= Kmdd and V/y = 24/0Nbbp are much smaller than R'g as well as Ra. i.e., < R' and
vm
0y < R'G- The reason is that R' and RG involve the multiplication of terms related to c, X and
(I+1) is typically larger than 3 for r' > based on empirical obser- vations. We also observe that I K (T++1) may be smaller than for r' 1, but the linear classifier's expressive capacity is very limited and thus has large training error. Therefore, focus on the case where >
In Theorem A.I
I
ii= Ki
Now we can conclude that QGRDL. < QGIN. Therefore, the generalization error upper bound of GIN larger than of GRDL, meaning our GRDL generalizes better on unseen data than GIN the worst case. It is worth noting that these results apply to other GNNs such as GCN.
We now use numerical experiments on real datasets to support our claim. The training and testing accuracy of GRDL and GIN are shown in Table 4 We see that the training accuracy of our GRDL is close that of GIN, but the testing accuracy our GRDL is much higher than that of GIN. This means that GRDI. and GIN have similar training errors but the former has stronger generalization ability.
B Theory and Experiments of GRDL with Multiple Reference Distributions
Currently, we use K reference distributions for classification (one for each class). One natural approach to enhance the model's expressive power is to increase the number of reference distributions for each class. However, counterintuitively, our empirical observations suggest that having only one reference per class is optimal. In this section, we will explore and provide insights into this phenomenon.
16

---

Table Comparison of the trainining and testing accuracy between GRDL and GIN.
GRDI.
GIN
Dataset
Training Accuracy
Testing Accuracy
Training Accuracy
Testing Accuracy
MUTAG
93.3
92.1
92.7
89.4
PROTEINS
83.1
82.6
80.5
76.2
NCII
82.8
80.4
83.3
82.2
IMDB-B
76.3
74,8
75.9
64.3
IMDB-M
53.1
52.9
51.7
50.9
PTC-MR
71.3
68.3
66.1
64.6
BZR
93.1
92.0
93.9
82.6
COLLAB
82.1
79.9
82.3
79.3
Average
79.4
77.9
78.3
73.6
PE[P)
Suppose we have P reference distributions for each class, i.c. D -
[D (p)
where D(
is the
AE[K]]
p-th reference the k-th class. The prediction in Equation (5) changed to
Σ ((H.. p=1
yprrddi arg max ke KE[K]
Siks
(24)
The training algorithm is nearly the same as our GRDL with one reference per class (Algorithm) except for the mini-batch training loss because of the multiple references, i.c.,
I
k
L= B
Yik log Dik + + Σ Σ
(D (P) D(
(25)
=
kzkp-p'=
We compare the model with P = 2 (GRDL-2) and P = 3 (GRDL-3) with our GRDL (P = 1).
Table shoows the classification accuracy of the models on the benchmark datasets.
Table 5: Classification accuracy of models with multiple reference distributions. Bold text indicates the best mean accuracy.
METHOD
DATASET
GRDL
GRDL-2
GRDL-3
MUTAG
92.11.5.9
91.5114.8
90.4113.1
PROTEINS
82.6=1.2
81.4#2.1
81.3#2.9
NCII
80.4=10.8
79.3+1.0
80.0
IMDB-B
74.8+2.0
73.6#2.2
7..0+1.4
IMDB-M
52.9-11.8
51.1+1.2
50.3+2.1
PTC-MR
68.3+-5.4
66.3+6.4
65.4+:5.5
BZR
92.0+11.1
87.1+2.7
88.243.1
COLLAB
79.8:10.9
77.911.2
77.
To explain why GRDL performs better than the models with more references, we first introduce the following theorem
i=1" Theorem B.1. Let n be the minimum number of nodes for graphs {G, [G 0 be the hyper-parameter
N
in the Gaussian kernel (Equation 15).. c || For graphs { y: drawn i.i.d from
(p) PE[r)
any probability distribution over X {1. f1. K} and references (D()) probability least -8. every loss function L,, and network
D( mmx with
KEIKi
under Assumption satisfy
In (2/0)
87 24 + In N /
Ln < 1,10++ + 37V
2N
N

---

where
140P*KHaH Kmd, ng
20NDON
i
2/3
3
Rg = =
Vm
This is essentially a more general version of Theorem 3.2 theorem.
The following is a brief proof of this
Proof. The only difference between multiple reference distributions and a single reference distribution comes from the calculation of Sij.
1818
Σ p=1
MMD (H.. MMD (H,, D.
MMD2 (H.. MMD? (H.
- 4V0P nn 11/2 H. H +m m- 1-2mmm11 |/2 - -Di1l2)
Then with minor modifications of proof of Lemma F.14 the covering number F is given by
640 RR
24bDPVON
In (c)F,))
Kmdln
nE²
/IEE
Then the theorem can be proved using the same process as the proof of Theorem 3.2
Let max,, Ki (9) 1 max, and suppose is sufficiently large. The bound Theorem B.1 can be simplified
L,(f) & F,(++ (0 (Vo++>NNu)) N
S sin)+ (nbl|X]2cc (T
& POK/nn
Kmd
+ + N
N
(26)
Empirically, we observe that the training loss L., and the misclassification rate are nearly the same for small and large P as shown Figure Therefore, smaller P implies tighter generalization bound in 26 This means that one reference distribution for each class (P = 1) may be the optimal choice.
Another explanation is that, the nodes embeddings of graphs in the same class be regarded as samples drawn from a single discrete distribution, thus learning single reference distribution is sufficient to provide high classification accuracy. On the other hand, the union of multiple distributions can be regarded as a single distribution.
C Detailed Training Algorithm of GRDL
In practice, since the scale of is different from the scale of other parameters in the model, a different learning rate is used update Suppose Adam [Kingma and Ba] [014] used to optimize the parameters, then the training of GRDL model is presented in Algorithm
D More Experiments
D.1 Dataset Statisties
The statistics of the datasets are reported in Table PC-3, MCF-7, and ogbg-molhiv are three large graph datascts.
18

---

MUTAG
IMDB-BINARY
P= 1
P 1
P 2
P
P 3
0.50
P=3
Mis-dl Mis-daesfication Rate
0.5
Mis doe-ddssfiaatin
0.4
0.40
0.30
0.1
0.20
80
Epoch
Epoch
Figure 4: Training data misclassification rate on MUTAG (left) and IMDB-BINARY (right) with different numbers of references for each class (P). The effect of P on the training misclassification rates not obvious.
Algorithm 1 GRDL Training
1: Input: Graphs [G On the learning rate of and 0g the learning rate of 0, batch size B.
2: Initialize w, D, and 6,
repeat
4: Sample minibatch ii B, [ B
5: 8; + (w.D,o(G.), i
6: ÿ; f- softmax(s:), iE
L = 1 L
log Dik + X Σ (D,
7:
B
iEB k=1
8:
(gw, [ww GD. 90)
(w, D) + (w, D) w. DC
9:
01 Adam ((w, D), (9w: gD))
1 0 / a2 Adam go)
11: until convergence conditions are met
Output: fw,D.0
D.2 Experiment Settings
In the GNN literature, researchers typically perform 10-fold cross-validation and report the best average accuracy along with standard deviation [Xu et al. 2018 Papp et al. 2021 Maron al.) 2019]. But here, we adopt a different strategy used in |inneent Cuaz et al. 2022] We quantify the generalization capacities of models by performing 10-fold cross-validation with holdout test set which is never seen during training. The validation accuracy tracked every epochs, and the model that maximizes the validation accuracy retained for testing. This setting more realistic than simple 10-fold CV and can better quantify models' generalization performances [Bengio and Grandvalet 20003. However, the test sets for MUTAG and PTC-MR contain only 18 and 34 graphs respectively, making them too small for assessing generalization ability. Therefore, for MUTAG 10-fold cross-validation following [Xu et al.) (2018]. Notice that kernel-based methods do not require stopping criterion dependent on a validation set, so we report results of 10-fold nested coss-validation repeated 10 times following [Titouan al. 2019).
and PTC-MR,
D.3 prprmmerrreeter Settings and Parameter Initializations
Model For all the baselines, we adopt the hyper-parameters suggested in the original papers. For methods, we use GIN [Xu et al. 2018 layers as the embedding network. Every GIN layer is an
19

---

Table 6: Dataset Statistics
datasets
features
#graphs
#classes
min #nodes
median #nodes
max #nodes
MUTAG
{0, ..... 6}
188
2
10
17
28
PROTEINS
29
1113
2
13
63
NCII
0. 36
4110
2
3
27
111
PTC-MR
{0, 17}
344
2
2
13
64
BZR
R3
405
2
13
35
57
IMDB-B
None
1000
2
17
136
IMDB-M
None
1500
3
7
10
89
COLLAB
None
5000
3
32
52
492
PC-3
....
28
27509
2
3
24
113
MCF-7
28)
27770
2
24
113
oghg-molhiv
2
41127
2
23
222
MLP layers (r - 2) with batch normalization, whose number of units is validated in {32, 64) for all datasets. The parameter validated in {0.1, 1]. We validate the number of GIN layers (L) in {3, 4, 5, 6, 7, 8. For each dataset, the references' dimension (m) is validated in the minimum number of nodes (G1), average the minimum and median number of nodes (G2), median number of nodes (G3), average of the median and maximum number of nodes (G4), and the maximum number of nodes (G5) of graphs in the dataset. The reference for each class is initialized there is m-node graph in the dataset that belongs to the corresponding class, then the reference is initialized as node embeddings the graph. 2) no graph the class has m nodes, then we perform K-Means clustering on the graphs of the class, and the m clustering center is chosen to be the initial reference.
follows: 1)
Optimization The models are trained with Adam optimizer with an initial learning rate 10-3 for network weights and references. The learning rate 0 decays exponentially with a factor 0.95. Since the Gaussian kernel parameter 0 is small in practice (around 10-3 in our model), it is hard to choose a learning rate for it. Therefore, we consider ग = instead. я initialized to 500 and its initial learning rate 0g is validated in {0.1, (0.11), 1}. The batch size for all datasets is fixed to 32.
Detailed papam-parmmeters setting can be found Table
Table 7: parammte settings for experiment results in Table
DATASETS
#LAYERS
REFERENCE
HIDDEN CHANNELS
C22
MUTAG
5
G2
32
1.0
1.0
PROTEINS
G3
32
1.0
NCI1
G3
32
1.0
0.1
IMDB-B
5
G3
32
1.0
1.0
IMDB-M
5
G3
32
0.1
0.1
PTC-MR
5
G3
32
1.0
0.1
BZR
G3
32
1.0
COLLAB
G3
32
1.0
0.1
PC-3
6
G4
64
1.0
0.1
MCF-7
6
G4
64
1.0
0.1
OGBG-MOLHIV
G4
64
1.0
0.1
D.4 Time Complexity
To provide a comprehensive understanding, we first show the forward propagation time complexity of the three models for single graph (A, X), A Raxn X E Raxd Given that all three models employ Graph Neural Network (GNN) for obtaining node embeddings. we denote the
complexity and the number parameters of the GNN embedding part as C₁ and Ni, respectively. Additionally, both OT-GNN and TFGW are augmented with MLP for classification, introducing
20

---

an extra complexity C2 and additional parameters N2. In the case of our GRDL, the number of references aligns with the number of classes K.
Let's assume the number of references for OT-GNN 11, and for TFGW, is 22. Notably, TEGW and OT-GNN usually choose K1 2K and K₂ 2K. Additionally, assuming that all references D; E IR mxd Since the GW distance is iteratively computed in Vincent- -uaz et al. 22022), we denote the number of iterations for convergence T. The time complexity and the number of parameters are outlined in Table
Table 8: Time complexity and number of parameters for GRDL, OT-GNN and TFGW.
MODEL
COMPLEXITY
PARAMETERS
GRDL.
C1 + O + mn + m²))
N1 + Kmd
OT-GNN
C1+ (K+ n) log (m n)) C2
Ni Kymd + N2
TFGW
C1 01+0 + + +0²
Ni K2md + N2
Notice that Wasserstein distance can approximated by sinkhorn iterations with complexity O((m n)²) per iteration [Cuturi, 2013). But in practice, the exact calculation with O((m+n)) log (m + n)) complexity empirically gives better performance in terms of both precision and speed, so it is implemented in the original paper of OT-GNN [Chen et al. 2021]. Theoretically, our GRDL has lower prediction time complexity and a reduced parameter count. Table shows the empirical prediction time per graph
Table 9: Average prediction time per graph (10-3 Table 10: Comparison of GRDL with/without reg- seconds).
ularization on references norm.
DATASET
METHOD
DATASET
METHOD
GRDL
OT-GNN
TEGW
GRDL
GRDL-R
MUTAG
1.2
25.6
53.5
MUTAG
92.115.9
91.615.5
PROTEINS
1.3
29.4
48.3
PROTEINS
82.611.2
80.311.2
NCII
1.2
25.1
83.5
NCI1
80.410.8
78.610.9
IMDB-B
1.2
16.3
66.0
IMDB-B
74.8+2.0
73.6+1.6
IMDB-M
16.3
66.5
IMDB-M
52.9+1.8
48.3+1.6
PTC-MR
1.8
15.0
58.4
PTC-MR
68.3+-5.4
68.146.4
BZR
2.1
23.8
76.2
BZR
92.0.11.1
90.712.4
AVERAGE
1.4
21.6
64.6
COLLAB
79.8.0.99
77.910.7
D.5
Ablation Study
We consider two variants of GRDL. The first one is GRDL with a fixed 0 = 10-2 in the Gaussian kernel. The other GRDL with on the references. We also include another baseline where we first use sum pooling over node embeddings and get the graph embedding vectors. The graph vectors are then used to compare with references (vectors in this case) with discrimination loss. The classification results of benchmark datasets are given Table []] The original model with learnable and discriminativeness constraints consistently outperforms the other two.
in ( which does not have the discriminativeness constraint
D.6 Influence of 0
In our model, we initialized the Gaussian kernel hyper-parametee 0 to 2 10-3 and it was adaptively learned during training. Actually, all values between x 10-4 and 10-1 give similar performance, as it is adaptively adjusted in the training. The initialization of the neural network parameters and the reference distributions cannot guarantee that x close to x'. If too large, the Gaussian kernel k(x, x') = exp (-0l x'13)) will be too sharp, which will lead to almost zero values. Hence, MMD will fail to effectively quantify the distance between the embeddings and reference distributions, shown in Table [2
21

---

Consider a model regularizing the norm of Table 11: Classification accuracy of ablation methods. Bold text indicates the best mean accuracy.
METHOD
DATASET
GRDL
GRDL FIXED 0
GRDL À
GRDL+SUM
MUTAG
92.1=5.9
90,4#6.4
89.9=4,9
89.9=6.0
PROTEINS
8.2
81.810.9
81.8
78.4110.6
NCII
80.4.108
80.242.2
80.0
77.24:1.7
IMDB-B
7.08
7..8
73.1
71.6115.2
IMDB-M
12.9=1188
52.1#1.2
51.3=1.
49.8=5.4
PTC-MR
68.3=5.4
66.615.7
66.6#5.9
62.5#6.3
BZR
92.0=1.11
90.1+1.5
89.5=2.3
85.3
COLLAB
0.9
79.5+00.7
79.0+1.0
77.140.9
Table 12: Classification accuracy MUTAG dataset with different A.
x 10-4
x 10-3
1 x 10-2
1 x 10
1 x 10
1 x 10
x 10
Accuracy
0.9096
0.9149
0.9113
0.9113
0.8254
0.6822
0.5737
0.3345
D.7 Experiments on The Generalization Error Bound
Use moderate-size message passing network We choose the training loss to be the cross-entropy loss (A = 0) and l, chosen the same as the training loss. We validate the number of GIN layers L E [3, 5, 6) and the number of MLP layers for each GIN layer f2,3, 4]. L,, is set to be the be the training loss. From Figure
validation loss and i.,, is
we have the following observations
For any fixed r, if L is increasing, the empirical risk L., increases, and the population risk Ly either increases (r = 3 and r = 4) or first decreases then increases (r (r=37 2).
For any fixed L, if r increasing, the population risk Ly first decreases then increases in most of the cases, and the empirical risk L,, decreases in most of the cases.
These observations align with our bound and support our claim that moderate-size GNN should be used.
Use moderate-size references We validate the reference size (m) in experiments real datasets, as detailed in Appendix D.3 The results in [pp]endi(D.3]sshov that moderate-size references (G2, G3, G4) provide better generalization results. Here, we present the classification results for MUTAG and PROTEINS by choosing m from more fine- fineggrained sets. For MUTAG, m is chosen chosen from 1, 1,3, 5...., 61. The figures Figure show that our model performs the best when moderate m is used.
from ...,..., 30. For PROTEINS,
Regularization on references norm barely helps references |D|[| (GRDL-R)
min LeE + Ap + De||D||2
(27)
The hyper-pane paremeetrettrr À is set 0.01. Table 10 compares the empirical results of GRDL model and the results of GRDL-R model. From the table, we can see that GRDL performs better than GRDL-R all datasets, which verifies discussion in Section 3.3 Therefore, the regularization of references barely helps in our model.
D.8 Parameter Number and Time Cost Comparison with Graph Transformers
Table 13 compares the number of parameters and training time per epoch of our GRDL with two graph transformers method. We can see that our GRDI. has significantly fewer parameters and training time, making it preferable. All experiments are conducted on one RTX3080.
22

---

L-3
1-2.
0.50
tran
mahn
tah
tran
0.00
0.90
0985
1445
0.80
3 6.5
0995
6.00
0.02
1.65
0662
0066
0/62
6663
1865
2.00
40
48
49
spach
opoch
opoch
Irain
train
trai
tran
1.2
valid
vaid
1.49
0:7T5
0.00
0.07
0.00
0.02
0.65
40 50
73 50 130
20
30
40 30
70 50 100
20
35
40 30
70
100
20 32
48 55
1pach
8p00h
400ch
000ch
4,
L-3
4, 4.4
1-4.L-5
1-4.L-6
trahn valid
taann valid
tran
tran vald
0.02
1.2
vald
1.2
2.02
1.64
2.65
0 00 100
0 40
40
03
48
Figure 5: The blue and orange lines denote the training error L,, and validation error Ly, respectively, of GRDL with r (2,3, 4], L E (3,4,5, 6,
Table 13: Number of parameters and time cost per training epoch (seconds) of GRDL and Graph transformers.
Method
Dataset
GRDL
SAT
Graphormer
Parameters
Time
# Parameters
Time
Parameters
Time
MUTAG PROTEINS
11k
0.11
663k
0.64
647k
0.59
12k
0.52
666k
3.51
650k
3.31
NCII
13k
1.77
667k
12.08
651k
11.37
IMDB-I B
15k
0.42
680k
3.69
664k
3.42
IMDB-M
13k
0.69
674k
4.32
658k
4.06
PTC-MR
12k
0.17
663k
1.17
647k
0.97
BZR
11k
0.21
665k
1.26
649k
1.09
COLLAB
31k
3.71
725k
17.45
709k
16.89
Average
15k
0.95
675k
5.51
659k
5.21
E Proof Setups
Vector and matrix norms The f2-norm || ||2 is always computed entry-wise; thus, for a matrix, corresponds to the Frobenius norm. The metric p of function spaces is defined the formrr of the difference between the outputs of functions given some input X, i.e.,
p(fi f2) = (X) fx(
(28)
Finally, let ||- llo be the spectral norm and lp.. be the (p, q) matrix norm defined by || Iln- [I[] -hlpp .l............................ ... | 11 for A pdxm
23

---

0.13
0.190
0.12
NW
Mii-daasfiisslonn Rale
W
W
Mis-dassfication Rate
0.11
0.185
L
0.10
0.180
0.175
0.08
3
7
11
13
15
17
19
21
23
25 27
29
13
17
21
25
29
33
37
41
45 48 53 81
(a) MUTAG
(b) MUTAG
Figure 6: Misclassification rate of GRDL MUTAG (Figure 6al and PROTEINS (Figure 6b using different reference sizes m. The figures show that our model performs the best when a moderate m is used.
Rademacher complexity Rademacher complexity is a standard complexity measure of hypothesis function space. Given dataset and hypothesis function space F, the Rademacher complexity is defined as
RF(
sup fEF N fG.()))
(29)
where oi,..., ON are independent Rademacher variables.
Then the bound can be derived with the help of the following lemma: Lemma E.1. Given hypothesis function space IF that maps graph G X to RR and any 7y O,
define Fx = {(G, y) + L,f(G)).)) F}. Then, with probability at least - over a sample of size N. every
satisfies L,(f) s L,( (Rg(F,) + +3v (2/8)
This Lemma is standard tool in Rademacher complexity [Mohri et al. 2018 The only problem left calculate the Rademacher complexity Rgg (F.).
Covering number complexity bounds Direct calculation the Rademacher complexity is often hard and the covering number is typically used to upper bound it. V is 6-cover of U with respect to some metric @ if for all v E U, there exists E V such that e(v, v') S e, meaning
sup min e(v, o') S.. e'EV
(30)
The covering number N (e, U, e) defined as the least cardinality of the subset V. With covering number, the Rademacher complexity is upper bounded by the following Dudley entropy integral: Lemma E.2 (Lemma A.5 of Bartlett et al. [2017] reformulated). Let Fr, be real-valued function
class taking values in [0, 7), and assume that 0 E FT.- Then
4ar VN
12
R₂(F,) S inf
(en
a>0
N
Now the only thing left is bound N Pp.
F Proof for Theorems, Corollaries, and Lemmas
F11 Correctness Analysis
We first provide the formal definition of correct classification:

---

Definition F.1 (Correctness of Classification). For graph G; with node embedding H, belonging to the k-tth class, is correctly classified if MM, D minj MMD(H,,))) Dj).
Lemma F.2 (Correctness of Classification). The classification of graph G. belonging to the k-th class (with latent node embedding H;) is correct with probability at least 6 if
1 V
min MMD PP) > jzk
4 4
log 8
Lemma F.2 suggests that larger reference distributions size (m) and graphs with more nodes (n) [ [ 4/41ogg 2). making correct classification easier. Proof of this
induce smaller (Jm +
vn
theorem is provided in Appendix F.10
F.2 Lipschitz properties
This section proves useful lemmas related to functions' lipschitz property.
Lemma F3. For any Z, Z' E B and W Rdxm [| - Z') 2 S ||W || Z Z'I12
Proof. First consider matrices X, Y d where X, Y are positive semi-defniite Y is unitarily diagonalizable, means QAQ where A diag(A1 ......... Aa) is the diagonal matrix of eigenvalus of
Y. Then we have
Tr(XY) Tr(XQQQ - Tr(AQ-1XXX
-XQQ, Let P Q - XQ, and Ao max; do we have
Tr = Tr(AP) = Σ NEPRE S
Σ
AoPrs Tr(P) = ATTT(Q- = Tr(X)
k
Take X = (Z-27 - - (Z - Z') and Y = WWT easy to see that
(Z- Tr (z- z T (z - (a-z')wTT) S AmmarWWW (WW Tr (( 114--11 ZZ 2')) = | 11-1I/Z-'
Lemma F.4. of Rdd RRd k-Lisschitz along ever coordinate, then it k-Lipschitz according to ||- for any p 2 1.
Proof. For any z E Rd.
1/P
- -1)))-0(2)111---
Σ [o(2) - (2p))/1
1/P
< Σ ke 24 2/Pp
<|| z'11p
Lemma F.5 (Lemma A.3 of Bartlett et 2017)) ) For every and every p 2 1, M(: 2-L.ipchhiz W.t.
-1p-
Proof. Let v. v. be given. Without loss of generality, suppose M(v.j) 2 M(v,.j). Choose coordinate 7 j so that M(v', = 1/$ vf. Then
M(r.j) - M(u. = (v, max vz) (0/ v/) = Uj v/j + of + (ain--r)
|fj
< (wg - v/)) (0/ vi) S 2| v' 01 S 2| v' 1|p
25

---

Lemma F.6. For every p > 1, rr(-M((,B) is L-piscchitz w.rr || ll.-
Proof. Recall that,
0
t< -,,
= re(t)=
1 +
t/c
r E [- t> 0,
(31)
1
Then the proof is trivial be Lemma R55
Lemma E.7. Cross entropy loss l(xyy) = -E yk log
(xp Σ exp (x,) is 22-iiccchitz w.r. ||
112.
Proof. Since I is differentiable, sufficient to find μ such that |ill2 S μ.. Without loss of
(xp( generality, suppose y: 1, then y( log Σ* (x,)
Let Σx exp 2g, have
V4 Eigs exp (21)
exp (x,)
VlJ
i
Therefore
Eies exp (2 + Eies exp (2xz)
(0)
Eigs exp (xx))
VI
I 2
g2
g2
where (a) is because Cauchy-Schwae Schwarz inequality.
F.3
Covering number
The following lemma provides an upper bound of the covering number for the network FG.
Lemma F8 (Covering number bound of FG). Let c ||Ållo and d max,, d!". Given an L-layer GIN message passing network FG. for any E > 0
Rg 6²
In (E,
where Rg
2x (2dd
(II n²) (Σt= (m) and = 1[- Ki =
A IT
2/3
3/2
E
Firstly, introduce the core lemma used to find the covering number of compositions of multiple hypothesis function classes.
Lemma E9, Given hypothesis function classes Fi, F2, that maps input from matrix space to output in matrix space and their covering radius (E1, , Ek). Assume all functions in F; is k Lipschitz wrt. ||- l1., and In F., p) S g(Tk) for some function g with parameters a (7) can be multi- valued. Then there exists c-cover C of F Fr Fi with Dimn (c (111]-:4) Kg such that
In C S
g(T))
Proof. Inductively construct covers as follows.
Let C₁ be the co-vr of Fi. By our assumption,
In |C1 S gm))
Let C, as as of F, .... Fr. Suppose In [C,1 S E (T.). For every foo... E C,,, we construct Cj+1.ff.....ff as an 1f+1 cover of F,-1 o fo
f. Define
C++1 =
U
f EC
26

---

It is clearly a cover of F5+1 F3 o ..... Fi By our assumption, we know that
In CC++1.f....11 11 - ((1)-1)
CG+1.13.....11 B3 S exp (g(1)+1))
Then, it is trivial to
C3+1 S |cyl exp (o(ni))
In CJt+1 S Σ g(m)
By the inductive arguments above, we can conclude that
In |C| = In |Cx
Σ g(m))
Next, inductively find the cover radius e for
It is trivial in the base case that the cover C₁ is C1. Suppose for Cs. the cover radius satisfies
CA
G
Ri
jmit1
For all fh+1 In o oi E Futl o Fn o ... .....r Fi, there exists lht1 o S/ o.... ... S E Cz+1
such that
plfit1 o fh. o...o fi. f f...... fi) s pl o fh o ..... fú, fnt1 o f/ o .... fi)
plh+1 Sh o .... fí, la c .... fi)
entl + kntip(f
fí, ..... fi)
ch+1 + Kh+1Eh
h+1
E Kg
i=1
j=it1
By the inductive arguments,
Ek
Kij
j=it1
The following matrix covering number is well-known and the detailed proof can be found in Bartlett jet al. [2017).
Lemma F10. Let conjugate exponents (p. g) and (r. s) be given with p S 2, as well as positive reals (a, b, e) and positive integer m. Let matrix E RRuxd be given with | S Then
a 2 2/r
In (LN(AXA A Rd ||A S a)
11 ..
In (2dm)
2
For the composition of a hypothesis function class and a x- r-Lipschitz function, we have the following lemma
Lemma F.11. Suppose vb is a funnitinn,,,,,nncinnn, then In, o F. s InN(e/R,FF)))
Proof. Let C denote S-cover of F, then for any f F, there exists f E C such that p(fs") S E.
Let Z denote the input, we have
27

---

p f 10 = -1b0 (Z) - v f(2)ll2
<xllf(2) f(Zzh)ll
(Lemma
kp(l(.))
Se
Lemma F.12. Given H, H' E Ruxd and D, D' E RR
Squared MMD distance with gaussian
kernel k(x, y) exp 1-01 y1l) safisfies
MMD (H.D) MMD (H', D') & 4V8 (n 11-1/2 H H 12 + m 11/21ID -D'll2)
Proof. The matrices have the form
h
d'
h
h 2
d
d'
H
H'
D
D'
h
m
Then we have
MMD
(H.))
MMD (H', D')
eexp (-0l lb; hy1l3)
exp (-0llh;; hh1 -1',1]))
1,1=1
exp (-0)) d. d,113) exp (-ølld's -d' d'
Texp (-0llh; dg113) exp (-0llh': d', [
1=1
(a)
V
h, h |l, - hh'sll21 m
||d: d - ||d'; d'
112
1,==1
2v8
h; - d - Ilh1 - d'sllal
mn
1=1 j=1
(6)
(b. - h';) - (h, -h,) + v0
Σ
|| (d: - d',) -dd, -d',) l12
n2
m²
1
4J=l
2/0
(h. h';) - (d, d';) ll2
mn
4
4v0
h: hl
|; d'
n
m
(6) 4 On
4 Om m
H'
D'Il2
n
=4v0 n -1/2
H
H'
|| + m
11/2 D - D'
In the above derivation, (a) holds due to exp (-22) exp y < | yl for any y 2 0, (b) holds due to the triangle inequality, and (c) holds by the Cauchy-Schward Schwarz inequality.
The covering number for single GIN message passing layer Fl with the following Lemma:
28

---

Lemma F.13 (Covering number of F)). Let || For any I E [L] and e >> 0
[[im ks)
IN In (c,FF, .p)
| In(2d)),
e²
2/3
3/2
where = I11ssk k.
Proof. With a little abuse of notation, remove the superscript in Equation 19 for now
F= ((A.)) + (.... ((AH) W1) W,--) W, W. B
where B; := W; ! la S N4. /W S b.}. Denote F; = pZ + σ (ZWi) W, E B,} for i i (r - F, = (Z + ZW, W, E B, then
FF oF oF.
For any S E F [r 1] with arbitrary input Z, Z'
Il fz( ||or (ZW;) :) o (Z'W;)ll
S ZW; Z Z'W 1112
(Lemma F44
- W; 1l. 1Z 2|2
(Lemma
K. Z Z'Il2
Similarly, for any fr E Fy, Lemma gives
llf( - fz 1l = zW, Z'W, 112 S Kr Z Z/
Denoting Z:-1 as the input Fi (Zu Z ÁH) and using the Lipschitz conditions, have
i
Ji (1
II Ki
| se
II Ki
|
(32)
for any fi 0........ fi F, Fi-1 ..... F1. So /Z,-1//2
[II]- K3))
|H||| & c-1- By
Lemma F.10 and Lemmal F.II] we have
In (e,, F.
lnd
W is the maximum dimension of weight matrices (as previously defined in the main text). Thus by
Lemma F99 we have the covering number
bZ In(2d=) = |
62
Kg
IN (c, F p)
S
with cover radius 6 = EE= 1ii K3) Next we need to choose to minimize the right hand side of the above inequality. Holder's inequality states that when 1.
(a, b) I ||al|p||bll
1/8
Σ b,b; S
Σ of
Σ 69
29

---

Let Let bi (11, K3) )² 3 1 -II]= Kig. Choose p = 3
2
fx37
1/2
Σ 0i
Σ (B.Es)
(a,3))) $
2
Σ
Ci
Biei
Σ
(a.
6j
)
2
(33)
-
bi
II Rj
II
K3
2=
j=1
[11)1]
Kij
bi
$
2
Σ
?
2 j=1
12
Add the superscript back,
In. (e, .) s lnddd c²
11
2
Σ
H(-1)= = ((-1) ( (...)a)) (Ax))) where p(h) E jkk for ls E I - 1]. By Equation (32
it is easy to see
1-11 (1(22)
(.. (Ax)) ll2
S
j=1
<
X||2
1=1
= |
ig1-1,j5r
2/3
3/2
Letting K; JI
(3) jsr
Kj
Ei=1
we finish the proof, i.e.,
2
2
2
[T Ks)
In (c,FF, p)
s
1x
2
With the covering number of FG, we can calculate the covering number of F in Equation IT
Lemma F.14 (Covering number of F). Suppose A in the kernel (Equation 15 is fixed. For any 0
640KRG ne²
(24bbVNN Vine
In (e,
Kmdln In
where RG is defined the same as Lemma
F.8
Proof. Denote S E Nx as the output of function F. Consider the entry (i, of S, by Lemma F.12
has
|8ij - - = MMMD (H. D,) MMD 2 (H)
< 4v0 11/3 H. H [|2 + m m112 1/2 D/ -D'112
30

---

Then for the whole matrix S,
N
K
S| - S
8ij
K ?
N
K
I <v80
(n-1/2 1/2
H
H 12 + m |/ -Dyll))
j=1
N K
4v8
Σ
(n
H. H
D, Dj1
1= j=l
20
V (Kn | H Nm- | D
where (a) holds due to (x + y)² s 2(x² + y²). If H H' S 6 and DD - D S 62, then
|S - Sl1l s 4v20 / 1K + Nm-
6
by choosing 61 8vK# and 62 N e. Let BD = DD Kgnx
D s bp). It
well-known that there exists an cg-cover obeying
3bb
Kmd
N (e2, BD, (12))
(34)
62
Denote the output space of Fa, H. Z respectively, we can bound the covering number
(e, = N (e, 2, l12)
N H. (e (e,, 111))
It follows from Lemma F8 and inequality
34 that
In (c, s In (g, H. (12) In (ez, BD. 11112)
640K RG
+ Kmdln 24b /ON Vmme
ne2
E.4
Proof of Lemma E.2
The Dudley entropy integral bound used by Bartlett et al. 2017 is
Lemma F.15 (Lemma A.5 of Bartlett et al. [2017]] )) Let F be real-valued function class taking
values in [0, 1), and assume that F. Then
4a
12
NN
Rg(F) < inf
(c,
a>0
VN
N
Lemma E.2 can be proved with simple modifications.
31

---

Proof. Let F' = - F, where (xx) 1 x, then FF is real-valued function class taking values in
[0, 1]. By Lemma F.15 it has
VN
4a
12
(5.F%))) dl
c
RF(F)) & inf
a>0
VN
+
N
Ja
V
IINN
(7
inf
4a
12
MVN
V IIn (f,
Fr de de)
as0
VN
Ni
VVN
4a
12
inf
+
VinN(e, Fr,
(Lemma F.11
a20
VN
NY
Multiplying both side by 7, has
4ay 12 TVN
Ra(Fa) S inf
+
az0
VN
N
aa
F.5
Proof of Lemma E8
Proof. By Lemma F:1 know
2l77 (IL:=1 )² In (1.F
67 |112 ln(2))
For any J1 E FF, given input Z, it has
110 . ((zz) w(") ... w ) w
[l(
S 1 (...o (Áz)) w(T) ... w ll2
(Lemma F3
< 110 1...a ((AZ) w(") w(22) w
(Lemma F.4
11 3 j=1
|AZ||
r
II
i K
| |Z||2
j=1
/Z|2
which means all ft Fl is exi-Lipschit. Applying Lemma F9
we have
7p [I] CKi)
1.
In, F', .P) <
(2d
6?
with e Etn (z) (I111==1+100 cki)) The only thing left is to minimize Σt_ o "''' ons)²
by con-
trolling e's. Choose af = 7ř (II)=1 eni)
, 1 cnjy Choose p = 3. 2. and apply
32

---

Holder's inequality in the same ways as Equation 33). this yields
2
Σ
4
Brer
2
Σ
(an
3
T [T CKj)
2
2L
61
Ckty
c
j=1+1
j=l
[1] cKij
1
22
(m)
E
e²
Thus derives the conclusion
RG
In In, -
2
where Ro = 2 1n (IL mit
(Etn(1)) (7)
3
F.6 Proof of Theorem 3.2
Proof.
Sincely by (.)) is s-Lisschitz, we can bound the covering number of F,, (defined in Lemma E.1
In (e, s In ((:)
(Lemma
GA0KRan
2AbDHVON ON
ne² + Kmdln
(Lemmaa F.14
/mee
Denote 11
Ropr
= Kmd, 03 = 24v0NboH vm
then by Lemma E.2 we can bound the
Rademacher complexity
IVN
4ay
12
13 de
Rg(FF)
S inf a>0
+ 22 In
VN
N
2
WNN
4ory
12
U1 + U2
inf
+ U22 In Ug de
a20
VN
N
2
4ar
12
NVN
VUI + U2
inf
+ v 1/ In de
a>0
VN
N
4ary VN
12
VN
(NN - -0--))) a)))
inf a>0
+
Vu1 + U2 In
+ YV
22 In us
N
4Y
12 + 02 In
12y(N 1) U2 Inv3
+
N
NVN
47
12
un
12
N
N
where (a) holds due In 1 s L. (b) holds due to Vz+y S V VJ. For (c), we have chosen
VN
can be shown that the covering number bound of Fn satisfies Nee, S (3bp Kmd
(Lemma F.14 Combining the bounds of N (e,Fa. and (e. p) and Lemmas E. and E.2 we derive the generalization bound:
87 + 24 01
In + 2 In
In (2/8)
1,(f) s i.())
+ 3YV
N
2.V
This finished the proof.
33

---

E.7 Corollary of Theorem 3.2
Corollary F.16 (Miscclassification rate upper bound of GRDL). Let be the minimum number of nodes for graphs {G:) be the hyper-perameter in gaussian kernel (Equation 15). = || 1l.. For graphs G {[G,, }}}{ drawn i..dd from any probability distribution over X { K}
and references {D k D2 E gmxd, with probability at least every margin Ç and network f F under Assumption
3.7 satisfy
In (2/8)
8+ 24
+ + 1n NN - 24v Nu ln
Pr mar [(G), # v] s [((() + +3 G
2NV +
N
where
2/3
3
-2500K KoKK Rg
48bp v ON VmC
n²² U2 Kmd,
RR 22 1X
i
and
E, E, I[f(())) S + arg maxj f(Gi),l
Proof. Choose the loss L,(:))) v)
4(59) rc(--((,)))
where M(r,y) = By max Uj is the margin operator and
t< < -
r((1) t/c LE [c,),
t>0.
is called the ramp loss. The population ramp risk is defined as Le(f) == Bo-x (r((-M(((G). v))) Given the graph dataset sampled from X, the empirical ramp risk is ic(ls)
N EN Ccl- y:)). It is clear that |arg f(G), + yl s rc(-M(f((G.u)) so
[arg f(G), + w) s Le(l)
Pr Jarg max f(G), * = G
E G~X
is easy see that = 1 in this case. Also by Lemma by Theorem 3.2 with simple substitution
μ = 2 Then it is trivial to get the bound
Pr (arg max [(G), + v) < (())
G~X
In (2/8) 2N
8 8 In
N N - 24
Nu
h
+3
N
where
11
2560 Ro 122 n²2
=
Kmd, Us
LbbOVON vmL
RR
2L 1 I (IE-, (00)²)
El. El=
2/3\
Also,
rc(-M(](G)) vi)) S ([(())), S arg maxi (GG)),), so we have
N =c(f== N-1 Σ rc(-M(((G). S --1 Σ If(G.), SS+ arg max ((G,)) 341
Corollary E.17 (Generalization bound with cross-entropy loss), Suppose (,(,,)) y) is the cross-entropy loss LCE 7 Let n be the minimum number of nodes for graphs {G+) be the hyper-parameter in gaussian kernel (Equation (5 ).
||A||o. For graphs G [GG,, y drawn i.i.d from
34

---

any probability distribution over X' x {l...., K and references
( k= D2 E R with
probability least 6. every network f E under Assumption 3.
satisfy
In (2/6) 2N
8y + 24 + U2 N 24y No2l
(,) - L,()) + 3wV
+
N
where
D1
1280KRc 02
Kmd, 2/3
24
Rg
2D X In
(II (IT- )
Σl Ei=1
6
2/3
Proof. According to Lemma F.7
V2. Then the proof is trivial by substituting it into Theorem 3.2
F8 Adjacency matrix spectral norm
Lemma F.18. Let G = (V, E) be an undirected graph with adjacency matrix E RRux,, da be the maximum degree of G. Then, the adjacency malrix satisfies
|| S dg
Proof. Based on the definition of the spectral norm, we have
|||
(a) | 1=
max X Ax
max |
Ta S max
Σ
2 1 ( +
x2) = dG Σ
3
2 da
=
|
(i.))EE
(1E)
iEV
where (a) is because A is real symmetric matrix.
Lemma F.19, For any matrix X E RMX"
| S | S V where r = rank
Proof. By the definition of spectral norm,
X |
Amax XX
where Amax denotes the largest eigenvalue. Since X X is a positive semi-definite real symmetric matrix, it must has n real eigenvalues that can be ordered as
\ 2 ... 2..
A++1 A, 0.
Then has
| = VA
Σ A V
= VI
Lemma F.20. Let G (V,E) be a graph with adjacency matrix A E Ruxn Assume 0, then
c A A I| >
Proof. By Lemma F.19
(a) 1 Vr
|||| 2 A 12
A
I|
2
||A||2
Jr
||||
||
21
Vr
where (a) is because E 1.
35

---

F9 Generalization of MMD (to be used in Section F.10
Before stating the lemma, we first give alternative definitions of MMD. Let IP be a continuous probability distribution of some random variable Z taking values from space 2. Then, the kernel mean embedding of associated with the continuous, bounded, and positive-definite kernel function k: 2 2 IR is
f//= 1(2,))))P()
ps :=
(35)
which is element in the Reproducing Kernel Hilbert Space (RKHS) H associated with kernel k. In many practical situations, it is unrealistic to assume access to the true distribution P. Instead, we only have access to samples p {=+]== from P. We can approximate 33 by the empirical kernel mean embedding
Pp
k(zt.)).
(36)
For another continuous distribution probability distribution is defined as
Q with samples mm0m the MMD between the two
MMD(P, Q) l| pallxr,
and the empirical MMD is
MMD(P,Q) - 1| - Ael kel.
Denote = MM Q and d MMD(P,Q), we have the follow Lemma:
Lemma F.21. With probability at least 8 have
vn) 2 1 2l 2
d - dl $ mm +
Proof. We use the following Lemma:
Lemma F222 (Theorem Gretton al. -2²
201
reformulated). Assume k(x,8) S K. Then
with probability at least 2 exp
2K (m(m)
d
22
1
+
1
te
mm
vn
mm then it has
Let = 2exp
(k(m+
2
log
Therefore, with probability at least -
1
2 55
d
2
+
+
2 2og
m
Vi
m
n
1
2
Vm
2
V
2
log
Vm
36

---

E.10 Proof of Lemma F.2
Proof. For simplicity, let k'' = arg o HM, Dj). Since H; and Dy are finite samples
from Pk, and D is sampled from Pk', by Lemma F.21 we have
[FM Pb) MMD(H, ( SAI=
+
2 +
log
w.p. (1- - 8'),
Vm
Vn
8'
[MM Pw) MM,(H, D&) S 2
2+
2 log
w.p. (1 (1-8'). 8').
8
Therefore, with probability at least 28' (union bound), we have
MM, (M) Ps) = MMD(H, D&) A and
MMD MMMDH, DR) S A2.
follows that
MMD(H, D&) MMD(H, Dw) S PM -1 +
By Definition F.1
to ensure correct classification, we can let
-M,DPPs, Pk) + A1 +2
This means
MM PA) > + (1
2
2log 8'
(37)
Therefore, (37 holds, the classification correct with probability at least finish the proof.
25'. Letting á = 28'
L
F.11 Proof of Theorem A.1
Let H RE n.xd be the output of the message passing layers. Then the mean readout matrix multiplication
0
0
0
1
0
0
Z MH.
M
42
722
is easy to see M < 1. Since a MLP is concatenated after readout, by the proof of Lemma F.8 the covering number of GIN F' is
21 X In
In p)
where A (II
(4+))
Σ.
E
(
2/3/3
6;
Then by Lemma E.2
the generalization bound can be easily derived by taking a VN"
37

---

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

---

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

---

reproducible, they including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
CodeSuomissss wwwiebbmmsssioooo ssioniiiccy for more details. httpsccccpbbccccccccc wwwcc/guiieeeeee /utpc//uudde/eeeeuuuuiiiii
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why. At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The paper specifies all the training and test details necessary to understand the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports information about the statistical significance of the experi- ments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
40

---

The paper provides sufficient information on the computer resources needed to reproduce the experiments.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction). 10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: All the datasets used in the paper are open-source. There is no negative societal impact.
Guidelines:
The answer NA means that there is no socictal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA]
Question:
Justification: The paper poses no such risks.
Guidelines:
41

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The creators and original owners of assets used in the paper are properly credited and the license and terms of use explicitly mentioned and properly respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssii thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out the asset's ' creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
42

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
43


Reviews:
[{"review_id": "nqNs1OE1wo", "reviewer": "Reviewer_5HH3", "summary": "This paper proposes to make graph-level predictions via distribution comparison between node-level representations and discrete reference distributions. The authors claim that their proposed method avoids the requirements of graph pooling for graph-level tasks. and reduce the risk of information loss. Theoretical and empirical justification results are provided.", "questions": "Please refer to the weaknesses.", "limitations": "Yes. The authors describe the limited performances of the proposed method on certain datasets.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The authors propose a novel and simple method for graph classification and provide theoretical analysis on the generalization bound. The discussion is clear and extensive.\n- The method shows advantage in time cost compared to related works.\n- The authors performed extensive ablation study on the proposed method.", "weaknesses": "- Equation in L138-139 (a missing equation index?) also requires summation over nodes. The description of \"avoid graph pooling operation\" seems to be overclaimed. I suggest that the authors reconsider it.\n- An ablation study on the discrimination loss and the usage of node-level representation is required. I think the main improvement in performance may be attributed to the discrimination loss. It helps the model learn distant representations for graphs of different labels in the feature space.  The performance of the proposed method should be compared with and without the discrimination loss. Besides, the authors should also implement a baseline with discrimination loss where node representations are first sum-pooling and then compared with the reference distribution.\n- Minor: Latest baseline models are required for a comprehensive empirical comparison, such as graph pooling including SEP[1], GMT[2], and CoCN[3] and graph transformers including Exphormer[4], GRIT[5], and MPNN-VN[6]. Considering the time limitation and the similarity of the datasets, a comparison on part of the datasets will be sufficient.\n\n[1] Structural entropy guided graph hierarchical pooling. ICML'22\n\n[2] Accurate Learning of Graph Representations with Graph Multiset Pooling. ICLR'22\n\n[3] All in a row: Compressed convolution networks for graphs. ICML'23\n\n[4] Exphormer: Sparse Transformers for Graphs. ICML'23\n\n[5] Graph Inductive Biases in Transformers without Message Passing. ICML'23\n\n[6] On the Connection Between MPNN and Graph Transformer. ICML'23", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Weakness 1:**\n\nThank you for your feedback. The equation in lines 138-139 stems from the definition of the Maximum Mean Discrepancy (MMD). MMD is a measure between two discrete distributions, where the inputs are two matrices and the output is a scalar. This means that in the computation, elementary operations like summation are compulsory: it involves summation over the kernel values rather than the original node features. Regarding the claim about avoiding graph pooling operations, we would like to clarify that traditional graph pooling operations typically compress a graph's node embedding matrix into a single vector before classification. In contrast, our method allows for the direct classification of the graph using its node embeddings without compressing them into a single vector. We treat the node embedding matrix as a discrete distribution and handle it by MMD, a theoretical-grounded measure between two distributions. We appreciate your suggestion and will ensure that this distinction is more clearly communicated in the revised manuscript.\n    \n**Response to Weakness 2:**\n    \nThank you for your insightful suggestion. We appreciate your interest in the impact of the discrimination loss on our model's performance. We actually included an ablation study of our proposed method without the discrimination loss in Appendix D.5 Table 10 (where the discrimination loss coefficient $\\lambda = 0$). Following your second advice, we also implement a baseline (denoted as GRDL:SumDis) with discrimination loss, where node representations are first aggregated using sum-pooling and then compared with the reference distribution. The results of the ablation study regarding these two baselines are in the following table.\n    $$\n    \\begin{matrix}\n    \\hline\n    Method              & MUTAG         & PROTEINS      & NCI1          & IMDB-B        & IMDB-M        & PTC-MR        & BZR           & COLLAB & Average \\\\\\\\\n    \\hline\n    GRDL        & \\textbf{92.1} \\pm 5.9 & \\textbf{82.6} \\pm 1.2 & \\textbf{80.4}\\pm 0.8          & \\textbf{74.8}\\pm 2.0 & \\textbf{52.9} \\pm 1.8          & \\textbf{68.3} \\pm 5.4          & \\textbf{92.0} \\pm 1.1 & \\textbf{79.8}\\pm 0.9          & \\textbf{77.9} \\\\\\\\\n    GRDL:\\lambda = 0   & 89.9 \\pm 4.9  & 81.8 \\pm 1.3  & 80.0\\pm 1.6   & 73.1 \\pm 1.5  & 51.3 \\pm 1.4  & 66.6 \\pm 5.9  & 89.5 \\pm 2.3  & 79.0 \\pm 1.0 & 76.4\\\\\\\\\n    GRDL: SumDis & 89.9 \\pm 6.0 & 78.4 \\pm 0.6 & 77.2 \\pm 1.7 & 71.6 \\pm 5.2 & 49.8 \\pm 5.4 & 62.5 \\pm 6.3 & 85.3 \\pm 1.5 &  77.1 \\pm 0.9 & 74.0\\\\\\\\\n    \\hline\n    \\end{matrix}\n    $$\n\nThe results show that discrimination loss can increase the performance of our model. However, our method without discrimination loss still outperforms the baseline with sum-pooling and discrimination loss. We will include these results in the revised version of the manuscript.\n\n\n**Response to Weakness 2 (minor):**\n\nThank you so much for pointing out these baselines. Due to the time limit, we implemented SEP, GMT, and MPNN-VN. The results are shown in the following table. Our method GRDL outperformed the competitors in most cases. We will include these additional results in our paper and discuss all the six references you mentioned.\n    $$\n    \\begin{matrix}\n    \\hline\n    \\text{Method}  & MUTAG                 & PROTEINS              & NCI1                  & IMDB-B                & IMDB-M                & PTC-MR                & BZR                   & COLLAB                       & Average \\\\\\\\\n    \\hline\n    \\text{GRDL (ours)}   & \\textbf{92.1} \\pm 5.9 & \\textbf{82.6} \\pm 1.2 & 80.4 \\pm 0.8 & \\textbf{74.8} \\pm 2.0 & \\textbf{52.9} \\pm 1.8 & 68.3 \\pm 5.4 & \\textbf{92.0} \\pm 1.1 & 79.8\\pm 0.9 & \\textbf{77.9} \\\\\\\\\n    \\text{SEP  [ICML 2022]}   & 89.4 \\pm 6.1  & 76.4 \\pm 0.4  & 78.4 \\pm 0.6   & 74.1 \\pm 0.6  & 51.5 \\pm 0.7  & 68.5 \\pm 5.2  & 86.9 \\pm 0.8  & \\textbf{81.3} \\pm 0.2 & 75.8\\\\\\\\\n    \\text{GMT [ICLR2022]}    & 89.9 \\pm 4.2  & 75.1 \\pm 0.6  & 79.9 \\pm 0.4   & 73.5 \\pm 0.8  & 50.7 \\pm 0.8  & 70.2 \\pm 6.2  & 85.6 \\pm 0.8  & 80.7 \\pm 0.5 & 75.7\\\\\\\\\n    \\text{MPNN-VN [ICML2023]} & \\textbf{92.1} \\pm 5.2  & 78.3 \\pm 1.0  & \\textbf{80.9} \\pm 0.8   & 72.4 \\pm 1.2  & 50.9 \\pm 1.9  & \\textbf{71.4} \\pm 5.2  & 90.2 \\pm 1.1  & 80.1 \\pm 0.8 & 77.0\\\\\\\\\n    \\hline\n    \\end{matrix}\n    $$\n    \n**Please do not hesitate to let us know if you need more explanation or have further questions.**", "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": "b5K12zp4bh", "reviewer": "Reviewer_aUnT", "summary": "The paper introduces a novel algorithm called GRDL for graph classification. GRDL  treats each graph’s latent node embeddings given by GNN layers as a discrete distribution and directly classify distributions without global pooling. The authors derived generalization error bounds for GRDL and verified them numerically. The experiments on many graph datasets show the superiority of GRDL. GRDL is 10 times faster than leading competitors.", "questions": "* Besides GIN, there are other GNN models such as GCN and GAT. Why did the authors consider GIN only in the theoretical analysis and experiments?\n* I think the parameter $\\theta$ of the Gaussian kernel can be absorbed into the neural network parameter. I suggest the authors discuss the necessity of setting or optimizing $\\theta$ separately. \n* In Theorem 3.2, the bound is related to $K$, the number of classes. But, in many literature of generalization analysis, the bound is not related to the number of classes. Could the author explain the difference?", "limitations": "The authors discussed the limitations in Section 6.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* Originality: The proposed algorithm GRDL and the theoretical results are novel.\n* Quality: The paper is well-organized and contains rich theoretical results and numerical comparisons. \n* Clarity: The motivation (e.g. Example 2.1), assumptions, optimization, implication of theorems, and the experimental setting have been clearly explained.\n* Significance: Graph classification is a challenging problem due to the difficulty in converting nodes’ embeddings to a vector as the global representation of each graph. The proposed method gets rid of readout operations and directly classifies the discrete distributions formed by nodes’ embeddings. It can outperform graph kernels, GIN, and graph transformers. Moreover, the paper proved that the proposed model has better generalization ability than the baseline GIN, which is a big contribution.", "weaknesses": "There is no major weakness found. Please refer to my questions in the next section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Question 1:**\n\nThank you for your question. We chose GIN because it is a highly representative model within the class of Graph Neural Networks (GNNs) that utilize neighbor aggregation schemes. GIN is probably the most expressive model in this category, and such schemes are widely employed in many classic GNN designs, including GCN and GraphSAGE.\n\nIn terms of theoretical analysis, our approach can be readily adapted to models like GCN and GraphSAGE with only minor modifications. GAT uses an attention mechanism for aggregation, and this approach differs significantly from the general aggregation scheme employed by GIN, GCN, and many other models. We believe the analysis of GIN provides broader and more valuable insights. Additionally, as we said in our paper, the analysis on GIN's generalization ability is currently limited, and our work aims to address this gap. It's also worth noting that our proposed reference layer can be combined with other models like GCN and GAT to classify graphs without any modification.\n\n**Response to Question 2:**\n\nThank you for your insightful comment. While it is theoretically possible to absorb the parameter $\\theta$ of the Gaussian kernel into the neural network parameters, we believe that setting or optimizing $\\theta$ separately is crucial in practice.\n\nThe main reason for this is that the initial neural network parameters and the reference distributions do not necessarily ensure that nodes of graphs $\\mathbf{x}$ are close to nodes of graphs $\\mathbf{x}'$. If $\\theta$ or the scale of the node embeddings $\\mathbf{H}$ is too large, the Gaussian kernel becomes overly sharp, resulting in almost zero values. This can lead to a situation where the Maximum Mean Discrepancy (MMD) fails to effectively quantify the distance between the embeddings and the reference distributions, of which the complexity is related to $K$.\n\nTo illustrate the importance of setting or optimizing $\\theta$ separately, we actually conducted experiments on the MUTAG dataset with different values of $\\theta$ on Appendix D6, Table 11. The results, shown in the following table, demonstrate that the choice of $\\theta$ significantly impacts classification accuracy. \n    $$ \n    \\begin{matrix} \n    \\hline \n    \\mathbf{\\theta} & 1\\times10^{-4} & 1\\times10^{-3} & 1\\times10^{-2} & 1\\times10^{-1} & 1 & 1\\times10^{1} & 1\\times10^{2} & 1\\times10^{3}\\\\\\\\ \n    \\hline \n    \\textbf{Accuracy} & 0.9096 & 0.9149 & 0.9113 & 0.9113 & 0.8254 & 0.6822 & 0.5737 & 0.3345\\\\\\\\ \n    \\hline \n    \\end{matrix} \n    $$\nThis shows the necessity of carefully selecting or optimizing $\\theta$ to ensure good classification performance. We will elaborate on these findings in the revised manuscript.\n\n**Response to Question 3:**\n\nThank you for your insightful question. The difference arises from our model's unique use of reference distributions. In previous literature on generalization analysis, the focus has often been on models that aggregate node embeddings into vectors and then classify these vectors using another neural network, without incorporating reference distributions. This conventional approach does not typically involve a dependency on the number of classes $K$. In contrast, our model introduces reference distributions.\n    \nWe have also included an additional generalization analysis theorem in the appendix (Theorem A.1) for the GIN model with mean pooling, which does not involve reference distributions. This analysis, consistent with traditional approaches, does not include $K$ in the bound. We hope this clarification and the additional theorem help highlight the unique aspects of our model and the corresponding theoretical analysis.\n\n**Please do not hesitate to let us know if you need more explanation or have further questions.**", "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": "1qhN3CmEgX", "reviewer": "Reviewer_anD1", "summary": "Instead of compressing node embedding matrix into a graph-level vector, this paper proposes a reference distribution learning method GRDL especially designed for graph classification task. GRDL achieves graph classification by measuring the dissimilarity between distributions of the input graph and the references. Theoretical analysis of the generalization error bound offers guidance of hyperparameter tuning.", "questions": "Please refer to the weaknesses.", "limitations": "N/A", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- This paper is well-motivated to avoid information loss caused by node embedding downsampling.\n- The idea of considering graph classification as a distribution comparison problem is interesting.\n- The authors have solid mathematical skills.", "weaknesses": "- The idea is borrowed from domain transfer learning but lacks adaption to graph classification task. In graph classification task, graphs in each dataset “are drawn i.i.d” as the authors mentioned at line 205. This means that although graphs have different classes, they belong to an identical distribution, which is contradictory to the hypothesis of this paper that different classes belong to different reference distributions.\n- In my opinion, this paper didn’t avoid information compression compared to mean pooling and max pooling. MMD unifies the source and target inputs as a vertex in the same RKHS and then calculate the distance between them. I think the mapping from embedding matrix into a vertex can be regarded as information compression, and the calculation of mean discrepancy is similar to mean pooling.\n- The time complexity is too high, the datasets used for large-scale experiments are unreasonable, and the competitors used in efficiency experiment is unreasonable. The time complexity is $O(N^2)$, which is the same as the highly criticised time-consuming node clustering pooling methods (such as DiffPool[1]), while node dropping methods (such as SAGP[2]) only requires a time complexity of $O(E)$. The complexity restricts its scalability to larger-scale graphs. Three so-called large-scale datasets are not really large-scale. They are only large in the number of graphs but not in the number of nodes in each single graph. The authors should add experiments on synthetic large-scale datasets. Besides, in time cost comparison, the authors didn’t choose competitors with SOTA efficiency but used two time consuming methods, which is quite unreasonable.\n- The theoretical contribution of generalization error bound is limited. Firstly, the result offers fuzzy insights into the choose of hyperparameters by giving “moderate-size message passing GIN”, and “moderate-size references”. How to define “moderate”? At line 240, the authors analysis that “a network with a smaller $L4 and $r4 may guarantee a tighter bound on the population risk compared to a larger one. Therefore, a promising strategy is to use a moderate-size message passing GNN”. What’s the causality between “smaller” and “moderate-size”? That’s quite confusing. Experimental results in Appendix show that hyperparameters are still choosed on trial and error. Besides, the generalization ability comparison with GIN with mean readout is meaningless because the competitor is not the SOTA.\n- Important baselines are missing in the experiments. Please add comparison results with recent graph pooling methods such as ASAP[3], MinCutPool[4], StructPool[5], MuchPool[6], TAP[7], Wit-TopoPool[8], and MSGNN[9].\n\nReferences\n\n[1]Ying Z, You J, Morris C, et al. Hierarchical graph representation learning with differentiable pooling[J]. Advances in neural information processing systems, 2018, 31.\n\n[2]Lee J, Lee I, Kang J. Self-attention graph pooling[C]//International conference on machine learning. PMLR, 2019: 3734-3743.\n\n[3]Ranjan E, Sanyal S, Talukdar P. Asap: Adaptive structure aware pooling for learning hierarchical graph representations[C]//Proceedings of the AAAI conference on artificial intelligence. 2020, 34(04): 5470-5477.\n\n[4]Bianchi F M, Grattarola D, Alippi C. Spectral clustering with graph neural networks for graph pooling[C]//International conference on machine learning. PMLR, 2020: 874-883.\n\n[5]Yuan H, Ji S. Structpool: Structured graph pooling via conditional random fields[C]//Proceedings of the 8th International Conference on Learning Representations. 2020.\n\n[6]Du J, Wang S, Miao H, et al. Multi-Channel Pooling Graph Neural Networks[C]//IJCAI. 2021: 1442-1448.\n\n[7]Gao H, Liu Y, Ji S. Topology-aware graph pooling networks[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021, 43(12): 4512-4518.\n\n[8]Chen Y, Gel Y R. Topological pooling on graphs[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2023, 37(6): 7096-7103.\n\n[9]Lv Y, Tian Z, Xie Z, et al. Multi-scale Graph Pooling Approach with Adaptive Key Subgraph for Graph Representations[C]//Proceedings of the 32nd ACM International Conference on Information and Knowledge Management. 2023: 1736-1745.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Weakness 1:**\n\nThanks for your comment. This is a misunderstanding. Almost all papers studying the theory of classification use the i.i.d assumption. The identical distribution does **NOT** contradict the multiple classes scenario. Here the identical data distribution $\\mathcal{D}$ is actually a composition of $K$ sub-distributions, where each sub-distribution (related to one reference distribution in our method) corresponds to a class. An intuitive example is the Gaussian mixture models: data distribution $\\mathcal{D}$ is composed of $K$ Gaussians, i.e., $p_{\\mathcal{D}}\\left(\\mathbf{x}\\right)=\\sum_{k=1}^K p\\left(\\mathbf{x} \\mid \\mathbf{z}\\right) p(\\mathbf{z})=\\sum_{k=1}^K \\pi_k \\mathcal{N}\\left(\\mathbf{x} \\mid \\mu_k, \\Sigma_k\\right)$ (samples drawn i.i.d from $p_{\\mathcal{D}}$ belongs to different classes). For instance, the following popular papers on classification used i.i.d assumption as us.\n\n[1] VN Vapnik. The nature of statistical learning theory. Springer science \\& business media, 2013. (68000+ citations)\n\n[2] PL Bartlett et al. Spectrally-normalized margin bounds for neural networks. NeurIPS 2017. (1200+ citations)\n\n[3] C. Zhang et al. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM 64, no. 3 (2021): 107-115. (7000+ citations)\n\n**Response to Weakness 2:**\n\nWe treat the nodes' embeddings as discrete distributions and measure the distance between two distributions using MMD. MMD [1] with a Gaussian kernel actually compares all orders of statistics between two distributions rather than the means, though this is implicitly conducted in the RKHS using the mean difference. In other words, MMD compares also the higher-order statistics between distributions while mean pooling compares only the first-order statistics, i.e., mean. Therefore, the information loss of MMD is much less than the mean and max poolings. \n\nWe used Example 2.1 to show the limitation of mean and max pooling and the motivation for we regard each node embedding matrix as a discrete distribution. Two different distributions may have the same mean and max but their MMD is never zero. MMD has also been utilized in generative models (e.g. MMD-GAN [2]) to compare distributions, where comparing the means (like mean pooling) in the feature space given by a neural network does not work.\n\n\n[1] Arthur Gretton et al. A kernel two-sample test. JMLR 2012.\n\n[2] Li et al. MMD GAN: Towards deeper understanding of moment matching network. NeurIPS 2017.\n\n**Response to Weakness 3:**\n\nWe acknowledge that our method is efficient in terms of the number of graphs rather than the number of nodes in each graph. However, there are many graph datasets with a large number of graphs but a relatively small number of nodes in each graph, for which our method can be used.\n\nIt is really very difficult to propose an algorithm with both SOTA accuracy and SOTA efficiency. Our method has a good trade-off between them. We follow your suggestion and compare the time cost of our method with two pooling methods published in 2023 (WitTopoPool and MSGNN). The results are in the **global rebuttal** due to the character limitation. In fact, these two methods are much more costly than ours. The GNN-based topological pooling layer requires the calculation of pairwise node similarity, which is $O(N^2)$. Besides, the time complexity of its witness complex-based topological layer is also quadratic. The subgraph sampling, selection, and evolution of MSGNN are also very costly.\n\n**Response to Weakness 4:**\n\nThanks for your insightful comment. Similar to the previous work on learning theory such as [1][2][3], our theorem can only show the impact of the model architecture and parameters on the generalization ability of the model and there is always a trade-off between model complexity and training accuracy, that's why we used the words like \"moderate\" and \"smaller\". The upper bounds of the training error are data-dependent, which means we may never point out exactly what model is the best according to only the theoretical analysis. \n\nThe generalization bound is the upper bound of the difference between training error and testing error. We say \"a network with a smaller $L$ and $r$ may guarantee a tighter bound on...\" because in the bound, the term $\\tilde{\\mathcal{O}}\\left(\\frac{\\mu \\bar{b}\\|\\mathbf{X}\\|_2 c^L(L r)^{\\frac{3}{2}} \\bar{\\kappa}^{L r} \\sqrt{\\theta K / n}}{N}+\\gamma \\sqrt{\\frac{K m d}{N}}\\right)$ increases with $L$ and $r$. So here the \"smaller\" is an exact expression.\n\nWe say \"moderate-size references\" because the bound scales the reference size $m$ as $\\tilde{O}(\\sqrt{m})$, which means the bound is not very sensitive to $m$ because of the square root. If $m$ is too small, the expressive power of the model will be low; if it is very large, the complexity $\\tilde{O}(\\sqrt{m})$ is high. Therefore, we say \"moderate-size\", meaning a trade-off, should be used. This is supported by the experiments in Appendix D.3 (Figure 6) in our paper. \n\nLet's use an intuitive example (may not be true in practice) to further explain why we have to use \"moderate\" rather than a concrete value (e.g. 0, 1, $\\infty$) in a discussion of the theoretical result. Suppose there is a parameter or hyperparameter $s$ of the model and the bounds scales with it as $\\tilde{O}((s-1)^2)$ and $s$ does not influence the training error, then the best $s$ is 1. However, in practice, the training error may decrease when $s$ increases. The training error is data-dependent, which means we cannot find the best $s$ using the theoretical result only. Instead, one may use cross-validation or AutoML to find a good $s$.\n\n**Response to Weakness 5:**    \n\nThe added results (MinCutPool, ASAP, Wit-TopoPool, MSGNN) are in **global rebuttal**. Our method has better classification accuracy on most of the datasets and has the highest average accuracy.\n\n**Please do not hesitate to let us know if you need more explanation or have further questions.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely appreciate the reviewers' comments. In this rebuttal, we added the following experiments.
1. **Training time per epoch** compared to two latest baselines (WitTopoPool and MSGNN both proposed in 2023) mentioned by reviewer anD1 on both experimental datasets in our paper and three synthetic datasets. The three synthetic datasets have 2000 graphs with 100(SYN-100), 300(SYN-300), 500(SYN-500), and 1000(SYN-1000) nodes per graph, respectively. The edge number is $0.1n^2$ where $n$ is the number of nodes. See the following table.
$$
\begin{matrix}
\hline
  & MUTAG                 & PROTEINS              & NCI1                  & IMDB-B                & IMDB-M                & PTC-MR                & BZR    & COLLAB & SYN-100 & SYN-300 & SYN-500 & SYN-1000\\\\
\hline
\text{GRDL (ours)} & 0.4 & 3.4 & 12.6 & 2.4 & 3.5 & 0.8 & 1.2 & 16.3 & 26.6 & 45.8 & 88.7 & 220.8\\\\
\text{WitTopoPool (2023)}  & 0.4  & 2.6 & 21.4 & 2.4 & 2.6 & 1.0 & 1.3 & 39.1 & 32.9 & 50.8 & 97.5 & 201.3\\\\
\text{MSGNN (2023)} & 45.2  & - & - & - & - & 75.5  & 135.3 & - & - & - & - & -\\\\
\hline
\end{matrix}
$$
Message to Reviewer anD1: As can be seen, our method GRDL is more efficient than these two latest pooling methods you mentioned when the number of nodes in each graph is less than 1000. In fact, graph dataset for graph-level learning (not node-level learning) with an average node number larger than 1000 is rare.
2. **Ablation study** for the two terms in the objective function of our method GRDL. See the following table.
    $$
    \begin{matrix}
    \hline
    Method              & MUTAG         & PROTEINS      & NCI1          & IMDB-B        & IMDB-M        & PTC-MR        & BZR           & COLLAB & Average \\\\
    \hline
    GRDL        & \textbf{92.1} \pm 5.9 & \textbf{82.6} \pm 1.2 & \textbf{80.4}\pm 0.8          & \textbf{74.8}\pm 2.0 & \textbf{52.9} \pm 1.8          & \textbf{68.3} \pm 5.4          & \textbf{92.0} \pm 1.1 & \textbf{79.8}\pm 0.9          & \textbf{77.9} \\\\
    GRDL:\lambda = 0   & 89.9 \pm 4.9  & 81.8 \pm 1.3  & 80.0\pm 1.6   & 73.1 \pm 1.5  & 51.3 \pm 1.4  & 66.6 \pm 5.9  & 89.5 \pm 2.3  & 79.0 \pm 1.0 & 76.4\\\\
    GRDL: SumDis & 89.9 \pm 6.0 & 78.4 \pm 0.6 & 77.2 \pm 1.7 & 71.6 \pm 5.2 & 49.8 \pm 5.4 & 62.5 \pm 6.3 & 85.3 \pm 1.5 &  77.1 \pm 0.9 & 74.0\\\\
    \hline
    \end{matrix}
    $$
 3. **In addition to the 12 baselines** compared in our original submission, we **added 6 more baselines**. See the following table.
 $$
    \begin{matrix}
    \hline
    Method  & MUTAG                 & PROTEINS              & NCI1                  & IMDB-B                & IMDB-M                & PTC-MR                & BZR                   & COLLAB                       & Average \\\\
    \hline
    GRDL (ours)    & \textbf{92.1} \pm 5.9 & \textbf{82.6} \pm 1.2 & \textbf{80.4} \pm 0.8 & \textbf{74.8} \pm 2.0 & \textbf{52.9} \pm 1.8 & 68.3 \pm 5.4 & \textbf{92.0} \pm 1.1 & 79.8\pm 0.9 & \textbf{77.9} \\\\
    SEP (2022)    & 89.4 \pm 6.1  & 76.4 \pm 0.4  & 78.4 \pm 0.6   & 74.1 \pm 0.6  & 51.5 \pm 0.7  & 68.5 \pm 5.2  & 86.9 \pm 0.8  & \textbf{81.3} \pm 0.2 & 75.8\\\\
    GMT (2022)    & 89.9 \pm 4.2  & 75.1 \pm 0.6  & 79.9 \pm 0.4   & 73.5 \pm 0.8  & 50.7 \pm 0.8  & \textbf{70.2} \pm 6.2  & 85.6 \pm 0.8  & 80.7 \pm 0.5 & 75.7\\\\
    MinCutPool (2020)  & 90.6 \pm 4.6  & 74.7 \pm 0.5  & 74.3 \pm 0.9   & 72.7 \pm 0.8  & 51.0 \pm 0.7  & 68.3 \pm 4.4  & 87.2 \pm 1.0  & 80.9 \pm 0.3 & 75.0\\\\
    ASAP (2020)  & 87.4 \pm 5.7  & 73.9 \pm 0.6  & 71.5 \pm 0.4   & 72.8 \pm 0.5  & 50.8 \pm 0.8  & 64.6 \pm 6.8  & 85.3 \pm 1.3  & 78.6 \pm 0.5 & 73.1\\\\
    WitTopoPool (2023) & 89.4 \pm 5.4  & 80.0 \pm 3.2  & 79.9 \pm 1.3   & 72.6 \pm 1.8  & 52.9 \pm 0.8  & 64.6 \pm 6.8  & 87.8 \pm 2.4  & 80.1 \pm 1.6 & 75.9\\\\
    MSGNN (2023) & 78.4 \pm 7.1  & - & - & - & - & 56.4 \pm 6.6  & 78.1 \pm 2.5 & - & \\\\
    \hline
    \end{matrix}
    $$
Message to Reviewer anD1: Our method outperformed the four pooling methods you mentioned as well as the other two pooling methods SEP and GMT proposed in 2022.

Besides supplementary experiments, we made several important rebuttals:
* We explained why our method avoids pooling: MMD takes summation over kernel values instead of summation over original nodes (see responses to reviewer 5HH3).
* We added an ablation study on the discrimination loss (see responses to reviewer 5HH3).
* We added experiments of six additional baselines and compared the classification accuracy (see responses to reviewer 5HH3, anD1 and also the PDF file in global rebuttal).
* We explained why optimizing/setting $\theta$ separately is necessary (see responses to reviewer aUnT).
* We argued the use of i.i.d assumption in our theoretical analysis is correct and has been commonly used in many famous papers of learning theory (see responses to reviewer anD1).
* We added experiments of two SOTA methods' training time per epoch on both datasets used in our paper and three synthetic datasets (see responses to reviewer anD1 and also the PDF file in global rebuttal).

**We are looking forward to your feedback on our rebuttal. Thanks.**

Meta-review: The paper proposes an architecture for graph-level prediction based on node-level representation computing by a GNN. Instead of using a pooling method, the paper derives a reference distribution learning method for graph-learning tasks. That is, the authors' architecture measures the dissimilarity between distributions of the input graph and the references. The authors propose a generalization analysis based on standard tools and conducted an empirical study showing somewhat promising results, mostly on smaller datasets from the TUDataset collection.

The reviewers liked the novel idea of using distribution comparison for graph-level prediction. Some highlighted the clear motivation and good exposition and the performed extensive ablation studies on the proposed method. Reviewer anD1 argued that the method shares similarities with mean pooling and max pooling; the time complexity is too high, and some GNN pooling baselines are missing in the experiments. The authors partially addressed some of these concerns in the rebuttal.

This is a borderline paper. A majority of reviewers favor its acceptance due to its novelty. I follow this assessment.
Decision: Accept (poster)