Source-linked AI summary
A Network Science Perspective on Evaluating Deep Graph Generative Models
Tianrui Mao, Abele Malan, Megha Khosla, Lydia Chen, Huijuan Wang
TL;DR
Because real social contact networks cannot be freely shared without privacy risks, the paper asks whether synthetic networks can support network-based epidemic mitigation evaluation. It compares deep graph generators and the configuration model using structural similarity and immunization-strategy utility, finding that SparseDiff and EDGE closely preserve multiple real-network properties and identify effective strategies.
Problem
Privacy risks limit sharing real social contact networks, creating a need to evaluate whether synthetic networks can support epidemic immunization research.
Method
The paper evaluates graph generators and the configuration model by comparing synthetic and real network properties and testing immunization-strategy rankings and outbreak sizes.
Results
SparseDiff and EDGE generate synthetic networks that closely preserve multiple real-world structural properties and accurately identify effective immunization strategies.
Takeaways & Limitations
Synthetic network generation models could facilitate network-based applications when real network data cannot be shared.
Takeaways & Limitations
The evaluation covers only one basic SIR-based immunization problem and requires real neighborhood networks for model training; scalability for larger neighborhoods needs further consideration.
Abstract
from arXiv · showhide
Traditional network models from network science, such as the Erdos-Renyi and configuration models, generate random networks that reproduce few selected topological properties observed in real-world networks. Deep graph generative models emerge as a data-driven approach, leveraging deep neural network architectures to learn complex structural distributions directly from real-world networks to generate more realistic synthetic networks. Because real social contact networks cannot be shared due to privacy risks, synthetic networks serve as an alternative for developing and evaluating epidemic mitigation strategies. In this work, we evaluate deep graph generative models as well as the configuration from a network science perspective by assessing both the topological similarity between generated and real-world networks and their utility in identifying effective node immunization strategies to sup- press epidemic/misinformation spreading. It is found that two deep graph generative models produce synthetic networks that closely resemble the structural properties of real-world networks, enabling them to identify effective immunization strategies.
1 Introduction
Classical network models preserve selected predefined properties, whereas deep graph generative models learn graph distributions from data to capture multiple structural properties. Synthetic networks can support graph learning and privacy-preserving network sharing, and this paper evaluates their similarity and immunization utility.
- Classical network models generate random graphs that preserve selected topological properties observed in real-world networks.The configuration model preserves each node’s exact degree.
- Deep graph generative models use neural networks to learn graph probability distributions directly from network data.This data-driven approach can implicitly capture multiple network properties and their dependencies.
- Synthetic graphs can augment limited graph datasets with realistic training examples for graph learning algorithms.
- Synthetic graphs can facilitate network data sharing by preserving key statistical properties while avoiding disclosure of individual-level connections.This reduces the risk of exposing sensitive relational information.
- The paper evaluates topological similarity and utility for epidemic immunization, which selects nodes to immunize to suppress epidemic or misinformation spreading.The motivation includes privacy concerns surrounding shared social contact networks.
2 Deep graph generative models
The study compares four graph generators with distinct architectures, alongside the configuration model baseline. Their representations and generation mechanisms trade off scalability, structural fidelity, and expressiveness for larger sparse graphs.
- The evaluation uses four distinct graph-generation architectures and the configuration model as a non-learning baseline.The models are adapted to datasets containing larger graphs than commonly used in computer science applications.
- GraphRNN: GraphRNN represents graphs as sequences and generates nodes and links sequentially using graph-level and link-level recurrent neural networks.Breadth-first-search orderings support link generation, while node-order sensitivity and long-range dependencies remain limitations.
- EDGE: EDGE is a discrete diffusion model that adds links to an initially empty adjacency matrix using active nodes and target degree information.Updating only a small active portion makes EDGE fast and scalable for sparse graphs, but link-only addition reduces expressiveness.
- SparseDiff: SparseDiff begins with a density-matched random graph and iteratively adds or removes links using structural and spectral features.Sparse partial processing supports scalability to larger graphs.
- GGSD: GGSD diffuses graph Laplacian eigenvalues and eigenvectors in the spectral domain to reconstruct adjacency structure.It offers partial-eigenpair and all-eigenpair variants.
3 Evaluation method
The evaluation generates synthetic local neighborhood networks from real-world network samples, compares structural distributions, and tests whether synthetic networks preserve immunization-strategy effectiveness under SIR spreading.
- Datasets and generation: The real-world network collection includes email, co-authorship, trust-based social, and Facebook friendship networks.The listed datasets include Ia-email-EU, CA-Astro Physics, Soc-advogato, Facebook, and CA-HepPh.
- Datasets and generation: Each generation model produces 1000 synthetic networks from sampled two-hop local neighborhood networks of real-world graphs.Real graphs are preprocessed by retaining their largest connected component before neighborhood sampling.
- Datasets and generation: Model configurations are based on original-author settings, with dataset-specific adaptations for neighborhood size, degree inputs, community structure, and sparse processing.EDGE draws target degrees directly from observed training networks, while SparseDiff processes one-tenth of possible links at a time.
- Epidemic immunization: Epidemic spreading is modeled with SIR dynamics, where infected nodes transmit at rate β and recover at rate γ.The tested values are β ∈ {0.2, 0.4, 0.6} and γ = 1.
- Epidemic immunization: The immunization task selects f% of nodes to minimize the final average outbreak size from a random seed.Immunization is implemented by removing selected nodes at t = 0.
- Immunization strategies: Centrality strategies rank nodes by topological metrics, and the evaluation tests whether their effectiveness ranking transfers from real to synthetic neighborhoods.Metrics include degree, leverage, collective influence, k-shell, betweenness, closeness, eigenvector, and PageRank centrality.
4 Performance analysis
The evaluation compares synthetic and real neighborhood networks through topological properties and immunization performance. Edge and SparseDiff most accurately reproduce real-world properties, while SparseDiff generally best preserves immunization rankings and outbreak sizes.
- Network similarity: Topological similarity is assessed using distributions of node count, degree, link density, clustering, modularity, and largest eigenvalue.
- Network similarity: Edge and SparseDiff reproduce real-world network properties more accurately than Configuration, GraphRNN, and GGSD.The other models show discrepancies in size, density, clustering, modularity, or degree heterogeneity.
- Immunization strategies: Immunization performance is evaluated across infection rates β ∈{0.2, 0.4, 0.6} and immunization rates f ∈{5%, 10%, 15%}, using outbreak size.
- Immunization strategies: Betweenness, Pagerank, and leverage centrality consistently perform best on real-world networks, whereas k-shell centrality performs worst.
- Immunization strategies: Smaller largest eigenvalues, smaller LCCs, and higher modularity characterize pruned networks produced by the three best-performing strategies.
- Model comparison: SparseDiff generally best reproduces both real-world immunization rankings and the average outbreak size associated with each strategy.It correctly identifies the three most effective and two least effective strategies; EDGE also performs well in identifying extremes.
5 Conclusion and future work
The paper finds that SparseDiff and EDGE generate synthetic networks preserving multiple structural properties and supporting effective immunization-strategy identification. It notes that the evaluation covers only one basic SIR immunization problem and that scalability for larger neighborhoods requires further consideration.
- Conclusion: SparseDiff and EDGE closely preserve multiple structural properties of real-world networks and enable identification of effective immunization strategies.
- Conclusion: The findings suggest network generation models could support network-based applications when real network data cannot be shared.
- Future work: The evaluation considers only one basic immunization problem modeled with the SIR process.The authors identify other applications as an area for exploration.
- Future work: Scalability should be examined in greater detail when identifying immunization strategies for larger neighborhood networks.