圖數(shù)據(jù)管理與挖掘-第四講（子）圖匹配算法（涵蓋近似圖匹配） 北京大學(xué)2021暑期
四、子圖匹配
=======
PART 1: 子圖同態(tài)
Graphs to Adjacent matrices
找這樣的相當(dāng)于f變換的M'
怎么找？basic idea：初始化一個(gè)矩陣，然后展開(kāi)樹(shù)搜索逐行修正矩陣，中間如得到不符合要求的矩陣則回溯。
Neighborhood Connection Pruning：如果鄰居不匹配，則該節(jié)點(diǎn)不可能匹配
找同態(tài)的過(guò)程==狀態(tài)轉(zhuǎn)換的過(guò)程
多個(gè)中間狀態(tài)可能由不同的路徑到達(dá)，合適的順序選擇也是一種優(yōu)化
以上都可以總結(jié)為帶有回溯的DFS
邊表joint
- binary join做法（自然連接）
- 不止一個(gè)pair同時(shí)進(jìn)行匹配，預(yù)先計(jì)算N(v)（worst case optimal join）
Summary：
====
PART 2: Graph Similarity
定義相似度：最大共子圖
induced subgraph（推導(dǎo)子圖）視頻里描述的定義應(yīng)該可以specified為“點(diǎn)導(dǎo)出子圖”（實(shí)際圖論中邊導(dǎo)出子圖倒也很少見(jiàn)）
Maximum Common Induced Subgraph
- 共同導(dǎo)出子圖：如果一個(gè)圖C，同構(gòu)于G1的點(diǎn)導(dǎo)出子圖，也同構(gòu)于G2的點(diǎn)導(dǎo)出子圖，則稱(chēng)C為G1, G2的共同導(dǎo)出子圖
- Maximum：含有端點(diǎn)最多的（……）
尋找極大共子圖（MCIS）-基于極大團(tuán)的算法
乘積圖：新圖每條邊((ui,vi), (uj,vj))滿(mǎn)足
- 點(diǎn)的標(biāo)簽相同
- (ui,uj)和(vi, vj)同時(shí)是存在or不存在的
乘積圖中的極大團(tuán)對(duì)應(yīng)于極大共子圖
結(jié)點(diǎn)替換語(yǔ)義：
f在二圖之間做映射
對(duì)f的check，本質(zhì)上是搜索問(wèn)題（搜索空間中的尋路算法）
可以apply的一個(gè)算法：A*算法（best first）
其中，本問(wèn)題的h(x)與中間狀態(tài)的部分匹配情況有關(guān)
<后面講了一堆啟發(fā)式函數(shù)怎么選擇的，以及如何利用機(jī)器學(xué)習(xí)來(lái)幫助這個(gè)過(guò)程的，但是我沒(méi)有基礎(chǔ)，實(shí)在聽(tīng)不下去了，下次一定>
