Source-linked AI summary
EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao B. Schardl, Charles E. Leiserson
TL;DR
Dynamic-graph methods must handle changing node sets, but existing approaches often rely on node embeddings requiring nodes to be known across the full time span. EvolveGCN evolves GCN parameters with an RNN instead, and generally outperforms related methods across link prediction, edge classification, and node classification.
Problem
Existing dynamic-graph approaches typically use node embeddings and require knowledge of nodes throughout training and testing, limiting applicability when node sets change.
Method
EvolveGCN adapts GCNs over time by using an RNN to evolve their parameters without relying on node embeddings.
Results
EvolveGCN generally outperforms related approaches across link prediction, edge classification, and node classification.
Takeaways & Limitations
Evolving network parameters allows the approach to handle dynamic data without requiring a node to be present throughout the full time span.
Takeaways & Limitations
Version choice is data-set dependent: the -H version may suit informative node features, whereas the -O version may suit structure-dominant graphs.
Abstract
from arXiv · showhide
Graph representation learning resurges as a trending research subject owing to the widespread use of deep learning for Euclidean data, which inspire various creative designs of neural networks in the non-Euclidean domain, particularly graphs. With the success of these graph neural networks (GNN) in the static setting, we approach further practical scenarios where the graph dynamically evolves. Existing approaches typically resort to node embeddings and use a recurrent neural network (RNN, broadly speaking) to regulate the embeddings and learn the temporal dynamics. These methods require the knowledge of a node in the full time span (including both training and testing) and are less applicable to the frequent change of the node set. In some extreme scenarios, the node sets at different time steps may completely differ. To resolve this challenge, we propose EvolveGCN, which adapts the graph convolutional network (GCN) model along the temporal dimension without resorting to node embeddings. The proposed approach captures the dynamism of the graph sequence through using an RNN to evolve the GCN parameters. Two architectures are considered for the parameter evolution. We evaluate the proposed approach on tasks including link prediction, edge classification, and node classification. The experimental results indicate a generally higher performance of EvolveGCN compared with related approaches. The code is available at \url{https://github.com/IBM/EvolveGCN}.
1 Introduction
Dynamic graphs require methods that capture changing relational structure, while common GNN–RNN approaches depend on node embeddings across time. EvolveGCN instead evolves GCN parameters with an RNN, keeping model size independent of the number of time steps.
- Motivation: Static GNNs do not directly address graphs whose nodes and relationships evolve over time.Examples include social networks gaining friendships and citation networks receiving new articles.
- EvolveGCN: EvolveGCN uses an RNN to update GCN network parameters at every time step rather than regulating node embeddings.This model adaptation places the temporal mechanism on the GCN itself, so changing nodes pose no restriction.
- Limitations of prior work: Existing GNN–RNN methods extract node embeddings with a GNN and learn their temporal dynamics using an RNN.These approaches learn one GNN model for all graphs along the temporal axis.
- Limitations of prior work: Such embedding-based methods require knowledge of nodes across the whole time span and provide limited assurance for future new nodes.Frequent node appearance and disappearance also makes irregular behavior difficult for RNNs to learn.
- EvolveGCN: The proposed parameterization keeps model size from growing with time because GCN parameters are computed from the RNN and only RNN parameters are trained.The resulting model remains as manageable as a typical RNN.
2 Related Work
Dynamic-graph research includes efficient matrix-factorization updates, temporal random walks, autoencoding, point processes, and GNN–recurrent hybrids. The related GNN–recurrent approaches generally use GNNs to digest graph information and recurrent models to handle dynamism.
- Matrix factorization: Matrix-factorization methods update graph-Laplacian eigenvector embeddings from prior time steps instead of recomputing them, emphasizing computational efficiency.DANE is given as an example of this approach.
- Random walks: Random-walk methods model history-conditioned transition probabilities through node-embedding inner products, with CTDANE enforcing temporal walk order.NetWalk instead resamples only when the graph changes substantially.
- Deep learning approaches: DynGEM uses an autoencoder with reconstruction and connected-node distance losses, adapting architecture depth to graph size and initializing later models from earlier ones.Its defining mechanism is progressive reuse across time steps.
- Point processes: Continuous-time point-process methods such as Know-Evolve and DyRep model edge occurrences using neural-network intensity functions that take node embeddings as input.Dynamic-Triad extends point-process modeling to triadic closure.
- GNN–recurrent models: The most relevant prior family combines GNNs with recurrent architectures, typically using the GNN to digest graph information and the recurrent component to handle dynamism.Examples include GCRN, WD-GCN/CD-GCN, RgCNN, and STGCN, with differing architectural combinations.
3 Method
EvolveGCN extends GCNs to dynamic graph sequences by evolving GCN parameters with recurrent architectures rather than relying on persistent node embeddings. Its evolving graph convolution unit combines graph convolution across layers with weight evolution over time, using two parameter-evolution variants.
- Graph convolution: At each time step, EvolveGCN processes an adjacency matrix and node-feature matrix with a GCN whose parameters vary across time and layers.Node features initialize the embeddings, which are transformed through graph-convolution layers into representations or prediction probabilities.
- Graph convolution: The GCN layer applies normalized adjacency-based neighborhood aggregation with a weight matrix to update node embeddings.The initial embedding matrix is the input feature matrix, and the output layer can produce high-level node representations or softmax probabilities for node classification.
- Weight evolution: EvolveGCN uses a recurrent architecture to update each layer’s GCN weight matrix from current and historical information.The recurrent architecture may use GRU or LSTM mechanisms, depending on how the weights are assigned recurrent roles.
- Weight evolution: In EvolveGCN-H, GCN weights act as recurrent hidden states updated by a GRU using node embeddings as input.The implementation extends GRU inputs and hidden states from vectors to matrices and summarizes node embeddings to match dimensions.
- Weight evolution: In EvolveGCN-O, GCN weights are recurrent input/output states modeled with an LSTM, without using node embeddings in the recurrent update.The LSTM output becomes the input at the subsequent time step, and the vector formulation is extended to matrices.
- Evolving graph convolution unit: The EGCU combines graph convolution with recurrent weight evolution, and chaining these units across layers and time forms the EvolveGCN model.Graph convolutions proceed vertically across layers while information and weight matrices evolve horizontally across time.
4 Experiments
EvolveGCN is evaluated across diverse dynamic-graph datasets and predictive tasks against static, recurrent-embedding, and unsupervised baselines. Results show strong performance in link and edge classification, while node-classification behavior depends on the comparison and emerging events.
- 4.1 Data Sets: Experiments combine synthetic and public benchmark datasets, with temporal training, validation, and test splits.The evaluation covers varied datasets, tasks, compared methods, and metrics.
- 4.2–4.4 Predictive Tasks: EvolveGCN supports link prediction, edge classification, and node classification through end-to-end trained embeddings and predictive models.Link prediction uses concatenated node embeddings and an MLP; edge classification follows the same pattern, while node classification uses a softmax output.
- 4.5 Results for Link Prediction: At least one EvolveGCN version achieves the best link-prediction result on SBM, UCI, and AS.For BC-OTC and BC-Alpha, EvolveGCN beats both GCN-related baselines but remains below DynGEM and dyngraph2vec.
- 4.6 Results for Edge Classification: Both EvolveGCN versions outperform GCN and GCN-GRU on edge-classification F1 across BC-OTC, BC-Alpha, and Reddit.The same pattern is reported for precision and recall, although those results are omitted from the figure.
- 4.7 Results for Node Classification: On Elliptic minority-class F1, EvolveGCN-O outperforms static GCN but trails GCN-GRU, while dynamic models outperform static modeling overall.Micro averages exceed 0.95 and are considered less informative because licit and illicit transaction classes are highly skewed.
- 4.7 Results for Node Classification: At step 43, all methods perform poorly after the dark-market shutdown, with non-dynamic models suffering the most.Dynamic models also fail to perform reliably because the emerging event was not learned.
5 Conclusions
Dynamic graphs require models that handle continual change rather than assuming a fixed structure. EvolveGCN evolves GNN parameters with an RNN, and experiments report generally higher performance across several dynamic-graph tasks.
- Dynamic graph applications require neural networks to handle graphs that continually evolve rather than remain static.
- EvolveGCN uses an RNN to evolve GNN parameters, capturing graph dynamism in the network rather than in node embeddings.
- EvolveGCN handles changing node membership more flexibly because nodes need not remain present throughout the full time span.
- Experiments report generally higher performance than related approaches for link prediction, edge classification, and node classification.