Graph Matching 图结构匹配算子集
算子类别：Graph Matching（图结构匹配、子图模式包含与树同构判定）
算法数量：2 个
适用阶段：结构模式识别、子图模板匹配、树结构对齐、层级结构去重、模式检索、结构一致性校验
产品定位：为“一个图是否包含某种结构模式 / 两棵树是否结构一致 / 是否可以通过节点重命名实现结构匹配”提供图结构匹配与模式识别能力底座。
一、算子集概述
Graph Matching 算子集聚焦于图与图之间的结构对应关系，主要用于判断图结构是否相同、是否包含某种模式、以及树形结构是否可以一一对应。
它主要回答以下问题：
-
子图模式包含
- 一个大图中是否包含指定的小图模式？
- 某种结构模板是否出现在目标图中？
- 是否存在结构上的“弱匹配”或“模式嵌入”？
-
树结构匹配
- 两棵树是否具有相同结构？
- 即使节点名称不同，树的层级关系是否一致？
- 两个组织结构、目录结构、分类结构是否等价？
-
结构模板识别
- 某个业务流程是否符合标准模板？
- 某个网络局部结构是否匹配已知模式？
- 是否可以从图中检索出特定结构形态？
-
结构去重与归并
- 两个树形结构是否只是节点命名不同？
- 多个结构样本中是否存在重复模式？
- 是否可以将结构一致的图归为同一类？
二、算子能力分类
| 能力类型 | 对应算子 | 功能描述 |
|---|---|---|
| 子图单态匹配 | subgraph_is_monomorphic | 判断目标图中是否存在与模式图单态匹配的子图结构 |
| 树同构判定 | tree_isomorphism | 判断两棵树是否结构等价，并返回节点对应关系 |
三、通用输入输出约定
-
输入
G/G1/G2- NetworkX Graph / DiGraph
- 用于表示待匹配图、目标图或模式图
-
常见输入对象
G1：第一个图或主图G2：第二个图或模式图root1/root2：树结构中指定的根节点，部分树匹配场景可能需要
-
常见输出类型
- 判定类：
bool - 匹配类：节点映射、节点对列表或匹配关系
- 结构类：表示两个图或两棵树之间的对应关系
- 判定类：
四、算子详细说明
1. subgraph_is_monomorphic —— 子图单态匹配判定
功能说明 判断一个目标图中是否存在与给定模式图满足单态匹配关系的子图。
单态匹配可以理解为一种相对宽松的结构匹配方式：
- 模式图中的节点需要映射到目标图中的节点
- 模式图中的边关系需要在目标图中得到保留
- 相比严格的诱导子图同构，单态匹配通常更关注“模式边是否存在”，而不强制要求额外边完全一致
也就是说，它适合回答：
“这个大图里有没有出现过这种结构模式？”
而不是严格要求：
“这个局部结构是否和模式图完全一模一样，没有多余关系？”
产品价值
- 支持结构模式检索
- 可以发现目标图中的局部结构模板
- 适合用于规则识别、模式命中、风险结构发现
- 比严格同构更适合真实业务图，因为业务图中常常存在额外关系
典型场景
- 欺诈网络中的团伙模式识别
- 交易图中的可疑路径或局部结构检测
- 知识图谱中的模式查询
- 流程图中的模板结构匹配
- 社交网络中的局部关系模式发现
- 系统依赖图中的架构模式检查
适用与特性
- 图类型：无向图 / 有向图，取决于具体匹配对象
- 输入：目标图与模式图
- 输出：
bool - 特点：适合判断“是否包含某种结构模式”
- 注意：图匹配类问题通常计算成本较高，大图或复杂模式下需要谨慎使用
2. tree_isomorphism —— 树同构判定
功能说明 判断两棵树是否在结构上等价。
如果两棵树可以通过重新命名节点，使得节点之间的连接关系完全一致，则它们是同构的。
例如：
- 节点名称不同，但层级结构一样
- 目录名不同，但目录嵌套关系一样
- 组织成员不同，但组织层级形态一样
tree_isomorphism 通常不仅可以判断是否同构，还可以返回两棵树之间的节点对应关系。
产品价值
- 快速判断两个树结构是否一致
- 支持树形模板匹配、结构去重和结构归并
- 可用于对比两个层级系统是否只有命名差异
- 适合组织架构、分类体系、目录结构等树形数据
典型场景
- 组织架构结构一致性校验
- 分类树模板匹配
- 文件目录结构对比
- 物料 BOM 层级结构对比
- 流程树或决策树结构对齐
- 多个树形样本的结构去重
常见输出
- 若两棵树同构：返回节点对应关系
- 若两棵树不同构：返回空匹配或表示不匹配的结果
适用与特性
- 图类型：树结构，通常为无向树
- 输出：节点映射 / 节点对应关系
- 相比一般图同构，树同构问题结构更特殊，通常计算更高效
- 适合作为树形数据结构校验、对比和归并的基础能力
五、推荐使用指南
1. 子图模式识别
- 判断目标图是否包含指定结构模式：
subgraph_is_monomorphic - 查找业务图中的风险模板：
subgraph_is_monomorphic - 检查流程图是否命中特定结构片段：
subgraph_is_monomorphic
2. 树结构对比
- 判断两棵树是否结构一致：
tree_isomorphism - 对比组织架构、分类树、目录树：
tree_isomorphism - 获取两棵树之间的节点对应关系：
tree_isomorphism
3. 结构模板匹配
- 图中是否包含某个模式：
subgraph_is_monomorphic - 树是否符合某个层级模板：
tree_isomorphism
4. 结构去重与归并
- 两个树结构是否只是节点命名不同：
tree_isomorphism - 多个局部图结构是否命中相同模板：
subgraph_is_monomorphic
六、可直接回答的典型问题
- “这个大图里是否包含这个子图模式？”
- “这个交易网络中是否出现了某种可疑结构？”
- “这个流程图是否符合指定模板？”
- “这两棵树的结构是不是一样？”
- “两个组织架构是否只是节点名称不同？”
- “两个目录树是否具有相同的层级结构？”
- “这个分类体系是否和标准分类模板一致？”
- “能否给出两棵树之间的节点对应关系？”
- “这个图中是否存在某种局部关系模式？”
- “这个结构是否可以作为某个模板的实例？”
七、算子清单
| 序号 | 算子名称 | 中文说明 |
|---|---|---|
| 1 | subgraph_is_monomorphic | 子图单态匹配判定 |
| 2 | tree_isomorphism | 树同构判定 |