Significance of Side Information in the Graph Matching Problem
Significance of Side Information in the Graph Matching Problem
复制标题
辅助信息在图匹配问题中的意义
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
N. Kiyavash
中科院分区：
文献类型：
--
作者：
K. Singhal;Daniel Cullina;N. Kiyavash
基于渗流的图匹配算法依赖于种子顶点对的可用性作为边信息来有效地跨网络匹配用户。虽然这样的算法在实践中工作得很好，但是存在对攻击者潜在有用的其他类型的辅助信息。在本文中，我们考虑的问题匹配两个相关的图时，攻击者可以访问侧信息，无论是在社区标签或不完美的初始匹配的形式。在前一种情况下，我们提出了一个朴素的图匹配算法，通过引入社区度向量，利用社区标签的信息，在一个有效的方式。此外，我们分析了一个变种的基本渗流算法在文献中提出的社区结构的图。在后一种情况下，我们提出了一种新的渗透算法，使用两个阈值，作为输入的不完美匹配匹配相关的图。
我们评估所提出的算法合成以及真实的世界的数据集，使用各种实验。实验结果表明，社区作为边信息的重要性，特别是当种子的数量很少，网络是弱相关的。
Percolation based graph matching algorithms rely on the availability of seed vertex pairs as side information to efficiently match users across networks. Although such algorithms work well in practice, there are other types of side information available which are potentially useful to an attacker. In this paper, we consider the problem of matching two correlated graphs when an attacker has access to side information, either in the form of community labels or an imperfect initial matching. In the former case, we propose a naive graph matching algorithm by introducing the community degree vectors which harness the information from community labels in an efficient manner. Furthermore, we analyze a variant of the basic percolation algorithm proposed in literature for graphs with community structure. In the latter case, we propose a novel percolation algorithm with two thresholds which uses an imperfect matching as input to match correlated graphs.
We evaluate the proposed algorithms on synthetic as well as real world datasets using various experiments. The experimental results demonstrate the importance of communities as side information especially when the number of seeds is small and the networks are weakly correlated.