图匹配算法（涵盖近似图匹配）

【图数据管理与挖掘-第四讲（子）图匹配算法（涵盖近似图匹配） 北京大学2021暑期-邹磊教授】https://www.bilibili.com/video/BV1zh411q7PW?vd_source=7c2b5de7032bf3907543a7675013ce3a

图同构：

定义：

给定一个query Q和图G，若存在一个内射函数，满足：

①，点的标签一致

② ，边的标签一致

给定两个图Q和G，是否存在一个双射函数:

点相互对应映射

，Q中的边在G中有相互对应的边

，存在一对一满足的逆函数使G中两点对应的边在Q中也存在

目前为止子图同构问题仍是一个未知问题，无法证明是一个NP-complete问题，也无法找到一个多项式可解算法

应用：

将两个图像通过特征点提取的方法提取出一些特征点和它们之间的拓扑关系，构建出图，对上图进行匹配实质上是对下图进行比对

对化学结构式进行比对，将结构式定义为graph，对graph进行匹配

SPARQL的比对，在data graph找匹配

 Cypher语言

Gremlin语言匹配，过程化和match的语义匹配

子图匹配是在这些语言基础上的一个基础算子

经典算法：

Ullmann Algorithms：

将图转换为连接矩阵，将判断Q是否为G的子图问题转化为它们表达的连接矩阵的关系

存在一个矩阵（定义中所讲的内设函数f），矩阵为N（MA矩阵N*N）*M（MB矩阵M*M），对于Q中的每一个节点都要mapping到G中的节点，每一行中只有一个”1“，每一列中最多只有一个“1”

数学关系：

Q中的123对应G中的423

             

将MB中的423列取出来，并做一个行列变换，4对应第一列，2对应第二列，3对应第三列

若在MA中为1的位置在MC中的位置也为1，那么就认为f被找到，若找不到这样的MC就认为不存在这样的Q到G的一个子匹配

流程： 

①创建M矩阵，M为N*M的矩阵，若Q中的第i个节点和G中第j个节点一致且Q中节点的度数小于G中节点的度数，标1

②进化M为，因为要求一行只有一个1，转化为树搜索问题，有两个1，则随机把一个1划掉

满足一行只有一个1，一列最多只有一个1

③将②中得到的做测试，若该对应则代表成立，不成立则需要做回溯；若为列举问题，则成立也需要做回溯

Neighborhood Connection Pruning：

若Q中第i个节点v可以匹配G中第j个节点u，意味着v的任何一个邻居一定能匹配u的某一个邻居

匹配：

不匹配：

则将对应的1的位置变为0

使用公式进行验证 

VF2 Algorithms： 

将寻找子图同构问题转化为状态转换的过程：Q当中的某个节点i匹配到G当中的某个节点j的一个状态，若包含所有节点则为所有匹配，只包含部分节点为部分匹配

状态转换过程：

当S3时G包含整个子图Q，则认为找到了子图匹配

如何寻找状态转换：

假设S表示为一种中间状态，Q(S)和G(S)分别表示为在该状态下Q和G中所包含的节点，找到Q(S)和G(S)的所有邻居，表示为NQ(S)和NG(S)，寻找中间状态

提高效率产生的候选策略：

 引入节点的邻接点点集有交集，则可以引入

对于某一状态，可能由多个不同的中间状态转化过来，包含不同的顺序，不同顺序对应的空间不同

Backtracking search-based Methods：

对经典算法做总结，是对搜索路径带有回溯的DFS搜索，首先对于某一个点产生候选集，第二步定义一个匹配顺序，不同算法中有不同的匹配顺序，根据顺序一步一步将节点添加进子集进行匹配，后期使用不同的优化策略

Multi-way Join for Subgraph Match：

还是在寻找Q和G的子匹配问题

 T1表示所有能匹配u1u2之间的边，T2表示能匹配u1u3之间的边，T3表示匹配u2u3之间的边

 实际上，要寻找包含所有边的匹配，于是对表做一个自然连接，若结果大于0表明存在这样的子图匹配，并且其所有的子图匹配为R

对所有空间的一个BFS搜索

Binary Join：

构造一个二叉左深的树

Worst Case Optimal Join：

 以点为中心，寻找所有标签为x的节点，寻找节点的邻居，对每一行进行操作

 一定情况下减少中间结果的大小

图的相似性：

定义：

当两个图的公共部分很多时，可以说这两个图比较相似

①induced subgraph（推导子图）：给一个图G和一组点集S，将所有的两个端点都在S的边取出，有这些边和S点集组合成的图称为induced subgraph

②maximum common induced subgraph：C同构于G1和G2的某个induced subgraph，最大的含义表示包含的点的数目是最多的（不可以引入新的节点）

③maximum common edge subgraph：并不要求是推导子图，如下图，若为推到子图则cd边将被包含，而此时没有被包含，所以只是边图

Finding Maximal Common Induced Subgraph：

maximum clique-based algorithm(for MCIS)：转换为完全图问题，定义在G1和G2上的一个乘积图表示为G1*G2=G#，G#中的点集表示为G1中的一个点和G2中的一个点对，该点对中的两点标签是一致的，对应边满足：

 构成的每一个clique就是一个common induced subgraph

④Minimal Edit Distance：当两个图G1和G2相似时，通过多少步骤让两者转化为彼此，方法如下：

删除边，增加孤立点，连线 ，三个步骤

Node Substitution Semantic：

定义为一个match，从G1到G2的匹配是一个函数过程，点与点的匹配数目若不同，会引入虚拟点

在function f的作用下，找到G1中的每一个节点到G2的每一个节点的映射关系，在映射关系的作用下，若点与点的标签是一样的，则distance=0；若点与点的标签是不一样，distance=1。

虚拟点：与任何点的标签都不同

若点与点之间没有边，也认为有边，不过边的标签很特殊，记为

function f有很多，在所有的对应关系中选择最小值

最小f可以使得G1和G2的距离用GED表示 

A*-Alorithm：

被称为best-first-search

过程：给一个节点*（搜索的初始点）和一个目标点，寻找路径

寻找最小路径，最开始从初始点寻找每一条路径，用x表示某一种中间状态，针对于每一个中间状态都计算cost

cost称为f(x)，cost包括g(x)表示从原始节点到中间节点花费了多少cost，以及h(x)记为到最终节点还需要花费多少cost

估计h(x)：

h(x)代表中间状态到目标结点距离的估算

法1：

已被匹配

被已匹配的点推断出来的子图为和，

未被匹配

其中，计算h(x):

 ：两个点之间的距离，若标签一样则为“0”

：未匹配的点对之间的距离

图中的ABC与ABD三个点已经互相匹配上，N1包含ABC，N2包含ABD；若匹配，首先用 表示点标签，其次考虑和G1中任何一个点（ABC）之间的关系以及与G2（ABD）之间的关系，在所有的M2关系中找到最小的

用最小值来进行求和

考虑了下面要匹配的点和已匹配的点之间的拓扑关系 

 法2：

法3：

将图拆解为S1和S2

定义两个star的距离 ，从边到叶子，相当于之间的距离计算

然后建立二部图，在每一步中进行二部图匹配的过程

用P表示匹配，需要找到一个最小的匹配关系