同构 - 如何判断两个图是否相似？

同构 - 如何判断两个图是否相似？#

import networkx as nx
import matplotlib.pyplot as plt

什么是同构？为什么它有趣？#

由于无标签图可以有多种空间表示形式，如果两个图具有相同的边数、顶点数和相同的边连接性，则它们是同构的。让我们看一个两个同构图的例子：

plt.subplot(221)
G = nx.cubical_graph()
nx.draw_spectral(G, with_labels=True, node_color="c")
plt.title("G", fontweight="bold")
H = nx.cubical_graph()
plt.subplot(222)
nx.draw_circular(H, with_labels=True, node_color="yellow")
plt.title("H", fontweight="bold")

plt.show()
../../../_images/5b9e62ca821d82900f2712646341c928ccddc467fc1456ace95896ba7e6657a3.png

这两个图的空间表示形式非常不同，然而它们是同一个图！

形式化定义#

如果我们能在 G 和 H 的顶点集之间建立一个双射，那么 G 和 H 是同构的。

\[ {\displaystyle f\colon N(G)\to N(H)} \]

例如，如果

\(v\) 和 \( w \) 在 G 中相邻 \(\iff\) \(f(v)\) 和 \(f(w)\) 在 H 中相邻

要形式化证明两个图是同构的，我们需要找到顶点集之间的双射。对于前面的例子，双射是

\[f(i) = i+1 \hspace{0.5cm} \forall i \in [0, 7]\]

对于小例子，同构可能看起来很容易。但它不是一个简单的问题。对于 n 个节点的两个图 G 和 H，有 n! 种可能的双射函数。对于更大的图，检查每种组合是不可行的选项。实际上，同构是被称为 NP 的问题的一部分。这意味着我们不知道任何能在多项式时间内运行的算法。

应用#

图同构问题有很多应用。

  • 图像识别：图像可以转换为图，通过寻找（子）同构，我们可以比较两张图片是否相似。

  • 电子电路设计和通信网络不同表示形式的等效性验证。

  • 化合物和蛋白质的识别。

  • 指纹、面部和视网膜匹配算法。

  • 社交网络上的聚类算法。

同构算法#

朴素方法

有一些我们可以检查的初始属性，用于决定是否可能存在同构：

  • G 和 H 必须具有相同的节点数和边数。

  • G 和 H 的度序列必须相同。

这些是必要条件，但不能保证两个图是同构的。让我们看一个小例子：

plt.subplot(221)
G = nx.cycle_graph(6)
nx.draw_circular(G)
plt.title("G", fontweight="bold")
plt.subplot(222)
H = nx.union(nx.cycle_graph(3), nx.cycle_graph(3), rename=("s", "d"))
nx.draw_circular(H, node_color="r")
plt.title("H", fontweight="bold")
plt.show()
../../../_images/6aac89853acf721adb5c7ceae3e910551e15516c61f358ce5f638fe94bf0fe43.png

我们可以使用函数 nx.faster_could_be_isomorphic()，如果 G 和 H 具有相同的度序列，该函数返回 True。

nx.faster_could_be_isomorphic(G, H)

True

这些图显然不是同构的，但它们具有相同的度序列。

我们可以检查的另一个属性是

  • 相同数量的特定长度的环，例如，三角形。

我们可以使用函数 nx.fast_could_be_isomorphic() 来检查图是否具有相同的度序列和三角形序列。三角形序列包含每个节点所属的三角形数量。

nx.fast_could_be_isomorphic(G, H)

False

这个新属性使我们能够检测到前面例子中的图不是同构的。

我们可以更进一步检查

  • 相同数量的极大团。

我们可以使用函数 nx.could_be_isomorphic() 来检查图是否具有相同的度序列、三角形序列和团序列。团序列包含每个节点所属的极大团数量。

nx.could_be_isomorphic(G, H)

False

同样，我们可以检测到 G 和 H 不是同构的。但这些条件不足以说明两个图是同构的。让我们看下面的例子：

plt.subplot(221)
G = nx.path_graph(5)
G.add_edge(2, 5)
nx.draw_circular(G, with_labels=True, node_color="g")
plt.title("G", fontweight="bold")

plt.subplot(222)
H = nx.path_graph(5)
H.add_edge(3, 5)
nx.draw_circular(H, with_labels=True, node_color="c")
plt.title("H", fontweight="bold")
plt.show()
../../../_images/5fb2141d4b235bc3b738e061faa8c5df192905f8c4026450e601baa810014506.png 
nx.could_be_isomorphic(G, H)

True

这些图满足所有必要条件，但它们不是同构的。

一些可在多项式时间内求解的图类别#

  • 树

  • 平面图（实际上，平面图同构是 O(log(n))）

  • 区间图

  • 置换图

  • 循环图

  • 有界参数图

    • 有界树宽图

    • 有界亏格图

    • 有界度图

    • 有界特征值重数图

    • k 可缩图（有界度和有界亏格的推广）

让我们看一个例子，我们可以使用同构模块中的函数 tree_isomorphism() 来检查两棵树是否在 \(O(n*log(n))\) 时间内同构。该函数使用分治（D&C）方法，一旦找到每棵树的根，就匹配这些树，并返回包含节点匹配的列表。

因此，让我们使用它来检查一个具有 \(2^4 - 1\) 个节点的 2 叉树是否是一个高度为 3 的平衡二叉树。

t1 = nx.balanced_tree(2, 3)
t2 = nx.full_rary_tree(2, 15)

from networkx.algorithms import isomorphism as iso

print("Node matching")
iso.tree_isomorphism(t1, t2)

Node matching

[(0, 0),
 (1, 1),
 (3, 3),
 (7, 7),
 (8, 8),
 (4, 4),
 (9, 9),
 (10, 10),
 (2, 2),
 (5, 5),
 (11, 11),
 (12, 12),
 (6, 6),
 (13, 13),
 (14, 14)]

高级算法#

VF2#

该算法用于解决图同构问题以及子图同构问题。

VF2 是一个递归算法，在每个步骤中，我们扩展当前的匹配函数以覆盖两个图中更多的节点，直到没有更多节点可匹配为止。这不是一个暴力方法，因为有一些可行性规则可以避免探索整个递归树。

形式上，我们有一个函数 \( M: s \rightarrow N(G) \times N(H) \)。\(M\) 是在当前状态 \(s\) 下，在 \(G\) 和 \(H\) 的节点子集之间的匹配函数。我们从初始状态 \(s_0\) 开始，其中 \(M(s_0) = \emptyset\)。在每个步骤中，我们考虑一组节点，将当前状态 \(s\) 扩展到下一个状态 \(s'\)。在这个新状态下，\(M(s') = M(s) \cup {(g, h)} , g\in N(G), h\in N(H)\)。一致性条件是与 \(M(s)\) 相关联的偏图 \(G\) 和 \(H\) 是同构的。有两种可行性检查类型：

  • 语法（图结构）：包括检查一致性条件以及 k 步预查规则，用于提前检查一致状态 \(s\) 在 k 步后是否没有一致的后续状态。

  • 语义（属性）。

伪代码

Match(s)

Input: Intermediate state

Output: The mapping between the 2 graphs

IF M(s) covers all nodes of H THEN:
    RETURN M(s)
ELSE:
    Compute P = {(g, h)...} the set of candidates for inclusion in M(s). 
    FOR each p in P:
        IF the feasibility rules succeed for the inclusion of p in M(s) THEN:
            Compute the state of s'
            MATCH(s')
       ENDIF
   ENDFOR
   Restore data structures
ENDIF

让我们使用 VF2 来检查前面例子中的图

G = nx.path_graph(5)
G.add_edge(2, 5)

H = nx.path_graph(5)
H.add_edge(3, 5)

nx.is_isomorphic(G, H)

False

时间复杂度

  • 最佳情况：\(\in \theta(n²)\)，如果只探索了 \(n\) 个状态，例如，如果每个节点被探索一次。

  • 最坏情况：\(\in \theta(n!n)\)，如果必须完全探索所有可能的匹配。

最新进展#

  • VF2++ 和 VF2 Plus。它们包含对 VF2 算法的一些优化。

  • 有一些新算法：QuickSI、GraphQL、TurboISO、BoostISO、CFL-Match、VF3、CECI 和 DAF。

参考文献#

目录