CS Paper Radar

PolarFlow: Spectral Geometric Flow Matching for Directed Graph Generation via Polar Decomposition

Yanan Zhao, Feng Ji, Alba Carballo-Castro, Jingyang Dai, Antonio Ortega, Pascal Frossard, Wee Peng Tay

eess.SP ·submitted 2026-10-30 09:23 UTC · v1

Abstract

Directed graphs model asymmetric relationships in biology, transportation, social networks, and electronic design automation. Recent discrete diffusion and flow-matching methods generate directed graphs effectively, but their edge-wise categorical formulations require dense predictions over all ordered node pairs and repeated categorical updates during generation. This motivates a fundamental question: can comparable generative quality be achieved through a more computationally efficient formulation that better exploits the structure of directed adjacency matrices? Existing benchmarks also cover limited network structures, restricting comprehensive evaluation. We introduce PolarFlow, a continuous geometric flow-matching framework based on polar decomposition and truncated spectral coordinates. Its representation comprises four coupled components: a Stiefel frame and rotation angles encoding the orthogonal factor, and a second Stiefel frame and nonnegative eigenvalues characterizing the positive-semidefinite factor. PolarFlow learns a joint velocity field along geometry-aware conditional paths on this product space, reconstructs a continuous adjacency-score matrix, and discretizes it into a binary directed graph. By replacing discrete edge-wise generation with joint continuous transport, PolarFlow improves computational efficiency while retaining global adjacency structure. To broaden evaluation, we introduce complementary Circuit and Twitter benchmarks spanning engineered functional and naturally evolved social networks. Across synthetic and real-world datasets, PolarFlow achieves generative quality comparable to competitive discrete methods while substantially reducing training and sampling time.

Closest papers

Nearest neighbours by meaning across the whole index.

Constraint-Preserving Flow Matching for Spectral Graph Generation

cs.LG cs.AI ·2026-11-03 ·Anita Yang, Ken-ichi Kawarabayashi, Yohan Jung
similarity 0.66
Abstract

Spectral graph generation models graphs through the eigenvalues and eigenvectors of their Laplacians, providing a compact and continuous alternative to direct graph construction. However, these eigensystems must retain the structural properties of graph Laplacians. Existing approaches preserve eigenvector orthonormality but do not enforce the Laplacian nullspace constraint, potentially producing eigensystems inconsistent with Laplacian structure. To address this, we introduce Laplacian-Constrained Stiefel Flow Matching (LaSFM), which preserves the nullspace condition alongside eigenvector orthonormality and positive eigenvalues during generation. We characterize the underlying constrained Stiefel manifold and formulate flow matching on it. We further extend LaSFM to property-guided generation, steering samples toward desired graph properties while maintaining these constraints. Experiments demonstrate improved performance on both spectral and graph-level metrics, along with better alignment with target properties.

0.27

Path Laplacian Encodings for Directed Graphs

cs.LG ·2026-10-03 ·Lydia Mezrag, Semih Cantürk, Michael Perlmutter, Bastian Rieck, Guy Wolf
benchmark similarity 0.61
Abstract

Directed graphs naturally model many real-world systems in which interactions are asymmetric, such as citation networks, web graphs, and information-flow networks. However, graph learning methods commonly rely on message passing with symmetrized graph representations or positional encodings that only partially exploit edge directionality. We introduce PathLapPE, a novel spectral positional encoding (PE) derived from the path Laplacian on directed graphs. PathLapPE provides node- and edge-level features that encode directional higher-order structure and can be incorporated into standard graph learning architectures. Empirical results on node- and graph-level benchmark tasks show that PathLapPE yields consistent improvements across several architectures, especially when combined with direction-aware message passing. Compared with magnetic Laplacian positional encodings, a widely studied spectral positional encoding for directed graphs, PathLapPE does not require additional fine-tuning of directionality hyperparameters while offering competitive runtime and performance.

0.16

Alignment Matters Inside and Out in Equivariant Graph Flow Matching

cs.LG math.OCstat.ML ·2026-08-27 ·Moritz Piening, Christian Wald
similarity 0.61
Abstract · Gromov-Wasserstein, Optimal Transport, Flow Matching, Graph Generation, Equivariant Networks

Graphs are invariant under node permutations, motivating permutation-equivariant architectures in generative models. In flow matching, however, symmetry also affects the source-target coupling: one must choose both which graphs to pair and which node representatives to align. We study these two forms of alignment, termed outer and inner alignment, and their effect on equivariant graph flow matching. We connect inner alignment to transport on the graph quotient space, whose Euclidean quotient metric coincides with Gromov-Monge distance, and show that quotient couplings admit aligned representative lifts while symmetrization yields equivariant flow-matching minimizers, including for categorical endpoints. In practice, we compare random augmentation, permutation-blind minibatch optimal transport, approximate Gromov-Wasserstein alignment, and combinations of inner and outer alignment. Across continuous graph and molecular generation, alignment can substantially simplify trajectories and improve few-step generation, while its benefits depend on the alignment and computational budget. Our results highlight that effective graph flow matching benefits from alignment both inside and across graph pairs.

0.37

Latent Flow Matching for Molecular Graph Generation

cs.LG cs.AI ·2026-10-05 ·Mathis Goupillon, Roman Bresson, Konstantinos Divriotis, Michalis Vazirgiannis
similarity 0.59
Abstract

Modern graph generative models typically operate directly in the discrete graph space, explicitly generating node and edge variables, which can become costly as graphs grow. In this paper, we perform generation explicitly on latent representations of entire graphs obtained from a pretrained Variational Autoencoder with high reconstruction fidelity. The generated representations, obtained through flow matching, are then decoded only at the final step. Across molecular benchmarks of increasing size, our approach achieves strong validity and FCD while offering a favorable quality-efficiency trade-off compared with state-of-the-art explicit graph generative models. One of the main advantages of this formulation is that the graph representation only needs to be learned once, after which the same one can be reused across multiple generative objectives without retraining. We demonstrate generation guided by molecular properties and further introduce validity-aware generation though a classifier learned directly in latent space. All code will be made available upon acceptance.

0.21

Efficient Graph Generation via Direct Prediction and Flow Matching

cs.LG ·2026-10-04 ·Susie Lu
published similarity 0.57
Abstract · NeurIPS 2026 Workshop on Geometric Distributional Deep Learning (Oral)

Generative modeling of graph-structured data is crucial for tasks ranging from drug discovery to social network simulation. Among these models, denoising diffusion models have achieved great success in graph generation by learning to progressively reverse a process that adds noise to the original graph. However, the standard noise-prediction approach of diffusion models is suboptimal for graph data. The goal for a graph generative model is to learn the clean graphs' topological properties, such as connectivity and degree distribution. Because a diffusion model that predicts noise does not explicitly learn these topological properties, it is challenging for the model to output graphs with the desired structural statistics. To address this challenge, we introduce Direct Graph Flow Matching (DiGFM), a novel graph transformer model guided by two goals: predict clean graphs and improve sampling efficiency. Distinct from the prevailing diffusion approach, DiGFM employs a continuous flow-matching paradigm and integrates direct graph prediction. Specifically, DiGFM maps the prior noise distribution to the clean graph distribution via a multi-step process: the model repeatedly predicts the underlying clean graph, and a transformation is employed to convert the model output to the velocity vector that points in the direction toward the clean graph distribution. This design enables DiGFM to generate high-quality samples using only 2.5% to 15.6% of the steps required by diffusion-based models, which leads to a 5.3x to 257x speedup in wall-clock inference time. Experiments demonstrate that DiGFM outperforms or matches prior state-of-the-art models across general graph benchmarks and molecular datasets, generating graphs with strong adherence to ground-truth structural statistics at significantly faster inference speeds.

0.34

Trajectory Matching: Discrete Flow Matching with Structured Actions

cs.LG ·2026-10-23 ·Niklas Kemper, Marten Lienen, David Lüdke, Stephan Günnemann
theory similarity 0.56
Abstract

The natural units of structured discrete generation are often not independent single-component edits but richer actions: attaching a fragment to a molecule, inserting a node together with an incident edge, or growing a hierarchy by adding a child. Yet most existing discrete flow matching methods (DFM) are restricted to independent component-wise edits over fixed-size states. This restriction stems from endpoint conditioning: endpoints fix the source and target during training but not the action sequence between them, making tractable conditional rates hard to define for complex actions that cannot be factorized component-wise. We propose trajectory matching, which conditions the flow on a full sequence of actions connecting the endpoints. This yields principled, simulation-free training targets for user-defined action spaces, including actions that change state size, modify multiple components, or depend on earlier actions. We prove that the resulting objective recovers the marginal flow and that trajectory matching strictly subsumes factorized DFM, while additionally capturing actions with prerequisite structure such as hierarchy growth or fragment-based molecule generation. Empirically, on tree and molecular graph generation, trajectory matching with domain-aligned actions matches or surpasses factorized DFM baselines (lifting MOSES validity from 92.8% to 99.2%) and transfers without retraining to substructure extension and linking. Trajectory matching enlarges the design space of discrete flow matching by turning the action vocabulary into a modeling choice. An interactive explanation of trajectory matching is available at https://niklaskemper.com/blog/trajectory-matching/.

0.45

Embedded Graph Flows for Categorical Graph Generation

cs.LG ·2026-09-04 ·Ethan Ma, Zihan Wang, Chris Siu Yeung Chow, Xinguo Feng, Qingqing Li +3 more
code/data similarity 0.55
Abstract

Generating categorical graphs requires choosing node and edge types that form a coherent structure without depending on node order. Many graph generators encode categories as fixed one-hot vectors, which can impose an artificial geometry in which categories are equidistant. We propose Embedded Graph Flows (EGF), a generative model that learns continuous embeddings for node and unordered-edge categories and transports Gaussian noise towards these learnt endpoints using a permutation-equivariant graph transformer. A terminal readout maps the embeddings back to discrete graph categories. Across molecular benchmarks, EGF achieved competitive performance. On QM9, EGF gives the best result on all four reported metrics among the three methods, including a Fréchet ChemNet Distance (FCD) of 0.150, compared with 0.717 for the categorical-diffusion baseline DiGress and 0.812 for the bridge-based baseline GruM. When applied to larger molecules in ZINC250k, EGF retains the lowest maximum mean discrepancy (MMD) using the neighbourhood subgraph pairwise distance kernel (NSPDK), indicating close agreement with the local substructures of the reference molecules. Our code is available at https://github.com/Trusted-System-Lab/EGF.

0.40

High-Resolution Dynamic Functional Connectivity Generation with Graph-Variate Flow Matching

cs.LG ·2026-09-29 ·Om Roy, Yashar Moshfeghi, Keith Malcolm Smith
similarity 0.55
Abstract

High-resolution dynamic functional connectivity (DFC) can reveal rapidly evolving brain-network interactions, but short temporal windows yield noisy, often low-rank covariance estimates. Graph-Variate Dynamic (GVD) connectivity addresses this by modulating fast instantaneous interactions with stable trial-level support. This suppresses spurious fluctuations and emphasizes persistent, informative connections. We show that the Hadamard construction lifts low-rank instantaneous connectivity from the positive-semidefinite to the positive-definite cone, keeping high-resolution trajectories on the SPD manifold without ridge regularisation or post-hoc projection. We introduce GVD-CFM, a class-conditional generative model for high-resolution dynamic connectivity. Each trial is represented as SPD GVD matrices on a product Riemannian manifold, then mapped through a global log-Euclidean diffeomorphism and an invertible temporal DCT basis. A Transformer-based conditional flow models all spectral modes jointly and generates the full trajectory non-autoregressively in Euclidean coordinates while preserving exact correspondence with valid SPD sequences. Retaining the full DCT basis also enables decoding on denser temporal grids without retraining. Across multiple EEG motor-imagery datasets, GVD-CFM delivers the strongest overall results for held-out distributional fidelity, temporal-dynamics preservation, and synthetic-to-real classification. It also remains computationally efficient relative to strong raw-signal and direct GVD-space generative baselines. GVD-CFM therefore provides a practical framework for realistic, temporally coherent, high-resolution brain-network generation with preserved manifold structure and resolution-flexible decoding from a single trained model.

0.26