University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Information Recovery in Shuffled Graphs via Graph Matching

Information Recovery in Shuffled Graphs via Graph Matching

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

If you have a question about this talk, please contact info@newton.ac.uk.

SNA - Theoretical Foundations for Statistical Network Analysis

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2017 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity