Holistic Prediction on a Time-Evolving Attributed Graph

Shohei Yamasaki, Yuya Sasaki, Panagiotis Karras, Makoto Onizuka

Abstract

Real-world networks are dynamic entities where nodes, links, and attributes evolve simultaneously. Traditional graph prediction models often compartmentalize these tasks, treating the appearance of new links or the disappearance of nodes as independent events. This paper introduces AGATE (A General framework for predicting Attributed Time-Evolving graphs), a modular framework that treats these tasks as an interdependent whole. By employing a novel reuse mechanism, AGATE allows sub-prediction tasks to inform one another, capturing deep interdependencies. We also present PROSER, a method for predicting attributes of new nodes, and TGGNN, a graph neural network designed for shifting topologies. Evaluations on NBA, Reddit, and AMiner datasets show that AGATE significantly improves accuracy over state-of-the-art independent models.

Introduction: The Challenge of Dynamic Graphs

Most real-world networks—ranging from social media platforms to citation graphs—are "time-evolving attributed graphs." They are characterized by constant flux: users join or leave, profiles are updated, and new connections are formed.

Overview of the holistic graph prediction task.

Current research often suffers from two major limitations:

  1. Compartmentalization: Existing techniques typically focus on a single aspect, such as link prediction or node classification, ignoring the fact that these events are often correlated. For example, a new user's attributes heavily influence their initial connections.
  2. The "New Node" Problem: Predicting the arrival of entirely new nodes and their associated attributes remains a significant challenge for models that primarily learn from existing graph structures.

The AGATE Framework

To address these gaps, we propose AGATE, a unified framework designed for holistic graph prediction. AGATE operates through a structured three-stage pipeline that emphasizes the interdependence of graph evolution.

The three-stage architecture of the AGATE framework.

1. Graph Size Prediction

The process begins by estimating the scale of change. Using a Long Short-Term Memory (LSTM) network, the model predicts the number of nodes and links to be added or removed in the subsequent time step. This provides a structural budget for the following stages.

2. Independent Prediction

In this stage, specialized models generate "first draft" predictions for various sub-tasks, including node loss, link changes, and attribute updates. These initial predictions serve as the foundation for the holistic refinement process.

3. Reuse Mechanism

The core innovation of AGATE is the reuse mechanism. Instead of treating the initial predictions as final, they are fed back into the models. For instance, the predicted attributes of a new node can refine the prediction of its potential links. This iterative process allows the framework to capture complex, multi-way dependencies between different types of graph changes.

Specialized Components: PROSER and TGGNN

Beyond the general framework, we introduce two specific components to enhance performance:

  • PROSER (Probabilistic Selection Rule): To solve the "New Node" problem, PROSER uses logistic regression to learn the historical distribution of attributes for new arrivals. This ensures that predicted new nodes possess realistic and diverse attributes, avoiding the "averaging" effect common in standard neural networks.
  • TGGNN (Time-directed Gated Graph Neural Network): This architecture is specifically tailored for dynamic graphs. It handles shifting topologies more effectively than standard Graph Convolutional Networks (GCNs) by incorporating temporal gating mechanisms.

Experimental Evaluation

We evaluated AGATE on three diverse real-world datasets:

  • NBA: A highly dynamic dataset (players as nodes, teammates as links) where nodes, links, and attributes (e.g., points, age) all change.
  • Reddit: A dataset where nodes (subreddits) and links (posts) change, but node attributes remain static.
  • AMiner: A citation network that grows over time but lacks node disappearance.

Key Results and Insights

  • Interdependence as a Catalyst: The holistic approach yielded dramatic improvements. In the NBA dataset, the ROC AUC for predicting node loss improved from approximately 85% to over 98% when using the full AGATE framework compared to independent baselines.
  • Optimal Iteration: While the reuse mechanism is powerful, accuracy typically peaks after one or two iterations. Excessive iteration can lead to error accumulation, where inaccuracies in one sub-task begin to degrade others.
  • Superior Attribute Matching: AGATE, powered by PROSER, achieved significantly higher matching similarity for new node attributes on the NBA and Reddit datasets compared to standard feedforward network baselines.
  • Scalability: Despite its holistic nature, AGATE remains efficient. Inference on real-world graphs typically takes less than 10 seconds, with computational costs scaling linearly with the number of nodes.

Conclusion and Future Directions

AGATE represents a significant shift from fragmented to holistic graph prediction. By acknowledging and modeling the interdependencies of network evolution, it achieves state-of-the-art performance across multiple tasks. Future work will focus on extending the framework to handle directed and labeled edges, as well as exploring automated hyperparameter optimization to further refine the holistic pipeline.

Summary updated

BibTeX
@inproceedings{yamasaki2023holistic,
  author = {Shohei Yamasaki and Yuya Sasaki and Panagiotis Karras and Makoto Onizuka},
  title = {{Holistic Prediction on a Time-Evolving Attributed Graph}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2023},
  doi = {10.18653/v1/2023.acl-long.765},
}
Figure