Subsampling Graphs with GNN Performance Guarantees

• URL: http://arxiv.org/abs/2502.16703v1
• Date: Sun, 23 Feb 2025 20:21:16 GMT
• Title: Subsampling Graphs with GNN Performance Guarantees
• Authors: Mika Sarkin Jain, Stefanie Jegelka, Ishani Karmarkar, Luana Ruiz, Ellen Vitercik,
• Abstract summary: We introduce new subsampling methods for graph datasets.<n>We prove that training a GNN on the subsampled data results in a bounded increase in loss compared to training on the full dataset.
• Score: 34.32848091746629
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: How can we subsample graph data so that a graph neural network (GNN) trained on the subsample achieves performance comparable to training on the full dataset? This question is of fundamental interest, as smaller datasets reduce labeling costs, storage requirements, and computational resources needed for training. Selecting an effective subset is challenging: a poorly chosen subsample can severely degrade model performance, and empirically testing multiple subsets for quality obviates the benefits of subsampling. Therefore, it is critical that subsampling comes with guarantees on model performance. In this work, we introduce new subsampling methods for graph datasets that leverage the Tree Mover's Distance to reduce both the number of graphs and the size of individual graphs. To our knowledge, our approach is the first that is supported by rigorous theoretical guarantees: we prove that training a GNN on the subsampled data results in a bounded increase in loss compared to training on the full dataset. Unlike existing methods, our approach is both model-agnostic, requiring minimal assumptions about the GNN architecture, and label-agnostic, eliminating the need to label the full training set. This enables subsampling early in the model development pipeline (before data annotation, model selection, and hyperparameter tuning) reducing costs and resources needed for storage, labeling, and training. We validate our theoretical results with experiments showing that our approach outperforms existing subsampling methods across multiple datasets.

Related papers

• Data Pruning in Generative Diffusion Models [2.0111637969968]
  Generative models aim to estimate the underlying distribution of the data, so presumably they should benefit from larger datasets. We show that eliminating redundant or noisy data in large datasets is beneficial particularly when done strategically.
  arXiv  Detail & Related papers  (2024-11-19T14:13:25Z)
• TCGU: Data-centric Graph Unlearning based on Transferable Condensation [36.670771080732486]
  Transferable Condensation Graph Unlearning (TCGU) is a data-centric solution to zero-glance graph unlearning. We show that TCGU can achieve superior performance in terms of model utility, unlearning efficiency, and unlearning efficacy than existing GU methods.
  arXiv  Detail & Related papers  (2024-10-09T02:14:40Z)
• Group Distributionally Robust Dataset Distillation with Risk Minimization [17.05513836324578]
  We introduce an algorithm that combines clustering with the minimization of a risk measure on the loss to conduct DD.<n>We provide a theoretical rationale for our approach and demonstrate its effective generalization and robustness across subgroups.
  arXiv  Detail & Related papers  (2024-02-07T09:03:04Z)
• Diving into Unified Data-Model Sparsity for Class-Imbalanced Graph Representation Learning [30.23894624193583]
  Graph Neural Networks (GNNs) training upon non-Euclidean graph data often encounters relatively higher time costs. We develop a unified data-model dynamic sparsity framework named Graph Decantation (GraphDec) to address challenges brought by training upon a massive class-imbalanced graph data.
  arXiv  Detail & Related papers  (2022-10-01T01:47:00Z)
• Condensing Graphs via One-Step Gradient Matching [50.07587238142548]
  We propose a one-step gradient matching scheme, which performs gradient matching for only one single step without training the network weights. Our theoretical analysis shows this strategy can generate synthetic graphs that lead to lower classification loss on real graphs. In particular, we are able to reduce the dataset size by 90% while approximating up to 98% of the original performance.
  arXiv  Detail & Related papers  (2022-06-15T18:20:01Z)
• 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)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  Graph neural networks (GNNs) have been shown powerful capacity at modeling structural data. We present a novel Graph Matching based GNN Pre-Training framework, called GMPT. The proposed method can be applied to fully self-supervised pre-training and coarse-grained supervised pre-training.
  arXiv  Detail & Related papers  (2022-03-03T09:53:53Z)
• Scaling Knowledge Graph Embedding Models [12.757685697180946]
  We propose a new method for scaling training of knowledge graph embedding models for link prediction. Our scaling solution for GNN-based knowledge graph embedding models achieves a 16x speed up on benchmark datasets.
  arXiv  Detail & Related papers  (2022-01-08T08:34:52Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  Semi-supervised learning (SSL) over graph-structured data emerges in many network science applications. To efficiently manage learning over graphs, variants of graph neural networks (GNNs) have been developed recently. Despite their success in practice, most of existing methods are unable to handle graphs with uncertain nodal attributes. Challenges also arise due to distributional uncertainties associated with data acquired by noisy measurements. A distributionally robust learning framework is developed, where the objective is to train models that exhibit quantifiable robustness against perturbations.
  arXiv  Detail & Related papers  (2021-10-20T14:23:54Z)
• Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More [85.52940587312256]
  We propose a model-agnostic certificate based on the randomized smoothing framework which subsumes earlier work and is tight, efficient, and sparsity-aware. We show the effectiveness of our approach on a wide variety of models, datasets, and tasks -- specifically highlighting its use for Graph Neural Networks.
  arXiv  Detail & Related papers  (2020-08-29T10:09:02Z)
• Omni-supervised Facial Expression Recognition via Distilled Data [120.11782405714234]
  We propose omni-supervised learning to exploit reliable samples in a large amount of unlabeled data for network training. We experimentally verify that the new dataset can significantly improve the ability of the learned FER model. To tackle this, we propose to apply a dataset distillation strategy to compress the created dataset into several informative class-wise images.
  arXiv  Detail & Related papers  (2020-05-18T09:36:51Z)

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.