Friday, 20.10.2017
10:00

11:00
Abstract:
The graph similarity problem, also known as approximate graph
isomorphism or graph matching problem has been extensively
studied in the machine learning community, but has not received
much attention in the algorithms community.
Given two graphs G,H with adjacency matrices A_G,A_H, a
wellstudied measure of similarity is the Frobenius distance
dist(G,H):=min_P  A_G^P  A_H _F,
where P ranges over all permutations of the vertex set of G, A_G^P
denotes the matrix obtained from A_G by permuting rows and columns
according to P, and M_F is the Frobenius norm of a matrix M.
The (weighted) graph similarity problem, denoted by SIM (WSIM),
is the problem of computing this distance for two graphs of same order.
This problem is closely related to the notoriously hard
quadratic assignment problem (QAP), which is known to be
NPhard even for severely restricted cases.
It is known that SIM (WSIM) is NPhard: we strengthen this
hardness result by showing that the problem remains NPhard
even for the class of trees. Identifying the boundary of
tractability for this problem is best done in the framework
of linear algebra. Our main result is a polynomial time
algorithm for the special case of WSIM where both input
matrices are positive semidefinite, have boundedrank, and
where one of the matrices has a bounded clustering number.
The clustering number is a natural algorithmic parameter
arising from spectral clustering techniques. We complement
this result by showing NPhardness for matrices of bounded rank
and for positivesemidefinite matrices.