Source-linked AI summary
Node Embedding over Temporal Graphs
Uriel Singer, Ido Guy, Kira Radinsky
TL;DR
Temporal graph prediction needs node representations that capture changing structure rather than isolated snapshots. The paper introduces tNodeEmbed, which aligns static embeddings across time and jointly combines historical representations with task objectives; it reports gains across diverse datasets and tasks, while prior temporal approaches can face scaling limits.
Problem
Temporal graph prediction requires representations that capture node and edge evolution for tasks such as future link prediction and node classification, while some existing temporal methods face scaling limitations.
Method
tNodeEmbed initializes static node embeddings, aligns representations across time, and jointly learns a task-specific temporal embedding from historical node representations.
Results
tNodeEmbed outperforms or matches baselines across diverse temporal graphs for link prediction and node classification, without underperforming on the evaluated datasets.
Takeaways & Limitations
Temporal embeddings can jointly represent graph structure and dynamics across multiple prediction tasks, with reported benefits across varied graph types and time granularities.
Takeaways & Limitations
Some temporal approaches in the surrounding literature do not scale because of high training-time requirements or node-dependent model parameters.
Abstract
from arXiv · showhide
In this work, we present a method for node embedding in temporal graphs. We propose an algorithm that learns the evolution of a temporal graph's nodes and edges over time and incorporates this dynamics in a temporal node embedding framework for different graph prediction tasks. We present a joint loss function that creates a temporal embedding of a node by learning to combine its historical temporal embeddings, such that it optimizes per given task (e.g., link prediction). The algorithm is initialized using static node embeddings, which are then aligned over the representations of a node at different time points, and eventually adapted for the given task in a joint optimization. We evaluate the effectiveness of our approach over a variety of temporal graphs for the two fundamental tasks of temporal link prediction and multi-label node classification, comparing to competitive baselines and algorithmic alternatives. Our algorithm shows performance improvements across many of the datasets and baselines and is found particularly effective for graphs that are less cohesive, with a lower clustering coefficient.
1 Introduction
The paper introduces tNodeEmbed, a temporal node-embedding method that combines static structure with node histories for dynamic link prediction and classification. It evaluates the approach across temporal networks and finds gains over baselines, especially when graph dynamics are informative.
- Tasks: The method targets dynamic link prediction and multi-label node classification over changing graphs.Examples include predicting future friendships or a person’s future role.
- Method: tNodeEmbed learns node representations that preserve both static network neighborhoods and temporal dynamics.Its joint optimization combines static node embeddings with historical temporal representations.
- Method: It aligns independently learned embeddings across time before combining a node’s historical representations for a task-specific objective.Alignment is intended to distinguish genuine network dynamics from stochastic variation in embedding training.
- Evaluation: The evaluation covers diverse real-world social, biological, and scholarly networks and compares tNodeEmbed with state-of-the-art baselines.The experiments include both temporal link prediction and multi-label node classification.
- Findings: The authors report superior performance across many datasets and baselines, with the method particularly valuable when network structure is less cohesive.They also identify minimum historical behavior as necessary for learning dynamics and limited gains on graphs with higher clustering coefficients.
2 Related Work
Prior temporal-graph methods address evolution through graph-level prediction models, direct task optimization, or matrix-based approaches, but face scaling or representation limitations. This paper positions tNodeEmbed as an end-to-end, task-jointly optimized alternative evaluated across temporal prediction settings.
- Temporal graph methods: Temporal graph research includes graph-level deep models and methods that directly optimize downstream prediction losses.These approaches represent entire graphs or learn task-specific predictors without necessarily learning reusable feature representations.
- Limitations: Several prior temporal methods scale poorly because training time or parameter counts grow with the number of nodes.Other approaches struggle across multiple timestamps or trade scalability for lower performance.
- Feature learning: Classical matrix-based feature learning is difficult to scale because graph eigendecomposition is computationally expensive.Spectral clustering and PCA are examples of dimensionality-reduction approaches applied to graph representations.
- Static embeddings: Static neural graph embeddings achieve strong node-classification and edge-prediction results but primarily model individual graph snapshots.tNodeEmbed extends this feature-learning paradigm to capture temporal behavior.
- Positioning: The proposed architecture is jointly optimized for a given task and is reported to outperform relevant baselines across datasets for temporal link prediction and node classification.This end-to-end design connects temporal representation learning directly to prediction objectives.
3 Feature Learning Framework
The framework learns temporal node representations from graph snapshots, aligns independently trained static embeddings, and jointly optimizes a task-specific final embedding. It supports node classification and link prediction by combining a node’s historical embeddings.
- Framework objective: The framework represents temporal graphs as snapshots and learns node and edge evolution end-to-end for prediction tasks.The target tasks are node classification and link prediction.
- Temporal representation: Node dynamics are modeled recursively with learned matrices, node representations, and an activation function.The initial representation is f0(v)=0, while A, B, Rt, and Qt are learned during training.
- Joint optimization: The complete model minimizes the task loss jointly over the parameters defining the final temporal embedding.The optimization includes A, B, Q1,...,QT, and R2,...,RT.
- Initialization: Static node embeddings initialize each time step, producing a T × d representation per node that is later optimized for the end task.The implementation uses node2vec embeddings for the graph snapshots.
- Temporal alignment: Orthogonal alignment reduces arbitrary differences between independently trained embeddings at consecutive time steps while transforming newly appearing nodes.The alignment uses an orthogonal transformation fitted on nodes present at both time steps.
- Task-specific embedding: An LSTM combines each node’s T historical embeddings into a single d-dimensional representation for supervised prediction.The final temporal embedding is the last LSTM memory state and is optimized for the selected task.
4 Experimental Setup
The experiments cover temporal link prediction and multi-label node classification across real-world networks, using temporal datasets, task-specific splits and metrics, and comparisons with static and temporal baselines.
- Datasets: The datasets span social, biological, and scholarly networks with varied temporal granularities and directed or undirected edges.Examples include Facebook, CollegeMsg, PPI, Slashdot, arXiv hep-ph, Cora, and DBLP.
- Experimental Tasks: The evaluation uses temporal link prediction and multi-label node classification as its two fundamental tasks.Link prediction forecasts future edges, while classification predicts node labels.
- Evaluation Protocol: Link prediction uses a pivot-time train/test split, balanced random negative sampling, and AUC evaluation.Training contains edges at or before the pivot, while test positives occur afterward and involve nodes already present in training.
- Evaluation Protocol: Node classification randomly assigns 80% of nodes to training and reports micro F1, macro F1, and AUC.Macro F1 averages per-class scores, whereas micro F1 is computed globally from true and false predictions.
- Baselines: The comparison includes node2vec, matrix-factorization methods, temporal random-walk and Hawkes-process methods, and DynamicTriad.Baselines use embeddings from the last time step, while node2vec also initializes tNodeEmbed.
5 Experimental Results
Across temporal link prediction and multi-label node classification, tNodeEmbed generally outperforms or matches competing baselines. Its advantage is especially consistent on graphs with lower clustering coefficients, while alignment can affect performance across datasets.
- Temporal Link Prediction: tNodeEmbed outperforms all baselines across three link-prediction datasets and achieves the highest result on all six datasets.It reaches comparable results to other methods on arXiv hep-ph, Facebook friendships, and CollegeMsg.
- Graph Properties: tNodeEmbed tends to perform better than baselines on graphs with lower global clustering coefficients.The authors relate clustering coefficient to graph cohesiveness and note that denser graphs make link appearance easier to predict.
- Multi-Label Node Classification: tNodeEmbed outperforms all baselines across both node-classification datasets and all metrics except DBLP micro F1, which equals TFNM.TFNM’s macro F1 is especially low on DBLP, implying collapse into one label.
- Overall Findings: Overall, the evaluation reports clear performance gains over baselines for both temporal link prediction and node classification.The evaluation also examines real-world and synthetic graphs, clustering coefficient, and the effect of alignment.
- Synthetic Graphs: Across four synthetic degree distributions, tNodeEmbed outperforms node2vec and is comparable with CTDNE.The results are consistent with observations on real-world graphs, and the gap over node2vec is larger when clustering coefficient is lower.
- Alignment: Removing alignment decreases link-prediction performance in three of six datasets, while node-classification results follow the same trends.Alignment is intended to reduce noise from independently trained embeddings by making representations consistent across time points.
6 Conclusions
The framework extends graph embeddings to capture temporal dynamics and jointly optimize node representations with task-specific objectives. It performs across diverse temporal graphs while leaving finer-grained time resolution as future work.
- Unlike prior temporal-graph prediction methods focused on one task, the framework jointly optimizes node representations and task-specific objectives.
- The method is evaluated on diverse large-scale temporal graphs spanning weights, directions, time spans, granularities, and two graph prediction tasks.
- The framework generalizes graph embedding to capture graph dynamics and can adapt any static graph embedding technique into a temporal node embedding.
- Future work will learn embeddings using the best time resolution instead of taking snapshots at discrete time points.