图同构是两个结构完全相同的图之间的数学关系,即使它们的顶点名称不同,或者画出来的样子不同。同构是顶点之间的一一对应,并且在两个方向上都保持邻接关系。在图论中,同构将图的内在结构与描述图时使用的非本质性标号之间的区别形式化。
相应的计算问题是判定两个有限图是否同构。这个问题在计算机科学中处于一种特殊地位:给定一个候选同构,很容易验证它是否成立,但目前尚无适用于所有图的已知多项式时间算法,也尚未证明该问题是 NP 完全的。拉斯洛·鲍鲍伊于 2015 年公布的拟多项式时间算法大幅缩小了这一差距,但并未彻底解决问题。
图同构将结构图论、置换群、逻辑可定义性以及识别重复对象的实用算法联系起来。其应用包括化学结构登记、组合对象分类以及关系数据比较。在不同场景下,需要仔细确定同构必须保持哪些特征,例如边的方向、原子类型或顶点颜色。
定义与数学表述
对于有限简单无向图 和 ,同构是一个双射函数 ,使得对所有不同的顶点 ,都有
如果存在这样的映射,就称这两个图同构,记作 。这一条件既保持邻接关系,也保持非邻接关系。这使同构区别于一般的图同态:图同态只需将边映射为边,不必是双射。
这一概念是数学结构之间的同构的一个实例。顶点的名称、边的列出顺序,以及绘图中顶点的位置,都不属于抽象图的结构。例如,将一个四顶点环画成正方形,或画成含有两条相交对角线段的图形,所得的图是同构的,前提是交点不被视为顶点。除非图附带了嵌入或额外的几何数据,否则几何上的相交不具有结构意义。
图同构是一种等价关系。恒等映射证明了自反性,同构映射的逆映射证明了对称性,而映射的复合则证明了传递性。其等价类称为同构类。有标号图具有指定的顶点集,通常为 ;无标号图通常被理解为有标号图的一个同构类。这一区别在计数中很重要:若干不同的邻接表可能只代表同一个无标号图。
图同构也可以用矩阵表述。设 和 是两个具有 个顶点的图的邻接矩阵。这两个图同构,当且仅当存在置换矩阵 ,使得
这一运算按照同一种顶点重标号方式,同时重新排列行和列。虽然这与矩阵相似类似,但这里允许的变换仅限于置换矩阵;任意可逆的基变换并不能表示图同构。
通过保持各类图所规定的关系,这一定义可以推广到其他图模型。对于有向图,同构保持边的方向。对于多重图,同构保持边的重数;自环也必须保持。在顶点着色图中,相互对应的顶点必须具有相同的颜色。边的标签和数值权重同样可以作为必须精确保留的属性。颜色究竟是固定的名称,还是其本身也可以被置换,会界定出不同的问题,因此,保持哪些属性以及如何保持,也是数学定义的一部分。
结构不变量及其局限
图不变量是在同构下保持不变的量或对象。基本例子包括顶点数和边数、顶点度数的多重集、连通分支的数量与大小,以及是否存在指定长度的圈。如果两个图在任何一个不变量上不同,它们就不可能同构。因此,在开始开销更大的搜索之前,可以利用不变量以较低成本排除不可能同构的情形。
简单不变量相同通常不足以判定同构。圈图 与两个三角形的不交并都有六个顶点、六条边,度数序列也都是 ,但只有前者是连通的。即使同时考虑连通性和所有顶点的度数,也仍然不够:三棱柱图与完全二部图 都是具有六个顶点的连通三正则图。三棱柱图包含三角形,而 不包含。每增加一项检验,都能缩小可能的范围,但未必能唯一确定这个图。
谱不变量源自线性代数。同构图的邻接矩阵具有相同的特征多项式和相同的特征值,包括各特征值的重数。对于简单无向图,量 给出长度为 的闭游走的数量。因此,谱蕴含了关于边、三角形以及更长闭游走的信息。然而,不同构的图也可能具有完全相同的谱;这样的图称为同谱图。
一个很有启发性的例子是施里克汉德图与 车图。两者都有16个顶点,且都是参数为 的强正则图:每个顶点都有六个邻点,相邻顶点有两个公共邻点,不相邻的两个不同顶点也有两个公共邻点。它们的邻接谱完全相同,但这两个图并不同构。车图中存在与棋盘各行、各列对应的四顶点团,而施里克汉德图中不存在这样的团。
如果两个图具有相同的不变量当且仅当它们同构,那么这个不变量就是完全不变量。规范邻接编码提供了这样一种不变量,但计算这种编码可能需要大量工作。这一区别体现了两个不同的目标:一是构造判别力强且可高效计算的必要条件,二是构造完整的分类。实际系统通常会按层次使用计算成本逐渐增加的不变量,只对通过初期筛选的情形采用穷举或群论方法。因此,由不完全不变量生成的哈希值可用于索引,但仅凭哈希值相同并不能确定两个图同构。
自同构、群作用与规范形式
自同构是一个图到其自身的同构。一个图的所有自同构在函数复合运算下构成一个群,记为 。对于一个有 个顶点的图,这个群是对称群 的子群。自同构群描述了图的组合对称性,而这种对称性不一定与某种具体画法中可见的对称性一致。
图的对称性可以从完全对称到完全不对称。完全图 的任意顶点置换都保持邻接关系,因此其自同构群的阶为 。对于圈图 ,当 时,旋转和反射构成一个阶为 的群。另一个极端是不对称图,它只有恒等自同构。不对称图仍然可以有许多不同的带标号表示;不对称意味着,对于一个固定的表示,没有任何非平凡的顶点置换能保持该表示不变。
自同构群通过其在顶点集上的群作用,将顶点划分为若干轨道。如果存在某个自同构将一个顶点映射到另一个顶点,那么这两个顶点就属于同一轨道。稳定子描述了将选定顶点固定后所剩余的对称性。这些概念可以直接用于搜索算法:通过已知自同构相互关联的分支,无须分别探索。算法通常只存储一个紧凑的生成集,而不会列出所有自同构,因为即使是一个很小的图,其自同构群也可能极其庞大。
轨道—稳定子定理还解释了带标号计数与无标号计数之间的关系。对于一个有 个顶点的图 ,在固定顶点集 上,与 同构的不同带标号图的数量为
顶点的每一种排列都会产生一个带标号表示,但产生相同边集的排列会因自同构而被视为等价。因此,与顶点数相同的不对称图相比,高度对称的图具有更少的不同带标号表示。
规范形式为每个图指定其同构类的一个标准化代表。形式上,规范化映射 满足 ,且
一种在数学上成立的构造方法,是从所有顶点排列所对应的邻接编码中,选取字典序最小的一个。这种方法是完备的,但直接实现时需要考察 种排列。
当需要比较大量图时,规范化尤其有用:每个图只需规范化一次,此后便可通过比较规范编码来判断是否相等。规范标号确定的是一个标准化的带标号表示,而不是为原图的每个顶点赋予一个内在唯一的身份。当存在自同构时,从输入图到同一个规范代表可能存在多个不同的映射,而且这些映射可能同样有效。
计算复杂性与拟多项式时间的突破
图同构判定问题通常简称为 GI,其输入为两个有限图,所要判定的是它们之间是否存在同构。该问题属于 NP,因为顶点之间的双射可以作为证书。给定这一双射后,通过比较相应的邻接关系即可验证其有效性;对于具有 个顶点的图,最多需要进行 次检查。寻找证书与验证证书是不同的计算任务。
一种直接的算法是尝试全部 种顶点排列。这一阶乘级上界远大于多项式上界,但它只是一个基准。算法可以先匹配顶点的度数、分解连通分量、细化顶点分类,并利用对称性。这里的计算复杂性问题关注的是对所有输入都成立的性能保证,包括刻意构造的、具有特殊结构的困难实例,而非典型比较任务的运行速度。
目前,尚不清楚 GI 是否存在多项式时间算法,也不清楚它在多项式时间多对一归约下是否为 NP 完全问题。从复杂性类的结构来看,GI 若是 NP 完全问题,也会是一个令人意外的结果。图非同构问题存在一种满足要求的双消息随机交互式证明,因此 GI 属于 coAM 类。根据复杂性理论中的标准结果,若 GI 是 NP 完全问题,多项式层级就会坍缩至第二层。这种坍缩尚未被排除,因此上述结论只是有条件的证据,并不能证明 GI 不是 NP 完全问题。
1982 年,尤金·卢克斯(Eugene Luks)为度数有界的图建立了多项式时间算法:对于每个固定的最大度数 ,该问题都能在关于顶点数的多项式时间内求解,其中多项式取决于 。这一方法引入了强大的置换群技术。这项工作及后续进展表明,重要的结构限制能够改变该问题在最坏情况下的复杂性。
巴拜(Babai)于 2015 年宣布了一种求解一般图同构问题的确定性拟多项式时间算法,相关论文收录于 2016 年 ACM 计算理论研讨会的论文集中。其运行时间具有如下形式:
从渐近意义上看,这一上界显著小于此前确立的平方根指数型一般上界,但它并不是多项式时间上界。该算法结合了置换群分析、组合划分,以及针对高度有组织结构的处理方法;这些结构难以用较简单的拆分论证来处理。
这一结果针对的是最坏情况下的渐近复杂性,并不意味着它能够全面取代实用软件。在常规输入上,基于其他方法的实现可能快得多。反过来,良好的实测性能也不能解决是否存在多项式时间算法的问题。这些是衡量算法成功与否的不同标准。
颜色细化与 Weisfeiler–Leman 层级
颜色细化根据顶点的局部邻域反复细分顶点集合。初始时,所有顶点可以具有相同的颜色,也可以用颜色记录原子类型等输入属性。每一轮中,顶点的新颜色由它上一轮的颜色以及邻居颜色的多重集决定:
编码过程为相同的特征签名赋予相同的新颜色,为不同的特征签名赋予不同的颜色。由于特征签名保留了上一轮的颜色,各颜色类只会分裂,不会合并。
比较两个图时,细化过程必须使用一致的颜色标识,例如可以对两个图的不交并进行细化。如果某种最终颜色在两个图中出现的次数不同,那么这两个图不同构。如果每个图的每个最终颜色类都恰好包含一个顶点,且各颜色的出现次数在两个图中一致,那么将同色顶点配对就能确定一个同构。在这两种情况之间,细化可以提供约束,但无法判定两个图是否同构。
细化终止时,所得划分是均衡划分:同一类中的任意两个顶点,在每个类中拥有的邻居数都相同。对于有 个顶点的图,真正使颜色类发生分裂的轮次最多为 ,不过高效的实现无须在每一轮都从头计算所有特征签名。借助划分细化数据结构,这一操作的开销可以足够低,从而成为许多同构判定程序的核心子程序。
颜色细化也称为一维 Weisfeiler–Leman 细化,简称 1-WL。它在一大类图上完全无法起到区分作用:若以统一颜色初始化,-正则图的所有顶点就会始终保持相同的颜色。因此,两个顶点数相同的 -正则图,无论在环或整体结构上有何差异,仅靠 1-WL 都无法区分。
高维 Weisfeiler–Leman 过程为顶点的有序元组着色,而不是为单个顶点着色。元组的初始颜色记录各坐标之间的相等关系和邻接关系;后续细化则纳入将坐标替换为其他顶点所获得的信息。对于固定的维数 ,这一过程可在多项式时间内完成,但其存储需求和运行时间都会随 迅速增长。这个层级能够识别越来越丰富的结构关系,但不存在某个固定维数可以区分所有不同构的有限图。1992 年发表的 Cai–Fürer–Immerman 构造为所需维数确立了很强的下界。
这种区分能力的差别在机器学习中同样重要。在标准假设下,采用邻域聚合的图神经网络的区分能力不会强于 1-WL。学习得到的数值特征可能有助于预测,却未必是完备的同构不变量。高阶架构能够表达更细致的结构差异,但通常也会带来更高的计算成本。
个体化–细化方法与实用软件
许多在实践中表现出色的算法通过有选择地打破并列状态,来增强颜色细化的效果。这种策略称为个体化–细化。如果细化后某个类中仍有多个顶点,算法就选择其中一个顶点,为其赋予唯一的颜色,然后再次细化。不同的选择构成搜索树的不同分支。一旦划分成为离散划分,按顺序排列的各个单元素类就给出了一个候选顶点顺序,进而确定一种邻接编码。
因此,典型的搜索节点由顶点集的一个有序划分,以及沿搜索路径积累的信息组成。算法选取一个非单元素的目标单元,针对候选顶点分别建立分支,并在每个分支中进行细化。细化可能揭示两个分支不可能产生相同的规范结果,也可能仅经过一次个体化,就迫使许多其他顶点得到进一步区分。对于有利的输入,只需少量个体化操作就能完全区分图中的顶点。
自同构是剪枝的另一个主要依据。如果两个已完成的分支产生相同的带标号邻接结构,那么它们的顶点顺序就确定了输入图的一个自同构。所发现的这些置换生成了完整自同构群的一个子群。如果这个子群能够在满足当前约束的前提下,将某个尚待探索的分支选择映射到另一个选择,那么相应的搜索子树就是等价的,可以略去其中一棵。因此,图的对称性可能使朴素搜索更困难,却也能使利用群信息的剪枝更有效。
规范标号比仅仅找到一个符合要求的对应关系需要更谨慎的处理。目标单元的选择、节点比较和剪枝规则,都必须保证最终答案不依赖输入图的顶点名称。一种可行的组织原则,是按字典序排列叶节点证书。算法内部可以使用图的原始标号来控制执行过程,但不能让这些标号以一种随重新标号而变化的方式决定规范结果。
布伦丹·麦凯(Brendan McKay)的 nauty、伊戈尔·马尔科夫(Igor Markov)和哈迪·卡泰比(Hadi Katebi)及其合作者开发的 saucy、托米·云蒂拉(Tommi Junttila)和佩特里·卡斯基(Petteri Kaski)的 bliss,以及麦凯和阿道夫·皮佩尔诺(Adolfo Piperno)的 Traces,都是为密切相关的对称性与标号任务开发的代表性软件。这些系统的功能和搜索策略并不完全相同:有的侧重规范标号,有的侧重自同构计算、稀疏图处理,或更强的细化与前瞻机制。
性能在很大程度上取决于图族。看似随机的图往往很快就能通过邻域特征区分顶点,而某些正则图或通过代数方法构造的图则难以用局部细化加以区分。此外,对于一些重要类别的个体化–细化算法,已有严格证明的指数级下界。因此,基准测试结果需要说明图的规模、密度、所属结构族,以及所要求的输出究竟是判定结果、显式的同构映射、规范形式,还是自同构群的生成元。
受限图类与结构分解
对于许多可以按可控方式进行结构分解的图类,图同构问题更容易求解。树就是一个基本例子。树的中心由一个顶点或两个相邻顶点组成,可以通过反复删除叶子来找到。以中心为根后,可以为每个顶点赋予一个类型,由其子节点类型构成的多重集决定。两棵有根子树同构,当且仅当这些多重集递归地相同。
由此可得到一种自底向上的树同构算法。所有叶子都被赋予相同的初始类型;内部顶点则根据其子节点类型排序后得到的集合来编码。对于有两个中心顶点的树,可以对中心边进行对称处理,例如引入一个辅助根节点。直接采用排序的实现可在多项式时间内完成,而更精细的方法能够达到线性时间。该过程之所以有效,是因为删除连接父节点的边,就能将一棵子树与图的其余部分分离,且不会在边界两侧留下复杂的相互作用。
平面图也有高效的同构算法,经典的线性时间结果在20世纪70年代就已出现。这类算法利用逐步分解得到的连通性越来越强的部分,以及平面嵌入的性质。三连通平面图在球面上的嵌入除镜像反射外本质上是唯一的,这大大限制了可能的对应关系。对于存在割点或分离点对的图,则需要额外记录相关信息,以便将同构的各部分一致地组合起来。平面性本身并不能确定唯一的顶点标号。
有界度提供了另一种使问题易于求解的条件。卢克斯算法并非简单地比较邻域:有界度图仍可能具有大范围的对称性和复杂的环。该算法利用度数上界带来的群论约束,研究与部分结构信息相容的置换。这里的“有界”是指最大度为一个不随输入规模变化的固定常数。如果度数随顶点数量增长,那么针对固定度数的多项式时间保证就不能给出统一的多项式界。
树宽有界的图是另一个重要的图类。树分解将图组织为沿一棵树排列、彼此重叠的袋,并要求包含同一顶点的所有袋在这棵树上构成一个连通部分。宽度给出了袋大小减一的上界。由于各部分之间的接口很小,动态规划可以跟踪候选对应关系在这些接口上的表现。
然而,任意给定的树分解本身并不一定在顶点重新标号后保持不变。同构算法必须获得具有适当不变性的分解,或者将各种可能的分解选择纳入考虑。纵观这些例子,使问题易于求解的关键并不只是图的边较少,而在于能够控制各个结构部分如何组合,以及需要考虑多少种相容的对应方式。
逻辑刻画、交互式证明及相关问题
有限图可以视为带有二元邻接关系 的结构。同构就是保持这一关系的双射。这将图同构置于模型论的框架内,也将算法与一阶逻辑的表达能力联系起来。普通的一阶公式可以陈述局部性质,例如是否存在三角形,但资源有界的公式无法刻画有限图之间所有可能的区别。
计数逻辑在这类语言中加入了关于满足某一条件的元素数量的陈述。有界变量计数逻辑与 Weisfeiler–Leman 层级的各个层次密切对应,具体的层级编号取决于定义细化过程时所采用的约定。相关的卵石博弈描述了这样一种过程:一方选择顶点,另一方则试图维持部分对应关系。借助这些刻画,无须逐一显式分析算法的每次执行,就能证明某一类算法无法区分特定的图。
另一种逻辑联系来自用于证明非同构的交互式证明。假设验证者拿到图 和 。验证者随机选择一个比特 ,对 进行随机重标号,再将得到的图发送给计算能力不受限制的证明者。证明者必须判断 的值。如果原来的两个图不同构,收到的图就恰好属于其中一个图的同构类,因此正确的证明者总能作答。
如果两个图同构,那么无论 取哪个值,发送的图都具有相同的概率分布。因此,任何证明者猜中这个隐藏比特的概率都不可能超过 。重复执行可使错误接受的概率按指数速度下降。这一协议说明,随机性与交互如何能够在不提供通常 NP 意义下的简短确定性证书的情况下,验证两个图不同构。
有必要区分几种相近的计算任务。搜索问题要求给出一个明确的同构。对于不受限制的有限图,可以利用颜色固定候选的顶点对应关系,并测试每个选择是否能扩展为完整同构,从而将搜索问题归约为多项式次同构判定查询。同样,利用判定查询和稳定子方法,也可以求得自同构群的生成元。规范化对输出的要求更强:有了规范形式,就能直接判定同构,但在讨论这些任务的一般关系时,不应毫无依据地声称它们的复杂性完全相同。
子图同构是另一个问题,它问的是:在指定的边保持规则下,一个图是否出现在另一个图内部。其一般形式的判定问题是 NP 完全的。图编辑距离则衡量将一个图变为另一个图需要做出多少次修改。这些问题允许部分匹配或结构差异,而通常的图同构要求两个图除标号外完全相同。
应用与表示方式的重要性
化学结构登记是图同构的一项重要应用。分子图通常以顶点表示原子,以带标签的边表示化学键;顶点属性可以包括元素、同位素和形式电荷。通过同构判定,可以确定两条记录所编码的连接关系是否相同。当元素标签是结构的一部分时,碳顶点不能映射到氧顶点;当要求保持键级时,双键也不能与单键互换。
不过,“同一种分子”的说法还需要额外的约定。芳香结构可能采用不同的化学键编码;隐式氢与显式氢的表示方式可能不同;立体化学则需要普通无标签连接图以外的信息。即使数据库出于特定目的将互变异构体或不同质子化状态归为一组,直接按其编码构成的图也未必同构。因此,规范分子字符串的生成需要将图处理算法与化学标准化规则相结合。只有先由这些规则确定所比较的对象,规范化才能消除标号带来的歧义。
在组合数学中,同构检验可以防止重复生成。搜索正则图、关联结构、组合设计或其他有限对象时,往往会通过多条构造路径得到同一个抽象结构。规范构造方法依据不变性规则决定允许哪些扩展,从而不必保留每一个带标号的候选对象。自同构群还可以识别顶点、边或区组的等价选择,进一步减少工作量。因此,最终枚举的通常是同构类,而非未经归并的带标号编码。
关系结构通常可以转换为着色图。例如,关联结构可以表示为二部图,其中一种颜色表示点,另一种颜色表示区组。保持颜色的要求可以防止同构意外地交换这两种角色。有向边及其他关系也可以通过辅助顶点和用于区分的构件来编码。正确的归约必须确保,图同构与所要表达的结构同构精确对应;如果构件之间区分不足,就可能引入虚假的对称性。
电路比较与形式验证体现了结构等价和语义等价之间的界限。两个电路图可能在重新命名元件和导线后同构,这为其编码的连接关系相同提供了证据。然而,结构不同的电路也可以计算同一个布尔函数。因此,功能等价与图同构并不是同一个问题,即使二者出现在同一验证流程中也是如此。
大规模数据系统也会使用图指纹和规范编码来检测重复数据。快速但不能完全判定同构的哈希方法可以将可能匹配的对象分组,在需要确定结果时再进行精确检查。必须明确规定哪些信息需要保持不变,以及软件采用何种规范格式:两个正确的规范化实现可能选取不同的代表。规范编码只是在所选约定下实现了标准化,并不是抽象图所对应的、普遍固定的字节串。