318 Hanes Hall, CB #3260 Chapel Hill, NC 27599-3260
Loading Events

« All Events

  • This event has passed.

STOR Colloquium: Vince Lyzinski, Univ. of Massachusetts Amherst

January 18, 2019 @ 3:30 pm - 4:30 pm

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 3rd floor lounge of Hanes Hall


January 18, 2019
3:30 pm - 4:30 pm
Event Category:


120 Hanes Hall
Hanes Hall
Chapel Hill, NC 27599 United States