Frameworks for Measuring Graph Similarity

• Applicant: Gaurav Rattan, Ph.D.
• Subject Area: Theoretical Computer Science
• Term: from 2018 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 411032549

In this project, we are interested in developing theoretical frameworks for measuring similarity of graphs. We propose a novel framework based on graph homomorphism numbers, along with re-examining other existing approaches to graph similarity. We believe that the existing insights and tools for the Graph Isomorphism problem can inspire novel frameworks for measuring graph similarity (and vice-versa). Therefore, the main objective of this project is to extend the frontier of our understanding of graph similarity measures from a theoretical perspective. Our first objective is to propose/study a novel framework for measuring graph similarity,. We seek to design encodings of graphs as (possibly infinite-dimensional) vectors with the following property. The distance between the corresponding vectors (in a suitably chosen metric) must be a useful measure of similarity between the graphs. The natural candidates for such encodings are restricted homomorphism vectors HOM_C(G), where we fix a class C of graphs and list the homomorphism numbers Hom(F,G) for every graph F in class C. In a suitable metric, the distance between the vectors HOM_C(G) and HOM_C(H) is a candidate similarity measure. Our preliminary work establishes a strong mathematical motivation for considering such measures, and we seek to further develop these similarity measures within our framework. We consider other interesting classes of graphs C as a basis for our similarity measures, e.g. paths, bounded tree-width graphs, bounded path-width graphs and cycles. Our second key objective is to study graph similarity from a convex optimization viewpoint. The adjacency matrices of two graphs G and H have been already used to define distance measures between the graphs. We seek efficient algorithms for computing and approximating such measures of similarity. In particular, our novel approach is to establish the role of the spectrum (eigenvalues/eigenvectors) of the input graphs, for this problem (as suggested by our preliminary work). Our main toolbox will be to generalize the known convex optimization tools for graph isomorphism.From a purely practical perspective, the Graph Similarity has been extensively studied in other fields, viz. machine learning and database theory. An important objective of our project is to theoretically explain the success of practical and heuristic algorithms used in these fields. In general, the practical applications of our project can be found in fields dealing with graph-structured and relational data: examples include pattern analysis, graph classification and graph mining. In particular, the emerging field of graph kernels is of central interest to us. Theoretically, we seek to use our frameworks for designing new graph learning algorithms. Finally, we seek efficient implementations of our work: this part of the project will consist of experimental testing.

• DFG Programme: Research Grants