GraphFinder: From Problem Recognition to Ontology-Grounded and Executable Graph Formalization

Many real-world optimization problems appear as unstructured natural-language descriptions that do not mention graphs explicitly, and it is often unclear whether they can be formalized as classical graph problems and solved by established graph algorithms. This paper asks whether LLMs can reliably transform such descriptions into executable, ontology-compatible graph formalizations. We propose GraphFinder, which first determines whether a useful graph abstraction exists from a natural language optimization problem, then selects and instantiates a classical formulation from a curated graph problem ontology and returns an executable solver. The system uses typed slot filling to constrain formalization, treats verbal LLM verification only as advisory, and uses program execution plus machine-checkable output conditions as its acceptance gate. We explicitly distinguish executable success from semantic faithfulness and add a 100-instance equivalence tier with independent reference solvers. On the 520-problem GraphAbstraction-Bench we build, 55-way identification reaches 0.880-0.925 top-1 accuracy, while free-form executable end-to-end success is only 0.30-0.37. Ontology grounding with execution raises executable end-to-end success to 0.84 on the paired 50-problem subset and 0.715 on all 200 implicit optimization problems. On the 100-instance equivalence tier with concrete numeric data and independent reference solvers, reference-correct end-to-end success is 0.80 with predicted classes and 0.72 with oracle classes.