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

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

Share This Event

  • This event has passed.

Details

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

Venue

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