Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling

• URL: http://arxiv.org/abs/2207.03584v2
• Date: Sun, 10 Dec 2023 16:50:15 GMT
• Title: Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling
• Authors: Hongkang Li, Meng Wang, Sijia Liu, Pin-Yu Chen, Jinjun Xiong
• Abstract summary: Graph convolutional networks (GCNs) have recently achieved great empirical success in learning graphstructured data. To address its scalability issue, graph topology sampling has been proposed to reduce the memory and computational cost of training Gs. This paper provides first theoretical justification of graph topology sampling in training (up to) three-layer GCNs.
• Score: 83.77955213766896
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph convolutional networks (GCNs) have recently achieved great empirical success in learning graph-structured data. To address its scalability issue due to the recursive embedding of neighboring features, graph topology sampling has been proposed to reduce the memory and computational cost of training GCNs, and it has achieved comparable test performance to those without topology sampling in many empirical studies. To the best of our knowledge, this paper provides the first theoretical justification of graph topology sampling in training (up to) three-layer GCNs for semi-supervised node classification. We formally characterize some sufficient conditions on graph topology sampling such that GCN training leads to a diminishing generalization error. Moreover, our method tackles the nonconvex interaction of weights across layers, which is under-explored in the existing theoretical analyses of GCNs. This paper characterizes the impact of graph structures and topology sampling on the generalization performance and sample complexity explicitly, and the theoretical findings are also justified through numerical experiments.

Related papers

• Understanding the Effect of GCN Convolutions in Regression Tasks [8.299692647308323]
  Graph Convolutional Networks (GCNs) have become a pivotal method in machine learning for modeling functions over graphs. This paper provides a formal analysis of the impact of convolution operators on regression tasks over homophilic networks.
  arXiv  Detail & Related papers  (2024-10-26T04:19:52Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  Graph Transformers, which incorporate self-attention and positional encoding, have emerged as a powerful architecture for various graph learning tasks. This paper introduces first theoretical investigation of a shallow Graph Transformer for semi-supervised classification.
  arXiv  Detail & Related papers  (2024-06-04T05:30:16Z)
• On the Topology Awareness and Generalization Performance of Graph Neural Networks [6.598758004828656]
  We introduce a comprehensive framework to characterize the topology awareness of GNNs across any topological feature. We conduct a case study using the intrinsic graph metric the shortest path distance on various benchmark datasets.
  arXiv  Detail & Related papers  (2024-03-07T13:33:30Z)
• Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes [4.23480641508611]
  Graph Neural Networks (GNNs) are theoretically bounded by the 1-Weisfeiler-Lehman test. Our study presents a novel perspective by focusing on simple paths within graphs during the topological message-passing process.
  arXiv  Detail & Related papers  (2023-08-13T19:45:20Z)
• Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks [89.28881869440433]
  This paper provides the first theoretical characterization of joint edge-model sparse learning for graph neural networks (GNNs) It proves analytically that both sampling important nodes and pruning neurons with the lowest-magnitude can reduce the sample complexity and improve convergence without compromising the test accuracy.
  arXiv  Detail & Related papers  (2023-02-06T16:54:20Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• SStaGCN: Simplified stacking based graph convolutional networks [2.556756699768804]
  Graph convolutional network (GCN) is a powerful model studied broadly in various graph structural data learning tasks. We propose a novel GCN called SStaGCN (Simplified stacking based GCN) by utilizing the ideas of stacking and aggregation. We show that SStaGCN can efficiently mitigate the over-smoothing problem of GCN.
  arXiv  Detail & Related papers  (2021-11-16T05:00:08Z)
• Wide Graph Neural Networks: Aggregation Provably Leads to Exponentially Trainability Loss [17.39060566854841]
  Graph convolutional networks (GCNs) and their variants have achieved great success in dealing with graph-structured data. It is well known that deep GCNs will suffer from over-smoothing problem. Few theoretical analyses have been conducted to study the expressivity and trainability of deep GCNs.
  arXiv  Detail & Related papers  (2021-03-03T11:06:12Z)
• Towards Deeper Graph Neural Networks [63.46470695525957]
  Graph convolutions perform neighborhood aggregation and represent one of the most important graph operations. Several recent studies attribute this performance deterioration to the over-smoothing issue. We propose Deep Adaptive Graph Neural Network (DAGNN) to adaptively incorporate information from large receptive fields.
  arXiv  Detail & Related papers  (2020-07-18T01:11:14Z)
• Infinitely Wide Graph Convolutional Networks: Semi-supervised Learning via Gaussian Processes [144.6048446370369]
  Graph convolutional neural networks(GCNs) have recently demonstrated promising results on graph-based semi-supervised classification. We propose a GP regression model via GCNs(GPGC) for graph-based semi-supervised learning. We conduct extensive experiments to evaluate GPGC and demonstrate that it outperforms other state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-02-26T10:02:32Z)

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.