The project broadly looks into different topology- and geometry-inspired graphical signatures for easy description and comparison of complex data. One such powerful signature is geometric graphs. A geometric graph is a combinatorial graph, endowed with a geometry that is inherited from its embedding in a Euclidean space.
Formulation of a meaningful measure of (dis-)similarity in both the combinatorial and geometric structures of two such geometric graphs is a challenging problem in pattern recognition. In [1], I presented two notions of distance measures for geometric graphs: the geometric edit distance (GED) and geometric graph distance (GGD). While the former is based on the idea of editing one graph to transform it into the other graph, the latter is inspired by the inexact matching of the graphs. Alongside studying the metric properties of GED and GGD, I investigated how the two notions compare. I proved a very strong result showing that both the distances are \mathcal{NP}-hard to compute, even if the graphs are planar and arbitrary cost coefficients are allowed.
To remedy the computational challenges of GGD, I later proposed the Graph mover’s distance [2], a polynomial-time computable alternative that is based on optimal transport.
In order to provide an alternative distance measure for graphs, I also worked with Ben Holmgren, who was an undergraduate student at Montana State University at the time. In [3], we presented various topological properties of the space of graphs under the Fréchet distance.
Collaborators
- Vitaliy Kurlin, University of Liverpool
- Carola Wenk, Tulane University (past)
- Erin Chambers, St. Louis University (past)
- Liz Munch, Michigan State University (past)
Graduate Mentees
- Khush Shah, George Washington University
- Shikha Kumari, George Washington University