PaperlayerView exact revision on arXiv

Source-linked AI summary

From topology learning to graph generation: A unifying perspective

Xiaowen Dong, Hoi-To Wai, Siheng Chen, Laura Toni, Dorina Thanou

arXiv:2609.02286v1stat.MLcs.LGeess.SP

TL;DR

Graph structure learning must address both recovering an individual topology from observations and learning distributions over graph instances. This review places these tasks in a common two-stage generation process and treats them as inverse problems, using the framework to connect methods and suggest cross-paradigm integration. Its supported conclusion is that the unified view bridges research communities and motivates formulations combining graph and signal generation.

  • Problem

    Graph structure learning research has developed along separate directions for inferring individual graph topologies and learning generative distributions over graph instances.

  • Method

    The review defines graph topology learning and graph generation as inverse problems of successive mappings from parameters to topology and topology to node observations.

  • Results

    The review provides a unified framework that places topology learning and graph generation, including model-based and data-driven formulations, under a common perspective.

  • Takeaways & Limitations

    The framework identifies potential synergies, including combining graph and signal generation and transferring graph signal processing concepts to deep graph generative models.

Abstract

from arXiv · show

Learning graph structures from data is a fundamental problem that spans a wide range of signal processing and machine learning tasks. While significant effort has been made to tackle the problem, existing research has largely evolved along two parallel directions. The first seeks to infer the topology of an individual graph from observations supported on it, whereas the second seeks to learn a generative distribution from observed graph instances, enabling the sampling of new graphs. This review presents a unified framework that connects these formulations by viewing them as inverse problems of a common generation process for graph data. We review the major methodologies within this framework, highlight their relationships, strengths, and limitations, and identify opportunities for integrating ideas across paradigms. By bridging graph topology learning and graph generation, this review provides a broader cross-disciplinary perspective on the field and outlines promising directions for future research.

I. INTRODUCTION

Graph structure learning encompasses inferring an individual graph topology from node observations and learning a distribution over graph instances. The review unifies both problems as inverse problems of a two-stage graph-data generation process and identifies links between model-based and data-driven approaches.

  • Problem instances: Graph structure learning addresses either individual topology inference from node observations or graph generation from sampled graph instances.Topology learning targets the graph underlying observed signals, whereas graph generation learns a distribution over graphs.
  • Unified generation process: The framework models graph data through h: Θ → G, which generates graph topology, followed by f: G → X, which generates node observations.The graph topology may be represented by an adjacency matrix W, while node observations are graph signals such as x.
  • Unified generation process: Topology learning inverts f to infer G from x, while graph generation inverts h to infer θ from observed graph structures.The two learning problems correspond to inverse problems of the respective stages in the common generation process.
  • Approach families: Model-based approaches use known statistical or physical mappings and can provide strong identifiability guarantees, but depend on valid modeling assumptions.Data-driven approaches make fewer prior assumptions and learn implicit mappings directly from data, allowing adaptation to downstream tasks.
  • Approach families: Data-driven graph generation can learn probability distributions rather than only point estimates, but this flexibility reduces interpretability and theoretical guarantees relative to explicit generative models.For graph generation, the distinction concerns whether h is known; unknown mappings can use latent node representations for generation.
  • Opportunities: The review proposes combining stages and transferring methods, including using graph filtering and signal smoothness in deep graph generative models and generative learning for topology inference.It also suggests directly linking graph-parameter space Θ to graph-signal space X through combined mappings.

II. FRAMEWORK

The framework treats graph topology learning and graph generation as inverse problems associated with different stages of a common graph-data generation process. It distinguishes model-based from data-driven learning and extends both problem types to downstream task objectives.

  • Graph generation learns a probabilistic model from observed graph instances so that new graph instances can be generated.
  • The review unifies these problems by associating them with different stages of a shared generation process for graph-related data.
  • Task-driven graph structure learning incorporates labels or specified optimization objectives into the criterion used to learn the graph or generative-model parameters.
  • Model-based approaches assume the signal or graph-generation mapping is known, whereas data-driven approaches learn an unavailable mapping from data.
  • The framework covers probabilistic graphical models, graph signal processing, stochastic block models, and deep graph generative models as representative approaches.
  • Graph topology learning infers a graph G from observed signals x through the inverse of a mapping from G to x.

MLP: MLP

Encoder–decoder methods learn latent graph structures from node observations and use those structures to reconstruct or predict the observations. The review highlights their flexibility for nonlinear dynamics and graph inference without relying on a fixed prototype process.

  • The encoder–decoder framework can capture nonlinear relations between observations and adjacency matrices without relying on a prototype dynamical or filtering process.
  • Explicit DAG inference can impose a DAG constraint while minimizing the ELBO, distinguishing it from approaches using only implicit functional dependence graphs.
  • Encoder–decoder models use node-observation trajectories to infer a latent graph and decode observations conditioned on that graph.
  • The encoder represents edge types between node pairs, while the decoder predicts the observed trajectories given the latent adjacency matrix.
  • Variational encoder–decoder approaches train their parameters by maximizing the evidence lower bound.
  • Ground-truth graphs and node observations can alternatively supervise a mapping that reconstructs causal graphs or networks from new observations.

C. Incorporating domain knowledge in topology learning

Domain knowledge guides topology learning by adding inductive biases and structural constraints. The review contrasts explicit constraints with implicit, data-driven ways of capturing topological properties.

  • Explicit topological constraints: Prior knowledge guides topology-learning optimization toward desirable graph solutions.Topological constraints are motivated by their prevalence in real-world networks and can be encoded in optimization-friendly forms.
  • Explicit topological constraints: Sparsity is a common explicit constraint, promoted through penalties or by directly specifying the desired number of edges.Examples include the ℓ1-norm of a precision matrix, adjacency-matrix regularization, and fixed edge counts.
  • Explicit topological constraints: Structured graph assumptions include Cartesian products, Kronecker products, disconnected components, motif densities, and acyclicity.These constraints encode properties such as factorization, prescribed zero eigenvalues, reference-motif similarity, or DAG structure.
  • Implicit topological constraints: Explicit constraints are mathematically convenient but restrict which topological properties can be represented.Node-degree distributions and local clustering coefficients are harder to encode and have therefore been less studied.
  • Implicit topological constraints: Implicit approaches absorb topology from templates or ground-truth graphs into latent representations, priors, or score functions.These data-driven methods capture desirable properties without necessarily specifying them as explicit feasibility constraints.
  • Implicit topological constraints: The explicit-versus-implicit distinction parallels the review’s model-based-versus-data-driven distinction.Both contrasts describe whether topological knowledge is imposed through designed structure or learned from graph data.

IV. LEARNING GRAPH GENERATION

Graph generation learning estimates distributions over graphs from observed instances or inverts known generation mappings. The section covers classical random-graph models, end-to-end signal-based learning, and newer scalable generative approaches.

  • Problem formulation: Graph-generation learning treats observed graphs as samples from a distribution hG(θ) and estimates the parameter θ.This parameter-estimation perspective supports generating new graph instances after fitting the model.
  • Known graph-generation mappings: The Erdős–Rényi model independently includes each possible edge with probability p, which can be estimated by maximum likelihood.Its estimator is consistent, with bp → p in mean-square sense as m → ∞.
  • Known graph-generation mappings: The β-model represents heterogeneous degrees through node-specific parameters, while preferential attachment models power-law degree distributions.Both provide parameterized generation mechanisms whose parameters can be estimated from observed graphs.
  • Known graph-generation mappings: Exponential random graph models use sufficient statistics such as edges, triangles, or subgraph counts to parameterize graph distributions.Their maximum-likelihood estimation is challenging because the partition function Z(θ) is intractable, though consistency holds under certain conditions.
  • End-to-end learning: When the signal-generation mapping is known, end-to-end learning can invert the composite function fX ◦ hG without separately inverting fX.The reviewed examples infer node centrality under low-pass filtering and heterogeneous-degree assumptions.
  • Modern generative approaches: Recent methods combine hierarchical growth with local diffusion, use decoder-only Transformers, or replace diffusion with flow matching.Reported benefits include generation at several-thousand-node scale, extrapolation to unseen sizes, and competitive quality with fewer sampling steps.
  • Modern generative approaches: Diffusion models typically require a large number of sampling steps, creating a practical limitation despite their empirical success.This motivates alternatives such as flow matching and more scalable generation procedures.
  • Modern generative approaches: Posterior-oriented methods can sample multiple plausible graphs rather than returning one estimate, supporting uncertainty quantification and Bayesian model averaging.GFlowNets amortize sampling with a reusable policy while maintaining sample diversity.

C. Incorporating domain knowledge in graph generation

Domain knowledge can constrain graph-generation models through hard support restrictions or implicit distributional learning. These approaches trade explicit validity guarantees against flexibility and data-driven expressiveness.

  • Hard constraints: Hard constraints restrict the support of a learned graph distribution to admissible graphs.They can enforce structural families such as planarity or acyclicity during generation.
  • Hard constraints: Projection-based methods impose hard requirements during sampling without retraining the underlying generative model.PRODIGY projects intermediate graph representations toward a user-specified constrained space at each sampling step.
  • Implicit constraints: Implicit approaches absorb topological properties from observed graph samples into generative-model parameters or latent representations.They avoid explicit feasibility sets or topology-specific penalties.
  • Implicit constraints: NetGAN reproduces degree, community, and motif statistics by learning random-walk distributions rather than explicitly specifying those properties.GraphRNN and GRAN use sequential construction decisions, whereas SPECTRE models spectral representations encoding global structure.
  • Trade-offs: Distributional validity does not guarantee that every generated sample satisfies the properties present in the training data.This distinguishes implicit approaches from projection-based methods that impose constraints during generation.

V. TASK-DRIVEN GRAPH STRUCTURE LEARNING

Task-driven graph structure learning uses downstream objectives as additional supervision for learning graph topologies. The review describes supervised prediction and latent-state formulations, often yielding nested optimization problems.

  • General formulation: Task-driven learning treats the graph as an intermediate representation optimized for downstream utility rather than solely for explaining observations.The downstream objective adds supervision and can jointly influence graph learning and the downstream model.
  • Interpretation and limitations: Task-driven learning introduces supervision beyond simply inverting the graph-generation mappings.Its implicit bias can correspond to explicit properties such as heterogeneity in node degrees, bridging implicit and explicit priors.
  • General formulation: Joint graph and downstream-model learning commonly produces a nested optimization problem.The graph is updated using the downstream objective while the downstream model is learned on the current graph.
  • Supervised graph neural networks: For supervised graph neural networks, the upper-level objective evaluates validation performance and the lower-level objective minimizes training loss.The GNN can be replaced by another graph machine-learning model.
  • Supervised graph neural networks: Task-driven topology learning has been formulated with bilevel and penalized bilevel optimization, supported by hypergradient- and penalty-based algorithms.These methods target graph structures that improve downstream GNN performance.
  • Latent states: Latent-state formulations represent downstream outputs such as denoising, sampling-set selection, or equilibrium states and incorporate them into topology objectives.The task mapping is typically assumed known and depends on the application.
  • Latent states: Exploiting task structure can make a single-level formulation sufficient to approximately incorporate the downstream task.Examples include graph signal clustering, representation learning for classification, and sampling-set selection.
  • Interpretation and limitations: Methods for unknown dynamics remain relatively scarce, and the interplay between topology learning and downstream tasks remains insufficiently understood.The review characterizes research in this direction as still in its infancy.

VI. BRIDGING TOPOLOGY LEARNING WITH GRAPH GENERATION

Topology learning and graph generation share fundamental characteristics despite being discussed separately, and recognizing these commonalities supports a higher-level synthesis and bridges between them.

  • Topology learning and graph generation have traditionally evolved as distinct research directions.
  • The two problems share several fundamental characteristics that support a unified perspective.
  • Recognizing their commonalities may inspire new formulations and methodologies.
  • Recent developments begin to bridge the two traditionally separate directions.

A. A unified generating process for graph data

The review places topology learning and graph generation within one hierarchy: latent parameters generate graph structure, which produces observations through an observation process. Each field typically recovers one stage, while recent work combines them.

  • Topology learning recovers latent graph structure from node observations by modeling the observation process f_X.Under assumptions such as smoothness, dynamical processes, or graph filtering, the learned graph can also identify the mechanism governing observed signals.
  • Graph generation learns a probability distribution over graphs rather than estimating a single graph, enabling synthesis of previously unseen graphs with similar statistical and structural properties.
  • A unified hierarchy represents topology learning and graph generation as complementary components of one graph-data generation process.Topology learning focuses on G-to-X mappings, while graph generation focuses on Θ-to-G mappings.
  • Latent generative parameters first determine graph structure, which then produces graph observations through statistical, physical, or filtering processes.
  • Existing methods typically recover only one stage and therefore do not fully model the mechanism responsible for observed graph data.
  • Recent work bridges the stages by combining topology learning with graph formation parameters or by extending generation to graph-supported observations.Examples include graph deconvolution, joint topology and parameter learning, and graph-aware generative models.
  • Methodological transfer can inform graph generation with topology-learning models and extend topology learning with probabilistic structural models.

B. Bridging communities in graph structure learning

Graph structure learning spans communities that study interactions, representations, graph populations, and generative mechanisms at different abstraction levels. The unified process reveals complementary problems and opportunities to transfer priors, flexibility, and mechanistic principles.

  • Graph structure learning has developed across research communities including PGMs, GSP, GML, and network science.
  • The communities differ mainly in abstraction level but address complementary learning problems defined on components of the same generating process.
  • GSP: GSP approaches often recover graphs from signals under smoothness, diffusion, or dynamical-process assumptions.The learned graph is expected to reflect meaningful variable interactions and support downstream signal processing.
  • GSP: Graph topology learning can be understood as representation learning when signal models use latent spaces or bases associated with the learned graph.
  • PGMs and GSP: PGMs and GSP can yield closely related optimization problems despite differing modeling assumptions, with both expressing node-pair relationships through unified graph interpretations.
  • GML: GML learns representations and graph structures for downstream predictive or generative objectives, including graph generation and data augmentation.
  • Network science: Network science models graph populations through probabilistic mechanisms explaining structural properties such as communities, degree distributions, motifs, and temporal evolution.Examples include ER, SBM, and PA models selected for different network contexts.
  • These connections create opportunities to combine physically grounded graph priors with GML flexibility and enrich deep generators with network-science mechanisms.

VII. FUTURE PERSPECTIVES

The unified perspective motivates graph structure learning formulations that jointly model multiple components of the generating process. Future approaches may explain how relational systems emerge and evolve rather than treating topology learning and graph generation separately.

  • The review motivates a new generation of graph structure learning formulations that jointly model multiple components of graph-data generation.
  • These formulations treat topology learning and graph generation as parts of unified models rather than separate problems.
  • Future systems may explain how relational systems emerge and evolve.

A. From graphs with pairwise relations to higher-order structures and richer geometries

The review extends graph structure learning beyond pairwise graphs toward higher-order structures and richer geometries. Its unified perspective treats the relational representation and underlying domain geometry as objects that can be inferred from data.

  • Real-world interactions may not be adequately captured by pairwise relationships, motivating structure learning over higher-order relational representations.
  • Candidate representations include hypergraphs, simplicial complexes, cell complexes, cellular sheaves, vector bundles, and product manifolds.
  • Future systems may treat the choice of relational representation itself as part of the learning problem rather than assuming it a priori.
  • Topology learning can generalize from recovering an unknown graph to discovering a general topological or geometric domain.
  • Graph generation can likewise extend from distributions over graphs to distributions over richer relational representations.
  • The review frames this evolution as learning relational representations directly from data when the underlying domain geometry is inferred rather than prescribed.

B. From learning a graph structure to learning a generating process

The review proposes viewing topology learning, graph generation, and downstream tasks as complementary components of a common relational data-generating process. This shifts emphasis from estimating structures toward explaining how relational structures are generated and evolve.

  • Topology learning, graph generation, and downstream tasks could be treated as complementary components of a common relational data-generating process.
  • A holistic approach could illuminate how relational structures are formed, evolve, and generate observations.
  • Under this perspective, the graph is an intermediate latent representation rather than the final object of learning.
  • Probabilistic topology learning and causal structure learning are emerging examples of methods that reason about latent graph-generating processes and directed dependencies.
  • Although early methods remain specialized, they illustrate a shift from estimating relational structures toward explaining the processes that generate them.

C. Toward a universal learning paradigm via foundation models

The review points toward generalist and foundation-model-based systems that combine probabilistic learning, semantic and domain knowledge, and transferable structural priors. It also envisions graph learning systems that infer changing relational structure and design candidate structures in closed-loop workflows.

  • Toward universal learning systems: Existing methods are typically designed for specific inputs, assumptions, graph domains, or downstream tasks, motivating generalist models for heterogeneous graph problems.
  • Toward universal learning systems: Foundation models may provide a common interface for combining graph signal processing, graph generative models, causal inference, and domain knowledge.
  • Toward universal learning systems: A unified probabilistic framework combining causal inference and domain knowledge is described as enabling more data-efficient and transferable graph learning systems.
  • Dynamic and design-oriented applications: The review identifies latent, time-varying, and directly designable relational structure as a setting for consequential future applications.
  • Dynamic and design-oriented applications: Graph topology learning may progress toward uncertainty-aware, multiscale inference of changing interactions from streaming observations.
  • Dynamic and design-oriented applications: Graph generation may move beyond reproducing observed statistics toward designing proteins, molecular complexes, materials, and network configurations with specified properties.
  • Dynamic and design-oriented applications: A transformative closed loop would infer relational structure, generate candidate intervention structures, evaluate them through simulation or experiment, and update models from feedback.
Loading 2609.02286v1…