大规模图数据管理与分析 课件 04-子图匹配

大规模图数据管理与应用子图匹配第四章2子图同构的定义3

子图同构的定义4查询图示例数据图示例

子图同构5子图同构：子图同构的判定问题（是否存在子图同构）为NP-Complete问题.子图同构的枚举问题（找到所有子图同构）为NP-hard问题.应用：图像识别和匹配，分子结构式搜索，以及图数据库等.(a)(b)(c)例子：分子结构式搜索查询图子图同构6

ABABA

子图同态BDCEBDCEBDCEA导出子图同构子图同构，而非导出子图同构子图同构算法的分类7基于搜索的方法8

基于搜索的方法9常见的过滤方法10

常见的过滤方法（LDF,NLF示例）11示例查询图示例数据图LDF和LDF+NLF过滤后的候选集Ullmann算法[1]12

Ullmann算法13查询图与数据图

Ullmann算法14

Ullmann算法15

Ullmann算法16Ullmann算法步骤Step

2:对于M中存在多个元素为1的行，依次选择其中1个元素，并且将其余元素置为0，然后再考虑下一行（这是经典的回溯算法)。100101000010100001000010100001000010100001000010

Ullmann算法17

VF2算法[2]18

ABC

ABC

A

VF2算法19

VF2算法20

GraphQL[3]21

GraphQL22

示例查询图示例数据图

GraphQL23

QuickSI[4]24

QuickSI25枚举深度为1时，用LDF深度大于1时，遍历上级节点匹配的邻居集合CFL[5]26

CFL（Top-down）27示例查询图示例数据图

CFL（Top-down）28示例查询图示例数据图

CFL（Top-down）29示例查询图示例数据图

CFL（Top-down）30示例查询图示例数据图

CFL（Bottom-up）31示例查询图示例数据图

CFL（Bottom-up）32示例查询图示例数据图

CFL（总览）33示例查询图示例数据图CFL34

CFL35

CECI[6]36

CECI（生成）37示例查询图示例数据图

CECI（生成）38示例查询图示例数据图

CECI（生成）39示例查询图示例数据图

CECI（生成）40示例查询图示例数据图

CECI（生成）41示例查询图示例数据图

CECI（生成）42示例查询图示例数据图

CECI（生成）43示例查询图示例数据图

CECI（过滤）44示例查询图示例数据图

CECI（总览）45示例查询图示例数据图CECI46

基于连接的方法47将图上的边视为二元关系表的元组，整个查询图的匹配结果可以通过连接查询图所有边匹配的关系表得到。ABABCCA

基于连接的方法（两两连接）48

基于连接的方法（最坏情况最优连接）49

u1u2u3v1v2v3

v4v2v3

知识图谱概述50基于连接的方法（最坏情况最优连接）51

基于连接的方法（最坏情况最优连接）52

基于连接的方法（最坏情况最优连接）AGMBound[7]53

XYRSXYTXY

0.50.50.5AGMBound[7]54

XYRSXYTXY

0.50.50.5

AGMBound55

LeapfrogTriejoin[8]56

参考文献57[1]JulianRUllmann.1976.AnAlgorithmforSubgraphIsomorphism.InJACM.[2]LuigiPCordella,PasqualeFoggia,CarloSansone,andMarioVento.2004.A(sub)graphisomorphismalgorithmformatchinglargegraphs.InTPAMI.[3]HuahaiHeandAmbujKSingh.2008.Graphs-at-a-time:querylanguageandaccessmethodsforgraphdatabases.InSIGMOD.[4]HaichuanShang,YingZhang,XueminLin,andJeffreyXuYu.2008.Tamingverificationhardness:anefficientalgorithmfortestingsubgraphisomorphism.InPVLDB.[5]FeiBi,LijunChang,XueminLin,LuQin,andWenjieZhang.2016.Efficientsubgraphmatchingbypostponingcartesianproducts.InSIGMOD.[6]BibekBhattarai,HangLiu,andHHowieHuang.2019.Ceci:Compactembeddingclusterindexforscalablesubgraphmatching.InSIGMOD.[7]AlbertAtserias,MartinGrohe,andD́anielMarx.2008.Sizeboundsand