Graphs are Evidence, Not Circuits
Abstract
Graph learning has mistaken its evidence for its machinery. The evidence says what is observed; the query says what must be inferred; the circuit specifies how observations are combined. Message passing commonly inherits that circuit from the observed graph. We separate these choices and show why the distinction matters. Changing only the query on identical evidence moves a linear predictor from 58 accuracy points below an exact solver to within 0.1 point of it. Recompiling Minesweeper's clue relationships improves a parameter-matched GCN by 5.24 AUC points; randomizing those relationships erases the gain. Exact examples explain why seeing farther can still leave a linear predictor below optimal performance. puts the separation to work: preserve a strong GNN, learn explicit local relationships within a declared library, and add inference only when held-out validation shows a gain. Without label inputs, it reaches state-of-the-art-level Minesweeper performance at 99.09 ROC-AUC; training-label inputs raise this to 99.97. Relative to its matched baselines, remaining ranking error falls by approximately 63% and 98%. On arxiv-year, the gain persists beyond generic correction and a second GNN under matched label access. A separate model learns numerical relationships within a supplied counting family and reuses them on independent boards without further training. For questions about groups of cells, it improves on treating its individual predictions as independent. Treat the graph as evidence, then build the computation the question requires.
est. 32% chance this paper gets accepted at ICLR 2027.
What do you think this paper will get?
All positions stay anonymous.