标签：HyperISO TKDE 匹配 Subgraph hq mu 超边 hd he

[TKDE 2022]HyperISO: Efficiently Searching Subgraph Containment in Hypergraphs

总结

涉及了合理的过滤和匹配顺序策略，第一个实现子超图匹配

简介

文章的目标是异构超图上的子图匹配。超图的定义是一条边可以连多个点的图，类似给点分了很多的group。

各类定义

符号定义表

超图的pairwise graph

总之就是在同一条超边连着的点之间添加该超边符号的边：

子超图

和正常的子图类似，也是点对应，超边对应。更具体地讲，给定一个query超图 \(HQ = (V_q, He_q, \Sigma_{hq}, \Omega_{hq})\) 和data超图\(HD = (V_d, He_d, \Sigma_{hd}, \Omega_{hd})\)。如果存在两个映射\(F':V_q \to V_{hs}\) 以及\(F'':He_q \to He_s\) 能把HQ映射成一个同构的子超图HS，且满足一下三个要求：

\(\forall \mu \in V_q, \sigma _q(\mu)=\sigma_d(F'(\mu))\), 也就是点对应
\(\forall he \in He_q, {\rm if}\ V(he)=\{\mu_1, \mu_2,\dots, \mu_k\}, \exists F''(he) \in He_d,\ {\rm satisfying} \{F'(\mu_1), F'(\mu_2), \dots, F'(\mu_k)\} \subset V(F''(he))\), 也就是超边里的所有点都要对应
\(\forall he \in He_q, \omega_q(he) \subset \omega_d(F''(he))\), 也就是超边也要对应

感觉二三两点换一下比较合适。

定理1：
如果Query超图是Data超图的子图，那么它们的pairwise图也会是子图关系。

Baseline

先转换成普通图，然后使用已经有的同构算法（CFL, DPiso， RapidMatch）得到Q的多组嵌入，最后确认其中的一个Q的嵌入能被转换成HQ的嵌入。这套baseline是从点下手的，但在超图中，利用好超边才能更有效率地实现匹配，毕竟一条边上可以有很多点。

模型

模型的整体框架：

前两行是把超图转换成权重图，这些权重图能够帮助模型进行初步的过滤。

第四行是生成 HQ 超边和点的匹配序列。判断先后的策略有两个，一个是超边候选的大小（应该是指同一种超边的数量），一个是超边内的点数。

最后就是枚举结果。其中包含两个匹配过程，先进行超边的匹配，匹配通过后再进行超边内点的匹配。

基于连接的过滤

定义2 超边邻居：
超边\(he_0\)的邻居集被定义为\(Nei(he_0)=\{he|V(he_0) \cap V(he) \neq \empty \}\)，所以超边的邻居还是超边。邻居的数量定义为\(deg(he_0)\)。这个定义下好像自己和自己是算数的。

权重图的定义：\(WG=(Vh, W_e, \Sigma, W(W_e))\)，其中\(Vh\)是超图中的超边识别的派生，\(We\)是两条至少共有一个点的超边形成的边组，\(\Sigma\)是\(Vh\)的标签组，这些标签由超边的点数得到，\(W(We)\)表示两个超边共享的点数组。具体可以看下图：

这两个图就是图1转换来的权重图。

其实就是点上的数字表示这个超边里的点数，权重边表示它们之间共用的点数。

初始候选：

对于一个query图中的超边\(he_q\)，用

\[C(he_q) = \{he_d \in He_d|\{deg(he_d) \geq deg(he_q) \}\} \cap \{|V(he_d)| \geq |V(he_q)|\} \]

来表示它的候选。就是data图中的超边里，点数和邻居数都比query图里的大的。

对于图3来说，\(hq_0\)和\(hq_2\)的候选一样，有\(hd\)的0,1,2,3,4,5,6，但\(hq_1\)和\(hq_3\)因为超边里的点变多了，候选就只有0,1,2,3,4,5了

这种比较naive的方法，自然没法过滤太多的结果。因此文中提出了connection-based 过滤技术。

权重筛选

如果两条超边\(hq_1\)，\(hq_2\)能在权重图\(WQ\)里形成权重边（有相同的点），那么它们匹配的\(hd_1\)和\(hd_2\)必然也能在权重图\(WD\)里形成权重边，并且\(C(hq_1) \cap Nei(hd_1) \neq \empty\)。多加这个判断可以进一步减少候选。

对照图4。假设已经知道\(hq_1\)匹配\(hd_1\)，如果用原始比大小的方法，得到的\(hq_2\)的候选为(a)中的结果，但如果加上权重图的判断，那么就会缩减到(b)中的结果。

具体的步骤：

对于一对候选\((hd_1 \in C(hq_1))\)，构建出靠数量判断得到的\(Nei(hd)\)和\(Nei(hq)\)之间的二部图。图(a)中只展示了\(hq_2\)，实际\(hq_0\)也会需要加入。
判断权重关系，比如\(we_q(hq_1,hq_2)\)要不大于\(we_d(hd_1,hd_n)\)。比如(b)中，就把6给拿走了，因为它们间的权重是0。

邻居筛选

比如图3中\(hq_1\)，\(hq_2\)可以匹配\(hd_1\)和\(hd_3\)（图4(b)里的情况），但\(hd_3\)的邻居\(hd_6\)并不能匹配\(hq_2\)的邻居\(hq_3\)，所以也得排除，就得到了图4(c)的结果

索引筛选

除了上述的两层筛选，文中还加入了一层索引筛选。超边之间的边除了能有权重，还可以根据共用的点标签标上索引：

之前已经是按\(hq_1 \to hd_1\)的前提来筛选了，按索引接着筛就是，\(hq_1\)和\(hq_2\)之间是B，但\(hd_1\)和\(hd_0\)之间是A，所以\(hd_0\)也被排除，最后就是图5(b)的结果。

这个算法实际就是在判断共用点是不是同一个标签的。

基于顶点的过滤

最naive的就是用点的label先筛一次，比如图1中的\(\mu_0\)是A，所以它的候选为\(C(\mu_0) = \{v_0, v_7, v_{11}, v_{15}\}\)。
不过，因为\(\mu_0 \in V(hq_0)\)，而且\(C(hq_0) = \{hd_0, hd_2, hd_4\}\)，所以筛选可以进一步缩小为\(C(\mu_0) = \{v_0, v_7, v_{11}\}\)。

候选优先级排序策略

最简单的方法就是看哪个超边的候选少，就先匹配那个。

继续用图1做例子。根据上面的筛选，\(C(hq_0) = \{hd_0, hd_1, hd_4\}\)三个，\(C(hq_1) = \{hd_1, hd_2, hd_4, hd_5\}\)四个，\(C(hq_2) = \{h_1, hd_2, hd_5\}\)三个， \(C(hq_3) = \{hd_0, hd_1, hd_3, hd_4\}\)四个。根据候选少的先（候选少的匹配过程中能让候选多的候选变少），所以匹配的顺序是\({hq_0, hq_2, hq_1, hq_3}\)，然后根据顺序递归地分配\(hd\)，匹配不上就返回重新匹配，直到全匹配上。

这样的做法忽视了超边之间的关联，容易出现冗余匹配。

顶点优先排序策略

这地方其实有问题，因为上面的筛选之后，比如\(hq_0\)在匹配\(hd_1\)的情况下，\(hq_2\)只能匹配\(hd_2\)。但这边又把所有可能全合在了一起再重新挨个匹配。所以真正的匹配操作是在之前做的那个二部图上实现。

双枚举策略

这块主要是为了节省内存开销。更具体地说，一个主回溯过程是用来获取匹配完成的HQ顶点，另一个是用来识别已经匹配完了的HQ的超边。

第一行的函数的意思是如果\(hq_1\)的顺序排在\(hq_2\)的前面，那\(hq_1\)里的点的顺序也会在\(hq_2\)里的点的前面。因为要对所有超边的点做匹配，所以一个点可以多次出现在排序里。

第二行的函数是记录已经排好序的点的顺序。

第十行的函数是用来记录某位置的点对应的超边。

算法四其实就是递归地在比对两条超边里的点是否匹配，匹配返回hd，不匹配就返回空。

算法三则是先规划好点的匹配顺序，再递归地比对。如果全比对完成了则不断地将所有递归结果合并；还没比对结束则先将当前匹配的点所对应的hq取出，并找还没被匹配，但是这个hq的点的候选的data图里的点，增加匹配规则。此外因为每个hq的点都不一定只被识别一次，所以如果遇到已经匹配过的点，那么会直接得到该点在当前的hq下匹配的hd，再去确认这个hq里的其他点是不是也和这个hd匹配。

大致思路明白，就是点级别上多加判断，减少重复的匹配。不过伪代码非常乱，细节上和文章都对不太上。比如这个Identified函数，只有判断没有更改，不知道是在哪会去记录。