Centrality-guided Pre-training for Graph

Authors: Bin Liang, Shiwei Chen, Lin Gui, Hui Wang, Yue Yu, Ruifeng Xu, Kam-Fai Wong
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph neural networks, Graph representation, Graph pre-training, Graph centrality

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.

Decision: accept (poster)
Reviewer scores: 8, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730265353992

thread_type:
official_review

<thread_object>
creator: reviewer_eswp

<content>
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.

strengths:
1. The experiments are comprehensive. A large number of datasets from various tasks are included, validating the effectiveness of the proposed method.
2. This paper is easy to read.

weaknesses:
1. **The motivation is not well explained.**
    
    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.
    
2. **The method lacks novelty.**
    
    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.
    

Minor Point:

The 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.

[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.

[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.

[3] Zhu, Yanqiao, et al. "Graph contrastive learning with adaptive augmentation." *Proceedings of the web conference 2021*. 2021.

[4] Jin, Wei, et al. "Self-supervised learning on graphs: Deep insights and new direction." *arXiv preprint arXiv:2006.10141* (2020).

[5] Hu, Ziniu, et al. "Pre-training graph neural networks for generic structural feature extraction." *arXiv preprint arXiv:1905.13728* (2019).

questions:
1. Can the authors provide more evidence to support their basic opinion?
2. Can the authors make further discussion on the differences with existing works?
3. 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.
4. What does "CenPre uses the original node representation" mean in line 484?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730270146289

thread_type:
official_review

<thread_object>
creator: reviewer_7dhx

<content>
summary:
Summary:
The 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.

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. 
- 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.
- There are three hyperparameters λ1/2/3 to be tuned. It seems it is quite hard to tune these parameters.
- 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.


[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.
[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.

questions:
same as cons
</content>
</thread_object>

</thread>
<thread>
creation date:
1730451903074

thread_type:
official_review

<thread_object>
creator: reviewer_rwjn

<content>
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.

The main contributions include:

Aligning graph representations with structural information during pretraining to generate improved graph representations for downstream tasks.
Introducing the CenPre framework based on centrality, capable of learning structure-integrated graph representations from both local and global perspectives.
Demonstrating, through experiments on multiple real-world datasets, that CenPre significantly outperforms baseline models in node classification, link prediction, and graph classification tasks.

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.

2、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.

3、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.

2、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.

3、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.

4、The analysis of computational and spatial complexity is not comprehensive, with a lack of detailed efficiency comparisons to existing methods.

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.

2、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.

3、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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730706215951

thread_type:
official_review

<thread_object>
creator: reviewer_agzv

<content>
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.

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.
2. 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.
3. the experimental results outperform baselines significantly.

weaknesses:
1. The use of SVD limits the applicable ability from very large graphs.
2. based on Table 4, the proposed framework is most effective for sparse graphs. For relatively dense graphs like Photo, the improvement is limited.
3. 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. 
4. some writing errors, e.g., missing "is" in "which the maximum absolute" at line 267, capital "D"at line 245

questions:
1. Why do you choose $L_2$ as your alignment loss function not a distribution alignment loss function like KL-divergence?
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a new SSL approach for graph learning, which aims to enhance graph representations by incorporating structural information, and specifically node importance as determined by centrality measures.  The approach is comprised of multiple modules spanning node-level and graph-level structure learning through different centrality types (degree and eigenvector), as well as an alignment phase. The authors compare their work to prior baselines in graph SSL, including some from 2023 and outperform in various tasks including node clasisifcation, link prediction and graph classification.

Reviewers leaned positively on this work, hence the accept recommendation. Yet, there were a few themes of comments that were raised which I encourage the authors to fold into the revision:

- Concerns around time and space complexity (rWJN, agZV)

- Several missing references on notable works in the graph SSL community, e.g. GBT and GGD (as 7DHX mentions).

- Some motivation around the use of centrality measures and why exisitng methods cannot capture this information well could be improved (eSwp, rWJN)

Besides this feedback, the line of work referenced on multi-task graph SSL should be improved with [1,2], and there should be some discussion around non-contrastive methods for graph SSL as well [3].  Nonetheless, the authors' proposal appears complementary in spirit to most of these works and the use of centrality-oriented pre-training independently seems of interest to the community.

[1] Multi-task Self-supervised Graph Neural Networks Enable Stronger Task Generalization (Ju et al, ICLR 2023)

[2] Automated Self-Supervised Learning for Graphs (Jin et al, ICLR 2022)

[3] Link Prediction with Non-Contrastive Learning (Shiao et al, ICLR 2023)