Dynamic GNN Adaptation via Cached Propagation and SVD-Guided Selective Optimization

Graph neural networks offer a potent mechanism for learning on graph data across domains and tasks. A vast majority of these mechanisms assume that the underlying graph and the corresponding node/edge attributes are static, and do not change over time. However, graphs corresponding to most real-world phenomena evolve via the addition or deletion of nodes and edges, or changes to node/edge attributes. This paper proposes efficient solutions for maintaining the GNN over such evolving graphs without recourse to full retraining. Our solution use cached propagation for the forward passes and a spectral value decomposition based selective optimization for the backward passes. We adapt our solution to two representative GNN architectures, Graph Convolution Networks (GCNs) and Graph Sample and Aggregate (SAGE) over two downstream tasks: node classification and link prediction. Extensive experimental evaluation indicates that our solutions offer competitive accuracy and speedup over existing dynamic GNN methods while keeping the spectral drift small.