Principled Latent Diffusion for Graphs via Laplacian Autoencoders

• URL: http://arxiv.org/abs/2601.13780v1
• Date: Tue, 20 Jan 2026 09:37:53 GMT
• Title: Principled Latent Diffusion for Graphs via Laplacian Autoencoders
• Authors: Antoine Siraudin, Christopher Morris,
• Abstract summary: LG-Flow is a latent graph diffusion framework.<n>A permutation-equivariant autoencoder maps each node into a fixed-dimensional embedding from which the full adjacency is provably recoverable.<n>Our approach achieves competitive results against state-of-the-art graph diffusion models, while achieving up to $1000times$ speed-up.
• Score: 9.238565851133602
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph diffusion models achieve state-of-the-art performance in graph generation but suffer from quadratic complexity in the number of nodes -- and much of their capacity is wasted modeling the absence of edges in sparse graphs. Inspired by latent diffusion in other modalities, a natural idea is to compress graphs into a low-dimensional latent space and perform diffusion there. However, unlike images or text, graph generation requires nearly lossless reconstruction, as even a single error in decoding an adjacency matrix can render the entire sample invalid. This challenge has remained largely unaddressed. We propose LG-Flow, a latent graph diffusion framework that directly overcomes these obstacles. A permutation-equivariant autoencoder maps each node into a fixed-dimensional embedding from which the full adjacency is provably recoverable, enabling near-lossless reconstruction for both undirected graphs and DAGs. The dimensionality of this latent representation scales linearly with the number of nodes, eliminating the quadratic bottleneck and making it feasible to train larger and more expressive models. In this latent space, we train a Diffusion Transformer with flow matching, enabling efficient and expressive graph generation. Our approach achieves competitive results against state-of-the-art graph diffusion models, while achieving up to $1000\times$ speed-up.

Related papers

• Diffusion-Free Graph Generation with Next-Scale Prediction [3.505533791554976]
  We propose a novel diffusion-free graph generation framework based on next-scale prediction.<n>By leveraging a hierarchy of latent representations, the model progressively generates scales of the entire graph without the need for explicit node ordering.<n>Experiments on both generic and molecular graph datasets demonstrated the potential of this method, achieving inference speedups of up to three orders of magnitude over state-of-the-art methods.
  arXiv  Detail & Related papers  (2025-03-30T22:30:34Z)
• Random Walk Diffusion for Efficient Large-Scale Graph Generation [0.43108040967674194]
  We propose ARROW-Diff (AutoRegressive RandOm Walk Diffusion), a novel random walk-based diffusion approach for efficient large-scale graph generation.<n>We demonstrate that ARROW-Diff can scale to large graphs efficiently, surpassing other baseline methods in terms of both generation time and multiple graph statistics.
  arXiv  Detail & Related papers  (2024-08-08T13:42:18Z)
• Advancing Graph Generation through Beta Diffusion [49.49740940068255]
  Graph Beta Diffusion (GBD) is a generative model specifically designed to handle the diverse nature of graph data. We propose a modulation technique that enhances the realism of generated graphs by stabilizing critical graph topology.
  arXiv  Detail & Related papers  (2024-06-13T17:42:57Z)
• Input Snapshots Fusion for Scalable Discrete-Time Dynamic Graph Neural Networks [27.616083395612595]
  We propose SFDyG, which combines Hawkes processes with graph neural networks to capture temporal and structural patterns in dynamic graphs effectively.<n>By fusing multiple snapshots into a single temporal graph, SFDyG decouples computational complexity from the number of snapshots, enabling efficient full-batch and mini-batch training.
  arXiv  Detail & Related papers  (2024-05-11T10:05:55Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• Leveraging Graph Diffusion Models for Network Refinement Tasks [72.54590628084178]
  We propose a novel graph generative framework, SGDM, based on subgraph diffusion. Our framework not only improves the scalability and fidelity of graph diffusion models, but also leverages the reverse process to perform novel, conditional generation tasks.
  arXiv  Detail & Related papers  (2023-11-29T18:02:29Z)
• Sparse Training of Discrete Diffusion Models for Graph Generation [45.103518022696996]
  We introduce SparseDiff, a novel diffusion model based on the observation that almost all large graphs are sparse. By selecting a subset of edges, SparseDiff effectively leverages sparse graph representations both during the noising process and within the denoising network. Our model demonstrates state-of-the-art performance across multiple metrics on both small and large datasets.
  arXiv  Detail & Related papers  (2023-11-03T16:50:26Z)
• Supercharging Graph Transformers with Advective Diffusion [28.40109111316014]
  This paper proposes Advective Diffusion Transformer (AdvDIFFormer), a physics-inspired graph Transformer model designed to address this challenge.<n>We show that AdvDIFFormer has provable capability for controlling generalization error with topological shifts.<n> Empirically, the model demonstrates superiority in various predictive tasks across information networks, molecular screening and protein interactions.
  arXiv  Detail & Related papers  (2023-10-10T08:40:47Z)
• Autoregressive Diffusion Model for Graph Generation [12.390149720274904]
  We propose an emphautoregressive diffusion model for graph generation. Unlike existing methods, we define a node-absorbing diffusion process that operates directly in the discrete graph space. Our experiments on six diverse generic graph datasets and two molecule datasets show that our model achieves better or comparable generation performance with previous state-of-the-art.
  arXiv  Detail & Related papers  (2023-07-17T21:21:18Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling [20.618785908770356]
  Diffusion-based generative graph models have been proven effective in generating high-quality small graphs. However, they need to be more scalable for generating large graphs containing thousands of nodes desiring graph statistics. We propose EDGE, a new diffusion-based generative graph model that addresses generative tasks with large graphs.
  arXiv  Detail & Related papers  (2023-05-06T18:32:27Z)
• Graph Generation with Diffusion Mixture [57.78958552860948]
  Generation of graphs is a major challenge for real-world tasks that require understanding the complex nature of their non-Euclidean structures. We propose a generative framework that models the topology of graphs by explicitly learning the final graph structures of the diffusion process.
  arXiv  Detail & Related papers  (2023-02-07T17:07:46Z)
• Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations [57.15855198512551]
  We propose a novel score-based generative model for graphs with a continuous-time framework. We show that our method is able to generate molecules that lie close to the training distribution yet do not violate the chemical valency rule.
  arXiv  Detail & Related papers  (2022-02-05T08:21:04Z)
• FeatureNorm: L2 Feature Normalization for Dynamic Graph Embedding [39.527059564775094]
  Graph convolutional network (GCN) has been widely explored and used in non-Euclidean application domains. In this paper, we analyze the shrinking properties in the node embedding space at first, and then design a simple yet versatile method. Experiments on four real-world dynamic graph datasets compared with competitive baseline models demonstrate the effectiveness of the proposed method.
  arXiv  Detail & Related papers  (2021-02-27T09:13:47Z)

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.