Hypergraph-Based Dynamic Graph Node Classification

Static graph neural networks have been widely applied in graph representation learning tasks. Therefore, we first utilize a backbone GNN to perform feature extraction on each node of every temporal slice, as shown in Fig. 2(a). This process yields a feature representation for each node at each time step. For the t-th temporal slice of the dynamic graph $\textbf{G}^{t}$, we can utilize it to obtain feature representations.

where $\mathbf{Z}^{t}$ represents the matrix of feature embeddings for the nodes in the graph snapshot $\mathbf{G}^{t}$ processed by the GNN, with $\mathbf{Z}^{t}=[\mathbf{z}_{1}^{t},\mathbf{z}_{2}^{t},\ldots,\mathbf{z}_{n}^{t}]$, where $n$ is the number of nodes. $\mathbf{A}^{t}$ denotes the adjacency matrix of $\mathbf{G}^{t}$, and $\mathbf{X}^{t}$ refers to the initial feature matrix of the nodes in $\mathbf{G}^{t}$.

In dynamic graphs, nodes possess both individual features and common features shared within their subgroups. To better capture the higher-order correlations of nodes within each time slice, we construct multi-scale hypergraphs by capturing individual-level and group-level dependencies, as shown in Fig. 2(b).

Individual-level hypergraph construction.  We capture the individual high-order dependencies of each node in the dynamic graph by constructing a series of individual hyperedges, denoted as $\mathcal{G}_{in}=(\mathcal{V}_{in},\mathcal{E}_{in})$. Here, $\mathcal{G}_{in}$ includes individual nodes $\mathcal{V}_{in}$ and the set of hyperedges $\mathcal{E}_{in}$. Specifically, for a given node $v_{it}$, we identify $K$ nodes from other time slices within a specified time range that are most close to the feature vector obtained from (1), excluding the current time slice. These $K+1$ nodes are then connected via a hyperedge $\mathbf{e}_{it}$, as shown in (2).

where $\mathcal{N}_{K}$ represents the set of $K$ nearest neighbors, which can be calculated using various distance metrics such as Euclidean distance, Chebyshev distance, cosine distance, etc. $|*|$ denotes the temporal distance between nodes. $\tau$ represents the threshold value of the time range. We model the multi-scale temporal dependencies in the dynamic graph by setting three threshold ranges: short-term connection, mid-term connection, and long-term connection, respectively. We construct the individual hypergraph $\mathcal{G}_{in}$ using $v_{it}$ and $e_{it}$ obtained from all nodes in each time slice.

Group-level hypergraph construction. To better capture the multi-granularity group features of each category in dynamic graphs, we construct a series of group-level hypergraphs $\mathcal{G}_{group}$, where $\mathcal{G}_{group}=(\mathcal{V}_{group},\mathcal{E}_{group})$, including group nodes $\mathcal{V}_{group}$ and group hyperedge sets $\mathcal{E}_{group}$. In summary, we first group the feature vectors $\mathbf{Z}^{t}$ according to the true labels $\mathbf{Y}^{t}$ of the nodes, followed by hierarchical clustering and aggregation of these groups within each time slice. This process yields spatio-temporal group representations, which are then used to construct hypergraphs for each node category, capturing both the features and their spatio-temporal dependencies in the dynamic network. The mathematical representation is as follows:

where $y_{v}^{t}$ denote the label of node $v$ at time $t$. By grouping node embeddings with the same label, we obtain $\mathbf{O}^{c,t}=\{\mathbf{z}_{v}^{t}\mid y_{v}^{t}=c\}$, where $C$ represents the number of node categories. The function $Cluster_{M}(\cdot)$ performs clustering on the grouped embeddings. Applying $Cluster_{M}(\mathbf{O}^{c,t})$ yields the clusters $\{\mathbf{O}^{c,t}_{1},\mathbf{O}^{c,t}_{2},\ldots,\mathbf{O}^{c,t}_{M}\}$, where $M$ denotes the number of clusters. The aggregation function $Agg(\cdot)$ is applied to aggregate the vectors within each cluster, which could be operations such as $\max(\cdot)$, $\min(\cdot)$, or $avg(\cdot)$. Finally, for each group, we obtain $\mathbf{Z}^{c,T}_{group}\in\mathbb{R}^{M\times T}$. This process is formalized to capture diverse temporal characteristics of nodes within the same category across different clusters at various time steps.

We merge each time slice obtained from $\mathbf{Z}^{c,t}_{group}$ by (3) to obtain the grouped $\mathbf{Z}^{c,T}_{group}$. Following the construction method of individual-level hypergraph in (2), we construct hyperedges for $\mathbf{Z}^{c,T}_{group}$ separately to capture the spatio-temporal evolutionary relationships of various category group characteristics, resulting in $\mathcal{V}_{group}^{c}$ and $\mathcal{E}_{group}^{c}$. Hence, we obtain $\mathcal{G}_{group}=\{\mathcal{G}_{group}^{c}\}_{c\in C}$.

After constructing individual-level hypergraph $\mathcal{G}_{in}$ and group-level hypergraph $\mathcal{G}_{group}$, We employ Hypergraph Neural Networks (HGNN)[24] for node-weighted information propagation and feature updating to obtain spatio-temporal fusion features within hyperedges, as illustrated in Fig. 2(c).

For a given hypergraph $\mathcal{G}$, the incidence matrix $\mathbf{H}$ is defined based on the node set $\mathcal{V}$ and edge set $\mathcal{E}$ as:

Based on $\mathcal{G}_{in}$ and $\mathcal{G}_{group}$, we can derive the individual and group-level incidence matrices, $\mathbf{H}_{in}$ and $\mathbf{H}_{group}$, through (4). Following the approach of frequency-domain GCNs [1], we use Fourier transformation to shift spatial signals to the frequency domain for convolution, and then apply the inverse Fourier transformation [24], as formalized by the following equation:

where $\mathbf{Z}$ represents the feature matrix, $\mathbf{H}$ denotes the incidence matrix, $\Theta$ is the learnable hypergraph convolution kernel, $\mathbf{W}$ is the learnable weight matrix, and $\sigma$ is the non-linear activation function.

More specifically, for a given node $v_{it}$, $H(v_{it})$ represents all hyperedges connected to node $v_{it}$, containing nodes with the highest relevance to $v_{it}$. We aggregate the features of nodes from different time slices in the hyperedges, except for $v_{it}$, using the corresponding weights $\mathbf{w}_{it}^{jt^{\prime}}$ in $H(v_{it})$ to capture the temporal dependencies within the same hyperedge:

$v_{it}$ and $v_{jt^{\prime}}$ represent a pair of nodes at different time slices within a hyperedge. $d(\mathbf{z}_{it},\mathbf{z}_{jt^{\prime}})$ denotes the distance between $v_{it}$ and $v_{jt^{\prime}}$ . We can use various methods to compute the distance, such as Euclidean distance, cosine distance, etc. $\sigma$ can be set as the median of distances between all pairs of vertices, $\mathbf{z}^{l-1}_{jt^{\prime}}$ represents the output of node $v_{jt^{\prime}}$ at layer $l-1$ in HGNN.

After obtaining different hyperedge features for the dynamic graph node $v_{it}$, we compute the weight by measuring the similarity between the hyperedge features and node features and normalize the weights using softmax function. Then, we perform edge-node level spatio-temporal dependency aggregation:

The node representations obtained from the above process, denoted as $\mathbf{z}^{l}_{it}$ ,are passed through a non-linear function, yielding the integrated representation of node dependencies across time and space.

After the hypergraph information propagation, we obtain the individual and group hypergraph representation, $\mathbf{Z}_{in}$ and $\mathbf{Z}_{group}$.By applying the softmax function, for each time slice, we compute the predicted labels $\mathbf{\hat{Y}}_{in}$ and $\mathbf{\hat{Y}}_{group}$ for the nodes in $\mathcal{G}_{in}$ and $\mathcal{G}_{group}$, respectively. The true labels for the group-level hypergraph, $\mathbf{Z}_{group}^{c}$, are represented by $c$ as follows:

For $\mathcal{L}_{in}$ and $\mathcal{L}_{group}$, we assign different weights, denoted as $\alpha$ and $\beta$, respectively, resulting in the overall loss function $\mathcal{L}_{all}$, which consists of the following two terms:

During training, we construct both individual and group-level hypergraphs to capture diverse node representations using hypergraph neural networks. During testing, without labels, we use only individual-level hypergraphs and the trained network for predictions. The group-level hypergraphs, used for data augmentation, capture evolving relationships within the same class, addressing variations in unseen test sets.

We conducted experiments using five real-world dynamic graph datasets, with detailed information provided in Table II, We selected seven baselines for comparison, including both static[1, 8] and dynamic graph neural networks[13, 18, 19, 16, 25]. The primary task is to predict the node labels in the test set at various time slices using the node features and label information from limited time slices in the training set. To better evaluate the model’s performance, we used accuracy and Macro-AUC as evaluation metrics. Each method employs a two-layer graph neural network, utilizing both GCN and GraphSAGE as GNN layers for experimentation.

As shown in Table I, we conduct experiments using both GCN and GraphSAGE backbones, with EvolveGCN and DySAT sharing experimental results across both sets. The results demonstrate that the HYDG model consistently outperforms baseline models in node classification tasks across five datasets. By constructing individual hypergraphs and multi-scale group-level hypergraphs while capturing spatio-temporal dependencies, HYDG achieves superior accuracy on the DBLP5, Reddit, Wiki, and ML-RATING datasets using both GCN and GraphSAGE backbones, and records the highest AUC scores on the DBLP3, Reddit, and ML-RATING datasets. Notably, HYDG shows a 2%-3% improvement in accuracy on the DBLP5 and Reddit datasets compared to the best-performing baselines, despite slightly trailing RNN-GCN in AUC on DBLP3. These results suggest that the ability of HYDG to capture spatio-temporal dependencies enables better learning of node representations and relationships in dynamic graphs, outperforming traditional methods based on self-attention mechanisms and RNNs.

To better explore the roles of individual-level hypergraphs and group-level hypergraphs in capturing spatio-temporal dependencies in dynamic graphs, we conduct ablation experiments on these two modules separately, and the results are shown in Fig. 3. (i) Removal of individual-level hypergraphs. Utilizing only group-level hypergraphs yields poor accuracy and AUC results. This is because group-level hypergraphs capture features only within each slice, resulting in insufficient usable nodes and inadequate capture of features and dependencies across samples. (ii) Removal of group-level hypergraphs. Utilizing only individual-level hypergraphs achieves relatively high accuracy but results in lower AUC. This is because the individual hypergraph construction, which links hyperedges by identifying each node’s nearest neighbors, may capture only single dynamic dependency patterns. Additionally, connections between nodes with different labels can lead to incomplete dynamic feature representations.