Learning Graph Edit Distance via Reinforcement Learning

Supervised by: Anthony Gillioz

If you are interested in this topic or have further questions, do not hesitate to contact me.

Context/Background/Current State

Graph Edit Distance (GED) is a popular technique used to match and compare pairs of graphs. Basically, GED finds the minimal set of edit operations that transform a source graph gs into a target graph gt. GED turns out to be very flexible and intuitive. However, GED’s drawback lies in its computational complexity, making it impractical for graphs with a substantial number of nodes (for graphs with several thousands of nodes, for instance, GED is definitely unfeasible).


  • The current research project aims to use reinforcement learning to learn edit operations, with the hope of speeding up GED computation at inference time.


TBD with the supervisor.

Required Skills

  • Good programming skills, particularly working with different frameworks. 
  • Basic knowledge of reinforcement learning and graphs.


Achieving a good and practical solution with these models is a complex task, especially when dealing with Out-of-Distribution Data (that is data that were not in the training set).

Further Reading