图数据管理与挖掘-第四讲（子）图匹配算法（涵盖近似图匹配） 北京大学2021暑期

四、子图匹配

=======

PART 1: 子图同态

Graphs to Adjacent matrices

找这样的相当于f变换的M'

怎么找？basic idea：初始化一个矩阵，然后展开树搜索逐行修正矩阵，中间如得到不符合要求的矩阵则回溯。

Neighborhood Connection Pruning：如果邻居不匹配，则该节点不可能匹配

找同态的过程==状态转换的过程

多个中间状态可能由不同的路径到达，合适的顺序选择也是一种优化

以上都可以总结为带有回溯的DFS

边表joint

1. binary join做法（自然连接）
2. 不止一个pair同时进行匹配，预先计算N(v)（worst case optimal join）

Summary：

====

PART 2: Graph Similarity

图的相似性匹配。

定义相似度：最大共子图

induced subgraph（推导子图）视频里描述的定义应该可以specified为“点导出子图”（实际图论中边导出子图倒也很少见）

Maximum Common Induced Subgraph

• 共同导出子图：如果一个图C，同构于G1的点导出子图，也同构于G2的点导出子图，则称C为G1, G2的共同导出子图
• Maximum：含有端点最多的（……）

寻找极大共子图（MCIS）-基于极大团的算法

乘积图：新图每条边((ui,vi), (uj,vj))满足

• 点的标签相同
• (ui,uj)和(vi, vj)同时是存在or不存在的

乘积图中的极大团对应于极大共子图

结点替换语义：

f在二图之间做映射

对f的check，本质上是搜索问题（搜索空间中的寻路算法）

可以apply的一个算法：A*算法（best first）

其中，本问题的h(x)与中间状态的部分匹配情况有关

<后面讲了一堆启发式函数怎么选择的，以及如何利用机器学习来帮助这个过程的，但是我没有基础，实在听不下去了，下次一定>