Timezone: »
Condensing Graphs via One-Step Gradient Matching
Wei Jin · Xianfeng Tang · Haoming Jiang · Zheng Li · Danqing Zhang · Jiliang Tang · Bing Yin
Event URL: https://openreview.net/forum?id=WVpAeZd6ooY »
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).
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).
Author Information
Wei Jin (Michigan State University)
Xianfeng Tang (Amazon)
Haoming Jiang (Georgia Institute of Technology)
Zheng Li (Amazon)
Danqing Zhang (Amazon)
Jiliang Tang (Michigan State University)
Bing Yin (A9.com)
More from the Same Authors
-
2022 Poster: pyKT: A Python Library to Benchmark Deep Learning based Knowledge Tracing Models »
Zitao Liu · Qiongqiong Liu · Jiahao Chen · Shuyan Huang · Jiliang Tang · Weiqi Luo -
2022 : Bi-channel Masked Graph Autoencoders for Spatially Resolved Single-cell Transcriptomics Data Imputation »
Hongzhi Wen · Wei Jin · Jiayuan Ding · Christopher Xu · Yuying Xie · Jiliang Tang -
2022 : Graph Neural Networks for Multimodal Single-Cell Data Integration »
Hongzhi Wen · Jiayuan Ding · Wei Jin · Yiqi Wang · Yuying Xie · Jiliang Tang -
2022 Spotlight: pyKT: A Python Library to Benchmark Deep Learning based Knowledge Tracing Models »
Zitao Liu · Qiongqiong Liu · Jiahao Chen · Shuyan Huang · Jiliang Tang · Weiqi Luo -
2022 Poster: Learning to Sample and Aggregate: Few-shot Reasoning over Temporal Knowledge Graphs »
Ruijie Wang · Zheng Li · Dachun Sun · Shengzhong Liu · Jinning Li · Bing Yin · Tarek Abdelzaher -
2022 Poster: A Large Scale Search Dataset for Unbiased Learning to Rank »
Lixin Zou · Haitao Mao · Xiaokai Chu · Jiliang Tang · Wenwen Ye · Shuaiqiang Wang · Dawei Yin -
2022 Poster: Task-Agnostic Graph Explanations »
Yaochen Xie · Sumeet Katariya · Xianfeng Tang · Edward Huang · Nikhil Rao · Karthik Subbian · Shuiwang Ji -
2021 Poster: Graph Neural Networks with Adaptive Residual »
Xiaorui Liu · Jiayuan Ding · Wei Jin · Han Xu · Yao Ma · Zitao Liu · Jiliang Tang -
2019 Poster: Meta Learning with Relational Information for Short Sequences »
Yujia Xie · Haoming Jiang · Feng Liu · Tuo Zhao · Hongyuan Zha -
2019 Poster: Efficient Approximation of Deep ReLU Networks for Functions on Low Dimensional Manifolds »
Minshuo Chen · Haoming Jiang · Wenjing Liao · Tuo Zhao