GRAPHVQ: STRUCTURE-AWARE AUTOREGRESSIVE DECODING OVER CONTEXT-QUANTIZED GRAPH TOKENS

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 BCEcalibrated 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.4× 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–17× 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.