A Centrality-based Graph Learning Framework

1 Introduction

Graph Neural Networks (GNNs) [Welling and Kipf, 2017; Yu and Jia, 2024; Yu and Jia, 2023; Wu et al., 2023] are a powerful class of machine learning models specifically designed to work on graph-structured data. Their architecture effectively leverages relationships between nodes, enabling their interactions on graphs, making GNNs well-suited for application in various domains like computer vision [Han et al., 2022; Gao et al., 2020], natural language processing [Meng et al., ;

∗Corresponding author: haishuai.wang@zju.edu.cn.

Wu et al., 2021], and biological information [Yu et al., 2025; Koh et al., 2024]. Currently, the most popular GNNs were initially developed to learn node representations, demonstrating outstanding performance on a wide range of node-level tasks. Among these, several notable GNNs have each contributed unique advancements to the field: Graph Convolutional Networks (GCN) [Welling and Kipf, 2017] extended the concept of convolution to graph data, also bridging the gap between spatial and spectral GNNs; Graph Attention Networks (GAT) [Veliˇckovi´c et al., 2018] incorporate attention mechanisms into GNN models, allowing the model to weigh the importance of different neighbors dynamically; GraphSAGE [Hamilton et al., 2017] was designed for more scalable graph learning via sampling nodes' local neighborhood. Unlike node-level learning which targets specific nodes and their local neighborhoods, graph-level learning addresses tasks where the objective is to understand properties of the entire graph. This distinction introduces unique challenges, such as the graph isomorphism problem, and it is inevitable to tackle global structural information and manage varying graph sizes and topologies. Graph-level learning holds significant importance in diverse fields like protein classification [R´eau et al., 2023], drug discovery [Koh et al., 2024], molecular property prediction [St¨ark et al., 2022]. These applications demonstrate its profound impact on scientific and industrial advancements.

Inspired by the outstanding performance of GNNs in nodelevel tasks, many recent graph-level learning frameworks have extended GNN architectures with graph pooling or called readout operations [Navarin et al., 2019]. Typically, these frameworks first generate node representation matrices for each graph using GNNs, and then a readout function aggregates these node representations to produce a comprehensive graph-level embedding that encapsulates the global information of the entire graph. A representative model in this domain is the Graph Isomorphism Network (GIN) [Chen et al., 2019], which employs a readout function to aggregate node embeddings into a single graph-level vector, aiming to summarize the entire graph's information. However, this framework of directly combining GNNs with readout functions presents certain limitations. By not thoroughly analyzing the inherent characteristics specific to graph-level learning, such approaches may inadvertently lead to information loss during the aggregation process. For instance, GIN leverages the Weisfeiler-Lehman test [Shervashidze et al., 2011] to analyze GNNs' expressive power on graph-level learning but is also constrained by this theory. This existing framework can result in suboptimal performance, as it does not inherently address the complexities unique to graph-level tasks.

In this paper, we step further to explore the essence of existing GNN-based graph-level learning pipelines. Through theoretical analyses, we reveal that current approaches using GNNs paired with common readout functions essentially adopt a single-view perspective based solely on degree-based centrality. To address this limitation, we propose a multiview approach by introducing different types of graph centrality measures, each capturing distinct and complementary aspects of how nodes contribute to the overall graph structure. These diverse centrality measures provide multiple views of node importance, offering a more comprehensive understanding of the graph than the traditional degree-based single view. Building on this multi-view perspective, we propose a novel method called Adaptive Centrality Readout (ACRead), which employs an attention-based mechanism to adaptively integrate information from multiple centrality views when aggregating node representations into graph-level embeddings. ACRead serves as a novel readout function that can be paired with various GNNs. When compared with other state-ofthe-art readout functions, ACRead exhibits impressive performance with a variety of supervised and unsupervised GNN backbones. Moreover, we also propose a new graph-level learning framework named Adaptive Centrality-based Graph Learning (ACGL) that leverages these multiple centrality views directly. ACGL is both simple and effective, which is demonstrated by comprehensive experiments conducted on real-world datasets. Without relying on traditional GNNs, it achieves superior performance over other baselines by effectively combining different centrality perspectives. The main contributions of our paper are summarized as follows:

• We analyze existing graph-level learning frameworks from a centrality perspective, revealing their limitations in integrating only a single view of node degree.
• We propose a multi-view approach based on adaptive centrality, which can be used as a readout function in conjunction with GNNs and can also constitute a GNNfree graph learning framework.
• Comprehensive experiments demonstrate the superior performance of the proposed method, learning more informative graph embeddings than existing frameworks by incorporating diverse centrality perspectives.

2 ProposedMethod

2.1 Notation and ProblemFormulation

A graph Gi has ni nodes, and its adjacency matrix is denoted by AGi ∈ Rni×ni . The degree matrix of AGi is DGi = diag(d1, . . . , dni ) ∈ Rni×ni . The initial node features of the graph Gi are represented by XGi ∈ Rni×d . G = {G1, ..., GN} is the graph set. We aim to learn the graph representation vector zGi for each graph Gi to support various downstream tasks.

The general pipeline for graph classification using message passing paradigm [Welling and Kipf, 2017] can be summarized in two steps:

Graph Encoding. GNNs are primarily employed to encode graphs through a series of graph convolutional layers. Each layer operates on a message-passing principle, which involves two key steps for aggregating the neighborhood information of each target node:

where a certain GNN model is adopted here and HGi ∈ Rni×dL is the output node representation of graph Gi.

Readout Function. To unify each size of the graph, following the convolution operation performed by the GNNs, the node embedding matrix HGi is processed through a readout function. This function transforms HGi ∈ Rni×dL into a graph vector zGi ∈ RdL , which is essential for the graph classification task,:

where HGi [j, :] denotes the j-th row of the node embedding matrix for graph Gi, i.e., the representation of node vj, and HGi [:, j] will refer the j-th column of the node representations for graph Gi.

2.2 Revisiting Graph-level Learning Paradigm

The aforementioned two steps represent the most common frameworks in current graph-level learning, demonstrating good performance in related tasks. However, some studies [Garg et al., 2020; Balcilar et al., 2021] have indicated that the expressive capacity of this paradigm has significant limitations. For instance, Chen et al. pointed out that this approach is constrained by the Weisfeiler-Lehman test [Shervashidze et al., 2011]. Therefore, we examine the essence of existing graph-level learning frameworks from a new perspective and build a novel pipeline. Although current GNNs are diverse, it has been discovered that similar performance can be achieved by simplifying them and retaining core mechanisms. Therefore, we discuss the streamlined framework. Following the assumptions in [Wu et al., 2019], where the nonlinearity is removed and weights are collapsed, we have the specified graph encoding process formulated as

where UGi is the adjacency matrix, and a k-hop message passing is performed here. Then the readout function is conducted to extract the graph-level representation of each graph. We find that common readout functions can be uniformly described as

where rGi is defined as a readout vector which is specified by the adopted readout function. Existing GNN-based graphlevel learning frameworks follow this process of combining node-level representation learning and graph-level readout. However, this combination is crude, expecting to inherit the excellent performance of GNNs on node-level tasks while ignoring the important question of what information should be learned for the graph-level prediction. We therefore proceed to analyze the nature of the existing framework and the reasons for its limitations.

Remark 1. The most common readout functions used in graph-level learning can be reformulated as

where 1Gi denotes an all-one vector, eGi = [1/ni, · · · , 1/ni], and Imax(x)i = I{i = argmax(x)}. That is, the readout functions can be described as the inner product over the feature dimensions for a node representation and a particular readout vector.

Remark 2. Combining Equations (3), (4), (5) and the above analyses, the pipeline of existing GNN-based graphlevel learning can be further written as

where cGi = (r⊤Gi UkGi )⊤, which actually computes a certain statistic related to degree for each node. Subsequently, the vector cGi makes a weighted summation of the node features, only depending on this statistic to obtain a representation of the entire graph Gi. Our analysis reveals the nature of the existing framework, which straightforwardly combines powerful GNNs and readout functions, but is essentially just a weighted degree-based summation. This pipeline struggles to exploit the capabilities of GNNs and potentially undermines the performance of downstream tasks.

To be specific, we take SUM as an example, the vector of ones 1Gi is selected to be the readout vector, then we have

where the l-th value of cGi is

Based on these formulations, three well-known message passing strategies are considered:

1. Message Passing of GIN: GIN adopts the message passing mechanism with a non-normalized adjacency matrix, i.e., UGi = AGi . Therefore each element in cGi is calculated as

1. Message Passing of GCN (Random Walk): For the widely used GCN, there are two strategies. One is to adopt random walk normalized adjacency matrix UGi = AGi D-1 Gi , then we have the following vector cGi :

1. Message Passing of GCN (Symmetric): The more popular message passing in GCN is with symmetrically normalized adjacency matrix UGi = D- 12 Gi AGi D- 12 Gi :

Through the analyses above, we find that the existing graph-level learning pipeline can be viewed as an aggregation of node information based on a certain statistic of all nodes. This statistic, like the node degree here, is used as a basis for integrating node information.

2.3 Adaptive Centrality

It can be seen that existing methods are essentially based on a single statistic-node degree and do not explicitly design the learning mechanism of the overall framework. We first introduce the concept of centrality [Sade, 1989]. The centrality of nodes on a graph describes the importance of nodes in the whole graph, and there are several critical centrality measures beyond the degree-based ones:

Closeness Centrality of a node i is the reciprocal of the average shortest path distance from node i to all other nodes:

d(i, j) is the shortest path distance between nodes i and j. Betweenness Centrality of a node i is computed by the shortest paths between all pairs of nodes s and t and counting how many of these paths pass through node i:

where γst is the number of shortest paths between nodes s and t, and γst(i) is the number of paths through node i.

Bridge Centrality. For an edge (i, j) that is not part of any bridge, node i has a bridge centrality of 1, otherwise 0, i.e.,

Building on the above analyses of the existing graphlevel learning paradigm and the concept of centrality, two research questions for further experimental investigation are (1) whether models based only on centrality are comparable to existing graph-level learning frameworks? (2) how does different centrality affect graph-level learning performance? To answer these questions, we conducted an experiment on the performance of two common GNN baselines as well as GNN-free baselines based on different centrality. Note that the centrality-based baselines utilize the MLP as a trainable component, and then readout the graph representations by different centrality, respectively. As shown in Fig 1, it is obvious that centrality-based models can achieve comparable or even better performance without the well-known message passing mechanism. This result corroborates our theoretical analysis that a straightforward combination of GNNs and readout functions collapses into a simple model based on a single type of centrality. In addition, it is observed that a single centrality may not adapt to different types of graph data. These results highlight the importance of selecting appropriate centrality measures based on the nature of the dataset, as they can significantly influence the graph-level tasks.

The results of this experiment inspired us to design a centrality-based framework for graph-level tasks, which touches on the essence more than existing pipelines, but also poses challenges. Since the applicability of different centrality to different types of graph data varies, manually selecting the most appropriate centrality can be very labor-intensive. Thus we would like to learn an adaptive centrality to synthesize the information provided by different centrality.

First, we construct a centrality matrix CGi ∈ Rni×s collecting various centrality measures for each graph Gi, where s denotes the number of initial centrality measures. Subsequently, a trainable weight vector w ∈ Rs is used to measure the overall importance of each centrality. Specifically, we let each element in w weight each column in CGi , as CGi = [w[1]CGi [:, 1], ...,w[s]CGi [:, s]]. This allows the model to initially learn how much information each centrality should provide to the subsequent process. Then we apply normalization to the centrality matrix due to the different scales of the centrality measures, which enhance model stability, i.e., ˆCGi = CGi -µGi σGi . This involves calculating the mean µGi and variance σGi .

After this, to further extract the information in the centrality matrix as well as the importance of each centrality and the interactions between them, we designed a centrality attention mechanism:

where QGi = Wq ˆCGi , KGi = Wk ˆCGi , VGi = Wv ˆCGi , and d is the dimension of the hidden layer. Through this attention-based manner, we can better capture the data distribution among different centralities and effectively learn an adaptive centrality that accommodates various datasets.

In practice, we also employ multi-head self-attention to enhance the model's expressiveness, allowing the model to capture different aspects of node relationships:

where QhGi = Wh q ˆCGi , KhGi = Wh k ˆCGi , Vh Gi = Wh v ˆCGi , and dh is the dimension for head h. Finally, the outputs from all heads are concatenated and projected through a linear transformation to produce the final adaptive centrality representation:

whereWO ∈ R∑Hi=1 di×d is a learnable weight matrix for the output transformation.

The adaptive centrality ΞGi ∈ RnGi ×d modulates the importance of nodes in the final representation. The final graph embedding zGi is computed as the weighted sum of the adaptive centrality, expressed as follows:

The choice of HGi offers considerable flexibility. It can be derived from various approaches, such as the node embeddings learned by a GNN or even the initial node feature vectors themselves. The function gΨ also provides a flexible mechanism for integrating the learned centrality ΞGi with node embeddings to produce the final graph embedding. It can take various forms: for instance, it could be a simple linear transformation that directly converts ΞGi into a vector, which is then used to perform a weighted summation over the node embeddings. Alternatively, it could act as a mapping function that applies the Hadamard product between ΞGi and HGi , followed by a summation.

In summary, the flexibility in the choice of gΨ and HGi allows for adapting the centrality-based method to different scenarios, leveraging either learned representations from GNN models or raw feature inputs, depending on the needs of the task or the dataset characteristics. Moreover, our ACGL framework can incorporate other graph learning strategies, making it a highly adaptable and extensible method for a wide range of graph-based tasks.

2.4 Overall Framework

For better understanding, we briefly describe our proposed method in this subsection

where MΦ denotes the adaptive centrality learning process, which contains the initial construction of CGi , Equations (16) and (17). Φ is the set of all trainable parameters, similarly we have W and Ψ for corresponding processes. fW is an encoder chosen from linear layer, MLP, and GNNs. When equipped with GNNs, the model can be viewed as ACRead, while it becomes ACGL when choosing a linear layer or an MLP.

For a comprehensive understanding of computational efficiency, we analyze the time complexity of our proposed method for N graphs. The GNN encoder, responsible for transforming initial node features into node embeddings, exhibits a time complexity of O(N(nd+ |E|)(Ld+d0)). Here, n denotes the maximum number of nodes, |E| represents the maximum number of edges, d0 is the dimension of initial node features, d indicates the maximum hidden dimension, and L represents the number of GNN layers. This complexity encompasses both propagation and aggregation operations across all layers. In the adaptive centrality mechanism, the query, key, and value mapping layers utilize a hidden dimension dh (where dh ≪ d), resulting in a complexity of O(Nnsdh). The attention computations, including score calculations and matrix multiplications, contribute a complexity of O(Nhn2dh) (where s ≪ dh and h represents the number of attention heads). Given that the batch size n remains smaller than the hidden dimension d during training, the overall time complexity maintains at O(N(nd + |E|)(Ld + d0)). Notably, the computational overhead introduced by our approach is minimal in the context of the complete framework. For the detailed training times, please refer to Appendix B.5.

3 Expreiments

This section presents experiments to evaluate our proposed methods. We first introduce experimental settings, followed by performance analysis on graph classification and representation learning tasks. We also conduct ablation studies and provide visualizations. Detailed experimental settings are provided in the Appendix B.

3.1 Experiments Setting

Datasets. We utilize 8 graph-level datasets, comprising 2 social network datasets (IMDB-B and IMDB-M) and 6 smallmolecule chemical datasets (MUTAG, DD, PROTEINS, NCI1, Mutagenicity and OGBG-Molhiv). All datasets were collected from the TU datasets [Morris et al., 2020] and open graph benchmark repositories [Hu et al., 2020].

Backbone and Baseline. This paper employed six commonly used supervised GNN frameworks: basic GNNs (GCN [Welling and Kipf, 2017], GraphSAGE [Hamilton et al., 2017], SGC [Wu et al., 2019]), and three more expressive GNNs (GAT [Veliˇckovi´c et al., 2018], GIN [Xu et al., 2018], and GUNet [Gao and Ji, 2019]). Besides, two unsupervised GNNs (InfoGraph [Sun et al., 2019] and GraphCL [You et al., 2020]) are also used in this article. Additionally, we selected 11 readout functions as baselines, including simple readouts (Sum, Mean, Max), as well as learnable readouts (Attention [Li et al., 2016], Set2Set [Vinyals et al., 2016], Deep Sets [Zaheer et al., 2017], SRead [Lee et al., 2021], Janossy MLP [Buterez et al., 2022]), sequence-based readouts (Set Transformer, and Janossy GRU [Buterez et al., 2022]), and kernelbased methods (KerRead [Yu et al., 2024]).

Parameter Settings. In this paper, we utilized 9 different centrality measures as the initial centrality features, including: degree centrality, betweenness centrality, closeness centrality, PageRank, hubs, authorities, load centrality, harmonic centrality, and bridge centrality. These centrality measures offer varied insights into node importance and influence within the graph, forming the foundation for our adaptive centrality module. Additional experimental settings and implementation details can be found in the Appendix.

3.2 Experimental Results Analysis

Graph Classification. We conducted a comprehensive graph classification task using 11 readout functions across 6

backbone models. The results for 7 smaller datasets are compared in Tables 1 and Appendix B.4, while the results for a larger dataset are shown in Table 2 to ensure the reliability of our findings. Based on these tables, we observed the following phenomena: (i) ACRead exhibited superior performance, outperforming the previously strongest baseline, KerRead, by an average of 5.1%, 4.2%, and 5.5% on GAT, GUNet, and SGC, respectively. (ii) ACRead demonstrated strong stability. While other readouts performed poorly on GAT and SGC, ACRead maintained consistent performance across all backbones. Specifically, the largest performance difference for ACRead across the 6 backbones was only 3.5%, whereas other readouts showed performance gaps as large as 8.1%. (iii) ACRead's effectiveness persisted even on weaker models. For instance, even on the less expressive SGC model, ACRead outperformed most readouts applied to stronger backbones like GUNet. These results highlight the robustness and effectiveness of ACRead across various models and datasets.

GraphRepresentationLearning. The graph clustering results are shown in Table 3, which provides a comparison of 11 readout functions across two unsupervised GNN backbones, InfoGraph and GraphCL, and we can find that: (i) ACRead consistently outperforms other readouts. It achieves the highest performance in terms of both ACC and NMI across multiple datasets, particularly on MUTAG, DD, and NCI1. (ii) ACRead demonstrates strong adaptability across datasets. It maintains robust performance across molecular datasets and social network datasets, confirming its versatility. (iii) While other readouts show significant performance variation depending on the dataset and backbone, ACRead maintains stable results across both InfoGraph and GraphCL. For example, with the InfoGraph backbone, ACRead's NMI ranges from 19.2 to 36.9 across datasets, which is comparatively lower than the fluctuations observed in other methods.

Selection of gΨ and HGi . To validate the effectiveness of our proposed ACGL framework, we experimented with various configurations of HGi and gΨ to assess their performance in graph classification. As shown in Table 4, we conducted experiments on four datasets using three different HGi and two different gΨ. The operators ⊙ and Linear respectively represent the Hadamard product using the learned Υ ∈ RnGi ×d directly, or a linear transformation into a vector of size nGi × 1 followed by weighted summation. We observed the following phenomena: (i) More complex HGi typically leads to better results. Using the initial features XGi as the starting vector already yields performance comparable to Table 1. However, it's clear that applying an MLP transformation on XGi yields even better results, and the best performance is achieved when HGi is learned using GNNs for weighted summation, as evidenced in Tables 1. (ii) The ⊙ operator outperforms the simple linear summation, as it not only applies weights to each node but also to each dimension, enabling the capture of more information.

The Number of Heads. Figure 2 illustrates the relationship between the number of heads and the accuracy across four datasets. The x-axis represents the number of heads, scaled exponentially (from 20 to 24 ), while the y-axis shows the corresponding accuracy for each dataset. In general, accuracy tends to increase with a higher number of heads across all datasets. This trend suggests that increasing the number of attention heads in the model contributes positively to classification performance, reflecting improved representation learning. However, the performance improvement diminishes as the number of heads increases from 23 to 24 . While the initial increase in heads (from 20 to 23 ) leads to notable accuracy gains across all datasets, the jump from 23 to 24 shows a much smaller improvement. This trend suggests that after a certain point, adding more heads yields diminishing returns, possibly because the model reaches a saturation point where further splitting attention no longer substantially enhances the representation learning.

Visiualization. The normalized adaptive centrality scores, scaled between (0, 1), are visualized with darker colors representing nodes of greater influence on the graph embedding. We randomly selected two samples from the MUTAG dataset, as shown in Figure 3, where the goal is to predict mutagenicity in Salmonella typhimurium. Both samples activate the mutagenic gene. Adaptive centrality identified functional groups like F and Cl as important, while carbon atoms in the benzene ring were less significant. This highlights adaptive centrality's ability to capture node importance, offering insights for future graph-level tasks.

Supplementary Experiment Due to space constraints, additional crucial experiments are included in the appendices, including graph classification performance with GUNet, GraphSAGE, and SGC backbones (Appendix B.4), as well as training time analysis (Appendix B.5).

4 Conclusion

In this paper, we revisited the essence of message passing in graph-level tasks through the perspective of centrality, uncovering that it primarily operates as a weighted summation with degree-based centrality, which represents a single-view of node centrality. Building on this insight, we introduced a novel graph-level learning method with a more generalizable form of centrality-adaptive centrality, which integrates multiple views of node centrality and is utilized to build a novel readout function, called Adaptive Centrality-based Readout (ACRead). ACRead was applied to six supervised and two unsupervised GNN backbones, consistently outperforming existing readout methods across eight graph datasets. Furthermore, the approach could also perform as an individual graph-level learning framework without GNNs, called Adaptive Centrality-based Graph Learning (ACGL), which still achieved competitive performance by effectively combining different views of node centrality.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant Nos. 62202422 and 62372408).

Contribution Statement

Jiajun Yu and Zhihao Wu contributed equally as co-first authors.