Instant Graph Neural Networks for Dynamic Graphs
Graph Neural Networks (GNNs) have been widely used for modeling
graph-structured data. With the development of numerous GNN variants, recent
years have witnessed groundbreaking results in improving the scalability of
GNNs to work on static graphs with millions of nodes. However, how to instantly
represent continuous changes of large-scale dynamic graphs with GNNs is still
an open problem. Existing dynamic GNNs focus on modeling the periodic evolution
of graphs, often on a snapshot basis. Such methods suffer from two drawbacks:
first, there is a substantial delay for the changes in the graph to be
reflected in the graph representations, resulting in losses on the model's
accuracy; second, repeatedly calculating the representation matrix on the
entire graph in each snapshot is predominantly time-consuming and severely
limits the scalability. In this paper, we propose Instant Graph Neural Network
(InstantGNN), an incremental computation approach for the graph representation
matrix of dynamic graphs. Set to work with dynamic graphs with the edge-arrival
model, our method avoids time-consuming, repetitive computations and allows
instant updates on the representation and instant predictions. Graphs with
dynamic structures and dynamic attributes are both supported. The upper bounds
of time complexity of those updates are also provided. Furthermore, our method
provides an adaptive training strategy, which guides the model to retrain at
moments when it can make the greatest performance gains. We conduct extensive
experiments on several real-world and synthetic datasets. Empirical results
demonstrate that our model achieves state-of-the-art accuracy while having
orders-of-magnitude higher efficiency than existing methods.