Brave the Wind and the Waves: Discovering Robust and Generalizable Graph Lottery Tickets

Kun Wang, Yuxuan Liang, Xinglin Li, Guohao Li, Bernard Ghanem, Roger Zimmermann, Zhengyang zhou, Huahui Yi, Yudong Zhang, Yang Wang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

The training and inference of Graph Neural Networks (GNNs) are costly when scaling up to large-scale graphs. Graph Lottery Ticket (GLT) has presented the first attempt to accelerate GNN inference on large-scale graphs by jointly pruning the graph structure and the model weights. Though promising, GLT encounters robustness and generalization issues when deployed in real-world scenarios, which are also long-standing and critical problems in deep learning ideology. In real-world scenarios, the distribution of unseen test data is typically diverse. We attribute the failures on out-of-distribution (OOD) data to the incapability of discerning causal patterns, which remain stable amidst distribution shifts. In traditional spase graph learning, the model performance deteriorates dramatically as the graph/network sparsity exceeds a certain high level. Worse still, the pruned GNNs are hard to generalize to unseen graph data due to limited training set at hand. To tackle these issues, we propose the Resilient Graph Lottery Ticket (RGLT) to find more robust and generalizable GLT in GNNs. Concretely, we reactivate a fraction of weights/edges by instantaneous gradient information at each pruning point. After sufficient pruning, we conduct environmental interventions to extrapolate potential test distribution. Finally, we perform last several rounds of model averages to further improve generalization. We provide multiple examples and theoretical analyses that underpin the universality and reliability of our proposal. Further, RGLT has been experimentally verified across various independent identically distributed (IID) and out-of-distribution (OOD) graph benchmarks. The source code for this work is available at <uri>https://github.com/Lyccl/RGLT</uri> for PyTorch implementation.

Original languageEnglish (US)
Pages (from-to)1-17
Number of pages17
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
DOIs
StateAccepted/In press - 2023

Keywords

  • Computational modeling
  • Deep learning
  • graph convolutional network
  • Graph neural networks
  • lottery ticket hypothesis
  • node classification
  • out-of-distribution generalization
  • Pattern analysis
  • Robustness
  • Special issues and sections
  • Streams
  • Training

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Brave the Wind and the Waves: Discovering Robust and Generalizable Graph Lottery Tickets'. Together they form a unique fingerprint.

Cite this