基于双目标优化的多尺度图聚类框架：突破与创新

在图聚类领域，尚无评估网络社区的客观标准，这使得众多聚类方法难以比较。研究人员开展 “Two antagonistic objectives for one multi-scale graph clustering framework” 的研究，提出 nPnB 框架，可评估聚类、比较方法性能，为该领域发展提供重要支撑。

　　在当今科学研究的广袤领域中，复杂系统的研究愈发重要。从微观的生物细胞相互作用，到宏观的社会网络关系，复杂系统无处不在。而图（Graph）作为一种强大的工具，能够将复杂系统中的实体和它们之间的相互作用清晰地展现出来，节点代表基本实体，边代表相互作用。在图的研究中，检测图中的社区（Community Detection），即找到那些内部紧密连接，而与其他社区连接相对稀疏的节点集合，成为了关键任务。

然而，历经 20 多年的深入研究，社区检测依旧面临诸多挑战，堪称一个 “难题”。尽管大家对网络社区有着一个普遍接受的非正式定义（Commonly Accepted Informal Definition，CAID），即社区内部节点紧密相连，外部连接稀疏，但却没有一个客观的正式标准来评估网络社区。这一困境导致在众多图聚类方法之间，难以进行有意义的比较，就像在黑暗中摸索，没有明确的方向。不同的聚类方法犹如一盘散沙，缺乏统一的评估标准，使得研究人员难以判断哪种方法更优，严重阻碍了该领域的发展。

为了打破这一僵局，来自法国认知、语言、言语、人体工程学实验室（Cognition, Langues, Langage, Ergonomie，CLLE）、法国社会分析与数学中心（Centre d’Analyse et de Mathématique Sociales，CAMS）以及法国巴黎法兰西岛复杂系统研究所（Complex Systems Institute of Paris ?le-de-France，ISCPIF）的研究人员 Bruno Gaume、Ixandra Achitouv 和 David Chavalarias 展开了深入研究。他们的研究成果发表在《Scientific Reports》上，为图聚类领域带来了新的曙光。

研究人员提出了一种创新的图聚类框架 ——nPnB 框架。该框架的核心在于，将网络社区的两个关键属性：每个模块紧密连接（PDC，Each module is Densely Connected）和模块之间连接薄弱（PWC，Modules are Weakly Connected to each other），分别用精度（Precision）和召回（Recall）这两个在科学领域广泛应用且易于理解的指标进行精确形式化。通过这种方式，将图聚类问题转化为一个可以量化评估的任务。

在研究过程中，研究人员用到了以下几个主要关键技术方法：

• 定义 nPnB 框架：将图聚类视为节点对的受限二分分类器，通过特定的函数定义来计算 Precision 和 Recall，从而评估聚类质量。
• 引入 F_s分数：综合 Precision 和 Recall，引入 F_s分数来平衡两者的关系，其中 s 作为权衡参数，可根据需求调整聚类的粒度，即描述尺度（description scale）。
• 提出 BEC 算法：基于 F_s优化提出 BEC（Binary Edges Classifier）算法，通过启发式方法在合理时间内找到优化 F_s分数的聚类。

下面详细介绍研究结果：

• 形式化社区检测目标：研究人员将 CAID 分解为 PDC 和 PWC 两个属性，用 Precision 和 Recall 形式化这两个属性。在 nPnB 框架下，Precision 衡量聚类中模块内部连接的紧密程度，Recall 衡量模块之间连接的稀疏程度。并且证明了这两个指标通常是相互拮抗的，即不存在同时最大化 Precision 和 Recall 的解决方案。例如，在一个简单的图结构中，当试图提高 Precision 时，模块内部连接更加紧密，但这往往会导致模块之间的连接增多，从而降低 Recall。这意味着在实际应用中，需要根据具体需求在 Precision 和 Recall 之间进行权衡12。
• 作为双目标任务的图聚类：由于 Precision 和 Recall 相互拮抗，在 nPnB 框架下，寻找网络中的非重叠簇可以被视为一个非平凡的双目标任务。研究人员通过一个简单的玩具图（toy graph）展示了不同分区的 Precision 和 Recall 得分，发现存在一些最优分区，即帕累托前沿（Pareto front）或帕累托最优解（Pareto optimal solutions）。在选择最优分区时，需要根据对 Precision 和 Recall 的优先级设定来进行，这取决于建模者的需求，只有在确定了两者的权衡关系后，才能评估不同聚类方法的性能34。
• nPnB 作为统一图聚类框架：nPnB 框架统一了对分区聚类和重叠聚类的评估，无论是从内在（相对于原始图）还是外在（相对于已知的 “ground-truth”）角度。通过定义 TP、TN、FP、FN 这四个指标，使得基于这些指标的任何度量（如 Precision、Recall、F_s、Jaccard、RandIndex 和 MCC）都可以用于评估任何聚类。这一框架的提出，解决了以往不同聚类方法难以比较的问题，为研究人员提供了一个统一的评估平台56。
• 基于 F_s优化的新聚类方法：nPnB 框架不仅可以用于比较聚类方法，还能定义新的聚类方法。研究人员提出了 BEC 算法，通过优化 F_s分数来寻找图聚类。该算法通过聚合过程，根据边的相似性度量依次遍历图的边，合并顶点的簇，以提高 F_s分数。实验表明，该算法在与其他最先进的聚类方法比较时，表现出了良好的性能78。
• nPnB 框架中的聚类比较：研究人员在标准的真实世界图（如电子邮件图 G_em）和人工图（如 BenchmarkER 和 BenchmarkLFR 生成的图）上对不同聚类方法进行了比较。在真实世界图上的比较发现，非参数化方法（如 Louvain、Infomap、Starling 和 Oslom）在 Precision 和 Recall 的权衡上存在差异；BEC 聚类家族在内在评估中表现优于其他方法；同时，作为 “ground-truth” 的部门分区（C_Dep）在电子邮件图中的 Precision 和 Recall 得分较低，这对其作为 “ground-truth” 的相关性提出了质疑。在人工图上的比较结果表明，不同方法在识别随机图中是否存在组结构以及在处理具有复杂社区结构的图时，表现各有优劣。例如，在 BenchmarkER 随机图中，一些方法在特定连接概率下才能识别出无组结构，而 BEC^s_p和 BEC^{s_ps0=0.15在连接概率足够大时能够识别；在 BenchmarkLFR 图中，不同方法在不同混合参数（μ）下的性能有所不同，BEC 方法在一些情况下表现出色910。}

研究结论和讨论部分指出，nPnB 框架具有诸多优势。它实现了聚类评估的统一，无论是内在还是外在评估，有重叠还是无重叠的聚类都能进行评估；评估基于广泛使用的 Precision 和 Recall 指标，简单易懂；能够内在评估 “ground-truth” 聚类的相关性；还为新聚类算法的设计提供了灵感，产生了 BEC 算法，并能获取关于复杂系统内在描述尺度的有用信息。然而，该框架也存在局限性，它仅考虑了图的边结构，未考虑节点的其他属性。未来的研究可以朝着考虑加权、有向和动态网络，以及结合节点属性的方向发展。这一研究为图聚类领域提供了新的思路和方法，推动了该领域的发展，有助于研究人员更好地理解和分析复杂系统中的社区结构。