Graph Structure Learning via Lottery Hypothesis at Scale

Wang Yuxin, Hu Xiannian, Xie Jiaqing, Yin Zhangyue, Zhou Yunhua, Qiu Xipeng, Huang Xuanjing
Proceedings of the 15th Asian Conference on Machine Learning, PMLR 222:1401-1416, 2024.

Abstract

Graph Neural Networks (GNNs) are commonly applied to analyze real-world graph-structured data. However, GNNs are sensitive to the given graph structure, which cast importance on graph structure learning to find optimal graph structures and representations. Previous methods have been restricted from large graphs due to high computational complexity. Lottery ticket hypothesis suggests that there exists a subnetwork that has comparable or better performance with proto-networks, which has been transferred to suit for pruning GNNs recently. There are few studies that address lottery ticket hypothesis’s performance on defense in graphs. In this paper, we propose a scalable graph structure learning method leveraging lottery (ticket) hypothesis : GSL-LH. Our experiments show that GSL-LH can outperform its backbone model without attack and show better robustness against attack, achieving state-of-the-art performances in regular-size graphs compared to other graph structure learning methods without feature augmentation. In large graphs, GSL-LH can have comparable results with state-of-the-art defense methods other than graph structure learning, while bringing some insights into explanation of robustness.

Cite this Paper

BibTeX
@InProceedings{pmlr-v222-yuxin24a, title = {Graph Structure Learning via Lottery Hypothesis at Scale}, author = {Yuxin, Wang and Xiannian, Hu and Jiaqing, Xie and Zhangyue, Yin and Yunhua, Zhou and Xipeng, Qiu and Xuanjing, Huang}, booktitle = {Proceedings of the 15th Asian Conference on Machine Learning}, pages = {1401--1416}, year = {2024}, editor = {Yanıkoğlu, Berrin and Buntine, Wray}, volume = {222}, series = {Proceedings of Machine Learning Research}, month = {11--14 Nov}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v222/yuxin24a/yuxin24a.pdf}, url = {https://proceedings.mlr.press/v222/yuxin24a.html}, abstract = {Graph Neural Networks (GNNs) are commonly applied to analyze real-world graph-structured data. However, GNNs are sensitive to the given graph structure, which cast importance on graph structure learning to find optimal graph structures and representations. Previous methods have been restricted from large graphs due to high computational complexity. Lottery ticket hypothesis suggests that there exists a subnetwork that has comparable or better performance with proto-networks, which has been transferred to suit for pruning GNNs recently. There are few studies that address lottery ticket hypothesis’s performance on defense in graphs. In this paper, we propose a scalable graph structure learning method leveraging lottery (ticket) hypothesis : GSL-LH. Our experiments show that GSL-LH can outperform its backbone model without attack and show better robustness against attack, achieving state-of-the-art performances in regular-size graphs compared to other graph structure learning methods without feature augmentation. In large graphs, GSL-LH can have comparable results with state-of-the-art defense methods other than graph structure learning, while bringing some insights into explanation of robustness.} }
Endnote
%0 Conference Paper %T Graph Structure Learning via Lottery Hypothesis at Scale %A Wang Yuxin %A Hu Xiannian %A Xie Jiaqing %A Yin Zhangyue %A Zhou Yunhua %A Qiu Xipeng %A Huang Xuanjing %B Proceedings of the 15th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Berrin Yanıkoğlu %E Wray Buntine %F pmlr-v222-yuxin24a %I PMLR %P 1401--1416 %U https://proceedings.mlr.press/v222/yuxin24a.html %V 222 %X Graph Neural Networks (GNNs) are commonly applied to analyze real-world graph-structured data. However, GNNs are sensitive to the given graph structure, which cast importance on graph structure learning to find optimal graph structures and representations. Previous methods have been restricted from large graphs due to high computational complexity. Lottery ticket hypothesis suggests that there exists a subnetwork that has comparable or better performance with proto-networks, which has been transferred to suit for pruning GNNs recently. There are few studies that address lottery ticket hypothesis’s performance on defense in graphs. In this paper, we propose a scalable graph structure learning method leveraging lottery (ticket) hypothesis : GSL-LH. Our experiments show that GSL-LH can outperform its backbone model without attack and show better robustness against attack, achieving state-of-the-art performances in regular-size graphs compared to other graph structure learning methods without feature augmentation. In large graphs, GSL-LH can have comparable results with state-of-the-art defense methods other than graph structure learning, while bringing some insights into explanation of robustness.
APA
Yuxin, W., Xiannian, H., Jiaqing, X., Zhangyue, Y., Yunhua, Z., Xipeng, Q. & Xuanjing, H.. (2024). Graph Structure Learning via Lottery Hypothesis at Scale. Proceedings of the 15th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 222:1401-1416 Available from https://proceedings.mlr.press/v222/yuxin24a.html.

Related Material