The Transferability of Downsamped Sparse Graph Convolutional Networks

• URL: http://arxiv.org/abs/2408.17274v2
• Date: Sun, 8 Sep 2024 09:31:16 GMT
• Title: The Transferability of Downsamped Sparse Graph Convolutional Networks
• Authors: Qinji Shu, Hang Sheng, Feng Ji, Hui Feng, Bo Hu,
• Abstract summary: We introduce a novel downsampling method based on a sparse random graph model and derive an expected upper bound for the transfer error. Our findings show that smaller original graph sizes, higher expected average degrees, and increased sampling rates contribute to reducing this upper bound. By incorporating both sparsity and topological similarity into the model, this study establishes an upper bound on the transfer error for downsampling in the training of large-scale sparse graphs.
• Score: 12.629928166637
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: To accelerate the training of graph convolutional networks (GCNs) on real-world large-scale sparse graphs, downsampling methods are commonly employed as a preprocessing step. However, the effects of graph sparsity and topological structure on the transferability of downsampling methods have not been rigorously analyzed or theoretically guaranteed, particularly when the topological structure is affected by graph sparsity. In this paper, we introduce a novel downsampling method based on a sparse random graph model and derive an expected upper bound for the transfer error. Our findings show that smaller original graph sizes, higher expected average degrees, and increased sampling rates contribute to reducing this upper bound. Experimental results validate the theoretical predictions. By incorporating both sparsity and topological similarity into the model, this study establishes an upper bound on the transfer error for downsampling in the training of large-scale sparse graphs and provides insight into the influence of topological structure on transfer performance.

Related papers

• Revealing Decurve Flows for Generalized Graph Propagation [108.80758541147418]
  This study addresses the limitations of the traditional analysis of message-passing, central to graph learning, by defining em textbfgeneralized propagation with directed and weighted graphs. We include a preliminary exploration of learned propagation patterns in datasets, a first in the field.
  arXiv  Detail & Related papers  (2024-02-13T14:13:17Z)
• PAC Learnability under Explanation-Preserving Graph Perturbations [15.83659369727204]
  Graph neural networks (GNNs) operate over graphs, enabling the model to leverage the complex relationships and dependencies in graph-structured data. A graph explanation is a subgraph which is an almost sufficient' statistic of the input graph with respect to its classification label. This work considers two methods for leveraging such perturbation invariances in the design and training of GNNs.
  arXiv  Detail & Related papers  (2024-02-07T17:23:15Z)
• Graph Out-of-Distribution Generalization with Controllable Data Augmentation [51.17476258673232]
  Graph Neural Network (GNN) has demonstrated extraordinary performance in classifying graph properties. Due to the selection bias of training and testing data, distribution deviation is widespread. We propose OOD calibration to measure the distribution deviation of virtual samples.
  arXiv  Detail & Related papers  (2023-08-16T13:10:27Z)
• Robust Causal Graph Representation Learning against Confounding Effects [21.380907101361643]
  We propose Robust Causal Graph Representation Learning (RCGRL) to learn robust graph representations against confounding effects. RCGRL introduces an active approach to generate instrumental variables under unconditional moment restrictions, which empowers the graph representation learning model to eliminate confounders.
  arXiv  Detail & Related papers  (2022-08-18T01:31:25Z)
• Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling [83.77955213766896]
  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.
  arXiv  Detail & Related papers  (2022-07-07T21:25:55Z)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  This paper focuses on creating a small graph to represent the original graph, so that GNNs trained on the size-reduced graph can make accurate predictions. We view the original graph as a distribution of receptive fields and aim to synthesize a small graph whose receptive fields share a similar distribution.
  arXiv  Detail & Related papers  (2022-06-28T02:10:05Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• A Graph Data Augmentation Strategy with Entropy Preserving [11.886325179121226]
  We introduce a novel graph entropy definition as a quantitative index to evaluate feature information among a graph. Under considerations of preserving graph entropy, we propose an effective strategy to generate training data using a perturbed mechanism. Our proposed approach significantly enhances the robustness and generalization ability of GCNs during the training process.
  arXiv  Detail & Related papers  (2021-07-13T12:58:32Z)
• Recognizing Predictive Substructures with Subgraph Information Bottleneck [97.19131149357234]
  We propose a novel subgraph information bottleneck (SIB) framework to recognize such subgraphs, named IB-subgraph. Intractability of mutual information and the discrete nature of graph data makes the objective of SIB notoriously hard to optimize. Experiments on graph learning and large-scale point cloud tasks demonstrate the superior property of IB-subgraph.
  arXiv  Detail & Related papers  (2021-03-20T11:19:43Z)
• On the Importance of Sampling in Learning Graph Convolutional Networks [13.713485304798368]
  Graph Convolutional Networks (GCNs) have achieved impressive empirical advancement across a wide variety of graph-related applications. Despite their success, training GCNs on large graphs suffers from computational and memory issues. We describe and analyze a general textbftextitdoubly variance reduction schema that can accelerate any sampling method under the memory budget.
  arXiv  Detail & Related papers  (2021-03-03T21:31:23Z)

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.