LGDC: Latent Graph Diffusion via Spectrum-Preserving Coarsening

AI summary

Overview

Research area: Generative modeling for graphs — specifically, the comparison and combination of autoregressive and one-shot (diffusion/flow) graph generation paradigms.

Technical level: Advanced. The paper assumes familiarity with graph Laplacians, discrete diffusion processes, spectral graph theory, and graph coarsening.

Scope: The paper analyzes the local-versus-global trade-off between autoregressive and one-shot graph generators, then proposes LGDC, a hybrid that diffuses over a spectrum-preserving coarsened graph and decodes back to full resolution in a single expansion–refinement pass.

What This Paper Is About

Graph generation methods split into two families: autoregressive models that grow a graph node by node, and one-shot models such as diffusion that produce the entire graph at once. The authors first run a controlled comparison showing that autoregressive methods win on locally structured data while one-shot methods win on globally structured data, then ask whether the two strengths can be merged. LGDC answers this by running diffusion in a smaller, spectrally faithful latent graph and restoring fine detail with one coarse-to-fine expansion step.

Key Contributions

1. A systematic comparison of the two paradigms. The authors characterize autoregressive models as strong on fine-grained local structure (degree, clustering, motifs) and one-shot models as strong on global structure (spectral distributions, community organization), supported by dataset statistics (Table 1) and a benchmark comparison with training-time tricks disabled for fairness (Table 2).

2. The LGDC hybrid framework. A unified pipeline that (i) coarsens a graph with spectrum-preserving coarsening, (ii) runs discrete diffusion in the coarsened latent space, and (iii) decodes back to the original size with a single expansion–refinement step, jointly optimizing the latent diffusion model p_theta(G_c) and the expansion model p_phi(G | G_c).

3. Empirical validation across structural regimes. LGDC reaches a V.U.N. of 86.0 on Tree (above the autoregressive HSpectre at 82.5) and 82.5 on Planar (above HSpectre at 62.5 and DeFoG at 77.5), and reports lower degree, clustering and orbit discrepancies than DeFoG on Community-20 (0.037 vs 0.071, 0.027 vs 0.115, 0.007 vs 0.037).

4. A complexity reduction. LGDC's sampling cost is stated as O(n² + T·n_c²), compared with O(T·n²) for one-shot models and O(T·n²/3) for autoregressive models, with savings growing as the compression ratio n_c/n shrinks.

Main Findings

• The local–global trade-off is real. Table 2 shows autoregressive HSpectre reaching V.U.N. 82.5 / A.Ratio 2.1 on Tree while one-shot DeFoG reaches 77.5 / 3.5 on Planar and 85.0 / 3.7 on SBM. Dataset statistics in Table 1 show Tree dominated by local metrics and Planar/SBM exhibiting global organization in spectral and connectivity statistics.

• LGDC is competitive on both ends. On Tree it records V.U.N. 86.0 ± 2.0 and A.Ratio 1.70; on Planar V.U.N. 82.5 ± 2.7 and A.Ratio 3.06; on Community-20 it achieves the lowest local discrepancies among the reported methods.

• Expansion restores local detail while preserving global structure. On Planar, degree error falls from 0.0016 ± 0.0005 to 0.0006 ± 0.0001 and motif error from 0.0697 ± 0.0131 to 0.0079 ± 0.0030, while spectral distance changes only from 0.0126 ± 0.0021 to 0.0090 ± 0.0011. On Tree, degree error falls from 0.0005 ± 0.0003 to 0.0002 ± 0.0002 and spectral distance from 0.0085 ± 0.0012 to 0.0078 ± 0.0009.

• Wavelet (multi-scale) distance improves after expansion. Tree: 0.0078 ± 0.0004 to 0.0041 ± 0.0003. Planar: 0.0089 ± 0.0008 to 0.0063 ± 0.0005. On Community-20, the reported wavelet distance rises from 0.0410 ± 0.0166 to 0.1175 ± 0.0061, and spectral distance rises from 0.0457 ± 0.0175 to 0.1431 ± 0.0084.

• Expansion is not uniformly beneficial in the reported tables. For Tree, Local Ratio improves from 4.22 ± 3.11 to 0.86 ± 0.52, but Global Ratio worsens from 1.79 ± 0.63 to 2.21 ± 0.31 (driven by diameter moving from 0.0249 ± 0.0120 to 0.0789 ± 0.0202). For Planar, both Local Ratio (4.81 ± 1.52 to 19.88 ± 3.51) and Global Ratio (9.03 ± 6.81 to 19.46 ± 7.34) increase.

• Validity and diversity remain high. V.U.N. stays above 80 in all reported cases; it drops from 97.5 ± 1.58 to 86.0 ± 2.0 on Tree and from 100.0 ± 0.0 to 82.5 ± 2.74 on Planar after expansion. Community-20 V.U.N. is not reported.

• A single inversion step replaces many. Unlike HSpectre's multiple expansion–refinement cycles (1 → 3 → 8 → ... → n), LGDC performs one coarse-to-fine inversion from n_c to n at training and testing. The setup fixes n_c ≈ n/5, with M = 16 for Tree and Planar and M = 4 for Community-20.

Methodology in Plain English

The pipeline runs in four moves. First, a fine graph is compressed with Randomized Edge Contraction, a non-learning procedure chosen so the coarse graph's Laplacian eigenvalues and eigenspaces stay close to the original — formalized as a restricted spectral similarity bound on the trace of XᵀLX. This matters because those spectral quantities encode connectivity, community structure and planarity, so the small graph is a faithful stand-in for global shape.

Second, a discrete diffusion model in the style of DiGress (permutation-equivariant graph transformer, factorized node-feature and adjacency transition distributions, cross-entropy reconstruction loss) is trained to generate these small latent graphs. Running diffusion here rather than on the full graph is what makes global modeling cheap.

Third, a decoarsening model learns to invert a single coarsening step. It predicts a node expansion vector v (how many fine nodes each coarse node becomes) and an edge-selection mask e over a candidate edge set built from intra-cluster and inter-cluster candidates; supervised pairs (v*, e*) come from inverting one coarsening step. Since G is determined by (v, e), the conditional model factorizes accordingly and is trained with the expansion–refinement objective of Bergmeister et al. (2024) applied to a single coarse-to-fine transition.

At test time, the model samples a latent graph via reverse diffusion, then expands and prunes in one pass to produce the final graph.

Why This Matters

Impact on research. The paper reframes a practical rivalry as a structural complementarity: local and global graph statistics are not in conflict, and a latent-space design can address both. It also opens a non-Euclidean latent-diffusion direction, since prior latent graph diffusion work (Yang et al. 2024, Zhou et al. 2024) embeds graphs into Euclidean vectors rather than reducing node count.

Real-world applications (the domains the paper cites as motivation for graph generation):

• Drug discovery and molecular design, where valid and novel molecular graphs are the target.
• Social network modeling, where community structure matters at the global scale while individual ties matter locally.
• Any setting needing synthetic graphs with controlled global organization, such as community-structured data for benchmarking or simulation.

Industry relevance. The complexity argument is the commercial hook: at O(n² + T·n_c²) instead of O(T·n²), the savings grow with compression ratio, and the authors note T typically exceeds n in graph generation. One co-author is affiliated with MediaTek Research, and the single-pass decoder is positioned as a practical substitute for multi-round expansion. Real-world deployment is not demonstrated, since the experiments use synthetic benchmarks.

Future Directions

• Iterative or uncertainty-aware refinement to stop small edge-mask errors from propagating when the candidate edge set is large, which the authors identify as the main decoding failure mode.
• Sparse or structured expansion to address the O(n²) dense worst-case cost that still makes very large graphs hard to handle.
• Adaptive or learned spectrum-preserving coarsening, since results depend on the chosen projection matrix and compression ratio, and different coarsenings produce different cluster structures and reconstruction difficulty.
• Explicit global constraints and richer data. The current refinement does not enforce planarity or connectivity, and the paper suggests extending LGDC to richer node and edge attributes and larger heterogeneous graphs beyond the synthetic benchmarks used here.

Target Audience

Researchers and graduate students working on generative models for graphs, spectral graph theory, or hierarchical/latent diffusion. The paper is most useful to readers already comfortable with discrete diffusion and graph Laplacians who want a principled way to trade full-resolution computation for a spectrally faithful latent space; practitioners focused on molecular or social-network generation will find the complexity argument and the honest limitation section useful for judging whether the hybrid is worth adopting.

Authors’ abstract

Graph generation is a critical task across scientific domains. Existing methods fall broadly into two categories: autoregressive models, which iteratively expand graphs, and one-shot models, such as diffusion, which generate the full graph at once. In this work, we provide an analysis of these two paradigms and reveal a key trade-off: autoregressive models stand out in capturing fine-grained local structures, such as degree and clustering properties, whereas one-shot models excel at modeling global patterns, such as spectral distributions. Building on this, we propose LGDC (latent graph diffusion via spectrum-preserving coarsening), a hybrid framework that combines strengths of both approaches. LGDC employs a spectrum-preserving coarsening-decoarsening to bidirectionally map between graphs and a latent space, where diffusion efficiently generates latent graphs before expansion restores detail. This design captures both local and global properties with improved efficiency. Empirically, LGDC matches autoregressive models on locally structured datasets (Tree) and diffusion models on globally structured ones (Planar, Community-20), validating the benefits of hybrid generation.