基于随机游走的图匹配算法

SIGAI特约作者

Roger

上海交通大学博士生

图匹配是计算机视觉和模式识别领域重要的NP难问题。本文主要介绍了基于随机游走的图匹配算法RRWM [1]以及它在超图匹配上的扩展RRWHM [2]。

图匹配简介

在计算机视觉领域，图匹配（graph matching，GM）算法旨在利用图结构的相似度信息，寻找图结构之间节点与节点之间的匹配关系，如图 1所示。图匹配算法是计算机视觉与模式识别领域一类历久弥新的算法。

图 1 图匹配示意图

由于是寻找节点到节点的匹配关系，图匹配问题的结果由一个指派矩阵（assignment matrix）X表示。在图 1所示的问题中，指派矩阵为一个4×4的{0, 1}矩阵（问题中，4个节点匹配4个节点），其中指派矩阵的每行、每列有且仅有一个元素为1。

在图匹配问题中，我们同时考虑了图结构之间节点与节点的一阶相似度以及边与边的二阶相似度。相似度矩阵（affinity matrix）K同时包含了一阶的节点相似度信息以及二阶的边相似度信息。相似度矩阵是一个具有高阶复杂度的矩阵，在图 1所示的问题中，相似度矩阵规模为16×16。其中，相似度矩阵的对角线元素包含了节点与节点的相似度信息，非对角线元素包含了边与边的相似度信息。

基于相似度矩阵K与指派矩阵X，图匹配问题可以被公式化为如下数学形式：

其中，vec(X)代表将矩阵X转换为一个列向量。一个列向量的转置乘矩阵乘列向量，结果是一个数值。直观地看，公式（1）的含义为同时最大化匹配结果中的一阶相似度以及二阶相似度。在数学上，公式（1）是一个NP-难的二次指派问题（Quadratic Assignment Problem），无法在多项式时间内找到全局最优解。因此，研究者们提出了许多近似算法来高效、精确地求解该问题。今天我们介绍基于随机游走的算法RRWM [2]，以及它在超图上的扩展RRWHM [3]。它们是精确求解公式（1）的经典算法。

随机游走简介

随机游走（random walk）是图论中的重要算法，在数据挖掘领域有广泛的应用。简而言之，随机游走算法构建了若干个随机游走器（random walker）。随机游走器从某个节点初始化，之后在每一步随机游走中，随机地访问当前节点的某个邻接节点。

随机游走一项有名的应用即为谷歌的PageRank算法，如图 2所示。PageRank算法中，每个随机游走器均模仿了一个用户浏览互联网时的行为：用户随机地点击当前网页中的某个链接，跳转到下一个网站。被更多用户访问的网站因此具有更高的权重，在搜索结果中排名更加靠前。PageRank是在图上运行的：基于链接的指向关系，所有互联网页面构成了一个图结构。因此，通过构建网页之间的链接关系图，搜索引擎就能为所有网页计算权重并排序。

图 2 PageRank算法示意（图源wikipedia）

因此，以PageRank为代表的随机游走算法拥有为图中的节点计算权重的能力。本文介绍的基于随机游走的图匹配算法就将随机游走算法扩展到了图匹配问题中，用于计算图匹配问题中匹配关系的权重。

伴随图

在开始介绍具体算法之前，我们还需要最后一点预备知识。读者可能已经发现，图匹配的问题形式中存在两个带匹配的图，而随机游走只在单个图上进行。因此，若要将随机游走算法应用于图匹配问题，我们就需要将图匹配问题转化为单个图，即伴随图（association graph）[1]的形式。

图 3 （a）图匹配问题与（b）伴随图

如图 3所示，考虑两个节点（1，2）匹配三个节点（a，b，c）的情况。（a）中两个图结构代表原始的图匹配问题，（b）中的图为伴随图。图匹配问题中，节点与节点的对应关系（橙色虚线双箭头）转化为伴随图中的节点，例如节点1与节点a的匹配关系转化为伴随图中的节点1a；边与边的相似度信息（蓝色虚线双箭头）转化为伴随图中的边，例如边12与边ab的相似度（即K1a:2b的值）转化为伴随图中的有权边1a-2b。伴随图是一个无向权值图。通过随机游走算法，我们可以为伴随图的每个节点计算权重。图匹配问题进而被转化为寻找伴随图中具有最大权重的若干个节点的问题。

RRWM[2]

在该论文中，作者分析并提出了在伴随图上基于随机游走的图匹配算法RRWM：Reweighted Random Walk for Graph Matching。首先，作者提出在伴随图中增加吸收节点（absorbing node），使其他所有节点的出度相等。基于伴随图的形式，一种朴素的思路是在伴随图上直接采用随机游走算法为每个节点进行评分。在论文中，作者通过分析发现，在伴随图上直接采用随机游走算法实际上与基于谱分解的算法[1]是等价的。

随后，作者提出了在随机游走过程中重新分配每个节点的权重，即采用Reweighted jumps。该方法的本质是，在随机游走的每一步中，加入了额外的匹配约束信息（问题约束中，最终得到的匹配结果一一对应的）。最终RRWM的算法形式非常简单，如下所示，其中Reweighting部分在算法的8-14行。若去掉Reweighting部分，则该算法退化为直接采用随机游走进行评分的朴素算法，即算法[1]。

图 4中的实验结果显示，RRWM算法（红色实线）能够获得当时最先进的匹配精度。特别地，与SM算法[1]（黑色实线）的对比显示，在随机游走的过程中引入额外的匹配约束信息，能够显著地提升模型的匹配精度。

图 4 仿真实验结果

超图与超图匹配

超图（hypergraph）是图的扩展：超图由节点与超边组成，其中节点的定义与图的节点一致，超边（hyperedge）则可以连接任意数目的节点。图 5即为一个超图的例子，其中，超边e1连接了三个节点（v­1，v2，v3），超边e4只连接了一个节点v4。

图 5 一个超图的例子（图源wikipedia）

超图匹配（hypergraph matching，HGM）算法利用超图之间的高阶相似度信息，求解节点与节点的对应关系。作为对比，图匹配算法只利用了至多二阶的图结构信息。作为图匹配算法的扩展，超图匹配算法显式地建模了更高阶的图结构信息，通常情况下能够获得更精确、更鲁棒的匹配结果。例如，一种常见的三阶图相似度形式如图 6所示，该三阶相似度衡量了图中三角形结构的相似度。公式（2）为该三阶相似度的数学形式。

图 6 一种常见的三阶图相似度形式

在包含了高阶相似度信息的超图匹配中，相似度矩阵扩展为相似度张量，高阶的相似度信息由张量中的元素表示。通常，t阶相似度张量的递归定义如公式（3）。它同时包含了t阶的相似度以及（t-1）阶相似度张量中的信息。

将公式（1）中的相似度矩阵X转换为相似度张量H，超图匹配的数学形式为

RRWHM[3]

作为RRWM在超图匹配上的扩展，原问题中的伴随图转换成了伴随超图：匹配问题中节点的对应关系依然对应伴随超图中的节点；而高阶的相似度则等价于伴随超图中的超边。因此，在RRWM的伴随图上沿着边的随机游走，转变在RRWHM的伴随超图上沿着超边的随机游走。沿着超边的随机游走如图 7所示。

图 7 沿着超边的随机游走示意图

RRWHM的算法形式与RRWM类似，同样包含了在随机游走过程中考虑图匹配约束条件的Reweighted jump。RRWHM的算法如下所示。

RRWHM可以看做RRWM在超图上的扩展，其中相似度矩阵扩展为了相似度张量，伴随图扩展为了伴随超图，沿着伴随图的边的随机游走扩展为了沿着伴随图超边的随机游走。由于采用了高阶（三阶）的相似度信息，在实验中，RRWHM具有比RRWM更高的匹配精度。

总结

本文主要介绍了计算机视觉图匹配算法中的一类经典算法：基于随机游走的图匹配算法RRWM，以及它在超图匹配中的扩展RRWHM。在本文中，我们还简单介绍了图匹配、随机游走、图匹配伴随图、超图与超图匹配等背景知识。

参考文献

[1] Leordeanu and Hebert, “A Spectral Technique for Correspondence Problems Using Pairwise Constraints.” ICCV 2005.

[2] Cho, Lee, and Lee, “Reweighted Random Walks for Graph Matching.” ECCV 2010.

[3] Lee, Cho, and Lee, “Hyper-Graph Matching via Reweighted Random Walks.” CVPR 2011.

本文为SIGAI原创