Graph Neural Networks (GNNs) have shown promising performance in various
graph learning tasks, but at the cost of resource-intensive computations. The
primary overhead of GNN update stems from graph propagation and weight
transformation, both involving operations on graph-scale matrices. Previous
studies attempt to reduce the computational budget by leveraging graph-level or
network-level sparsification techniques, resulting in downsized graph or
weights. In this work, we propose Unifews, which unifies the two operations in
an entry-wise manner considering individual matrix elements, and conducts joint
edge-weight sparsification to enhance learning efficiency. The entry-wise
design of Unifews enables adaptive compression across GNN layers with
progressively increased sparsity, and is applicable to a variety of
architectural designs with on-the-fly operation simplification. Theoretically,
we establish a novel framework to characterize sparsified GNN learning in view
of a graph optimization process, and prove that Unifews effectively
approximates the learning objective with bounded error and reduced
computational load. We conduct extensive experiments to evaluate the
performance of our method in diverse settings. Unifews is advantageous in
jointly removing more than 90% of edges and weight entries with comparable or
better accuracy than baseline models. The sparsification offers remarkable
efficiency improvements including 10-20x matrix operation reduction and up to
100x acceleration in graph propagation time for the largest graph at the
billion-edge scale.

通过在个别矩阵元素上考虑统一图传播和权重变换操作，并进行联合边权稀疏化以提高学习效率，Unifews 在逐渐增加稀疏性的情况下适用于不同的架构设计，并在理论上证明了较低的计算负载以及稳定的近似学习目标。通过广泛的实验评估，Unifews 在移除超过 90% 的边和权重条目的同时，与基准模型相当或更高的准确性方面具有优势，并在效率方面提供了显着的改进。