Information Recovery in Shuffled Graphs via Graph Matching
Information Recovery in Shuffled Graphs via Graph Matching
复制标题
通过图匹配恢复打乱图中的信息
DOI：
10.1109/tit.2018.2808999
复制
发表时间：
2016
影响因子：
2.5
通讯作者：
V. Lyzinski
中科院分区：
文献类型：
--
作者：
V. Lyzinski
虽然许多多图推理方法在隐含的假设下运行，即在图的顶点集上已知显式顶点对应关系，但在实践中，这些对应关系可能只是部分或错误地已知。在此，我们为理解错误观察到的顶点对应可能对后续推理产生的实际影响以及图匹配方法恢复丢失的顶点对齐和推理性能的能力提供了信息理论基础。在相关随机块模型设置中，我们建立了由于错误观察顶点对应而导致的互信息损失与图匹配算法恢复图间真实对应的能力之间的对偶性。在此过程中，我们根据图间的相关性建立了图匹配性的相变，并推测了由于顶点标签洗牌导致的相对信息损失的类似相变。我们用两个样本图假设检验和联合谱图聚类的例子证明了图洗牌和匹配对后续推理的实际影响。
While many multiple graph inference methodologies operate under the implicit assumption that an explicit vertex correspondence is known across the vertex sets of the graphs, in practice these correspondences may only be partially or errorfully known. Herein, we provide an information theoretic foundation for understanding the practical impact that errorfully observed vertex correspondences can have on subsequent inference, and the capacity of graph matching methods to recover the lost vertex alignment and inferential performance. Working in the correlated stochastic blockmodel setting, we establish a 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. In the process, we establish a phase transition for graph matchability in terms of the correlation across graphs, and we conjecture the analogous phase transition for the relative information loss due to shuffling vertex labels. We demonstrate the practical effect that graph shuffling—and matching—can have on subsequent inference, with examples from two sample graph hypothesis testing and joint spectral graph clustering.
影响因子：
4.5
作者：
Choi, David;Wolfe, Patrick J.
通讯作者：
Wolfe, Patrick J.