Centrality-guided Pre-training for Graph
Authors: Bin Liang
Shiwei Chen
Lin Gui
Hui Wang
Yue Yu
Ruifeng Xu
Kam-Fai Wong
Venue: ICLR 2025 Poster (2025)
Keywords: Graph neural networks
Graph representation
Graph pre-training
Graph centrality
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose CenPre, a framework that integrates structural information into node representations using centrality measures, outperforming state-of-the-art methods in node classification, link prediction, and graph classification.

Abstract: Self-supervised learning (SSL) has shown great potential in learning generalizable representations for graph-structured data. However, existing SSL-based graph pre-training methods largely focus on improving graph representations by learning the structure information based on disturbing or reconstructing graphs, which ignores an important issue: the importance of different nodes in the graph structure may vary. To fill this gap, we propose a Centrality-guided Graph Pre-training (CenPre) framework to integrate the distinct importance of nodes in graph structure into the corresponding representations of nodes based on the centrality in graph theory. In this way, the different roles played by different nodes can be effectively leveraged when learning graph structure. The proposed CenPre contains three modules for node representation pre-training and alignment. The node-level importance learning module fuses the fine-grained node importance into node representation based on degree centrality, allowing the aggregation of node representations with equal/similar importance. The graph-level importance learning module characterizes the importance between all nodes in the graph based on eigenvector centrality, enabling the exploitation of graph-level structure similarities/differences when learning node representation. Finally, a representation alignment module aligns the pre-trained node representation using the original one, essentially allowing graph representations to learn structural information without losing their original semantic information, thereby leading to better graph representations. Extensive experiments on a series of real-world datasets demonstrate that the proposed CenPre outperforms the state-of-the-art baselines in the tasks of node classification, link prediction, and graph classification.

Published as a conference paper at ICLR 2025
CENTRALITY-GUIDER PRE-TRAINING FOR GRAPH
1,355 Bin Liangl.3.5+, Shiwei 2. Lin Gui Hui Wang', Yue Yu?,
Ruifeng Xu Kam-Fai Wong
'The Chinese University of Hong Kong Peng Cheng Laboratory
Harbin Institute of Technology (Shenzhen) *King's Ssin'sSuu College London 6 Ministry of Education Key Laboratory of High Confidence Software Technologies, CUHK bin. 1 aiianneuul cuhk. edu. hk; (shwchen, wangh06, yuy) @pc1. ac cn;
Lin. 1. gui@kelk aael.ac....... ac. uk; xuruifeng@hee edu, en; kfwongêse. cuhk, edu.hk hk
ABSTRACT
Self-super learning (SSL) has shown great potential learning generalizable representations for graph-structured data. However, existing SSL-based graph pre-training methods largely focus on improving graph representations by learning the structure information based on disturbing or reconstructing graphs, which ig- nores an important issue: the importance of different nodes in the graph structure may vary. To fill this gap, propose Centrality-guidde Graph Pre-training (CenPre) framework to integrate the distinct importance of nodes in graph structure into the corresponding representations of nodes based the centrality in graph theory. In this way, the different roles played by different nodes can be effectively leveraged when learning graph structure. The proposed CenPre contains three modules for node representation pre-training and alignment. The first is a node- level importance learning module, fusing the fine-grained node importance into node representation based on degree centrality, allowing the aggregation of node representations with equal/similar importance. The second one, the graph-level importance learning module, characterizes the importance between all nodes in the graph based on eigenvector centrality, enabling the exploitation of graph-level structure similarities/differnnees when learning node representation. Finally, representation alignment module aligns the pre-trained node representation using the original one, permitting graph representations to learn structural information without losing their original semantic information, thereby leading to better graph representations. Extensive experiments series of real-world datasets demon- strate that the proposed CenPre outperforms the state-of-the-art baselines the tasks of node classification, link prediction, and graph classificatior
INTRODUCTION
Graph neural networks (GNNs) aim to model the structural information of the graph by neigh- borhood aggregation schemes, becoming increasingly popular in graph representation learning for graph-structured data (Zhu al., 2021a). such as knowledge graphs (Baek al., 2020), social networks (Fan et al.) 2019), point clouds (Shi & Rajkumar 20200), and chemical analysis (De Cao & 2018). Graph representation learning can produce oow-dimensional vector representations for graph-structuure data in many applications, including node/graph classification, link prediction, and graph generation (You et al. 2020 Wang et al. 2020 Zhang Chen 2018 Hou et al. (019)).
Recently, self-supervised learning on graph-structured data has shown great potential in learning generalizable, transfcrable, and robust representations due to the advantage of learning graph structural information without annotated data (Hu et al. 2020 You et al. 2020). Among many, graph predictive learning and graph contrastive learning (GCL) have become two main paradigms learning graph representation, where mutual information between graph representations
be learned by leveraging
the similarity/difference between augmented views (Hu et al. 2020: Kim et al. 2022
You et al.
"Equal contribution.
"Corresponding authors.
'The source code of this work is released at httptttpp///gtttee http:/uuu....///////11111111

---

Published as a conference paper at ICLR 2025
Xia et al. 2022b). Furthermore, Jin et al. (2020) and Hu et al. (2019b) explore centrality in learning graph structures in pre-training graphs. Despite promising progress made by existing graph representation learning methods, they largely ignore the importance of different nodes in the graph structure may vary when learning graph structure. This deficiency may result in the inability to exploit important characteristic information in the graph structure when learning graph representations.
2020 2021
To alleviate this issue, in this paper, we propose a novel graph pre- pre-tranning framework to produce better graph representation that leverages graph structure in learning graph representations by exploiting the distinct importance of different nodes in graph structure based on the notion of graph centrality, dubbed centrality-guides Graph Pre- Pre-training (CenPre). There are three modules in the proposed CenPre: 1) node-level importance learning module, which aims to enhance the node representations with the node importance in graph structure based on the property of degree centrality; 2) graph- level importance learning module, which is designed to leverage the global importance of node based on the property of eigenvector centrality when learning node representation; and 3) graph representation alignment module, which aligns the importance-fused node representation with the original one.
Node-level importance learning. Degree centrality defines the importance of node based on the degree of that node. The higher the degree, the more crucial a node becomes in the graph (Zaki & Meira 2014). Based on this property, argue that the degree of node can represent its importance in a graph, which plays a crucial role in its representation, so its representation can be refined by degree. Therefore, corresponding degree. This approach enables the model to capture statistical regularities between representations and graph structures, allowing it to assess node importance effectively, As a result, nodes with similar degrees receive comparable representations, while distinctions are maintained for nodes of varying significance.
explore predictive learning
map each node representation into the
Graph-level importance learning. Eigenvector centrality, or cigencentrality, measures a node's 's influence within connected network by accounting for direct and indirect connections (Zaki Meira 2014; 2014 Bonacich 2007). Such measure provides a comprehensive understanding of node's role in the global graph structure. Building on this, we propose identifying the most influential neighbors of each node to obtain global structural perspective, which can guide the refinement of node representations. To achieve this, we introduce a Contrastive Representation-Sttuuur Tre-Training (CReSP) strategy that aligns node representations with the graph-level importance of nodes. Specifically, matrix decomposition is used to extract significant eigenvalues and eigenvectors, facilitating the identification of key neighbors in large, sparse graphs. Using cross-attention, the graph representation guides the structure matrix in determining node importance relative to the current node. Inspired by CLIP (Radford al. 2021), CReSP refines this alignment by matching node representations with their structural patterns, maximizing the similarity between nodes with shared important neighbors and distinguishing node representations with different global importance, thereby enhancing node representations by incorporating graph-level node importance information.
Graph representation alignment. After the graph structure pre-training, a graph representation alignment module is devised to align the pre-trained structure- fusure graph representation using the original representation, allowing the graph representation to retain the original semantic information while learning the graph structure information.
Our main contributions are as follows:
We are the first to explore node importance in learning graph structure and align the graph representation with graph structure in the graph pre-training process, aiming to produce better graph representations for downstream tasks.
Based the notion of centrality, novel centrality-guidee Graph Pre-training (CenPre) framework is proposed to learn importance-fused graph representation from both local and global perspectives.
We conduct a series of experiments on real-world graph graph-structured benchmark datasets to evaluate the effectiveness of our CenPre in learning graph representation. Experimental results show that our CenPre significantly outperforms baselines in the tasks of node classification, link prediction, and graph classification.
2

---

Published as a conference paper at ICLR 2025
2
RELATED WORK
2.1 GRAPH NEURAL NETWORKS
Graph Neural Networks (GNNs) capture node dependencies through graph topology. The Graph Convolutional Network (GCN) (Kipf & Welling, 2017) aggregates local neighborhood features, excelling in node classification but struggling with global structures. Graph Attention Network (GAT) (Velickovic al. 2018) improves feature aggregation via attention mechanisms, enhancing performance in heterogeneous graphs but increasing computational demands. Graph Isomorphism Network (GIN) (Xu et al. 2019) improves structure distinction but risks overfitting on small datasets, while GraphS AGE (Hamilton et al. 2017) scales well for large graphs using neighborhood sampling, though it may lose information in dense networks. Graph Transformers (Dwivedi & Bresson 2020) capture long-range dependencies with self-attention, but are computationally intensive for large-scale graphs. Some other previous works extend GNNs by leveraging centrality to enhance structural understanding. For instance, Maurya et al., 2019 proposes a GNN framework for approximating betweenness centrality by leveraging constraiedd message passing and ranking loss learn structural node importance efficiently. (Avelar et al. (2018) introduces multitask GNN- based learning framework to approximate multiple centrality measures, enabling shared representations and accurate structural feature predictions.
2.2 SELF-SUPERVISED LEARNING ON GRAPHS
supervvpe learning has achieved promising performance in graph pre-training, Early works like DeepWalk (Perozzi al., 2014) and node2vec (Grover & Leskovec, (016) use random walks to capture local structures, while contrastive learning methods such as DGI (Veličković et al. 2019). InfoGraph (Sun et al., 2020), and GraphCL. ( (You et al., (020) maximize agreement between augmented views. MVGRL (Hassani & Khasahmadi| 2020) contrasts different graph views using diffusion, but these methods face challenges in selecting augmentations and handling negative samples. GGD Zheng et al. 2022) eliminates contrastive similarity computation by discriminating augmented positive and negative node groups through a binary classification task. BGRL (Thakoor et al.) (2021). T-BGRL (Shiao et al.] 2022), and CCA-SSG (Zhang al.. 2021) align representations without negative samples, offering more efficient alternatives. Graph autoencoders (GAF) (Gareía-Durán & Niepert 2017). VGAE (Kipf & Welling (016)), and other variants reconstruct graph structure but often underperform in classification. GraphMAE (Hou et al. 2022) improves performance using masked feature reconstruction, bypassing augmentations, while GPT-GNN (Hu et al. (020) introduces autoregressive graph generation for pre-training. Along the line of work on multi-tase learning, GBT (Bielak et al. 202T) proposes incorporate multi-task objectives, including node proximity and subgraph features, capture intrinsic graph properties without relying augmentation. PARETOGNN (Ju et al. 2022) enhances task generalization by reconciling multiple pretext tasks through multiple- gradient descent algorithm promoting Pareto optimality. AutoSSL (Jin al.) 2021) leverages the homophily principle to automatically search for optimal combinations of multiple self-supervised tasks, significantly enhancing the performance downstream tasks such node clustering and classification. For the works that use centrality, GCA (Zhu et al.) 2021b) adaptively retains critical structural features using centrality-guider augmentations enhance representation learning. Relying on node degrees for its centrality- such as clustering and node distance prediction learn robust structural embeddings. Hu al.) (2019b) uses centrality score ranking to guide GNNs in capturing structural features but overlooks the actual value of the centrality score. Unlike previous approaches, we use degree centrality to assess node importance and Figenvector centrality for global structural information, integrating both local and global properties to guide graph pre-training efficiently. A detailed analysis of our motivation shown in Appendix FF
multiple-gradient
learning, |Jin et al. (2020) combines tasks
PRELIMINARIES
Notations Let G {V,E) represent undirected graph, where V = {ri, U2, Cn is the set of nodes and E the set of edges. X, Nxd, and X. R[ denote the node and edge feature matrices, respectively. The representation of a node e; is h, and the graph-level representation is Hg (h1 th,.,,....,,. h.
3

---

Published as a conference paper at ICLR 2025
Ld
h1
F11
Fin
h2
1'11
T22
Degree Predictor
Le
hg
15
11
f
hz
ha
nn
Tul
H2
:
Att
si
$/
S/i
h
hg
5
0
0
0
0
1
0
SVD
0
0
0
Degree matrix
Graph
Adjacency matrix
Node-level structure learning
Graph-level structure learning
Representation alignment
Figure 1: Illustration of CenPre framework. is the GNN encoder that is used to generate node representation, f is the pre-trained GNN encoder produced by our CenPre framework, and f the original GNN encoder without pre-training. "Att" represents cross-attention. h, 8, and embeddings, where ra h; Sg-
Graph Neural Networks GNNs update the graph representation Hg by leveraging the graph topology. For example, GCN (Kipf & Welling, (016)) updates node representations by aggregating neighborhood information based on the adjacency matrix A. The degree matrix D. with D; repre- senting the degree of node v, normalizes the influence neighboring nodes. The propagation rule for GCN is:
= = (
where Á -= A + / includes self-loops, Ó is its degree matrix, W(K) is the trainable weight matrix, and (-)) is a non-linear activation function.
METHOD
The motivation for CenPre is based on node2vec (Grover Leskovec 2016), which suggests that nodes with similar roles have similar embeddings. Additionally, as highlighted in (McNulty) (022). influential nodes in graph layouts tend to be positioned centrally due to their stronger connectiv- ity. Building on the relationship between node importance and centrality, we propose novel Centrality-guided Graph Pre-training (CenPre) framework to learn node representations. Unlike node2vec (Grover & Leskovec, 22066), our goal enhance node embeddings by aggregating or differentiating them based on centrality, rather than just role similarity. The CenPre architecture is shown in Figure
To achieve this, we propose integrating node importance into representation learning from two perspectives: 1) node-level importance learning, which enhances node representations based on their individual importance in the graph; and 2) graph-level importance learning, which improves node representations by considering the importance related nodes. We introduce a graph represen- tation alignment module to align the centrality-guided node representations with the original ones, preserving semantic information while incorporating node importance. In this study, we use degree centrality and eigenvector centrality as local and global measures of node importance, respectively, to guide CenPre's pre-training for more accurate, seuucture-wwrrt node embeddings. More discussion other centrality measures can be found in Appendix A
4

---

Published as a conference paper at ICLR 2025
4.1 NODE-LEVEL IMPORTANCE LEARNING
In this section, we introduce the node-level importance learning module of our CenPre framework in detail. Based the Definition [ from Degree Centrality, we propose node-level importance learning, aiming to identify the degrees of nodes to distinguish the importance of nodes, so as to guide the refinement of the node representation according to the degree of the node.
Definition 1. Degree Centrality defines the importance of node based on the degree of that node. The higher the degree, the more crucial it becomes in the graph.
From [q it is evident that GNNs like GCNs use the adjacency matrix to aggregate information from neighboring nodes in equal and uniform manner, assuming that all sources of information contribute equally. However, GCNs focus solely on the connections between nodes when aggregating neighbor information and do not account for the specific roles or characteristics of nodes. In this study, we address this limitation by incorporating node importance into the learning process, allowing for more accurate representations. To be specific, for each graph, we obtain the degree d, of each node & by summing the values in its corresponding row of the adjacency matrix A, which represents the connections between nodes:
= :-=4->>
ΣA: Aij
where Aij represents the entry in the adjacency matrix A indicating the presence (1) or absence (0) of an edge between nodes ii and vy. Then, we train a degree predictor Pa to predict the degree of each node based on the node representations {h1, f2..... h. The loss of Pa is defined as:
1 D of log (Pa(h:; n
Ld =
(3)
where Pa(h;; 0a) is the predicted distribution of the degree of node i; and ) is the ground-truth distribution. 0g represents the trainable parameters the degree predictor Pa. In this way, the degree information can be integrated to refine the node representation.
4.2 GRAPH-LEVEL IMPORTANCE LEARNING
Node-level importance learning reflects a local perspective, focusing on the importance derived from the node itself. Solely utilizing node degree as metric for node-level learning might be misleading, as nodes with similar degrees are not necessarily similar in other respects (c.g., two users in social network can have the same number of followers). A broader, more global perspective that considers attributes like "the degree distribution of a node's 's neighbors" is necessary. Such an intuition captured by the essence of Eigenvector Centrality (Definition 2). which reflects how a node's 's importance is shaped by the importance of its neighbors. Therefore, beyond learning local node-level importance, we propose to integrate graph-level importance using Eigenvector Centrality,
Definition 2. Eigenvector Centrality defines relationships with high-scoring nodes have more contribution to the score of a node than connections to nodes with low eigenvector centrality scores.
As described previously and by definition, degree centrality provides insight into a node's immediate environment, while eigenvector centrality reflects its importance relative to the entire network. Together, they offer a more comprehensive picture of a node's role within the graph, which is naturally divided into four categories. More details are shown in Appendix
To compute Eigenvector Centrality, we first obtain Amax which is the maximum absolute eigenvalue of the adjacency matrix A, and solve for the eigenvector ū:
X J- Au
This is an example of the seeenn-Dcompssttion where we decompose A into a set of eigenvectors and eigenvalues. This classic technique is powerful but may not always be numerically stable for ill-conditioned matrices" which can arise in large, sparse, or noisy networks. Moreover, it is also
An ill conditioned matrix typically has high condition number, which is the ratio of the largest to the smallest singular value. This makes numerical operations such as Inversion or Digen-Decomposition highly sensitive small perturbations in the data.
5

---

Published as a conference paper at ICLR 2025
computationally expensive for large matrices. To address this, we turn to (Truncated) Singular Value Decomposition (ED and SVD are equal if the A = A A A = O, which is usually the case for A from undirected graph, Appendix for proof). It retains only the top l singular values and vectors reducing computational cost while preserving the most important structural information:
A=UEV U
(5)
where U and V are orthogonal matrices containing the left and right singular vectors, and Σ is diagonal matrix storing the singular values. The left singular vectors in Us can be used as structural representations for each node. Specifically,, each row of the matrix Us provides aeweiddesadddiiinnaaaaaaa k-dimensional embedding that captures the most important structural properties of the graph with respect to its overall connectivity. Denoting this structural representation retrieval process function ftruncated avd that returns the truncated left singular matrix Us for a given adjacency matrix A, we can obtain the structural representation 8; for each node v; as follows:
Sg
{s1, $2, ................................ sn (U UJ U UR svv (A)
(6)
Based on this, the issue of producing importance-fusse structure representation for a specific node o evolved into how to determine the importance of each node in graph for 84 In our case, treat the structure representation Sg and graph representation Hg as two modalities-one encoding the structural properties and the other capturing the feature-hased characteristics of the graph-and use graph representation Hg to cross-attend over structural representation. By aligning the two modalities, we produce the importance-fused graph-level structural representation Sg:
--= = ( S2..., s CrossAtt(Hg:: Sg) = (W
(7)
where Wg. We. and We are the weight matrices of query, key, and value in the cross-attention mechanism, respectively. After obtaining the importance-fused structure representation S'g, inspired by CLIP (Radford et al., 2021) aligning text and image modalities, we propose a Contrastive Representation-Stuutee Struuture Pre- TreiTrainngg (CReSP) model Pe to train the node representation based structure representation. This contrastive learning objective
on the graph-level importance-fusse is designed capture both local node features and global structural roles by aligning these two complementary modalities in the same embedding space. The loss of Pe is defined as:
n
L.
(yllo(PPoorrt + Mrlog(Pa(rT (TTT((()(TTs
(0oo)):
[ra, T2, m. Finl
(8)
where y represents the index label towards the importance-fused structure matrix. ray = h48 represents the computation of similarity between h, and sj. 0g represents the trainable parameters of the CReSP model Pe.
4.3 GRAPH REPRESENTATION ALIGNMENT
Based on the pre-trained GNN encoder ft learned by our CenPre, we use the L2-norm align the structure-fusse node representation with the original one, aiming to prevent the loss of the original semantic information while learning the graph structure information The loss of graph representation alignment module is defined as:
d Σ
C, EE(G))) Σ
(f(())) f(()))
where f'(1;) and (w)))) represent the representation node v produced by the pre-trained GNN encoder fH and the original GNN encoder fo.
'Conventionally we set to explain 2 0.95 variance. 'In the preliminary experiments, we also tried other loss functions, such KI--divereence, I zooom, Cosine Distance, etc. We found that the performance of L--norm was more stable, we L--norm in method.

---

Published as a conference paper at ICLR 2025
4.4 OVERALL LEARNING OBJECTIVE
The overall learning objective of our CenPre is to train the framework by jointly minimizing the three losses derived from Node-level Importance Learning, Graph-level Importance Learning, and Graph Representation Alignment. The overall loss & is defined as:
C = X1Ca A2C. + Ash,
(10)
where hyperparameters Yy X2 and A are scaling weights to balance the losses. In this way, our proposed CenPre can effectively integrate structural information into node representations to pro- duce structure-fuse node representation by learning important information from graph structures. Meanwhile, the graph representation alignment that aligns the structure- representation using the original node representation can also prevent the loss of original semantic information due to excessive learning of structural information.
5 EXPERIMENTS
In this section, we first evaluate the performance of our CenPre compared with existing state-of-the-art (SOTA) competitors in the tasks of node classification, link prediction, and graph classification. Then, we present a deep analysis of our CenPre show its effectiveness in learning graph representation.
5.1 DATASETS AND EXPERIMENTAL SETTINGS
Dataset We evaluate the effective- ness of proposed CenPre frame- work through the tasks of node classification, link prediction, and graph classification on 13 widely used benchmark datasets. These datasets include the Citation Net- works triplet (Kipf & Welling 2017) (Cora, Citeseer, Pubmed), Amazon- Co-Purchase networks (Shchur et al. 2018) (Computer, Photo), TUD Benchmark datasets (Morris et al. 2020) (MUTAG, NCI1, PROTEINS, DD, IMDB-B, RDT-B), and two large-scale graphs from the Open Graph Benchmark (Hu et al.) 2020) (ogbn-arXiv, ogbl-Coolab). The statistics of the datasets are shown in Table We can see that these datasets span various domains, with the number of graphs ranging from 1 4,110, the average number of nodes ranging from 17.93 to 235,866 2558668,60 and the average number of edges ranging from 19.79 to 2,315,598, demonstrating the diversity and comprehensiveness of the datasets.
Table 1: Statistics of datasets.
Task
#Graphs
#Edges
Aleatuues
#Classes
Cora
Node&Linn
2,708
10.556
1,433
7
CiteSeer
Node&Link
3,327
9,104
3,703
PubMed
Node&Link
19,717
88,648
500
3
Computer
Node
491,722
Photo
Node
7,650
238, 238,162 162
745
8
arXiv
Node
169.343
2,315,598
128
40
Collab
Link
235,868
1,285,465
128
MUTAG
Graph
188
17.93
19.79
2
NCII
Graph
4,110
29.87
32.30
PROTEINS
Graph
1,113
39.06
72.82
29
2
Graph
IMDB-B
Graph
1,000
19.77
96.53
10
RDT-B
Graph
2,000
429.63
497.75
10
Baselines & Implementation Details We compare our CenPre with series of SOTA baseline models, including 1) supervised learning methods: GCN (Kipf & Welling 2017). GAT (Velickovic
al. 2018), GIN (Xu al.) 2019), and SAGE (Hamilton al. 2017); graph kernels methods:
WL Shervashidze et al. 2011) and DGK (Yanardag & Vishwanathan, 2015); 3) self-supervised learning methods: node2vec (Grover & Leskovee|
graph2vec (Narayanan al., a (017)). Info-
2016). VGAE (Kipf & Welling 2016). ARGA (Pan al. 2018), GraphMAE (Hou et al. (002)). DGI (Veličković et al. a [209)] GRACE (Zhu al. 2020), GCA (Zhu et al., 2021b). BGRL (hhakoor et 2021). CCA-SSG (Zhang et al. 2021).
Graph (Sun et al.) 2020), GAE (Kipi & |
CraphCL You et al. 2020), JOAO You et al. 2021). InfoGCL (Xu et al. (021). SimGRACE (Xia al.) 2022a), AutoGCL (Yin al. 2022). Mas (Li et al. 2023), MaskGAE, (L al. 2023).
TopoGCL (Chen et al. 2024). Patcher (Ju et al. 2023) and GPA (Zhang et al. 2024). Please refer to
Appendix for detailed information of these baseline models and Appendix D for implementation
details, which follows the evaluation protocol established by previous works (Li ct al. 2023 Hou
al. 2022
7

---

Published as a conference paper at ICLR 2025
Table 2: Experimental results of node classification. Averaged accuracy (%) over 10 runs reported. The best and second-hest results are highlighted in red and blue, respectively. A.R. is short for the average rank. The smaller the value of A.R., the higher the ranking of model performance. Results with denote the significance tests of our CenPre over the baseline models p-value < 0.05.
Methods
Cora
CiteSeer
PabMed
Computer
Photo
arXiv
A.R.J
GCN
81.50.10.20
70.30.10.40
79.00.1:0.50
86.51
92.42.1:0.22
70.40
10.8
Supervised
GAT
83.00=1..70
72.50=0.70
79:00::0.30
06.93=0.29
92.56++0.35
70.60+40:00
8.0
GAB
74.90=00440
0..60=0.50
74.20:+:.30
85. 15.10:0.40
91.00 91:00+00.10
63.60=+0.50
15.0
VGAE
76.30=t0.20
0.200:0.20
75 80:1:0400
85.80=0.300
91.50:2:0220
64.80
14.0
ARGA
77.95.10.70
64.441.
80.44.100.4
85.86.1.111
91.82.10.08
67.34:10.09
12.5
NodeProperty
81.94:00.00
0.060=00000
79.44:4:0.00
10.3
DGI
82.30.10.60
71.80:10.70
76.80.10.60
83.95 0..47
91 91.61:10.22
65.10:10.40
11.8
GRACE
81.90:10.40
71 71.20:10.50
80.60:1:0.40
06.25
92.15:10.24
78:10.0444
10.5
Self-supervised
GCA
81,80=t:0.20
71.90=0040
81.00=+:030
07.85=0.31
92.53++0.16
28:20:00200
8.8
BGRL
82.86:20.449
71.41=0.922
x2.05=::0.85
0..3
93.17=10.30
71.64=0.122
5.7
CCA-SSG
83,59-40.75
73.36=#0.2
80.81++0.38
88.74-0.28
93.14-+0114
69.22240:22
6.7
GraphMAE
84,20=t0,44
73.40=0044
81.10==0:44
89.51=0.08
93.23-+0.13
71.75=00177
3.8
Patcher
04.17:10.54
0.665:0.05
81.13:10.68
09744
81.23:1:0322
72.31::0.22
6.7
MaskGAE,
83.77.10.33
72.94.1..20
82.69.10.33
09.4410.11
93.30.10.04
70.97.10.29
4.5
MaskGAEp
84.30:10.39
73.80=10.81
83.58:1:0.45
09.54:20.06
93.3110.13
71.16:0.33
2.7
CenPre (ours)
85.15
76.94.12.12*
83.91.10.12
91.22.10.05
93.96.10..14
72.47.10.15
1.0
Table 3: Experimental results of link prediction. Average AUC, Average Precision (AP), and Hit @ 5td (%) over 10 runs are reported. Hit@ 50 measures the proportion of correct links among the top 50 predictions. The best and second-best results are highlighted in red and blue, respectively.
Methods
Cora
CiteSeer
PubMed
COLLAR
A.R.J
AUC
AUC
AP
AUC
AP
50
GCN
86.70.10.00
87.55_0.05
91.10:1.50
91.72-10.43
84.66:20.10
86.20:10.11
47.14.0.01
9.4
Supervised
GAT
86.8411.277 88.66:0.08
91.2011010
92.02-10.44
84.2110.10
86.62-10.22
10.1
GIN SAGE
86.66:10.59 87.62-0.58
92.62:10.24
92.54-10.11
84.05:0.322
86.17:10.25
10.4
1..33-11006
88.81=1.36
92.5440.87
92.70:::.02
84.98.2.65
87.12:22.95
54.63 1.12
7.3
2ode2vec 78.32.10.74
70.71
75.36:11.22
76.03-10.11
79.98-10.35
81 81.55.10.83
57.01-1..52
10
Latent
MatrixFactor
62:25:1:2211
6..20=1117
61.6513.88
61.99:1.500
68.56:1
68.23:13.13
08.96:10.29
11.5
GAE
91.09=0.01 92.83-0.03
96,40+0.01
96.50:10.02
90.52-00044
91.68:+0.05
47.14=11445
7.1
VGAE
91.40:0.011 92.60=0001
94.40:10002
94.70-10.02
90.00:0.022
92.00-10.02
1.87
7.8
ARGA
92.40:10.00
93.23-10.00
96.81
97.11110.00
91.94:10.00
93.03.10.00
2..3
6.3
Self-supervised
GraphMAL
94.8820.23 93.52=0.51
06.2410.26
95.47-0041
94.32-0.40
93.54:10.22
5.3
MaskGAE,
96.42.10.17 95.21
98.02.10.22
98. 98.18
98.75.10.04
98.66.10..6
05.84
2.8
MaskGAF,
96.45.0.118
95.95-0.221
97.8740..22
98.09-10.17
98.84.00.04
98.78:10005
65.98:10.39
2.3
CenPre (ours)
97.44:10.85
96.05
99.02
99.04
99.82.10.10"
99.62.10.10*
66.03 0.22
1.0
5.2 COMPARISONS WITH BASELINES
Node Classification Table shows the results of node classification. Our CenPre overall outper- forms the SOTA baseline models, in which our CenPre achieves the best performance on all datasets. This demonstrates the effectiveness of the proposed CenPre in node classification. Further, our CenPre performs best on both the Cora dataset with 2,708 nodes and the arXiv dataset with 169,343 nodes, indicating that our CenPre can be effective on datasets of different types and sizes.
Link Prediction We further evaluate the performance of our CenPre in link prediction and report the comparison results with SOTA baseline models in Table Our CenPre achieves overall better performance than the baseline models, reaching optimal performance in all datasets. This indicates that leveraging the node importance based on the notion of Centrality can improve the representations of nodes in a graph, thereby leading to better link prediction performance.
Graph Classification Table 4 shows the experimental results of graph classification. We can see that our CenPre consistently outperforms the baseline models on all datasets. This verifies the effectiveness of CenPre in graph classification, indicating that the proposed Centrality-guidee method can improve the learning of the entire graph based on the improvement of node representations, therefore achieving optimal performance in graph classification. Further, CenPre performs
8

---

Published as a conference paper at ICLR 2025
Table 4: Experimental results of graph classification. Averaged accuracy=std. (%) over 10 runs are reported. The best and second-best results are highlighted in red and blue, respectively.
Methods
NCTI
PROTEINS
DD
MUTAG
IMDB-B
RDT-B
A.R.J
GCN
76,29:
75.17=33.3
73.26+24.46
19.81+1.58
57.35++4.04
81.30=6.93
12
Supervised
GAT
74.90=11.72
74.724:4.01
17.30+13.68
78.89+2.05
54.60:7.45
72.70=2.30
12.7
SAGE
7..73::1.34
74.01114.27
75.7813.91
78.75:11.18
58.9511..74
53.10:5.40
12.7
WT. 60.31:10.46
72.92.10.56
76.44:12.35
80.72.1..00
72.30:13.44
68.82:0.411
11.2
Kernel
DGK
81.01=1.006
73.30: 82
74.85::0.74
87,44
66.96:20.56
78.04=0.39
10.3
node2vee
54.89+11661
57,49+33.57
12.63++10,20
56,40+22.80
69.70=4.10
16.2
Vee
73,22+t:181
73.30::2.00
70,3242.32
83.15:::9.25
71.10::0.54
25.78=1100
13.1
InfoGraph
1..20.1:.006
74.44.0.31
7..24
19.01.11.13
73.03.10.87
82.50 1.42
9.3
GraphCLL
77.87:00.41
74.39:10.45
78.62:+0.40
86.80:1:1.34
71.14::0.44
89.53=0.84
8.2
JOAD
78.07.10.47
74.55.10.41
77.32.10.54
87.35.1:1.02
70.21
85.29 1.35
9.2
Self
InfaGCT
80.20-1:060
11.20-+-1.300
10:10::0.90
10.5
GraphMAE
80,40=t0.30
15.30++0.39
18.1
75.52=
88.01
7.5
SimGRACE
79.12-t0.44
05.35-
77.44+1111
89.01++1.31
71.30:00.77
09.51=0.89
6.3
AutoGCL
82.00=1:.229
05.80=+0.36
77.57=0.60
88 18.64
72.32++0.93
88.58= 1.49
5
TopoGCL
81.30:00.27
77.30:20.89
09.13=00.35
90.09:+0.93
74.67=00.32
90.40=0.53
2.8
GPA
80.42:10.44
75.94:10:25
79.90-10.35
89.68
74.64:10.35
89.32:0.38
5.3
CeaPre (ours)
88.13=0.91"
80.25=0..7"
85.18=1.37"
94.74=0.48"
78.05=11221
91.20=0.50
1.0
consistently better than TopoGCL (Chen et 2024) which considers the topological information of the graph. This denotes that leveraging node-level and graph-level importance can improve the learning of graph structure when modeling a graph, thus improving the performance of graph classification.
al.
5.3 ANALYSIS OF OUR CENPRE
Table 5: Experimental results of the ablation study. A
denotes the performance drop relative to the full CenPre. "w/o SVD" means the adjacency matrix A is used di- rectly the structural representation, and AUC is used as the evaluation metric for Cora-Link.
Ablation Study We conduct an ablation study to analyze the impact of each module of the CenPre on performance. The results are reported in Table 5 We can see that whether using only node-level structure (w/ Ca) or graph-level structure (w/ Lz), the performance of the model has significantly decreased. This verifies that we need to simultaneously explore the different impor- tance of nodes from both local and global perspectives in order better learn the structural information of the graph. In ad- dition, the removal of graph representation alignment (w/o L.)) seriously degrades the performance of our CenPre. This indicates that it is necessary to align the node representation when learning structural information, since can prevent the loss the graph semantic information, especially for node classification. Further, the removal of node-level importance learning (w/o La) and graph-level importance learning (w/o L.) can lead to considerable performance degradation, which demonstrates that learning node importance from both node and graph levels can make full use of the important structural information of node a graph, thus improving the model's performance. The performance of "w/o SVD" shows that the removal of SVD noticeably degrades the performance of our CenPre. This implies that exploiting SVD to produce the structure representation based on important singular values and eigenvectors can help the model better learn the graph's structural information.
Methods
Cora-Node
Cora-Link
|MUTAG-Grphl
CoaPre
85.1540.449
0.00
95.05=0.18
0.00
94.7422.48
0.00
w/ La w/ L.
81.43:2.330
3.72
92.80= 1.05
2.25
91.62-0.005
3.12
79.91+0.22
5.24
93.17=0.65
1.88
90.38
4.36
who Ca
80.40:00110
4.75
94.08=0.29
0.97
86.84-0.133
7.9
84.21
0.94
94.07-0.544
0..26
wlo C,,
78.63-10.50
7.12
91.29 1.57
3.76
89.47:12.55
5.27
w/o SVD
83.4540.61
1,70
93.72=0.22
1.33
93.52-0.42
1.22
Analysis of Generalizability To analyze the generalizability of our CenPre different graph autoencoders, we conduct comparative exper- iments based on different graph autoencoders and report the results in Table 6 We can see that the proposed CenPre can directly adapt to different graph autoencoders and achieve vary- ing degrees of performance improvement, which validates the generalizability of our CenPre in
Table 6: Experimental results of using different graph autoencoders on the Cora dataset.
Methods
Original
w/ CenPre
Improvement
GAB
74.90=10:40
81 56
6.66
YGAE
76.30:10.20
18.30=11115
2.00
ARGA
77.95:10.70
80:73:0.27
2.78
DGI
82,30=:0.60
83.11=00544
0.81
CenPre (ours)
05.15=20.49
0.00

---

Published as a conference paper at ICLR 2025
(a) graph
(b) original
(c) w/ node
(d) CenPre
Figure 2: The T-SNE 3D plots of the extracted nodes during different pre-training stages.
(a) original
(b) mio node
(c) who graph
160 mil regularieation
(el Centre
Figure 3: The T-SNE 2D plots of all the test samples from the CORA dataset.
graph pre-training. In addition, it can be noted that CenPre, which uses the original node represen- tation, achieves better performance than those that use graph autoencoders. This implies that using the original representation can better assist our CenPre learning the structural information of the graph, thereby obtaining better node representations. Furthermore, this also indicates that exploring better methods for graph autoencoders may further enhance the learning of graphs.
Analysis of Node Representation To analyze how our CenPre improves the representation of nodes, we select node from Cora data and retain first-order neighbors to analyze the changes in their representation different learning stages. The results are shown in Figure We can see that, the original representations nodes are divergent and the correlation between them cannot be observed. After node-level importance learning, Furthermore, through our complete CenPre, important nodes (4, 6, 7) are further aggregated (Figure (d)). This indicates that our CenPre can learn the similarity importance between nodes based Centrality, thereby improving the representation of nodes.
important nodes gathered together.
Visualizations To qualitatively demonstrate how our CenPre improves the node representations, Figure shows the t-SNE (van der Maaten & Hinton 2008) visualization of node representations from original representations (a), the variants of our CenPre (b), (c) and (d), and our CenPre (e). We can observe that the original node representations largely diffuse and overlap between different labels. The variants of our CenPre can show differences between different labels, which denotes that exploring preferable methods to learn better node representations is key to improving node classification. Further, the node representations derived by our CenPre can be better separated from different labels. This indicates that our CenPre make full use of the node importance based on Centrality, and further improve the representations of nodes based on the representation alignment, therefore leading improved node representations.
CONCLUSION
In this paper, we propose CenPre, Centralitt-guudder Pre-training framework for node representation learning. CenPre integrates structural information into graph representation by using node importance based on Degree and Eigenvector Centrality while preserving semantic information through graph alignment module. Experiments on real- worldworld datasets demonstrate its superiority over state-of-the art models in node classification, link prediction, and graph classification.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We sincerely thank the anonymous reviewers for their insightful feedback and valuable suggestions, which have significantly enhanced the quality of this work. This work was partially supported by Hong Kong RGC GRF No. 14206324, CUHK direct grant No. 4055209, CUHK Knowledge Transfer Project Fund No. KPF23GWP20, National Natural Science Foundation of China 62176076, Natural Science Foundation Guangdong 2023A 151501 2922, Shenzhen Foundational Research Funding JCYJ202208 88 102415032, and the Major Key Project of PCI (C12202309, Guangdong Provincial Key Laboratory of Novel Security Intelligence Technologies 2022B 211000005, the UK Engineering and Physical Sciences Research Council through a New Horizons grant (EP/X019063/1) and by UKRI Impact Accelcration Accounts.
REFERENCES
Pedro H. C. Avelar, Henrique Lemos, Marcelo O. R. Prates, and L. Lamb. Multitask learn- ing on graph neural networks learning multiple graph centrality measures with unified network. In International Conference on Artificial Neural Networks, 2018. URL https
7/api www.steiiicchooarcccoooooo ott.a//cc........ooooooooaaaaaaa
Jinheon Back, Dong Bok Lee, and Sung Ju Hwang. Learning to extrapolate knowledge: Transductive few-shot out-of-graph link prediction. Advances in Neural Information Processing Systems, 33: 546-560, 2020.
Alex Bavelas. Communication patterns in task-oriented groups Journal of the Acoustical Society of America, 22:725 1950. URL https: www.seeeanntsoo.m weeemnniisccoola..ooooo wwt.oooll.aaorooooouussosee
121849458
Piotr Bielak, Tomasz Kajdanowicz. and N. Chawla. Graph barlow twins: A self-supervised
representation learning framework for graphs. ArXiv, 0bs/2106.024666 2021. URL https:
//api. www.stettnttnoooaaaoooeoccccccaa
Phillip Bonacich. Factoring and weighting approaches to status scores and clique identification. Jour- nal of Mathematical Sociology, 2:1 2:113-120, 1972. htt.ttts:: http:///c...smmmticcccchohhooo
org/Co Crr//orp:TTD: 120637488
Phillip Bonacich. Some unique properties of eigenvector centrality. Social networks, 29(4)5555-564 2007.
Yuzhou Chen, Jose Frias, and Yulia R Gel. Topogel: Topological graph contrastive learning. In
Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 11453-11400 2024.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs arXiv preprint arXiv: 1805. 11973, 2018.
Vijay Prakash Dwivedi and Xavier Bresson. generalization of transformer networks to graphs. 09699
CoRR, abs/2012.09669, 2020.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. ArXiv, 103/1903, 2019. URL httth:tt///aaa www.eticsccoo.t..oo 70349949
Leonard M. Freeman. A set of measures of centrality based upon betweenness. In Sociometry, 1977.
URL https://app. wwwant htt.:///eecccco.....oooooo/ooo/p
62597900
Linton C. Freeman. Centrality in social networks conceptual clarification. Social Networks, 215-239, 1978. URL httth: http:://waaaaaaaaaaaaaocccoa.ooa
Alberto García- Durán and Mathias Niepert. Learning graph representations with embedding prop- agation. ArXiv, abss/7110003599 2017. URL http::///aa..eennnnecccccc..aaa .rrg/
CorpusTD:3974155

---

Published as a conference paper at ICLR 2025
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SICKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Sys- tems 30: Annual Conference Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1024-1034, 2017. URL ht.tttss:: /ttp::::s//ppppeeddeeee
neur wwweeurrpp....... cc/ .ttml
2oper/2017/0 201 http://///.aaaeeeeeooaaaaaaaaaa.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-viow representation learning on graphs. In International conference on machine learning, pp. 4116-4126. PMLR, 2020.
Yifan Hou, Jian Zhang. James Cheng, Kaili Ma, Richard TB Ma, Hongzhi Chen, and Ming-Chang Yang. Measuring and improving the of graph information in graph neural networks. In International Conference on Learning Representations, 2019.
Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, C. Wang. and Jie Tang. Graphmae: Sclf-supervised masked graph autoencoders. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022. U //api sww.nestscemtiiccccchooooo
orq/CozpusID: 248987361
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22 18:22118-2222 18-22113, 2020.
Weihua Hu Bowen Liu", Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference on Learn- ing Representations, 2020. UtL/tttps: http:ppp///pppppeiiieeee net/ forum ietoormmiiiee Hid=HJIWWJSFDD
Ziniu Hu, Changjun Fan, Ting Chen, Kai-Wei Chang, and Yizhou Sun. Pre-training graph neural networks for generic structural feature extraction. CoRR, abs/1905. 137288 2019a. URL http
13728
Ziniu Hu, Changjun Fan, Ting Chen, Kai-Wei Chang, and Yizhou Sun. Pre-training graph neural networks for generic structural feature extraction. ArXiv, abs//995.13733 2019b. |RLhttps
//api. wew.sssemaniccccccoc
Cttg/CorpussDD.. ID: 173188920
Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai-Wei Chang, and Yizhou Sun. Gpt-gnn: Generative pre-training graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 1857-1867, 2020.
Wei Jin, Tyler Derr, Haochen Liu, Yiqi Wang, Suhang Wang. Zitao Liu, and Jiliang Tang. Self- supervised learning on graphs: Deep insights and new direction. ArXiv, 0bs/2006610144 2020.
URL https:://pppp.... www.:pppsssmaaassssscccccc http:aaww.....aaa....oooooo/oaaa
Wei Jin, Xiaorui Liu, Xiangyu Zhao, Yao Ma. Neil Shah, and Jiliang Tang. Automated self-supervised learning for graphs. ArXiv, abs/2106.05470, 2021. URL BtRL:ttps:/// /api....... www.nticscooooo....o....
org/CorpusID: 235390683
Mingxuan Ju, Tong Zhao, Qianlong Wen, Wenhao Yu, Neil Shah, Yanfang Ye, and Chuxu Zhang. Multi-task self-supervised graph neural networks enable stronger task generalization. ArXiv, abs/2210.02016. 2022. URL URL hwl.htttppe//ppp..sennntiicaaai wwtpraacccccooooooorooororppeeee 252715492
Mingxuan Ju, Tong Zhao, Wenhao Yu, Neil Shah, and Yanfang Ye. Graphpatcher: Mitigating degree bias for graph neural networks via test-time augmentation. Advances in Neural Information Processing Systems, 36, 2023.
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18:39 -3.99-4311 1953. URL https: /appi. semant www.eaanntsccccsloooomcooooooo ar trtp/cooooa.....r//rppsssstttt
12

---

Published as a conference paper at ICLR 2025
Dongki Kim, Jinheon Baek, and Sung Ju Hwang. Graph self- supervieed learning with accurate discrepancy learning. In 36th Conference on Neural Information Processing Systems, NeurIPS 2022. Neural Information Processing Systems, 2022.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization
CoRR, abs/1412.6980,, 2014. URL httpt://ppp.... sewanticschooar..oooooo wtt.pooo......rooooooss..... 6628106
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint 1 2016.
Thomas N. Kipf and Max Welling. Semi-supervvsed classification with graph convolutional networks. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24- 26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL /nttps://operrvviiie net /
SJJ4ayYg]
Jintang Li, Ruofan Wu, Wangbin Sun, Liang Chen, Sheng Tian, Liang Zhu, Changhua Meng, Zibin Zheng, and Weiqiang Wang. What's behind the mask: Understanding masked graph modeling for graph autoencoders. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1268-1279, 2023.
Massimo Marchiori and Vito Latora. Harmony in the world. Physica A-statisticaa Mechati and Its Applications, 285:539-540 546, 2000. Ltl.hhteee////pp.eeeeoooooooooor
Corpus I ID: : 10523345
Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Fast approximations of betweenness centrality with graph neural networks. Proceedings of the 28th ACM International Conference on Infor- mation and Knowledge Management, 2019. URL httts:://aaaatt semanticcchola..........
Corpus ID: 207 758212
Keith McNulty. Handbook of graphs and networks in people analytics: with examples in R and python. Chapman and Hal//CRC, 2022.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL www. www.ggaaaaeeeingg....
Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs. arXiv preprint arXiv:1707.05005. 2017.
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversar- ially regularized graph autoencoder. ArXiv, abs/1802.04407, 2018. URL https://api
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Ed- ward Yang, Zach De Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. ArXiv, abs/1912.01773. 2019. URL htt.::tts:seee
orq/Corpus ID: 202786778
Bryan Perozzi, Rami AI-Rfou, and Steven S. Skiena. Deepwalk: online learning of social representa- tions. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 2014. UtL/nttss: //ap:::/ap..... www.tt org.
ottpr//cccc.oaaa.oooo/oooooossla :o:pp :D: 3051291
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. International conference on machine learning, pp. 8748-8763, PMLR, 2021.
Gert Sabidussi. The centrality index of a graph. Psychometrika, 31:581-603, 603, 1966. URL https 7/api sema nt caccool ar. htt.ccho......oooooooooooi111111
13

---

Published as a conference paper at ICLR 2025
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 18100886, 2018.
Nino Shervashidze, Pascal Schweitzer, Brik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehme graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Weijing Shi and Raj Rajkumar. Point-gnn: Graph neural network for 3d object detection a point cloud. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pp. 1711-1719, 2020.
William Shiao, Zhichun Guo, Tong Zhao, Evangelos E. Papalexakis, Yozen Liu, and Neil Shah.
Link prediction with non-contrastive learning. ArXiv, 113322 2022. URL https
//api. semanntccccctic wrt.CorrpssDDiea....c 2540044229
Fan- Yun Sun, Jordan Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. In Interna- tional Conference on Learning Representations, 2020. URL
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L. Dyer, Rémi Munos, Petar Velivckovi'c, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. In International Conference on Learning Representations, 2021. URL
httpps://api swwant insthooicscchlaa wwtp/oorgg.ooeooooo :o: :4:
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, (066):579-2605- 2008.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL httpa////oeeeeeeeeeeeeeeeoooe
Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2019.
net/
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, Juncheng Liu, and Bryan Hooi. Nodeaug: Semi-supervised node classification with data augmentation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 207-217, 2020.
Jun Xia, Lirong Wu, Jintao Chen, Bozhen Hu, and Stan Li. Simgrace: A simple framework for graph contrastive learning without data augmentation. In Proceedings of the ACM Web Conference 2022, pp. 1070-1079, 2022a.
Jun Xia, Yanqiao Zhu, Yuanqi Du, and Stan Li. A survey of pretraining on graphs: Taxonomy, methods, and applications. arXiv preprint arXiv:2202.074 07899, 2022b.
Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang. Infogel: Information- aware graph contrastive learning. Advances in Neural Information Processing Systems, 34: 30414-30425, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https //openreview. net www.://oroomidrrrre......
Pinar Yanardag and SVN Vishwanathan. Deep graph kemels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Yihang Yin, Qingzhong Wang, Siyu Huang, Haoyi Xiong, and Xiang Zhang. Autogel: Automated graph contrastive learning via learnable view generators. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 8892-8900, 2022.
14

---

Published as a conference paper at ICLR 2025
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 33: 5812-5823, 2020.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In International Conference on Machine Learning, pp. 12121-12132. PMLR, 2021.
Mohammed J Zaki and Wagner Meira. Data mining and analysis: fundamental concepts and algorithms. Cambridge University Press, 2014.
Hengrui Zhang, Qitian Wu, Junchi Yan, David Paul Wipf, and Philiip Yu. From canonical correlation analysis to sulf-supprvised graph neural networks. In Neural Information Processing Systems, 2021. URL [Rttt:ts://appp
semant coscoollhaec Cotprroo//oorroo::23336333
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
Xin Zhang, Qiaoyu Tan, Xiao Huang, and Bo Li. Graph contrastive learning with personalized augmentation. IEEE Transactions on Knowledge and Data Engineering, 2024.
Yizhen Zheng, Shirui Pan, Vincent Cs Lee, Yu Zheng, and Philip S Yu. Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination. In Advances in Neural Information Processing Systems, 2022.
Yanqiao Zhu, Yichen Xu, Feng Yu, Q. Liu, Shu Wu, and Liang Wang. Deep graph contrastive repre- sentation learning. ArXiv, abs/2006.04110 04111, 2020. httptt:::///// api. semanticscholaat :tc//oorpus11::2155330
Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Yuanqi Du, Jieyu Zhang, Qiang Liu, Carl Yang, and Shu Wu. A survey on graph structure learning: Progress and opportunities. arXiv preprint arXiv:2103.03036, 2021a.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. Proceedings of the Web Conference 2021, pp. 2069-2060 2021b.
A APPENDIX
A CENTRALITY MEASURES
Centrality is key concept in network analysis used to identify the most important or influential nodes within graph. Different centrality measures capture various aspects of node's 's importance. ranging from its immediate connections to its role in facilitating communication between other nodes. These measures help in understanding the structure of the graph, the flow of information, and the relative significance of individual nodes in maintaining the overall connectivity. Below, we introduce several commonly used centrality measures:
Degree Centrality (Freeman 1978) counts the number of direct connections a node has. Nodes with higher degree centrality are considered more locally important due to their numerous direct interactions within the network. For node v; the degree centrality is given by:
CD(Us) EE
(11)
where Aij is the entry in the adjacency matrix A, indicating the presence or absence of an edge between nodes and j.
Eigenvector Centrality (Bonacich) 1972) assigns relative scores to nodes based on the
principle that connections to sigh-scoring nodes contribute more to the score of the node itself. It captures both direct and indirect influences in the network. For node v, the eigenvector centrality is given by:
1 ス EACCEE(U)
Cε(U:)
(12)
15

---

Published as a conference paper at ICLR 2025
where À is the largest eigenvalue of the adjacency matrix A.
Betweenness Centrality (Freeman, 1977) quantifies the number of times a node acts as bridge along the shortest path between two other nodes. For a node v,s betweenness centrality is given by:
CB(U))=
(13)
Ost
where ast is the total number of shortest paths from node 8 to node I, and a (1;) is the number of those paths that pass through node 14-
Closeness Centrality (Bavelas) 1950, Sabidussi 1966) measures how close node is to all
other nodes in the network. For a node 04 closeness centrality is defined as:
Cc(u) E, d( U2)
(14)
where d(u;, Uj) the shortest path distance between nodes v, and Vy-
PageRank Centrality is a variant of eigenvector centrality that evaluates the importance of node based on the quality and quantity of incoming connections, where connections from more important nodes weigh more heavily. The PageRank score Pf(()) for node o is given by:
1 d PR(U)) N
PR(y3)
+
Σ
(15)
(W(e)))
(EN(v))
where the damping factor (typically set to 0.85), N the total number of nodes, and (wş) is the set of neighbors of node vzz
Katz Centrality (Katz 1953) extends degree centrality by considering the total number of walks between nodes. It is defined as:
Ck(u;) = Σ A
(16)
where a is constant (decay factor) and /3 is an additional weight applied to each node, allowing for paths of different lengths to contribute to the centrality.
Harmonic Centrality (Marchiori & Latora 2000) a variation of closeness centrality that computes the sum of the reciprocals of the shortest path distances from one node to all other nodes. It is defined as:
CHi) = Σ d(v;, Uz)
(17)
where d(v;, Uz) the shortest path distance between nodes v, and Vg.
Table provides detailed comparison of node types based on Degree Centrality and Eigenvector Centrality, highlighting their roles and characteristics in network structures. The table categorizes nodes into four distinct types depending on their local and global importance, as measured by high or low values of these centrality metrics. Each category is accompanied by a description of the node's structural characteristies within the network and an illustrative example from social networks, offering a practical understanding of how centrality measures reflect different types of influence and connectivity in real-world scenarios.
B EICEN-DECOMPOSITION (ED) AND SINGULAR VECTOR DECOMPOSITION (SVD)
Theorem B.I. ED and SVD of a matrix are equivalent if and only if A symmetric positive semi-definite, i.e., AT AAAZ 0.
Proof. Given a matrix A E Rnnn the SVD of A is written as:
= UEVT
(18)
where:
16

---

Published as a conference paper at ICLR 2025
Degree
Eigen
Node Characteristics
Examples Social Network
High
Low
A node connected to many other nodes that are highly central. Im- portant locally but not globally.
A celebrity with many followers but most of those followers are inactive non-influential accounts.
Low
High
A node with few direct connections but connected to highly central nodes. Important globally but locally.
A journalist or analyst who is fol- lowed by a few highly influential pub- lic figures or news organizations.
High
High
A node that is both locally and glob- ally important, with many connec- tions and highly central neighbors.
A popular politician who has many followers who themselves influen- tial, such as other public figures.
Low
Low
A node with few connections and low global importance. Neither locally nor globally important.
A regular person with few followers, none whom are influential or cen- tral.
Table 7: Comparison of Degree Centrality and Eigenvector Centrality for Different Node Types and their examples in social networks.
U R is orthogonal matrix (i.e., UTU 1),
I xxn x is an orthogonal matrix (i.e., VTV = I),
Σ E R is a diagonal matrix containing the singular values d1 02, 02,..., on where a; 2 0.
The ED matrix E Rax" " is given by:
A QAQ-1
(19)
where:
Q R is an invertible matrix whose columns are the eigenvectors A,
A E Rax is a diagonal matrix whose entries are the eigenvalues \1 An.
We want to establish the conditions under which the SVD and ED matrix A are equivalent. Specifically, we need to check under what conditions:
USVT = QAQ-1
(20)
For the two decompositions be equivalent, the matrix A must be symmetric, which implies that the left and right singular vectors are the same:
A=A -- UXUT
(21)
In SVD, the singular values o; in Σ are always non-negative. For the cigenvalues X the ED to match the singular values, all eigenvalues must be non-negative as well. This requires that A be positive semi-definite. For SVD and ED to coincide, the matrix Q the ED must be orthogonal, i.c. Q T. This occurs when the eigenvectors of A are orthonormal. In this case, Q QT. and the ED becomes:
A = QAQ
(22)
Thus, for A have orthonormal eigenvectors, must be symmetric. In conclusion, the SVD and ED of matrix A are equivalent if and only if:
A is symmetric, i.e., A=
A is positive semi-definite.
The eigenvectors of A are orthonormal.
17

---

Published as a conference paper at ICLR 2025
In this case, the SVD and ED both yield the same decomposition:
UEU QAQ'
(23)
where Σ A, and the columns of (in SVD) and Q (in ED) are the same orthonormal eigenvectors of A.Thus, SVD and ED are equivalent when A is symmetrie and positive semi-definite.
C BASELINES
We compare and evaluate our CenPre framework with series of baseline models, which are grouped by graph kernel methods, graph supervised learning methods, and graph self-supervised learning methods. The more detailed introduction of the baseline models is as follows:
Graph Kernels Methods:
WL (hhervashidze al. 2011 measures graph similarity by iteratively refining node labels through aggregation of neighboring node labels, capturing graph structure and preserving node attribute information.
DGK (Yanardag & Vishwanathan 2015) uses neural networks to learn representations of subgraphs and combine them to compute a similarity score, enabling more expressive and flexible graph comparisons for various graph analysis tasks.
Graph Supervised Learning Methods:
GCN (Kipf Welling 2017) uses spectral graph theory to aggregate neighboring node features, learning new node representations for tasks like classification and link prediction.
GAT (Velickovic et al. 2018) uses an attention mechanism to assign weights to neighboring nodes, computing weighted sums of their features to capture complex relationships for tasks where neighbor importance varies.
GIN (Xu et al. 2019) aggregates node features by summing a node's features with its neighbors' and applying an MLP, capturing local structure and complex feature interactions for effective node and graph classification.
SAGE (Hamilton et al. 2017) generates node embeddings by sampling and aggregating neighborhood features, enabling it to generalize to unseen nodes and graphs for scalable node classification and link prediction.
Graph Self-supervised Learning Methods
GAE (Kipf& & Welling 2016) encodes nodes into latent embeddings and reconstructs the
graph structure to learn meaningful representations for tasks such as node classification and link prediction.
VGAE (Kipf & Welling 2016) extends the GAEs with variational inference to learn prob- abilistic latent variable models, providing robust and expressive node embeddings for graph-based tasks such as link prediction and anomaly detection.
ARGA (Pan et al. 2018) enhances GAEs by incorporating adversarial training, ensuring more robust and discriminative node embeddings for graph tasks like node classification and link prediction through adversarial regularization.
GraphMAE (Hou et 2022) leverages masked node feature reconstruction to learn rich and informative node embeddings, enhancing performance on downstream graph tasks such as node classification and graph classification.
MaskGAE (Li al. 2023) applies masking and reconstruction strategies learn meaningful graph representations, enhancing performance on tasks such as node classification and link prediction.
DGI (Veličković et al. 2019) maximizes mutual information between local and global graph representations, producing highly expressive node embeddings that excel tasks such as node classification and graph classification.
18

---

Published as a conference paper at ICLR 2025
GRACE (Zhu al. 2020) leverages contrastive learning to maximize agreement between different views of the same graph, resulting in robust and informative node embeddings for various graph-baser tasks.
GCA (Zhu et al. 2b2 enhances contrastive learning by incorporating adaptive augmenta- tion strategies, yielding discriminative and robust node embeddings for diverse graph-related tasks.
BGRL Thakoor et al. 2021 learns graph representations by leveraging a bootstrapping mechanism to predict target network outputs, producing effective node embeddings for tasks such as node classification and link prediction without the need for negative sampling.
CCA-SSG (Zhang et al. 2021 utilizes canonical correlation analysis to maximize agreement between different graph views, generating high-quality node embeddings for downstream tasks such as node classification and clustering.
node2vec (Grover & Leskoved 2016) uses biased random walks to generate node sequences, which then used with the Skip-gram model produce continuous node embeddings for downstream tasks like node classification and link prediction.
graph2vee (Narayanan et al. 2017) uses the Skip-gram model to generate continuous embeddings, capturing structural and global graph characteristics for downstream tasks.
2020) maximizes mutual information between graph-level and substructure-Ievel representations, resulting in informative embeddings for downstream graph classification and clustering tasks.
InfoGraph (Sun et al.
GraphCL. You et al. 2020) designs four contrastive learning with graph augmentations to capture rich and robust graph representations, improving performance on tasks such as graph classification and clustering.
202 dynamically optimizes data augmentations to enhance contrastive learning, producing robust and generalizable node embeddings for various graph tasks.
JOAO (You et al.
InfoGCL (Xu et al. 2021) combines contrastive learning with mutual information maxi- mization to enhance node and graph-level embeddings, yielding improved performance on various graph-based tasks.
Patcher (Ju et al. 2023) mitigates degree bias in Graph Neural Networks through test-time augmentation, enhancing the robustness and generalization of graph representations for various graph-based tasks.
SimGRACE (Xia et al., 2022a) enhances graph contrastive learning by leveraging similarity- based augmentations, producing robust node and graph embeddings for improved perfor- mance on downstream tasks.
AutoGCL Yin et al. 2022) employs learnable view generators to create optimized aug- mentations, leading robust and effective graph embeddings for various downstream
tasks.
TopoGCI. (Chen et al. 2024 leverages topological invariance and extended persistence capture higher-order substructures, enhancing graph representations and delivering sig- nificant performance gains in unsupervised graph classification, particularly in biological, chemical, and social interaction graphs.
GPA (Zhang al., 2024) customizes augmentation strategies for each graph based its topology and node attributes, enhancing representation learning and outperforming state-of-the-art models across diverse benchmark datasets.
NodeProperty (Jin et al., 2020) combines tasks such as clustering and node distance prediction to learn robust structural embeddings.
D MORE DETAILS OF EXPERIMENTAL IMPLEMENTATION
For node classification and link prediction tasks, we use a 2-layer GCN (Kipf Welling, 2017) the encoder for self- supervueer pretraining under the CenPre framework. increasing to 4 layers for the arXiv (Hu et al. 2020) dataset. After pretraining, we freeze the encoder to extract node embeddings, which then input into 2-layer MI.P for classification and prediction. Results
19

---

Published as conference paper at ICLR 2025
Table 8: Experimental implementation for node classification, link prediction, and graph classification. In node classification tasks, we Hidden Size to 64 for the Citation Networks, 128 for the Amazon Co-Buy, and 512 for the XrXiv dataset, which has 4-layer MLP as the downstream classifier.
Parameter
Description
Node Class.
Link Prod.
Graph Class.
LR
Learning Rate
0.001
0.001
0,001
T/2
Weight Decay
Se.4
Early Stopping Patience
15
15
15
C.A.
Early Stopping Min-Delta
1e-5
16-5
1o-5
Ps
Leurning Rate Scheduler Patience
8
B
Batch size
128
128
1
K
Number GNN Layers
2
M
Number of ML. Layers
2/4
2
da
Hidden Layer
64/128/512
128
À1
Scaling Weight of Node-Level Loss Luode
1
An
Scaling Weight of Graph-Level Loss graph
1
Ag
Scaling Weight of Regularization Loss Ereg
5
F
Training epochs
100
100
300
nd
Dropout Ratio Pooling Function
0.2
POOL()
menn
reported as mean and standard deviation over 5 runs. For graph classification, we use a GIN (Xu et al. 2019) encoder instead, which is commonly used in previous graph classification works. we use the Adam (Kingma & Ba 2014) optimizer with an initial learning rate of ir 0.01. The balancing hyperparameters for loss components are set to Å =, A2 = 1, and À3 = 5, determined through pilot studies. For model parameters, use grid search find the optimal parameter combination. For the three hyperparameters Å₁ X2, and λą, in preliminary experiments, we found that when these three hyperparameters
within reasonable range of values, the performance of the model will only fluctuate within certain range. When hyperparameters are set to A = 1, A2 1, and λ 5, the model's performance is optimal. Therefore, we them to the same scale.
A2 and X 5, also making
Our framework is built PyTorch (Paszke al. 2019) and PyTorch Geometric (Fey & Lenssen 2019), leveraging their datasets and functionalities. Experiments are conducted on an Intel(R) Xeon(R) Gold 6248R CPU at 3.00GHz and an Nvidia Tesla V100 GPU with 32GB VRAM. Table shows all relevant parameter settings for our experiments.
E COMPLEXITY ANALYSIS
To analyze the computational requirements of CenPre, consider the complexity of its iterative operations during training while treating the truncated-SVD as a pre-computation step. The precom- puted structural representations reused throughout the training process, and their computation does not contribute to the iterative complexity of the framework.
E. SPACETIME COMPLEXITY OF CENPRE
The space complexity of CenPre during training is determined by:
The node embeddings, are stored as matrix size O(nd), where n is the number of nodes and d is the dimensionality of the embeddings.
The adjacency matrix A, which has O(EE) space complexity for sparse graphs, where E is the number of edges.
The cross- mros-aatention mechanism, which requires storing O(n?) attention weights during alignment.
Combining these, the overall space complexity of CenPre is:
O(nd + F 1 +
(24)
The time complexity of CenPre's iterative operations during training is follows:
20

---

Published as a conference paper at ICLR 2025
Computing node degrees from the adjacency matrix A has O(EE) complexity. Training the degree predictor Pa for n nodes requires (nd) operations per iteration.
Node-level importance learning:
Graph-level importance learning: The cross-attention mechanism aligns graph and structural representations, incurring O(1dd) complexity due to pairwise attention calculations.
Graph representation alignment: Computing the Ly-norm alignment between structure-fused and original embeddings requires (nd) operations.
The total time complexity per training iteration is:
O( nd + n²d)
(25)
Note that the truncated-SVD operation is considered preprocessing step and involves decomposing the adjacency matrix to obtain the top & singular vectors. Its time complexity O(kr)) and space complexity is Okk)), where & is the number of retained singular values. This cost does not contribute to the complexity of iterative training and is incurred only once.
E.2 TIME COMPLEXITY COMPARISON WITH OTHER METHODS
In this subsection, we provide concise summary of the theoretical time complexity of other methods.
GraphCL costs O(L + nd + N2d) per iteration. This includes Eld") for the GNN encoder over L layers, (ndd) for the projection head, and (N) for contrastive loss computation with minibatch size N. Graph augmentation adds minor costs (O(n) to O(EE,))
GraphMAE consists of three main components. Masked feature reconstruction, including masking and re-masking, incurs O(n) complexity for nodes. The GNN encoder and decoder operate over layers with a complexity of (LL)E)d)) where [E] the number of edges and d is the embedding dimension. The scaled cosine error computation for feature reconstruction adds O(nd). Thus, the overall time complexity per iteration is O(L)Eld2 + nd).
MaskGAE per iteration includes ( for the GNN encoder processing the un- masked graph over layers, E( d) for the structure decoder reconstructing masked edges, and ((nd) for the degree decoder approximating node degrees, where E and Emask] are the numbers of unmasked and masked edges, respectively. Overall, the complex- ity is ((L + | (d + nd).
TopoGCL includes three main components. Extended persistence computation, involving simplicial complex operations, has a complexity of O(N3) for N nodes. The GNN en- coder, applied over L layers, incurs OLLEEdd) for [E] edges and embedding dimension d. Contrastive loss computation for minibatch of size M adds O(M2d). Thus, the overall complexity is O(N3 + E| + M2d), with extended persistence dominating for dynamic graphs.
AutoGCL incurs (( for the GNN-based view generator and encoder operating over L layers with EE| edges and embedding dimension d, and O(N2d) for contrastive loss computation with minibatch size N. Thus, the overall complexity O() + d²
The time complexity comparison highlights the computational efficiency and scalability of CenPre compared to other graph learning methods. CenPre achieves a lower overall complexity of O[|E) nd + n²d) by leveraging precomputation for structural representations, making well-suited for large sparse graphs. In contrast, methods like GraphCL and AutoGCL incur higher costs due to the quadratic dependence on minibatch size (O(2dd) in contrastive loss computation, which can become bottleneck for large-scale data. GraphMAE and MaskGAE share similar complexities, but their dependency on the number of masked and unmasked edges ([Evisl and [maas) introduces sensitivity to the masking ratio. TopoGCL stands out with a cubic dependence on the number of nodes (O(n²) for extended persistence computation, making it less efficient for large graphs, though it provides rich topological insights. Overall, CenPre balances computational demands with performance by focusing on centrality measures and pretraining strategies, offering a practical advantage in terms scalability and efficiency.
21

---

Published as a conference paper at ICLR 2025
F SCALING SENSITIVITY V.S. RANKING SENSITIVITY
Another significant challenge in the centrality-guidee pre-training method is its sensitivity to scaling. As noted by (Hu et al., 2019a), centrality scores are not directly comparable across graphs of varying scales. Consequently, focusing solely the centrality-baser loss may fail to effectively capture meaningful features.
To tackle the issue of scaling sensitivity, some existing studies have proposed learning the centrality- based ranking instead of directly optimizing an explicit centrality loss (Hu et al. (019a). However, a slight modification graph, such as the removal of few edges, may significantly alter centrality values without necessarily impacting the ranking.
Graph
Adjacency
Centrality
Degree order
D
E
F
0
0
0
Degrees
0
0
0
Eigenvalues
3.6
223
1.5
-0.9
0.5
After removing important
(changes are highlighted in red)
Degree order
D
E
F
0
0
0
Degrees
0
0
Eigenvalues
-2.8
3.1
1.2
0.9
0
0
Figure 4: The changes of different centrality after removal of one edge AG. We highlight the changes red color, where you could find a minor removal might cause significant changes in many different centralities but cannot be captured by the order-based feature, which is proposed in (Hu et al. 2019a) to reduce the scaling sensitivity but might introduce new problem.
Here, we demonstrate this property using simple example graph with nodes (as shown in Figure 4). When the edge between node A and node G is removed, the degree of both nodes A and G changes, but their rankings based on degree centrality remain unchanged. This illustrates that relying solely on degree order-based centrality fails to capture structural changes in the graph, as evidenced by the significant updates eigenvalues following the edge removal.
For similar reason, in graph containing several clusters of nodes with only single edge connecting different clusters, removing the connecting edges between clusters may leave the ranking- based loss unchanged but fundamentally alters the semantic structure of the nodes (as shown in Figure 5). Consequently, training strategies designed to address scaling sensitivity, such as ranking-based loss, may inadvertently introduce sensitivity to ranking changes.
Therefore, in our work, we address this issue by employing representation alignment- loss, as defined in Equation [ to ensure that the learned representations align with an existing reference scale. This approach can be intuitively understood as aligning the learned representations with prior distribution maintain appropriate scale. By introducing the parameter λş, which controls the contribution of C, in the final loss, we strike a balance between scaling sensitivity and ranking sensitivity.
22

---

Published as a conference paper at ICLR 2025
Cluster
Cluster
Cluster
Node
Edge
Removed edge
Figure 5: A graph which contains several clusters of nodes, where the nodes are almost fully connected within clusters but only one edge connected between different clusters. Removing the connecting edges (red edges) between clusters might not change the ranking-baas -ased loss but completely change semantic structure of nodes.
10
14
15
18
19
20
Figure 6: Comparison results of using and not using graph representation alignment on the Cora dataset. "Ir" represents graph representation alignment.
To investigate the efficiency of the proposed method, we consider three dimensions to evaluate the proposed module:
Does the proposed alignment strategy lead to better performance?
Does the proposed alignment strategy wildly be used for many different node representations prior distribution?
Does the proposed alignment strategy lead to a more stable training process under the perspective of scaling?
For the first question, compared to (Hu et al. 2019a), which employs ranking-based loss to address scaling sensitivity, our proposed method demonstrates the ability to effectively capture centrality- guided information using alignment- based loss, shown in Table 5 Notably, the removal of the alignment- based loss results in a significant performance drop compared to other components, highlighting its importance.
For the second question, as shown in Table 6, the node encoding results can be utilized as prior knowledge within the alignment-based loss to consistently enhance performance.
23

---

Published as a conference paper at ICLR 2025
For the third question, conduct additional experiment to track the L2-norm variations during the training process. If the proposed method fails to address the scaling sensitivity issue fully, the learned norm would exhibit rapid fluctuations during optimization. In this experiment, calculate and compare the average T-2-norm of all nodes with and without graph representation alignment, shown in Figure In the figure, without graph representation alignment, the average T2-norm fluctuates significantly within the range [0.4, 1.2] over 20 training epochs. This behavior suggests that the model struggles appropriately scale and balance the learning objectives within a unified space when directly targeting scaling- senisivve objectives. Conversely, with our proposed alignment strategy, the learned representations stabilize around consistent norm of 0.4. It indicates that our alignment strategy effectively addresses the scaling sensitivity issue without requiring ranking- baannd learning objectives, which introduce the ranking sensitivity issue and potentially harm the performance.
W
04
W
01
82
Figure 7: Performance trends of the CenPre on the Cora dataset as function of hyperparameters Å1 A2 and λz. Each graph shows the model's accuracy (%) as the corresponding hyperparameter varied while keeping the other two fixed a value of 1. The shaded bands around each curve represent the standard deviation, highlighting the variability in performance.
G ANALYSIS OF THE HYPERPARAMETERS
Figure Soureedenmee demonstrates the sensitivity of the CenPre's performance to the variation of hyperparameters d1 λ2 and λs, which control the contributions of the alignment, eigenvalue, and degree losses, respectively. The results show that the performance of the model will only fluctuate within a certain range when the values of hyperparameters the value range of A is 1-4, the fluctuation amplitude of model performance is within 1%, Further, we can see that both excessively large and excessively small values can lead to a clear decrease in performance. In addition, analysis reveals that the model is most sensitive to X3. showcasing the critical role of the alignment loss in optimizing performance. Based on the results of the three hyperparameters, we can conclude that the model performs best when A 1, A2 = 1, and X3 5. One possible reason that this setting places the three hyperparameters on the same scale, which can lead to better learning of losses. Therefore, we set λ = 1, A2 = 1, and Xa 5 in our experiments.
within reasonable range. For example, when
H DISCUSSION REGARDING THE TRAINING STABILITY
In the proposed framework, there are three types of operations involved: Definition Operation-1 Interaction between two trainable vectors, such as the inner product between weight matrix/vector and node representations.
Definition 4. Operation-2 A feed-forward layer with vectorized inputs and outputs.
Definition 5. Operation-3 Interaction between predictive vectors and optimization objectives.
Accordingly, the discussion will contain three parts:
Proposition H.1. the two vectors in Operation-I are independently drawn from Gaussian distribu- tions, then the output of Operation-l also follows Gaussian distribution. Proposition H.2. If the input of Operation-2 is Gaussian, then with high probability, the output distribution Operation-2 remains bounded.
24

---

Published as a conference paper at ICLR 2025
Proposition H.3. Based the assumptions Proposition H..1 and Proposition H.2 the difference in gradients between any two training samples defined in Operation-3 is approximately bounded.
Proposition
H.1 and Proposition H.2 are straightforward and intuitive.
H.1 PROOF OF PROPOSITION
Proof. Let the representation vector of a node be r = {II, "2, ...,T, T'n and the weight matrix be W Way, where 1, and 1,,,... ...,. k. Assume they are randomly initialized as:
Yi NN o N o.)
(26)
By the normal product distribution, each term WayTi has a mean of zero and a variance proportional to the product of the variances:
E(w,yra) = 0, Var(wsrri) = 0,,00-
(27)
For the output of Operation-1, defined as 2 Wr, where 2 = 21, 22 24 and 2j = - WigFi+ obtain:
2j ~ NO N0,no,
(28)
Thus, for any e 2 0, there exists 2 0 such that
P[[ 8) e.
(29)
In addition, applying layer normalization operator after Operation-1 can further constrain the variance.
H.2 PROOF OF PROPOSITION
Proof. By the Keine-Cannor theorem, all mapping functions in Operation-2 are continuous on R" Since the input is Gaussian and bounded with high probability, the output is also bounded. This property can described using Lipschitz continuity: for any pair of inputs za and 26 Operation-2. there is constant K that bounds the corresponding output O, and O₂ by:
110, - Osll K zoll-
(30)
Thus, we have:
80,
< K, 0z,
(31)
we force 2y approximate to Zz-
H.3 PROOF OF PROPOSITION H.
Proof. By probabilistic convergence, for any 0, there exist 0. and content K such that for any pair of inputs Ta and rb, after applying Operation-1 and Operation-2, the output satisfied:
||0.- Obll K6, with probability 1
(32)
25

---

Published as a conference paper at ICLR 2025
In our training step, each node will be updated times, positive sample and -1 times as a negative sample. The objective label based on the index, ensuring || 1.
Denoting Pe (rai 0e) as the function formed by Operation-1 and Operation-2, and using the notation
O₂ and za for any imput representation Tax we derive:
1 80 Oza WK
V O, Ozo Or
(33)
O₂
For specific dimension Tai the gradient update is:
80 Oza
K S Va
yee Oo Dza drai
Σ
wij-
(34)
Oa j=l
Since Σi=1 Way follows normal distribution due independent initialization, obtain similar gradient for another sample Tb:
1 80, Ozb
v O₂ Ozb Oru
<
Ob
Wij.
(35)
Considering ||>||| and ||>]]] are all identifiable representations of labels (only one dimension is 1 and others are o), we then have ||=|| || = 1. In addition, Oa and O₂ are predictive outputs, which are usually normalized by activation such as softmax.
For specific dimension, conclude that the gradients for updating should remain on the same scale. Moreover, each training sample treated as a positive sample once and as a negative sample 1 times. This ensures that the updates to the representations are uniformly scaled across training samples and identifiable labels. In contrast, the learned representations may become biased when predicting non-identifiable labels dealing with imbalanced category types. As highlighted in (Hu et al. (201b)), directly optimizing the eigenvalues can yield negative outcomes, as it may be initially caused by the imbalanced distribution in 2/5 and subsequently in O:,
I LIMITATIONS
Despite its advantages, the CenPre framework has certain limitations. Firstly, its reliance on centrality measures may not fully capture complex, multi-faceted structural properties of graphs, potentially leading to sub-optimal representations dense graphs and heterogeneous networks. Additionally, the computational complexity of calculating centrality measures, especially for large-scale graphs, can be high, impacting scalability and efficiency. Furthermore, the framework's s performance may be sensitive the choice centrality measures. requiring careful tuning and selection based on specific graph characteristics. Future work should address these limitations by exploring more comprehensive structural descriptors, optimizing computational efficiency for broader applicability, and trying to explore an effective method to exploit the node importance in more differentiated way.
26


Reviews:
[{"review_id": "9GUDtscNKT", "reviewer": "Reviewer_agZV", "summary": "The paper introduces a novel self-supervised framework for graphs, which considers aligning graphs' representation and structure based on centrality in graph theory. It contains three modules of node representation pre-training and alignment. The node-level structure learning aims to enhance the node representations based on degree centrality to assign similar embeddings for nodes with the same degree. The graph-level structure learning is based on eigenvector centrality to provide information on node importance from a global point of view. Specifically, it uses the graph representation to guide the structure matrix in determining node importance through a cross-attention module. at last, a graph representation alignment module is applied to minimize the discrepancy between the pre-trained structural embedding and embeddings learned by other graph models. The experimental results demonstrate the effectiveness of the framework.", "questions": "1. Why do you choose $L_2$ as your alignment loss function not a distribution alignment loss function like KL-divergence?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. It proposes a novel self-supervised framework for pre-training the graph that considers both structure embeddings and graph embedding based on node features only.\n2. it introduces a novel alignment module with a loss function that aligns the structure embeddings from a global perspective and node embeddings based on node features only.\n3. the experimental results outperform baselines significantly.", "weaknesses": "1. The use of SVD limits the applicable ability from very large graphs.\n2. based on Table 4, the proposed framework is most effective for sparse graphs. For relatively dense graphs like Photo, the improvement is limited.\n3. combined with Tables 4, 5, and 6. the proposed framework is most effective for graph classification while it has limited improvement for node classification and edge classification. \n4. some writing errors, e.g., missing \"is\" in \"which the maximum absolute\" at line 267, capital \"D\"at line 245", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "59EDSpjCEB", "reviewer": "Reviewer_rWJN", "summary": "In this paper, the authors propose the CenPre framework, which aligns graph structure information with representations based on the concept of centrality. By learning importance at both the node and graph levels, CenPre enhances node representation quality through pretraining and alignment modules.\n\nThe main contributions include:\n\nAligning graph representations with structural information during pretraining to generate improved graph representations for downstream tasks.\nIntroducing the CenPre framework based on centrality, capable of learning structure-integrated graph representations from both local and global perspectives.\nDemonstrating, through experiments on multiple real-world datasets, that CenPre significantly outperforms baseline models in node classification, link prediction, and graph classification tasks.", "questions": "1、The paper employs degree centrality and eigenvector centrality to measure node importance. What are the specific reasons for choosing these two centrality metrics? Were other centrality measures considered, and if so, why were they not selected? It is recommended to explore a broader range of centrality metrics and analyze their suitability for different types of graph data and tasks. Experimental comparisons of the CenPre framework's performance under different centrality metrics could further optimize how node importance is measured.\n\n2、The CenPre framework consists of three modules. How do these modules interact with each other? For instance, when integrating information between the node-level and graph-level structural learning modules, is there interference or synergistic enhancement? How could experimental or theoretical analysis be used to understand the interactions between these modules more deeply? A more detailed experimental design, examining the impact of various module combinations on model performance, would allow for an in-depth analysis of module synergy. From a theoretical perspective, a mathematical model describing the information flow and interactions between modules could provide a foundation for further optimizing the framework structure.\n\n3、In the experimental section, for hyperparameter settings such as λ1, λ2, and λ3 in the balanced loss component, it is mentioned that these values were determined through pilot studies, but the specific tuning process and rationale were not elaborated. Could you provide more details on the hyperparameter selection process to help readers better understand the model’s sensitivity and stability?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1、The authors propose a novel centrality-guided graph pretraining framework, CenPre, which integrates graph structural information with node representations. This systematic application of the centrality concept in graph pretraining is innovative.\n\n2、Unlike traditional graph representation learning methods that rely solely on augmentation, this paper introduces an innovative approach by learning node importance at both the node and graph levels, with corresponding modules designed for structural information integration.\n\n3、The experimental section conducts a comprehensive evaluation on 13 benchmark datasets across various domains and scales, covering node classification, link prediction, and graph classification tasks. The rigorous experimental setup and comparisons with numerous advanced baseline models enhance the reliability and persuasiveness of the results.", "weaknesses": "1、The choice of centrality metrics by the authors is relatively traditional, lacking exploration of alternative, potentially more suitable centrality measures for complex graph structures or specific application scenarios.\n\n2、There is an absence of sensitivity analysis on the model under different parameter settings, making it difficult for readers to understand the stability and performance trends of the model with various hyperparameter values.\n\n3、The theoretical explanation of the relationship between centrality, graph structure, and node representation lacks depth, missing a more rigorous mathematical basis to explain why this method can effectively improve graph representation learning performance.\n\n4、The analysis of computational and spatial complexity is not comprehensive, with a lack of detailed efficiency comparisons to existing methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NTcZHFNGg9", "reviewer": "Reviewer_7DHX", "summary": "Summary:\nThe author proposed CenPre framework enhances graph representations by integrating structural information, specifically node importance via centrality measures, into self-supervised learning. CenPre includes modules for node-level structure learning using degree centrality, graph-level structure learning with eigenvector centrality, and a representation alignment module that retains semantic integrity while incorporating structural insights. Experiments show that CenPre outperforms current methods in node classification, link prediction, and graph classification.", "questions": "same as cons", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The author proposed a new method CenPre framework enhances graph representations by integrating structural information, specifically node importance via centrality measures, into self-supervised learning. \n- Experiments show that CenPre outperforms current methods in node classification, link prediction, and graph classification.", "weaknesses": "- More self-supervised learning methods with different training paradigms are encouraged to be added. GBT[1] using barlow twins and GGD[2] using group discrimination.\n- There are three hyperparameters λ1/2/3 to be tuned. It seems it is quite hard to tune these parameters.\n- Has the pretraining methods tried to employed to be pretrained on a set of other datasets first and then evaluate on a target dataset? It seems the method is still dataset-specific? The L_d and L_e only relies on graph topology and seems to be able to used in this setting.\n\n\n[1] Bielak, P., Kajdanowicz, T., & Chawla, N. V. (2022). Graph barlow twins: A self-supervised representation learning framework for graphs. Knowledge-Based Systems, 256, 109631.\n[2] Zheng, Y., Pan, S., Lee, V., Zheng, Y., & Yu, P. S. (2022). Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination. Advances in Neural Information Processing Systems, 35, 10809-10820.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ROpcLkS4BH", "reviewer": "Reviewer_eSwp", "summary": "To address the problem that existing graph SSL methods focus on augmentation but overlook the integration of structural information, this paper proposes a Centrality-guided Graph Pre-training (CenPre) framework to learn better graph representations that incorporate structural information. CenPre consists of three modules that use degree, eigenvector centrality, and original graph representations to conduct aligning during pre-training. Experimental results demonstrate the effectiveness of CenPre on various tasks and datasets.", "questions": "1. Can the authors provide more evidence to support their basic opinion?\n2. Can the authors make further discussion on the differences with existing works?\n3. The third module aligns the centrality-guided node representation with \"the original pre-trained model (line 320).\" How is the \"original pre-trained model\" obtained? Does this mean in CenPre we need to conduct pre-training twice? The overall workflow of the method needs a clearer elucidation.\n4. What does \"CenPre uses the original node representation\" mean in line 484?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The experiments are comprehensive. A large number of datasets from various tasks are included, validating the effectiveness of the proposed method.\n2. This paper is easy to read.", "weaknesses": "1. **The motivation is not well explained.**\n    \n    As the foundation of this paper, the authors claim that existing graph SSL methods only focus on augmentation and neglect the integration of structural information. This is somewhat not convincing. a) It is well known that GNNs can effectively capture both semantic and structural information simultaneously, especially considering some GNN variants with stronger expressive power. It is arbitrary to say that existing SSL methods fail to incorporate structural information because they can implicitly achieve this. b) At the same time, it is also common practice to explicitly consider structural information in existing SSL works. More theoretical or experimental evidence should be provided regarding the limitations of existing methods.\n    \n2. **The method lacks novelty.**\n    \n    The proposed CenPre basically uses centrality to guide the representation learning during pre-training. However, the concept of centrality has already been widely introduced in GNNs [1,2,3,4,5]. Among them, [4,5] exactly use centrality as a pretext task for pre-training. A detailed discussion on the differences between CenPre and previous works is necessary, which is missing in this paper.\n    \n\nMinor Point:\n\nThe paper uses a considerable amount of space (Sec 4.1 and Sec 4.2) to introduce the well-known concept of centrality, which is unnecessary.\n\n[1] Maurya, Sunil Kumar, Xin Liu, and Tsuyoshi Murata. \"Fast approximations of betweenness centrality with graph neural networks.\" *Proceedings of the 28th ACM international conference on information and knowledge management*. 2019.\n\n[2] Avelar, Pedro, et al. \"Multitask learning on graph neural networks: Learning multiple graph centrality measures with a unified network.\" *International Conference on Artificial Neural Networks*. Cham: Springer International Publishing, 2019.\n\n[3] Zhu, Yanqiao, et al. \"Graph contrastive learning with adaptive augmentation.\" *Proceedings of the web conference 2021*. 2021.\n\n[4] Jin, Wei, et al. \"Self-supervised learning on graphs: Deep insights and new direction.\" *arXiv preprint arXiv:2006.10141* (2020).\n\n[5] Hu, Ziniu, et al. \"Pre-training graph neural networks for generic structural feature extraction.\" *arXiv preprint arXiv:1905.13728* (2019).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)