Rethinking Structure Learning For Graph Neural Networks

• URL: http://arxiv.org/abs/2411.07672v1
• Date: Tue, 12 Nov 2024 09:39:22 GMT
• Title: Rethinking Structure Learning For Graph Neural Networks
• Authors: Yilun Zheng, Zhuofan Zhang, Ziming Wang, Xiang Li, Sitao Luan, Xiaojiang Peng, Lihui Chen,
• Abstract summary: Graph Structure Learning (GSL) has been extensively applied to reconstruct or refine original graph structures. GSL is generally thought to improve GNN performance, but there is a lack of theoretical analysis to quantify its effectiveness. This paper proposes a new GSL framework, which includes three steps: GSL base, new structure construction, and view fusion.
• Score: 16.753943955505406
• License:
• Abstract: To improve the performance of Graph Neural Networks (GNNs), Graph Structure Learning (GSL) has been extensively applied to reconstruct or refine original graph structures, effectively addressing issues like heterophily, over-squashing, and noisy structures. While GSL is generally thought to improve GNN performance, it often leads to longer training times and more hyperparameter tuning. Besides, the distinctions among current GSL methods remain ambiguous from the perspective of GNN training, and there is a lack of theoretical analysis to quantify their effectiveness. Recent studies further suggest that, under fair comparisons with the same hyperparameter tuning, GSL does not consistently outperform baseline GNNs. This motivates us to ask a critical question: is GSL really useful for GNNs? To address this question, this paper makes two key contributions. First, we propose a new GSL framework, which includes three steps: GSL base (the representation used for GSL) construction, new structure construction, and view fusion, to better understand the effectiveness of GSL in GNNs. Second, after graph convolution, we analyze the differences in mutual information (MI) between node representations derived from the original topology and those from the newly constructed topology. Surprisingly, our empirical observations and theoretical analysis show that no matter which type of graph structure construction methods are used, after feeding the same GSL bases to the newly constructed graph, there is no MI gain compared to the original GSL bases. To fairly reassess the effectiveness of GSL, we conduct ablation experiments and find that it is the pretrained GSL bases that enhance GNN performance, and in most cases, GSL cannot improve GNN performance. This finding encourages us to rethink the essential components in GNNs, such as self-training and structural encoding, in GNN design rather than GSL.

Related papers

• GSLB: The Graph Structure Learning Benchmark [34.859275408785614]
  Graph Structure Learning (GSL) has recently garnered considerable attention due to its ability to optimize both the parameters of Graph Neural Networks (GNNs) and the computation graph structure simultaneously. There is no standard experimental setting or fair comparison for performance evaluation, which creates a great obstacle to understanding the progress in this field. We develop a comprehensive Graph Structure Learning Benchmark (GSLB) curated from 20 diverse graph datasets and 16 distinct GSL algorithms.
  arXiv  Detail & Related papers  (2023-10-08T14:13:03Z)
• OpenGSL: A Comprehensive Benchmark for Graph Structure Learning [40.50100033304329]
  We introduce OpenGSL, the first comprehensive benchmark for Graph Structure Learning (GSL) OpenGSL enables a fair comparison among state-of-the-art GSL methods by evaluating them across various popular datasets. We find that there is no significant correlation between the homophily of the learned structure and task performance, challenging the common belief.
  arXiv  Detail & Related papers  (2023-06-17T07:22:25Z)
• SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization [67.28453445927825]
  Graph Neural Networks (GNNs) are de facto solutions to structural data learning. Existing graph structure learning (GSL) frameworks still lack robustness and interpretability. This paper proposes a general GSL framework, SE-GSL, through structural entropy and the graph hierarchy abstracted in the encoding tree.
  arXiv  Detail & Related papers  (2023-03-17T05:20:24Z)
• Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs [71.93227401463199]
  This paper pinpoints the major source of GNNs' performance gain to their intrinsic capability, by introducing an intermediate model class dubbed as P(ropagational)MLP. We observe that PMLPs consistently perform on par with (or even exceed) their GNN counterparts, while being much more efficient in training.
  arXiv  Detail & Related papers  (2022-12-18T08:17:32Z)
• Self-Supervised Graph Structure Refinement for Graph Neural Networks [31.924317784535155]
  Graph structure learning (GSL) aims to learn the adjacency matrix for graph neural networks (GNNs) Most existing GSL works apply a joint learning framework where the estimated adjacency matrix and GNN parameters are optimized for downstream tasks. We propose a graph structure refinement (GSR) framework with a pretrain-finetune pipeline.
  arXiv  Detail & Related papers  (2022-11-12T02:01:46Z)
• Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth [57.10183643449905]
  Graph Neural Networks (GNNs) have been studied from the lens of expressive power and generalization. We study the dynamics of GNNs by studying deep skip optimization. Our results provide first theoretical support for the success of GNNs.
  arXiv  Detail & Related papers  (2021-05-10T17:59:01Z)
• Deep Graph Structure Learning for Robust Representations: A Survey [20.564611153151834]
  Graph Neural Networks (GNNs) are widely used for analyzing graph-structured data. To improve the robustness of GNN models, many studies have been proposed around the central concept of Graph Structure Learning.
  arXiv  Detail & Related papers  (2021-03-04T13:49:25Z)
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case [93.37576644429578]
  Graph neural networks (GNNs) have made great progress recently on learning from graph-structured data in practice. We provide a theoretically-grounded generalizability analysis of GNNs with one hidden layer for both regression and binary classification problems.
  arXiv  Detail & Related papers  (2020-06-25T00:45:52Z)
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
  Graph Neural Networks (GNNs) are emerging machine learning models on graphs. Most existing GNN models in practice are shallow and essentially feature-centric. We show empirically and analytically that the existing shallow GNNs cannot preserve graph structures well. We propose Eigen-GNN, a plug-in module to boost GNNs ability in preserving graph structures.
  arXiv  Detail & Related papers  (2020-06-08T02:47:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.