HERTA: A High-Efficiency and Rigorous Training Algorithm for Unfolded Graph Neural Networks
This work addresses scalability issues for researchers and practitioners using Unfolded GNNs, offering a rigorous solution with convergence guarantees, though it is incremental in improving training efficiency.
The paper tackles the scalability challenges in training Unfolded Graph Neural Networks by proposing HERTA, an algorithm that accelerates training with a nearly-linear time worst-case guarantee while preserving model interpretability, achieving significant speedups in experiments on real-world datasets.
As a variant of Graph Neural Networks (GNNs), Unfolded GNNs offer enhanced interpretability and flexibility over traditional designs. Nevertheless, they still suffer from scalability challenges when it comes to the training cost. Although many methods have been proposed to address the scalability issues, they mostly focus on per-iteration efficiency, without worst-case convergence guarantees. Moreover, those methods typically add components to or modify the original model, thus possibly breaking the interpretability of Unfolded GNNs. In this paper, we propose HERTA: a High-Efficiency and Rigorous Training Algorithm for Unfolded GNNs that accelerates the whole training process, achieving a nearly-linear time worst-case training guarantee. Crucially, HERTA converges to the optimum of the original model, thus preserving the interpretability of Unfolded GNNs. Additionally, as a byproduct of HERTA, we propose a new spectral sparsification method applicable to normalized and regularized graph Laplacians that ensures tighter bounds for our algorithm than existing spectral sparsifiers do. Experiments on real-world datasets verify the superiority of HERTA as well as its adaptability to various loss functions and optimizers.