research-article

Fast Graph Condensation with Structure-based Neural Tangent Kernel

Authors:

Qing LiAuthors Info & Claims

WWW '24: Proceedings of the ACM Web Conference 2024

Pages 4439 - 4448

https://doi.org/10.1145/3589334.3645694

Published: 13 May 2024 Publication History

Abstract

The rapid development of Internet technology has given rise to a vast amount of graph-structured data. Graph Neural Networks (GNNs), as an effective method for various graph mining tasks, incurs substantial computational resource costs when dealing with large-scale graph data. A data-centric manner solution is proposed to condense the large graph dataset into a smaller one without sacrificing the predictive performance of GNNs. However, existing efforts condense graph-structured data through a computational intensive bi-level optimization architecture also suffer from massive computation costs. In this paper, we propose reforming the graph condensation problem as a Kernel Ridge Regression (KRR) task instead of iteratively training GNNs in the inner loop of bi-level optimization. More specifically, We propose a novel dataset condensation framework (GC-SNTK) for graph-structured data, where a Structure-based Neural Tangent Kernel (SNTK) is developed to capture the topology of graph and serves as the kernel function in KRR paradigm. Comprehensive experiments demonstrate the effectiveness of our proposed model in accelerating graph condensation while maintaining high prediction performance. The source code is available on \hrefhttps://github.com/WANGLin0126/GCSNTK https://github.com/WANGLin0126/GCSNTK.

Supplemental Material

PPTX File

Supplemental video

Download
1.67 MB

References

[1]

Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. 2019. On exact computation with an infinitely wide neural net. Advances in neural information processing systems, Vol. 32 (2019).

[2]

Per Block, Marion Hoffman, Isabel J Raabe, Jennifer Beam Dowd, Charles Rahal, Ridhi Kashyap, and Melinda C Mills. 2020. Social network-based distancing strategies to flatten the COVID-19 curve in a post-lockdown world. Nature Human Behaviour, Vol. 4, 6 (2020), 588--596.

[3]

George Cazenavette, Tongzhou Wang, Antonio Torralba, Alexei A Efros, and Jun-Yan Zhu. 2022. Dataset distillation by matching training trajectories. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 4750--4759.

[4]

Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020. Simple and deep graph convolutional networks. In International conference on machine learning. PMLR, 1725--1735.

[5]

Zhiwei Deng and Olga Russakovsky. 2022. Remember the past: Distilling datasets into addressable memories for neural networks. Advances in Neural Information Processing Systems, Vol. 35 (2022), 34391--34404.

[6]

Tian Dong, Bo Zhao, and Lingjuan Lyu. 2022. Privacy for free: How does dataset condensation help privacy?. In International Conference on Machine Learning. PMLR, 5378--5396.

[7]

Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. 2019. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in neural information processing systems, Vol. 32 (2019).

[8]

Wenqi Fan, Xiaorui Liu, Wei Jin, Xiangyu Zhao, Jiliang Tang, and Qing Li. 2022a. Graph trend filtering networks for recommendation. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. 112--121.

Digital Library

[9]

Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. 2019. Graph neural networks for social recommendation. In The world wide web conference. 417--426.

[10]

Wenqi Fan, Yao Ma, Qing Li, Jianping Wang, Guoyong Cai, Jiliang Tang, and Dawei Yin. 2020. A graph neural network framework for social recommendations. IEEE Transactions on Knowledge and Data Engineering, Vol. 34, 5 (2020), 2033--2047.

[11]

Wenqi Fan, Xiangyu Zhao, Xiao Chen, Jingran Su, Jingtong Gao, Lin Wang, Qidong Liu, Yiqi Wang, Han Xu, Lei Chen, et al. 2022b. A comprehensive survey on trustworthy recommender systems. arXiv preprint arXiv:2209.10117 (2022).

[12]

Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997 (2018).

[13]

Eugene Golikov, Eduard Pokonechnyy, and Vladimir Korviakov. 2022. Neural tangent kernel: A survey. arXiv preprint arXiv:2208.13614 (2022).

[14]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems, Vol. 30 (2017).

[15]

Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, Vol. 33 (2020), 22118--22133.

[16]

Wei Hu, Zhiyuan Li, and Dingli Yu. 2019. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. arXiv preprint arXiv:1905.11368 (2019).

[17]

Arthur Jacot, Franck Gabriel, and Clément Hongler. 2018. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, Vol. 31 (2018).

[18]

Wei Jin, Xianfeng Tang, Haoming Jiang, Zheng Li, Danqing Zhang, Jiliang Tang, and Bing Yin. 2022. Condensing graphs via one-step gradient matching. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 720--730.

Digital Library

[19]

Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. 2021. Graph condensation for graph neural networks. arXiv preprint arXiv:2110.07580 (2021).

[20]

Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016).

[21]

Yann LeCun. 1998. The MNIST database of handwritten digits. http://yann. lecun. com/exdb/mnist/ (1998).

[22]

Saehyung Lee, Sanghyuk Chun, Sangwon Jung, Sangdoo Yun, and Sungroh Yoon. 2022. Dataset condensation with contrastive signals. In International Conference on Machine Learning. PMLR, 12352--12364.

[23]

Can Li, Lei Bai, Wei Liu, Lina Yao, and S Travis Waller. 2020. Graph neural network for robust public transit demand prediction. IEEE Transactions on Intelligent Transportation Systems, Vol. 23, 5 (2020), 4086--4098.

Digital Library

[24]

Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora. 2019. Enhanced convolutional neural tangent kernels. arXiv preprint arXiv:1911.00809 (2019).

[25]

Mengyang Liu, Shanchuan Li, Xinshi Chen, and Le Song. 2022. Graph condensation via receptive field distribution matching. arXiv preprint arXiv:2206.13697 (2022).

[26]

Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. 2021a. Is Homophily a Necessity for Graph Neural Networks?. In International Conference on Learning Representations.

[27]

Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. 2021b. A unified view on graph neural networks as graph signal denoising. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 1202--1211.

Digital Library

[28]

Dougal Maclaurin, David Duvenaud, and Ryan Adams. 2015. Gradient-based hyperparameter optimization through reversible learning. In International conference on machine learning. PMLR, 2113--2122.

[29]

Luke Metz, Niru Maheswaranathan, Jeremy Nixon, Daniel Freeman, and Jascha Sohl-Dickstein. 2019. Understanding and correcting pathologies in the training of learned optimizers. In International Conference on Machine Learning. PMLR, 4556--4565.

[30]

Timothy Nguyen, Zhourong Chen, and Jaehoon Lee. 2020. Dataset meta-learning from kernel ridge-regression. arXiv preprint arXiv:2011.00050 (2020).

[31]

Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. 2013. On the difficulty of training recurrent neural networks. In International conference on machine learning. Pmlr, 1310--1318.

[32]

Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. 2018. Modeling relational data with graph convolutional networks. In The Semantic Web: 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3--7, 2018, Proceedings 15. Springer, 593--607.

Digital Library

[33]

Ozan Sener and Silvio Savarese. 2017. Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXiv:1708.00489 (2017).

[34]

Nikolaos Tsilivis and Julia Kempe. 2022. What Can the Neural Tangent Kernel Tell Us About Adversarial Robustness? Advances in Neural Information Processing Systems, Vol. 35 (2022), 18116--18130.

[35]

Paul Vicol, Luke Metz, and Jascha Sohl-Dickstein. 2021. Unbiased gradient estimation in unrolled computation graphs with persistent evolution strategies. In International Conference on Machine Learning. PMLR, 10553--10563.

[36]

Vladimir Vovk. 2013. Kernel ridge regression. Empirical Inference: Festschrift in Honor of Vladimir N. Vapnik (2013), 105--116.

[37]

Kai Wang, Bo Zhao, Xiangyu Peng, Zheng Zhu, Shuo Yang, Shuo Wang, Guan Huang, Hakan Bilen, Xinchao Wang, and Yang You. 2022. Cafe: Learning to condense dataset by aligning features. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 12196--12205.

[38]

Tongzhou Wang, Jun-Yan Zhu, Antonio Torralba, and Alexei A Efros. 2018. Dataset distillation. arXiv preprint arXiv:1811.10959 (2018).

[39]

Max Welling. 2009. Herding dynamical weights to learn. In Proceedings of the 26th Annual International Conference on Machine Learning. 1121--1128.

Digital Library

[40]

Max Welling. 2013. Kernel ridge regression. Max Welling's classnotes in machine learning (2013), 1--3.

[41]

Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019. Simplifying graph convolutional networks. In International conference on machine learning. PMLR, 6861--6871.

[42]

Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. 2020. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, Vol. 32, 1 (2020), 4--24.

[43]

Zhe Xu, Yuzhong Chen, Menghai Pan, Huiyuan Chen, Mahashweta Das, Hao Yang, and Hanghang Tong. 2023. Kernel Ridge Regression-Based Graph Dataset Distillation. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2850--2861.

Digital Library

[44]

Zhilin Yang, William Cohen, and Ruslan Salakhudinov. 2016. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning. PMLR, 40--48.

[45]

Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. 2019. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.04931 (2019).

[46]

Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski. 2019. Graph convolutional networks: a comprehensive review. Computational Social Networks, Vol. 6, 1 (2019), 1--23.

[47]

Xiao-Meng Zhang, Li Liang, Lin Liu, and Ming-Jing Tang. 2021. Graph neural networks and their current applications in bioinformatics. Frontiers in genetics, Vol. 12 (2021), 690049.

[48]

Yuchen Zhang, John Duchi, and Martin Wainwright. 2013. Divide and conquer kernel ridge regression. In Conference on learning theory. PMLR, 592--617.

[49]

Yanfu Zhang, Shangqian Gao, Jian Pei, and Heng Huang. 2022. Improving social network embedding via new second-order continuous graph neural networks. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining. 2515--2523.

Digital Library

[50]

Bo Zhao and Hakan Bilen. 2021. Dataset condensation with differentiable siamese augmentation. In International Conference on Machine Learning. PMLR, 12674--12685.

[51]

Bo Zhao and Hakan Bilen. 2023. Dataset condensation with distribution matching. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision. 6514--6523.

[52]

Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. 2020. Dataset condensation with gradient matching. arXiv preprint arXiv:2006.05929 (2020).

[53]

Xin Zheng, Miao Zhang, Chunyang Chen, Quoc Viet Hung Nguyen, Xingquan Zhu, and Shirui Pan. 2023. Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data. arXiv preprint arXiv:2306.02664 (2023).

[54]

Fan Zhou, Qing Yang, Ting Zhong, Dajiang Chen, and Ning Zhang. 2020. Variational graph neural networks for road traffic prediction in intelligent transportation systems. IEEE Transactions on Industrial Informatics, Vol. 17, 4 (2020), 2802--2812. io

Cited By

Shokouhinejad HRazavi-Far RHiggins GGhorbani A(2024)Node-Centric Pruning: A Novel Graph Reduction ApproachMachine Learning and Knowledge Extraction10.3390/make60401306:4(2722-2737)Online publication date: 22-Nov-2024
https://doi.org/10.3390/make6040130
Zhang ZHensley CChen Z(2024)Improving Node Classification with Neural Tangent Kernel: A Graph Neural Network ApproachProceedings of the International Conference on Machine Learning, Pattern Recognition and Automation Engineering10.1145/3696687.3696703(93-97)Online publication date: 7-Aug-2024
https://dl.acm.org/doi/10.1145/3696687.3696703
Zhang JChua TNgo CKumar RLauw HKa-Wei Lee R(2024)Graph Unlearning with Efficient Partial RetrainingCompanion Proceedings of the ACM Web Conference 202410.1145/3589335.3651265(1218-1221)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589335.3651265
Show More Cited By

Index Terms

Fast Graph Condensation with Structure-based Neural Tangent Kernel
1. Information systems
  1. Information systems applications
    1. Data mining
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis

Recommendations

EXGC: Bridging Efficiency and Explainability in Graph Condensation
WWW '24: Proceedings of the ACM Web Conference 2024

Graph representation learning on vast datasets, like web data, has made significant strides. However, the associated computational and storage overheads raise concerns. In sight of this, Graph condensation (GCond) has been introduced to distill these ...
Simple Graph Condensation
Machine Learning and Knowledge Discovery in Databases. Research Track
Abstract
The burdensome training costs on large-scale graphs have aroused significant interest in graph condensation, which involves tuning Graph Neural Networks (GNNs) on a small condensed graph for use on the large-scale original graph. Existing methods ...
Graph neural tangent kernel: fusing graph neural networks with graph kernels
NIPS'19: Proceedings of the 33rd International Conference on Neural Information Processing Systems

While graph kernels (GKs) are easy to train and enjoy provable theoretical guarantees, their practical performances are limited by their expressive power, as the kernel function often depends on hand-crafted combinatorial features of graphs. Compared to ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '24: Proceedings of the ACM Web Conference 2024

May 2024

4826 pages

ISBN:9798400701719

DOI:10.1145/3589334

General Chairs:
Tat-Seng Chua
National University of Singapore
,
Chong-Wah Ngo
Singapore Management University
,
Proceedings Chair:
Roy Ka-Wei Lee
Singapore University of Technology and Design
,
Program Chairs:
Ravi Kumar
Google
,
Hady W. Lauw
Singapore Management University

Copyright © 2024 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 May 2024

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

the Hong Kong Research Grants Council
NSFC
The Hong Kong Polytechnic University
SHTM Interdisciplinary Large Grant
Research Collaborative Project

Conference

WWW '24

Sponsor:

SIGWEB

WWW '24: The ACM Web Conference 2024

May 13 - 17, 2024

Singapore, Singapore

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
151
Total Downloads

Downloads (Last 12 months)151
Downloads (Last 6 weeks)23

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shokouhinejad HRazavi-Far RHiggins GGhorbani A(2024)Node-Centric Pruning: A Novel Graph Reduction ApproachMachine Learning and Knowledge Extraction10.3390/make60401306:4(2722-2737)Online publication date: 22-Nov-2024
https://doi.org/10.3390/make6040130
Zhang ZHensley CChen Z(2024)Improving Node Classification with Neural Tangent Kernel: A Graph Neural Network ApproachProceedings of the International Conference on Machine Learning, Pattern Recognition and Automation Engineering10.1145/3696687.3696703(93-97)Online publication date: 7-Aug-2024
https://dl.acm.org/doi/10.1145/3696687.3696703
Zhang JChua TNgo CKumar RLauw HKa-Wei Lee R(2024)Graph Unlearning with Efficient Partial RetrainingCompanion Proceedings of the ACM Web Conference 202410.1145/3589335.3651265(1218-1221)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589335.3651265
Zhang JXue RFan WXu XLi QPei JLiu XChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Linear-Time Graph Neural Networks for Scalable RecommendationsProceedings of the ACM Web Conference 202410.1145/3589334.3645486(3533-3544)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645486

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents