STOR Colloquium: Vince Lyzinski, Univ. of Massachusetts Amherst

Vince Lyzinski
The University of Massachusetts Amherst

Graph matching in edge-independent networks

The graph matching problem seeks to find an alignment between the vertex sets of two graphs that best preserves common structure across graphs. Here, we consider the closely related problem of graph matchability: Given a latent alignment between the vertex sets of two graphs, under what conditions will the solution to the graph matching optimization problem recover this alignment in the presence of shuffled vertex labels?  We consider the problem of graph matchability in non-identically distributed networks, and working in a general class of edge-independent network models, we demonstrate that graph matchability is almost surely lost when matching the networks directly, and is almost perfectly recovered when first centering the networks using Universal Singular Value Thresholding before matching. While there are currently no efficient algorithms for solving the graph matching problem in general, these results nonetheless provide practical algorithmic guidance for approximately matching networks in both real and synthetic data applications.

Refreshments will be served at 3:00pm in the 3^rd floor lounge of Hanes Hall