Recurrent GNNs: The Power of Iteration
4th European Summer School on Artificial Intelligence, ESSAI 2026, 6 - 10 July 2026, Vienna, Austria
Lecturers:
  • Floris Geerts (University of Antwerp)
  • Jonni Virtema (University of Glasgow)
Level of the course:
Introductory

Course overview (full slides):

Recurrent Graph Neural Networks (GNNs) take the familiar message-passing idea and add one game-changing feature: they can iterate beyond a fixed bound—updating node representations again and again, until a stable “fixed point” or some other halting condition is reached. Why does this matter? Because many standard GNNs only see a fixed-radius neighbourhood, which raises a natural set of questions: What can a finite-depth GNN never compute uniformly? When do we truly need recursion? Can a neural model learn concepts like reachability (“is there a path between nodes?”) without hard-coding a graph algorithm? This course is a student-friendly, mathematically precise introduction to those questions. We start with labeled graphs and basic GNN definitions, then connect expressivity to colour refinement and graded modal logic. Next, we push past their limits focusing on the following topics: Why do reachability and other global properties break the usual tools? What changes once we allow iteration? Finally, we show how recurrent GNNs line up with fixpoint logics and discuss what this tells us about their capabilities and limitations. If you are curious about the fundamentals of graph ML—what these models can express, what they cannot, and how these results are proven—this course is for you.

Schedule and topics covered:
  • Day 1 (slides):
    • Part 1: Basics of Graph Learning
    • What are we learning: Properties of graph structured data.
    • Constraints on learning: Invariants that any learned function must obey.
    • What is the model: Graph Neural Networks (GNNs) – built to satisfy these invariants.
    Part 2: Limits of Graph Neural Networks.
    • How capabilities of GNNs can be measured? Distinguising power. Uniform and non-uniform expressivity.
    • To what can we compare GNNs? Graph algorithms (colour refinement) and logic.
  • Day 2 (slides):
    • Part 3: Graded modal logic and bisimulation
    • How capabilities of GNNs be related to formal languages?
    • Key concepts: Basics of graded modal logic, bisimulation, and characteristic formulae.
    Part 4: Logical characterisations of GNNs
    • We show that graded modal logic and GNNs have the same distinguishing power.
    • We prove that GNNs are at least as expressive than GML.
    • We prove that non-uniform expressivity of GNNs and GML coincide.
  • Days 3-4 (slides):
    • Part 5: GNNs and Recursion
    • Different approaches to add recursion to GNNs.
    • Expressivity of these recurrent GNN alternatives.
    • Two extension of GML to define recursive classifiers.
  • Extra (slides): Real computation and arithmetic circuits.