A Diffusive Data Augmentation Framework for Reconstruction of Complex Network Evolutionary History

Recent advancements in temporal networks have significantly enriched complex network analysis [7, 8, 9, 10, 11]. Early models such as Erdős-Rényi and Barabási-Albert ([12, 13]) mainly addressed static network properties, offering limited applicability to dynamic systems. [14] provided foundational concepts like temporal paths, establishing a basis for subsequent research. [15] highlighted bursty interaction patterns in real-world networks, emphasizing temporal heterogeneity. [16] extended random walk theory to temporal networks, crucial for understanding diffusion processes. [17] introduced methods for detecting communities in dynamic structures, while [18] integrated predictive models for forecasting interactions. [19] reviewed evolving community detection approaches, showcasing the need to address both temporal and topological dynamics in analysis. [6] introduced the problem and method for predicting network evolution based on network structures. By utilizing the timestamps of a subset of network edges, the method effectively predicts and reconstructs the remaining edges, achieving promising results. Furthermore, this work demonstrated that the reconstructed edge timestamps could also enhance performance in link prediction tasks, further underscoring the significance of studying network evolution.

Recent developments in temporal network generation have significantly advanced the field, focusing on capturing both the structural and temporal dynamics of evolving networks. [20] improved temporal modeling by transforming temporal interactions into static graphs, while [21] utilized motif-based approaches for generating time-dependent structures, though it assumed fixed rates and lacked adaptability to real-world temporal fluctuations. [22] introduced TIGGER leveraging temporal point processes, combining both inductive and transductive learning to handle large-scale, complex networks with superior efficiency and accuracy. This progression highlights the growing ability of temporal models to replicate the nuanced evolution of real-world dynamic systems.

Employing generative methods such as generative adversarial networks (GANs) to learn a distribution based on a small sample of data and subsequently conduct sampling to obtain a large quantity of training samples is a commonly adopted method [23, 24, 25, 26]. Diffusion models have recently shown significant advantages in performance, and have done well on graph generation tasks [27, 28, 29, 30], making them suitable for solving the problem of small-sample learning in reconstructing network evolutions. Specifically, [28] first propose to introduce the score-based diffusion model to solve the graph generation problem. The Gaussian noise is adopted to construct the diffusion process, leading to poor sparsity generated graphs. [29] explore jointly modeling the nodes and edges with semantic features. [27] use multinomial noise to make the diffusion process operating in discrete space, which greatly improves the performance. Therefore, we can see that using graph diffusion models to generate sufficient samples to enhance edge order prediction performance is promising.

In the study of network evolution, predicting the exact generation time of edges represents a significant challenge. Directly learning the relationship between network features and edge generation times proves to be difficult due to the inherent complexity and variability of these relationships across different networks. Moreover, such a task lacks generalizability; the features learned in one network often fail to generalize effectively to another, rendering the task unsuitable for cross-network transferability. Thus, learning to predict edge generation times within the same network—where partial timestamps are available for predicting the remaining ones—is appropriate. However, if the goal is to generalize across networks and learn the relationship between network features and edge generation times, the equivalence transformation becomes crucial.

To address this limitation, we reformulate the original task of predicting edge generation times into an equivalent task: predicting the relative temporal order of generation between any two edges in the network. This reformulation simplifies the prediction problem into a pairwise classification task, which is more robust and transferable across networks.

We rigorously prove the mathematical equivalence between these two tasks, with the final equivalence result expressed as:

where $x$ represents the pairwise prediction accuracy, and $M$ denotes the total number of edges in the network. The detailed proof is provided in Appendix -A.

Furthermore, as illustrated in Fig. 2, experimental results validate this equivalence in real-world networks. These results demonstrate that improving pairwise prediction accuracy directly contributes to reducing the overall prediction error in edge generation times. Equation 1 reveals that the overall sequence error scales inversely with the square root of the edge count, favoring networks with many edges.

This equivalence also yields an additional benefit: achieving a low RMSE in predicting edge generation times does not necessitate exceedingly high accuracy in pairwise temporal order predictions. This insight reduces the performance requirements for the underlying pairwise prediction model, enhancing the practical applicability of the approach.

To infer the complete temporal order of edge generation from pairwise relationships, we adopt the Borda algorithm. This algorithm aggregates pairwise predictions to construct a global sequence of edge generation times while ensuring consistency across predictions. A detailed explanation of the Borda algorithm, including its derivation and implementation, is provided in the Appendix -B.

In the study of complex networks, the generation time of edges is a critical factor influencing network evolution. Our prediction task aims to learn the relationship between network structure and edge generation time, given a temporal network. Specifically, we focus on how to infer the generation order of edges in the absence of time labels.

Our ultimate goal is to predict the generation time of each edge for a pure network structure. To simplify the task, we specify it as follows: for any two edges $e_{i}$ and $e_{j}$ in the network, we need to predict their generation order, determining which edge is generated first and which is generated later. By inferring the order of all edges, we can construct the overall generation sequence of edges in the network, thereby gaining a comprehensive understanding of the network’s evolutionary process.

1. Temporal Network Representation: Let the temporal network $G$ consist of a set of nodes $V$ and a set of edges $E$. Each edge $e_{k}\in E$ represents a connection between a pair of nodes $(u_{k},v_{k})$ and has an associated generation time $t_{k}$.

2. Edge Generation Order: For any two edges $e_{i}=(u_{i},v_{i})$ and $e_{j}=(u_{j},v_{j})$, we define the generation order relation $R(e_{i},e_{j})$ as follows:

Here, $R(e_{i},e_{j})=1$ indicates that edge $e_{i}$ is generated before edge $e_{j}$, while $R(e_{i},e_{j})=0$ indicates that the generation time of edge $e_{i}$ is later than or equal to that of edge $e_{j}$.

3. Edge Generation Time Prediction: Our task can be expressed as a binary relation prediction problem, where the objective is to predict the edge generation order $R(e_{i},e_{j})$ by learning the structural features of the network $S(G)$:

In this context, $\hat{R}(e_{i},e_{j})$ is the predicted generation order, and the function $f$ represents the model used to infer the generation order based on network structural features.

4. Construction of Edge Generation Sequence: Once the generation order for all edges is predicted, we can obtain the overall edge generation sequence $T$, expressed as:

Here, $k_{1},k_{2},\ldots,k_{m}$ are the indices of edges arranged according to the predicted generation order.

Through the above description and mathematical definitions, our task clearly demonstrates how to infer edge generation times based solely on structural information in the absence of time labels, thus providing robust support for the evolutionary prediction of complex networks.

The framework for predicting the order of two edges in a network is structured as follows. Initially, we utilize an embedding representation learning method to obtain a representation vector for each edge in the network. These embedding vectors are derived from 12 network features, which include the degree, clustering coefficient, betweenness centrality, common neighbors, random walk probability, minimum spanning tree connection, Jaccard coefficient, resource allocation index, Adamic-Adar index, shortest path length, PageRank, and average clustering coefficient [31, 32, 33]. These features are calculated based on the network’s adjacency matrix and provide a comprehensive structural description of each edge. Let us denote the edges as $e_{1}$ and $e_{2}$, with their respective embedding vectors represented as $\mathbf{h}_{1}$ and $\mathbf{h}_{2}$.

Each embedding vector is subsequently fed into a fully connected neural network comprising three layers. The architecture is defined as follows:

Input Layer: The first layer receives the input vectors $\mathbf{h}_{1}$ and $\mathbf{h}_{2}$, which are concatenated to form a single input vector $\mathbf{h}=[\mathbf{h}_{1};\mathbf{h}_{2}]\in\mathbb{R}^{d}$, where $d$ is the dimension of the embedding vectors.

Hidden Layer: The second layer is a hidden layer with a dimensionality of $\frac{2}{3}d$. This layer applies a linear transformation followed by a ReLU activation function, defined as:

where $\mathbf{W}_{1}\in\mathbb{R}^{\frac{2}{3}d\times d}$ and $\mathbf{b}_{1}\in\mathbb{R}^{\frac{2}{3}d}$ are the weight matrix and bias vector for the hidden layer, respectively.

Output Layer: The output layer consists of two neurons that produce a scalar output $z_{1}$ and $z_{2}$:

where $\mathbf{W}_{2}\in\mathbb{R}^{2\times\frac{2}{3}d}$ and $\mathbf{b}_{2}\in\mathbb{R}^{2}$ are the weights and biases for the output layer.

After obtaining the outputs $z_{1}$ and $z_{2}$, we apply the softmax function to convert these into a probability distribution representing the likelihood that each edge was generated first:

These probabilities reflect the generation times of the edges, normalized to ensure that they sum to one.

The loss function $L$ is defined as the categorical cross-entropy loss between the predicted probabilities and the true labels $y\in\{0,1\}$, where $y=1$ indicates that $e_{1}$ occurs before $e_{2}$:

Additionally, we incorporate $L2$ regularization to mitigate overfitting. The regularization term is defined as:

where $\lambda$ is the regularization strength. Thus, the final loss function to be minimized is:

Current methods for network evolution prediction rely on partial edge timestamps to train models and predict the temporal order of remaining edges. For instance, the Nature Communications [6] approach performs well on synthetic networks by learning from one fully timestamped network and predicting on another. However, its effectiveness diminishes on real-world networks due to the structural homogeneity of synthetic networks (e.g., Barabási–Albert [34], Popularity-similarity-optimization model [35], Fitness model [36]), which share scale-free properties. In contrast, real-world networks exhibit diverse and complex generative mechanisms, making learned models difficult to generalize across networks.

A more critical limitation arises in scenarios where no temporal information is available. In practice, collecting edge timestamps is often infeasible, leaving only the network’s topological structure. Existing methods, which depend on partial temporal annotations, fail to address the challenge of predicting temporal dynamics in completely untimestamped networks.

To address the limitations of existing methods, we propose a joint training approach that combines multiple networks to train a single model, exposing it to diverse network types and improving its ability to generalize to unseen networks.

In Section V-I, we demonstrate why traditional methods struggle with transferability when trained on a single network type. Structural differences across networks lead to significant performance gaps, making these models unreliable on unseen data. Reformulating the prediction task—from predicting edge generation times to predicting pairwise edge order—mitigates this issue. Furthermore, Section V-C1 highlights the superior performance of our jointly trained model, which achieves consistent results on unseen networks.

Fig. 4 illustrates our approach. Solid circles represent existing networks, and current methods often exhibit instability, as gaps between networks hinder generalization. Joint training reduces these gaps by incorporating a diverse range of networks, enabling the model to learn more generalizable patterns.

To further enhance the model’s transferability, we generate augmented networks using diffusion models, represented by the small solid circles in Figure 4. These augmented networks expand the range of each original network, increasing coverage across network types and reducing gaps. The broader state space allows the model to encounter more diverse network structures during training, improving its robustness on unseen networks. The dashed circles in Figure 4 represent the combined sets of original and augmented networks, showcasing the scalability and adaptability of our approach.

In Section IV-B1, we detail the diffusion-based augmentation process and demonstrate its effectiveness in further improving the model’s performance.

As shown in Fig. 5, we propose an enhanced framework for network evolution prediction based on diffusion models. The core idea is that we have a limited number of temporal networks. By performing extensive sampling on each temporal network, we input the samples into the diffusion model to learn the underlying generation mechanism of the temporal networks. The diffusion model then generates an arbitrary number of augmented samples. Using a combination of a small number of real temporal networks and a large number of diffusion-augmented temporal networks, we input them into a comparative paradigm-based neural network (CPNN) for training. This approach results in a model with better transferability and stability. In practical applications, when a static network is input into the trained CPNN, we can predict the temporal order of pairs of edges. Further, by applying the Borda count algorithm, we can derive the overall edge order of the entire network, enabling the prediction of edge evolution processes in static networks.

This study employs 10 real-world datasets from five distinct categories: Protein-Protein Interaction (PPI) Networks, World Trade Web (WTW), Collaboration Networks, Animal Networks, and Transportation Networks. These datasets, covering diverse domains, provide a solid foundation for evaluating the proposed methods. The details of the datasets are summarized in Table I, and the descriptions are as follows:

• •

  PPI Networks: This category includes five networks: Fungi, Human, Fruit, Worm, and Bacteria. Each node represents a protein, while edges denote interactions between proteins. The datasets capture the first occurrence of each edge to distinguish the order in which interactions are established. These networks are particularly valuable for studying temporal evolution in biological systems.

• •

  WTW: The WTW dataset represents global trade relations between countries from 1997 to 2013. Nodes correspond to countries, and edges signify bilateral trade relationships. The generation time of an edge reflects when trade between two countries was first recorded. This dataset highlights the evolving dynamics of global trade.

• •

  Collaboration Networks: We use the Thermody collaboration network, constructed from publication data of the American Physical Society. Nodes represent researchers, and edges denote coauthorship relationships. The earliest collaboration between two authors determines the generation time of an edge. This dataset provides insight into academic collaboration patterns.

• •

  Animal Networks: The Weaver network is based on 10 months of social interaction data from colonies of weaver birds in South Africa. Nodes represent individual birds, and edges denote interactions. To improve data density and reduce sparsity, the raw data is aggregated into 8 snapshots, capturing the temporal dynamics of social behavior.

• •

  Transportation Networks: Two transportation networks are used: Airplane and Coach. In the Airplane network, nodes are airports, and edges represent flight connections, while in the Coach network, nodes are coach stations, and edges denote transport links. The generation time of an edge is the earliest recorded connection between two nodes. The data is aggregated into daily snapshots, resulting in 5 snapshots for Airplane and 4 snapshots for Coach.

These datasets, spanning diverse domains such as biology, economics, collaboration, animal, and transportation, provide comprehensive support for the experiments in this study.

To evaluate the effectiveness of our proposed method, we compare it against a set of state-of-the-art baseline models. These models are designed to explore the relationship between node, edge, and network features and the edge weights within a network. The baseline models fall into three categories and are described as follows:

• •

  Random Forest (RF) [44]: A tree-based machine learning algorithm that uses node and edge-level features to predict edge weights. Its robustness and ability to handle non-linear feature interactions make it a strong benchmark.

• •

  TIGGER [22]: A temporal generative model that combines synthetic network generation with node embeddings to capture dynamic relationships and predict edge weights over time.

• •

  NetGAN [45]: A generative adversarial network (GAN)-based model designed to recreate realistic network structures by learning the patterns of walks in the graph. The model is adapted here to generate networks with weighted edges.

• •

  Digress [46]: A state-of-the-art method for network generation, utilizing a discrete denoising diffusion model to directly operate on graph structures while preserving their sparsity and topology. By employing a Markovian noise process and a graph transformer for reconstruction, Digress sets a new benchmark in generating large-scale graphs.

These baselines encompass a wide range of methodologies, from classical physics-based models to advanced deep learning and generative approaches, providing a comprehensive basis for comparison. The detailed parameter settings for these models are presented in the supplementary material.

To further validate the effectiveness of our augmentation strategy, we applied it to networks generated using alternative baseline methods and compared the results. Specifically, synthetic networks were generated through baseline approaches, and these augmented samples were then combined with the original training data for joint training. The results revealed that, although the augmentation increased the diversity of the training samples, the performance improvements achieved by the baseline methods were limited compared to those observed with our proposed approach.

In this experiment, five real networks were used to train the generation models, and each trained model generated 100 augmented networks. To maximize the performance gains, we selected the augmented network set from the five generated options that brought the most significant improvement when used for augmentation. Among these, the Worm network generated by our method led to the largest performance enhancement. The augmented baseline models showed some performance improvement compared to their non-augmented counterparts. However, the magnitude of the improvement was notably smaller than that achieved with our proposed method. Across all test networks, the accuracy showed modest gains, indicating that while the additional synthetic samples did contribute to enhancing the predictive capabilities of the baseline models, the improvements were not as significant as those observed with our augmentation strategy. This suggests that, although the baseline methods benefited from augmentation, they were less effective in capturing the structural and temporal dynamics of the networks, resulting in smaller performance gains compared to our approach.

To evaluate the effectiveness of our augmentation method compared to baseline approaches, we analyzed the discrepancy between generated networks and their corresponding real networks. The primary metric used for this evaluation was the Normalized Root Mean Square Error (NRMSE), which measures the difference between the generated edge generation times and the real timestamps.

Table IV presents the NRMSE results for networks generated using our method and the baseline approaches. Our method, which learns directly from real networks, consistently achieves lower NRMSE values compared to the baselines. This indicates that the generated networks more accurately replicate the temporal dynamics of edge generation observed in the real data. Baseline methods exhibit higher NRMSE values, suggesting a lack of fidelity in capturing the nuances of real network evolution. The inability to closely match the temporal properties of real networks limits the utility of baseline-generated samples in enhancing model performance.

Table V illustrates the performance of models trained on one network and tested on others. The results highlight two key findings: First, models perform well on the same network they are trained on. Diagonal entries, such as Airplane (0.9915) and Fruit (0.8589), demonstrate the ability to accurately capture the relationship between network features and edge generation times within the same network. Second, the models often fail when transferred to different networks. As seen in the underlined results, such as Thermody on Fruit (0.4787) and Fruit on Worm (0.5369), accuracies below 0.6 indicate poor transfer performance in binary classification tasks. This inconsistency reflects the complexity of real-world network mechanisms and the challenge of determining whether two networks are compatible for transfer.

In summary, models trained on a single network are unstable when applied to new networks. While some networks show decent transfer performance, others exhibit significant failures, highlighting the limitations of single-network training for generalizable predictions.

This section evaluates the structural and dynamic similarity between augmented and the original networks. We employ various metrics, including degree distribution, eigenvector centrality, and clustering coefficient distribution, to assess similarity. The analysis reveals that the degree distributions of the networks generated by TopoEvoDiff closely align with those of the original networks. This indicates a strong preservation of structural characteristics. Furthermore, the eigenvector centrality measures show a robust correlation between nodes’ importance in both networks, confirming the retention of critical structural roles. Lastly, clustering coefficient distributions closely match between the generated and original networks, reflecting consistent local clustering tendencies.

Fig. 9 highlights the effectiveness of our approach, showing that the enhanced networks generated by TopoEvoDiff exhibit structures more similar to the original networks compared to those produced by the representative TIGGER method. The top graphs present results for the Airplane network, while the bottom graphs correspond to the Thermody network. This demonstrates the ability of our method to generate augmented networks with greater structural fidelity.

The results of predicting edge generation timestamps within a single network reveal an important finding: high prediction accuracy can be achieved using only a small subset of the network’s edges. As shown in Fig. 10, utilizing just 20% of a network’s edges for training yields strong performance, and increasing the number of training edges does not lead to significant improvements. This indicates that beyond a certain threshold, the additional training samples do not provide substantial value for improving accuracy within the same network.

This observation further supports the uniqueness of our augmentation strategy. The improvement in model performance on unseen networks is not merely a result of increasing the number of training samples. Instead, it demonstrates that the augmented samples generated through our method contribute meaningful and diverse information, enabling the model to generalize effectively across different networks. This contrasts with the plateauing effect observed when merely increasing training edges from the same network, highlighting the distinctive value of our augmentation approach.

Pairwise relationship prediction addresses the challenges of network heterogeneity and facilitates cross-network generalization by normalizing relationships across networks. This approach is crucial for transferring learned models between networks with diverse structural and temporal characteristics, a task that direct prediction often fails to achieve.

Direct prediction struggles due to significant differences in edge timestamp distributions and feature characteristics across networks. For instance, as shown in Fig. 11, edge timestamps in Thermody are evenly distributed, whereas other networks exhibit skewed distributions. Similarly, clustering coefficient distributions vary greatly, hindering generalization.

Some network features are more transferable. For example, the common neighbor count exhibits similar distributions across networks, as demonstrated in Fig. 11. This aligns with our experimental findings, where common neighbor count proves highly effective for learning the relationship between network features and edge generation timestamps. Furthermore, by shifting to pairwise learning of feature-edge relationships, normalization is achieved within the network itself, ensuring that the models learned through this method are inherently transferable across networks.