Incremental GNN Embedding Computation on Streaming Graphs

A team of researchers has published a paper, "Incremental GNN Embedding Computation on Streaming Graphs," accepted for ICDE 2026, that tackles a major bottleneck in deploying Graph Neural Networks (GNNs) on real-time data. GNNs are powerful for analyzing relationships in data like social networks or financial transactions, but applying them to live, "streaming" graphs is inefficient. The standard method, Runtime Embedding Computation (RTEC), requires recalculating embeddings across the entire graph for every small change, incurring heavy computational overhead from multi-hop graph traversals.

The researchers' key insight was that most of a graph remains unchanged during updates, making most computations redundant. Their novel framework addresses this by decoupling the GNN's message-passing process into a set of generalized, fine-grained operators. It then safely reorders these operators, transforming the expensive full-graph computation into a localized operation focused only on the affected subgraph. This preserves the original model's accuracy while drastically cutting work.

To handle massive graphs, the team also engineered a GPU-CPU co-processing system that intelligently offloads historical embedding data to CPU memory with communication-optimized scheduling, preventing GPU memory bottlenecks. The results are dramatic: experiments across various graph sizes and GNN models show the framework reduces redundant computation by 64% to 99% and delivers speedups ranging from 1.7x to an extraordinary 145.8x compared to state-of-the-art solutions. This makes real-time, low-latency inference on dynamic graphs finally practical.