[Paper] Graph Machine: Exploring Edge Mechanisms as an Inductive Bias
Overview
Abstract
Transformers provide a powerful architecture for global content-based matching, but reasoning problems may benefit from a stronger inductive bias toward iterative traversal of latent relations. We introduce Graph Machine, an architecture with two explicit edge-based mechanisms: Edge-augmented attention, in which edges modulate attention between nodes, and edge-centric referral, in which nodes exchange addresses to update their edges. Conceptually, this enables the model to dynamically and differentiably construct and revise relational graphs across layers. We study this inductive bias using Sudoku under controlled settings and find that Graph Machine outperforms Transformer baselines, with ablation studies and mechanistic analysis attributing the gains to the edge mechanisms. Surprisingly, we found that the model discovers a compact edge-based construction for Sudoku geometry. Our results support explicit edge mechanisms as a promising architectural design, motivating broader evaluation.
Selected figures
Figure 1. GM representations.
Figure 2. GM layers.
Figure 3. GM edge sublayer.
Figure 4. GM node sublayer.
Figure 5. Edge-augmented attention tensor operations (1 head).
Figure 6. Edge-centric referral tensor operations (1 head).
Figure 8. GM-0 constructs edges representing constraint regions in early layers.
Figure 9. GM-0 composes existing regions through self-referral to produce more complex regions.
Figure 16. GM-0 applies the 1-2-4 construction broadly, including in cells that are not middle-of-row/column.
Figure 10. GM-0's edges are input-adaptive (excerpt).
Figure 11. GM-0's edge and node factors specialize in relational and content-based roles, respectively (excerpt).
Paper
Citation
Text
Hou, Lintai. "Graph Machine: Exploring Edge Mechanisms as an Inductive Bias". arXiv preprint arXiv:2608.06834 (2026). https://arxiv.org/abs/2608.06834BibTeX
@misc{hou2026gm1,
title = {Graph Machine: Exploring Edge Mechanisms as an Inductive Bias},
author = {Hou, Lintai},
year = {2026},
eprint = {2608.06834},
archivePrefix = {arXiv},
primaryClass = {cs.LG},
url = {https://arxiv.org/abs/2608.06834}
}