Information Recovery in Shuffled Graphs via Graph Matching

Add to your list(s) Download to your calendar using vCal

• Vince Lyzinski (Johns Hopkins University)
• Wednesday 09 November 2016, 14:00-15:00
• Seminar Room 2, Newton Institute.

If you have a question about this talk, please contact INI IT.

This talk has been canceled/deleted

In a number of methodologies for joint inference across graphs, it is assumed that an explicit vertex correspondence is a priori known across the vertex sets of the graphs. While this assumption is often reasonable, in practice these correspondences may be unobserved and/or errorfully observed, and graph matching—aligning a pair of graphs to minimize their edge disagreements—is used to align the graphs before performing subsequent inference. Herein, we explore the duality between the loss of mutual information due to an errorfully observed vertex correspondence and the ability of graph matching algorithms to recover the true correspondence across graphs. We then demonstrate the practical effect that graph shuffling—and matching—can have on subsequent inference, with examples from two sample graph hypothesis testing and joint graph clustering.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.