Weisfeiler-Lehman 图核的拓扑相似度

Weisfeiler-Lehman (WL) 图核Graph Kernel是一种用于衡量两个图之间拓扑相似度的强大方法广泛应用于图分类、图聚类和图检索任务。它基于经典的 Weisfeiler-Lehman 图同构测试算法通过迭代细化节点标签来捕捉图的局部和全局结构信息。以下是关于 WL 图核如何衡量拓扑相似度的核心机制和特点1. 核心思想颜色细化Color RefinementWL 图核的核心在于模拟1维 Weisfeiler-Lehman 测试的过程。其基本逻辑是如果两个图在拓扑结构上相似那么它们的节点在经过多轮“邻居聚合”后生成的标签分布也应该相似。初始化每个节点根据其初始属性如节点类型、度数等获得一个初始标签颜色。如果没有节点属性通常所有节点初始标签相同或仅基于度数。迭代细化在每一轮迭代hhh中节点vvv的新标签由其当前标签和其所有邻居节点的当前标签集合共同决定。具体来说将节点vvv的旧标签与其邻居的旧标签排序后拼接形成一个多重集Multiset。通过一个哈希函数将这个多重集映射为一个新的压缩标签。这意味着只有当两个节点拥有相同的旧标签且它们的邻居标签集合也完全相同时它们才会获得相同的新标签。拓扑捕获经过hhh轮迭代后节点的标签实际上编码了以其为中心、半径为hhh的子树结构Subtree Pattern。因此标签的演化过程本质上是在捕捉不同深度的局部拓扑结构。2. 相似度的计算方式WL 图核通过比较两个图在每一轮迭代中生成的标签直方图Label Histograms来计算相似度特征向量构建对于图GGG在第000到HHH轮迭代中统计每种标签出现的次数。将所有轮次的标签计数拼接成一个长向量ϕ(G)\phi(G)ϕ(G)。这个向量代表了图GGG的拓扑特征描述符。向量中的每一个维度对应一种特定的子树模式由标签序列定义。内积计算两个图GGG和G′GG′之间的 WL 核值KWL(G,G′)K_{WL}(G, G)KWL​(G,G′)定义为它们特征向量的内积点积KWL(G,G′)⟨ϕ(G),ϕ(G′)⟩ K_{WL}(G, G) \langle \phi(G), \phi(G) \rangleKWL​(G,G′)⟨ϕ(G),ϕ(G′)⟩如果使用归一化的版本如余弦相似度则衡量的是两个图中相同拓扑模式出现的频率分布的重叠程度。直观理解如果两个图拥有大量相同的局部子树结构即在很多轮迭代中产生了相同的标签它们的特征向量在内积空间中的夹角就小数值就大表示拓扑相似度高。3. 拓扑相似度的特性与优势子树匹配WL 图核等价于计算两个图中所有高度为HHH的子树模式的匹配数量。这使得它对局部结构的微小变化非常敏感。计算高效相比于精确的图同构判定通常是指数级复杂度WL 图核的计算复杂度约为O(H⋅∣E∣)O(H \cdot |E|)O(H⋅∣E∣)其中∣E∣|E|∣E∣是边数HHH是迭代次数。这使得它能处理包含数千个节点的大图。表达能力它能够区分绝大多数非同构图。它是许多现代图神经网络如GIN, Graph Isomorphism Network的理论上限。研究表明标准消息传递神经网络MPNN的表达能力不超过 1-WL 测试。局限性正则图失效对于所有节点度数相同的正则图如环图、完全图如果节点没有初始属性1-WL 无法区分它们因为所有节点的标签在迭代中始终保持一致。特定结构盲区存在一些非同构图如某些强正则图WL 测试无法区分因此 WL 核会认为它们完全相似尽管这种情况在实际数据中较少见。更高阶的kkk-WL 可以解决部分问题但计算成本会急剧增加。4. 应用场景由于其高效的拓扑相似度衡量能力WL 图核常用于化学分子分析判断两个分子图原子为节点键为边是否具有相似的子结构从而预测相似的生物活性。社交网络分类识别具有相似连接模式的社区或用户群体。程序代码分析将代码抽象为图通过拓扑相似度检测代码克隆或漏洞。总结Weisfeiler-Lehman 图核通过将图的拓扑结构转化为标签分布序列利用子树模式的重叠度来量化相似度。它是一种在计算效率和结构表达能力之间取得极佳平衡的方法是图机器学习领域中衡量拓扑相似度的基准工具之一。