Graph Sequential Neural ODE Process for Link Prediction on Dynamic and Sparse Graphs

Linhao Luo, Reza Haffari, Shirui Pan

TL;DR

Predicting future connections in dynamic graphs (like social networks or e-commerce) is notoriously difficult when data is sparse or arrives at irregular intervals. GSNOP (Graph Sequential Neural ODE Process) addresses this by merging Neural Processes—which model uncertainty to prevent overfitting—with Neural Ordinary Differential Equations (ODEs) to handle the continuous, "choppy" nature of time-evolving interactions.

What Problem Does This Paper Address?

Most real-world graphs are dynamic: social connections and consumer behaviors evolve constantly. Predicting future "links" typically requires extensive historical data. However, many scenarios—such as emerging platforms or niche communities—suffer from extreme sparsity.

Comparison between standard dynamic link prediction and the sparse setting where training data is limited.

Existing Dynamic Graph Neural Networks (DGNNs) struggle in these environments for two primary reasons:

  1. Overfitting: With limited data, models tend to memorize specific historical links rather than learning generalizable patterns.
  2. Irregular Timing: Interactions do not occur at fixed intervals; they arrive in bursts or after long periods of inactivity. Standard discrete-time models fail to capture this continuous "flow."

Methods

The authors propose GSNOP, a flexible framework designed to enhance existing DGNNs. The architecture follows a three-stage process:

The GSNOP architecture, illustrating the flow from context data to target data through latent representations.
  • DGNN Encoder: A standard dynamic graph encoder converts historical interactions into vector representations, capturing the "who, what, and when" of the graph's history.
  • Sequential ODE Aggregator: This is the core innovation. Instead of simple averaging, it uses a Recurrent Neural Network (RNN) to capture event sequences, followed by a Neural ODE to model the derivative of the graph's state. This allows the model to "evolve" the distribution of possible links to any future point in time continuously.
  • Link Prediction Decoder: Utilizing the Neural Process paradigm, GSNOP defines a distribution over functions rather than a single deterministic output. By sampling from this distribution, the model explicitly accounts for uncertainty, preventing it from overcommitting to incorrect predictions when data is sparse.

Datasets and Experimental Setup

The model was evaluated on three continuous-time dynamic graph (CTDG) datasets:

  • WIKI: Wikipedia users and the pages they edit.
  • REDDIT: Users and the subreddits they post in.
  • MOOC: Student interactions with online course materials.

To simulate real-world sparsity, the researchers used only 10% or 30% of historical data for training, requiring the model to predict the remaining 90% or 70% of the timeline.

Key Results

GSNOP consistently outperformed state-of-the-art baselines, with the performance gap widening as data became scarcer:

  • Significant Performance Gains: On the WIKI dataset with 30% training data, GSNOP improved the Average Precision (AP) of the JODIE baseline from 0.3329 to 0.4258.
  • Resilience to Sparsity: While standard DGNN performance dropped sharply when training data was reduced from 100% to 10%, GSNOP remained robust. At 10% training data on WIKI, GSNOP achieved an AP of 0.2979, nearly double the baseline's 0.1820.
  • Advantage over Standard NPs: GSNOP also outperformed other Neural Process variants (like SNP or CNP), validating that the Neural ODE component is essential for modeling dynamic graph evolution.

Key Insights

  • Uncertainty as a Feature: By adopting a stochastic approach, the model acknowledges its lack of information in sparse settings, leading to better generalization on unseen links.
  • Modeling the Derivative: Predicting how a state changes (the derivative) via ODEs is mathematically more robust for irregular time intervals than predicting the next discrete state.
  • Model Agnostic: GSNOP is an "upgrade" rather than a replacement; it can be wrapped around various DGNN architectures to improve their resilience.

Limitations and Future Work

Despite its success, GSNOP has challenges:

  • Hyperparameter Sensitivity: The model is highly sensitive to learning rates. High rates can lead to "gradient explosion" due to the specific ODE solver techniques used.
  • Latent Space Interpretability: The latent variables ($z$ values) do not always map to human-interpretable features.
  • Future Directions: Future research will focus on making the latent space more representative and optimizing ODE integration to reduce computational costs.

Summary updated

Abstract

Link prediction on dynamic graphs is an important task in graph mining. Existing approaches based on dynamic graph neural networks (DGNNs) typically require a significant amount of historical data (interactions over time), which is not always available in practice. The missing links over time, which is a common phenomenon in graph data, further aggravates the issue and thus creates extremely sparse and dynamic graphs. To address this problem, we propose a novel method based on the neural process, called Graph Sequential Neural ODE Process (GSNOP). Specifically, GSNOP combines the advantage of the neural process and neural ordinary differential equation that models the link prediction on dynamic graphs as a dynamic-changing stochastic process. By defining a distribution over functions, GSNOP introduces the uncertainty into the predictions, making it generalize to more situations instead of overfitting to the sparse data. GSNOP is also agnostic to model structures that can be integrated with any DGNN to consider the chronological and geometrical information for link prediction. Extensive experiments on three dynamic graph datasets show that GSNOP can significantly improve the performance of existing DGNNs and outperform other neural process variants.
BibTeX
@inproceedings{luo2022graph,
  author = {Linhao Luo and Reza Haffari and Shirui Pan},
  title = {{Graph Sequential Neural ODE Process for Link Prediction on Dynamic and Sparse Graphs}},
  booktitle = {WSDM},
  year = {2022},
  doi = {10.1145/3539597.3570465},
}
Figure