Condensing Graphs via One-Step Gradient Matching
Authors:
- Wei JinWJWei Jin
- Xianfeng TangXTXianfeng Tang
- Haoming JiangHJHaoming Jiang
- Zheng LiZLZheng Li
- Danqing ZhangDZDanqing Zhang
- Jiliang TangJTJiliang Tang
- Bing YinBYBing Yin
Preprint
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. 15x in CIFAR10 for synthesizing 500 graphs). Code is available at \url{https://github.com/amazon-research/DosCond}.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Dataset Condensation with Distribution Matching2023
- CAFE: Learning to Condense Dataset by Aligning Features2022
- 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
- A Comprehensive Survey on Graph Neural NetworksIEEE Transactions on Neural Networks and Learning Systems, 2020
- Transferring Robustness for Graph Neural Network Against Poisoning Attacks2020
- A Semi-Supervised Graph Attentive Network for Financial Fraud Detection2019
- DeepGCNs: Can GCNs Go As Deep As CNNs?2019
- Herding dynamical weights to learn2009