Clique

general · 首次出现 2026-08-04 · 最近出现 2026-11-19 · 累计提及 6

综述

Clique(团)是图论中的基础概念,指图中两两互相连接的顶点构成的子集;在无向图中,若一个团不能再加入任何顶点而保持完全连接,则称其为极大团,包含顶点数最多的团称为最大团。Clique 相关研究横跨组合数学、理论计算机科学与机器学习,其判定与枚举的计算复杂性(最大团问题是经典 NP 完全问题)使其长期是算法研究的核心对象,近年来也频繁出现在图对齐、因果发现等学习任务中。

Clique 研究的近期进展

  • Clique Constraints for Exact Causal Structure Learning:该工作将团约束引入因果结构学习,利用团结构刻画变量间的互斥关系,以实现更精确的因果图恢复,是把图论中的 clique 概念落地到机器学习任务的代表性尝试。
  • 最优无歧义DNF与Alon-Saks-Seymour猜想:这篇论文围绕布尔函数复杂度展开,与 Alon-Saks-Seymour 猜想相关——该猜想本质上涉及图的色数与团数之间的关系,是团理论在组合数学中的重要分支。
  • 无监督多尺度Gromov-Wasserstein超图对齐:在超图对齐任务中,团(clique)对应超图中的完全子结构,该研究借助 Gromov-Wasserstein 距离在无监督设定下做多尺度结构匹配,团结构是其对齐信号的重要来源之一。
  • 当前焦点与观察点

    目前围绕 clique 的研究呈现两条主线。其一是算法与复杂度层面:最大团求解的精确算法、参数化算法以及团枚举的工程实现仍是活跃方向,实际应用包括社交网络社区发现、生物网络分析等。其二是机器学习中的结构约束层面:像团约束用于因果发现这类工作,显示图论的组合结构正被转化为优化问题的正则项或约束条件,这一思路有望推广到图匹配、图生成等更多任务。

    值得注意的观察点是:团相关的理论结果(如与色数、DNF 复杂度的联系)往往推进缓慢但影响深远,而应用侧的进展则更快、更分散。对关注者而言,判断一项 clique 研究的价值,可以看它是提供了新的复杂度刻画,还是在真实图数据上给出了可复现的求解或建模改进。

    相关报道

    5 条在档