From topology learning to graph generation: A unifying perspective

I. INTRODUCTION

• Graph structure learning addresses either inferring an individual graph’s topology from node observations or learning a distribution over graph samples for synthesis.The two formulations differ in both objective and observed data: node observations for topology learning versus graph samples for graph generation.Source: §I · pp. 1–2
• The proposed framework models graph data through mappings h: Θ → G and f: G → X, making topology learning the inverse of f and graph generation the inverse of h.Here, h generates graph topologies from parameters, while f generates node observations from a given topology.Source: §I · pp. 2–3
• Model-based methods use specified statistical or physical mappings and offer rigorous formulations with stronger identifiability or theoretical guarantees, but depend on valid modeling assumptions.These assumptions limit applicability relative to data-driven methods, which learn implicit mappings directly from data.Source: §I · p. 4
• Data-driven methods make fewer assumptions and can adapt to downstream tasks, but their flexibility generally reduces interpretability and theoretical guarantees.For graph generation, this flexibility can support learning a probability distribution rather than only a point estimate.Source: §I · p. 4
• The review’s main contribution is a unified perspective that places topology learning and graph generation, including their model-based and data-driven forms, under one framework.This perspective highlights complementary strengths and potential synergies across research communities.Source: §I · p. 4
• The framework motivates boundary-spanning formulations and methodological transfer, including direct links from graph parameters to signals and combinations of GSP ideas with deep generative learning.The review specifically proposes combining graph filtering and signal smoothness with deep graph generative models, while generative learning can inform topology inference.Source: §I · p. 4

A. Problem instances

• The framework defines topology learning from graph signals, graph generation from graph instances, and task-driven structure learning as related problem instances within one generation process.Topology learning infers W from signals under fX or bfX, whereas graph generation learns hG or bhG to sample new graphs; downstream labels or objectives can guide either formulation.Source: A. Problem instances · pp. 5–6

B. Families of approaches

• The literature separates model-based learning with known fX or hG from data-driven learning that estimates these mappings from paired observations or graph collections.Known mappings support likelihood-based estimation, while unknown mappings can be learned from graph-signal pairs or graph-level observations and then used for inference or generation.Source: B. Families of approaches · pp. 6–7

A. Learning graph topology with a known mapping fX

• With a known fX, topology learning estimates a graph adjacency matrix from signals, commonly using smoothness models in which neighboring nodes have similar values or distributions.Representative formulations include PGMs, Gaussian Markov random fields, and GSP models; estimation often uses MLE or objectives that penalize signal variation across connected nodes.Source: A. Learning graph topology with a… · pp. 7–8
• The framework identifies a direct link between PGM and GSP topology learning: restricting the precision matrix to Laplacian-like structure makes graph smoothness central to both approaches.GSP factor-analysis models use x = Uh+n with Gaussian noise, while related methods extend learning beyond Gaussian signals to exponential-family noise.Source: A. Learning graph topology with a… · p. 8
• Kernel-based topology learning promotes smoothness jointly on the learned graph and a node-attribute kernel space, improving robustness to randomly missing observations.The regularizer xT (L⊗K†)x becomes a modified Laplacian quadratic form that captures smoothness in both spaces; addresses randomly missing entries, while and assume a known missingness mask.Source: A. Learning graph topology with a… · pp. 8–9
• Topology learning extends beyond a single graph to time-varying settings, where consecutive learned graphs are constrained to remain similar, and to extensions addressing streaming data, partial observations, hidden nodes, and class-specific adjacency matrices.One formulation constrains the number of edges modified across consecutive timestamps to be small via ℓ1-norm-based regularization.Source: A. Learning graph topology with a… · p. 9
• Optimization formulations can be solved, for example, by block-coordinate descent, but tuning hyperparameters such as ρ is challenging; addresses this by unrolling an algorithm for a reformulated version of Eq. (2).The formulations remain based on prototypes that explicitly promote signal smoothness.Source: A. Learning graph topology with a… · pp. 9–10
• Known dynamical mappings support topology learning from diffusion, infection, and autoregressive observations by modeling temporal and spatial dependencies, including spatiotemporal smoothness.For example, learns transmission probabilities as edge weights by maximum likelihood, while uses polynomial adjacency dynamics and jointly learns L and temporal correlation parameters R.Source: A. Learning graph topology with a… · pp. 10–11
• These approaches can learn directed graphs, including DAGs interpreted as causal relations; they differ mainly in enforcing acyclicity, with traditional approaches relying on a combinatorial constraint and NOTEARS proposing enforcement.Source: A. Learning graph topology with a… · pp. 11–12
• Known-mapping topology learning converts acyclicity into the continuous constraint h(W) = tr(e^W◦W)−n = 0 and solves the resulting program with an augmented Lagrangian method.Extensions address time-series data,, sparsity in W [51], sparsity in n [52], and joint estimation of W and unknown noise.Source: A. Learning graph topology with a… · p. 12
• Under certain assumptions, a network game admits a unique and stable Nash equilibrium, with β determining the nature of strategic interaction;, exploit this relationship.Source: A. Learning graph topology with a… · p. 12
• Graph filtering unifies smoothness and several dynamical models through a graph shift S and filter g(·), encompassing low-pass, band-limited, diffusion, and stationary processes.Diffusion-based methods include heat kernels and dictionary learning, while polynomial-filter methods use adjacency or Laplacian shifts and may impose sparsity.Source: A. Learning graph topology with a… · p. 13
• Under symmetric S and i.i.d. Gaussian x0, graph stationarity makes covariance C commute with S, so they share eigenvectors; eigenvalues are then found by optimization –.Source: A. Learning graph topology with a… · pp. 13–14

B. Learning graph topology with an unknown mapping bfX

• With an unknown mapping, topology learning learns graph G from observed signals x by learning the mapping through training examples and a quality criterion; for stationary graph processes, eigenvectors of S can be obtained without knowledge of {gk}.Source: A. Learning graph topology with a… · p. 14

A. Learning graph topology with a known mapping fX

• Commutativity-based methods learn a sparse matrix S from an estimated graph shift ˆG, avoiding eigendecomposition and symmetry assumptions used in and.When the input covariance is unavailable, related methods instead use input–output pairs, jointly estimating filter parameters and graph structure under known support assumptions [74],.Source: A. Learning graph topology with a… · p. 15
• Bayesian topology learning replaces deterministic point estimation with MAP inference using a likelihood from graph filtering and a topology prior approximated by a GNN.The algorithm alternates annealed Langevin updates of W with gradient updates of filter parameters, using ground-truth adjacency matrices to train the prior.Source: A. Learning graph topology with a… · p. 16
• Because the classical SEM is linear and restrictive for nonlinear relations, uses MLP node mechanisms whose first-layer weights define functional-dependence edges under sparsity and DAG constraints.The resulting reconstruction-loss optimization recovers a DAG underlying the observations.Source: A. Learning graph topology with a… · p. 16

MLP: MLP

• Variational encoder–decoder models learn an explicit DAG W by encoding observations into latent noise and decoding them through a nonlinear structural model while optimizing the ELBO.Unlike ’s implicit functional-dependence graph, directly estimates W subject to a DAG constraint.Source: MLP: MLP · p. 17
• For temporal trajectories, encodes a factorized distribution over latent edge types and uses a decoder GNN to predict observations, while addresses amortized inference across time series.These frameworks recover latent interaction graphs for explaining past and predicting future trajectories without relying on a prototype process such as the SEM.Source: MLP: MLP · p. 17

C. Incorporating domain knowledge in topology learning

• Domain knowledge provides inductive biases that guide topology learning toward desirable solutions, motivated by the prevalence of constraints in real-world networks.Many such constraints can be encoded in closed forms amenable to optimization.Source: C. Incorporating domain knowledge in… · pp. 18–19
• Explicit priors include sparsity, Cartesian-product graph structure, and k-component structure, imposed through precision-matrix ℓ1 penalties, graph factorization, or constraints on the first k eigenvalues.Source: C. Incorporating domain knowledge in… · pp. 18–19
• Closed-form constraints are mathematically convenient but restrictive, making properties such as degree distributions and local clustering coefficients harder to encode.This limitation has left these network-science characterizations less studied in explicit approaches.Source: C. Incorporating domain knowledge in… · p. 19
• Implicit approaches use reference graphs or ground-truth adjacency data to capture topological properties through learned latent similarities or score functions.A VAE encourages similarity to a template graph in latent space, while a GNN approximates the gradient of the log prior on vectorized adjacency matrices [76].Source: C. Incorporating domain knowledge in… · p. 19

A. Learning graph generative models with a known mapping hG

• Given M observed graphs and known hG: Θ → G, the goal is to estimate the distribution parameter and use it to generate new graph instances.From a statistical learning perspective, this is a parameter estimation problem.Source: A. Learning graph generative models… · pp. 19–20
• The ER model generates each possible edge independently with probability p, whose MLE is consistent and converges in mean square as the number of observed graphs grows.The β-model extends this setup to heterogeneous expected degrees, with node parameters estimated by an efficient fixed-point iteration and a consistent estimator.Source: A. Learning graph generative models… · p. 20
• ERGM generalizes ER and β models using sufficient statistics such as edge and triangle counts, but its MLE requires approximating an intractable partition function.The MLE is consistent under certain conditions on the sufficient statistics.Source: A. Learning graph generative models… · pp. 20–21
• End-to-end variants invert fX ◦ hG from graph signals, enabling centrality or community inference without directly observing topology under assumptions such as low-pass filtering.For blind community detection, spectral clustering on the covariance matrix of graph signals recovers block assignments with theoretical guarantees under certain conditions.Source: A. Learning graph generative models… · pp. 21, 23
• In the affine PA model, m is identified by edge counts and δ is estimated by MLE; the resulting estimator is consistent and asymptotically normal as n →∞.PA generates power-law degree distributions by attaching new nodes preferentially according to existing degree plus δ.Source: A. Learning graph generative models… · pp. 21–22
• For SBM, known block assignments permit MLE estimation of block-edge probabilities, whereas unknown assignments motivate EM or spectral-clustering estimators that are consistent under stated conditions.The unknown-assignment likelihood is intractable because it sums over K^n assignments; EM treats assignments as latent variables.Source: A. Learning graph generative models… · p. 22
• Latent-variable models introduce z to generate graphs, with representations encoding global structure, node embeddings, or both, but typically provide weaker identifiability and fewer statistical recovery guarantees.Graph VAEs encode observed graphs with qϕ(z|G) and decode them with pθ(G|z), optimizing reconstruction and KL terms; nearby latent points support interpolation and sampling.Source: A. Learning graph generative models… · pp. 23–24
• Autoregressive graph generators construct graphs through conditional generation steps, factorizing the graph distribution into actions such as adding nodes, creating edges, or assigning attributes, while capturing dependencies and enforcing structural constraints.Representative examples include GraphRNN, and these models remain sensitive to node ordering.Source: A. Learning graph generative models… · pp. 24–25
• Hierarchical autoregressive generation improves scalability while preserving diffusion expressiveness, enabling graphs with several thousand nodes and better extrapolation to unseen graph sizes.It refines graph resolution through multiscale expansion and local diffusion rather than predicting every node or edge individually.Source: A. Learning graph generative models… · p. 25
• AutoGraph recasts autoregressive graph generation as sequence modeling through a reversible graph-to-sequence transformation, enabling scalable generation with decoder-only Transformers.This formulation bridges graph generation and autoregressive language modeling.Source: A. Learning graph generative models… · p. 25
• GANs learn an implicit graph distribution rather than explicitly maximizing data likelihood, and incorporating global structural information into implicit graph generative models substantially improves expressive power.Adversarial training is often unstable, with issues such as mode collapse and optimization difficulties.Source: A. Learning graph generative models… · pp. 25–26
• Diffusion models generate graphs by iteratively denoising from a simple prior, learning reverse dynamics while using a prescribed forward corruption process that connects data to noise.They can operate on adjacency matrices, node and edge attributes, or continuous latent graph representations, and generate samples from the learned graph distribution rather than reconstructing a specific original graph.Source: A. Learning graph generative models… · p. 26
• Diffusion models represent generation as iterative refinement through latent graph states, improving flexibility and global structure modeling but requiring many denoising steps and substantial computational cost.They have been extended to continuous-time, mixture, latent, structure-aware, and autoregressive-hybrid formulations.Source: A. Learning graph generative models… · p. 27
• Flow-based and flow-matching models learn probability transport from a simple reference distribution to graph space, providing an efficient alternative to diffusion while retaining complex-distribution modeling.Flow matching directly learns time-dependent transport dynamics rather than an invertible transformation with Jacobian determinants.Source: A. Learning graph generative models… · pp. 27–28
• DeFoG adapted flow matching to graph generation, achieving competitive sample quality with substantially fewer sampling steps than diffusion models.Subsequent work improved stability and expressiveness, incorporated graph geometry and reward signals, and extended transport maps to categorical variables.Source: A. Learning graph generative models… · p. 28
• Bayesian graph structure generation targets posterior distributions over graph structures conditioned on observed data, rather than the empirical distribution of observed graph instances.The posterior combines likelihood p(D|G) with a prior p(G).Source: A. Learning graph generative models… · p. 28
• GFlowNets sequentially construct graphs while optimizing flow consistency so their sampling probability is proportional to the unnormalized posterior, enabling diverse posterior exploration instead of a single point estimate.They learn reusable policies that can accelerate posterior exploration while maintaining sample diversity and support Bayesian model averaging, uncertainty quantification, and robust structure discovery.Source: A. Learning graph generative models… · p. 29

Explicit constraints

• Explicit constraints restrict a learned graph generator’s distribution to admissible graphs, paralleling how hard constraints restrict feasible estimates in topology learning.In graph generation, the constraint acts on the support of the learned distribution.Source: C. Incorporating domain knowledge in… · pp. 29–30
• PRODIGY projects each sampling step toward a user-specified constrained space, imposing hard and potentially non-differentiable requirements without retraining the underlying model.The projection mechanism works with pretrained continuous or discrete graph diffusion models.Source: C. Incorporating domain knowledge in… · pp. 29–30
• ConStruct modifies discrete diffusion with edge-absorbing noise and a constraint-aware projector so intermediate and final graphs satisfy structural families such as planarity or acyclicity.This construction keeps generated graphs within the constrained family throughout the diffusion process.Source: C. Incorporating domain knowledge in… · p. 30

Implicit topology learning

• Implicit approaches absorb topological properties from observed graph samples into model parameters or latent representations without an explicit feasibility set or topology-specific penalty; NetGAN learns random-walk distributions, reproducing degree, community, and motif statistics.Source: C. Incorporating domain knowledge in… · p. 30
• Unlike PRODIGY and ConStruct, implicit methods encourage topological validity only in distribution and do not guarantee every generated sample satisfies the observed properties.Their learned distributions may capture topology statistically without enforcing validity sample by sample.Source: C. Incorporating domain knowledge in… · p. 30

Task-driven formulation

• Task-driven learning treats the graph as an intermediate representation for prediction and jointly optimizes its structure with downstream objectives.The downstream task supplies additional supervision, biasing learned structures toward predictive utility rather than solely explaining observations.Source: §V · p. 30

Optimization framework

• Because graph structure influences the downstream model and receives supervision from it, task-driven learning often yields a nested optimization in which both components are updated jointly.Bilevel optimization algorithms include hypergradient-based methods [152] and penalty-based methods.Source: §V · pp. 30–31

Example 15: Tasks through supervised graph neural networks

• In supervised graph neural network tasks, proposed bilevel optimization to jointly learn the GNN and supporting graph topology, using validation performance upper-level and training loss lower-level objectives.Source: §V · p. 32

Example 16: Tasks through latent states

• Latent-state formulations encode tasks such as denoising, sampling-set selection, and economic-network utility through a task-dependent state that regularizes topology learning.In [158], equilibrium conditions from a network game form the lower-level problem, while the upper level fits observed signals and regularizes the equilibrium-dependent topology.Source: §V · p. 32

Task-induced topology learning

• Task-structured methods can sometimes incorporate downstream objectives as direct single-level regularizers, and implicit task bias can correspond to explicit properties such as degree heterogeneity.These results span graph signal clustering, classification representations, and sampling-set selection, while [158] connects equilibrium utility optimization to explicit topological priors.Source: §V · p. 33

Task-driven graph generation

• Downstream-task learning is extending from topology to graph generation through SBM posteriors, non-uniform ER models, diffusion models, and generated-node augmentation.Research on unknown dynamics and the broader interplay between graph topology learning and downstream tasks remains relatively scarce and still developing.Source: §V · p. 34

V. TASK-DRIVEN GRAPH STRUCTURE LEARNING

• Task-related rewards directly influence the policy used for graph generation.Source: §V · p. 34
• Synthetic accessibility is identified as an example of a task-related reward.Source: §V · p. 34
• Drug-likeness is identified as another example of a task-related reward.Source: §V · p. 34

• The section identifies shared characteristics between topology learning and graph generation and discusses developments that connect the two problems.These commonalities support a unified perspective and may inspire new formulations and methodologies.Source: §VI · p. 34

• Topology learning recovers latent graph structure from node observations under assumptions such as smoothness, dynamics, or graph filtering, while also identifying the mechanism generating those observations.The learned graph can therefore define a generative model for synthesizing or predicting graph signals through the known or learned observation process.Source: A. A unified generating process for… · p. 34
• Graph generation learns the graph-generating mechanism and a probability distribution over directly observed graph instances, enabling synthesis of unseen graphs with similar statistical and structural properties.Source: A. A unified generating process for… · p. 34
• The unified hierarchy places latent parameters Θ above graph structure G and graph-structured observations X, but existing methods typically recover only one stage: G-to-X topology learning or Θ-to-G graph generation.Consequently, neither family fully models the complete mechanism responsible for observed graph data.Source: A. A unified generating process for… · pp. 34–35
• Recent work bridges the gap by combining traditionally separate elements, jointly learning graph topology and formation parameters for heterogeneous graphs, and incorporating graph operators into graph-supported signal generation,.Source: A. A unified generating process for… · p. 35

• GSP, PGMs, GML, and network science historically evolved independently despite studying related graph-structured data.Source: B. Bridging communities in graph… · p. 35
• Viewing these perspectives as complementary learning problems on one generating process creates opportunities to combine GSP priors, GML flexibility, and network-science mechanisms.Examples include physically grounded priors with flexible graph learning and mechanistic principles in deep generative models.Source: B. Bridging communities in graph… · pp. 35, 37
• GSP recovers graph topologies that explain observed signals through assumptions such as smoothness, diffusion, or dynamical evolution, supporting downstream signal processing.Graph topology learning can also be understood as representation learning, with latent spaces encoded by eigenvector bases or graph-dependent dictionaries.Source: B. Bridging communities in graph… · pp. 35–36
• PGMs infer interaction structures through conditional dependencies, yet often yield optimization problems closely related to GSP and dynamical-process approaches.Source: B. Bridging communities in graph… · p. 36
• GML treats graphs primarily as latent variables for representations optimized for predictive or generative tasks, including graph generation for molecule design, simulation, and data augmentation.Many recent graph-generation methods use encoder-decoder models whose latent spaces may be learned from data or predefined by a noise model.Source: B. Bridging communities in graph… · p. 36
• Network science models graph populations through probabilistic mechanisms governing organization, including community structure, degree distributions, motifs, and temporal evolution.Classical random graph models, SBMs, and PA models represent graphs as realizations of mechanisms p(G|Θ), selected according to the target system.Source: B. Bridging communities in graph… · p. 36

• Future formulations jointly model multiple components of the generating process for graph data.Source: §VII · p. 38
• These approaches treat graph topology learning and graph generation as a unified problem rather than separate problems.Source: §VII · p. 38
• Unified models aim to explain how relational systems emerge and evolve.Source: §VII · p. 38

Motivation and representations

• Higher-order interactions motivate extending graph structure learning beyond pairwise graphs to hypergraphs, [175],,, simplicial complexes,,, and cell complexes.Richer geometries include cellular sheaves,,, vector bundles, and product manifolds.Source: A. From graphs with pairwise relations… · p. 38

Learning the representation

• Future algorithms could infer whether pairwise graphs, higher-order complexes, or richer geometries best represent interactions and their associated feature transformations.This treats the relational representation itself as part of the learning problem rather than assuming a graph a priori.Source: A. From graphs with pairwise relations… · p. 38

Generalized learning tasks

• Graph topology learning generalizes from recovering an unknown graph to discovering a broader topological or geometric domain.Graph generation likewise extends from distributions over graphs to distributions over richer representations.Source: A. From graphs with pairwise relations… · p. 38

Broader paradigm

• The unified perspective becomes a special case of learning relational representations directly from data, with the underlying domain geometry inferred rather than prescribed.This reframes both topology learning and graph generation within a broader paradigm.Source: A. From graphs with pairwise relations… · p. 38

• Topology learning, graph generation, and downstream tasks can be unified as components of a common relational data-generating process.Under this view, mechanisms explain how relational structures are formed, evolve, and generate observations.Source: B. From learning a graph structure to… · p. 38
• The graph serves as an intermediate latent representation rather than the final object of learning.Source: B. From learning a graph structure to… · p. 39
• Probabilistic topology learning models observed graphs through latent generating processes, while causal structure learning uses structured search and RL to infer directed-dependency mechanisms.These specialized methods exemplify a shift from estimating connectivity patterns toward explaining the processes that generate relational structures.Source: B. From learning a graph structure to… · p. 39

C. Toward a universal learning paradigm via foundation models

• Foundation models could learn transferable representations and structural priors across heterogeneous graph learning problems.They address methods currently specialized to input data, modeling assumptions, graph domains, and downstream tasks.Source: C. Toward a universal learning… · p. 39
• Large language models have been used to guide causal graph discovery by reducing combinatorial search and incorporating prior knowledge.This exemplifies how foundation models can connect probabilistic learning with semantic and domain knowledge.Source: C. Toward a universal learning… · p. 39
• Foundation models may provide a common interface integrating graph signal processing, graph generation, causal inference, and domain knowledge within unified probabilistic learning.This integration is intended to produce graph learning systems that are more data-efficient and transferable across application domains.Source: C. Toward a universal learning… · p. 39

D. Promising applications

• The most consequential applications may involve systems whose relational structure is latent, time-varying, and directly designable, spanning biological, chemical, social, and urban networks.The paper looks five to ten years ahead when identifying these application opportunities.Source: D. Promising applications · p. 39
• Graph topology learning may evolve toward uncertainty-aware, multiscale inference of changing interactions from streaming observations.Such methods could support self-updating physical infrastructure, industrial processes, autonomous collectives, social networks, and biomedical mechanisms.Source: D. Promising applications · p. 39
• Deep graph generation may move from reproducing observed statistics toward goal-oriented design of proteins, molecular complexes, materials, and network configurations with specified properties,.The designs are intended to satisfy functional and physical properties.Source: D. Promising applications · p. 40
• The most transformative systems may close the loop by inferring relational structure, generating intervention candidates, evaluating them through simulations or experiments, and updating both models from feedback.Existing work jointly learning interaction structure and dynamics and large-scale graph-based forecasting illustrate related opportunities.Source: D. Promising applications · pp. 39–40