Learning Classical Graph Algorithms with Graph Neural Networks

Co-Supervised by: Kalvin Dobler

If you are interested in this topic or have further questions, do not hesitate to contact: kalvin.dobler@unibe.ch

    Background / Context

    Graph neural networks (GNNs) are widely used to learn representations of graph-structured data, but their ability to learn and execute algorithmic procedures remains an active research question. Recent work demonstrates that GNNs can, under specific conditions, learn to execute classical graph algorithms such as breadth-first search (BFS), depth-first search (DFS), and Bellman–Ford.

    This project investigates whether GNNs can learn to execute classical graph algorithms and, more importantly, whether the learned procedures generalize beyond the graph sizes, structures, and execution conditions encountered during training. Rather than evaluating only performance on in-distribution graphs, the project focuses on the generalization and robustness of learned algorithmic behavior.

    Question(s) / Goals

    The project will investigate:

    • Can standard and recurrent GNN architectures learn to execute classical graph algorithms such as DFS?
    • To what extent do learned algorithms generalize to larger graphs and previously unseen graph structures?
    • How robust are learned algorithms to graph perturbations, such as edge additions, deletions, and changes in graph density?
    • Does recurrent message passing improve generalization to algorithmic executions that require more steps than seen during training?
    • Which architectural and training choices are most important for reliable algorithmic reasoning and generalization?
    • What are the main failure modes, and can they reveal limitations of GNNs as models of algorithmic computation?

    Approach / Methods

    The student will implement several classical graph algorithms, such as:

    • Breadth-first search (BFS)
    • Shortest-path algorithms
    • Connected components
    • PageRank or label propagation
    • Optionally DFS or Bellman–Ford

    For each algorithm, synthetic graphs will be generated automatically, with the exact algorithm providing the ground-truth execution trace and final result.

    Different GNN architectures, such as GCN, GIN, and GraphSAGE, will then be trained to reproduce the algorithmic computation.

    A particular focus will be extrapolation: models will be trained on smaller graphs and evaluated on substantially larger graphs and graphs with different structural properties. The study can additionally investigate whether providing intermediate algorithmic states as supervision improves generalization compared with standard end-to-end training.

    Expected Contributions / Outcomes

    The project is expected to provide:

    • A systematic benchmark of GNNs for learning classical graph algorithms.
    • An evaluation of generalization across graph size and topology.
    • An analysis of the strengths and limitations of standard message-passing architectures for algorithmic reasoning.
    • Identification of factors that influence successful algorithm execution, such as message-passing depth, node representations, and intermediate supervision.
    • An open-source implementation and reproducible experimental framework.

    Required Skills

    • Familiarity with graph-theoretic concepts, machine learning experimentation and evaluation, or willingness to learn them.
    • Basic programming skills in Python.
    • Interest in graph neural networks and deep learning.

    Further Readings

    • Veličković et al., “Neural Execution of Graph Algorithms,” ICLR 2020.
    • Qharabagh et al., “Learning to Execute Graph Algorithms Exactly with Graph Neural Networks,” ICML 2026.