PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2610.02439v1cs.LG

TL;DR

Mechanistic graph models are interpretable but rely on instance-specific estimation, while deep models offer amortized inference but often lack interpretability and size extrapolation. This paper combines a recursive multifractal step graphon with a neural inverse operator; it reports strong zero-shot transfer and sensitive tracking of reversible EEG state changes.

  • Problem

    Mechanistic model recovery is instance-specific, while deep graph models often trade interpretability for amortized inference and are typically limited to training graph sizes.

    Source: §1 · p. 2

  • Method

    The paper combines a recursively parameterized multifractal step graphon with a neural inverse operator that recovers its base parameters in function space.

    Source: §1 · p. 2, §3.1 · p. 4

  • Results

    The method achieves the best average performance on three of four zero-shot graph-generation metrics and inferred EEG parameters track reversible brain-state changes more sensitively than traditional network statistics.

    Source: §5.3.1 · p. 8, §5.3.2 · p. 9

  • Takeaways & Limitations

    The results support using interpretable parameters with amortized inference for networks observed once or at sizes unseen during training.

    Source: §5.2 · p. 7, §6 · p. 10

    The model assumes the same connection rule repeats across scales, so networks with irregularly varying wiring rules fall outside that assumption.

    Source: §6 · p. 10

Abstract

from arXiv · show

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.

1 INTRODUCTION

Descriptive network statistics can obscure structural differences and vary across partial observations, while existing mechanistic and deep generative models have complementary limitations. The paper proposes combining interpretable generative rules with amortized inference that generalizes to unseen graph sizes.

1 INTRODUCTION

  • Recovering compact generative mechanisms can reveal hidden network differences that summary statistics obscure and that partial observations may distort.The paper motivates recovering mechanisms as a way to understand complex systems.Source: §1 · p. 2
  • Mechanistic-model recovery is instance-specific and can face local optima, slow convergence, and rapidly growing costs from searching latent node-to-community assignments.The estimation costs recur with each observation.Source: §1 · p. 2
  • Deep generative models offer amortized generation but often provide less interpretable representations and typically do not extrapolate to graph sizes outside training.The paper describes architectural size limits for autoregressive models and effective training-size limits for variational-autoencoder and diffusion approaches.Source: §1 · p. 2
  • The proposed framework formulates the generative model and parameter recovery in function space to combine interpretability and amortized inference, including generalization to unseen graph sizes.The paper frames both properties as jointly necessary for scientific applications.Source: §1 · p. 2
  • The multifractal step graphon is a recursively refined, piecewise-constant kernel whose small set of base coefficients encodes hierarchical community structure.The base parameters are θ(1) = (l(1), p(1)).Source: §1 · p. 2
  • The neural inverse operator casts graphon parameter recovery as operator learning, enabling amortized inference that generalizes to unseen graph sizes.Source: §1 · p. 2

2 RELATED WORK

Prior graphon methods face limits in either hierarchical representation, scalable inference, or the combination of interpretability and size flexibility. This work positions its approach as providing explicit wiring rules alongside an inverse operator that generalizes across graph sizes.

2 RELATED WORK

  • Standard step graphons offer interpretable blockwise connection probabilities but implicitly assume non-hierarchical topologies, while prior graphon estimation has used instance-specific statistical methods.Source: §2 · p. 3
  • Neural operators learn mappings between function spaces, but prior inverse-operator applications addressed PDE inverse problems rather than graphon estimation, to the authors’ knowledge.Source: §2 · p. 3
  • The approach combines explicit wiring rules linked in closed form to network properties with a function-space formulation that admits inference across graph sizes.The passage contrasts this with graphon autoencoders’ learned latent-factor interpretability and implicit neural graphons’ arbitrary-resolution flexibility.Source: §2 · p. 4

3 MULTIFRACTAL STEP GRAPHON FORMULATION

The formulation extends step graphons with a recursive Kronecker construction that compactly represents hierarchical connectivity and supports finite network sampling. Under a stated non-degeneracy condition, its parameters are identifiable up to base-community permutation.

3.1 OVERVIEW

  • The multifractal step graphon recursively refines a piecewise-constant kernel using base parameters for heterogeneous node attribution and weighted connectivity.A Kronecker recursion expands the parameters to depth K, yielding M^K communities with sizes and interaction strengths that factorize across scales.Source: §3.1 · p. 4

3.1.1 CONTINUOUS LATENT SPACE

  • The graphon formulation permits asymmetric kernels, with W(x, y) representing the probability of a directed edge from latent coordinate x to y.Source: §3.1.1 · p. 4

3.1.2 STEP GRAPHON PARAMETERIZATION

  • A step graphon partitions the unit interval into M subsets whose lengths come from a probability vector, while a blockwise affinity matrix specifies connection probabilities.The passage introduces the step-graphon construction from these partitions and affinities.Source: §3.1.2 · p. 4

3.1.3 MULTIFRACTAL CONNECTIVITY VIA KRONECKER RECURSION

  • Kronecker expansion of base parameters produces M^K latent intervals, with interaction amplitudes factorized multiplicatively across scales to permit varying heterogeneity.Uniform base connection probabilities yield a monofractal spectrum, whereas heterogeneous entries widen the spectrum; the parameters therefore control the monofractal–multifractal continuum.Source: §3.1.3 · p. 5

3.1.4 SAMPLING NETWORKS FROM THE MULTIFRACTAL STEP GRAPHON

  • Finite graphs are sampled by assigning nodes to latent intervals and using the graphon’s block value as pairwise interaction intensity.The implementation maps continuous interaction intensity to nonnegative integer edge weights with a conditional geometric distribution; higher connection probabilities yield heavier-tailed weights.Source: §3.1.4 · p. 5
  • Varying base parameters yields degree distributions spanning Poisson-like, log-normal-like, power-law-like, and bimodal regimes, as well as ranges of assortativity, modularity, spectral gap, and multifractal width.Source: Figure 3 · p. 6

3.1.5 IDENTIFIABILITY

  • Under a generic non-degeneracy condition on expanded block profiles, distinct multifractal step graphons identify their base parameters up to permutation.The proof uses block structure, uniqueness of Kronecker factorization, and consistent permutation across node-length and connection parameters.Source: §3.1.5 · p. 6

4 INFERENCE VIA NEURAL OPERATORS

The paper frames recovery of the graphon’s base parameters from an observed adjacency matrix as an inverse operator-learning problem. Its MWNOT implementation combines multiscale multiwavelet features with branch–trunk cross-attention; training details are deferred to an appendix.

4 INFERENCE VIA NEURAL OPERATORS

  • Recovering the base parameters from an observed graph amounts to learning an inverse operator from the graphon to its parameters.Because the first-level graphon is fully parameterized by these values, their recovery specifies the multiscale graphon.Source: §4 · p. 6
  • MWNOT combines a 2D multiwavelet decomposition with cross-attention as one architecture for approximating the inverse operator, not as a claim of architectural optimality.The basis is suited to low-regularity piecewise-constant graphons, and the paper reports that detail-coefficient energy grows exponentially with recursion depth.Source: §4 · p. 6

4.1 ARCHITECTURE

  • The input adjacency matrix is decomposed across L scales into coarse and detail coefficients, then branch–trunk cross-attention maps multiscale features to predicted base parameters.The branch encodes wavelet tokens; learnable trunk queries correspond to l(1) and p(1), and scale-specific outputs are decoded by MLPs.Source: §4.1 · pp. 6–7

4.2 TRAINING

  • Training details covering data generation, losses, optimization schedule, and hyperparameters are provided in Appendix F.Source: §4.2 · p. 7

5 EXPERIMENTS

The experiments test the model’s topology coverage, recovery across graph sizes, transfer to empirical graphs, and performance on single-observation networks, including an EEG case study.

5.1 COMPACT PARAMETERIZATION OF DIVERSE TOPOLOGIES

  • Varying θ(1) alone produces networks with distinct degree distributions, assortativity, modularity, spectral gaps, and multifractal spectrum widths.The spectrum ranges from monofractal to multifractal.Source: §5.1 · p. 7

5.2 ZERO-SHOT TRANSFER TO UNSEEN SIZE

  • MAE for p(1) and l(1) remains stable as graph size increases from N = 128 to N = 8192, and recovery also remains stable across hierarchical depths.The model is trained on N ∈ {128, 512, 1024} and evaluated across sizes and depths.Source: Figure 4 · p. 7, §5.2 · p. 7

5.3.1 GRAPH GENERATION BENCHMARK

  • The model has the best average performance on three of four zero-shot benchmark metrics, despite training only on synthetic graphs and using ∼22× fewer parameters than LGGM-X.It wins on all metrics in 4/12 domains; LGGM-X performs better on some domains, including infrastructure networks.Source: Table 1 · p. 8, §5.3.1 · p. 8
  • The benchmark compares zero-shot generation from synthetic graphon realizations with LGGM-X, which is pretrained on more than 5,000 empirical graphs with the target domain held out.The evaluation uses the same code, test sets, and metrics as the benchmark protocol.Source: §5 · p. 7, §5.3.1 · p. 8

5.3.2 APPLICATIONS TO SINGLE-OBSERVATION EMPIRICAL DATA

  • On single-observation networks, the zero-shot method is better than or tied with WMGM on 10 of 18 comparisons and runs 9–550× faster.WMGM is better on four of six spectral-error comparisons; the authors report a remaining gap in spectral structure.Source: Table 2 · p. 9, §5.3.2 · p. 9
  • In EEG networks, inferred assortativity and multifractal width separate moderate sedation from other states and return to baseline-like levels after recovery.Their effect sizes are |d| = 0.8–0.9, while traditional network statistics show smaller effects (|d| = 0.2–0.6), none significant after correction.Source: Table 3 · p. 9, §5.3.2 · pp. 9–10

6 DISCUSSION

The authors present the framework as complementary to deep and mechanistic models, while identifying assumptions and performance limitations that bound its current scope.

6 DISCUSSION

  • The framework is intended as a complementary method for settings requiring interpretable parameters and amortized inference, not as a replacement for deep or mechanistic models.LGGM-X and WMGM comparisons serve as reference points for transfer and fit.Source: §6 · p. 10
  • The model assumes the same connection rule repeats across scales, placing networks with irregularly varying rules outside its assumption.The inverse operator is not permutation-equivariant; the paper uses deterministic degree-sorting canonicalization.Source: §6 · p. 10
  • The authors identify spectral metrics as an area needing improvement and propose more expressive rules and comparisons of inverse-operator architectures as future work.Source: §6 · p. 10

AI USE STATEMENT

The authors report using generative AI tools in specified research and writing tasks, while reviewing AI-assisted work and taking responsibility for the paper’s final content.

AI USE STATEMENT

  • Generative AI tools were used to design and provide feedback on methodology and experiments, implement methods, and interpret results.Source: AI USE STATEMENT · p. 11
  • The authors report that AI tools were not used to develop theoretical models or conceptual frameworks, formulate mathematical claims, or assist with proofs.Source: AI USE STATEMENT · p. 11
  • The authors reviewed AI-assisted work and take responsibility for the final content, including AI-assisted text, claims, and artifacts.Source: AI USE STATEMENT · p. 11

Supplemental Material

The supplement explains the choice and expressivity of the base-community count, derives recursive closed forms for network statistics, and establishes identifiability of the base parameters up to community-label permutation.

A MODEL SELECTION

  • At depth K, M = 4 would yield 4096 blocks for the smallest training graphs at largest depth, so supporting larger M requires exponentially larger training graphs.With M = 2, the same setting yields 64 blocks.Source: A MODEL SELECTION · p. 16
  • An M = 2 model does not restrict the graph to two communities: two recursive steps yield an M = 4 rule whose base rule is Kronecker-factorizable.Unrestricted M = 4 additionally permits non-factorizable branching rules.Source: A MODEL SELECTION · p. 16

B.1 EXPECTED EDGE DENSITY

  • The expected edge density at depth K is the depth-1 density raised to the Kth power.This follows from factorization of the block parameters across the K recursive levels.Source: §B.1 · p. 16

B.2 EXPECTED DEGREE OF A NODE IN BLOCK q

  • Expected node degree decomposes into independent contributions from each recursive level, with each scale’s factor depending only on the node’s block at that level.Source: §B.2 · p. 16

B.3 MULTIFRACTAL SPECTRUM

  • The multifractal spectrum is determined by θ(1) alone in the limit; heterogeneity in p(1) yields a non-degenerate spectrum, while uniform entries give a collapsed spectrum.Source: §B.3 · p. 17

B.4 IMPLICATION

  • Across these derivations, depth-K observables are powers or products of depth-1 quantities, and the multifractal spectrum is fully characterized by θ(1).The factorizations provide analytical tools for relating θ(1) to observable network properties.Source: B CLOSED-FORM NETWORK STATISTICS UNDER… · p. 16, §B.4 · p. 17

C.1 STEP 1: A STEP GRAPHON DETERMINES ITS BLOCK PARAMETERS UP TO PERMUTATION

  • A step graphon determines its block structure and parameters up to permutation of the blocks.Because the partition intervals are contiguous, their boundaries are properties of the graphon; only block labels can differ.Source: C PROOF OF PROPOSITION 1… · p. 17, §C.1 · pp. 17–18

C.2 STEP 2: UNIQUENESS OF THE KRONECKER FACTORIZATION

C.3 STEP 3: COMBINING THE RESULTS

The proof combines block structure and Kronecker factorization to identify the multifractal step graphon’s base parameters up to community relabeling. The architecture then uses multiscale wavelet features and cross-attention to predict those parameters.

C.3 STEP 3: COMBINING THE RESULTS

  • The Kronecker structure forces the block permutation to arise from a base-level permutation, so the graphon determines its base parameters up to community relabeling.The two base parameters must share the same permutation.Source: §C.3 · p. 19

C.4 DISCUSSION OF ASSUMPTIONS

  • Identifiability assumes every base community has positive measure; a zero-mass community is absent and reduces the effective model dimension.With zero interaction entries, multiple rank-1 factorizations may coincide; exact zeros are measure-zero under the stated sampling procedure.Source: §C.4 · p. 19
  • The result requires K ≥ 2; at K = 1, identifiability reduces to the classical standard step-graphon case.It also does not establish identifiability across arbitrary measure-preserving graphon representatives or stability from finite noisy samples.Source: §C.4 · p. 19

D.1 ARCHITECTURE

  • A 2D multiwavelet transform decomposes the adjacency matrix into coarse coefficients for macroscopic connectivity and detail coefficients for high-frequency variations.The detail coefficients cover horizontal, vertical, and diagonal variations, and the coarse output is passed to the next scale.Source: §D.1 · pp. 19–20
  • The model flattens multiscale wavelet coefficients into tokens, then uses cross-attention to map the input function to fixed-size representations of target parameters.The tokens form the branch input, while learnable query embeddings serve as the trunk.Source: §D.1 · p. 20
  • Scale-specific representations are concatenated into global embeddings, which MLPs decode into predictions of the base parameters.The queried targets are the community distribution l(1) and interaction matrix p(1).Source: §D.1 · p. 20

E EMPIRICAL VALIDATION OF THE MULTIWAVELET BASIS

The multiwavelet detail shares increase with recursion depth, matching the graphon’s recursive structure. The input-ordering procedure addresses the architecture’s reliance on spatially aligned block structure.

E EMPIRICAL VALIDATION OF THE MULTIWAVELET BASIS

  • Deeper recursion adds finer-scale block boundaries, increasing detail energy where the encoder and cross-attention represent the multifractal structure.The authors interpret this as an empirical match between the basis and graphon construction.Source: E EMPIRICAL VALIDATION OF THE… · p. 21
  • Both ρfine and ρdetail grow approximately exponentially with K, spanning roughly two orders of magnitude over the recursion depths used in training.Figure S1 plots fine-scale detail share and total detail energy share against recursion depth.Source: Figure S1 · p. 21, E EMPIRICAL VALIDATION OF THE… · p. 21

E.1 INPUT ORDERING

  • Function-space processing trades architectural permutation equivariance for generalization to unseen graph sizes and benefits from spatially aligned block structure.Degree sorting provides a deterministic, metadata-free ordering for inputs and approximately aligns blocks under the model’s expected-degree relation.Source: §E.1 · p. 21

F.1 DATA GENERATION

The appendix specifies how synthetic training data are generated, how the model is optimized, and the settings used for compute and expressivity sweeps.

F.1 DATA GENERATION

  • Training pairs are generated from randomly sampled base community measures and strictly positive interaction matrices, expanded by Kronecker products before multinomial node assignment and geometric edge sampling.Each community measure entry is initialized to at least 0.1, with parameter sets having |l(1)1| ≤ 0.01 rejected.Source: §F.1 · p. 22

F.2 LOSS FUNCTION

  • The composite training loss uses binary cross-entropy with logits for the interaction matrix and KL divergence for the community distribution.The interaction loss is applied to raw MLP outputs.Source: §F.2 · p. 22

F.3 OPTIMIZATION AND HYPERPARAMETERS

  • Training runs for 2,000 epochs on graphs of sizes 128, 512, or 1,024 and depths 2, 4, or 6, with recovery error evaluated on new unaugmented graphs.Each epoch draws 2,000 graphs; the selected checkpoint minimizes validation MAE for the two base parameters.Source: §F.3 · p. 22

F.4 COMPUTE RESOURCES.

  • Training used two NVIDIA V100 GPUs and took approximately eight hours; inference is reported as a per-graph forward-pass time.The timing excludes normalization, sorting, and log-binning.Source: §F.4 · pp. 22–23

G EXPRESSIVITY SWEEP DETAILS

  • The expressivity sweeps vary community heterogeneity and interaction structure across specified parameter interpolations, with 10 realizations per setting for the two main sweeps.A separate panel uses three interaction targets, while degree-distribution regimes use hand-tuned configurations.Source: G EXPRESSIVITY SWEEP DETAILS · p. 23

H ZERO-SHOT BENCHMARK: EVALUATION PROTOCOL AND FULL RESULTS

The appendix details the zero-shot benchmark protocol and the single-network reconstruction comparison, then defines the multifractal, degree, and spectral distances used for evaluation.

H ZERO-SHOT BENCHMARK: EVALUATION PROTOCOL AND FULL RESULTS

  • The zero-shot protocol applies one parameter estimate per benchmark graph without per-graph optimization, selects recursion depth from a closed-form density relation, and averages generated-graph metrics over ten seeds.The benchmark uses held-out graphs from twelve domains; generated graphs are postprocessed under the benchmark protocol.Source: H ZERO-SHOT BENCHMARK: EVALUATION… · p. 23

I SINGLE-INSTANCE RECONSTRUCTION: PROTOCOL

  • The single-instance comparison evaluates six once-observed networks, contrasting the operator’s reconstruction with a per-instance WMGM fit; neither method’s depth is chosen by minimizing evaluation metrics.WMGM is fitted separately at each depth, while the operator receives a dyadically cropped input.Source: I SINGLE-INSTANCE RECONSTRUCTION:… · p. 24

J.1 MULTIFRACTAL SPECTRUM (f(α)) ESTIMATION

  • Multifractal MSE compares empirical and synthetic continuous f(α) curves, using linear interpolation over their shared α support.The curves are estimated with the Chhabra-Jensen method and compared across 30 q values and 50 α-support points.Source: §J.1 · pp. 24, 26

J.2 DEGREE WASSERSTEIN DISTANCE

  • Normalized degree Wasserstein distance compares degree distributions after degrees are converted to probability mass functions, removing dependence on absolute scale.The underlying degree distance is the 1-Wasserstein distance between empirical and synthetic degree distributions.Source: §J.2 · p. 26

J.3 SPECTRAL WASSERSTEIN DISTANCE

  • Spectral Wasserstein distance compares the eigenvalue distributions of the empirical and synthetic normalized Laplacians; directed-network spectral distances use union-symmetrized graphs.The appendix describes the normalized Laplacian spectrum as bounded between 0 and 2 regardless of network size or absolute density.Source: §J.3 · pp. 26–27

K EEG ANALYSIS

In the EEG case study, inferred-rule summaries distinguish moderate sedation from other states, while most networks meet the multifractal fit criterion. For periodic multirule generators, repeated blocks permit exact single-basis compression, and the shortest such block determines the minimal effective branching number.

K EEG ANALYSIS

  • For 20 volunteers across four sessions, alpha-band EEG connectivity used session-averaged, surrogate-thresholded wPLI; inferred rules were summarized by assortativity and multifractal width.Edges were retained when session-mean wPLI exceeded the 95th percentile of the channel-pair surrogate distribution.Source: K EEG ANALYSIS · p. 27
  • LOSO AUCs were 0.69 [0.55, 0.83] versus baseline, 0.72 [0.58, 0.85] versus mild sedation, and 0.75 [0.62, 0.89] versus recovery.All three 95% bootstrap intervals exclude chance (0.5).Source: K EEG ANALYSIS · p. 27, Figure S2 · p. 28
  • 76 of 80 EEG networks passed the multifractal-MSE fit threshold; 71 passed on degree distance and 27 on spectral distance.Multifractal MSE is the decision metric; degree and spectral distances are reported for completeness.Source: Figure S2 · p. 28, K EEG ANALYSIS · p. 29
  • Fit did not differ detectably across sedation states (Kruskal–Wallis p = 0.40; Friedman p = 0.42).Moderate-sedation comparisons with each other state had Holm-corrected p = 0.65; baseline versus recovery had p = 0.86.Source: K EEG ANALYSIS · p. 29

L COMPRESSION OF A PERIODIC MULTIRULE GENERATOR

Related papers

Loading 2610.02439v1…