Source-linked AI summary
Variational Graph Recurrent Neural Networks
Ehsan Hajiramezanali, Arman Hasanzadeh, Nick Duffield, Krishna R Narayanan, Mingyuan Zhou, Xiaoning Qian
TL;DR
Dynamic graph embedding lacks uncertainty modeling despite evolving topology and node attributes, while deterministic recurrent models also struggle with highly variable sequences. The paper proposes VGRNN and SI-VGRNN, which introduce stochastic latent variables and flexible variational inference; both outperform competing methods in dynamic link prediction, with SI-VGRNN gaining 2% over VGRNN on Cora.
Problem
Existing dynamic graph embeddings use deterministic node vectors, while dynamic graphs can change both node and edge sets and recurrent models have limited variability modeling.
Method
VGRNN integrates GRNN with VGAE and high-level stochastic latent variables, while SI-VGRNN adds semi-implicit variational inference for more flexible posteriors.
Results
VGRNN and SI-VGRNN outperform competing methods across dynamic link prediction tasks and datasets; SI-VGRNN improves accuracy by 2% over VGRNN on Cora.
Takeaways & Limitations
Random latent variables support dynamic graph link prediction, while flexible posteriors can improve latent representations when Gaussian structure is insufficient.
Takeaways & Limitations
The model assumes a constant node-attribute dimension across time, and its deterministic GCRN predecessor is limited for highly variable sequences.
Abstract
from arXiv · showhide
Representation learning over graph structured data has been mostly studied in static graph settings while efforts for modeling dynamic graphs are still scant. In this paper, we develop a novel hierarchical variational model that introduces additional latent random variables to jointly model the hidden states of a graph recurrent neural network (GRNN) to capture both topology and node attribute changes in dynamic graphs. We argue that the use of high-level latent random variables in this variational GRNN (VGRNN) can better capture potential variability observed in dynamic graphs as well as the uncertainty of node latent representation. With semi-implicit variational inference developed for this new VGRNN architecture (SI-VGRNN), we show that flexible non-Gaussian latent representations can further help dynamic graph analytic tasks. Our experiments with multiple real-world dynamic graph datasets demonstrate that SI-VGRNN and VGRNN consistently outperform the existing baseline and state-of-the-art methods by a significant margin in dynamic link prediction.
1 Introduction
Dynamic graph embedding must address evolving topology, node attributes, and uncertainty that deterministic representations cannot capture. The paper proposes variational graph recurrent models and semi-implicit inference to improve dynamic graph modeling.
- Motivation: Existing node embedding methods mainly assume static graphs with fixed nodes and edges, although many real-world networks evolve over time.Dynamic graphs occur in social, citation, and financial transaction networks.
- Motivation: Deterministic dynamic graph embeddings cannot model uncertainty arising from multiple information sources, including node attributes and graph structure.
- Approach: The paper introduces GRNN as a dynamic graph autoencoder and extends it to VGRNN by adding high-level latent random variables.The added variables target complex dependencies between topology and time-varying node attributes while modeling uncertainty in node representations.
- Approach: SI-VGRNN combines VGRNN with semi-implicit variational inference to obtain more flexible posteriors and more expressive latent representations.
2 Background
Graph recurrent models combine graph convolutions with recurrent networks, but deterministic hidden-state transitions restrict variability modeling. VGRNN introduces stochastic latent variables, while semi-implicit inference expands the posterior family.
- Graph recurrent networks: GCRN combines graph convolutional and recurrent networks to capture spatial and temporal patterns in node attribute sequences.Its recurrent architecture can use LSTM or GRU-style gated activations with graph convolutional layers replacing deep layers.
- Graph recurrent networks: Because GCRN uses a deterministic transition function, its mapping function provides the only source of variability in the modeled joint distributions.
- Graph recurrent networks: Highly variable sequences can induce large hidden-state variations and potential overfitting, limiting deterministic GCRN modeling.
- Variational graph recurrent networks: VGRNN combines GRNN with VGAE so stochastic latent variables represent nodes with distributions and model temporal dependencies between changing graphs.Its prior construction also supports predicting links at future time steps.
- Semi-implicit inference: Semi-implicit variational inference uses a mixing distribution over posterior parameters to represent skewness, kurtosis, multimodality, and other complex posterior characteristics.The resulting marginal posterior can be implicit and need not have an analytic density.
3 Variational graph recurrent neural network (VGRNN)
VGRNN models dynamic graphs with changing node and edge sets by combining recurrent hidden states with stochastic node representations. SI-VGRNN further uses a semi-implicit hierarchical posterior to obtain more flexible latent distributions.
- 3.1 Overview: VGRNN accepts variable-length adjacency and node-attribute sequences, allowing node and edge sets to change across snapshots.New nodes, disappearing nodes, forming edges, and disappearing edges are permitted.
- 3.2 VGRNN model: Each node at each time step is represented by a distribution, enabling uncertainty in dynamic node embeddings.VGRNN integrates GRNN and VGAE so topological and node-attribute dynamics are modeled jointly.
- 3.2 VGRNN model: The VGRNN generation process uses a VGAE for each graph snapshot, conditioned on the previous GRNN hidden state.The conditional prior and generating distribution may use flexible functions of preceding graph information.
- 3.2 VGRNN model: GRNN hidden states are updated recurrently from time-dependent graph topology, node attributes, and latent variables.Deep feature extractors process X(t) and Z(t), while the hidden state summarizes information through the current snapshot.
- 3.2 VGRNN model: VGRNN parameters are learned by jointly optimizing a variational lower bound for the generative and inference models.The model uses an inner-product decoder in the experiments, while other decoders are possible.
- 3.3 Semi-implicit VGRNN (SI-VGRNN): SI-VGRNN mixes variational posterior parameters through a hierarchical construction, producing a posterior that is not Gaussian after marginalization.Its mixing distribution can be implicit, and direct ELBO optimization requires a derived lower bound because the original objective is intractable.
4 Experiments
Experiments evaluate VGRNN and SI-VGRNN on six real-world dynamic graphs across inductive, dynamic, and new link-prediction settings. Both models generally outperform competing methods, while flexible posteriors help most on Cora and stochastic latent variables are especially beneficial for sparse, weakly clustered graphs.
- Experimental setup: Six real-world dynamic graphs are used to evaluate VGRNN, SI-VGRNN, and competing node-embedding methods.The experiments compare against four competing methods, including recurrent baselines with deterministic hidden states.
- Experimental setup: The evaluation covers inductive link detection, dynamic link prediction, and dynamic new link prediction using AUC and AP scores.Models are evaluated on the final snapshots, with earlier snapshots used for training; HEP-TH uses the final 10 snapshots for testing.
- Dynamic link detection: VGRNN and SI-VGRNN outperform competing methods across all datasets in inductive dynamic link detection.Their gains over GRNN and DynAERNN support the use of latent random variables, while comparison with VGAE indicates that temporal modeling also contributes.
- Dynamic link detection: SI-VGRNN improves accuracy by 2% over VGRNN on Cora, whereas its improvement is marginal on Facebook.The results suggest that flexible posteriors are more useful for Cora, while Gaussian latent variables already represent Facebook adequately.
- Dynamic and new link prediction: VGRNN and SI-VGRNN significantly outperform competing methods in both dynamic and new link prediction across evaluated datasets.GRNN cannot predict edges in the next snapshot, whereas the proposed models use priors based on previous time steps; neither method predicts new nodes.
- Graph structure and interpretability: Performance gains over baselines are more substantial for Facebook than for denser or more clustered graphs such as Enron and COLAB.The authors characterize very sparse graphs with few clusters as difficult to predict and associate the gains with stochastic latent variables capturing temporal trends.
- Graph structure and interpretability: In a simulated graph, latent variance increases for a node moving between communities but remains stable for a node whose community does not change.The authors interpret increased uncertainty as reflecting contradiction between information from previous and current time steps during non-smooth evolution.
5 Conclusion
The paper proposes VGRNN and SI-VGRNN, which embed dynamic-graph nodes as random latent vectors. Both methods substantially outperform competing methods on dynamic link prediction, especially for very sparse graphs.
- VGRNN and SI-VGRNN are presented as the first dynamic-graph node embedding methods that map each node to a random latent vector.
- Adding high-level latent variables increases graph recurrent neural networks' expressiveness for modeling complex graph dynamics.
- The methods generate interpretable random latent representations for nodes.
- SI-VGRNN combines VGRNN with semi-implicit variational inference to provide flexible variational inference.
- VGRNN and SI-VGRNN substantially outperform competing methods on dynamic link prediction, particularly for very sparse graphs.