AI的“连连看”黑科技

手机刷脸解锁、在海量网盘中搜寻相似照片，或者科学家在电脑前比对复杂的蛋白质结构时，计算机的幕后都在疯狂运行着同一种底层技术——图匹配（Graph Matching）。

简单来说，计算机看世界时，眼前的对象往往不是孤立的数字，而是一副由点（节点）和线（边）交织而成的“骨架”。将两幅甚至多幅“骨架”完美地对齐、连线，找出它们之间的对应关系，就是图匹配的核心任务。为了梳理这一计算机视觉与机器学习领域的基石技术，这篇综述论文跳出了传统模式识别的狭窄视角，用系统性的框架为我们揭开了如何教 AI 玩这场“超难数学连连看”的奥秘。

在数字世界里，最传统的记录数据方式是“向量”（可以理解为一串死板的数字排列）。但向量有一个致命弱点：抹杀空间和结构信息。相比之下，“图（Graph）”具有结构跨越能力。它允许我们在节点上挂载属性（比如人脸的五官特征），还能在连接节点的边上挂载任意的几何或数量关系（比如眼睛到鼻子的距离、角度）。这种灵活的建模方式让它成了描述真实世界物体关系的完美工具。

在理想的数学世界里，如果两幅图的节点和边完全对应、严丝合缝，这叫“图同构（Exact Graph Isomorphism）”。然而，现实生活充满了噪音、遮挡和形变。当两幅照片角度不同、或者蛋白质分子发生扭曲时，绝对重叠是不可能的。因此，论文将重点放在了更具现实控制力的“非精确加权图匹配（Inexact Weighted Graph Matching）”上。目标不再是追求零误差，而是在不完美的现实世界中，寻找能够最大化相似度（亲和力）或最小化扭曲程度的最佳折中连线方案。

图匹配听起来很直观，但在数学层面上通常被建模为著名的二次指派问题（QAP，Quadratic Assignment Problem），在计算机科学中属于NP-complete（或 NP-hard）级别的终极硬骨头。这意味着随着节点数量的增加，计算的可能性会呈指数级爆炸。为了衡量两幅图连线得好不好，科学家们设计了不同的数学天平：

1. 经典的二阶亲和力模型

最为通用的表现形式是Lawler的QAP模型，其核心优化目标可以写为：

在这里，矩阵X代表我们梦寐以求的配对连线图（1代表连上，0代表不连），而中间庞大的矩阵K就是二阶亲和力矩阵（Second-order Affinity Matrix）。它不仅记录了点和点像不像，更记录了“图1的A-B线”与“图2的C-D线”在结构上是否契合。

另一种由Koopmans-Beckmann提出的经典变形则更侧重于邻接矩阵的痕迹运算：

通过将点相似度（K_p）与边拓扑结构（F_i, F_j）分离开来，为大厂和科学家们提供了一本直观的结构账本。

论文强调了近年来的一项重大技术突破——通过将原本大到让人绝望的矩阵 K拆解为更小的点、边亲和力矩阵的乘积，不仅极大地节省了宝贵的计算机内存，更为各类图匹配算法的融合打通了理论隧道。

随着大数据的爆发，传统的“两两连线”已经无法满足AI的胃口了。综述论文重点向我们推介了近十年来最前沿的两个进化方向：

（1） 迈向高阶：用“三角形”对齐三角形：传统的二阶匹配只看一条线和另一条线配不配。但如果物体发生了剧烈的仿射形变，直线长度全变了怎么办？ 科学家们引入了高阶图匹配（Higher-order Graph Matching）。AI不再单线比对，而是每次抽取三个点组成小三角形（Triplet），直接比对三角形的内角。利用高阶张量（Tensor）来存储这种三阶甚至高阶的几何线索，极大地提升了AI在面对剧烈干扰时的鲁棒性。

（2）多图联合：绕不开的“循环一致性”幽灵：假设有100张猫的照片，用传统求解器两两不相关地进行匹配，很快就会遇到一个尴尬的“内讧”悖论： 如果照片A的猫眼配上了照片B的猫眼，照片B的猫眼配上了照片C的猫眼，但在独立计算时，照片A的猫眼却阴差阳错配上了照片C的猫嘴！这种逻辑上的崩溃被称为循环不一致（Cycle Inconsistency）。

为了解决这个问题，近年来涌现出了“一气呵成法（One-shot）”和“循序渐进法（Iterative）”。前者通过矩阵补全或同步技术一次性强制大一统，后者则在迭代中像揉面团一样逐步注入一致性约束，从而完美利用了跨图的多重信息流动。

既然精确解出QAP问题是计算上的灾难，科学家们到底是怎么让电脑在几毫秒内给出高分答案的？论文为我们梳理了三大主流的“数学妥协艺术（松弛策略）”：

（1）谱松弛（Spectral Relaxation）：直接放开配对矩阵非0即1的硬性限制，将其放宽为一个单位向量。通过直接计算亲和力矩阵的最大特征向量来瞬间锁定轮廓，速度极快，但对噪音敏感。

（2）半正定规划松弛（SDP）：把非凸的硬约束空间通过引入高维变量扩充为凸的半正定空间。虽然拥有极漂亮的数学逼近理论边界，但因为计算成本太贵，往往让大厂的服务器感到吃力。

（3）双妥协概率松弛（Doubly-stochastic Relaxation）：这是目前最流行的做法。它允许配对矩阵里的数值在0到1之间滑行（概率分布），把离散的跳跃变成平滑的斜坡，从而允许梯度下降和Frank-Wolfe等经典优化算法在上面纵马驰骋，最后再用临门一脚（如匈牙利算法）将其还原为离散的0和1。

作者简介：严骏驰，上海交通大学人工智能学院教授（兼计算机科学与工程系），主要从事机器学习及其与组合优化、图学习、计算机视觉等方向的交叉研究。曾在 IBM Research（IBM研究院）任研究员/首席研究员多年，长期致力于将学习方法与组合优化、图匹配等问题相结合。

ORCID：0000-0001-9639-7679

DOI：10.1145/2911996.2912035

已收藏 0

点赞 0