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).
Goal(s)
- The current research project aims to use reinforcement learning to learn edit operations, with the hope of speeding up GED computation at inference time.
Approach
TBD with the supervisor.
Required Skills
- Good programming skills, particularly working with different frameworks.
- Basic knowledge of reinforcement learning and graphs.
Remarks
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).