Weaving Graph over Tokens: Contextualizing Structured Sequences for LLMs

Jiaxuan Chen, Zixing Zhang, Ruijun Mao, Wei Sun, Zhicheng Liang, Yuhang Zhang, Yaxi Liu, Fangxin Wang
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:18337-18357, 2026.

Abstract

Generative Graph Language Models (GLMs) must reconcile topology with causal language modeling. Linearization obscures multi-hop connectivity, while encoder-based methods bottleneck token-level reasoning during generation. Viewing context modeling as a form of message passing, we introduce Weaver, an encoder-free framework that extends the attention mechanism of decoder-only LLMs to enable graph reasoning. Weaver maps graph distances into rotary positional embeddings so that structurally connected nodes become proximate in attention space, propagating information over graph topology as if it were sequential context. To achieve this, we combine: 1) a masking mechanism for causal tokens with graph structures; 2) a unified geometric encoding that couples sequential position and graph distance in joint rotary embeddings (Graph-over-Tokens RoPE); and 3) a design principle to prioritize local information to resolve positional ambiguity under graph symmetries. On zero-shot benchmarks, Weaver achieves state-of-the-art performance among generative GLMs, with gains of up to 30% over prior generative methods on heterophilic graphs, while matching specialized discriminative models on citation networks—all within a unified decoder-only framework.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-chen26gm, title = {Weaving Graph over Tokens: Contextualizing Structured Sequences for {LLM}s}, author = {Chen, Jiaxuan and Zhang, Zixing and Mao, Ruijun and Sun, Wei and Liang, Zhicheng and Zhang, Yuhang and Liu, Yaxi and Wang, Fangxin}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {18337--18357}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/chen26gm/chen26gm.pdf}, url = {https://proceedings.mlr.press/v306/chen26gm.html}, abstract = {Generative Graph Language Models (GLMs) must reconcile topology with causal language modeling. Linearization obscures multi-hop connectivity, while encoder-based methods bottleneck token-level reasoning during generation. Viewing context modeling as a form of message passing, we introduce Weaver, an encoder-free framework that extends the attention mechanism of decoder-only LLMs to enable graph reasoning. Weaver maps graph distances into rotary positional embeddings so that structurally connected nodes become proximate in attention space, propagating information over graph topology as if it were sequential context. To achieve this, we combine: 1) a masking mechanism for causal tokens with graph structures; 2) a unified geometric encoding that couples sequential position and graph distance in joint rotary embeddings (Graph-over-Tokens RoPE); and 3) a design principle to prioritize local information to resolve positional ambiguity under graph symmetries. On zero-shot benchmarks, Weaver achieves state-of-the-art performance among generative GLMs, with gains of up to 30% over prior generative methods on heterophilic graphs, while matching specialized discriminative models on citation networks—all within a unified decoder-only framework.} }
Endnote
%0 Conference Paper %T Weaving Graph over Tokens: Contextualizing Structured Sequences for LLMs %A Jiaxuan Chen %A Zixing Zhang %A Ruijun Mao %A Wei Sun %A Zhicheng Liang %A Yuhang Zhang %A Yaxi Liu %A Fangxin Wang %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-chen26gm %I PMLR %P 18337--18357 %U https://proceedings.mlr.press/v306/chen26gm.html %V 306 %X Generative Graph Language Models (GLMs) must reconcile topology with causal language modeling. Linearization obscures multi-hop connectivity, while encoder-based methods bottleneck token-level reasoning during generation. Viewing context modeling as a form of message passing, we introduce Weaver, an encoder-free framework that extends the attention mechanism of decoder-only LLMs to enable graph reasoning. Weaver maps graph distances into rotary positional embeddings so that structurally connected nodes become proximate in attention space, propagating information over graph topology as if it were sequential context. To achieve this, we combine: 1) a masking mechanism for causal tokens with graph structures; 2) a unified geometric encoding that couples sequential position and graph distance in joint rotary embeddings (Graph-over-Tokens RoPE); and 3) a design principle to prioritize local information to resolve positional ambiguity under graph symmetries. On zero-shot benchmarks, Weaver achieves state-of-the-art performance among generative GLMs, with gains of up to 30% over prior generative methods on heterophilic graphs, while matching specialized discriminative models on citation networks—all within a unified decoder-only framework.
APA
Chen, J., Zhang, Z., Mao, R., Sun, W., Liang, Z., Zhang, Y., Liu, Y. & Wang, F.. (2026). Weaving Graph over Tokens: Contextualizing Structured Sequences for LLMs. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:18337-18357 Available from https://proceedings.mlr.press/v306/chen26gm.html.

Related Material