Language models solve larger graphs with better scalable encoding

Scaling Graph Reasoning in Language Models with Learnable Graph Positional Encodings

Machine LearningArtificial Intelligence

Summary

Graph reasoning tasks often require representing a graph in a way language models can understand, but this usually grows too big and slow as graphs get large. The authors propose a new technique that uses special graph position markers created by graph neural networks and transformers to help language models handle larger graphs more efficiently. This method reduces the input size and keeps performance high, even as graphs grow to thousands of nodes. Additionally, the model stays effective even if the labels of the graph nodes change.

What this means in practice

  • For ai software engineers: Integrate scalable graph positional encodings into language models to enable efficient reasoning on large, complex graphs without context overload.
  • For data infrastructure teams: Optimize graph data processing pipelines by reducing serialized adjacency information and improving robustness to node relabeling in graph-based queries.

Authors

Javier Porras-Valenzuela, Arush Arora, Alejandro Ribeiro

Abstract

Solving reasoning tasks supported on graphs typically requires providing a Language Reasoning Model (LRM) with a serialized description of the graph. This approach results in the input length growing with the number of edges, which limits the size of the problems that can be solved. Furthermore, even when graphs fit in context, performance sharply decays as the graphs grow. We propose to address this by augmenting LRMs with scalable and permutation equivariant graph positional encodings that modulate attention logits. An additional post-fusion-style module incorporates structural information into hidden states. We compute these positional encodings using a GNN followed by a Graph Transformer. This eliminates the need for serialized adjacencies, reducing the context burden to $O(N)$. We jointly fine-tune the positional encoder and the LRM LoRA adapters using optimal solutions generated by graph-theoretic solvers, resulting in a computationally efficient method. Trained on small graphs, the model exhibits improved size-generalization across graph-theoretic tasks on graphs with up to 1,000 nodes, and produces fewer tokens than a conventional LRM. Additionally, we observe that our model remains robust to node relabelings. Evaluations on graph-theoretic benchmarks also show that performance on small graphs is preserved.