Less Can Be More: Unsupervised Graph Pruning for Large-scale Dynamic
  Graphs
Jintang Li Sheng Tian Ruofan Wu Liang Zhu Welong Zhao Changhua Meng Liang Chen Zibin Zheng Hongzhi Yin
The prevalence of large-scale graphs poses great challenges in time and
storage for training and deploying graph neural networks (GNNs). Several recent
works have explored solutions for pruning the large original graph into a small
and highly-informative one, such that training and inference on the pruned and
large graphs have comparable performance. Although empirically effective,
current researches focus on static or non-temporal graphs, which are not
directly applicable to dynamic scenarios. In addition, they require labels as
ground truth to learn the informative structure, limiting their applicability
to new problem domains where labels are hard to obtain. To solve the dilemma,
we propose and study the problem of unsupervised graph pruning on dynamic
graphs. We approach the problem by our proposed STEP, a self-supervised
temporal pruning framework that learns to remove potentially redundant edges
from input dynamic graphs. From a technical and industrial viewpoint, our
method overcomes the trade-offs between the performance and the time & memory
overheads. Our results on three real-world datasets demonstrate the advantages
on improving the efficacy, robustness, and efficiency of GNNs on dynamic node
classification tasks. Most notably, STEP is able to prune more than 50% of
edges on a million-scale industrial graph Alipay (7M nodes, 21M edges) while
approximating up to 98% of the original performance. Code is available at
https://github.com/EdisonLeeeee/STEP.