GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings

• URL: http://arxiv.org/abs/2106.05609v1
• Date: Thu, 10 Jun 2021 09:26:56 GMT
• Title: GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings
• Authors: Matthias Fey, Jan E. Lenssen, Frank Weichert, Jure Leskovec
• Abstract summary: GNNAutoScale (GAS) is a framework for scaling arbitrary message-passing GNNs to large graphs. Gas prunes entire sub-trees of the computation graph by utilizing historical embeddings from prior training iterations. Gas reaches state-of-the-art performance on large-scale graphs.
• Score: 51.82434518719011
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present GNNAutoScale (GAS), a framework for scaling arbitrary message-passing GNNs to large graphs. GAS prunes entire sub-trees of the computation graph by utilizing historical embeddings from prior training iterations, leading to constant GPU memory consumption in respect to input node size without dropping any data. While existing solutions weaken the expressive power of message passing due to sub-sampling of edges or non-trainable propagations, our approach is provably able to maintain the expressive power of the original GNN. We achieve this by providing approximation error bounds of historical embeddings and show how to tighten them in practice. Empirically, we show that the practical realization of our framework, PyGAS, an easy-to-use extension for PyTorch Geometric, is both fast and memory-efficient, learns expressive node representations, closely resembles the performance of their non-scaling counterparts, and reaches state-of-the-art performance on large-scale graphs.

Related papers

• Faster Inference Time for GNNs using coarsening [1.323700980948722]
  coarsening-based methods are used to reduce the graph into a smaller one, resulting in faster computation. No previous research has tackled the cost during the inference. This paper presents a novel approach to improve the scalability of GNNs through subgraph-based techniques.
  arXiv  Detail & Related papers  (2024-10-19T06:27:24Z)
• Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity [30.2972965458946]
  Graph Networks (GNNs) are widely applied to graph learning problems such as node classification. When scaling up the underlying graphs of GNNs to a larger size, we are forced to either train on the complete graph or keep the full graph adjacency and node embeddings in memory. This paper proposes a sketch-based algorithm whose training time and memory grow sublinearly with respect to graph size.
  arXiv  Detail & Related papers  (2024-06-21T18:22:11Z)
• A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening [18.688057947275112]
  Subgraph Graph Neural Networks (Subgraph GNNs) enhance the expressivity of message-passing GNNs by representing graphs as sets of subgraphs. Previous approaches suggested processing only subsets of subgraphs, selected either randomly or via learnable sampling. This paper introduces a new Subgraph GNNs framework to address these issues.
  arXiv  Detail & Related papers  (2024-06-13T16:29:06Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  Graph Neural Networks (GNNs) rely on graph convolutions to exploit meaningful patterns in networked data. We propose to learn GNNs on very large graphs by leveraging the limit object of a sequence of growing graphs, the graphon.
  arXiv  Detail & Related papers  (2022-10-27T16:00:45Z)
• Expander Graph Propagation [0.0]
  We propose an elegant approach based on propagating information over expander graphs. We show that EGP is able to address all of the above concerns, while requiring minimal effort to set up. We believe our analysis paves the way to a novel class of scalable methods to counter oversquashing in GNNs.
  arXiv  Detail & Related papers  (2022-10-06T15:36:37Z)
• Scalable Graph Neural Networks for Heterogeneous Graphs [12.44278942365518]
  Graph neural networks (GNNs) are a popular class of parametric model for learning over graph-structured data. Recent work has argued that GNNs primarily use the graph for feature smoothing, and have shown competitive results on benchmark tasks. In this work, we ask whether these results can be extended to heterogeneous graphs, which encode multiple types of relationship between different entities.
  arXiv  Detail & Related papers  (2020-11-19T06:03:35Z)
• Learning to Drop: Robust Graph Neural Network via Topological Denoising [50.81722989898142]
  We propose PTDNet, a parameterized topological denoising network, to improve the robustness and generalization performance of Graph Neural Networks (GNNs) PTDNet prunes task-irrelevant edges by penalizing the number of edges in the sparsified graph with parameterized networks. We show that PTDNet can improve the performance of GNNs significantly and the performance gain becomes larger for more noisy datasets.
  arXiv  Detail & Related papers  (2020-11-13T18:53:21Z)
• Robust Optimization as Data Augmentation for Large-scale Graphs [117.2376815614148]
  We propose FLAG (Free Large-scale Adversarial Augmentation on Graphs), which iteratively augments node features with gradient-based adversarial perturbations during training. FLAG is a general-purpose approach for graph data, which universally works in node classification, link prediction, and graph classification tasks.
  arXiv  Detail & Related papers  (2020-10-19T21:51:47Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGAT is a method to make attention based GNNs lightweight by using spectral sparsification to generate an optimal pruning of the input graph. We experimentally evaluate FastGAT on several large real world graph datasets for node classification tasks.
  arXiv  Detail & Related papers  (2020-06-15T22:07:54Z)

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.