The Power of D-hops in Matching Power-Law Graphs
The Power of D-hops in Matching Power-Law Graphs
复制标题
DOI：
10.1145/3460094
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
LIREN YU;Jiaming Xu;Xiaojun Lin
中科院分区：
文献类型：
--
作者：
LIREN YU;Jiaming Xu;Xiaojun Lin
研究了幂律图的种子图匹配问题。假设两个边相关图分别从一个具有幂律度分布的共同父图中独立地进行边采样。随机选择一组正确匹配的顶点对作为初始种子。我们的目标是使用种子来恢复两个图之间剩余的潜在顶点对应关系。从现有的专注于在$1$ hop邻域中使用高次种子的方法出发，我们开发了一种有效的算法，利用适当定义的D-hop邻域中的低次种子。具体来说，我们首先根据D-hop邻域中低度种子的数量匹配一组具有适当度的顶点对（我们称之为第一个切片）。这种方法显著减少了触发级联过程以匹配其余图所需的初始种子的数量。在具有n个顶点、最大度Θ（√n）和幂律指数2 4-β/3-β的Chung-Lu随机图模型下，通过最优选择第一个片，只要提供Ω（(log n)4-β）个初始种子，我们的算法就可以在没有任何误差的情况下，以高概率正确匹配常数部分的真对。我们的结果在种子大小要求上实现了指数级的降低，因为之前已知的最好的结果需要n1/2+ε种子（对于任何小常数ε>0）。综合数据和真实数据的性能评价进一步证实了算法的改进。
This paper studies seeded graph matching for power-law graphs. Assume that two edge-correlated graphs are independently edge-sampled from a common parent graph with a power-law degree distribution. A set of correctly matched vertex-pairs is chosen at random and revealed as initial seeds. Our goal is to use the seeds to recover the remaining latent vertex correspondence between the two graphs. Departing from the existing approaches that focus on the use of high-degree seeds in $1$-hop neighborhoods, we develop an efficient algorithm that exploits the low-degree seeds in suitably-defined D-hop neighborhoods. Specifically, we first match a set of vertex-pairs with appropriate degrees (which we refer to as the first slice) based on the number of low-degree seeds in their D-hop neighborhoods. This approach significantly reduces the number of initial seeds needed to trigger a cascading process to match the rest of graphs. Under the Chung-Lu random graph model with n vertices, max degree Θ(√n), and the power-law exponent 2 4-β/3-β, by optimally choosing the first slice, with high probability our algorithm can correctly match a constant fraction of the true pairs without any error, provided with only Ω((log n)4-β) initial seeds. Our result achieves an exponential reduction in the seed size requirement, as the best previously known result requires n1/2+ε seeds (for any small constant ε>0). Performance evaluation with synthetic and real data further corroborates the improved performance of our algorithm.