A Concentration of Measure Approach to Correlated Graph Matching
A Concentration of Measure Approach to Correlated Graph Matching
复制标题
DOI：
10.1109/jsait.2021.3056280
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Farhad Shirani;S. Garg;E. Erkip
中科院分区：
文献类型：
--
作者：
Farhad Shirani;S. Garg;E. Erkip
图匹配问题自然出现在网络隐私、图像处理和计算生物学等各种应用中。在本文中，图匹配是在随机模型下考虑的，其中一对具有成对相关边的随机生成的图将被匹配，使得给定第一个图中顶点的标签，通过利用其边之间的相关性来恢复第二个图中的标签。该问题是在各种设置和图形模型下考虑的。第一步，研究相关 Erdös-Rényi (CER) 图模型，其中顶点具有相似标签的所有边对都是基于相同的分布且独立于其他边生成的。引入了一种称为典型性匹配方案的匹配方案。该方案通过研究两个图的邻接矩阵的联合典型性来运行。关于序列排列典型性的新结果为基于 CER 模型参数的成功匹配提供了充分必要条件。下一步，结果将扩展到具有基于随机块模型（SBM）生成的社区结构的图。 SBM 模型是 CER 模型的推广，其中图中的每个顶点都与一个社区标签相关联，这会影响其边缘统计数据。结果进一步扩展到两个以上相关图的集成匹配。最后，研究了种子图匹配问题，其中第二个图中的标签子集在匹配之前已知。在这种场景下，除了获得成功匹配的充要条件外，还提出了多项式时间匹配算法。
The graph matching problem emerges naturally in various applications such as Web privacy, image processing and computational biology. In this article, graph matching is considered under a stochastic model, where a pair of randomly generated graphs with pairwise correlated edges are to be matched such that given the labeling of the vertices in the first graph, the labels in the second graph are recovered by leveraging the correlation among their edges. The problem is considered under various settings and graph models. In the first step, the Correlated Erdös-Rényi (CER) graph model is studied, where all edge pairs whose vertices have similar labels are generated based on identical distributions and independently of other edges. A matching scheme called the typicality matching scheme is introduced. The scheme operates by investigating the joint typicality of the adjacency matrices of the two graphs. New results on the typicality of permutations of sequences lead to necessary and sufficient conditions for successful matching based on the parameters of the CER model. In the next step, the results are extended to graphs with community structure generated based on the Stochastic Block Model (SBM). The SBM model is a generalization of the CER model where each vertex in the graph is associated with a community label, which affects its edge statistics. The results are further extended to matching of ensembles of more than two correlated graphs. Lastly, the problem of seeded graph matching is investigated where a subset of the labels in the second graph are known prior to matching. In this scenario, in addition to obtaining necessary and sufficient conditions for successful matching, a polynomial time matching algorithm is proposed.