Unifews: You Need Fewer Operations for Efficient Graph Neural Networks

Graph Neural Networks (GNNs) have shown promising performance, but at the cost of resource-intensive operations on graph-scale matrices. To reduce computational overhead, previous studies attempt to sparsify the graph or network parameters, but with limited flexibility and precision boundaries. In this work, we propose Unifews, a joint sparsification technique to unify graph and weight matrix operations and enhance GNN learning efficiency. The Unifews design enables adaptive compression across GNN layers with progressively increased sparsity, and is applicable to a variety of architectures with on-the-fly simplification. Theoretically, we establish a novel framework to characterize sparsified GNN learning in view of the graph optimization process, showing that Unifews effectively approximates the learning objective with bounded error and reduced computational overhead. Extensive experiments demonstrate that Unifews achieves efficiency improvements with comparable or better accuracy, including 10-20x matrix operation reduction and up to 100x acceleration on graphs up to billion-edge scale.

Artificial Intelligence models can understand complex network-structured data, like the web of friendships on a social media platform. These systems, known as Graph Neural Networks (GNNs), are powerful but require enormous computational resources, making them slow and costly, especially for the massive networks common in real-world scenarios. In our research, we aimed to make these GNNs more efficient. We developed Unifews, a technique that simplifies the data structure and the model parameters at the same time. We developed a theory showing that these two components can be computed in a unified way, effectively trimming the unnecessary details while focusing on critical information.Tests show that Unifews dramatically speeds up computation by up to 100 times. This advancement allows sophisticated GNNs to analyze much larger, more complex networks, or deliver results faster using simpler and cheaper hardware, like a single GPU.