Computing Graph Isomorphisms and Similarities
Daniel Neuen
MPI-INF - D1
02 Oct 2024, 12:15 pm - 1:15 pm
Saarbrücken building E1 5, room 002
Joint Lecture Series
Deciding if two graphs are isomorphic, i.e., whether they are structurally
identical, is a fundamental computational problem that has many important
applications. Despite extensive efforts in the past decades, GI has remained
one of only few natural problems contained in NP that are neither known to be
NP-complete nor known to be contained in P. In 20216, Babai proved in a
breakthrough result that GI can be solved in quasipolynomial time. In the first
part of my talk, ...
Deciding if two graphs are isomorphic, i.e., whether they are structurally
identical, is a fundamental computational problem that has many important
applications. Despite extensive efforts in the past decades, GI has remained
one of only few natural problems contained in NP that are neither known to be
NP-complete nor known to be contained in P. In 20216, Babai proved in a
breakthrough result that GI can be solved in quasipolynomial time. In the first
part of my talk, I will give an overview on recent developments on testing
isomorphism.
A closely related problem is that of determining the similarity between two
graphs. Arguably, this problem is even more relevant for many applications such
as machine learning tasks on graph-structured data. Natural approaches such as
counting edge modifications required to turn one graph into the other are
computationally intractable even on very restricted input graphs. As a result,
various other methods have been proposed to measure similarity between graphs
such as graph motif counts, i.e., measuring similarity based on counting
certain patterns appearing in the graphs. In the second part of the talk, we
will consider different ways of measuring similarity and discuss relations to
standard heuristics for isomorphism testing that have been discovered in recent
years.
Read more