A Non-Asymptotic Convergent Analysis for Scored-Based Graph Generative Model via a System of Stochastic Differential Equations

• URL: http://arxiv.org/abs/2508.14351v1
• Date: Wed, 20 Aug 2025 01:44:42 GMT
• Title: A Non-Asymptotic Convergent Analysis for Scored-Based Graph Generative Model via a System of Stochastic Differential Equations
• Authors: Junwei Su, Chuan Wu,
• Abstract summary: We present the first non-asymptotic convergence analysis for Score-based graph generative models (SGGMs)<n>Our analysis reveals several unique factors specific to SGGMs which affect the convergence bound.<n>This work deepens the theoretical understanding of SGGMs, demonstrates their applicability in critical domains, and provides practical guidance for designing effective models.
• Score: 6.598758004828656
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Score-based graph generative models (SGGMs) have proven effective in critical applications such as drug discovery and protein synthesis. However, their theoretical behavior, particularly regarding convergence, remains underexplored. Unlike common score-based generative models (SGMs), which are governed by a single stochastic differential equation (SDE), SGGMs involve a system of coupled SDEs. In SGGMs, the graph structure and node features are governed by separate but interdependent SDEs. This distinction makes existing convergence analyses from SGMs inapplicable for SGGMs. In this work, we present the first non-asymptotic convergence analysis for SGGMs, focusing on the convergence bound (the risk of generative error) across three key graph generation paradigms: (1) feature generation with a fixed graph structure, (2) graph structure generation with fixed node features, and (3) joint generation of both graph structure and node features. Our analysis reveals several unique factors specific to SGGMs (e.g., the topological properties of the graph structure) which affect the convergence bound. Additionally, we offer theoretical insights into the selection of hyperparameters (e.g., sampling steps and diffusion length) and advocate for techniques like normalization to improve convergence. To validate our theoretical findings, we conduct a controlled empirical study using synthetic graph models, and the results align with our theoretical predictions. This work deepens the theoretical understanding of SGGMs, demonstrates their applicability in critical domains, and provides practical guidance for designing effective models.

Related papers

• A Theory of Random Graph Shift in Truncated-Spectrum vRKHS [26.195791008324495]
  This paper develops a theory of graph classification under domain shift through a random-graph generative lens.<n>We consider intra-class graphs sharing the same random graph model (RGM) and the domain shift induced by changes in RGM components.
  arXiv  Detail & Related papers  (2026-02-27T10:19:57Z)
• Simplicial Gaussian Models: Representation and Inference [13.687470962704744]
  We propose the simplicial Gaussian model (SGM), which extends Gaussian PGM to simplicial complexes.<n>Our model builds upon discrete Hodge theory and incorporates uncertainty at every topological level through independent random components.<n>Motivated by applications, we focus on the marginal edge-level distribution while treating node- and triangle-level variables as latent.
  arXiv  Detail & Related papers  (2025-10-14T20:51:56Z)
• Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs [53.27010448621372]
  We analyze the universality and generalization of graph neural networks (GNNs) on attributed graphs with node attributes.<n>We prove a universal approximation theorem for GNNs and bounds generalization for GNNs on any data distribution of attributed graphs.<n>Our work extends and unites previous approaches which either derived theory only for graphs with no attributes, derived compact metrics under which GNNs are continuous but without separation power, or derived metrics under which GNNs are continuous and separate points.
  arXiv  Detail & Related papers  (2024-11-08T10:34:24Z)
• Greedy equivalence search for nonparametric graphical models [13.153623397411605]
  GES is known to consistently estimate the structure of directed acyclic graph (DAG) models. A general theory that covers general nonparametric DAG models, however, is missing. Here, we establish the consistency of greedy equivalence search for general families of DAG models that satisfy smoothness conditions on the Markov factorization.
  arXiv  Detail & Related papers  (2024-06-25T02:31:32Z)
• Generalization of Graph Neural Networks through the Lens of Homomorphism [7.223313563198697]
  We propose to study the generalization of Graph Neural Networks (GNNs) through a novel perspective - analyzing the entropy of graph homomorphism. By linking graph homomorphism with information-theoretic measures, we derive generalization bounds for both graph and node classifications. These bounds are capable of capturing subtleties inherent in various graph structures, including but not limited to paths, cycles and cliques.
  arXiv  Detail & Related papers  (2024-03-10T03:51:59Z)
• Histopathology Whole Slide Image Analysis with Heterogeneous Graph Representation Learning [78.49090351193269]
  We propose a novel graph-based framework to leverage the inter-relationships among different types of nuclei for WSI analysis. Specifically, we formulate the WSI as a heterogeneous graph with "nucleus-type" attribute to each node and a semantic attribute similarity to each edge. Our framework outperforms the state-of-the-art methods with considerable margins on various tasks.
  arXiv  Detail & Related papers  (2023-07-09T14:43:40Z)
• Granger causal inference on DAGs identifies genomic loci regulating transcription [77.58911272503771]
  GrID-Net is a framework based on graph neural networks with lagged message passing for Granger causal inference on DAG-structured systems. Our application is the analysis of single-cell multimodal data to identify genomic loci that mediate the regulation of specific genes.
  arXiv  Detail & Related papers  (2022-10-18T21:15:10Z)
• Heterogeneous Graph Neural Networks using Self-supervised Reciprocally Contrastive Learning [102.9138736545956]
  Heterogeneous graph neural network (HGNN) is a very popular technique for the modeling and analysis of heterogeneous graphs. We develop for the first time a novel and robust heterogeneous graph contrastive learning approach, namely HGCL, which introduces two views on respective guidance of node attributes and graph topologies. In this new approach, we adopt distinct but most suitable attribute and topology fusion mechanisms in the two views, which are conducive to mining relevant information in attributes and topologies separately.
  arXiv  Detail & Related papers  (2022-04-30T12:57:02Z)
• BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery [97.79015388276483]
  A structural equation model (SEM) is an effective framework to reason over causal relationships represented via a directed acyclic graph (DAG) Recent advances enabled effective maximum-likelihood point estimation of DAGs from observational data. We propose BCD Nets, a variational framework for estimating a distribution over DAGs characterizing a linear-Gaussian SEM.
  arXiv  Detail & Related papers  (2021-12-06T03:35:21Z)
• Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
  Graph auto-encoder (GAE) models are based on semi-supervised graph convolution networks (GCN) We design a specific GAE-based model for graph clustering to be consistent with the theory, namely Embedding Graph Auto-Encoder (EGAE) EGAE consists of one encoder and dual decoders.
  arXiv  Detail & Related papers  (2020-02-20T09:53:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.