图数据管理与挖掘-第四讲（子）图匹配算法（涵盖近似图匹配） 北京大学2021暑期
四、子图匹配
=======
PART 1: 子图同态
4-上 P1 - 00:04
4-上 P1 - 08:32
Graphs to Adjacent matrices
找这样的相当于f变换的M'
怎么找？basic idea：初始化一个矩阵，然后展开树搜索逐行修正矩阵，中间如得到不符合要求的矩阵则回溯。
Neighborhood Connection Pruning：如果邻居不匹配，则该节点不可能匹配
4-上 P1 - 27:19
找同态的过程==状态转换的过程
4-上 P1 - 35:44
多个中间状态可能由不同的路径到达，合适的顺序选择也是一种优化
4-上 P1 - 37:23
以上都可以总结为带有回溯的DFS
4-上 P1 - 38:56
边表joint
- binary join做法（自然连接）
- 不止一个pair同时进行匹配，预先计算N(v)（worst case optimal join）
=========================
