Hierarchical Estimation for Effective and Efficient Sampling Graph Neural Network

• URL: http://arxiv.org/abs/2211.09813v1
• Date: Wed, 16 Nov 2022 09:16:04 GMT
• Title: Hierarchical Estimation for Effective and Efficient Sampling Graph Neural Network
• Authors: Yang Li, Bingbing Xu, Qi Cao, Yige Yuan and Huawei Shen
• Abstract summary: Existing methods leverage three sampling paradigms including node-wise, layer-wise and subgraph sampling, then design unbiased estimator for scalability. We firstly propose an unified node sampling variance analysis framework and analyze the core challenge "circular dependency" experimental results on seven representative datasets demonstrate the effectiveness and efficiency of our method.
• Score: 18.979153994728
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Improving the scalability of GNNs is critical for large graphs. Existing methods leverage three sampling paradigms including node-wise, layer-wise and subgraph sampling, then design unbiased estimator for scalability. However, the high variance still severely hinders GNNs' performance. On account that previous studies either lacks variance analysis or only focus on a particular sampling paradigm, we firstly propose an unified node sampling variance analysis framework and analyze the core challenge "circular dependency" for deriving the minimum variance sampler, i. e., sampling probability depends on node embeddings while node embeddings can not be calculated until sampling is finished. Existing studies either ignore the node embeddings or introduce external parameters, resulting in the lack of a both efficient and effective variance reduction methods. Therefore, we propose the \textbf{H}ierarchical \textbf{E}stimation based \textbf{S}ampling GNN (HE-SGNN) with first level estimating the node embeddings in sampling probability to break circular dependency, and second level employing sampling GNN operator to estimate the nodes' representations on the entire graph. Considering the technical difference, we propose different first level estimator, i.e., a time series simulation for layer-wise sampling and a feature based simulation for subgraph sampling. The experimental results on seven representative datasets demonstrate the effectiveness and efficiency of our method.

Related papers

• Sparse Decomposition of Graph Neural Networks [20.768412002413843]
  We propose an approach to reduce the number of nodes that are included during aggregation. We achieve this through a sparse decomposition, learning to approximate node representations using a weighted sum of linearly transformed features. We demonstrate via extensive experiments that our method outperforms other baselines designed for inference speedup.
  arXiv  Detail & Related papers  (2024-10-25T17:52:16Z)
• 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)
• Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
  We introduce data structures for solving robust regression through gradient descent (SGD) Our algorithm effectively runs $T$ steps of SGD with importance sampling while using sublinear space and just making a single pass over the data.
  arXiv  Detail & Related papers  (2022-07-16T03:09:30Z)
• ScatterSample: Diversified Label Sampling for Data Efficient Graph Neural Network Learning [22.278779277115234]
  In some applications where graph neural network (GNN) training is expensive, labeling new instances is expensive. We develop a data-efficient active sampling framework, ScatterSample, to train GNNs under an active learning setting. Our experiments on five datasets show that ScatterSample significantly outperforms the other GNN active learning baselines.
  arXiv  Detail & Related papers  (2022-06-09T04:05:02Z)
• Calibrate and Debias Layer-wise Sampling for Graph Convolutional Networks [39.56471534442315]
  This paper revisits the approach from a matrix approximation perspective. We propose a new principle for constructing sampling probabilities and an efficient debiasing algorithm. Improvements are demonstrated by extensive analyses of estimation variance and experiments on common benchmarks.
  arXiv  Detail & Related papers  (2022-06-01T15:52:06Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  We consider the task of heavy-tailed statistical estimation given streaming $p$ samples. We design a clipped gradient descent and provide an improved analysis under a more nuanced condition on the noise of gradients.
  arXiv  Detail & Related papers  (2021-08-25T21:30:27Z)
• Sampling-free Variational Inference for Neural Networks with Multiplicative Activation Noise [51.080620762639434]
  We propose a more efficient parameterization of the posterior approximation for sampling-free variational inference. Our approach yields competitive results for standard regression problems and scales well to large-scale image classification tasks.
  arXiv  Detail & Related papers  (2021-03-15T16:16:18Z)
• 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)
• Bandit Samplers for Training Graph Neural Networks [63.17765191700203]
  Several sampling algorithms with variance reduction have been proposed for accelerating the training of Graph Convolution Networks (GCNs) These sampling algorithms are not applicable to more general graph neural networks (GNNs) where the message aggregator contains learned weights rather than fixed weights, such as Graph Attention Networks (GAT)
  arXiv  Detail & Related papers  (2020-06-10T12:48:37Z)
• Bayesian Graph Neural Networks with Adaptive Connection Sampling [62.51689735630133]
  We propose a unified framework for adaptive connection sampling in graph neural networks (GNNs) The proposed framework not only alleviates over-smoothing and over-fitting tendencies of deep GNNs, but also enables learning with uncertainty in graph analytic tasks with GNNs.
  arXiv  Detail & Related papers  (2020-06-07T07:06:35Z)

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.