Condensing Graphs via One-Step Gradient Matching
Authors:
Open Access
- 14 August 2022
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 720-730
Abstract
As training deep learning models on large dataset takes a lot of time and resources, it is desired to construct a small synthetic dataset with which we can train deep learning models sufficiently. There are recent works that have explored solutions on condensing image datasets through complex bi-level optimization. For instance, dataset condensation (DC) matches network gradients w.r.t. large-real data and small-synthetic data, where the network weights are optimized for multiple steps at each outer iteration. However, existing approaches have their inherent limitations: (1) they are not directly applicable to graphs where the data is discrete; and (2) the condensation process is computationally expensive due to the involved nested optimization. To bridge the gap, we investigate efficient dataset condensation tailored for graph datasets where we model the discrete graph structure as a probabilistic model. We further 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. Extensive experiments on various graph datasets demonstrate the effectiveness and efficiency of the proposed method. In particular, we are able to reduce the dataset size by 90% while approximating up to 98% of the original performance and our method is significantly faster than multi-step gradient matching (e.g. $15$× in CIFAR10 for synthesizing 500 graphs).Keywords
All Related Versions
Funding Information
- Army Research Office (W911NF-21-1-0198)
- National Science Foundation (IIS1714741, CNS1815636, IIS1845081, IIS1907704, IIS1928278, IIS1955285, IOS2107215, IOS2035472)
This publication has 12 references indexed in Scilit:
- Feature Overcorrelation in Deep Graph Neural Networks2022
- Few-Shot Graph Learning for Molecular Property Prediction2021
- LipschitzLR: Using theoretically computed adaptive learning rates for fast convergenceApplied Intelligence, 2020
- Graph Structure Learning for Robust Graph Neural Networks2020
- Towards Deeper Graph Neural Networks2020
- Transferring Robustness for Graph Neural Network Against Poisoning Attacks2020
- A Semi-Supervised Graph Attentive Network for Financial Fraud Detection2019
- End-to-End Incremental Learning2018
- Herding dynamical weights to learn2009
- Facility Location2009