Graphvq improves graph generation by modeling edge context precisely
GraphVQ: Structure-Aware Autoregressive Decoding over Context-Quantized Graph Tokens
Machine Learning
Summary
Graphs are tricky to generate with computers because connections between points can be complex and hard to predict in one step. The authors created GraphVQ, a method that breaks graphs into smaller, meaningful parts and uses detailed local information about connections to better recreate the whole structure. This approach helps the system recognize patterns and cycles that previous methods missed, leading to more accurate graph generation on several data tests. It shows that focusing on pairs of connected points rather than the entire graph at once can improve graph modeling.
What this means in practice
- •For biotech data teams: Generate realistic protein structure graphs with improved accuracy to aid molecular modeling tasks.
- •For graph algorithm engineers: Build graph generators that better capture complex edge relationships by conditioning on local node pair features.
Authors
Yuxiang Yao, Zijun Zhao
Abstract
Graph foundation models need a discrete token representation, but casting a graph as a generatable token sequence faces a structural obstacle: edges spanning beyond the serialization window cannot be emitted in one pass--so one-pass autoregressive generators systematically under-produce cycles--and a single global condition cannot tell candidate edges apart. GraphVQ removes both obstacles: node contexts--features plus a local edge mask under multi-order breadth-first serialization--are quantized into a shared codebook by a VQ-VAE with BCE-calibrated Bernoulli edge decoding, and a second-stage structure-aware decoder emits the global adjacency conditioned on token-derived pair features, whose necessity over any global-summary condition is formalized in a scoped impossibility result. The tokenizer reconstructs node features at 0.86--0.99 accuracy and decodes local edges at AUROC >= 0.89 (ECE <= 0.007). Under one same-split protocol on four datasets, pair conditioning improves orbit MMD 0.248 -> 0.174 on PROTEINS and 3.4x on a ring stress test, and vanishes on a random-label control--the signature of attribute--topology coupling--so the gain is claimed exactly where attributes carry edge-relevant signal. GraphVQ ranks first among learned generators on PROTEINS, ties for first on SYN-COMM, and improves orbit MMD 2.7--17x over one-stage generation on three datasets, with seed-level bootstrap intervals confirming the rankings are not seed noise; on MUTAG the unweighted edge target under-generates and is reported as such. These results locate the structural control of autoregressive graph generation in the granularity of the condition: pair-level token context turns a quantized vocabulary into a usable capacity axis for distribution-faithful graph generation and future token-level pretraining.