Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness

Guibin Zhang, Yanwei Yue, Kun Wang, Junfeng Fang, Yongduo Sui, Kai Wang, Yuxuan Liang, Dawei Cheng, Shirui Pan, Tianlong Chen
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:60197-60219, 2024.

Abstract

Graph Neural Networks (GNNs) excel in various graph learning tasks but face computational challenges when applied to large-scale graphs. A promising solution is to remove non-essential edges to reduce the computational overheads in GNN. Previous literature generally falls into two categories: topology-guided and semantic-guided. The former maintains certain graph topological properties yet often underperforms on GNNs. % due to low integration with neural network training. The latter performs well at lower sparsity on GNNs but faces performance collapse at higher sparsity levels. With this in mind, we propose a new research line and concept termed Graph Sparse Training (GST), which dynamically manipulates sparsity at the data level. Specifically, GST initially constructs a topology & semantic anchor at a low training cost, followed by performing dynamic sparse training to align the sparse graph with the anchor. We introduce the Equilibria Sparsification Principle to guide this process, balancing the preservation of both topological and semantic information. Ultimately, GST produces a sparse graph with maximum topological integrity and no performance degradation. Extensive experiments on 6 datasets and 5 backbones showcase that GST (I) identifies subgraphs at higher graph sparsity levels ($1.67%\sim15.85%$$\uparrow$) than state-of-the-art sparsification methods, (II) preserves more key spectral properties, (III) achieves $1.27-3.42\times$ speedup in GNN inference and (IV) successfully helps graph adversarial defense and graph lottery tickets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-zhang24bx, title = {Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness}, author = {Zhang, Guibin and Yue, Yanwei and Wang, Kun and Fang, Junfeng and Sui, Yongduo and Wang, Kai and Liang, Yuxuan and Cheng, Dawei and Pan, Shirui and Chen, Tianlong}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {60197--60219}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/zhang24bx/zhang24bx.pdf}, url = {https://proceedings.mlr.press/v235/zhang24bx.html}, abstract = {Graph Neural Networks (GNNs) excel in various graph learning tasks but face computational challenges when applied to large-scale graphs. A promising solution is to remove non-essential edges to reduce the computational overheads in GNN. Previous literature generally falls into two categories: topology-guided and semantic-guided. The former maintains certain graph topological properties yet often underperforms on GNNs. % due to low integration with neural network training. The latter performs well at lower sparsity on GNNs but faces performance collapse at higher sparsity levels. With this in mind, we propose a new research line and concept termed Graph Sparse Training (GST), which dynamically manipulates sparsity at the data level. Specifically, GST initially constructs a topology & semantic anchor at a low training cost, followed by performing dynamic sparse training to align the sparse graph with the anchor. We introduce the Equilibria Sparsification Principle to guide this process, balancing the preservation of both topological and semantic information. Ultimately, GST produces a sparse graph with maximum topological integrity and no performance degradation. Extensive experiments on 6 datasets and 5 backbones showcase that GST (I) identifies subgraphs at higher graph sparsity levels ($1.67%\sim15.85%$$\uparrow$) than state-of-the-art sparsification methods, (II) preserves more key spectral properties, (III) achieves $1.27-3.42\times$ speedup in GNN inference and (IV) successfully helps graph adversarial defense and graph lottery tickets.} }
Endnote
%0 Conference Paper %T Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness %A Guibin Zhang %A Yanwei Yue %A Kun Wang %A Junfeng Fang %A Yongduo Sui %A Kai Wang %A Yuxuan Liang %A Dawei Cheng %A Shirui Pan %A Tianlong Chen %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-zhang24bx %I PMLR %P 60197--60219 %U https://proceedings.mlr.press/v235/zhang24bx.html %V 235 %X Graph Neural Networks (GNNs) excel in various graph learning tasks but face computational challenges when applied to large-scale graphs. A promising solution is to remove non-essential edges to reduce the computational overheads in GNN. Previous literature generally falls into two categories: topology-guided and semantic-guided. The former maintains certain graph topological properties yet often underperforms on GNNs. % due to low integration with neural network training. The latter performs well at lower sparsity on GNNs but faces performance collapse at higher sparsity levels. With this in mind, we propose a new research line and concept termed Graph Sparse Training (GST), which dynamically manipulates sparsity at the data level. Specifically, GST initially constructs a topology & semantic anchor at a low training cost, followed by performing dynamic sparse training to align the sparse graph with the anchor. We introduce the Equilibria Sparsification Principle to guide this process, balancing the preservation of both topological and semantic information. Ultimately, GST produces a sparse graph with maximum topological integrity and no performance degradation. Extensive experiments on 6 datasets and 5 backbones showcase that GST (I) identifies subgraphs at higher graph sparsity levels ($1.67%\sim15.85%$$\uparrow$) than state-of-the-art sparsification methods, (II) preserves more key spectral properties, (III) achieves $1.27-3.42\times$ speedup in GNN inference and (IV) successfully helps graph adversarial defense and graph lottery tickets.
APA
Zhang, G., Yue, Y., Wang, K., Fang, J., Sui, Y., Wang, K., Liang, Y., Cheng, D., Pan, S. & Chen, T.. (2024). Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:60197-60219 Available from https://proceedings.mlr.press/v235/zhang24bx.html.

Related Material