Graph optimization is foundational to modern operations — routing vehicles through road networks, detecting communities in social networks, and influence-based targeting. Yet prevailing approaches treat each task instance in isolation, discarding persistent topological knowledge embedded in the underlying network.

GOFM shifts the focus from task-specific solvers to a task-agnostic structural prior. It internalizes network topology and distance geometry by encoding structure-aware random walks into a Transformer through progressive masked reconstruction. At inference, this learned prior facilitates diverse optimization tasks via lightweight constrained decoding, ensuring strict feasibility without retraining.

The GOFM framework consists of three stages:

GOFM handles five classical problem classes with a single pretrained backbone:

• Foundation-model framework for graph optimization: A single pretrained model performs well across multiple NP-hard graph tasks on real sparse networks, without any architectural changes.
• Self-supervised pretraining via structure-aware walks: Structure-aware random walks combined with progressive masked reconstruction equip the model with a holistic structural prior over the target graph.
• Cross-task reuse on real networks: Validated on networks up to 1,945 nodes across five routing families; generalizes beyond routing to community detection and influence maximization.

GOFM achieves competitive solution quality compared to widely used OR solvers such as LKH3 and Google OR-Tools, with inference one to two orders of magnitude faster on city-scale graphs. Unlike neural baselines trained on complete-graph distributions, GOFM maintains near-perfect feasibility across all settings.

On the Amazon Last Mile dataset, GOFM delivers a 24.5% reduction in total route distance — a direct impact on real-world logistics operations.