Spectral graph theory considers the matrices associated with graphs and studies these matrices’ eigenvalues and eigenvectors. Spectral graph theory has applications in many fields of computer sciences, but has had surprisingly little impact in planning. A paper by Steinerberger (2021) shows how a particular eigenvector can be used to construct a descending heuristic - following this greedily is guaranteed to lead to the goal. We give an alternative proof of this fact by showing that the eigenvector describes a network flow, and we establish further connections to planning by showing that the eigenvector describes a consistent, goal-aware heuristic. We also give some examples to illustrate the behaviour of Steinerberger’s algorithm, and answer one of his open questions.

HSDIP 2025 Paper [pdf]

This paper was accepted at the HSDIP 2025 workshop!

Talk [slides]

I gave this talk at AmsterCAPS 2025.

Code (coming soon)

I have some python code for generating all the pictures from the paper and slides. For now, just send me a message if you want access!

Updated:

You may also enjoy