A Generative Model of Complex Networks Using Graphons and Neural Inverse Operators

Wooseong Choi; Italo'Ivo Lima Dias Pinto; Chen Sun; Gaurav Gupta; Dong Song; Paul Bogdan

cs.LGOct 1, 2026

A Generative Model of Complex Networks Using Graphons and Neural Inverse Operators

Authors: Wooseong Choi, Italo'Ivo Lima Dias Pinto, Chen Sun, Gaurav Gupta, Dong Song, Paul Bogdan

Organizations: Department of Biomedical Engineering University of Southern California Los Angeles, CA 90089 · Department of Electrical Engineering University of Southern California Los Angeles, CA 90089 · AWS AI Santa Clara, CA 95050

Abstract

Generative graph models are central to understanding and simulating complex networks. However, existing approaches have complementary strengths and limitations. Mechanistic models offer interpretability but rely on instance-specific estimation methods. Deep generative models, on the other hand, offer amortized inference at the cost of interpretability and are largely limited to graph sizes seen during training. Scientific applications motivate a framework that retains the strengths of both paradigms. We bridge them by formulating both the generative model and parameter recovery in function space. A multifractal step graphon extends standard step graphons with a recursive construction that compactly parameterizes complex networks. This formulation admits a neural inverse operator to recover its parameters, enabling inference on unseen graph sizes. We evaluate our model, trained only on synthetic multifractal step graphon realizations, against both paradigms. Against a graph foundation model pretrained on empirical networks, our method achieves the best average performance on three of four metrics in a zero-shot graph-generation benchmark, indicating that the model transfers to real-world graphs. We also apply our method to single-observation networks, a regime largely inaccessible to deep models that require training corpora, where it performs comparably to an instance-specific method that optimizes on each graph. In a multi-subject EEG case study, the inferred parameters track a reversible change in brain state more sensitively than traditional network statistics. Together, these results indicate that mechanistic interpretability and amortized inference can be effectively unified in a generative graph model to enhance our understanding of complex networks.

Figures & tables

Figure 1: Discovery of Hidden Structures in Real-World Networks (a) The base graphon encodes hidden community structures underlying complex networks. (b) Kronecker expansion of base parameters produces the multifractal step graphon. (c) Finite realization of the graphon produces networks that share similar properties with those seen in various empirical domains 2 2 2 Figure 2 incorporates a brain tractography image by Yeh et al. (2018) [ CC BY-SA 4.0 ] and a protein interaction network by Chen et al. (2019) [ CC BY 4.0 ] via Wikimedia Commons. The citation network by citationgraph.org is Public Domain (CC0). This derived schematic is distributed under CC BY-SA 4.0. . Recovering the generative rule reveals (d) hidden differences between networks with the same statistics and (e) the shared latent structure of a network from different partial observations, where subsampling can produce different statistics.

Figure 2: Neural inverse operator architecture. (a) The input adjacency matrix is decomposed across $L$ scales by a 2D multiwavelet transform, yielding hierarchical coefficients that are tokenized and processed by a branch network (Keys and Values). (b) Learnable queries for $\ell^{(1)}$ and $p^{(1)}$ pass through a trunk network and are combined with the branch via cross-attention. Scale-specific outputs are decoded by MLPs to predict the base parameters.

Figure 3: Compact Parameterization of Diverse Topologies. (a) Degree distributions span Poisson-like, log-normal-like, power-law-like (with exponential-tail), and bimodal regimes that are present in real-life networks. (b) Sweeping $w_{\mathrm{struct}}$ allows expression of varying levels of assortativity and disassortativity. (c) $w_{\mathrm{struct}}$ also controls the full range of modularity (left axis) and spectral gap $\lambda_{2}$ (right axis). (d) Multifractal spectra forms a continuous envelope from monofractal to multifractal.

Figure 4: Model Accuracy on Synthetic Graphs. (a) The model generalizes to unseen graph sizes and (b) shows stable performance across varying levels of hierarchical structure.

Domain	Method	DEG	CC	Spec	Orb	Domain	Method	DEG	CC	Spec	Orb
FB	DiGress	0.3376	0.6298	0.0797	0.3593	BIO	DiGress	0.2712	0.5202	0.1127	0.3188
	LGGM-X	0.4723	0.6843	0.2924	0.7555		LGGM-X	0.1081	0.2696	0.0900	0.2053
	Ours-Mono	0.2782	0.3045	0.0308	0.0412		Ours-Mono	0.0879	0.1467	0.0827	0.1584
	Ours	0.0589	0.0500	0.0284	0.0403		Ours	0.0442	0.0605	0.0629	0.1090
ASN	DiGress	0.1496	0.3258	0.1506	0.4420	ECON	DiGress	0.2987	0.4841	0.2162	0.3834
	LGGM-X	0.0281	0.2440	0.0830	0.0618		LGGM-X	0.1213	0.0920	0.1120	0.1086

Table 1: Zero-shot Performance Comparison

Domain	Method	Time (ms)	MFrac	DegW	SpecW	Domain	Method	Time (ms)	MFrac	DegW	SpecW
C. elegans	WMGM	2060	2.68e-2	5.67e-4	6.97e-2	P2P Gnutella	WMGM	2540	5.19e-3	1.41e-4	8.09e-2
	Ours	3.76	2.19e-4	1.20e-3	1.27e-1		Ours	198	3.56e-3	1.23e-4	1.24e-1
Drosophila	WMGM	1930	7.35e-3	2.29e-4	6.41e-2	Power Grid	WMGM	1810	5.88e-4	4.23e-5	1.81e-1
	Ours	14.1	3.84e-3	2.69e-4	1.18e-1		Ours	198	1.24e-3	2.54e-5	2.58e-1
Allen Mouse	WMGM	1050	1.52e-4	1.38e-4	3.99e-3	MN Roads	WMGM	1490	1.73e-3	5.92e-5	1.86e-1
	Ours	2.95	7.86e-3	9.86e-5	6.82e-3		Ours	50.9	2.42e-3	1.24e-4	1.84e-1

Table 2: Reconstruction of Single-Instance Networks

Inferred generative rule $\hat{\theta}^{(1)}$
Measure	Baseline	Mild	Moderate	Recovery	$d$ Base $-$ Mod	$d$ Mild $-$ Mod	$d$ Rec $-$ Mod	$d$ Base $-$ Rec
Assortativity index	$-0.75\pm 0.32$	$-0.74\pm 0.27$	$-0.48\pm 0.34$	$-0.76\pm 0.29$	$\mathbf{-0.84}$ (0.043)	$\mathbf{-0.87}$ (0.043)	$\mathbf{-0.91}$ (0.036)	$0.03$
$\Delta\alpha$	$3.45\pm 2.29$	$3.44\pm 2.11$	$1.71\pm 1.86$	$3.55\pm 2.11$	$\mathbf{0.83}$ (0.048)	$\mathbf{0.87}$ (0.019)	$\mathbf{0.92}$ (0.019)	$-0.05$
Classical network metrics
Mean clustering	$0.67\pm 0.12$	$0.66\pm 0.12$	$0.73\pm 0.16$	$0.68\pm 0.11$	$-0.40$	$-0.45$	$-0.36$	$-0.07$
Mean shortest path	$1.36\pm 0.16$	$1.37\pm 0.16$	$1.28\pm 0.16$	$1.36\pm 0.15$	$0.48$	$0.57$	$0.47$	$0.03$

Table 3: Revealing Hidden Differences in EEG Networks Under Sedation.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure S1: Multiwavelet energy response to recursion depth. (a) Fine-scale detail share

\rho_{\text{fine}}

. (b) Total detail energy share

\rho_{\text{detail}}

. Both quantities grow approximately exponentially with

K

, consistent with the multiplicative scaling structure of the multifractal step graphon.

Domain	Method	DEG	CC	Spec	Orb
FB	DiGress	0.3376	0.6298	0.0797	0.3593
	LGGM-X	0.4723	0.6843	0.2924	0.7555
	Ours-Mono	0.2782 $\pm$ 0.0017	0.3045 $\pm$ 0.0166	0.0308 $\pm$ 0.0004	0.0412 $\pm$ 0.0008
	Ours	0.0589 $\pm$ 0.0027	0.0500 $\pm$ 0.0013	0.0284 $\pm$ 0.0008	0.0403 $\pm$ 0.0007
ASN	DiGress	0.1496	0.3258	0.1506	0.4420
	LGGM-X	0.0281	0.2440	0.0830	0.0618

Appendix

Table S1: Full version of Table 1 with seed-to-seed standard deviations. Lower is better.

Domain	Method	Time (ms)	MFrac	DegW	SpecW
C. elegans	WMGM	2060 $\pm$ 436	2.68e-2 $\pm$ 2.17e-2	5.67e-4 $\pm$ 2.55e-4	6.97e-2 $\pm$ 3.47e-3
	Ours	3.76 $\pm$ 0.97	2.19e-4 $\pm$ 4.02e-5	1.20e-3 $\pm$ 2.08e-5	1.27e-1 $\pm$ 6.92e-4
Drosophila	WMGM	1930 $\pm$ 77	7.35e-3 $\pm$ 8.56e-3	2.29e-4 $\pm$ 1.18e-4	6.41e-2 $\pm$ 1.62e-2
	Ours	14.1 $\pm$ 0.03	3.84e-3 $\pm$ 3.68e-4	2.69e-4 $\pm$ 6.71e-6	1.18e-1 $\pm$ 1.42e-3
Allen Mouse	WMGM	1050 $\pm$ 243	1.52e-4 $\pm$ 1.51e-5	1.38e-4 $\pm$ 3.76e-5	3.99e-3 $\pm$ 9.20e-3
	Ours	2.95 $\pm$ 0.04	7.86e-3 $\pm$ 2.00e-3	9.86e-5 $\pm$ 8.96e-6	6.82e-3 $\pm$ 8.37e-4

Appendix

Table S2: Full version of Table 2 with seed-to-seed standard deviations.

Panel of Figure 11 — Figure S2: Supplementary EEG analyses. (A) Predictive validity. ROC curves of the leave-one-subject-out (LOSO) logistic regression. The legend gives the AUC with its 95% bootstrap interval over subjects. Dotted line represents chance. (B) Fit by state. Reconstruction error $D$ (multifractal MSE, mean over ten generated networks) of every EEG network, grouped by sedation state ( $n=20$ per state). Boxes represent median and interquartile range. Whiskers represent $1.5\times$ IQR. Dashed line represents the pass threshold of (C) $D=0.0185$ . (Kruskal–Wallis $p=0.40$ ; Friedman over subjects $p=0.42$ ; two-sided Mann–Whitney tests of moderate sedation against each other state, Holm-corrected, $p=0.65$ for all three; baseline vs recovery $p=0.86$ ). (C) Synthetic reference range. Distribution of $\log_{10}D$ for 500 model-generated networks whose density lies in the EEG range (gray) and for the 80 EEG networks (blue), for the multifractal MSE (MFrac; the decision metric), the normalised degree Wasserstein distance (DegW) and the spectral Wasserstein distance (SpecW). Dashed lines represent the 95th percentile of the model-generated networks ( $0.0185$ , $0.0016$ and $0.017$ ). The number of EEG networks below the line pass are as follows: 76 of 80 on MFrac, 71 of 80 on DegW, and 27 of 80 on SpecW.

Graphon Theory

See all 9 papers

Jul 8, 2026

DiPhon: Diffusion on Graphons for Scalable Graph Generation

Diffusion models represent a leading paradigm for graph generation, with notable impact in domains such as molecular design. Yet, scaling these models to large graphs remains an open problem. We approach this question in the dense-graph setting through the lens of graphons, the size-agnostic limit objects of dense graph sequences, to study how structural graph statistics behave across node-size scales. This perspective leads to DiPhon, a diffusion framework for size-scalable graph generation. Specifically, we formulate a continuous diffusion process on the graphon space via a Jacobi stochastic differential equation (SDE), and propose DiPhon, a discretized graph-level process that mimics these dynamics on finite graphs. We further derive the corresponding reverse-time process, which requires access to the marginal score. For the Jacobi process, this score interestingly admits a tractable form, which we estimate from data via graph denoising and plug into the reverse process to generate graph samples. We prove that DiPhon matches exactly the first moment of the marginal distributions induced by the continuous graphon process, and approximates the second moment up to a closed-form discrepancy. Thus, DiPhon inherits key size-agnostic statistical properties of the graphon dynamics, providing a principled route toward scalable graph generation. Empirically, we demonstrate this scalability by training on small graphs and generating progressively larger graphs at inference time, without retraining, while preserving their core topological properties.

Sergio Rozada, Yiming Qin, Manuel Madeira +2

King Juan Carlos University · EPFL, Lausanne, Switzerland · University of Pennsylvania

Graphon Theory Graph Generation Graph Diffusion

Ask PDF

Oct 5, 2026

Graph Data Augmentation via Contrastive Generator Inversion ( $\texttt{DCBA}$ )

Graphs provide a natural representation of many complex systems, ranging from social platforms to ecosystems. However, the development of graph-based machine learning methods is often constrained by the limited availability of large and diverse graph datasets. In this paper, we introduce

\texttt{DCBA}

, a model-based approach to graph data augmentation that infers the configuration of a synthetic graph generator from an observed network. We instantiate the proposed framework using the

\texttt{ABCD}

generator, which produces scale-free networks with community structure. Our model learns a joint representation of graphs and generator parametrisations using a multi-positive contrastive objective with soft negative weighting. The learned representation enables the prediction of an

\texttt{ABCD}

configuration whose stochastic realisations preserve the macrostructural properties encoded by the generator. Experiments show that

\texttt{DCBA}

recovers generator parameters more accurately and robustly than an algorithmic inverse-modelling baseline. Its downstream utility is further demonstrated in community detection, where inferred configurations used to fine-tune

\texttt{PRoCD}

improve AMI on average by

161\%

on synthetic and

273\%

on real-world networks.

Mateusz Stolarski, Michał Czuba, Łukasz Kraiński +4

Wrocław University of Science and Technology · University of Technology Sydney · SGH Warsaw School of Economics +1

Synthetic Data Augmentation Data Augmentation Graph Generation Graph Data Augmentation

Ask PDF

Sep 1, 2026

A Network Science Perspective on Evaluating Deep Graph Generative Models

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.

Tianrui Mao, Abele Malan, Megha Khosla +2

Delft University of Technology, the Netherlands · University of Neuchâtel, Switzerland

Synthetic Data Generation Generative Modeling Synthetic Data Evaluation

Ask PDF

Abstract

Graphon Theory

Explore similar work

DiPhon: Diffusion on Graphons for Scalable Graph Generation

Graph Data Augmentation via Contrastive Generator Inversion (DCBA\texttt{DCBA}DCBA)

A Network Science Perspective on Evaluating Deep Graph Generative Models

Graph Data Augmentation via Contrastive Generator Inversion ( $\texttt{DCBA}$ )