Discrete-time Temporal Network Embedding via Implicit Hierarchical Learning in Hyperbolic Space

Menglin Yang; Min Zhou; Marcus Kalander; Zengfeng Huang; Irwin King

Source-linked AI summary

Discrete-time Temporal Network Embedding via Implicit Hierarchical Learning in Hyperbolic Space

Menglin Yang, Min Zhou, Marcus Kalander, Zengfeng Huang, Irwin King

arXiv:2107.03767v2Jul 8, 2021cs.SIcs.AI

TL;DR

Temporal graph embedding commonly uses Euclidean space, which may inadequately capture hierarchical structure in evolving networks. HTGN instead combines hyperbolic graph and recurrent networks with historical attention and temporal consistency, and it outperforms competing methods across temporal link prediction tasks. The DISEASE evaluation has a specific scope because all its test edges are new.

Problem
Existing temporal graph embedding methods model temporal dependencies and topology evolution in Euclidean space, despite the hierarchical properties of many temporal networks.
Method
HTGN maps temporal snapshots into hyperbolic space and combines HGNN, HGRU, HTA, and HTC to model topology, temporal patterns, historical states, and consistency.
Results
HTGN consistently outperforms competing temporal graph embedding methods, achieving an average AUC gain of 4.28% over the best baseline on link prediction.
Takeaways & Limitations
The results and ablations support hyperbolic geometry and the HTA and HTC modules as effective components for temporal graph embedding.
Takeaways & Limitations
On DISEASE, all test-set edges are new, so new link prediction and link prediction results are equivalent.

Abstract

from arXiv · show

Representation learning over temporal networks has drawn considerable attention in recent years. Efforts are mainly focused on modeling structural dependencies and temporal evolving regularities in Euclidean space which, however, underestimates the inherent complex and hierarchical properties in many real-world temporal networks, leading to sub-optimal embeddings. To explore these properties of a complex temporal network, we propose a hyperbolic temporal graph network (HTGN) that fully takes advantage of the exponential capacity and hierarchical awareness of hyperbolic geometry. More specially, HTGN maps the temporal graph into hyperbolic space, and incorporates hyperbolic graph neural network and hyperbolic gated recurrent neural network, to capture the evolving behaviors and implicitly preserve hierarchical information simultaneously. Furthermore, in the hyperbolic space, we propose two important modules that enable HTGN to successfully model temporal networks: (1) hyperbolic temporal contextual self-attention (HTA) module to attend to historical states and (2) hyperbolic temporal consistency (HTC) module to ensure stability and generalization. Experimental results on multiple real-world datasets demonstrate the superiority of HTGN for temporal graph embedding, as it consistently outperforms competing methods by significant margins in various temporal link prediction tasks. Specifically, HTGN achieves AUC improvement up to 9.98% for link prediction and 11.4% for new link prediction. Moreover, the ablation study further validates the representational ability of hyperbolic geometry and the effectiveness of the proposed HTA and HTC modules.

1 INTRODUCTION

Temporal graph embedding must model evolving structure, yet common Euclidean approaches may inadequately represent hierarchical network properties. HTGN addresses this gap with hyperbolic recurrent learning and temporal attention and consistency mechanisms.

Dynamic networks evolve through changing vertices, attributes, and edges, making representation learning important for understanding and predicting system behavior.
Existing temporal embedding methods use discrete snapshots or continuous events while primarily modeling temporal dependency and topology evolution in Euclidean space.
Hyperbolic geometry expands exponentially and represents hierarchical or tree-like structure more naturally than Euclidean space.
HTGN projects snapshot nodes into hyperbolic space, applies HGNN for topology, and uses HGRU for temporal dependencies.
HTGN adds hyperbolic temporal contextual attention for historical information and temporal consistency constraints for embedding stability and generalization.

2 RELATED WORKS

Related work covers discrete and continuous temporal graph embeddings alongside hyperbolic graph representation learning. HTGN builds on recurrent graph-neural approaches while extending them to hyperbolic geometry.

Temporal graph embedding: Temporal graphs are modeled either as discrete collections of evolving snapshots or as continuous streams of timestamped events.
Temporal graph embedding: Snapshot-based methods suit discrete temporal graphs, whereas reconstructing fine-grained timestamps from snapshots is generally infeasible.
Temporal graph embedding: Recurrent temporal embedding methods combine graph neural networks for structural information with recurrent architectures that summarize historical snapshots.
Hyperbolic graph embedding: Hyperbolic graph embedding methods generalize graph convolutions to model data with latent hierarchical structure.

3 PRELIMINARY AND BACKGROUND

The paper formulates discrete-time temporal graphs as snapshot sequences and describes a graph-recurrent embedding framework. It also introduces Riemannian manifolds and tangent spaces as geometric preliminaries.

Problem formulation: A discrete-time temporal graph consists of snapshots G_1 through G_T, each containing a node set and adjacency matrix that may change over time.
Problem formulation: The general framework combines a graph neural network for structural dependencies with a recurrent network for evolving regularities.
Problem formulation: The recurrent framework uses initial node features and the latest historical state to produce the current hidden representation.
Hyperbolic geometry: A Riemannian manifold is a smooth manifold equipped with a Riemannian metric, with each point associated with a tangent space.
Hyperbolic geometry: Figure 2 illustrates the tangent space T_xM and tangent vector v at point x on a curve through manifold M.

4 METHODOLOGY

HTGN combines hyperbolic graph processing, temporal recurrence, historical attention, and temporal consistency within a discrete-time recurrent architecture. Its objective jointly models temporal smoothness and graph homophily while preserving structural and temporal information.

Overall architecture: HTGN uses HGNN to extract topological dependencies, HTA to aggregate historical states, and HGRU to capture sequential patterns in hyperbolic space.The framework operates on discrete temporal snapshots and includes HTC to promote stability and smoothness.
Hyperbolic representation: HTGN maps Euclidean node features into hyperbolic space and performs hyperbolic transformations, attention-based aggregation, and activation through tangent-space operations.Exponential and logarithmic maps connect hyperbolic and tangent spaces, while aggregation is computed in the tangent space.
Historical attention: HTA attends to multiple historical latent states by projecting them into tangent space, concatenating them, and learning node- and time-dependent weights.The module uses Q to weight node importance within each historical state and r to determine weights across time windows.
Temporal recurrence: HGRU incorporates current and historical node states with gated updates, using logarithmic maps before recurrence and mapping the hidden state back to hyperbolic space.The tangent-space implementation is reported as more efficient for large-scale data while achieving similar performance to HyperGRU.
Training objective: The unified objective combines hyperbolic temporal consistency and homophily losses, balancing temporal smoothness with homophily regularity through λ ∈ [0, 1].Temporal consistency is imposed on consecutive snapshots, while homophily loss uses hyperbolic features to distinguish linked from non-linked nodes; negative edges are sampled to match positive edges.

5 EXPERIMENTS AND ANALYSIS

Experiments evaluate HTGN across diverse temporal networks and link-prediction settings, including new-link prediction and ablations. HTGN consistently outperforms competing methods, while removing hyperbolic geometry, HTA, or HTC degrades performance.

Experimental setup: HTGN is evaluated on six diverse networks spanning disease, academic, social, email, and Internet-router domains.The evaluation includes DISEASE, HepPh, COLAB, FB, Enron, and AS733.
Overall performance: HTGN consistently and significantly outperforms competing methods across both temporal link-prediction tasks.The comparison includes static and temporal graph embedding baselines, with experiments repeated five times.
Temporal link prediction: 4.28% average AUC gain over the best baseline is reported for temporal link prediction.The gains are especially notable on sparse graphs such as FB and long-term sequences such as HepPh.
New-link prediction: HTGN maintains more consistent performance on temporal new-link prediction, while the second-best AS733 baseline drops from 94.64% to 83.14%.HTGN declines by about 2% on AS733, whereas new-link prediction is described as more challenging than ordinary link prediction.
Ablation study: Removing any ablation component causes performance degradation, supporting the importance of hyperbolic geometry, HTA, and HTC.Removing HTC causes substantial degradation, HTA is most important on DISEASE, and HTC supports stable generalized performance on long-term tasks.

6 DISCUSSION

The discussion evaluates hyperbolic geometry, embedding dimensionality, and computational efficiency through ablations and comparisons on temporal graph datasets. HTGN preserves strong performance with compact embeddings and substantially lower per-epoch runtime than the compared methods.

Merits of Hyperbolic Geometry (RQ3): 21.35% AUC degradation occurs on DISEASE when hyperbolic geometry is removed, while HepPh shows an AUC drop of about 9%.The ablation attributes these declines to losing the ability to preserve hierarchical layout with lower distortion.
Merits of Hyperbolic Geometry (RQ3): 8-dimension HTGN on FB still outperforms VGRNN, while 4-dimension HTGN is comparable with 16-dimension VGRNN.The reduced embedding space also reduces learning parameters for large-scale or low-memory deployments.
Running Time Comparison (RQ4): 1.5 seconds is HTGN's running time per epoch, compared with 9.9s for VGRNN and 34.2s for DySAT.The comparison uses FB and HepPh networks and a machine with an NVIDIA GeForce GTX TITAN X GPU and 8 CPU cores.
Running Time Comparison (RQ4): HTGN uses a shared HGNN before HGRU, whereas VGRNN uses different GNNs and DySAT computes both temporal and structural attention.The discussion links these architectural differences to the observed efficiency comparison, especially on the denser HepPh network.

7 CONCLUSION

The conclusion presents HTGN as a hyperbolic framework for temporal network modeling that combines recurrent learning with hierarchical representation. It reports strong performance against state-of-the-art temporal graph embedding baselines and identifies continuous-time learning as future work.

7 CONCLUSION: HTGN combines hyperbolic graph neural networks with recurrent learning to capture topological dependency and hierarchical arrangement in temporal networks.Its hyperbolic temporal contextual self-attention extracts attentive historical states, while hyperbolic temporal consistency supports stability and generalization.
7 CONCLUSION: HTGN outperforms state-of-the-art temporal graph embedding baselines by a large margin on multiple real-world temporal graphs.The conclusion also proposes extending the method to more challenging tasks and continuous-time learning.

A.1 Geometry Initiations of Hyperbolic Space

This section introduces hyperbolic space through its curvature, Poincaré-disk geometry, and volume-growth properties. It explains why hyperbolic space is suited to representing hierarchical or tree-like structures.

A.1 Geometry Initiations of Hyperbolic Space: Hyperbolic space has constant negative curvature, unlike Euclidean geometry, which has zero curvature.Different Riemannian curvatures define different geometries.
A.1 Geometry Initiations of Hyperbolic Space: The Poincaré disk offers an intuitive visualization of hyperbolic embeddings, while the Lorentz model is suited to Riemannian optimization.The section uses the Poincaré disk to illustrate hyperbolic-space intuitions.
A.1 Geometry Initiations of Hyperbolic Space: Increasing the absolute curvature raises the distance between two fixed points and moves equal-length lines closer to the origin in the Poincaré disk.The illustrated disk radius decreases as the space bends more.
A.1 Geometry Initiations of Hyperbolic Space: Hyperbolic-ball volume grows exponentially with radius, whereas Euclidean-ball volume grows polynomially.This growth matches the exponential increase in nodes with depth in a tree, making hyperbolic space a continuous tree analogue.

A.2 Proof of Proposition 2

The proof begins from HTGN's loss function, decomposes its terms, and then aggregates the loss across timestamps before centering it on each node. The resulting node-level constraint combines temporal homophily with consecutive-state consistency.

A.2 Proof of Proposition 2: The proof starts by recalling the loss function L_t and arranging its first and second terms separately.These steps are identified as equations (21) and the subsequent decomposition of the loss components.
A.2 Proof of Proposition 2: The derivation samples as many negative edges as positive edges, with s set to 1.0 in the experiments.The proof states E1 = E2 = |E_t| under this sampling scheme.
A.2 Proof of Proposition 2: The loss is summed across all timestamps before the proof centers it on each node.The timestamp aggregation precedes the node-level formulation.
A.2 Proof of Proposition 2: The node-level constraint combines temporal homophily with consistency between the same node at consecutive timestamps.Temporal homophily attracts positive neighbors and separates sampled negative neighbors across timestamps.

A.3 Experiment details

The experiments construct temporal snapshots from real-world networks using dataset-specific time intervals, node features, and recurrent-model settings. The evaluation uses identity or trainable initialized features and fixed HTGN hyperparameters across datasets.

Datasets and temporal preprocessing: AS73310 is an Internet router network with 733 instances, daily snapshots, and the last 30 snapshots selected.It spans November 8, 1997, to January 2, 2000, over 785 days.
Node features: Enron and COLAB use identity-matrix node features, whereas HepPh, FB, and AS733 use trainable 128-dimensional Glorot-initialized features.The benchmark datasets are primarily associated with topology, while DISEASE is associated with node features.
Model settings: All recurrent models use one GRU layer, while HTA uses four historical windows for DISEASE and five for other datasets.The authors report limited parameter tuning because the goal was to evaluate HTA as a module in HTGN.
Model settings: The Fermi-Dirac parameters r and t are fixed at 2.0 and 1.0, respectively, following a common choice.These values are used across the experimental settings described.