HashAlign: Hash-Based Alignment of Multiple Graphs
HashAlign: Hash-Based Alignment of Multiple Graphs
复制标题
HashAlign：基于哈希的多个图的对齐
DOI：
10.1007/9783319.930404
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Koutra, Danai
中科院分区：
文献类型：
--
作者：
Heimann, Mark;Lee, Wei;Pan, Shengjie;Chen, Kuan-Yu;Koutra, Danai
融合或对齐两个或多个网络是许多图挖掘任务(例如，推荐系统、链接预测、网络集合分析)的基本构建块。以往的大部分工作都集中在将成对图对齐问题描述为一个具有可变约束和松弛的最优化问题。本文研究了多图对齐问题，提出了一种高效、直观的基于散列的网络对齐框架HashAlign，该框架同时利用了网络的结构属性和其他结点和边的属性(如果有)。我们介绍了一种新的LSH族构造，以及为此任务量身定做的健壮节点和图特征。我们的方法快速对齐多个图，同时避免了所有配对比较的问题，通过选择一个中心图来表示所有的对齐。我们在合成网络和真实网络上的广泛实验表明，平均而言，在配对对齐中，HashAlign值比基线对齐快10%到20%，在多重图对齐中比基线对齐快50%。
Fusing or aligning two or more networks is a fundamental building block of many graph mining tasks (e.g., recommendation systems, link prediction, collective analysis of networks). Most past work has focused on formulatingpairwisegraph alignment as an optimization problem with varying constraints and relaxations. In this paper, we study the problem ofmultiplegraph alignment (collectively aligning multiple graphs at once) and proposeHashAlign, an efficient and intuitive hash-based framework for network alignment that leverages structural properties and other node and edge attributes (if available) simultaneously. We introduce a new construction of LSH families, as well as robust node and graph features that are tailored for this task. Our method quickly aligns multiple graphs while avoiding the all-pairwise-comparison problem by expressing all alignments in terms of a chosen ‘center’ graph. Our extensive experiments on synthetic and real networks show that, on average,HashAlignisfaster and 10 to 20% more accurate than the baselines inpairwisealignment, andfaster while 50% more accurate inmultiplegraph alignment.
影响因子：
22.7
作者：
Andoni, Alexandr;Indyk, Piotr
通讯作者：
Indyk, Piotr