Converse bounds for multiple graph alignment and correlation detection based on last matching

Abstract

The paper focuses on information theoretic converse bounds for the alignment of $m$ correlated graphs and for the detection of correlation among $m$ graphs. A simple idea for $m\ge 3$ is that if the alignment of $m-1$ of the graphs is revealed as extra information (by a genie for example) then it is still necessary to produce the alignment between the one remaining graph and the others, i.e. the last matching must be accomplished. For both Gaussian and Erdos-Renyi models, the last-matching problem is equivalent to one with two observed graphs, providing a path to extend converse bounds for $m=2$ to larger $m$. While the method is rather obvious for alignment, we show that the method can also be used to derive converse bounds for weak detection of correlation.