Exploring Consistency in Graph Representations: from Graph Kernels to Graph Neural Networks
Authors: Xuyuan Liu
Yinghao Cai
Qihui Yang
Yujun Yan
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Neural Networks
Representation Consistency
Graph Classification
Primary area: graph_neural_networks

Abstract: Graph Neural Networks (GNNs) have emerged as a dominant approach in graph representation learning, yet they often struggle to capture consistent similarity relationships among graphs.  To capture similarity relationships, while graph kernel methods like the Weisfeiler-Lehman subtree (WL-subtree) and Weisfeiler-Lehman optimal assignment (WLOA) perform effectively, they are heavily reliant on predefined kernels and lack sufficient non-linearities. Our work aims to bridge the gap between neural network methods and kernel approaches by enabling GNNs to consistently capture relational structures in their learned representations. Given the analogy between the message-passing process of GNNs and WL algorithms, we thoroughly compare and analyze the properties of WL-subtree and WLOA kernels. We find that the similarities captured by WLOA at different iterations are asymptotically consistent, ensuring that similar graphs remain similar in subsequent iterations, thereby leading to superior performance over the WL-subtree kernel. Inspired by these findings, we conjecture that the consistency in the similarities of graph representations across GNN layers is crucial in capturing relational structures and enhancing graph classification performance. Thus, we propose a loss to enforce the similarity of graph representations to be consistent across different layers. Our empirical analysis verifies our conjecture and shows that our proposed consistency loss can significantly enhance graph classification performance across several GNN backbones on various datasets.

edu Exploring Consistency in Graph Representations from Graph Kernels to Graph Neural Networks
Xuyuan Liu!
Yinghao Cai'
Qihui Yang²
Yujun Yan'
Dartmouth College
University of California San Diego
(xuyuan. liu.gr, gr, yinghao cai, qiy0090ucsd.ed
Abstract
Graph Neural Networks (GNNs) have emerged dominant approach in graph representation learning, yet they often struggle to capture consistent similarity relationships among graphs. While graph kernel methods such as the Weisfeiler- Lehman subtree (WL-subtree) and Weisfeiler- kernels are effective in capturing similarity relationships, they rely heavily on pre- defined kernels and lack sufficient non-linearity for more complex data patterns. Our work aims bridge the gap between neural network methods and kernel approaches by enabling GNNs to consistently capture relational structures in their learned representations. Given the analogy between the message-passingg process of GNNs and WL algorithms, we thoroughly compare and analyze the properties of WL-subbree and WLOA kernels. We find that the similarities captured by WLOA at different iterations are asymptotically consistent, ensuring that similar graphs main similar in subsequent iterations, thereby leading to superior performance over the WL-subtree kernel. Inspired by these findings, we conjecture that maintaining consistency in the similarities of graph representations across GNN layers is crucial for capturing relational structures and improving graph classification performance. Thus, we propose a loss to enforce the similarity of graph representations to be consistent across different layers. Our empirical analysis verifies our conjecture and shows that our proposed consistency loss can significantly enhance graph classification performance across several GNN backbones on various datasets.
optimal assignment (WLOA)
Introduction
Graph classification tasks are extensively applied across multiple domains, including chemistry [Liu al., 2022, Xu et al., 2023], bioinformatics [ (Yan al., 2019, Li et al., 2023a,b), and social network analysis [Ying et al., 2018, Wang et al., 2024]. Graph neural networks (GNNs) [Kipf and Welling, 2017, Xu et al., 2019, Velickovic et al., 2018, Huang et al., 2024] have emerged as the predominant approach for performing graph classification, owing to their ability to extract rich representations from various types of graph data. A typical GNN employs the message-passing mechanism [Gilmer et al., 2017], where node features process effectively captures local tree structures, enabling the differentiation between various graphs. However, GNNs often struggle to preserve relational structures among graphs, resulting inconsistent relative similarities across the layers. As shown in Figure 1, graphs with higher relative similarity in one layer may exhibit reduced similarity in the subsequent layer. This phenomenon arises from the limitations of cross-entropy loss, which fails to preserve relational structures, as forces graphs within the same class into identical representations.
propagated and aggregated across connected nodes. This
release our code https: //githubb....////// http::///epppaaaaaaaaaatottttoto
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

GNN Layer
Similarity
Similarity
GNN Layer
Similarity
ft.
Shmilarity
GNN
Similarity
Similarity
Figure 1: Cosine similarity of three molecules from the NCI1 dataset, evaluated using graph representations from three consecutive GIN layers. Common GNN models fail to preserve relational structures across the layers.
Graph kernel methods, on the other hand, are designed to capture similarities between graphs and utilize these similarities for classification tasks. For instance, subgraph-pattens approaches [Sher- vashidze et al., 2009, Kriege et al., 2020] compare graphs by counting the occurrences of fixed-size subgraph motifs. Other methods compare sequences of vertices or edges encountered during graph traversals [Borgwardt and Kriegel, 2005, Kashima et al., 2003, Zhang et al., 2018]. Among all graph kernels, two notable ones are the Weisfeiler-Lehman subtree (WL-subtree) kernel [Shervashidze et al., 2011] and the Weisfeiler-Lehman optimal assignment (WLOA) kernel [Kriege al., 2016]. They found to have comparable performance to simple GNNs [Nikolentzos et al., 2021]. The WL-subtree kernel iteratively relabels graphs using the Weisfeiler- Weesman algorithm [Weisfeiler and Lehman, 1968] and constructs a kernel based on the number of occurrences of each label. The WLOAA kernel uses the same relabeling scheme but computes matching between substructures to reveal structural correspondences between the graphs.
While effective in capturing relative graph similarity, kernel methods rely predefined kernels and exhibit insufficient non-lincarities, limiting their ability to capture complex patterns in high- dimensional data. Additionally, kernel methods are computationally costly, making them unsuitable for handling large datasets and consequently limiting their overall applicability.
In this work, we aim to bridge the gap between kernel methods and GNN models. Given the iterative nature of GNNs, we study a class of kernels which are induced from graph representations obtained through an iterative process and name them iterative graph kernels (IGK). Within this framework, we define the consistency property, which ensures that similar graphs remain similar in subsequent iterations. Our analysis demonstrates that kernels with this property ensure better generalization ability, leading to improved classification performance.Furthemmoorr we find that this property sheds light why the WLOA kernel outperforms the WL-subtree kernel. The WLOA kernel asymptotically demonstrates consistency as the iteration goes to infinity, whereas the WL-subtree kernel does not exhibit this behavior. Inspired by these findings and the analogy between pressage-passingg GNNs and the WL-subtree kernel [Xu et al., 2019], 9], we hypothesize that this principle is also applicable to GNNs. To explore this. we introduce novel loss function designed to align the ranking of graph similarities across GNN layers. The aim is to ensure that the relational structures of the graphs preserved and consistently reflected throughout the representation space of these layers. We validate this hypothesis by applying our loss function to different GNN backbones across various graph datasets. Extensive experiments demonstrate that our proposed madel-agnostic consistency loss improves graph classification performance comprehensively.
In summary, the main contributions of this work are follows:
We present a novel perspective on understanding the graph classification performance of GNNs by analyzing the similarity relationships captured by different layers. New insights: We are the first to introduce and formalize the consistency principle within both kernel-based and GNN methods for graph classification tasks. Additionally, we provide theoretical proofs explaining how this principle enhances the performance.
Novel perspective:
Simple yet effective method: Empirical results demonstrate that the proposed consistency loss universally enhances performance across a wide range of base models and datasets.
2 Preliminaries
In this section, begin by introducing the notations and definitions used throughout the paper. Next, we provide an introduction to the fundamentals of Weisfeiler-Lehme isomorphism test, GNNs and graph kernels.

---

2.1
Notations and Definitions
Let g(V, &, X) be an undirected and unweighted graph with nodes, where denotes the node set, & denotes the edge set, and X denotes the feature matrix, where each row represents the features of corresponding node. The neighborhood of node is deñned as the set of all nodes that connected to (v) {ul (v, u) E } In graph dataset, each graph G. is associated with a label V/ which is sampled from label set C. In this paper, we focus on the graph classification task, where a model Ø is trained to map each graph to its label.
2.2 Weisfeiler-Lehmal Isomorphism Test
We first introduce the Weisfeiler-Lehmee
isomorphism test [Weisfeiler and Lehman, 1968], which be used to distinguish different graphs and is closely related the pressage-passing process of GNNs [Xu et al., 2019]. The WL algorithm operates by iteratively relabeling the colors of vertices in the graph. Initially, all vertices assigned the same color Co. In iteration i, the color of vertex is updated based on its current color Cv..-1 and the colors of its neighbors (CueN(o),s-1)- The update is given as follows:
C2, = fc ((Co,-ir(CueNNo. (CueN(o)a-11))
where fü is an injective coloring function that maps the multisets to different colors at iteration i. T.Tss process continues for predefined number of iterations until the coloring stabilizes (i.e., the colors no longer change).
2.3 Graph Neural Network
Most GNNs adopt the message-passing framework [Gilmer et al., 2017], which can be viewed as a derivative of the Weisfeiler-Lehman coloring mechanism. Specifically, let h (((=1) represent the feature vector of node at the (Is 1)-th iteration. A GNN computes the new feature for by aggregating the representations of itself and its neighboring nodes u E EN(u) as follows:
h (b) UPDATE ()) h!! (k-1) m!!)) where m (k) = AGGR (+)
: :EE(())
The initial node representations he are set to the raw node features X At the k-th iteration, the aggregation function AGGR! (-) computes the messages m received from neighboring nodes. Subsequently, the update function UPDATE(() computes new representation for each node by integrating the neighborhood messages my with its previous embedding (k-1) After T iterations, the final node representations are combined into graph representation using a readout function:
((n U luee v)).
hg READOUT
The readout function, essentially set function learned by the neural network, commonly employs AVERAGE or MAXPOOL.
2.4 Graph Kernel
kernel is a function used measure the similarity between pairs of objects. For a non-empty set x and function K x X IR, the function IK qualifies kernel on x if there exists Hilbert space Hs and a feature map function Φ : - Ha. such that IK(,, y) (d(xr), Φ(v)) for any x, y E X. where ( denotes the inner product in H4. Notably, such a feature map exists if and only if K. is a positive semi-definite function. Let IK a kernel defined on X. and let S {ø1..... ,, be finite set of samples X. The Gram matrix for S is defined G E g with each element Gy = (I,,, x representing the kernel value between the i-th and j-th data points in S. The Gram matrix is always positive semi-definite.
Graph kernel methods apply the kernel approaches graph data, typically defined using the R- convolution framework [Haussler et al., 1999, Bause and Kriege, 2022]. Consider two graphs, G and G'. The key idea to decompose the graphs into substructures using a predefined feature map function Φ, and then compute the kernel value by taking the inner product in the feature space: (G, G') (cb(),, (G")), based on these substructures. Weisfeiler-Lehman (WI.) graph kernels stand out of the most widely used approaches. These methods employ the Weisfeiler-Lehmarl
3

---

coloring scheme to iteratively encode graphs, calculating kernel values based on these colorings. The final kernel values are derived through the aggregation of intermediate results. Next, we introduce the WI.-subtree kernel and the WI.OA kernel in more detail. Let f be the coloring function at the i-th iteration, mapping the colored graph from the previous iteration to a new colored graph. Define v/ as the function that captures the cumulative coloring effect up to the i-th iteration: 1/ f o ...... f*. Specifically, the WL-subtree kernel computes the kernel value by directly using the label histogram as feature to compute the dot product, which is expressed as:
(h) wl subtree (9.9") Σ (6(+)))) (g)))
The WLOA kernel applies a histogram intersection kernel to match substructures between different graphs, which is formulated as:
KK (b) LLA (9,9") histmin (0t00)0EEaataannoo00000000000000 (i)
where w(i) is a nonnegative, monotonically non-decreasing weight function, and w(i) is commonly used in practice [Kriege et al., 2016, Siglidis et al., 2020J. The operator histmin denotes the histogram intersection kernel. is computed by comparing and summing the smallest matching elements between two sets. For example, consider two sets S {a, 6, 6, c} and S2 {a, 6, b, c). The histmin(Si,, S2) is calculated by taking the minimum frequency of each distinct element across the two sets, yielding min(2, 1) + min 2) + min(1,2) 4. To ensure that the kernel values fall in the range of 0 to 1, normalization is often applied. The normalized kernel value (()) is then expressed as follows:
K (G,9")
(G, (K /Kt (G'
3 Consistency Principles
To encode relational structures in GNN learning, we first examine how similarities are represented in graph kernels. In this section, we start by defining class of graph kernels, i.e., the iterative graph kernels, which encompasses many widely used kernels. Then, we delve into a key property known as the consistency property, which may play an important role enhancing classification performance. We support this assertion through theoretical analysis, elucidating how different kernels adhere to or deviate from this property, thereby explaining their performance differences.
3.1 Iterative Graph Kernels
In this paper, we interested in set of kernels defined follows:
Definition 3.1
Given a colored graph set X. feature map function & + Hy (where Hy is Hilbert space), and set of coloring functions Fe f (f........ f`} on X (with f X X). we define the set of iterative graph kernels (IGK) as:
o... KF. (I, v, of.. (x)) o... (v)) (66 (x), (3
where F. y X and di (.) represents composite function given by: wi = fio ... f Then the normalized kernel is given by:
K (x. y, Vk (0 x. Th KF. i)
K (o,0
Based on this definition, we can see that graph kernels utilizing the Weisfeiler-Lehman framework, including the WL-subtree kernel [Shervashidze et al., 2011], WLOA |Kriege et al., 2016), and the Wasserstein Weisfeiler-Lehman kernel [TTogninalli et al., 2019], should be classified as iterative graph kernels. Conversely, the subgraph-pattem approaches, such as the graphlet kernel [Shervashidze et al., 2009] and the shortest-path kernel [Borgwardt and Kriegel, 2005], do not fall into this category.

---

3.2 Key Properties: Monotonic Decrease & Order Consistency
To effectively capture relational structures, we design the IGKs to progressively differentiate between graphs. With each iteration, additional structural features are considered, enabling the distinction of graphs that may have been indistinguishable in earlier iterations. This implies two properties: (1) the kernel values monotonically decrease with larger iterations, the similarity between two graphs decreases with the consideration of more features; and (2) the similarity rankings across different iterations should remain consistent, meaning that graphs deemed dissimilar in early iterations should not be considered similar in later iterations. We then provide formal definitions for these two properties and prove how they improve generalization in the binary classification task.
Definition 3.2 (Monotonic Decrease) The normalized iterative graph kernels KF.,0(1; (, are said to be monotonically decreasing if and only if:
(F, y, (. Vx,yEX
Definition 3.3 (Order Consistency) The normalized iterative graph kernels Kx. oz. y. are said
to preserve order consistency if the similarity ranking remains consistent across different iterations for any pair of graphs, which is defined as:
(F,, (F, oz, Vr,y, Ex
Next, we show that these two properties can lead to a monotonically decreasing upper bound on the test error in the binary classification task, which suggests improved performance.
Consider binary graph classification task and assume that the graph representations obtained at any iteration have a uniform norm. This can be achieved by simply normalizing the graph representations at the end of each iteration. That is, for any graph æ: []ø( v (=))1l = 1. Then, for any IGK that is monotonically decreasing and preserves the order consistency, the following theorem holds:
Theorem 3.4 Let K5,,,(zz, i) be normalized iterative graph kernel. Its generalization ability the test set is provably strong when it decreases monotonically and preserves order consistency.
Proof sketch. We consider a binary classification task where supervision is provided through labels and similarity orders. We demonstrate that the presence of these two properties enhances the generalizability of the learned iterative kernel. The proof is structured in two steps:
We first show that iterative kernels can learn the correct ranking given sufficient data during training, using the PAC-learning framework.
Next, we demonstrate that, once the correct ranking is learned, an iterative kernel learned with the properties of monotonic decrease and order consistency guarantees that the error decreases the number of iterations increases.
rate of the graphs in the
Details of the proof can be found in Appendix A.
3.3 Theoretical Verification with WL-based Kernels
As discussed in Section 3.1, WI.-based kernels can be categorized as iterative graph kernels, as they are generated by the coloring functions an iterative refinement process. Consequently, natural question arises regarding how various kernels adhere to these properties and whether their adherence reflects their actual performance. We thus investigate two popular WL-based kernels: the WL-subtree kernel (Shervashidze et al., 2011] and the WLOA kemel [Kriege al., 2016].
The normalized WL-subtree kernel is neither monotonically decreasing nor does it preserve order consistency.
Theorem 3.5
Theorem 3.6 The normalized WLOA kernel is monotonically decreasing and asymptotically pre- serves order consistency when wi))
5

---

Proof sketch. For Theorem 3.5, we illustrate counterexample, while for Theorem 3.6, we consider two graph pairs where the similarity condition holds:
( w FLA (9,9")
((( WLOA (9,9")
The similarity at the next iteration + 1 is scaled by a factor dependent w()) 100);==1,0 = 1,... + The unnormalized kernel increases monotonically, though with diminishing increments over iterations. Given this, when wi) = 1 and h + oc, we obtain:
((++)) W LOA (G,9") 2 WLOA (G,g")
We include the complete proof in Appendix B.1 and B.2.
These findings imply that the WLOA kernel better preserves relational structures compared to the WL- subtree kernel, leading to improved classification performance, supported by the literature [Kriege al., 2016).
4 Proposed Strategy
Given the analogy between WL-based kernels and GNNs [Shervashidze et al., 2011, Gilmer et al., 2017], and the observation that GNNs often fail to preserve relational structures, we hypothesize that the consistency principle is also beneficial to GNN models. Thus, we aim to explore how to effectively preserve this principle within the GNN architectures.
Pelmoreer Condine Sindiarity
Xt refevence probabiiity matrix
Dー11
6-th mo
Dint
Similarity
Cross Entropy
D
*g prediction probahility matris
GNN Layer
DirtD
Figure 2: Computation of Consistency loss. At each layer, pairwise distance matrix is calculated using the normalized representations of graphs in a batch. After randomly selecting reference graph the reference probability matrix is computed using the distance matrix from previous layer, where entry (n, m) represents the known probability that the graph 34 more similar the graph x, than matrix of current layer, we compute the predicted probability that as is closer to x. than to 2m and form the prediction probability matrix. Consistency loss is computed as the cross-entropy between the predicted and reference probability matrices
graph Tm. For the distance
4.1 Consistency Loss
Our objective is to enhance graph representation consistency across GNN layers, which has significant potential to preserve the relational structure in the representation space. If we compare o(v (G))(()) to the graph representations obtained at the i-th layer, preserving the consistency principle is equivalent to preserving the ordering cosine similarity among the graph representations. However, due to the non-differentiable nature of ranking operations, directly minimizing the ranking differences between consecutive layers is not feasible using gradient-base based optimization techniques. Therefore, we aim to optimize pairwise ordering relations instead of the entire ranking list. In this work, proposed loss employs a probabilistic approach inspired by [Burges et al., 2005]. The entire framework is illustrated in Figure 2.
Let A E R denote the graph embedding matrix for n examples batch, each with d- dimensional feature vector. We first compute the distance matrix D for all the graphs in batch at

---

the h-th layer. The entries Di, of this matrix represent the distance between the representations of the i-th and j-th graphs, calculated as D Dist HH Hb: Here, the cosine distance, the complement of cosine similarity in positive space, expressed 1
H -H
Considering
the distance relationship to arbitrary graph 2ş in the batch, the predicted probability 1oth that nnm/k
Iy is more similar to graph nn than to graph Im at layer h is defined as 1P4 This probability score, which ranges from 0 to 1, is formulated using the sigmoid function follows:
(DA.,
< D
n.ml
A.
k.
p n.m [A: (Dh.n < Dk.m)
1 + exp (DA k.m
k.n
Given the distance matrix from the previous layer DA-1, the known probability that graph is more similar to graph Zn, than to graph Imm denoted as 1 k.n ( can be formulated follows:
pi-1
(1 2
sign (D (
We can then minimize the discrepancy between the predicted and the known probability distributions to enhance representation consistency across the layers. Here, we employ the cross-entropy loss to effectively measure the divergence between these two distributions. Specifically, for pair (I Imm centered 2i layer h, the cross-entropy loss can be expressed
Leross entmopy TTm sw. h) = f n.miik log for
(1 1ph-11 k) log (1- (pt n,ml(k
n.mlk
Then, the total loss function, which quantifies the consistency of pair-wise distance relations for graph Ty at layer h, can be formulated as
Leunsistency (k) =
Σ E(((nn (T)) Ik,h)
22,17
The overall objective function of the proposed framework can then be formulated as the weighted sum of the original loss and the consistency loss.
Liotal = Lorigin +
Σ
Lconsistency (i)
Here, À is hyperparameter that controls the strength of the consistency constraint.
Experiment
In this section, examine the effectiveness of the proposed consistency loss for the graph classi- fication task. Specifically, we aim to address the following questions: Q1: Does the consistency loss effectively enhance the performance of various GNN backbones in the graph classification task? Q2: How does the consistency loss influence the rank correlation of graph similarities across GNN layers? Q3: How does the consistency loss influence dataset performance across varying levels of complexity, both in structural intricacy and task difficulty?
5.1 Experiment Setup
Dataset We conduct extensive experiments using the TU Dataset [Morris al., 2020], the Open Graph Benchmark (OGB) [Hu et al., 2020] and Reddit Threads(Reddit-T) dataset [Bause and Kriege, 2022]. The TU Dataset consists of eight graph classification datasets, categorized into three main types: (1) Chem/Bioinformatics datasets, including D&D, NCII, NC1109, and PROTEINS; (2) Social Network datasets, including BIDD-BINARY.IDD--MUU
and COLLAB, where a constant feature value of I was assigned to all vertices due to the absence of vertex features; and (3) Computer Vision dataset, COIL-RAG. The OGB datasets include golg-molhiv, a molecular property prediction datasct used to determine whether molecule inhibits HIV replication. The Reddit- T dataset is
7

---

used for classifying threads from Reddit as either discussions or non-discussions, where users are represented as nodes and replies between them as links.
For the TU dataset and Reddit-T, consistent with prior work [Xinyi and Chen, 2019, Xu et al., 2019], utilize 8:1:1 ratio for training, validation, and testing sets. For the OGB datasets, use the official splits provided. Training stops at the highest validation performance, and test accuracy is taken from the corresponding epoch in each fold. Final results are reported as the mean accuracy (except ogbg-molhiv) and standard deviation over 10 folds. For ogbg-molhiv, we follow the official evaluator and use ROC-AUC as the evaluation metric. Detailed information about these datasets can be found in Appendix C.
Model We use three widely adopted GNN models as baselines: namely, GCN [Kipf and Welling, 2017], GIN [Xu et al., 2019], and GraphSAGE [Hamilton et al., 2017J. We also include two recent GNN models, namely GTransformer [Shi et al., 2021] and GMT [Back et al., 2021]. To ensure a fair comparison, we maintain the same number of layers and layer sizes for both the base models and the models with our proposed consistency loss, ensuring the sharing of the same network architecture. Detailed information about hyperparameter tuning is provided in Appendix D.
5.2 Effectiveness of Consistency Loss
To answer Q1. we present the results for the TU, OGB, and Reddit-T datasets in Table As shown in this table, GNN models with the consistency loss yield significant performance improvements over their base models on different datasets. These findings suggest that the consistency framework is versatile and robust approach for enhancing the predictive capabilities of GNNs in real-world datasets, irrespective of the base model and dataset domain. Notably, the GIN method demonstrates the most significant improvements, achieving enhancements of up to 4.51% % on the D&D dataset, 4.32% on the COLLAB dataset, and 3.70% on the IMDB-B dataset. This improvement can be linked to our empirical observation regarding the weak ability of GIN to preserve consistency across layers. In addition, our method demonstrates satisfactory improvements on datasets with numerous classes (e.g., COIL-RAG) and large-scale datasets (c.g., ogbg-molhiv and Reddit-T), indicating that our approach is both flexible and scalable for handling complex and extensive datasets.
Table 1: Classification performance on the TU, OGB and Reddit-T datasets, with and without the consistency loss. Highlighted cells indicate instances where the base GNN with the consistency loss outperforms the base GNN alone. The reported values are average accuracy for TU datasets and ROC-AUC for the ogbg-molhin dataset, including their standard deviations.
NCII
NC1109
PROTEINS
D&D
IMDB-B 1000
IMDB-M -
COLLAB
COIL-RAG
OGB-HI HIV REDDIT-T
#Graphs
4110
4127
1113
1178
1500
5000
3900
41127
203088
Avg. #nodes
29.87
29.68
39.06
284.32
19.77
13.00
74.49
3.01
25.50
23.93
GCN
73,96 237
74.04
sm
73.24: cme
74.92 2m
75.40
55.07
81.72ma
91.72
72.86
76.00
+ Comiitnncy
75.12
73.25 125
75 sme
78.56+ 12
75.85=
56,27+ux
83.44
93.38=144
73.75
77.12=0m
GIN
76.75
a01
72.97 120
41
70.80: un
52.13
93.33 19.84
71.60
12m
77.50:au
cossiieenyy
79.451 108
77.46 145
74.98 1.5
75
74.50_ sas
$3.46124
84.16198)
94.03
74.57.114
77.64_os
GrihSAGEE
74.40= un
73.17=
74 96 114
76.44 is 73. a3
$1.33a225
78
89.56
77.03
76.67
cassitteccy
78.261
74.10g
76.401
77.501 17s
74.75_ vas 54.27.131
82.1
78.6011
77.57_0m
Grrasformer
75.72=
77. 11
73.33
75.42=11
72.20+sa
53.33=m12
80.36aas
8
76.8
76.75aau
+ Lonsttnnny
76,83-136
75.82+1.9
77.03
76,57=124
73.75
56,53+1.44
80.48
91.67-1aa
76.90
77.14-ue
GMT
75.04
73. 90.00e2
72.70=4a
72,80=21s
79. 00.80s
$4.13-290
80.36e
90.85
74.86=22
72.06=mus
75.52-1m umm
75.20
74.86=2m
73.14
79.60
54.80+14:
82.80
92.00-143
77.19-014
Furthermore, we analyze the complexity and scalability of our method on the TU Dataset, with additional details provided in Appendices E.1 and E.2. Additionally, we demonstrate the method's potential to enhance performance significantly, even with a marginal increase in computational cost, as illustrated in Appendix F.
5.3 Effect of the Consistency Loss on Rank Correlation
To answer Q2, we compare the consistency of graph representations across layers with and without the proposed consistency loss. Specifically, we use the Spearman's 's rank correlation coefficient, a widely accepted method for computing correlation between ranked variables, to quantitatively measure the consistency of graph similarities across layers. For fair comparison, construct
8

---

distance matrix D for all test data at each layer h, where each row D represents the distances from graph 24 all other graphs. We then compute the rank correlation between D and D for each graph Zj.
We average the correlation values for all graphs to obtain the overall correlation for layer h. Then, we compute the mean of these values across lay- ers, enabling a global comparison of relational consistency throughout the model and dataset. All results were averaged over repeated exper- iments with the same training setting.
Spearman correlation was computed for graph representations from consecutive layers the TU datasets, both with and without consistency loss. Values with higher rank correlation are highlighted. The consistency loss can enhance the rank correlation graph similarities.
Table 2:
We present our results on series of datasets from the TU Dataset in Table 2. As shown in the table, evident that the representation space becomes more consistent with our proposed con- sistency loss. For example, a significant enhance- ment is observed for the GIN model. Another notable point is the result for the GCN model on the NCI109 dataset and for the GMT model on the IMDB-B dataset. We find that the cor- relation is already fairly high even without the implementation of Leonsistency, resulting in mini- mal correlation improvements with our method. This phenomenon provides plausible explanation for why our method is not effective in these two cases.
NCII
NCT109
PROTEINS
D&D
IMDB-B
GCN
0.753
0.920
0.584
0.709
0.846
+Cresbaraay
0.859
0.958
0,946
0.896
0.907
GIN
0.666
0.674
0.741
0.721
0.598
0.877
0.821
0,904
0.847
0.816
GraphSAGE
0,903
0,504
0.845
0,741
0.806
0.911
0.709
0.916
0.872
0.933
GTransformer
0.817
0.867
0.865
0.884
0.863
0.883
0.915
0.880
0.917
GMT
0,872
0.887
0,980
0.826
0.893
+ +oenbaiarayy
0.906
0.908
0,983
0.856
0.908
5.4 Study on Task Complexity
To address Q3 and further evaluate the performance of our method across different scenarios, we extended our study by conducting experiments on graph datasets with increasing task and structural complexity.
Increasing Task Complexity We increase the task complexity by expanding the number of classes that the model needs to classify. To assess the effect of increased class complexity on our method's performance, we sampled subsets from the REDDIT-MULLT 5K dataset (Yanardag and Vishwanathan, 2015] with a progressively greater number of classes, which originally consists of five classes. Specifically, we randomly sampled between 2 and 4 classes to construct new datasets from the original dataset and conducted classification tasks using both GCN and GCN with Leonsistency these newly constructed datasets. We report the mean test accuracy over five experiments for each subset, as presented in Table 3.
Table 3: Performance comparison across different subsets and the full set.
Subset1
Subset2
Subset3 (4 classes)
Fullset (5 classes)
(2 classes)
(3 classes)
GCN
79.50
67.13 68.00
50.30 57.15
53.80
GCN+Lonsisscyyy
81.10
57.12
The results demonstrate that the effectiveness of our method remains robust, even as the number of classes increases. In fact, it may provide greater advantages when applied to multi-class classification tasks. This resilience likely stems from our method's focus on identifying relational structures the intermediate representations of GNN models, rather than relying heavily on label information. This approach helps mitigate the impact of potential label noise in the original data. These findings align with the noticeable performance improvements observed in both binary and multi-class classification tasks, as shown in Table 1.
Increasing Structural Complexity We assessed the impact of structural complexity by partitioning the IMDB-B dataset into three subsets with progressively increasing graph densities. Graph density, denoted as d = N(N-IJ: where N is the number of nodes and M is the number of edges in graph
2M

---

G, was used as the criterion for creating these subsets. The dataset was divided into three groups: (small) for graphs with densities below the 33rd percentile, (median) for densities between the 33rd and 67th percentiles, and (large) for graphs with densities above the 67th percentile. We applied both GCN and GCN+ Cesesistency models to these subsets, and the results are summarized Table
Table 4: Performance comparison on IMDB-B datasets of different densities.
IMDB-B (small)
IMDB-B (medium)
IMDB-B (large)
GCN
77.58+4.11
66.25+5.35
67.61 +0.21
GCN+Lconsistens
84.24
69.06+4.00
44.43
The above results show that the GCN model, enhanced with the Lconsistency loss function, consistently outperforms the original version across different structural complexity groups, demonstrating the robustness and effectiveness of the proposed method.
Furthermore, we evaluate the method's ' efficiency under various complexity scenarios, as detailed in the Appendix E.3.
6 Related Work
Graph Distance and Similarity Measuring distances or similarities between graphs a fundamen- tal problem in graph learning. Graph kernels, which define graph similarity, have gained significant attention. Most graph kernels use the R-Convolution framework [Haussler et al., 1999] to compare substructure similarities. A trailblazing kernel by [Kashima et al., 2003] used node and edge attributes to generate label sequences through a random walk. The WL-subtree kernel [Shervashidze et al., 2011] generates graph-level features by summing node representation contributions. Recent works align matching substructures between graphs. For instance, Kriege et al. [2016] proposed a discrete optimal assignment kernel based on vertex kernels from WL labels. Togninalli et al. [2019] extended this to include fractional assignments using the Wasserstein distance. Additionally, measuring graph distances is also prevalent problem. Vayer et al. [2019] combined the Wasserstein and Gromov- Wasserstein distances [Villani and Society, 2003, Mémoli, 201 1]. Chen et al. [2022] proposed a polynomial-time WL distance for labeled Markov chains, treating labeled graphs special case.
Bridging Graph Kernels and GNNs Many studies have explored the connection between graph kernels and GNNs, attempting to integrate them into a unified framework. Certain approaches focus on leveraging GNN architecture to design novel kernels. For instance, Mairal al. [2014] presents neural network architectures that learn graph representations within the Reproducing Kernel Hilbert Space (RKHS) of graph kernels. Similarly, Du al. [2019] proposed graph kernel equivalent to infinitely wide GNNs, which can be trained using gradient descent. Conversely, other studies have incorporated kernel methods directly into GNNs. For example, Nikolentzos and Vazirgiannis [2020] utilized graph kernels as convolutional filters within GNN architectures. Additionally, Lee et al. [2024] proposes a novel Kernel Convolution Network that employs the random walk kernel as the core mechanism for learning descriptive graph features. Instead of applying specific kernel patterns as mentioned in previous work, we introduce a general method for GNNs to capture consistent similarity relationships, thereby enhancing classification performance.
7 Conclusion
In this paper, we study a class of graph kernels and introduce the concept of the consistency property for graph classification tasks. We theoretically prove that this property leads to more structure- representation space for classification using kernel methods. Based on this analysis, we extend this principle to enhance GNN models. We propose a novel, model-agnostic consistency learning framework for GNNs that enables them to capture relational structures in the graph representation space. Experiments show that our proposed method universally enhances the performance of backbone networks on graph classification benchmarks, providing new insights into bridging the gap between traditional keree methods and GNN models.
10

---

References
Jinheon Back, Minki Kang, and Sung Ju Hwang, Accurate learning of graph representations with graph multiset pooling. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL
net
(tormm?id=JHqqXeee
Franka Bause and Nils Morten Kriege. Gradual weisfeiler-leman: Slow and steady wins the race. In Bastian Rieck and Razvan Pascanu, editors, Learning on Graphs Conference, LoG 2022, 9-12 December 2022, Viriual Event, volume 198 of Proceedings of Machine Learning Research, page 20. PMLR, 2022. URL htw.h:ttp///tt httttp::/ppoceeeinggg mlr. wrw.spreeeeee.......... wwtp///asseee/eeee .htll.
Karsten M. Borgwardt and Hans-Peter Kriegel. Shortest-path kemels graphs. In Proceedings of the Sth IEEE International Conference on Data Mining (ICDM 2005). 27-30 November 2005, Houston, Texas, USA, pages 74-81. IEEE Computer Society, 2005. doi: D0.1109/CDM22000..0 132. URL battps:///ol org/ 10. 1109/ IID//ICCM...MM 2005.132.
Christopher J. C. Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Gregory N. Hullender. Learning to rank using gradient descent. In Luc De Raedt and Stefan Wrobel, editors, Machine Learning, Proceedings of the Twenty-Second International Conference (ICML 2005), Bonn, Germany, August 7-11, 2005, volume 119 of ACM International URL
Conference Proceeding Series, pages 89-96. ACM, 2005. doi:
attps://doi.org 10.
Samantha Chen, Sunhyuk Lim, Facundo Mémoli, Zhengchao Wan, and Yusu Wang. Weisfeiler- lehman meets gromov wenso--wasserttein. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 3371 1371-3416. PMLR, 2022. URL https: / http/ppeceeennss// .mw.mngs.........mmm.m.m.....mmm mlr.pres pres s/v162/ chen22o. //v16//chen22o html.
Simon S. Du, Kangcheng Hou, Ruslan Salakhutdinov, Barnabás Póczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'Alché-Bur Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 5724-5734, 2019, URL https / /ttp///peocecee..ee/ee//////. www.eeediinnnn.eeis...... cctpppp//ccppppp//01111 1a9a5b92d -atp:s2dd--bbttaacco Abstract htmll.
9/hash/ h/haahh/63fd3c554444448
Justin Gilmer, Samuel Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Teh, editors. Proceedings of the 34th International Conference on Machine Leurning, ICML. 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1263-1272. PMLR, 2017. URL. http: http:///ooceedddee mlr. wal...pees/vv0// / gilmer 17a. html.
William L. Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning large graphs. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1024-1034, 2017. URL https:::pppoceeettttttttt www.diinnniiin.nn...eeeee.ee..e. neurips. cc/ ec/paper/20 2017 22/7//0077/////// /hwsh/ 5atgabaee33aacccs5aaaaaaaaaaaaea
Abstract. html.
David Haussler al. Convolution kernels on discrete structures. Technical report, Citeseer, 1999.
Weihua Hu, Matthias Fey, Marinka Zitiik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florimg Balcan, and Hsuan-TKe -ien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL neurips. catss.ccpappppe httpe///222//2////eee 1tw.166006111115552222227785555 fc84fd0- Aero--bbttrtt.... html.

---

Zheng Huang, Qihui Yang, Dawei Zhou, and Yujun Yan. Enhancing size generalization in graph neural networks through disentangled representation learning. Forty-first International Conference on Machine Learning. 2024.
Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized kernels between labeled graphs. In Tom Fawcett and Nina Mishra, editors. Machine Learning. Proceedings of the Twentieth International Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA, pages 321-328. AAAI Press, 2003, URL http: htttp://www.. aaai org/Library httpL//brrr//////00///3/ ICW.L//03/////////// -44 php.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL htttps://ppeet openrevi ew net/ net/forummiieeeeeeeee
Nils M. Kriege, Lierre-Louis Giscard, and Richard C. Wilson. On valid optimal assignment kernels and applications to graph classification. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5- 10, 2016, Barcelona, Spain, pages 1615-1623, 2016. URL. https: httts::t:/:::eeeeeeeee http:///eoocoeeeeeeeeeee wechiinnnnnnnuuggee neurips. cc/paper html.
Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. A survey graph kernels. Appl. Netw, Sci., 5(1);,, 2020. doi: 00.1077/41109--09-9000 URL hattps:///oi. 1trg/10.1000 341109-019-0195-3
Meng- CenngCChichla Lee, Lingxiao Zhao, and Leman Akoglu. Descriptive kernel convolution network with improved random walk kernel. In Tat-Seng Chua, Chong- Wah Ngo. Ravi Kumar, Hady W. Lauw, and Roy Ka-Wei Lee, editors, Proceedings of the ACM on Web Conference 2024, WWW 2024, Singapore, May 13-17, 2024, pages 457-468 ACM, 2024. doi: 10.1445/558933436655005 URL https://doi. org/10 10.
Gaotang Li, Marlena Duda, Xiang Zhang, Danai Koutra, and Yujun Yan. Interpretable sparsification of brain graphs: Better practices and effective designs for graph neural networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1223-1234, 2023a.
Gaotang Li, Danai Koutra, and Yujun Yan. Size generalization of graph neural networks on biological data: Insights and practices from the spectral perspective. arXiv preprint arXiv:2305. /56/1, 2023b.
Lu Lin, Jinghui Chen, and Hongning Wang. Spectral augmentation for self-supervised learning on graphs. In The Eleventh International Conference on Learning Representaatioss, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL htttp:://ooenrevie..netttt idd= DjzBCrMBJ_p.
Shengchao Liu, Hanchen Wang, Weiyang Liu, Joan Lasenby, Hongyu Guo, and Jian Tang. Pre- training molecular graph representation with 3d geometry. The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
URL htttps://operreeee
net wtt.:e//ooooommoiiueeeeeeeeee
Julien Mairal, Piotr Koniusz, Zaïd Harchaoui, and Cordelia Schmid. Convolutional kernel networks. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 2627-2635, 2014. URL hww.h:tttt:/ttttmtt htttt::::p/pproeednng/ee/e 2c82e7 2c82e7712500c50000322222222 (200:000000000022999000000--1a10
www.eeiinnnnnnnnniiieeeeeeeeeeee wenriiuipp... wttpuripp.ccceeeeeeeeeeeeeeeeeee wc/paper///aeeeece///eeeeeeeeeee 1aaper/2044 hahaahhhhcccc26 html.
Facundo Mémoli. Gromov-wasserstein distances and the metric approach to object matching. Found. Comput. Math., 11(4):417-477, 2011. doi: 00.1007/810008-00 0119993-5.. URL https:
//doi.org/10 /////.1.000/// 000000/s12000001--90000
Mehryar Mohri. Foundations of machine learning, 2018.
12

---

Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. CoRR. abs/2007.0866, 2020. URL httph::t/ssaaa /tttps://arxiv... org/ wwrg/abs/2007.0000 2ww.2000770866..... 08663.
Giannis Nikolentzos and Michalis Vazirgiannis. Random walk graph neural networks. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Floring Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https:/ http:////ooeeddeegeee meg.eediiisnnnnnpsss...... cc/ cwwpaper/eaaeeepeeceeeeeeeeeeeee paaper/020// http//22220//hhaee hww.haaahaa///a//aeaaaaaaa cTt.e/aa277227711888888 1885308777 a97 wwstract..... chtsstrrct..tml...
Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph kemels: A survey. J. Artif. Intell. Res., 72:943-1027, 2021. doi: 1..3//AIR.111222.. URL attpss///oli http:///ooooog////// 0rg/10.1/ 161
3/ 3/jair.1. 13225.
Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M. Borgwardt. Efficient graphlet kernels for large graph comparison. In David A. Van Dyk and Max Welling, editors, Proceedings of the Twelfth International Conference on Artificial Intelligence and Statis- lics, AISTATS 2009, Clearwater Beach, Florida, USA, April 16-18, 2009, volume 5 of JMLR Proceedings, pages 488-495. JMLR.org, 2009. URL http:/ http::////cceedg....m.mm mlr. www.mml..........eee press/v5/s
hervashidze09a. .html.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lehmar graph kernels. J. Mach. Learn. Res., 12:2539 25611, 2011. doi: 10.5555/1953048.27777 20781187. URL https: //dl./dl/.// acm. org/ org/doi/// do0/ 5555 / 1953048. 2078187.
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, I/CA/ 2021, Virtual Event Montreal, Canada, 19-27 August 2021, pages 1548-1554, ijcai.org, 2021. doi: 00.24663/JCCA..222/221. URL https: //to:///ooooooo org/oo////0 10. 24923/2994//// 2222//2/111...22/111.11
2021/214.
Giannis Siglidis. Giannis Nikolentzos, Stratis Limnios, Christos Giatsidis, Konstantinos Skianis, and Michalis Vazirgiannis. Grakel: A graph kernel library in python. J. Mach. Learn. Res., 21:
54:1-54:5, 2020. URL https://wwwt jmlr. org/oopergaeee...... papers/ V21/v1-1/2/1 370. hhmll.
Mattco Togninalli, M. Elisabetta Ghisu, Felipe Llinares- López, Bastian Rieck, and Karsten M. Borgwardt. Wasserstein weisfeiler-lehman graph kernels. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché- Buc, Emily B. Fox, and Roman Gamett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 6436-6446. 2019, URL httptp:://ppoceeeiieie wwweeediinnnnnnnnnneeeeeeeeeeeee nwwrips....... cctpaper//019//////eeecc http///h////te/////22e//// 908794430511f445 Abstract .tml.
Titouan Vayer, Nicolas Courty, Romain Tavenard, Laetitia Chapel, and Rémi Flamary. Optimal transport for structured data with application on graphs. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 Proceedings of Machine Learning Research, pages 6275-6284. PMLR, 2019, URL http:///// / ppwp/edincc......////// mlr, .press/ v97/titouan19a, html.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver; BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https: htttps://operrevier
C. Villani and American Mathematical Society. Topics in Optimal Transportation. Graduate studies in mathematics. American Mathematical Society, 2003. ISBN 9781470418045. URL https://booke howp:://ooooooooooe...o.o google..gg..ooooooooo.. woon/books?iddkyy>>
Haohui Wang, Yuzhen Mao, Yujun Yan, Yaoqing Yang. Jianhui Sun, Kevin Choi, Balaji Veeramani, Alison Hu, Edward Bowen, Tyler Cody, et al. Evolunet: Advancing dynamic non-iid transfer learning graphs. In Forty-first International Conference Machine Learning, 2024.
13

---

Boris Weisfeiler and AA Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction. Teeebno--Tchniiheskkyya Informatsia, 2(9):12-16, 1968.
Zhang Xinyi and Lihui Chen, Capsule graph neural network. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https: pettps://openevviiee
wett/forummidddByBBBBBBe.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https: htthttss:///ppmmeeet http://ppppneeieeeeeeeeeeee ryGs6iA5Km.
Minkai Xu, Alexander S. Powers, Ron O. Dror, Stefano Ermon, and Jure Leskovec. Geometric latent diffusion models for 3d molecule generation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt. Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning. ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 38592-38610. PMLR, 2023. URL https: //proceedings. mlr. press/v202. xw23n. html.
Yujun Yan, Jiong Zhu, Marlena Duda, Eric Solarz, Chandra Sripada, and Danai Koutra. Groupinn: Grouping- based interpretable neural network for classification limited, noisy brain data. In Proceedings of the 25th ACM SIGKDD international conference knowledge discovery & data mining, pages 772-782, 2019.
Pinar Yanardag and S. V. N. Vishwanathan. Deep graph kernels. In Longbing Cao, Chengqi Zhang, Thorsten Joachims, Geoffrey I. Webb, Dragos D. Margineantu, and Graham Williams, editors, Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015, pages 1365-1374. ACM, 2015. doi: 10.1 141111282258.27882228
URL https: doi. org/ 10. 1145/ 22844//2772222.22 2783417.
Rex Ying. Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. Yike Guo and Faisal Farooq, editors, Proceedings of the 24th ACM SIGKDD International Conference
Knowledge
Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pages 974-983. ACM, 2018. doi: 10. 11444///19999321999999
URL https: //ooi. org/ /0////1...0 / 41445///291999 0211119..999999999 3219890.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. htRps: http:p:://pprceeeeeeee http:///occceeeeeeeeeee/e/ee www.eeeiiinnnnnuninineeeeeeeeeee aateeaaa-ddd--btractccce html.
Zhen Zhang, Mianzhi Wang. Yijian Xiang, Yan Huang, and Arye Nehorai. Retgk: Graph kernels based on return probabilities of random walks. In Samy Bengio, Hanna M. Wallach. Hugo Larochelle, Kristen Grauman, Nicold
and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 3968 3978, 2018 URL https: httttt::/tttceeeeeeeeeeeee http///proeeeenn..... wtwpeeeeeddnng..nuruiiseeee www.nnurii....m cc wttps/tr.ppppepeeeeeeeeeeeeeecea http://0000020211111111111111110 1ha84c708c1-Abstraae html.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph Contrastive Learning with Adaptive Augmentation. In Proceedings of The Web Conference 2021, WWW '21, pages New York, NY, USA, April 2021. Association for Computing Machinery. ISBN 9781450370233. doi: (0.1145/3423881.44454 3444880.. URL https: /ttpps:/ddie //oii org/10. 100 1145/3442388 3449802.
14

---

A Proof of Theorem 3.4
A.1 Learning Correct Similarity Order with Iterative Kernels
In this section, we first prove that the iterative kernel with bounded feature mapping is capable of learning the pairwise similarity order given sufficient training data, as shown by the PAC-learning framework. We consider a dataset consisting of instances I E X. where is the input space. The dataset denoted as X {21, T2,,............. ,n, We employ a kernel function K X X X I with an associated feature mapping & X Hig such that ((x,)) v) Reproducing Kernel Hilbert Space (RKHS) associated with K, and (t. +)xx denotes the inner product in Hk. We assume that the feature mappings are bounded, i.e., [| Hx. S R, Ve E x for some R>
( Here, Hx is the
Using this setup, we focus on an arbitrary fixed data point 2; and compute its similarity with other data points z + i) using the kernel function:
S == K (2i, = (6 (x:) (rz))
Thus, define the function f as f (az) (w, (x2,))= where o (z;). Since o (x.) and ll (z R. follows that [|w]] Htx I So the function representing the similarity between Iz and any other point 2j can be formulated as:
f (z²) = (o (z.) (z,)) Hx K (x,,))) = Siy-
Since we are dealing with ranking problem, we use the hinge loss function for pairs (æ,, (j k + :
Cninge (f. Iz, 2x) max (0, sjx (xz) (zx))),
(3)
where 5j* sign (ʃ" (xry) - l (dr=)), and f" represents the ground-truth ranking function.
Thus, the expected loss over all pairs is given by:
U(})= = (x)) I'ningg (S, xx)]
(4)
and the empirical loss over the sample given by:
2
i() (n 1)(n 2)
Cnngg (J,z)
(5)
jEc
since there are [m-1)nn-2 pairs among the n - 1 data points excluding I,, To assess how well the learned function / generalizes test data, we derive a generalization bound using Rademacher complexity. We define the function class for pairs by:
Fpair (f (I)) = (xx) - (xx)).
(6)
which represents the similarity difference between 2, and ax given the reference graph dt- Given that f(x) = (w, ((x)) with |||||| = and [b(())] $ R. we can bound f (zy, by:
If ax)) = 1f (zy) f (rx) | s If (4,)) + 1f (xx) < 2R².
since [f(x:)] = (w. (xx)) < |||||| ||)(z)]| < R R = R²
Given f (I. .x)) takes values the range | 2R² 2R²) Therefore, following the PAC-learning
framework in [Mohri, 2018), derive the following generalization bound. For any 8 0, with probability at least 1 - over a sample S of size m drawn, the following holds for all f E Fpair
ln(1/6)
L(f) < i(f) + 29Rg (Fpair) ) + MV
(8)
2m
where:
RRm (Faarr) ) is the empirical Rademacher complexity of Fpair.
15

---

M = 1 + 2R is an upper bound on the hinge loss function Inane
(n-1)(n-2) the number of pairs. 771 2
0 is the confidence level.
It is observed that as m increases, the term we proceed by proving that the Rademacher complexity is bounded and decreases as m increases.
In(1/8] decreases rate proportional to v 1/m, Next,
2m
Theorem A.1 Assuming [| Ro all æ E X, the empirical Rademacher complexity of the function class F pair can be bounded as:
2
(Fs((poo) S
Vm
for Proof Based the definition of Rademacher complexity, for function class Fpalr with sample
size m, the complexity Rs (Fsir) is defined as:
Σ oif (Z),, and)
Rg (F ) = Eg sup
(10)
m
where a = (ai..... 0m) are independent Rademacher variables (i.e., each os takes the value + I or -1 with equal probability), and {1 TK; ) are pairs sumpled from the data.
We can express Rs (F pair)) as:
W, Σ oi (1rg) & (caaa)
m
Rg (F
E
sup ||
(11)
m
Applying the Cauchy-Schwarz inequality:
(w. Hix S ||lll 1111 S R|
(12)
have:
Rg (Faate S - R Eo Σ o (6(x))))) & (wwn))
1
(13)
171
Using Jensen's 's inequality in the form B[l|X|||
( [|I 1/2
we obtain:
1/2
R m7
(F pair
E
Σ oh (6 (xxz.) (xxx))
(14)
MK
Since ay are independent Rademacher variables, we have lBo [o
Therefore:
m
m
E.
Σ
o. (d(z)) -((())))((())))
Eg [o
1 (xx & 11
(15)
( o 11
Given that [( $ R, we have:
1| (1x,), - (IxI)) < (2R)²= - 4R2.
(16)
Therefore,
m
E
- -2 (Tx)))
a (0(x,,
S Vm 416 2Rym.
(17)
16

---

Thus
Rs (F ) R. 12.2R// 2R vm
1 m
2R
(18)
m
mm
Therefore, the empirical Rademacher complexity decreases with m.
Thus, consider Equation
The term
In(1/8]
decreases proportionally to 1/ 1/vm.
2m
Empirical Rademacher complexity Mt (F
S
2R²
also decreases proportionally to vm
1//m.
Therefore, the generalization gap between L(f) and L(f) decreases as m increases, demonstrating that the kemel-based ranking function is PAC-leamable.
A.2 Linking Two Key Properties to Generalizability in Binary Classification
Building on the setup and conclusions from the previous section, we establish that the kernel can learn the correct ranking with sufficient training data. Here, we investigate how, once the correct ranking achieved, an iterative kernel with monotonic decrease and order consistency properties ensures decreasing error rate for test set graphs as iterations progress in binary classification tasks.
To formalize this, we define a probability space over the whole graph space where addition and scalar multiplication are defined. Let Ω be the set of all possible data points (graphs). Each data point Ir E Ω represents a possible outcome, and the event of observing 9i the singleton set {g₁} Ω. By considering all subsets of Ω we construct an event space F. Assuming the existence of an underlying probability distribution over these outcomes, we obtain the probability space (9, F, P). Using this framework, let μlz and My represent the unknown mean graph in class and class 2, respectively. Let (x E (0, 1] represent the ground-truth kernel function for pairs of graphs.
Without loss of generality, we analyze the eтror rate for graphs belonging to class 1; the error rate for class 2 can be derived similar manner. We define two random variables associated with the ground-truth kernel: Sy (g .t) and Sy ggge (py: 2), where x is randomly sampled instance from class 1. The terms s (x) and sy (xx denote specifie realizations of S. and sy. respectively, for given realization of the graph x belonging to class 1. Since s, O implies that there exists graph from class 1 that is completely different from Mas which is counterintuitive, we assume that the probability density function p(u), u E [0, 11. of neighborhood of 0:
s has the following asymptotic property on the right
lim p(u) C,
(19)
12 +++
where constant C' satisfies that 0 < C < +00. Lets! represent the estimated realizations of Sy and Sy at iteration respectively, for given graph realization x. 5 and z2 are estimates for μą and Hy. respectively. We assume that f and (() are obtained through operations on the training graphs, where these operations are closed in the graph space. Due to the capability of the iterative kernels, we further assume that as the iteration
( x) ( k
+ 20, the sequences {p! (r. ( (. and (K() (, He converge Has My and Kgg, respectively. We assume that the convergence rate of (K(() [=1
is much slower than the t.., Furthermore, every function in the series of convergence rate of [n1 (::) to and (n (+)
function {K (+) (., - is continuous.
Denote the training data for class and class {a1, T2, .n} C Ω and {v1, ... ym Ω. respectively. Since the learned kernels (+) preserve the similarity order, we can assume, without loss of generality, the following empirical ordering of the training graphs for the kernel at the i-th iteration:
( (II) < 5 (x22
5 (xx)
(20)
17

---

In this setting, for an arbitrary test graph sampled from the graph space, the decision boundary of the kernel learned during the i-th iteration is defined as follows:
Vg: if L (g)
(g) then g is classified as class 1
(21)
( y (g) then g is classified as class 2 satisfies: 5 (Ix) < 3 (Ix)). while 55 (Ix+1) > 5i, (I or a given iteration i, which means Ta is the misclassified training graph in class I closest to the decision boundary. If the training error is O, we take zo y1. We note that the integer k is independent of the iteration due to the consistency principle. Next, demonstrate this using the following lemma.
Vg : if (1) (g)
We assume that S (g) and sy (g). as well as s, (g) and (g), are not equal for any of the training data points. Next, we analyze the misclassification rate for graphs in class 1. Let the integer
Lemma A.2 For any sufficiently large iteration number i, there exists a fixed index k such that 5/ (Ix) < (0) (Iw). while 5 (Iu+1) By (Ix+1).
(8)
Proof 2 Since the series {eo y:000 converges to pas it satisfies Cauchy's 's convergence criterion. Specifically, v8 > 0, EN2 O. such that when >> N1.
(n(((t) - -- < 6.
(22)
Since we have assumed that (() are continuous: Ve > 0, 36 > 0. 3N2 > 0, such that for any
in class 1, vi > N2 and |a 11 - ) < 8, we have:
,x) (+++1) (p! (1) ,0) < E.
(23)
Based on Equation 23, we have:
(xx)) (ox)
(x)) - (Xt) mx) + (al ax)) - -((tt)
+ k(+t) .x) - (zf .x))
(24)
(x)+ - -K m2)1 BB (xx) (af mz)l + (xl+) ,xx) (x( mx))
Since the consistency principle holds, K ((+t)) (7()) IR) ((+t)) (nll IK) and 5/60 (0x) 5 (4) (xx)
have the same sign. If (Ix) - sy (Ix) < O, then K (z+ xx) k(++1) (ay (1) xxh) < 0. For
(af _ax) xx)) (a mx))
sufficiently large N, select an 0 such that < min NY Given our assumption that no training data point By lies precisely on the decision boundary, such an is guaranteed to exist. Consequently, Equation 24 simplifies to:
5 5(1+1) (xxx) - (xx) < 2c 22cKK* (( (p()) xxx - (K(+1) (p. < O.
(25)
Thus, (xx) 1) (xx)) have the same sign as the same conclusion can be derived in a similar manner. Since the number of training samples is finite, we can find sufficiently large iteration such that Equation 25 holds for all I after that iteration.
S (æx) 5/ (zx). If (xx) - (0)
By (xx) 0.
Thus, some point between si. (xx) and $ (#x41) is the decision boundary learned at the i-th iteration.
Based on our assumption that the convergence rate of (K(0) (t-))t is much slower than the convergence rate of (Tle (1) decreasing.
(t and (pl) (, a (mx) is asymptotically monotonically
50 (ax) > 5 ((++) (Ix), (xx)) when i - 400
(26)
Thus,
5f + Kgt (x)) + when + too $ (1x) > Kyt (Ha, Ix)
(27)
Thus, Vo E class 1, the probability of misclassifying x is given by: PP (Ix) < ByelHer Specifically, we have:
(b)))
Psss < (g)( S Ip(s, < (xn)
(28)
In the following theorem, we show that the probability of misclassifying any graph from class can be bounded using Markov's 's inequality.
18

---

Theorem A.3 If the iterative kernel decreases monotonically and preserves the similarity order, the probability of misclassifying a graph a x from class 1 has an upper bound that decreases monotonically as the number of iterations increases.
Proof 3 To upper bound the error rate, we begin by applying the transformation 1 1 to the original random variable Sz. The expectation of this transformed variable is:
f J
[_ -
-
p(u) du
(29)
p(u) du 1
Since u = 0 is singular point, we reformulate the improper integral as:
f p(u -1
lim 4--00
Here, since lim, p(w) = C. the limit exists and thus the given integral converges, ensuring the existence of the expectation. With this result, we can apply Markov's inequality the transformed random variable
1. For any nonnegative we have:
IP
1)
3
(30)
Thus
1
P S4
<
<
(31)
1+a
Let (mn) 1. Reserring Equation 28, we have:
1
P(s, < (gr & (822 S (xx))
<
(32)
(Irw)
Since 510h (IK) decreases monotonically and E (1. -1) is a constant, it follows that P(s, <
gt (Mz, [k)} has a monotonically decreasing upper bound.
B Theoretical Verification with WL-based Kernels
B.1 Proof of Theorem 3.5
Following Equation 2.4, the normalized WL-subtree kernel after h iterations can be expressed as:
Elm (o('" ow (G'))
(h) subtree (9,9") Eie (6(1) si (9))) EL (b(1"(())) ai (g)))
Next, we show by counterexample that the WL-subtree kernel may not preserve relational structure. For example, consider two graphs, G and G', in the h-th iteration. The color (label) set of the nodes in these graphs denoted as {Ca, Cb, ... Graph contains 200 nodes labeled C. and nodes labeled Cg, whereas graph G' contains 4 nodes labeled C, and 200 nodes labeled C.. The similarity computed using the vectors (W)( [200, 4] and Φ (vi (G') [4, 200). Consequently, the (h resulting similarity "'o_surereee 0.0400.
In the next iteration, for graph G, assume that half of the nodes currently labeled C. are relabeled to Co, while the other half are relabeled to Ca. Additionally, all nodes labeled C₁ are relabeled to
19

---

Ce. As a result, the updated histogram vector for & becomes & (1+++ (G)) [100, 100, 4]. Similarly, in graph g', half of the nodes labeled C. are relabeled to C. and the remaining half to Ca. with all nodes labeled Cs relabeled to Ce. resulting in histogram vector of (v=+11 (g)) [2, 200].
Here, the normalized similarity [ _ubtree is 0.0404, which exceeds [(0)) "wi_subrree'
This situation violates the principle of monotonic decrease, indicating that the WL-subtree kernel does not exhibit monotonicity a phenomenon frequently observed in real-world datasets.
B.2 Proof of Theorem 3.6
B.2.1 Monotonic Decrease in WLOA Kernel
The WLOA kernel after h iterations can be computed as follows:
K (b) WLOA (G.9')
histmin (o( ((1)
where wii) is a monotonically increasing function. The normalized kernel is given by:
(WLLAAG.9))
(N) (.
K (h) AWLLA(G.9))
(h) (
At any iteration the expression histmin (((( w(1) equals w()))) Conse- quently, for the h-th iteration, this implies:
h Σ (1)
K W WWLOOG (9.9)
Thus, the normalized kernel value for the graph pair (G, g') can be expressed as:
K L 9",
(2(h) (9,99
VIVI Σ 1= w(i)
Given this, the difference between the kernel value at the h-tth iteration, K iteration, ((h++) K can be expressed as follows:
KLLOA- and the (h + 1)-th
(A)
WLOa WL. (G.9') - (h+1)
WIOA (G,9")
K 1..LOAA9..17 (')
K 1h++))
VIVIA>" Eh (i) VIVIE> Eh=1 (i)
(b)
(WLTAA9,9))
( + Ahistinn(o(uhhee ((b (G)) (C) 1)1
V
Σ [l) ((i)
Σ w(i)
D=
Considering the hierarchical structure of the refinement processes, one can deduce the following
inequality:
(istmin(o(s// (G)). & (istmin(o(v" o( (0 (g'))) < ... histmin (G)), o( (G)))
Thus, for the kernel the (h 1)-th iteration, it follows that:
A histmin (0 (I)), (G)) w(1)
K (9.9")
(ttmin(o(v*+(()))) 4 (())))
Σh w(i)
> h
w(i)
20

---

Given this inequality, we get
1
(A)
LOAA
kw, (9, + w(h++)) kk(k)
[K(b]
Σ w(i)
WLOA (9,99
D
w(i)
1+1 w(it)
1
WLOA (9,9")
(N)
(()) El (1.10 En w(1)
w(++1)
WLOA (9.9")
VDVI>>
Σ w(i)
Σhit1 w(1)
(33)
1
K (b)
WLOA (9,9")
(1 wi) w(i) + with +11
V
Σ wi)
Einw(i) + whh + +1)
0
Therefore, we get D 2 0. The value of Equation 33 is non-negative, indicating that WLOA is monotonically decreasing.
B.2.2 Order Consistency in WLOA Kernel
Assume two graph pairs satisfy the following relation:
K (b) W LOA A (G. 2 EWLOA (9.9")
(h)
The normalized WLOA kernel for graph pair (G,g") iteration h can be expressed as:
((h+1)
WLLA (9,9")
E w(1)
(h+1)) WLOA (9,
(h+1)
KOL (9.g")
V DIIVEE E w(i)
h+1
E (i)
VIIIEE
K (h)
LLOA is monotonically increasing with the iteration number h, it follows from: (h++1 whh + 1). Thus, we have:
KIIOA
KWLoo LOA + histmin ((()*+(())
(9
[(++1)
(1)
KOWLOA (G,9")
(b)
w(i)
VIVIV' E wii)
1= w())
KWLOA (W.
(9.9")
i=1 w(i)
h+l
VIVI Σt w(i)
1 wii)
((th)
WwLL (9.
wii)
Given the monotonic decrease property of (2(h)) WLOA (9, g"),
wwe have:
(2(h1) (9.9") <
(h)
WLLA (G,9")
Thus, we can conclude:
Σ i= w(i) (h+1)
((++))
WOL (g,g")
1= w(i)
h+1
1 w(h + 1)
E (9.
Σh+l w(i)
When w(i 1, lim w(h+1) Kc (b+1)
h+1 lim (4+2
lim 400 F+2
2 = 0. Therefore,
Σm
KWLLA (G,g") > KWLOA (G, g") when h 00.
(h+1)
21

---

Table Dataset statisties.
Dataset
Task Description
# Class
# Size
Ave.Nodes Ave. Node Label.
ogbg-molhiy Molecular property prediction
41127
25.5
54.1
PROTEINS
Enzyme classification
1113
39.06
72.82
D&D
Enzyme classification
1178
284.32
715.66
NCI1
Molecular classification
2
4110
29.87
32.30
NC1109
Molecular classification
4127
29.68
32.13
IMDB-B
Movie venue categorization
2
1000
19.77
96.53
IMDB-M
Movie venue categorization
1500
13.00
65.94
COLLAB
Collaboration classification
5000
74.49
2457.78
COIL-RAG
Computer Vision
100
3900
3.01
3.02
Reddit-T
Reddit Thread Classification
203088
23.93
24.99
C Dataset
In this section, we provide the statistics of the datasets used, as shown in Table 5.
D Detailed Set-Up
TU Dataset We restrict the hyperparameters and ensure the same architecture is used for both the base and enhanced models on the same dataset for a fair comparison. Specifically, we fixed the hidden size 32, the number of layers 3, and used global mean pooling layer to generate the graph representations. The Adam optimizer was used for optimization. During the training process, we tuned both the base and enhanced models with the same search ranges: batch size (64, 128), dropout rate {0, 0.3) and learning rate (0.0001, 0,001, 0.01). The only additional parameter for the enhanced model is the regularization term, which ranges from (0.1, 0.5, 1, 10).
OGB Considering the complexity of the OGB dataset, we slightly expand the hyperparameter search range. Initially, we train the model with consistency loss, exploring hidden sizes [32, 64, 128, 256], batch sizes {64, 128, 256), and the number of layers (3, 4], while keeping other parameters consistent with our experiments on the TU dataset. Subsequently, we fix the hidden size and the number of layers ensure an identical network structure. We then repeat the parameter search process and employ the optimal settings for testing on the base model. All experiments on the OGB dataset are repeated times to calculate the mean and standard deviation.
Reddit-T Given that the Reddit-T and OGB datasets are of comparable size, we employ similar experimental settings for training models on these datasets. The architecture is kept fixed, and search for optimal hyperparameters for both the base model and the models incorporating consistency loss. Each model is trained and evaluated over 5 independent runs, with the mean and standard deviation the results recorded performance comparison.
E
Complexity & Scalability
E.1
Time Complexity
We present the time complexity analysis for our proposed consistency loss. The loss computation involves the computation of pairwise similarities of graphs in a batch, resulting in a computation complexity of O (batchsize batchsize-1 Obbatchsize*). Given that there are datasetsize batches in baighsize
2 each training epoch and that the similarities are computed between consecutive layers, the total
22

---

complexity is:
datasetsize
O( loss = 0 batchsize x layernum - 1)
batchsize
= O datasetsize x batchsize x layernum ).
This analysis shows that the time required compute consistency loss scales linearly with dataset size, batch size, and the number of layers. It is important to note that the training time for baseline models also scales linearly with dataset size.
Since batch size and the number of layers are generally small compared dataset size, our ex- periments primarily focus on how dataset size
Cirandomme
GMT GCN GIN
affects training time. We evaluate the training
time of several Grransformer, and GMT enhanced with
GIN, GraphSAGE,
Trining Thnek
GraphSAGE
our consistency loss. This evaluation is conducted on different subsets of the ogbg-molhiv dataset, with subset sizes adjusted by varying the sampling rates. The training times, measured in seconds, are presented in Figure 3 As shown, our find- ings confirm that training time increases linearly with dataset size, indicating that our method main- tains training efficiency comparable baselines without adding significant time burdens.
3000
10030
19000
20000
25003
30000
30000
40920
Dataset
Figure 3: Training Cost Escalates Linearly with Dataset Size Increase
Furthermore, empirically measure the training time for both the baseline models and our proposed methods. Each model comprises three layers and is trained on the ogbg-molhiv dataset (40,000+ graphs) for 100 epochs. We calculate the average training time per epoch in seconds and present the results in Table 6, showing that while the inclusion of the consistency loss slightly increases the training time, the impact is minimal.
Table 6: Average training time per epoch for different models on the ogbg-molhiv dataset, measured in seconds.
GMT
GTransformer
GIN
GCN
GraphSAGE
GCN
8.380
4.937
4.318
4.221
3.952
GCN+ Consisenyy
8.861
6.358
5.529
5,382
5.252
E.2
Space Complexity
Next, we present the space complexity analysis for our consistency loss. At each iteration, the loss function requires storing two pairwise similarity matrices corresponding two consecutive layers, which is given by:
0( loss) ) = (batchsizze))
Since use stochastic gradient descent, similarity matrices are not retained for the next iteration. The consistency loss requires significantly less space than node embeddings, making the additional space requirement minimal. Table shows the peak memory usage megabytes (MB) for different models when training on the moogyy dataset, illustrating that the space costs are negligible.
Table 7: Peak memory usage for different models the ogbg-molhiv dataset, measured in megabytes.
GMT
GTransformer
GIN
GCN
GraphSAGE
GCN
1334.0
1267.8
1291.3
1274.2
1288.4
GCN
1370.0
1330.6
1338.9
1320.1
1321.3
Cost Increase (%)
2.70
4.96
3.68
3.60
2.55
23

---

E.3 Efficiency on Different Task and Structural Complexities
Task Complexity We measured the runtime the models on different subsets to evaluate how task complexity, in terms of the number of classes, influences the efficiency of the proposed method. The results are presented in Table 8. As demonstrated, the additional computational time remains minimal even with increasing number of classes, suggesting that the method scales effectively with growing class complexity.
Table 8: Average training time per epoch on REDDIT subsets with varying class complexity, measured in seconds
Subsetl
Subset2
Subset3
Fullset
(2 classes)
(3 classes)
(4 classes)
(5 classes)
GCN GCN+Cconsistnny
0.203
0.345
0.408
0.493
0.227
0.355
0.430
0.557
Structure Complexity We also conducted experiments to assess the training costs on datasets with varying structural complexities when introducing the Lconsistency The results, summarized below in Table 9, show that the additional training cost remains minimal across datasets with different structures. This demonstrates the broad applicability of the proposed method, regardless structural complexity.
Table 9: Average training time per epoch for subsets of varying structural complexity from IMDB-B, measured in seconds.
IMDB-B (small)
IMDB-B (medium)
IMDB-B (large)
GCN
0.0308 0.0371
0.0311 0.0378
0.0321 0.0392
F Efficient Consistent Learning
To further minimize the overhead of our proposed consistency loss, we examined scenario where the consistency loss, denoted as LFL. was only applied to the first and last layers.
Building upon the experimental setup described in Section 5, we conducted experiments using various backbone models. The results are summarized in Table 10. The penultimate column of this table highlights the performance gains achieved by applying the consistency loss across all layers, while the final column demonstrates the improvements observed when the consistency loss is only applied the first and last layers.
Table 10: Graph classification performance with improvements of CALL and LFL L
base models.
NCII
NCI109
PROTEINS
DD
IMDB-B OGB-HIV
CALL
Cri
GCN+LFI.
75.96=0.50
74.67
72.97+2.85
76.27-1.69
74.6=1.85
74.44-1.42
+5.49
+7.08
GIN+LFI.
79.08
77.0+201
73.15+2.78
74.07-1.38
74.8+4.06
74.2+1.62
+10.95
+15.12
GraphSAGE+CFL
78.88
74.24
75.32+2.4
73.90
7.96
80.06-1.21
+9.10
+9.71
GTransformer+-FL
76.7921.4
74.38
73.6942.09
75.08=1.55
16.80
80.53
+9.00
+8.63
GMT+LpL
76.4021.00
75.6420.17
72.25
73.39
76.00
81.05=1.29
+6.23
+5.24
Notably, applying the consistency loss only to the first and last layers achieves performance compara- ble that of applying it across all layers, with both configurations yielding substantial improvements over the original model. This finding suggests that our proposed approach can be accelerated with minimal additional computational cost while still enhancing performance, thereby validating the effectiveness of the consistent learning principle.
24

---

G Similarity/Diffrrence with Contrastive learning
In this section, we discuss the similarities and differences between our method and graph contrastive learning. Graph Contrastive Learning (GCL) is self-supervised technique for graph data that emphasizes instance discrimination [Lin al., 2023, Zhu al., 2021]. A typical GCL framework generates multiple graph views via augmentations and contrasts positive samples (similar instances) with negative samples (dissimilar instances). This approach facilitates effective representation learning by capturing relationships between views, ensuring positive pairs remain close in the embedding space while distinctly separating negative pairs.
While both GCL and our method leverage graph similarity. our approach focuses on maintaining consistency across layers, rather than solely capturing similarities in contrastive learning. To demonstrate this, we integrated the GraphCL technique [You et al., 2020] into GCN model (GCN+CL) and assessed its performance and layer consistency across various datasets. The results, detailed in Tables 11 and 12, use classification accuracy and Spearman rank correlation to measure performance and consistency, respectively.
Table 11: Graph classification accuracy of GCN with contrastive learning applied across various datasets.
NCI1
NCT109
PROTEINS
D&D
IMDB-B
GCN+ CL
74.06 11.1
73.14 +1.90
72.50
+2.73
75.80
2.09
75.80
1.90
Conniteny
75.12 11.19 73.25 +1.25
75.07 +5.05
78.56 3332
75.85 +1.82
Table 12: Spearman correlation for graph representations from consecutive layers.
NCI1 NC1109
PROTEINS D&D IMDB-B
GCN+ CL
0.835
0.717
0.851
0.717
0.810
conniittyy
0.859
0.958
0.946
0.896
0.907
As demonstrated by the results, our method consistently outperforms GCN+CL in both graph classification performance and in enhancing similarity consistency across layers. This underscores the significant differences between our approach and regular GCL methods.
H Boarder Impact
This paper aims to advance the field of graph learning by proposing model-agnostic consistency learning framework. Our framework can be plugged into and improve current methods for graph classification tasks. This has potential benefits in sectors such as chemistry, bioinformatics, and social analysis, where graph classification widely used. Furthermore, we do not foresee direct negative societal ethical consequences arising from our work.
I Limitation
One limitation of our work is that the method involves additional computational costs, especially during large batch training processes. To extend our framework, sampling methodologies data or layers can be applied during the consistency- preceyy-peeeviingg training process. By selectively sampling data points or specific layers,
reduce the computational burden while still maintaining the effectiveness of the cross-layer consistency loss, making the framework more scalable and applicable larger datasets.
25

---

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 experiments and results to support the claims in the introduction and abstract are all in the main paper and the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings. It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations discussed in the main paper Sec. Limitations.
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 encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency 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, worse outcome might be that reviewers discover limitations that aren't It acknowledgen 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.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: This paper include theoretical result and proof involved in main paper and appendix.
26

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems. The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch 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.
Thcorems and Lemmas that the proof relies upon should be 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 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 training schedule and hyper-parameter are listed in Appendix Sec. D.
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 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 is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access 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 replicate the results, access to hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate 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) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.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 particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing 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 data public, and code is provided in the anonymous github.
27

---

Guidelines:
reproducible, they The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines tuttps://nips.. cc/pu
blic/gu guidee/Cooeeeeeeee
ssi onPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.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:
//nips.
hwt///gii////eee// SCoeee/mmdmeebiiaaaa swmmsssssnnPii oniolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. 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 to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have listed all the settings in the appenix for paramtere settings and training schedules. The data splits are decribed under each case study section in the main paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All of our results are listed with error bars.
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 or 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.
28

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative
error rates).
If error bars are reported in tables or plots, The authors should explain 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 the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification:
The compute resources experiments are reported the appendix.
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 compute required for each of individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https atttps//nneurr http:///eeii.peeeeeeeeee
Answer: [Yes]
Justification: The research conducted in this paper conforms, in every respect, to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The broader impact discussed in the appendix H.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal
impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
29

---

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 unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release 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).
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)?
Question:
Answer[[NA)
Justification:
The paper poses no such risks.
Guidelines:
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 usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators 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: They are properly cited and eredited.
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 URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswithcode thcode. /mm/ttasets has curated licenses for some datasets. Their licensing guide help determine the license of a dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: the new model introduced in the paper is well documented.
Guidelines:
30

---

The answer NA means that the paper does not release new assets. Researchers should communicate the details the dataset/code/moodll as part 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: 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 in the main paper.
According the NeurIPS 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: This work 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.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the 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 institution conducting the review.
31


Reviews:
[{"review_id": "nzhoer0c8g", "reviewer": "Reviewer_2j7s", "summary": "In this paper, the authors introduce the shortcomings of graph neural networks (GNNs) in capturing consistency and similarity relationships between graphs, and proposes a new loss function, aiming to enhance graph representation at different levels. Through theoretical analysis and experimental verification, the author proved that consistency loss can significantly improve the performance of GNN in graph classification tasks.", "questions": "1. If only the consistency of the first and last layers of the graph representation is enhanced to replace the consistency constraints of all layers, how much will the experimental performance drop? Will there be an improvement compared to the base model?\n\n2. Contrastive learning can also capture similarity between samples. Can the author give the differences and similarities between contrastive learning and the proposed method in the paper?", "limitations": "None", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The structure of the paper is clear and easy to follow.\n\n2. The proposed method seems reasonable and sound.\n\n3. The method is effective in comparison to base models.", "weaknesses": "1. I have some concerns about the efficiency of the method. The authors give the limitation about additional computational costs, which is commendable. I suggest that the authors provide the complexity analysis, specific running times and memory usage to enable further evaluation of the paper.\n\n2. The authors mention \"across a wide range of base models and datasets\" in the Introduction section, but the datasets used in experiments only have two classes. To further verify the effectiveness of the method on a wide range of datasets, I suggest that the author conduct experiments on datasets  with more classes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their insights on efficiency and the relation of the proposed method to contrastive learning. We aim for the responses to be clear in addressing the concerns and questions. If any concerns remain or if further improvements are deemed necessary, please let us know how we can further enhance the work.\n\n**1. Complexity Analysis.**\n\nWe've included the time and space complexity analysis in the general response. The additional costs introduced by our proposed loss are minimal.\n\n\n**2. Concerns Regarding only using first/final layer.**\n\n\nStudying the case where consistency loss is applied only between the first and final layers could be beneficial, as it may further reduce the training time. We conduct additional experiments applying our consistency loss to the first and final layers of various backbone models, with the results presented in Table R3. The second to last column in Table R3 highlights the improvement of applying consistency loss to all layers, compared to the baseline models. The last column shows the improvement when consistency loss is applied only to the first and last layers. As shown, applying consistency loss only to the first and last layers achieves similar performance to applying it to all layers. This suggests our method can be further accelerated with little to no performance sacrifice.\n\n\nTable R3. Classification performance on TU and OGB datasets for models with consistency loss applied to the first and last layers. The values represent average accuracy for TU datasets and ROC-AUC for the ogbg-molhiv dataset, along with their standard deviations.  $\\mathcal{L}\\_{FL}$ and $\\mathcal{L}\\_{ALL}$ denote the consistency loss applied to the first and last layers, and to all layers, respectively.\n|       |       NCI1       |      NCI109      | PROTEINS   |    DD |     IMDB-B      |    ogbg-mol     | Improvements of $\\mathcal{L}_{ALL}$ over base models| Improvements of $\\mathcal{L}_{FL}$ over base models|\n| :----------: | :--------------: | :--------------: | ---------------- | :--------------: | :-------------: | :--------------: | :---------------------------------------------------------: | :----------------------------------: |\n|     GCN+$\\mathcal{L}_{FL}$      | $75.96 \\pm 0.89$ | $74.67 \\pm 1.11$ | $72.97 \\pm 2.85$ | $76.27 \\pm 1.69$ | $74.60 \\pm 1.85$ | $74.44 \\pm 1.42$ |     $+5.49$      |      $+7.08$     |\n|     GIN+$\\mathcal{L}_{FL}$      | $79.08 \\pm 1.21$ | $77.00 \\pm 2.01$  | $73.15 \\pm 2.76$ | $74.07 \\pm 1.38$ | $74.80 \\pm 4.66$ | $74.20 \\pm 1.62$  |     $+10.95$      |    $+15.12$     |\n|  GraphSAGE+$\\mathcal{L}_{FL}$   | $78.88 \\pm 2.01$ | $74.24 \\pm 1.21$ | $75.32 \\pm 2.46$ | $73.9 \\pm 2.03$  | $76.6 \\pm 1.96$ | $80.06 \\pm 1.21$ |   $+9.10$   |         $+9.71$         |\n| GTransformer+$\\mathcal{L}_{FL}$ | $76.79 \\pm 1.24$ | $74.38 \\pm 0.49$ | $73.69 \\pm 2.09$ | $75.08 \\pm 1.57$ | $76.8 \\pm 1.60$  | $80.53 \\pm 0.73$ |  $+9.00$ |       $+8.63$         |\n|     GMT+$\\mathcal{L}_{FL}$   |  $76.4 \\pm 1.71$  | $75.64 \\pm 0.77$ | $72.25 \\pm 3.96$ | $73.39 \\pm 2.18$ | $76.6 \\pm 1.36$ | $81.05 \\pm 1.29$ |   $+6.23$  |    $+5.24$  |\n\n\n\n**3. Similarity/Difference with Contrastive learning.**\n\n\nThis is an interesting question. While both methods assess similarity, our approach **emphasizes the consistency across layers rather than merely capturing similarities, as contrastive learning does.** To validate this, we applied the GraphCL[1] contrastive learning technique to the GCN model (denoted as GCN+CL) and evaluated its performance and similarity consistency across various datasets. The results, shown in Tables R4 and R5, use accuracy for classification performance and Spearman rank correlation (Section 5.3) for assessing similarity consistency across layers. The last columns present the average decrease in accuracy and rank correlation for GCN+CL compared to GCN+$\\mathcal{L}_{\\text{consistency}}$.\n\n\n\nTable R4. Graph classification accuracy of GCN with contrastive learning applied across various datasets.\n|        |       NCI1       |      NCI109      |     PROTEINS     |        DD        |      IMDB-B      | Average decrease vs. GCN+$\\mathcal{L}_{\\text{consistency}}$ |\n| :----: | :--------------: | :--------------: | :--------------: | :--------------: | :--------------: | :-----------------------------: |\n| GCN+CL | $74.06 \\pm 1.91$ | $73.14 \\pm 1.90$ | $72.50 \\pm 2.73$ | $75.80 \\pm 2.09$ | $75.80 \\pm 1.90$ |           $1.31$             |\n\n\nTable R5. Spearman rank correlation for graph representations from consecutive layers.\n|        |  NCI1   | NCI109  | PROTEINS |   DD | IMDB-B  | Average decrease vs. GCN+$\\mathcal{L}_{\\text{consistency}}$|\n| :----: | :-----: | :-----: | :------: | :-----: | :-----: | :-------------------------------------: |\n| GCN+CL | $0.835$ | $0.717$ | $0.851$  | $0.717$ | $0.810$ |  $0.127$  |\n\nOur method consistently outperforms GCN+CL in both graph classification and improving similarity consistency, highlighting the key differences between the two approaches.\n\n[1]Y. You et al., Graph Contrastive Learning with Augmentations, NeurIPS, 2020\n\n\n**4. Multi-classification.**\n\nTo demonstrate the effectiveness of our method across diverse datasets, we applied it to REDDIT-MULTI-5K, a 5-class classification dataset. The results, presented in Table R6, show that our method consistently achieves improvements in this task.\n\nTable R6. Graph classification performance on REDDIT-MULTI-5K, measured in accuracy.\n| REDDIT(5K)                          | GIN            | GMT            | GCN            | GraphSAGE  | GTransformer   |\n| ----------------------------------- | -------------- | -------------- | -------------- | ---------- | -------------- |\n| Baseline                            | $54.06±2.10$     | $51.04\\pm 1.41$    | $53.80 \\pm 0.78$     | $58.42 \\pm 1.26$ | $50.84 \\pm 2.18$     |\n| +$\\mathcal{L}_{\\text{consistency}}$ | $55.12±1.17$ | $54.88 \\pm 1.33$ | $57.12 \\pm 1.47$| $58.38 \\pm 1.59$ | $52.24 \\pm 1.23$ |", "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": "mgeZkNKk15", "reviewer": "Reviewer_NH7G", "summary": "The authors propose to improve the quality of graph embeddings in GNNs by encouraging a n motion of consistency in the representation obtained at the various layers.", "questions": "Suggestions could include:\n- reporting the run time information to gauge the tradeoff between the additional complexity and the performance improvement \n- reporting a critical difference diagram ( https://scikit-posthocs.readthedocs.io/en/latest/generated/scikit_posthocs.critical_difference_diagram.html ) to summarise the results of Table 1 and 2.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work presented here offers interesting contributions: 1) a new perspective on understanding the graph classification performance of GNNs by examining the similarity relationships captured across different layers; 2) a novel consistency principle in both kernel and GNNs with theoretical proofs explaining how this principle enhances performance; 3) empirical evaluation across diverse GNN model types.", "weaknesses": "The paper could be improved by:\n- devising an artificial experiments with graph datasets of increasing structural complexity and with an increasing label alphabet to show a link between the complexity of the task and the amount of improvement offered by the proposed technique", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's question about artificial experiments, which provides an opportunity to explore how this method performs across different data scenarios. Should there be any remaining issues or suggestions for improvement, we welcome further feedback on how to refine our approach.\n\n**1.Increasing label alphabet.**\n\nTo investigate the influence of an increasing label alphabet on the runtime and performance of our method, we generated subsets with an increasing number of classes from the REDDIT-MULTI-5K dataset, which originally comprises five classes. Specifically, we randomly sampled between 2 to 4 classes from the dataset and run GCN and GCN+$\\mathcal{L}_{\\text{consistency}}$ on these subsets. \n\nTable R7. Graph classification performance on subsets of REDDIT-MULTI-5K, measured in accuracy.\n\n\n\n|                                        | Subset1 (2 classes) | Subset2 (3 classes) | Subset3 (4 classes) | Fullset |\n| :------------------------------------: | :-----------------: | :-----------------: | :-----------------: | :-----: |\n|              GCN              |       $79.50$       |       $67.13$       |       $50.30$       | $53.80$ |\n| GCN+$\\mathcal{L}_{\\text{consistency}}$ |       $81.10$       |       $68.00$       |       $57.15$       | $57.12$ |\n\n\n\n\n\nThe results in Table R7 show that the effectiveness of our method remains unaffected by the growing number of labels.\n\nWe further measure the runtime of the models on these subsets and present the results in Table R8. As shown in Table R8, the addtional time costs do not change much with the growing number of labels.\n\nTable R8: Average training time per epoch on subsets with varying class complexity from REDDIT, measured in seconds. \n\n\n\n|                                     | Subset1(2 classes) | Subset2(3 classes) | Subset3(4 classes) | Fullset |\n| :---------------------------------: | :----------------: | :----------------: | :----------------: | :----------------: |\n|            GCN           |      $0.203$       |      $0.345$       |      $0.408$       |      $0.493$       |\n| GCN +$\\mathcal{L}_{\\text{consistency}}$ |      $0.227$       |      $0.355$       |      $0.430$       |      $0.557$       |\n\n\n**2.Increasing structural complexity.**\n\nWe evaluate the impact of structural complexity by dividing the IMDB-BINARY dataset into three subsets with increasing graph density. This density, denoted as $d=\\frac{2 m}{n(n-1)}$, where $n$ is the number of nodes and $m$ is the number of edges in graph $G$, was employed as the criterion for creating these subsets. Specifically, the datasets were divided into: (small) for graphs with a density below the 33rd percentile, (median) for densities between the 33rd and 67th percentiles, and (large) for graphs with a density above the 67th percentile. We run GCN and GCN +$\\mathcal{L}_{\\text{consistency}}$ models on these subsets and present the results in Table R9.\n\n\nTable R9. Graph classification performance across subsets of varying structural complexity from  IMDB-B. Performance is measured in accuracy.\n\n\n\n|                                        | IMDB-B`(small)` | IMDB-B`(medium)` | IMDB-B`(large)` |\n| :------------------------------------: | :-------------: | :--------------: | :-------------: |\n|              GCN             |  $77.58±4.11$   |   $66.25±5.38$   |  $67.61±6.21$   |\n| GCN +$\\mathcal{L}_{\\text{consistency}}$ |  $84.24±4.85$   |   $69.06±4.06$   |  $71.43±4.43$   |\n\nBased on these results, we can conclude that with the $\\mathcal{L}_{\\text{consistency}}$ loss function, the GCN model consistently outperforms the original version across varying levels of structural complexity in both datasets, underscoring the effectiveness of the proposed method.\n\n\nWe also conducted experiments to assess the training costs on datasets with different structural complexities when introducing the $\\mathcal{L}_{\\text{consistency}}$ loss. The results are presented below.\n\n\nTable R10. Average training time per epoch for subsets of varying structural complexity from IMDB-B, measured in seconds.\n\n\n|                                        | IMDB-B`(small)` | IMDB-B`(medium)` | IMDB-B`(large)` |\n| :------------------------------------: | :-------------: | :--------------: | :-------------: |\n|              GCN             |       $0.0308$   |       $0.0311$   |    $0.0321$    |\n| GCN +$\\mathcal{L}_{\\text{consistency}}$ |   $0.0371$    | $0.0378$         |     $0.0392$     |\n\n\nGiven these results, we find that the additional training cost is minimal across datasets with different structural complexities, demonstrating its broad applicability.\n\nFor more analysis in time and space complexity of our method, please refer to the general responses. \n\n\n\n**3.Critical difference diagram.**\n\n\nWhile the suggestion to include critical difference diagrams is appreciated, these diagrams may not be suitable for our context. As shown in Table 1 and 2 (in the main paper), incorporating consistency loss generally enhances the performance of the baseline models. However, no clear ranking emerges across the different baselines, as each model excels in distinct datasets across various domains. Since the primary goal of this paper is not to determine the relative ranking of these models, such rankings would not yield meaningful insights.", "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": "lqn6dqee9y", "reviewer": "Reviewer_q7iD", "summary": "This work aims to bridge the gap between neural network methods and kernel methods by enabling GNNs to consistently capture relational structures in their learned representations. The authors propose a loss function that enforces the similarity of graph representations to remain consistent across different layers. Extensive experiments demonstrate that the proposed consistency loss can significantly enhance the graph classification performance of various GNN backbones on different datasets.", "questions": "Please see ‘Weaknesses’.", "limitations": "None", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This work explores the connection between kernels and GNNs, and proposes a consistency criterion. It has a strong theoretical foundation.", "weaknesses": "1.Does the consistency loss effectively enhance the performance of various GNN backbones in the graph clustering task?\n2.This algorithm does not seem suitable for application to large-scale datasets.\n3. There are several typos and grammatical/spelling errors that should be corrected.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's insightful question regarding the extension of our method to graph clustering tasks and large-scale graph datasets, since complexity and scalability are significant concerns in practical applications. \n\n**1.On Graph Clustering Tasks.**\n\nWhile applying our consistency loss to the graph clustering task is an interesting idea, it's important to note that our method is specifically designed for graph-level tasks rather than node-level tasks. This approach is grounded in graph kernels, which are predominantly used for graph-level applications. Thus, there are no theoretical guarantees for node-level tasks. Furthermore, unlike graph classification tasks where similarities are computed only within a batch of graphs, applying this approach to clustering requires calculating similarities between all nodes within a graph, which significantly increases computational costs. Nevertheless, we manage to apply our consistency loss to the Attention-driven Graph Clustering Network (AGCN) model[1] on the ACM dataset by leveraging a sampling strategy to compute similarities among the nodes.\nFollowing previous research[1,2], we evaluate the quality of clustering using four key metrics: Accuracy (ACC), Normalized Mutual Information (NMI), Average Rand Index (ARI), and macro F1-score (F1). Higher values for each metric signify better clustering performance. The results, presented in Table R11, demonstrate that applying our method to a clustering model leads to slight improvements. This suggests that our approach has the potential to enhance performance in graph clustering tasks.\n\n\nTable R11: Graph clustering on ACM Dataset,  evaluated in terms of accuracy/NMI/ARI/F1.\n\n\n\n|      |       AGCN       | AGCN+$\\mathcal{L}_{\\text{consistency}}$ |\n| :--: | :--------------: | :-------------------------------------: |\n| ACC  | $0.899\\pm 0.001$ |             $0.901\\pm0.004$             |\n| NMI  | $0.672\\pm0.004$  |             $0.676\\pm0.010$             |\n| ARI  | $0.725\\pm0.003$  |             $0.731\\pm0.010$             |\n|  F1  | $0.898\\pm0.001$  |             $0.901\\pm0.004$             |\n\n\n\n**2.On Large-Scale Datasets.**\n\nAs described in our general response, the computational cost associated with our method scales linearly with the dataset size, which is small compared to the training time. Furthermore, we conduct additional experiments to run our model on a real-world large dataset, Reddit Threads dataset[3], which contains over 200,000 graphs. We present the results in Table R12.\n\nTabel R12. Graph classification performance on Reddit Threads dataset, measured in accuracy.\n\n\n\n\n|               REDDIT Threads               |    GIN     |     GMT     |    GCN     | GraphSAGE  | GTransformer | Average improvements |\n| :----------------------------------------: | :--------: | :---------: | :--------: | :--------: | :----------: | :-----------------: |\n| w/o $\\mathcal{L}_{\\text{consistency}}$     | $77.50\\pm0.16$ | $72.06\\pm10.15$ | $76.00\\pm0.44$ | $76.67\\pm0.11$ | $76.75\\pm0.12$ | - |\n| w $\\mathcal{L}_{\\text{consistency}}$       | $77.64\\pm0.05$ | $77.19\\pm0.14$  | $77.12\\pm0.12$ | $77.57\\pm0.05$ | $77.14\\pm0.06$ | $1.54$ |\n\nTable R12 demonstrates that our method remains effective on large datasets and achieves noticeable improvements across a range of backbone networks.\n\n\n\n\n\n[1] Peng, Z., Liu, H., Jia, Y., & Hou, J. (2021). Attention-driven Graph Clustering Network. Proceedings of the 29th ACM International Conference on Multimedia.\n\n[2]Bo, D., Wang, X., Shi, C., Zhu, M., Lu, E., & Cui, P. (2020). Structural Deep Clustering Network. Proceedings of The Web Conference 2020.\n\n[3]Rozemberczki, B., Kiss, O., & Sarkar, R. (2020). An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs. ArXiv, abs/2003.04819.\n\n\n**3.Typo.**\n\nWe thank the reviewer for reminding us of this issue. We will address it in the next version.", "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 thank all reviewers for recognizing the novelty and theoretical contributions of our paper and appreciate the valuable feedback that has significantly enhanced our work. We hope our responses are informative and helpful. Further feedback on any remaining points of concern and suggestions for improvement would be gratefully received. We will begin by addressing the general question regarding our model's time and space complexity, followed by detailed responses to the specific questions raised by each reviewer.


**1. Time Complexity.**

We present the time complexity analysis for our proposed consistency loss. The loss computation involves the compuation of pairwise similarities of graphs in a batch, resulting in a computation complexity of $O\left(\text{batchsize} \cdot \frac{\text{batchsize}-1}{2}\right) = O(\text{batchsize}^2)$. Given that there are $\frac{\text{datasetsize}}{\text{batchsize}}$ batches in each training epoch and that the similarities are computed between consecutive layers, the total complexity is: $$
O(\text{loss})=O(\{\text{batchsize}^2 \times(\text{ layernum }-1) \times\frac{ \text{datasetsize }}{\text{batchsize }}\})=O(\text{ datasetsize} \times \text{batchsize} \times \text{layernum }).$$This analysis shows that the time required to compute consistency loss scales linearly with dataset size, batch size, and the number of layers. It is important to note that the training time for baseline models also scales linearly with dataset size.

Since batch size and the number of layers are generally small compared to dataset size, our experiments primarily focus on how dataset size affects training time. We evaluate the training time of several models—GCN, GIN, GraphSAGE, GTransformer, and GMT—each enhanced with our consistency loss. This evaluation is conducted on different subsets of the ogbg-molhiv dataset, with subset sizes adjusted by varying the sampling rates. The training time, measured in seconds, are presented in Figure R1 (see the attached PDF). As shown, our findings confirm that training time increases linearly with dataset size, indicating that our method maintains training efficiency comparable to baselines without adding significant time burdens.



Furthermore, we empirically measure the training time for both the baseline models and our proposed methods. Each model comprises three layers and is trained on the ogbg-molhiv dataset (40,000+ graphs) for 100 epochs. We calculate the average training time per epoch in seconds and present the results in Table R1. Table R1 shows that while the inclusion of the consistency loss slightly increases the training time, the impact is minimal.

Table R1: Average training time per epoch for different models on the ogbg-molhiv dataset, measured in seconds.

|                                          |  GMT  | GTransformer |  GIN  |  GCN  | GraphSAGE |
| :--------------------------------------: | :---: | :----------: | :---: | :---: | :-------: |
| w/o $\mathcal{L}_{\text{consistency}}$ | $8.380$ |   $4.937$    | $4.318$ | $4.221$ |   $3.952$   |
|   w $\mathcal{L}_{\text{consistency}}$   | $8.861$ |    $6.358$     | $5.529$ | $5.382$ |   $5.252$   |



**2. Space Complexity.**


Next, we present the space complexity analysis for our consistency loss. At each iteration, the loss function requires storing two pairwise similarity matrices corresponding to two consecutive layers, which is given by:
$$
O(\text { loss })=O(\text {batchsize}^2 )$$
Since we use stochastic gradient descent, similarity matrices are not retained for the next iteration. The consistency loss requires significantly less space than node embeddings, making the additional space requirement minimal. Table R2 shows the peak memory usage in megabytes (MB) for different models when training on the ogbg-molhiv dataset. Table R2 shows that the space costs are negligible.

Table R2. Peak memory usage for different models on the ogbg-molhiv dataset, measured in megabytes.
|                                          |  GMT   | GTransformer |  GIN   |  GCN   | GraphSAGE |
| :--------------------------------------: | :----: | :----------: | :----: | :----: | :-------: |
| w/o $\mathcal{L}_{\text{consistency}}$ | $1334.0$ |    $1267.8$    | $1291.3$ | $1274.2$ |  $1288.4$   |
|   w $\mathcal{L}_{\text{consistency}}$   | $1370.0$ |    $1330.6$    | $1338.9$ | $1320.1$ |  $1321.3$   |
|            Cost Increase (%)             |  $2.70$  |     $4.96$     |  $3.68$  |  $3.60$  |   $2.55$    |

Meta-review: After the rebuttal, the reviewers unanimously recommend to accept the paper. They highlight the strong theoretical foundation, a novel consistency principle, and the thorough empirical evaluation.
Decision: Accept (poster)