VF3图同构算法

概述

聊聊子图同构算法 VF3。

（子）图同构/匹配：

图同构问题
- 问题描述：若$G_1 =(V_1,E_1)$和 $G_2=(V_2,E_2)$ 间存在一个双射 $f:V1\rightarrow V_2 $使得$(u,v)\in E_1$iff $(f(u), f(v)) \in E_2$，则$G_1$和 $G_2$同构。
  - $f$被称为同构映射。它既是注射（不同元素有不同映射）也是满射（每个元素都包含在可行域中）。
  - *(iff 表示当且仅当)
- 问题难度：不确定图同构问题是否为 NP 问题，但已证明图同构问题在 quasi-polynomial 时间内可解，即时间复杂度为 $O(e^{({log~n})^c})$。
子图同构问题
- 问题描述：在一个较大的目标图（Target Graph）中找出与较小的查询/模式图（Query/Pattern Graph）同构的（所有）子图。
- 问题性质：已证明为 NP-Complete 问题（比图同构更难）。
理解子图同构与图同构的思路：
1. 目标图和模式图大小相同时，子图同构问题坍缩为图同构问题。
2. 子图同构是允许执行删除（且cost = 0）的图同构算法。
图匹配问题

同构与匹配问题的关系：

图同构：只需判断两个图是否同构，但不需要找出同构映射。
图匹配：判断是否同构， 并找出一组满足同构条件的映射。
由于几乎所有算法都需要找出这个映射才能确认同构，因此后续将不做区分。

(近似求解)错误容忍的图匹配：

在一些应用中，人们愿意接受存在一定差异的两张图为问题的近似解，因此产生了错误容忍的图匹配问题
可以通过图编辑距离/相似度算法进行错误容忍的graph matching
- 编辑距离：不同的编辑操作对应不同的 Cost Func
- 图相似度算法：一个例子就是 $\sigma(G_1, G_2)=1-\frac{|mcs(G_1, G_2|}{max(|G_1|,|G_2|)}$
  - mcs => 最大公共子图；|G| 表示图 G 的结点个数
从错误容忍的角度理解图同构和子图同构的关系：子图同构是允许执行删除（且cost = 0）的图同构算法

（子）图同构典型思路

比较流行的处理（子）图同构问题的思路有 3 种：

树搜索（Tree Search）：在树形的搜索空间深度优先搜索，配合启发式规则剪枝。这种方法通过构造一个搜索树来表示状态空间，每个状态代表一个部分解。搜索通常以深度优先的顺序进行，使用启发式方法来避免探索无用的部分。
- 典型算法：Ullmann, VF series, RI/RI-DS
约束传播（Constraint Propagation）：这种方法将子图同构问题视为一个约束满足问题 (CSP)，目标是找到满足所有互相制约的变量赋值。这些变量是模式图的节点，而约束是这些节点之间的关系需要与目标图中的对应节点匹配。这类算法维护每个模式节点的兼容节点域，并通过传播局部约束（如节点或边的一致性）来缩小域，最终缩减候选匹配。
- 典型算法：McGregor, BVCR
图索引（Graph Indexing）：这种方法源于图数据库应用，目标是从大量图中检索出包含特定模式的图。这类算法通过建立索引结构来快速检查目标图中是否存在模式，通常不需要加载整个目标图，从而过滤掉不可能的目标。
- 典型算法：GADDI, TurboISO

子图同构算法 VF3
VF3 概述

VF3 是典型的树搜索算法，其在 VF2Plus 的基础上进行了一系列的改进，擅长处理大型（指 10000+个节点）和密集图。
算法需要解决的核心问题是: 1. 如何将所有搜索情况组织成树以避免重复访问；2. 在回溯算法中如何最大程度剪枝。

VF3 关键特性和改进点：

状态空间表示（State Space Representation）
1. VF3 继承了 VF2 的状态空间表示方法，其中每个状态代表一个部分的顶点映射。VF3 使用深度优先搜索策略来遍历这个状态空间。
启发式搜索 + 剪枝（Heuristic Search and Pruning）
1. VF3 算法引入了更精细的启发式方法来选择下一个匹配的顶点对，这有助于减少搜索空间并提高算法效率。能够显著减少在大型和密集图中的计算复杂度。
图预处理和候选选择（Graph Preprocessing and Candidate Selection）
1. VF3 在搜索开始前进行图的预处理，计算可能的候选顶点集合，以便在搜索过程中快速决定候选顶点。
2. 算法还改进了候选节点的选择过程，通过对图中顶点的动态分类和快速筛选来优化匹配步骤。
VF 算法基础

我们的任务是在图 $G_1=(V_1,E_1)和G_2=(V_2,E_2)$间寻找一个同构映射 $M:V_1\rightarrow V_2$。

State Space Representation (SSR)

SSR （状态空间表示）是一种在图匹配算法中用来表示所有可能的节点匹配状态的结构。

SSR 中的每个状态 s 代表同构映射 M 的部分映射 $\widetilde M(s) $，满足 $\widetilde M(s)⊆ M$。

为了表示映射 $\widetilde M(s) $，VF3 算法根据节点是否已经在映射中，将节点分为 3 个不同的集合。

暂时无法在飞书文档外展示此内容

$\color{red}{\widetilde M_1(s)}$：核心集。存放$G_1$中已经匹配好的节点，保证集合中的节点满足同构映射
$\color{blue}{\widetilde{\mathcal{T_1}}(s)}$：可行（候选）集。保存与${\tilde M_1(s)}$直接相连的节点，它们是当前有可能加入核心集的节点
$\widetilde{V_1}(s)$：存放$G_1 $中的不在前两个集合中的其他节点
$G_2$也存在对应的三个集合

树状结构搜索 SSR

前面提到，状态 s 代表一种特定的顶点映射情况。不同状态间可以通过增减节点得到，因此状态的空间表示（SSR）天然为图结构。

在 VF3 算法中，为了不重复访问相同的状态，作者把 SSR 组织成一棵树，其中每个节点代表一个状态，每条边则代表一个可能的状态转换。

根节点代表一个空的匹配（即没有任何顶点映射），每个叶子节点代表一种完整的匹配方案。
每个状态可以通过添加一组新的节点对来扩展到下一个状态，或者通过去掉上一次加入匹配的节点对来回溯到上一个状态并重新探索。

为了将 SSR 组织成树，我们需要对 $G_1$的节点集 $V_1$排序，组成一个节点探索序列 $N_{G_1}$。

$N_{G_1}$的核心思想是优先探索受到更多约束和稀有的节点（以减少搜索空间大小）。
- $G_1$中节点的稀有程度，对应在$G_2$中找到一个满足同构映射的节点的难度，节点 u 的稀有程度定义为（图同构情况下，子图同构则为 $d’≥d(u)$）：
  - $P_f(u)=P_l(\lambda_{V_1}(u)) \cdot \Sigma_{d’=d(u)}P_d(d’)$.
  - 稀有程度$P_f$由 $P_l$（找到标签为 $l$的节点的难度）和 $P_d$（找到度为 d 的节点的难度）决定。
  - $\lambda_V(u)$是标签分配函数，输出节点 u 的标签。
- 节点 u 的约束程度，取决于它与多少个已经处于$N_{G_1}$中的节点间有边，用映射度$d_M(u)$表示（就是度，但只考虑与$N_{G_1}$中的节点的连接）。
因此，计算$N_{G_1}$的方式为对节点多级排序，排序优先级分别是：
- 节点的$d_M(u)$
- 稀有程度$P_f$
- 度

（若这三项均一样，则会随机选一个节点放入序列中）

在当前条件下，我们可以这样简单的描述 VF3 算法的流程：

每次向状态$s_c$中添加一组节点$(u_n,v_n)$，形成一个新的状态$s_n=s_c\cup(u_n,v_n)$，其中来自模式图$G_1$的节点$u_n$由 $N_{G_1}$决定，$v_n$则是由算法动态选择。
重复第一步，直到找到包含所有节点的理想状态或者证实匹配不存在。
可行性检查

事实上，我们不会直接将候选节点对 $(u_n,v_n)$加入状态 s 中，而是先对它们进行可行性检查。

可行性检查由两个部分组成：

$F_s$ （Semantic Feasibility）: 语义可行性，检查两个节点（以及它们之间的边）的标签是否一致。如果节点或边的标签不匹配，这对节点就不能被考虑作为当前搜索状态的一部分
$F_t$ （Structural Feasibility）: 结构可行性，检查两个节点的邻居节点是否能够满足同构的要求
- $F_t$ 由核心规则$F_c$（core rule）和两级前瞻规则$F_{la1}$， $F_{la2}$（1-level and 2-level lookahead rules）构成

$F_s$ 简单来说就是只让标签相同的节点通过，$F_t$ 则较为复杂，是确保映射保持结构一致性和提升算法效率的关键部分。

结构可行性 Ft

$F_t$ 的核心目标是：确保所建立的节点对不仅在当前步骤中结构上可行，而且不会在将来的几个步骤中导致映射失败。

通过分类函数 ψ 划分等价类

设置一个分类函数 $\psi:V_1∪V_2\rightarrow C=c_1,…,c_q; $ （等价类的数量 q 和分类函数可以自己设置）

分类函数会将节点划分成 q 个等价类，它只需要满足：
- 若节点 u 和 v 在同构映射中是一组匹配的节点对，则 u 和 v 必须在同个等价类中。
作者并未给出端到端的划分方案，但可以利用这些信息指导划分：
- 节点的标签（可以直接拿来当分类函数，也 f 可以完全不使用）
- 节点的度或其他的邻接信息
- 上下文或领域知识
进一步的，将${\widetilde{\mathcal{T_1}}(s)}$根据等价类进一步分成 q 个：$\widetilde T_1^{c_i}(s)$ （表示既在可行集中，又属于第 i 个等价类的节点），类似的也可以定义$\tilde V_1^{c_i}(s)$。划分等价类是为了计算结构可行性$F_t$ 。

结构可行性 Ft

结构可行性函数 $F_t$ 由三个部分组成，分别是 $F_c$，$F_{la1}$，$F_{la2}$，表示为：

$F_t(s_c,u_n,v_n)=F_c(s_c,u_n,v_n)\wedge F_{la1}(s_c,u_n,v_n)\wedge F_{la2}(s_c,u_n,v_n)$

核心规则 $F_c$：
1. $F_c(s_c,u_n,v_n)\Leftrightarrow\forall u^{\prime}\in adj_1(u_n)\cap\widetilde{M}_1(s_c)\quad\exists v^{\prime}=\widetilde{\mu}(s_c,u^{\prime})\in adj_2(v_n)\\wedge\forall v^{\prime}\in adj_2(v_n)\cap\widetilde{M}_2(s_c)\quad\exists u^{\prime}=\widetilde{\mu}^{-1}(s_c,v^{\prime})\in adj_1(u_n)$
2. 核心目标：确保当前这组节点的加入不会马上导致结果错误。
3. 假设当前考虑的节点组 $(u_n,v_n)$，核心规则 $F_c$对所有与$u_n$相邻且已经在映射中的节点$u’$，检查$u’$对应的匹配节点$v’$是否与$v_n$相邻。
前瞻性规则（Lookahead Rules $F_{la1}$ and $F_{la2}$）:

回顾基础概念中的介绍，SSR 中的每个状态 s 对应映射 $\widetilde M(s) $，VF3 算法根据节点是否已经在映射中，将节点分为 3 个不同的集合，分别是 $\widetilde M(s),\widetilde{\mathcal{T}}(s),\widetilde V(s)$，对于当前考虑的节点组 $(u_n,v_n)$（它们在可行集${\widetilde{\mathcal{T}}(s)}$中），在创建新状态 $s_n=s_c\cup(u_n,v_n)$之前，$(u_n,v_n)$需要满足两级前瞻性规则：

一级前瞻规则 $F_{la1}$

$F_{la1}(s_c,u_n,v_n)\iff F_{la1}^1(s_c,u_n,v_n)\wedge\ldots\wedge F_{la1}^q(s_c,u_n,v_n)$

对于第 i 个等价类，一级前瞻规则 $F^i_{la1}$定义为：

$F_{la1}^i(s_c,u_n,v_n)\iff|adj_1(u_n)\cap\widetilde{\mathcal{T}}_1^{c_i}(s_c)|\leq|adj_2(v_n)\cap\widetilde{\mathcal{T}}_2^{c_i}(s_c)|$

核心目标：提前识别和排除可能会未来几步中违反同构条件的节点。
查看可行集${\tilde{\mathcal{T_1}}(s)}/{\tilde{\mathcal{T_2}}(s)}$，对于$u_n$（模式图）的在当前可行集内且属于第 i 个等价类的邻居数量不能多于$v_n$（目标图）的（同属于 i 且在可行集内的邻居）数量
对于图同构问题，满足条件的邻居数量应该相同

二级前瞻规则 $F_{la2}$：

$F_{la2}(s_c,u_n,v_n)\iff F_{la2}^1(s_c,u_n,v_n)\wedge\ldots\wedge F_{la2}^q(s_c,u_n,v_n)$

对于第 i 个等价类，二级前瞻规则 $F^i_{la2}$定义为：

$F_{la2}^i(s_c,u_n,v_n)\iff|adj_1(u_n)\cap\widetilde{V_1}^{c_i}(s_c)|\leq|adj_2(v_n)\cap\widetilde{V_2}^{c_i}(s_c)|$

核心目标：在一级规则的基础上，加入更远一级的节点关系，进一步剪枝。
类似一级前瞻规则 $F_{la1}$，查看$u_n$既不在映射$\widetilde M_1(s) $中也不在可行集$\widetilde{\mathcal{T_1}}(s)$中的邻居节点，其数量不能多于$v_n$对应的此类邻居节点（图同构问题则也为相等）。

注意：对于有向图，需要分别考虑入边和出边。

VF3 算法的改进

VF3 算法在 VF2Plus 算法的基础上主要有两点改进：

改进模式图的预处理 (State Space Precalculation)
改进候选节点对的选择方式 (Candidate Selection)
状态空间预计算（State Space Precalculation ）

预处理的对象均是对模式图$G_1$。

根据$N_{G_1}$预计算${\widetilde M_1(s)}$与${\widetilde{\mathcal{T_1}}(s)}$

2.2.1 中提到，为了按照树状结构搜索SSR，我们定义了节点探索序列$N_{G_1}$，它是$G_1$中所有节点的一个排列。在算法迭代过程中，$u_n$总会按照$N_{G_1}$的顺序被匹配，因此我们可以提前计算每一层 SSR 的${\widetilde M_1(s)}$与${\widetilde{\mathcal{T_1}}(s)}$。

$\widetilde{\mathcal{T}}_1^{c_i}(s)$的存储优化：
- 若按照定义实现$\widetilde{\mathcal{T}}_1^{c_i}(s)$，则其需要$O(N_1^{2})$的空间来存储。
  - 假设$G_1$有$N_1$个节点，由于我们每次往状态中添加一个节点，因此 SSR 组成的树总共有 $N_1$层，每一层都需要维护$\widetilde{\mathcal{T}}_1^{c_i}(s)$。
- 结合可行集$\widetilde{\mathcal{T}}_1^{c_i}(s)$的定义，由于 SSR 每一层对应的$u_n$是确定的，因此$G_1$中的每个节点总会在一个固定的 SSR 层加入可行集中(它的第一个邻居加入同构映射时)，并在一个确定的时间离开可行集(它自己加入同构映射或算法退出)，在此过程中，它将持续被视为候选节点。
- 由此，算法对于每个节点，只记录其加入$\widetilde{\mathcal{T}}_1^{c_i}(s)$和退出$\widetilde{\mathcal{T}}_1^{c_i}(s)$的 SSR 层级，这样总体$\widetilde{\mathcal{T}}_1(s)$的空间开销变为$O(N_1)$。

近一步的，由于可行性检查都是在比集合大小，因此实现时，作者也不会真的维护可行集，而是采用对不同层，不同等价类，仅维护其大小的方式。

维护父节点树 (parent tree)

维护父节点树是预处理的另一个关键部分，算法会为每一个节点指定一个”父节点”。

核心目标：辅助后续的候选节点选择和状态回溯。
父节点树根据 $N_{G_1}$生成，对于$N_{G_1}$中的每个节点，算法检查其所有邻接节点，并基于它们在$N_{G_1}$的前后顺序来设置父子关系：
- 一个节点的父节点是在$N_{G_1}$中排在它前面且与它直接相连的第一个节点。
- 第一个匹配节点或孤立节点没有父节点。
显然，父节点树只是一个决策支持工具，我们不用真的创建一颗树，只需要保存每个节点的父节点，因此使用 KV 逻辑存储（节点作为 key，其父节点为 value）。

在需要回溯时，可以通过父节点信息迅速找到上一合法状态，撤销当前的选择，尝试其他可能的节点匹配。

候选节点选择（Candidate Selection）

在每一层 SSR 中，算法都会选取一组候选节点$(u_n,v_n)$，并对这组节点进行可行性检查。

其中模式图$G_1$的候选节点$u_n$已经由 $N_{G_1}$给出，因此Candidate Selection 的核心目标是确定目标图$G_2$的候选节点$v_n$。
主要原理是通过分析$G_1$候选节点$u_n$的父节点来缩小候选节点$v_n$的选择范围：
- 如果在父节点树上存在一个父亲节点 $\text{Parent}(u_n)$，则找到上一轮匹配中的$G_2$节点 $\tilde v$，在 $\tilde v$的邻居中选择第一个没有匹配且和 $u_n$为同一等价类的节点。表示为：

$R_2^{adj}(s_c,\psi(u_n),\widetilde{v})={v_n\in V_2:v_n\in adj_2(\widetilde{v})\cap R_2(s_c,u_n)}.$

如果不存在父节点(第一个节点或者孤立节点），则去掉邻居的条件，在$G_2$中随机选择一个与$u_n$为同一等价类的节点。表示为：

$R_2(s_c,\psi(u_n))={v_n\in V_2:v_n\notin\widetilde{M}_2(s_c)\wedge \psi(v_n)=\psi(u_n)}.$

算法流程概括为：

VF3 算法总结

VF3 算法总共由 3 个模块(阶段)组成：

预处理阶段：
1. 节点排序：基于节点的稀有性和约束程度(连接度)，为模式图$G_1$中的节点确定探索序列 $NG_1$
2. 状态空间预计算：为$G_1$中的每个节点预计算可能的候选节点集合，基于节点的属性和结构特征，确定$G_2$中哪些节点可能与之匹配。
匹配阶段：
1. 递归搜索：从$G_1$的第一个节点开始，递归地尝试匹配$G_2$中的候选节点。
2. 候选选择：根据是否存在父节点，为当前$G_1$候选节点 u 选择$G_2$中的候选节点 v。
3. 可行性检查：对每组候选节点，检查结构和语义的可行性，确保新增的节点匹配不违反已有的匹配结构，且在有继续探索的潜力。
4. 回溯：如果当前节点没有找到合适的匹配或后续匹配失败，则回溯到上一节点，尝试其他候选节点。
终止条件：所有节点都匹配上，或无法继续探索且无法回溯

（待补充）并发 & 多线程

VF3 的作者在后续更新了详细的性能分析和支持并发的 VF3 算法：

Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3
Comparing performance of graph matching algorithms on huge graphs
A Parallel Algorithm for Subgraph Isomorphism

实验结果

.grf test case的布局：

暂时无法在飞书文档外展示此内容

si2_rnd_eta04_m1000_00.grf

Case info: 1000 个节点，399,770 条边，节点属性全部设置为 1

结果 (处理时间/s)：

正确同构：0.0513868

子图同构：363.737 (第一个解)；3826.8 (全部解)

Benchmark	Samples	Edges	Attributes
rand4	1000	99,904	1 (等权)
si2_rnd_eta04	1000	399,770	1
rnd_ldg1	2500	1,248,179	1

汇总了直接匹配、修改属性、修改边的数量之后的图同构算法结束时间(second)

Benchmark	同构(无修改)	修改属性	修改边
rand4	1.20e-02	3.68e-03	1.27e-02
si2_rnd_eta04	5.51e-02	9.39e−03	2.11e-08
rnd_ldg1	1.91e-01	3.32e-02	2.08e-08

Q & A:

Q1：VF3 算法的评价？

A：VF3 算法和所有其他的 Tree Seach 方法一样，属于一种特别版本的 A* 搜索，即在树形结构上 dfs + 回溯，同时结合启发式策略剪枝。VF3 算法的设计精巧，因此展现了较强的表现，尤其擅长子图同构任务。虽然用 VF3 无法直接处理 LVS 规模的问题，但其可行性规则的设计值得参考。

Q2: 在处理图同构时，VF3 总能找到正确的解吗？算法退出时是不是代表两张图不同构？

A：是的，总能找到正确的解，退出则表示两张图不同构。虽然进行了大量剪枝，但是算法实际上还是能覆盖 G1 和 G2能匹配的所有情况，不过最坏情况下有可能需要从最后一步回溯到第一步。

Q3：可行集$\widetilde{\mathcal{T}}^{c_i}(s)$的理解

A: 在匹配过程中，G1 的候选节点总是根据$N_{G_1}$确定的，而 G2 的候选节点总是由候选选择确定的。

$\widetilde{\mathcal{T}}_1^{c_i}(s)$和$\widetilde{\mathcal{T}}_2^{c_i}(s)$的唯一作用就是进行可行性检查，无关节点选择。

Q4: VF3 的复杂度？

A: 最好情况下为线性，最坏情况下为指数级。VF3 算法的时间和空间复杂度与图的大小、密度、图的结构以及图中顶点和边的分布均有关。

作者没有给出官方时间复杂度，考虑最坏情况，即所有启发式规则均失效或为完全图，时间复杂度应当为$O(N^2)$~$O(N!N) $。通常在实际应用中，通过各种启发式优化和剪枝策略，其平均性能会比最坏情况表现得更好，但
考虑到网表比较的问题规模，一个较快的算法应当对网表进行拆分，采用分布式 + 并发执行。

（待补充）Implementation

VF3 算法的实现有很多现实考虑，因此代码和论文并不会严格对应。本段简要介绍官方实现中需要使用的数据结构和算法流程。

GitHub - MiviaLab/vf3lib: VF3 Algorithm

*(代码仓库是最新的版本，因此支持后续的并行优化等特性)

另外，NetworkX 封装了 VF2++算法，可以实现即插即用的图同构检测：https://networkx.org/documentation/stable/reference/algorithms/isomorphism.html

必要数据结构
Graph 的表示

VF3 使用 ARGraph 表示属性关系图（Attributed Relational Graph）

typedef std::vector<nodeID_t> NodeVec;
typedef std::vector<Edge> EdgeAttrVector;   
typedef std::vector<Node> NodeAttrVector;

// 基本属性
uint32_t n;                   /**< 节点数量 */
uint32_t n_attr_count;        /**< 不同节点属性的数量 */
uint32_t e_attr_count;        /**< 不同边属性的数量 */
uint32_t e_count;             /**< 边的总数 */
uint32_t e_out_count;         /**< 出边的总数 */
uint32_t e_in_count;          /**< 入边的总数 */
uint32_t node_label_count;    /**< 节点标签的数量 */
uint32_t max_deg_in;          /**< 最大入度 */
uint32_t max_deg_out;         /**< 最大出度 */
uint32_t max_degree;          /**< 最大度数 */

// 节点 & 边的属性
std::vector<Node> attr;                        /**< 节点属性 */
std::vector<EdgeAttrVector> in_attr;           /**< 入边属性 */
std::vector<EdgeAttrVector> out_attr;          /**< 出边属性 */

// 邻接信息
std::vector<NodeVec> in;                       /**< 入边相连的节点 */
std::vector<NodeVec> out;                      /**< 出边相连的节点 */

// 功能：边的检查和获取；检查两节点之间是否存在边，并获取特定节点的入边和出边
bool HasEdge(nodeID_t n1, nodeID_t n2) const;
bool HasEdge(nodeID_t n1, nodeID_t n2, Edge &pattr) const;
nodeID_t GetInEdge(nodeID_t node, uint32_t i) const;
nodeID_t GetInEdge(nodeID_t node, uint32_t i, Edge& pattr) const;
nodeID_t GetOutEdge(nodeID_t node, uint32_t i) const;
nodeID_t GetOutEdge(nodeID_t node, uint32_t i, Edge& pattr) const;

// 功能：边遍历；遍 历特定节点的所有入边、出边或所有边，并对每条边应用访问者模式进行处理。
void VisitInEdges(nodeID_t node, edge_visitor vis, param_type param);
void VisitOutEdges(nodeID_t node, edge_visitor vis, param_type param);
void VisitEdges(nodeID_t node, edge_visitor vis, param_type param);

VF3 使用 ARGLoader 加载图数据，从而将图的构建过程与具体的数据格式解耦。ARGLoader 提供了一组标准接口，任何实现了这些接口的加载器都可以用于构建 ARGraph。这促进了代码复用，不同的图加载器可以共享相同的图构建逻辑。

ARGLoader的主要功能包括：

virtual uint32_t NodeCount() const 节点计数。
virtual Node GetNodeAttr(nodeID_t node) 获取节点属性。
virtual uint32_t OutEdgeCount(nodeID_t node) const 出边计数。
virtual nodeID_t GetOutEdge(nodeID_t node, uint32_t i, Edge *pattr) 获取出边信息。返回指定节点的第 i 条出边的目标节点，并获取该边的属性。

State 的表示

typedef uint32_t nodeID_t
typedef uint8_t nodeDir_t;
typedef vflib::VF3LightSubState<data_t, data_t, vflib::Empty, vflib::Empty> state_t;
const nodeDir_t NODE_DIR_NONE = 0;
const nodeDir_t NODE_DIR_IN  = 1;
const nodeDir_t NODE_DIR_OUT = 2;
const nodeDir_t NODE_DIR_BOTH = 3;

// 图的引用和比较函数
ARGraph<Node1, Edge1> *g1;
ARGraph<Node2, Edge2> *g2;

// 重载，用来比较节点和边
NodeComparisonFunctor nf;  
EdgeComparisonFunctor ef;

// 方向性标识
nodeDir_t* dir;    // 表示节点的方向（无、入、出、双向）
nodeID_t* predecessors;    // 每个节点在有序序列中的前驱节点。

// 核心集
uint32_t *core_len_c;
nodeID_t *core_1;
nodeID_t *core_2;

// 终端集大小（Terminal Set Sizes）
uint32_t t2in_len, t2both_len, t2out_len;     // 第二个图的终端集大小
uint32_t *t1in_len, *t1both_len, *t1out_len;     // 第一个图在每个深度级别的终端集大小
uint32_t *t2both_len_c, *t2in_len_c, *t2out_len_c;     // 第二个图每个类的终端集大小
uint32_t **t1both_len_c, **t1in_len_c, **t1out_len_c;     // 第一个图每个深度级别和每个类的终端集大小

// 终端集更新
uint32_t *termout2_c, *termin2_c, *new2_c;     // 用于更新第二个图的终端集大小
uint32_t **termout1_c, **termin1_c, **new1_c;     // 用于更新第一个图的终端集大小
uint32_t *termin1, *termout1, *new1;     // 第一个图的终端集计数

// 节点集合
nodeID_t *in_2, *out_2;
int64_t last_candidate_index;

// 类和类别相关
uint32_t *class_1, *class_2;
uint32_t classes_count;

核心集（Core Set）就是论文中的核心集${\widetilde M(s)}$，它负责记录匹配进展和指导后续匹配。
终端集（Terminal Set）是文中可行集${\widetilde{\mathcal{T}}(s)}$ 的实现，但逻辑有变化。
- 状态跟踪：终端集帮助算法在匹配过程中跟踪每个节点的当前状态（如是否在核心集中，是否有入边或出边等），终端集在每个深度级别上动态更新。
- 核心：在状态转换时，只需更新大小，而不需要重新计算整个集合。
  - 维护集合长度一致性而非内容一致性： 在匹配过程中，只需要知道某个节点集合是否为空（长度是否为零）或者其大小相对于另一个集合的大小来决定下一步的操作。通过跟踪集合的长度，可以简化状态管理和更新的逻辑。
- 终端集有三种类型：
  - 入边终端集（In-terminal set）：跟踪每个节点的入边集合。
  - 出边终端集（Out-terminal set）：跟踪每个节点的出边集合。
  - 双向终端集（Both-terminal set）：跟踪同时存在入边和出边的节点集合。
- 一维数组 & 二维数组：
  - 一维数组的项目是维护了不同等价类的大小，
    - 如t2out_len_c[class]，表示第二个图类别 class 的节点的出边终端集大小。
  - 二维数组的项是既维护了不同等价类，也维护不同层的集合大小：
    - 如t1out_len_c[level][class]，表示在第一个图的深度级别 level 下，类别 class 的节点的出边终端集大小。

对State的操作

// public 
bool NextPair(nodeID_t *pn1, nodeID_t *pn2,
    nodeID_t prev_n1 = NULL_NODE, nodeID_t prev_n2 = NULL_NODE);
bool IsFeasiblePair(nodeID_t n1, nodeID_t n2);
void AddPair(nodeID_t n1, nodeID_t n2);
inline bool IsGoal() const { return core_len == n1; };
bool IsDead() const;
// private
void BackTrack();
void ComputeFirstGraphTraversing();
void UpdateTerminalSetSize(nodeID_t node,  // 换行
nodeID_t level, bool* in_1, bool* out_1, bool* inserted);

NextPair：查找下一个可行的节点对，基于当前状态更新候选节点。
IsFeasiblePair：检查节点对是否可以加入到当前状态中。
AddPair：将节点对添加到核心集 M 中，并更新状态。
IsDead：检查当前状态是否死节点，即是否不再可能找到匹配。
BackTrack：回溯操作，撤销上一次添加的节点对。
ComputeFirstGraphTraversing：初始化第一个图的遍历顺序和终端集大小，确保算法从最优的起点开始，并设置每个节点的初始状态。
UpdateTerminalSetSize：在匹配过程中动态更新终端集的大小和状态，确保终端集的计数器和节点状态在每一步都保持最新。这两个方法共同作用，支持VF3算法的高效执行。

VF3 算法 workflow
初始化（命令参数解析&配置，信号处理，读取图数据，初始化匹配引擎）

命令参数解析，参数实例 opt 包含了初始化需要的几乎所有参数

Options opt;
if(!GetOptions(opt, argc, argv)) {exit(-1);}
1
2
3
4
5
6
7
8
9
10
11
12

- 加载图数据（读取文件，通过 ARGLoader 构造为 ARGraph）

  - ```C++
    // Pattern & Target 
    typedef int32_t data_t
    std::ifstream graphInPat(opt.pattern);
    std::ifstream graphInTarg(opt.target);
    ARGLoader<data_t, Empty>* pattloader = CreateLoader<data_t, Empty>(opt, graphInPat);
    ARGLoader<data_t, Empty>* targloader = CreateLoader<data_t, Empty>(opt, graphInTarg);
    ARGraph<data_t, Empty> patt_graph(pattloader);
    ARGraph<data_t, Empty> targ_graph(targloader)

属性关系图（Attributed Relational Graph，ARG）是一种图形化表示方法，用于描述对象之间的属性和关系。其将对象表示为节点，对象之间的属性和关系表示为边。节点上通常带有属性信息，而边则表示对象之间的关联或依赖关系。

预处理（匹配引擎初始化，快速检查，节点分类，构造节点序列$NG_1$）

初始化匹配引擎 & FastCheck

typedef int32_t data_t
typedef vflib::VF3LightSubState<data_t, data_t, vflib::Empty, vflib::Empty> state_t
MatchingEngine<state_t>* me = CreateMatchingEngine(opt);
FastCheck<data_t, data_t, Empty, Empty> check(&patt_graph, &targ_graph);

FastCheck 能够排除显然不同构的 Case，对于图同构问题，FastCheck能够排除这些情况：
- 节点/边的数量不同；入边/出边的数量不同（有向图）
- 最大度不同；最大入度/出度不同（有向图）
- 节点属性明显不同
节点分类

std::vector<uint32_t> class_patt;
std::vector<uint32_t> class_targ;

NodeClassifier<data_t, Empty> classifier(&targ_graph);
NodeClassifier<data_t, Empty> classifier2(&patt_graph, classifier);
class_patt = classifier2.GetClasses();
class_targ = classifier.GetClasses();

构造模式图的节点序列$NG_1$，这一步的逻辑和论文一样，作者用优先队列 (堆)实现

VF3NodeSorter<data_t, Empty, SubIsoNodeProbability<data_t, Empty> > sorter(&targ_graph);
std::vector<nodeID_t> sorted = sorter.SortNodes(&patt_graph);

std::vector<nodeID_t> SortNodes(ARGraph<Node, Edge>* pattern)
{
    uint32_t nodeCount;
    uint32_t i;
    nodeCount = pattern->NodeCount();
    std::vector<nodeID_t> nodes_order; //Output vector with sorted nodes
//We use two structures the first used to quickly edit the deg_m of a node by its index
//The second to perform a priority queue by means a max heap
    std::vector<VF3SortingNode*> nodes(nodeCount);
    std::vector<VF3SortingNode*> candidates; //Node candidate for the addition
    std::vector<VF3SortingNode*>::iterator candidate_it;
    std::vector<VF3SortingNode*>::iterator max_node;
    //Initializing the node vector for sorting

    for (i = 0; i < nodeCount; i++) {
        nodes[i] = new VF3SortingNode(i, pattern->EdgeCount(i), probability->GetProbability(pattern, i));
    }

    uint32_t n = 0;
    candidate_it = std::min_element(nodes.begin(), nodes.end(), CompareSortingNodeProbability());
    nodeID_t top = (*candidate_it)->GetID();
    AddNodeToSortedSet(pattern, top, n, nodes, candidates, nodes_order);

    //Getting the first node of the heap
    for (; n < nodeCount - 1; n++) {
        candidate_it = std::min_element(candidates.begin(), candidates.end(), CompareCandidates<VF3SortingNode>());

        //Searching for remaining user
        if ((*candidate_it)->IsUsed())
        {
            candidate_it = std::find_if(nodes.begin(), nodes.end(), FindUnused());
            AddNodeToSortedSet(pattern, (*candidate_it)->GetID(), n, nodes, candidates, nodes_order);
        }
        else if (candidate_it != candidates.end())
        {
            AddNodeToSortedSet(pattern, (*candidate_it)->GetID(), n, nodes, candidates, nodes_order);
        }
    }
    return nodes_order;
}

匹配过程（从初始状态 s0 开始搜索）

1 2	`state_t s0(&patt_graph, &targ_graph, class_patt.data(), class_targ.data(), classes_count, sorted.data()); me->FindAllMatchings(s0); //MatchingEngine<state_t>* me`

FindAllMatchings的逻辑和论文一样：

typedef std::vector<std::pair<nodeID_t, nodeID_t> > MatchingSolution;
MatchingVisitor<VFState> *visit;
std::vector<MatchingSolution> solutions;
bool storeSolutions;

virtual bool FindAllMatchings(VFState &s)
{
    if (s.IsGoal()) {
        if (storeSolutions) {
            MatchingSolution sol;
            s.GetCoreSet(sol);
            solutions.push_back(sol);
        }
        if (visit) {
            return (*visit)(s);
        }
        return false;
    }

    if (s.IsDead()) {
            return false;
    }

    nodeID_t n1 = NULL_NODE, n2 = NULL_NODE;
    while (s.NextPair(&n1, &n2, n1, n2)) {
        if (s.IsFeasiblePair(n1, n2)) {
            VFState s1(s);
            s1.AddPair(n1, n2);
            if (FindAllMatchings(s1)) 
                return true;
        }
    }

    return false;
}

后处理 & 资源回收（释放 engine 和 loader 等）
1
2
3
delete me; delete pattloader; delete targloader;

VF3图同构算法

https://www.mementos.top/2024/07/26/VF3 图同构算法/

作者

Natsumi

发布于

2024年7月26日

许可协议

LRU & LFU 上一篇

VF3图同构算法

概述

（子）图同构/匹配：

图同构问题

子图同构问题

图匹配问题

（子）图同构典型思路

子图同构算法 VF3

VF3 概述

VF 算法基础

State Space Representation (SSR)

树状结构搜索 SSR

可行性检查

结构可行性 Ft

通过分类函数 ψ 划分等价类

结构可行性 Ft

VF3 算法的改进

状态空间预计算（State Space Precalculation ）

根据$N_{G_1}$预计算${\widetilde M_1(s)}$与${\widetilde{\mathcal{T_1}}(s)}$

维护父节点树 (parent tree)

候选节点选择（Candidate Selection）

VF3 算法总结

（待补充）并发 & 多线程

实验结果

Q & A:

（待补充）Implementation

必要数据结构

Graph 的表示

State 的表示

对State的操作

VF3 算法 workflow

初始化 （命令参数解析&配置，信号处理， 读取图数据，初始化匹配引擎）

预处理（匹配引擎初始化，快速检查，节点分类，构造节点序列$NG_1$）

匹配过程（从初始状态 s0 开始搜索）

后处理 & 资源回收（释放 engine 和 loader 等）

初始化（命令参数解析&配置，信号处理，读取图数据，初始化匹配引擎）