Bounding the Interleaving Distance for Geometric Graphs with a Loss Function
share
A geometric graph is an abstract graph along with an embedding of the graph into the Euclidean plane which can be used to model a wide range of data sets. The ability to compare and cluster such objects is required in a data analysis pipeline, leading to a need for distances or metrics on these objects. In this work, we study the interleaving distance on geometric graphs, where functor representations of data can be compared by finding pairs of natural transformations between them. However, in many cases, particularly those of the set-valued functor variety, computation of the interleaving distance is NP-hard. For this reason, we take inspiration from the work of Robinson to find quality measures for families of maps that do not rise to the level of a natural transformation. Specifically, we call collections ϕ = {ϕ_U| U} and ψ = {ψ_U| U} which do not necessarily form a true interleaving an assignment. In the case of embedded graphs, we impose a grid structure on the plane, treat this as a poset endowed with the Alexandroff topology K, and encode the embedded graph data as functors F: 𝐎𝐩𝐞𝐧(K) →𝐒𝐞𝐭 where F(U) is the set of connected components of the graph inside of the geometric realization of the set U. We then endow the image with the extra structure of a metric space and define a loss function L(ϕ,ψ) which measures how far the required diagrams of an interleaving are from commuting. Then for a pair of assignments, we use this loss function to bound the interleaving distance, with an eye toward computation and approximation of the distance. We expect these ideas are not only useful in our particular use case of embedded graphs, but can be extended to a larger class of interleaving distance problems where computational complexity creates a barrier to use in practice.
READ FULL TEXT