Source-linked AI summary
Streaming Graph Neural Networks
Yao Ma, Ziyi Guo, Zhaochun Ren, Eric Zhao, Jiliang Tang, Dawei Yin
TL;DR
Existing graph neural networks mainly model static graphs, despite the evolving structure and useful temporal information of many real-world graphs. DGNN jointly updates interacting nodes and propagates information to influenced nodes while modeling interaction order and time intervals, and experiments report effectiveness across dynamic graphs and tasks.
Problem
Most existing graph neural networks are designed for static graphs and cannot use dynamic information from evolving graphs, although that information benefits graph analytic tasks.
Method
DGNN coherently captures interaction sequences, time intervals, node-information updates, and propagation to influenced nodes in dynamic graphs.
Results
Experiments on real-world dynamic graphs report that DGNN outperforms baselines in most cases across link prediction and node classification.
Takeaways & Limitations
The reported results support modeling dynamic information through DGNN's update and propagation components for graph mining tasks.
Takeaways & Limitations
The current model chooses neighbors as influenced nodes, while theoretical analysis and alternative definitions remain future work; edge and node deletion is also left unmodeled.
Abstract
from arXiv · showhide
Graphs are essential representations of many real-world data such as social networks. Recent years have witnessed the increasing efforts made to extend the neural network models to graph-structured data. These methods, which are usually known as the graph neural networks, have been applied to advance many graphs related tasks such as reasoning dynamics of the physical system, graph classification, and node classification. Most of the existing graph neural network models have been designed for static graphs, while many real-world graphs are inherently dynamic. For example, social networks are naturally evolving as new users joining and new relations being created. Current graph neural network models cannot utilize the dynamic information in dynamic graphs. However, the dynamic information has been proven to enhance the performance of many graph analytic tasks such as community detection and link prediction. Hence, it is necessary to design dedicated graph neural networks for dynamic graphs. In this paper, we propose DGNN, a new {\bf D}ynamic {\bf G}raph {\bf N}eural {\bf N}etwork model, which can model the dynamic information as the graph evolving. In particular, the proposed framework can keep updating node information by capturing the sequential information of edges (interactions), the time intervals between edges and information propagation coherently. Experimental results on various dynamic graphs demonstrate the effectiveness of the proposed framework.
1 INTRODUCTION
Existing graph neural networks largely target static graphs, although many real-world graphs evolve and their temporal information benefits graph analytics. DGNN is proposed to update and propagate node information while modeling interaction order and timing.
- Graphs represent objects and pairwise relations in social, transportation, and e-commerce networks, motivating neural models specialized for graph-structured data.
- Most existing graph neural networks assume static graphs, whereas real-world networks evolve through new nodes, edges, and interactions.
- Dynamic information has improved graph analytic tasks including community detection, link prediction, and network embedding.
- DGNN addresses three questions: updating nodes after new interactions, propagating information to influenced nodes, and incorporating interaction intervals.
- The paper proposes a principled update-and-propagation approach and evaluates DGNN on graph-related tasks across real-world dynamic graphs.
2 THE PROPOSED FRAMEWORK
DGNN models dynamic graphs with separate update and propagation components. New interactions update their endpoint nodes, while interaction information is propagated to influenced nodes.
- The framework is presented through an overview before the paper details each component and its parameter-learning approach.
- The framework defines a dynamic graph as nodes and evolving edges or nodes, while considering only additions and leaving deletions for future work.
- DGNN has two major components: an update component for interacting nodes and a propagation component for influenced nodes.
- When a new interaction occurs, the update component incorporates its information into both endpoint nodes.
- The propagation component sends new interaction information to influenced nodes, whose definition can vary; the example uses nodes that interacted with either endpoint.
2.1 The update component
DGNN updates interacting nodes by processing their interaction histories sequentially and incorporating elapsed time into recurrent updates. The update component uses role-specific memories, hidden states, and merge operations to produce refreshed node information.
- The update component: Interactions involving a node are processed as a sequence so their order can capture evolving node properties.The update component is recurrently applied to interaction information rather than treating interactions as unordered.
- The interact unit: The interact unit computes interaction information from the general features of the source and target nodes before the interaction.A feedforward neural network combines the two node representations through learned parameters and an activation function.
- The update unit: The update unit receives prior cell memory, hidden state, time interval, and interaction information, then outputs updated memory and hidden state.DGNN uses separate S-Update and G-Update units for source and target roles, with shared structure but different parameters.
- The update unit: Elapsed time controls forgetting by discounting short-term memory while preserving long-term memory.The discount function decreases with larger time intervals, and the adjusted memory is then passed into the standard LSTM portion.
- The merge unit: The merge unit combines a node’s source and target hidden states to generate its updated general features.These merged features represent the node’s general property after the interacting-node updates.
2.2 The propagation component
The propagation component sends new interaction information from the interacting nodes to their current neighbors, using attention, time decay, and threshold-based filtering.
- Propagation considers the current neighbors of both interacting nodes as influenced nodes because new interactions change local graph structure.
- The component contains interact, prop, and merge units; the interact and merge units are shared with the update component.
- Four prop-unit types transmit information from each interacting node to its source or target neighbors, with separate parameters for each direction.
- Propagation uses the interval since a neighbor’s last interaction with the source node as a time-dependent factor.
- Figure 5 illustrates propagation from source node v2 to source neighbor v7 after interaction {v2,v5,t7}.
- If that interval exceeds threshold τ, propagation stops for the neighbor, reducing computation and filtering extremely old neighbors.
2.3 Parameter learning
DGNN learns parameters for link prediction and node classification using temporal interaction information, sequential mini-batches, negative sampling, and semi-supervised updates.
- DGNN supports multiple network-analysis tasks, with link prediction and node classification used to illustrate parameter learning.
- For link prediction, DGNN projects interacting nodes’ general features into source and target roles before applying a temporal graph-based loss.
- The interaction probability is modeled with a sigmoid applied to the inner product of the role-specific node features.
- The link-prediction loss uses Q negative samples drawn from distribution Pn(v), and the total loss aggregates interactions through time T.
- Mini-batches preserve temporal interaction order rather than randomly sampling edges, while negative samples use a uniform distribution over nodes in each mini-batch.
- Node classification uses cross-entropy loss after projecting each node’s representation into Nc class scores.
- Training is semi-supervised: labeled and unlabeled nodes participate in DGNN’s update and propagation components.
3 EXPERIMENTS
The experiments evaluate DGNN on dynamic graph datasets using link prediction and node classification, with dataset statistics reported in Table 1.
- The experiments use link prediction and node classification to demonstrate the effectiveness of DGNN.
- Three datasets are evaluated, with their important statistics summarized in Table 1.
- UCI represents directed message communications among users in an online student community, with edge creation times available for link prediction.
- DNC represents directed email communications from the 2016 Democratic National Committee email leak, where directed edges encode sender-to-recipient messages.
3.2 Link prediction
The link-prediction experiments compare DGNN with static and dynamic graph representation methods using temporally ordered interaction splits and ranking metrics.
- The evaluation compares representative graph neural networks, static embeddings, dynamic embeddings, and a tensor-based dynamic method.
- Static baselines such as GCN, GraphSage, and node2vec ignore edge-time information, whereas DynGEM requires snapshot-based dynamic data.
- Link prediction trains on the first 80% of edges, validates on 10%, and tests on the next 10% in temporal order.
- MRR measures the mean reciprocal rank of ground-truth nodes, with higher values indicating more top-ranked ground truths.
- Recall@20 and Recall@50 measure how many ground-truth nodes rank within the corresponding top-k positions.
- DGNN outperforms GCN and GraphSage and beats most baselines across all three datasets.
- Dynamic embedding methods outperform node2vec in most cases, suggesting that dynamic information is important for link prediction.
3.3 Node classification
The node-classification experiments evaluate DGNN against GCN, GraphSage, and label propagation under semi-supervised settings on Epinions. DGNN performs best across the tested settings, highlighting the role of temporal information.
- Experimental setting: Node classification is evaluated as semi-supervised inference of hidden node labels, using GCN, GraphSage, and LP as comparison methods.The evaluation hides 20% of node labels for validation and testing, while varying the labeled fraction among the remaining nodes.
- Experimental setting: Only the Epinions dataset contains label information, so node classification is conducted on that dataset.
- Experimental results: DGNN, GraphSage, and GCN outperform LP in all settings, indicating stronger performance from GNN-based methods in semi-supervised learning.
- Experimental results: DGNN outperforms GraphSage and GCN under all three settings, showing the importance of temporal information for node classification.
3.4 Model Component analysis
The component analysis removes propagation, time-interval information, or attention from DGNN and evaluates the resulting variants on link prediction. Removing any component reduces performance, supporting the value of all three design choices.
- Model variants: The analysis constructs DGNN-prop, DGNN-ti, and DGNN-att by removing propagation, temporal intervals, and attention, respectively.
- Findings: Removing propagation tests whether interaction information must reach nodes beyond the two directly involved in a new edge.
- Findings: Removing attention treats influenced nodes as having equal influence, whereas DGNN captures varied influence during propagation.
- Findings: All three component removals reduce link-prediction performance, indicating that propagation, time intervals, and varied influence each contribute to DGNN.
3.5 Parameter Analysis
The parameter analysis studies how DGNN’s propagation threshold τ affects link prediction on UCI. Performance improves as τ grows initially, then stabilizes or slightly declines after τ reaches 50.
- Parameter analysis: The analysis varies propagation threshold τ for UCI link prediction using MRR as the evaluation measure.The study reports similar observations under other settings and datasets.
- Parameter analysis: Performance first increases as τ becomes larger because a larger threshold propagates interaction information to more influenced nodes.
- Parameter analysis: After τ reaches 50, performance becomes stable or slightly decreases, suggesting that extremely old neighbors may add noise rather than useful information.
- Practical implication: Choosing a proper τ can improve efficiency by restricting propagation to a small number of influenced nodes.
4 RELATED WORK
Related work spans graph neural networks and dynamic graph analysis. Existing GNNs support diverse graph tasks but are predominantly designed for static graphs, whereas real-world graphs often evolve over time.
- Graph neural networks: Graph neural networks extend deep neural networks to graph-structured data and have been applied across multiple graph-analysis tasks.
- Graph neural networks: Prior GNN applications include physical-system dynamics, molecular property prediction, graph classification, node classification, and recommendation.
- Dynamic graph analysis: Most current GNN models assume static graphs with fixed nodes and edges.
- Dynamic graph analysis: Dynamic graph research studies evolving networks and tasks including community detection, link prediction, node classification, and knowledge-graph mining.
5 CONCLUSION
DGNN combines update and propagation components to model dynamic graphs, capturing edge order, interaction intervals, and influence strengths. Experiments address link prediction and node classification, while the current influence-set choice remains open to theoretical and empirical investigation.
- 5 CONCLUSION: DGNN uses update and propagation components to model dynamic graphs as new edges are introduced.The update component captures edge-creation order and time intervals; propagation transfers new interaction information to influenced nodes using influence strengths.
- 5 CONCLUSION: Experiments on three real-world dynamic graphs cover link prediction and node classification, with results supporting dynamic information and both proposed components.
- 5 CONCLUSION: The model currently defines influenced nodes as a node’s neighbors, leaving theoretical analysis, alternative influence sets, and other tasks such as unsupervised community detection for future work.