HGWaveNet: A Hyperbolic Graph Neural Network for Temporal Link
  Prediction
Temporal link prediction, aiming to predict future edges between paired nodes
in a dynamic graph, is of vital importance in diverse applications. However,
existing methods are mainly built upon uniform Euclidean space, which has been
found to be conflict with the power-law distributions of real-world graphs and
unable to represent the hierarchical connections between nodes effectively.
With respect to the special data characteristic, hyperbolic geometry offers an
ideal alternative due to its exponential expansion property. In this paper, we
propose HGWaveNet, a novel hyperbolic graph neural network that fully exploits
the fitness between hyperbolic spaces and data distributions for temporal link
prediction. Specifically, we design two key modules to learn the spatial
topological structures and temporal evolutionary information separately. On the
one hand, a hyperbolic diffusion graph convolution (HDGC) module effectively
aggregates information from a wider range of neighbors. On the other hand, the
internal order of causal correlation between historical states is captured by
hyperbolic dilated causal convolution (HDCC) modules. The whole model is built
upon the hyperbolic spaces to preserve the hierarchical structural information
in the entire data flow. To prove the superiority of HGWaveNet, extensive
experiments are conducted on six real-world graph datasets and the results show
a relative improvement by up to 6.67% on AUC for temporal link prediction over
SOTA methods.
Qijie Bai, Changli Nie, Haiwei Zhang, Dongming Zhao, Xiaojie Yuan
# HGWaveNet: A Hyperbolic Graph Neural Network for Temporal Link Prediction

###### Abstract.

Temporal link prediction, aiming to predict future edges between paired nodes in a dynamic graph, is of vital importance in diverse applications. However, existing methods are mainly built upon uniform Euclidean space, which has been found to be conflict with the power-law distributions of real-world graphs and unable to represent the hierarchical connections between nodes effectively. With respect to the special data characteristic, hyperbolic geometry offers an ideal alternative due to its exponential expansion property. In this paper, we propose HGWaveNet, a novel hyperbolic graph neural network that fully exploits the fitness between hyperbolic spaces and data distributions for temporal link prediction. Specifically, we design two key modules to learn the spatial topological structures and temporal evolutionary information separately. On the one hand, a hyperbolic diffusion graph convolution (HDGC) module effectively aggregates information from a wider range of neighbors. On the other hand, the internal order of causal correlation between historical states is captured by hyperbolic dilated causal convolution (HDCC) modules. The whole model is built upon the hyperbolic spaces to preserve the hierarchical structural information in the entire data flow. To prove the superiority of HGWaveNet, extensive experiments are conducted on six real-world graph datasets and the results show a relative improvement by up to 6.67% on AUC for temporal link prediction over SOTA methods.

Temporal link prediction, hyperbolic geometry, graph neural network, diffusion graph convolution, dilated causal convolution +
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition
+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition
+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer Vision and Pattern Recognition

+
Footnote †: journal: Computer
is also applied to simulate the evolution of graphs. Furthermore, DyRep (2017) leverages recurrent neural networks to update node representations over time. TGAT (Chen et al., 2017) uses the multi-head attention mechanism (Wang et al., 2018) and a sampling strategy that fixes the number of neighbor nodes involved in message-propagation to learn both spatial and temporal information.

These methods are all built upon Euclidean spaces. However, recent works (Chen et al., 2017; Chen et al., 2018) have noticed that most real-world graph data, such as social networks, always exhibit implicit hierarchical structures and power-law distributions (as shown in Figure 1(a)) rather than uniform grid structures which fit Euclidean spaces best. The mismatches between data distributions and space geometries severely limit the performances of Euclidean models (Chen et al., 2017; Chen et al., 2018).

Hyperbolic spaces are those of constant negative curvatures, and are found to keep great representation capacity for data with hierarchical structures and power-law distributions due to the exponential expansion property (as shown in Figure 1(b)) (Chen et al., 2017; Chen et al., 2018). In the past few years, researchers have made some progress in representing hierarchical data in hyperbolic spaces (Chen et al., 2017; Chen et al., 2018; Chen et al., 2018; Wang et al., 2018; Wang et al., 2018; Wang et al., 2018; Wang et al., 2018). HTGN (Wang et al., 2018) attempts to embed dynamic graphs into hyperbolic geometry and achieves state-of-the-art performance. It adopts hyperbolic GCNs to capture spatial features and a hyperbolic temporal contextual attention module to extract the historical information. However, this method faces two major shortcomings. First, for some large graphs with long paths, the message propagation mechanism of GCNs is not effective enough because only direct neighbor nodes can be calculated in each step. Second, the temporal contextual attention module cannot handle the internal order of causal correlation in historical data and thus loses valid information for temporal evolutionary process.

To address the two aforementioned shortcomings of HTGN, in this paper, we propose a novel hyperbolic graph neural network model named HGWaveNet for temporal link prediction. In HGWaveNet, we first project the nodes into hyperbolic spaces. Then in the aspect of spatial topology, a hyperbolic diffusion graph convolution (HDGC) module is designed to learn node representations of each snapshot effectively from both direct neighbors and indirectly connected nodes. For temporal information, recurrent neural networks always emphasize short time memory while ignoring that of long time due to the time monotonic assumption (Chen et al., 2017), and the attention mechanism ignores the causal orders in temporality. Inspired by WaveNet (Wang et al., 2018) and Graph WaveNet (Wang et al., 2018), we present hyperbolic dilated causal convolution (HDCC) modules to obtain hidden cumulative states of nodes by aggregating historical information and capturing temporal dependencies. In the training process of each snapshot, the hidden cumulative states and spatial-based node representations are fed into a hyperbolic gated recurrent unit (HGRU). The outputs of HGRU are regarded as the integration of spatial topological structures and temporal evolutionary information, and are utilized for final temporal link prediction. A hyperbolic temporal consistency (HTC) (Wang et al., 2018) component is also leveraged to ensure stability for tracking the evolution of graphs.

To conclude, the main contributions of this paper are as follows:

* We propose a novel hyperbolic graph neural network model named HGWaveNet for temporal link prediction, which learns both spatial hierarchical structures and temporal causal correlation of dynamic graphs.
* With regard to spatial topological structures, we design a hyperbolic diffusion graph convolution (HDGC) module to fit the power-law distributions of data and aggregate information from a wider range of nodes with greater effectiveness.
* For temporal evolution, we present hyperbolic dilated causal convolution (HDCC) modules to capture the internal causality between snapshots, and a hyperbolic temporal consistency (HTC) component is applied to remain stable when learning the evolution of graphs.
* We conduct extensive experiments on diverse real-world dynamic graphs. The results prove the superiority of HGWaveNet, as it has a relative improvement by up to 6.67% in terms of AUC over state-of-the-art methods.

## 2. Related Work

In this section, we systematically review the relevant works on temporal link prediction and hyperbolic graph representation learning.

### Temporal Link Prediction

Temporal link prediction on dynamic graphs has attracted increasing interests in the past few years. Early methods usually use traditional algorithms or shallow neural architectures to represent structural and temporal information. For instance, CTDNE (Cheng et al., 2017) captures the spatial and temporal information simultaneously by adding temporal constraints to random walk. Another example of using temporal random walk is DynNode2vec (Cheng et al., 2017), which updates the sampled sequences incrementally at each snapshot rather than generating them anew. DynamicTriad (Wang et al., 2018) imposes the triad closure process and models the evolution of graphs by developing closed triads from open triads. Furthermore, Change2vec (Chen et al., 2017) improves this process and makes it applicable for dynamic heterogeneous graphs. HTNE (Wang et al., 2018) integrates the Hawkes process into graph embedding to learn the influence of historical neighbors on current neighbors.

In contrast, graph neural network methods have recently received increasing attention. GCN (Wang et al., 2018) provides an excellent node embedding pattern for general tasks on graphs, and most of later models take GCN or its variants, such as GraphSAGE (Gan et al., 2017) and GAT (Gan et al., 2017), as basic modules for learning topological structures. GCRN (Wang et al., 2018) feeds node representations learned from GCNs into a modified LSTM to obtain the temporal information. Similar ideas are

Figure 1. (a) The degree distribution of real-world network MovieLens. Coordinate axes are logarithmic. (b) Areas of circles on hyperbolic spaces (curvature \(c=-1\)) and Euclidean spaces, which shows that the hyperbolic spaces expand exponentially while Euclidean spaces expand polynomially.
explored in EvolveGCN (Wang et al., 2017), E-LSTM-D (Chen et al., 2017) and NTF (Wang et al., 2017). The main difference between EvolveGCN and E-LSTM-D is that EvolveGCN could be considered as a combination of GCN and RNN while E-LSTM-D uses LSTM together with an encoder-decoder architecture. NTF takes a reverse order that characterizes the temporal interactions with LSTM before adopting the MLP for non-linearities between different latent factors, and sufficiently learns the evolving characteristics of graphs. To better blend the spatial and temporal node features, DySAT (Dai et al., 2017) proposes applying multi-head self-attention. TGN (Wang et al., 2017) leverages memory modules with GCN operators and significantly increases the computational efficiency. TNS (Wang et al., 2017) provides an adaptive receptive neighborhood for each node at any time. VRGNN (Wang et al., 2017) models the uncertainty of node embeddings by regarding each node in each snapshot as a distribution.

However, the prevailing methods are built upon Euclidean spaces, which are not isometric with the power-law distributions of real-world graphs, and may cause distortion with the graph scale grows.

### Hyperbolic Graph Representation Learning

Representation learning in hyperbolic spaces has been noticed due to their fitness to the hierarchical structures of real-world data. The significant performance advantages shown by the shallow Poincare (Poinacre, 2017) and Lorentz (Loren, 2017) models spark more attempts to this issue. Integrated with graph neural networks, HGNN (Wang et al., 2017) and HGCN (Chen et al., 2017) are designed for graph classification and node embedding tasks separately. HAT (Wang et al., 2017) exploits attention mechanism for hyperbolic node information propagation and aggregation. LGCN (Wang et al., 2017) builds the graph operations of hyperbolic GCNs with Lorentzian version and rigorously guarantees that the learned node features follow the hyperbolic geometry. The above hyperbolic GNN-based models all adopt the bi-directional transition between a hyperbolic space and corresponding tangent spaces, while a tangent space is the first-order approximation of the original space and may inevitably cause distortion. To avoid distortion, H2H-GCN (Chen et al., 2017) develops a manifold-preserving graph convolution and directly works on hyperbolic manifolds. For practical application situations, HGCF (Wang et al., 2017), HRCF (Wang et al., 2017) and HICF (Wang et al., 2017) study the hyperbolic collaborative filtering for user-item recommendation systems. Through hyperbolic graph learning, HyperStockGAT (Wang et al., 2017) captures the scale-free spatial and temporal dependencies in stock prices, and achieves state-of-the-art stock forecasting performance.

HVGNN (Wang et al., 2017) and HTGN (Wang et al., 2017) fill the gap of hyperbolic models on dynamic graphs. HVGNN generates stochastic node representations of hyperbolic normal distributions via a hyperbolic graph variational autoencoder to represent the uncertainty of dynamics. HTGN adopts a conventional model architecture that handles the spatial and temporal information with HGCNs and contextual attention modules separately, however, ignores the causal order in the graph evolution. To further improve the hyperbolic graph models especially on temporal link prediction problem, we propose our HGWaveNet in terms of discrete dynamic graphs.

## 3. Preliminaries

In this section, we first give the formalized definitions of discrete dynamic graphs and temporal link prediction. Then some critical fundamentals about hyperbolic geometry are introduced.

### Problem Definition

This paper discusses temporal link prediction on discrete dynamic graphs. Following (Wang et al., 2017), we define discrete dynamic graphs as:

Definition 3.1 (**Discrete Dynamic Graphs**).: _In discrete dynamic graph modeling, dynamic graphs can be viewed as a sequence of snapshots sampled from the original evolving process at consecutive time points. Formally, discrete dynamic graphs are represented as \(\mathcal{G}=(\mathcal{G}_{0},\mathcal{G}_{1},\cdots,\mathcal{G}_{T})\), in which \(\mathcal{G}_{t}\) is a snapshot at timestamp \(t\). The time granularity for snapshot divisions could be hours, days, months or even years depending on specific datasets and applications._

Based on Definition 3.1, temporal link prediction is described as:

Definition 3.2 (**Temporal Link Prediction**).: _The aim of temporal link prediction is to predict the links appeared in the snapshots after timestamp \(t\) based on the observed snapshots before timestamp \(t\). Formally, the model takes \((\mathcal{G}_{0},\mathcal{G}_{1},\cdots,\mathcal{G}_{t-1})\) as input in the training process, and then makes predictions on \((\mathcal{G}_{t},\mathcal{G}_{t+1},\cdots,\mathcal{G}_{T})\)._

### Hyperbolic Geometry of the Poincare Ball

The \(n\)-dimensional hyperbolic space \((\mathbb{H}_{c}^{n},\mathcal{G}^{c,\mathbb{H}})\) is the unique simply connected \(n\)-dimensional complete Riemannian manifold \(\mathbb{H}_{c}^{n}\) with a constant negative curvature \(-c(c>0)\), and \(\mathcal{G}^{c,\mathbb{H}}\) is the Riemannian metric. The tangent space \(7\pi_{\mathbf{c}}^{n}\) is a Euclidean, local, first-order approximation of \(\mathbb{H}_{c}^{n}\) around the point \(\mathbf{x}\in\mathbb{H}_{c}^{n}\). Similar to (Poinacre, 2017) and (Chen et al., 2017), we construct our method based on the Poincare ball, one of the most widely used isometric models of hyperbolic spaces. Corresponding to \((\mathbb{H}_{c}^{n},\mathcal{g}^{c,\mathbb{H}})\), the Poincare ball \((\mathbb{B}_{c}^{n},\mathcal{g}^{c,\mathbb{B}})\) is defined as

\[\begin{split}\mathbb{B}_{c}^{n}&=\left\{\mathbf{x} \in\mathbb{R}^{n}:c\|\mathbf{x}\|^{2}<1\right\},\\ g_{\mathbf{x}}^{c,\mathbb{B}}&=\left(\lambda_{\mathbf{x} }^{c}\right)^{2}g^{F},\quad\lambda_{\mathbf{x}}^{c}:=\frac{2}{1-c\|\mathbf{x} \|^{2}},\end{split} \tag{1}\]

where \(g^{F}=\mathbf{I}_{n}\) is the Euclidean metric tensor.

The Poincare ball manifold \(\mathbb{B}_{c}^{n}\) is an open ball of radius \(1/\sqrt{c}\) (see Figure 2). The induced distance between two points \(\mathbf{x},\mathbf{y}\in\mathbb{B}_{c}^{n}\) is measured along a geodesic and given by1

Footnote 1: \(-\mathbf{x}\oplus_{c}\mathbf{y}\) should be read as \((-\mathbf{x})\oplus_{c}\mathbf{y}\) rather than \(-(\mathbf{x}\oplus_{c}\mathbf{y})\).

\[d_{c}\left(\mathbf{x},\mathbf{y}\right)=\frac{2}{\sqrt{c}}\cdot\tanh^{-1}\left( \sqrt{c}\|-\mathbf{x}\oplus_{c}\mathbf{y}\|\right), \tag{2}\]

in which the Mobius addition \(\oplus_{c}\) in \(\mathbb{B}_{c}^{n}\) is defined as

\[\mathbf{x}\oplus_{c}\mathbf{y}=\frac{\left(1+2c(\mathbf{x},\mathbf{y})+c\| \mathbf{y}\|^{2}\right)\mathbf{x}+\left(1-c\|\mathbf{x}\|^{2}\right)\mathbf{y }}{1+2c(\mathbf{x},\mathbf{y})+c^{2}\|\mathbf{x}\|^{2}\|\mathbf{y}\|^{2}}. \tag{3}\]

Figure 2. A hyperbolic manifold \(\mathbb{H}\) and the corresponding Poincaré ball model \(\mathbb{B}\). The distances on the manifolds are measured along geodesics.
To map points between hyperbolic spaces and tangent spaces, exponential and logarithmic maps are given (Bou and Bou, 2017). For \(\mathbf{x},\mathbf{y}\in\mathbb{B}_{c}^{n},\mathbf{v}\in\mathbb{F}_{\mathbf{x}} \mathbb{B}_{c}^{n}\), \(\mathbf{x}\neq\mathbf{y}\) and \(\mathbf{v}\neq\mathbf{0}\), the exponential map \(\exp_{\mathbf{x}}^{c}:\mathcal{T}_{\mathbf{x}}\mathbb{B}_{c}^{n}\subset \mathbb{B}_{c}^{n}\) is

\[\exp_{\mathbf{x}}^{c}(\mathbf{v})=\mathbf{x}\oplus_{c}\left(\tanh\left(\frac{ \nabla\mathcal{L}_{\mathbf{x}}^{c}\|\mathbf{v}\|}{2}\right)\frac{\mathbf{v}}{ \sqrt{c}\|\mathbf{v}\|}\right), \tag{4}\]

and the logarithmic map \(\log_{\mathbf{x}}^{c}:\mathbb{B}_{c}^{n}\to\mathcal{T}_{\mathbf{x}}\mathbb{B} _{c}^{n}\) is

\[\log_{\mathbf{x}}^{c}(\mathbf{y})=d_{c}\left(\mathbf{x},\mathbf{y}\right) \frac{-\mathbf{x}\oplus_{c}\mathbf{y}}{\lambda_{\mathbf{x}}^{c}\|-\mathbf{x} \oplus_{c}\mathbf{y}\|}, \tag{5}\]

where \(\lambda_{\mathbf{x}}^{c}\) and \(d_{c}\left(\mathbf{x},\mathbf{y}\right)\) are the same as in Equations (1) and (2). In our method, we use the origin point \(\mathbf{o}\) as the reference point \(\mathbf{x}\) to balance the errors in diverse directions.

## 4. Methodology

This section describes our proposed model HGWaveNet. First, we elaborate on the details of two core components: hyperbolic diffusion graph convolution (HDGC) and hyperbolic dilated causal convolution (HDCC). Then other key modules contributing to HGWaveNet are introduced, including gated HDCC, hyperbolic gated recurrent unit (HGRU), hyperbolic temporal consistency (HTC) and Fermi-Dirac decoder. Finally, we summarize the overall framework of HGWaveNet and analyse the time complexity.

### Hyperbolic Diffusion Graph Convolution

Hyperbolic graph convolutional neural networks (HGCNs (Chen et al., 2017)) are built analogous to traditional GNNs. A typical HGCN layer consists of three key parts: hyperbolic feature transform

\[\mathbf{h}_{i}^{L,\mathbb{B}}=\mathbf{W}^{I}\otimes_{\ell^{-1}}\mathbf{x}_{i }^{L-1,\mathbb{B}}\oplus_{\ell^{-1}}\mathbf{b}^{I}, \tag{6}\]

attention-based neighbor aggregation

\[\mathbf{y}_{i}^{L,\mathbb{B}} =\text{Agg}_{\ell^{\prime}}(\text{Att}\left(\text{Concat}_{j\in \mathcal{N}(i)}\left(\log_{\mathbf{o}}^{\ell^{-1}}\left(\mathbf{h}_{j}^{L, \mathbb{B}}\right)\right)\right)), \tag{7}\]

and hyperbolic activation

\[\mathbf{x}_{i}^{L,\mathbb{B}}=\exp_{\mathbf{o}}^{\ell^{\prime}}\left(\sigma \left(\log_{\mathbf{o}}^{\ell^{\prime}}\left(\mathbf{y}_{i}^{L,\mathbb{B}} \right)\right)\right), \tag{8}\]

in which \(\mathbf{W}^{I},\mathbf{b}^{I}\) are trainable parameters and \(\mathbf{x}_{i}^{L,\mathbb{B}}\) is the representation of node \(i\) at layer \(l\) in manifold \(\mathbb{B}_{\ell^{\prime}}^{n}\). Following (Zhou et al., 2017), the matrix-vector multiplication \(\otimes_{\mathcal{E}}\) is defined as

\[\mathbf{M}\otimes_{\mathcal{E}}\mathbf{x}:=\exp_{\mathbf{o}}^{c}\left(\mathbf{ M}\log_{\mathbf{o}}^{c}\left(\mathbf{x}\right)\right),\quad\mathbf{M}\in\mathbb{R}^{n \times n},\mathbf{x}\in\mathbb{B}_{\mathcal{E}}^{n}. \tag{9}\]

However, the shallow HGCN can only aggregate information of direct neighbors and is not effective enough for large graphs with long paths. To overcome this shortcoming, we impose the diffusion process referring to (Henderson et al., 2017). Consider a random walk process with restart probability \(\alpha\) on \(\mathcal{G}\), and a state transition matrix \(\mathbf{P}\) (for most situations, \(\mathbf{P}\) is the normalized adjacent matrix). Such Markov process converges to a stationary distribution \(\mathcal{P}\in\mathbb{R}^{n\times n}\) after many steps, the \(i\)-th row of which is the likelihood of diffusion from node \(i\). The stationary distribution \(\mathcal{P}\) can be calculated in the closed form (Srivastava et al., 2017)

\[\mathcal{P}=\sum_{k=0}^{\infty}\alpha(1-\alpha)^{k}\mathbf{P}^{k}, \tag{10}\]

where \(k\) is the diffusion step. In practice, a finite \(K\)-step truncation of the diffusion process is adopted and separate trainable weight matrices are added to each step for specific objective tasks. Then, the diffusion convolution layer on graphs is defined as

\[\mathbf{Z}=\sum_{k=0}^{K}\mathbf{A}^{k}\mathbf{X}\mathbf{W}_{k}, \tag{11}\]

in which \(\mathbf{A}\) is the bi-direct adjacent matrix, \(\mathbf{X}\) is the input node features, \(\mathbf{W}_{k}\) is the weight matrix for the \(k\)-th diffusion step, and \(\mathbf{Z}\) is the output node representations.

On account of the sparsity of real-world data, we convert the graph convolution into equivalent spatial domains for efficiency. Do all above operations in the hyperbolic space, and replace the summation in Equation (11) with an attention mechanism for better information aggregation. Then, the \(k\)-th step of hyperbolic diffusion graph convolution at layer \(l\) is

\[\mathbf{X}_{k}^{l}=\text{HGCN}_{\varepsilon_{k}^{L}}\left(\mathbf{A}^{k}, \mathbf{X}^{l-1}\right), \tag{12}\]

where \(\text{HGCN}_{\varepsilon^{L}}(\cdot)\) is the conjunctive form of Equations (6), (7), and (8) with the adjacent matrix and node features as inputs. \(\mathbf{X}^{l}\) is calculated as

\[\mathbf{X}^{l}=\exp_{\mathbf{o}}^{l}\left(\text{Att}\left(\text{Concat}_{k}\left( \log_{\mathbf{o}}^{\ell^{\prime}}\left(\mathbf{X}_{k}^{l}\right)\right)\right) \right). \tag{13}\]

Hyperbolic diffusion graph convolution is finally constructed with the stack of layers defined by Equations (13) and (12), as sketched in Figure 3.

### Hyperbolic Dilated Causal Convolution

Causal convolution refers to applying a convolution filter only to data at past timestamps (Zhou et al., 2017), and guarantees that the order of data modeling is not violated, which means that the prediction \(p(x_{t}|x_{0},x_{1},\cdots,x_{t-1})\) emitted by the model at timestamp \(t\) cannot depend on future data \(x_{t},x_{t+1},\cdots,x_{T}\). For 1-D temporal information, this operation can be implemented by shifting the output of a normal convolution with kernel size \(5\) by \(\lfloor 5/2\rfloor\) steps, but a sufficiently large receptive field requires stacking many layers. To decrease the computational cost, dilated convolutions are adopted. By skipping the inputs with a certain step \(d\), a dilated convolution applies its kernel over a larger area than its length, and with the

Figure 3. A hyperbolic diffusion graph convolution (HDGC) module with the number of layers \(L=2\) and the number of diffusion steps \(K=2\). The part in red dashed rectangle is a complete HDGC layer.
stack of dilated convolution layers, the receptive field expands exponentially while preserving high computational efficiency. Based on the above definitions of causal convolutions and dilated convolutions, the dilated causal convolution operation in manifold \(\mathbb{B}_{\mathcal{C}}^{n}\) can be formalized mathematically as

\[(\mathbf{Z}_{i}\odot\mathbf{F})_{t}=\exp_{\mathbf{o}}^{c}\left(\sum_{s=0}^{S-1} \mathbf{F}_{s}\log_{\mathbf{o}}^{c}\left(\mathbf{Z}_{i,t-d\times s}\right) \right), \tag{14}\]

where \(d\) is the dilation step, \(\mathbf{Z}_{i,t}\in\mathbb{B}_{\mathbf{o}}^{n}\left(t\leq T\right)\) is the representation of node \(i\) at snapshot \(\mathcal{G}_{t}\) and \(\mathbf{F}\in\mathbb{R}^{S\times n}\) denotes the kernels for all dimensions (also called channels). A stacked hyperbolic dilated causal convolution module is shown in Figure 4.

Compared to attention-based historical information aggregation (Zhou et al., 2017), HDCC can learn the internal order of causal correlation in temporality. Meanwhile, compared to RNNs, HDCC allows parallel computation and alleviates vanishing or exploding gradient problems due to its non-recursion(Zhou et al., 2018). Considering the superiority of HDCC on sequence problems, we leverage this module in handling the temporal evolutionary information of graphs.

### Other Key Modules in HGWaveNet

Except for HDGC and HDCC, some other modules contribute greatly to our proposed HGWaveNet. Based on HDCC, we further design gated HDCC to preserve the valid historical information. Hyperbolic gated recurrent unit (HGRU) (Zhou et al., 2017) is able to efficiently learn the latest node representations in Poincare ball from historical states and current spatial characteristics. Additionally, as defined in (Zhou et al., 2017), hyperbolic temporal consistency (HTC) module provides a similarity constraint in temporality to ensure stability during graph evolution. Finally, a Fermi-Dirac decoder (Feng et al., 2019) is used to compute the probability scores for edge reconstruction.

#### 4.3.1. Gated HDCC

As shown in the left part of Figure 5, we adopt a simple gating mechanism on the outputs of HDCCs. What is noteworthy is the use of logarithmic map before the Euclidean activation functions and exponential map after gating. The formulation is described as

\[\mathbf{H}_{i,t}=\exp_{\mathbf{o}}^{c}\left(\tanh\left(\log_{\mathbf{o}}^{c} \left((\mathbf{Z}_{i}\odot\mathbf{F}_{1})_{t}\right)\right)\cdot\sigma\left( \log_{\mathbf{o}}^{c}\left((\mathbf{Z}_{i}\odot\mathbf{F}_{2})_{t}\right) \right)\right), \tag{15}\]

where \(\mathbf{F}_{1}\) and \(\mathbf{F}_{2}\) are different convolution kernels for two HDCCs, \(\mathbf{H}_{i,t}\in\mathbb{B}_{\mathbf{o}}^{n}\left(t\leq T\right)\) is the historical hidden state of node \(i\) at snapshot \(\mathcal{G}_{t}\), and \(\cdot\) denotes element-wise product. In addition, to enable a deeper model for learning more implicit information, residual and skip connections are applied throughout the gated HDCC layers.

#### 4.3.2. Hyperbolic Gated Recurrent Unit

HGRU (Zhou et al., 2017) is the hyperbolic variant of GRU (He et al., 2017). Performed in the tangent space, HGRU computes the output with high efficiency from historical hidden states and current input features, as

\[\mathbf{Z}_{i,t}=\exp_{\mathbf{o}}^{c}\left(\mathrm{GRU}\left(\log_{\mathbf{o }}^{c}\left(\mathbf{X}_{i,t}\right),\log_{\mathbf{o}}^{c}\left(\mathbf{H}_{i,t -1}\right)\right)\right). \tag{16}\]

In HGWaveNet, the historical hidden states are from gated HDCC module, so we use a single HGRU cell for just one step rather than linking it into recursion.

#### 4.3.3. Hyperbolic Temporal Consistency

In real-world graphs, the evolution proceeds continuously. Correspondingly, the node representations are expected to change gradually in terms of temporality, which means that the node representations at two consecutive snapshots should keep a short distance. Hence, HTC (Zhou et al., 2017) defines a similarity constraint penalty between \(\mathbf{Z}_{t-1}\) and \(\mathbf{Z}_{t}\) at snapshot \(\mathcal{G}_{t}\) as

\[\mathcal{L}_{\mathrm{HTC}}^{t}=\frac{1}{N}\sum_{i=1}^{N}d_{c}\left(\mathbf{Z}_ {i,t-1},\mathbf{Z}_{i,t}\right), \tag{17}\]

where \(d_{c}(\cdot)\) is defined in Equation (2) and \(N\) is the number of nodes. By adding the penalty in optimization process, HTC ensures that the node representations do not change rapidly and the stability of graph evolution is achieved.

#### 4.3.4. Fermi-Dirac Decoder

As a generalization of sigmoid, Fermi-Dirac decoder (Feng et al., 2019) gives a probability score for edges between nodes \(i\) and \(j\), which fits the temporal link prediction problem greatly. It is defined as

\[p_{F_{-D}}(\mathbf{x}_{i},\mathbf{x}_{j})=\frac{1}{\exp\left(\left(d_{c} \left(\mathbf{x}_{i},\mathbf{x}_{j}\right)-r\right)/s\right)+1}, \tag{18}\]

where \(r\) and \(s\) are hyper-parameters, and \(\mathbf{x}_{i}\), \(\mathbf{x}_{j}\in\mathbb{B}_{c}^{n}\) are hyperbolic representations of nodes \(i\) and \(j\).

### Framework of HGWaveNet

With all modules introduced above, we now summarize the overall framework of HGWaveNet in Figure 5. For the snapshot \(\mathcal{G}_{t-1}\in\mathcal{G}\), we first project the input node features into the hyperbolic space with exponential map, and then an HDGC module is applied to learn the spatial topological structure characteristics denoted by \(\mathbf{X}_{t-1}\). Simultaneously, the stacked gated HDCC layers calculate the latest historical hidden state \(\mathbf{H}_{t-2}\) from previous node representations \(\mathbf{Z}_{t-2},\mathbf{Z}_{t-3},\cdots\) (the initial historical node representations are padded randomly at the beginning of training). Next, the spatial information \(\mathbf{X}_{t-1}\) and the temporal information \(\mathbf{H}_{t-2}\) are inputted into a single HGRU cell. The output of HGRU \(\mathbf{Z}_{t-1}\) is exactly the new latest node representations at snapshot \(\mathcal{G}_{t-1}\), and is fed into the Fermi-Dirac decoder to make temporal link predictions for snapshot \(\mathcal{G}_{t}\).

To maximize the probability of connected nodes in \(\mathcal{G}_{t}\) and minimize the probability of unconnected nodes, we use a cross-entropy

Figure 4. A stacked hyperbolic dilated causal convolution (HDCC) module with dilated depth \(D=3\) and kernel size \(S=2\). Each circle refers to one node at a timestamp. Under the exponentially large receptive field, each node preserves the temporal causal correlations with the past \(S^{D}\) snapshots.
like loss \(\mathcal{L}_{CE}^{t}\) defined as

\[\begin{split}\mathcal{L}_{CE}^{t}=&\text{Avg}_{i \sim j}\left(-\log\left(p_{F-D}\left(\mathbf{Z}_{i,t-1},\mathbf{Z}_{j,t-1} \right)\right)\right)+\\ &\text{Avg}_{i^{\prime}\neq t^{\prime}}\left(-\log\left(1-p_{F-D} \left(\mathbf{Z}_{i^{\prime},t-1},\mathbf{Z}_{j^{\prime},t-1}\right)\right) \right),\end{split} \tag{19}\]

in which \(\sim_{t}\) denotes the connection at snapshot \(\mathcal{G}_{t}\) between two nodes, and \(\neq_{t}\) is the opposite. \((i^{\prime},j^{\prime})\) is the sampled negative edge for accelerating training and preventing over-smoothing. Taking the HTC module into account and summing up all snapshots, the complete loss function is

\[\mathcal{L}=\sum_{t=0}^{T}\left(\mathcal{L}_{CE}^{t}+\lambda\mathcal{L}_{HTC}^ {t}\right). \tag{20}\]

_Time Complexity Analysis._ We analyse the time complexity of our proposed HGWaveNet by module for each snapshot. For the HDGC module, the computation is of \(\mathcal{O}((Nd^{2}+|\mathcal{E}_{t}|Kd)L)\), where \(d\) is the dimension of node representations, \(|\mathcal{E}_{t}|\) is the edge number for snapshot \(\mathcal{G}_{t}\), \(K\) is the truncated diffusion steps and \(L\) is the layer number of HDGC. For gated HDCC, the time complexity is \(\mathcal{O}(S^{D}dD^{\prime})\), in which \(S\) and \(D\) are the kernel size and dilated depth of a single HDCC, respectively, and \(D^{\prime}\) is the layer number of the complete gated HDCC module. HGRU and HTC run only once for each snapshot, and both take the time complexity of \(\mathcal{O}(Nd)\). For Fermi-Dirac decoder, the time complexity is \(\mathcal{O}(|\mathcal{E}_{t}|d+|\mathcal{E}_{t}|d)\), in which \(|\mathcal{E}_{t}|\) is the number of negative samples for snapshot \(\mathcal{G}_{t}\).

## 5. Experiments and Analysis

In this section, we conduct extensive experiments on six real-world graphs and prove the superiority of our proposed HGWaveNet. In addition, we also conduct ablation studies and hyper-parameter analysis to corroborate the three primary ideas of our method: the fitness between graph distributions and hyperbolic geometry, the effectiveness of spatial information from a wider range of neighbors aggregated by HDGC, and the causality of historical information in the evolutionary process learned by HDCC.

### Experimental Setup

#### 5.1.1. Datasets

We evaluate our proposed model and baselines on six real-world datasets from diverse areas, including email communication networks Enron2(Friedman et al., 2017), academic co-author networks DBLP3(Friedman et al., 2017) and HepPh4(Friedman et al., 2017), Internet router networks AS733(Friedman et al., 2017), social networks FB6(Friedman et al., 2017) and movie networks MovieLens7(Friedman et al., 2017). The statistics of these datasets are shown in Table 1. We take the same splitting ratios for training and testing as (Zhang et al., 2018) on all datasets except MovieLens on which a similar manner is adopted. Gromov's hyperbolicity (Golovolov et al., 2016)\(\delta\) is used to measure the tree-likeness and hierarchical properties of graphs. A lower \(\delta\) denotes a more tree-like structure and \(\delta=0\) denotes a pure tree. The datasets we choose all remain implicitly hierarchical and show distinct power-law distributions.

Footnote 2: [https://www.cs.cornell.edu/~arb/data/email-Enron/](https://www.cs.cornell.edu/~arb/data/email-Enron/)

Footnote 3: [https://github.com/VGraphRNN/VGRNN/tree/master/data](https://github.com/VGraphRNN/VGRNN/tree/master/data)

Footnote 4: [https://snap.stanford.edu/data/cit-HepPh.html](https://snap.stanford.edu/data/cit-HepPh.html)

Footnote 5: [https://snap.stanford.edu/data-733.html](https://snap.stanford.edu/data-733.html)

Footnote 6: [https://networkregository.com/in-facebook-wall-wosn-dir.php](https://networkregository.com/in-facebook-wall-wosn-dir.php)

Footnote 7: [https://grouplenss.org/datasets/movielens/](https://grouplenss.org/datasets/movielens/)

#### 5.1.2. Baselines

Considering that HGWaveNet is constructed in the hyperbolic space for dynamic graphs, we choose seven competing baselines either in hyperbolic spaces or built for dynamic graphs to verify the superiority of our model. The baselines are summarized in Table 2, where HTGN on Poincare ball shows state-of-the-art performance in most evaluations.

#### 5.1.3. Evaluation Tasks and Metrics

Similar to (Zhang et al., 2018), our experiments consist of two different tasks: _temporal link prediction_ and _temporal new link prediction_. Specifically, _temporal link prediction_ aims to predict the edges that appear in \(\mathcal{G}_{t}\) and other snapshots after timestamp \(t\) based on the training on \((\mathcal{G}_{0},\mathcal{G}_{1},\cdots,\mathcal{G}_{t-1})\), while _temporal new link prediction_ aims to predict those in \(\mathcal{G}_{t}\) but not in \(\mathcal{G}_{t-1}\). To quantify the experimental performance, we choose the widely used metrics average precision (AP) and area under ROC curve (AUC). The datasets are split into training sets and test sets as shown in Table 1 by snapshots to run both our proposed model and baselines on the above tasks.

\begin{table}
\begin{tabular}{c|c c c c c} \hline \hline
**Datasets** & **Enron** & **DBLP** & **AS733** & **FB** & **HepPh** & **MovieLens** \\ \hline \# Nodes & 184 & 315 & 6,628 & 45,435 & 15,330 & 9,746 \\ \# Edges & 790 & 943 & 13,512 & 180,011 & 976,097 & 997,837 \\ \# Snapshots & 11 & 10 & 30 & 36 & 36 & 11 \\ Train : Test & 8.3 & 7.3 & 20:10 & 333 & 30.6 & 8.3 \\ \(\delta\) & 1.5 & 2.0 & 1.5 & 2.0 & 1.0 & 2.0 \\ \hline \hline \end{tabular}
\end{table}
Table 1. Statistics of datasets.

Figure 5. The overall framework of HGWaveNet. For \(\mathcal{G}_{t-1}\), the historical evolutionary information handled by gated HDCCs and the spatial topological information handled by HDGC are fed into an HGRU module. With the constraint of HTC, the hyperbolic outputs are decoded by a Fermi-Dirac decoder and the temporal link prediction for \(\mathcal{G}_{t}\) is made.

\begin{table}
\begin{tabular}{c|c c} \hline \hline
**Methods** & **Static/dynamic** & **Manifolds** \\ \hline
**HGCN**(Chen et al., 2017) & Static & Lorentz \\
**HAT**(Zhang et al., 2018) & Static & Poincaré \\
**EvolveGCN**(Zhang et al., 2018) & Dynamic & Euclidean \\
**GRUCGN**(Zhang et al., 2018) & Dynamic & Euclidean \\
**TGN**(Zhang et al., 2018) & Dynamic & Euclidean \\
**HTGN**(Zhang et al., 2018) & Dynamic & Poincaré \\ \hline \hline \end{tabular}
\end{table}
Table 2. Baselines.
### Experimental Results

We implement HGWaveNet8 with PyTorch on Ubuntu 18.04. Each experiment is repeated five times to avoid random errors, and the average results (with form _average value_\(\pm\)_standard deviation_) on the test sets are reported in Table 3 and Table 4. Next, we discuss the experimental results on each evaluation task separately.

Footnote 8: The code is open sourced in [https://github.com/TaiLvYuanLiang/HGWaveNet](https://github.com/TaiLvYuanLiang/HGWaveNet).

#### 5.2.1. Temporal Link Prediction

The results on temporal link prediction are shown in Table 3. Obviously, our HGWaveNet outperforms all baselines including the hyperbolic state-of-the-art model HTGN both on AUC and AP. To analyse the results further, we intuitively divide the six datasets into two groups: small (Enron, DBLP, AS733) and large (FB, HepPh, MovieLens), according to the scales. It can be observed that the superiority of our model is more significant on large graphs than small ones compared with baselines, especially those Euclidean methods. This is because the representation capacity of Euclidean methods decreases rapidly with increasing graph scales, while hyperbolic models remain stable by virtue of the fitness between data distributions and space properties.
* **w/o \(\mathbb{B}\):** HGWaveNet without hyperbolic geometry, implemented by replacing all modules with corresponding Euclidean versions.

We take the same experimental setup with HGWaveNet and baselines on these three variants, and the results are reported in the last rows of Table 3 and Table 4. The performance drops noticeably after removing any of these three components, which indicates their respective importance. In the following, we discuss the details of the effectiveness of these variants.

HDGC module imposes the diffusion process into hyperbolic graph convolution networks. It allows nodes to aggregate information from a wider range of neighbors and improves the efficiency of message propagation by calculating the stationary distribution of a long Markov process in a closed form. The fact that performance of w/o HDGC variant has a larger degradation on large graphs than small ones forcefully proves the effectiveness of this component for large graphs with long paths.

The purpose of HDCC module is to capture the internal order of causal correlation in sequential data. Generally, the larger a graph is, the more complex its evolution is and the richer historical information it has. The experimental results on w/o HDCC show the powerful ability of this component to capture causal order in temporal evolution process, especially on complex graphs (i.e. FB and MovieLens).

As observed in Table 3 and Table 4, the degradation of w/o \(\mathbb{B}\) is much more severe than that of the other two variants, which strongly supports our primary idea that hyperbolic geometry fits the power-law distributions of real-world graphs very well. Moreover, it is noteworthy that for most results, the variant w/o \(\mathbb{B}\) exhibits a comparable or even exceeding performance to other Euclidean baselines. This proves that our model architecture still keeps advanced even without the advantages of hyperbolic geometry.

### Parameter Analysis

We further study the influences of three hyper-parameters: representation dimension, truncated diffusion step and dilated depth.

We evaluate the performance of HGWaveNet and one of the best Euclidean models GRUGCN on two datasets FB (relatively sparse) and MovieLens (relatively dense) by setting the representation dimension into different values, as shown in Figure 6. On the one hand, it is clear that with the dimension decreasing, our model remains stable compared to GRUGCN, to which the hyperbolic geometry contributes greatly. On the other hand, for HGWaveNet, the degradation of the performance on MovieLens is severer than that on FB, which is consistent with the conclusion in (Wang et al., 2019) that hyperbolic models fit sparse data better than dense data.

Figure 7 shows the results of our model for temporal link prediction on MovieLens with different values of truncated diffusion step \(K\) in HDGC and dilated depth \(D\) in HDCC. The wrap-up observation that the performance generally increases as \(K\) and \(D\) increase proves the positive influences of diffusion process and dilation convolution. Specifically, in terms of truncated diffusion step, the performance has a great improvement from \(K=1\) to \(K=2\). When \(K>2\), the benefit from increasing \(K\) becomes too small to match the surge of computation from exponentially expanding neighbors in graphs. Dilated depth \(D\) is used to control the receptive field of causal convolution. However, as the receptive field expands, more noise is imported and may degrade the model performance. According to our extensive experiments, \(D=3\) is a nice choice in most situations, with the causal convolution kernel size being 2.

## 6. Conclusion

In this paper, we propose a hyperbolic graph neural network HGWaveNet for temporal link prediction. Inspired by the observed power-law distribution and implicit hierarchical structure of real-world graphs, we construct our model on the Poincare ball, one of the isometric models of hyperbolic spaces. Specifically, we design two novel modules hyperbolic diffusion graph convolution (HDGC) and hyperbolic dilated causal convolution (HDCC) to extract the spatial topological information and temporal evolutionary states, respectively. HDGC imposes the diffusion process into graph convolution and provides an efficient way to aggregate information from a wider range of neighbors. HDCC ensures that the internal order of causal correlations is not violated by applying the convolution filter only to previous data. Extensive experiments on diverse real-world datasets prove the superiority of HGWaveNet, and the ablation study further verifies the effectiveness of each component of our model. In future work, we will further generalize our model for more downstream tasks and try to use hyperbolic GNNs to capture more complex semantic information in heterogeneous graphs.

## Acknowledgments

This work is supported by the Chinese Scientific and Technical Innovation Project 2030 (2018AAA0102100), National Natural Science Foundation of China (U1936206, 62172237) and the Tianjin Natural Science Foundation for Distinguished Young Scholars (22JCJQJC00150).

Figure 6. The influence of representation dimension on two datasets FB and MovieLens for HGWaveNet and GRUGCN.

Figure 7. The influence of truncated diffusion step \(K\) (left) and dilated depth \(D\) (right) on MovieLens.