本研究分析了现有图嵌入神经网络（GNN）在图着色问题中的表现差异主要是由于其无法应对节点异质性以及其局部性；通过研究聚集 - 合并 GNN（AC-GNN）的性能以及其基于局部搜索的特性，我们得出了一系列在实践中使 GNN 在图着色问题中更具有等变性和强大性的规则，并提出了一个简单的 AC-GNN 变体以验证我们的理论，并实现了比现有启发式算法更高质量和更快速运行的结果。

Aug, 2022

利用图神经网络解决图着色问题，将图着色视为多类节点分类问题，利用基于统计物理学的 Potts 模型的无监督训练策略。我们展示了该方法在实际应用中的性能，并提供了数值基准结果。

Feb, 2022

通过以图分割问题为基础的近似算法，定义了 “网络社区概要图”，来表征不同规模网络中最佳社区的结构，实证研究了 100 多个实际网络，在大型网络中发现与小型不同的社区结构，发展出 “森林火灾” 生长过程为基础的图生成模型。

Oct, 2008

本文介绍了如何使用简单的 GNN 架构来解决图着色的基本组合问题，并且展示了该模型在独立于训练数据的图数据上的泛化能力以及优于其他基线模型的表现。同时，我们还展示了如何将节点嵌入在多维空间中进行聚类，从而获得构造性解决方案。我们的结果有助于缩小人们对 GNN 算法学习的差距，并提供了符号推理与深度学习系统集成的可靠方法。

Mar, 2019

最近几年来，有大量的研究专注于扩展图神经网络（GNNs）的表达能力，超越 Weisfeiler-Lehman (1-WL) 框架。在这项研究中，我们从图搜索的角度探讨了 GNNs 的表达能力，提出了一种新的顶点着色方案，并证明经典的搜索算法可以高效地计算超越 1-WL 的图表示。我们展示了这种着色方案从图搜索中继承的有用特性，可以帮助解决图的双连通性问题。此外，我们还展示了在某些条件下，GNNs 的表达能力随着搜索邻域的半径逐层递增。为了进一步研究所提出的方案，我们基于广度优先搜索和深度优先搜索开发了一种新类型的 GNN，突出了它们在 1-WL 之上所能捕捉到的图属性。

Mar, 2024

本文通过引入颜色编码的方法，改进了消息传递神经网络（MPNNs）的表达能力，提出了一种使用颜色消除相同节点属性的图神经网络，名为 Colored Local Iterative Procedure (CLIP)，证明该方法是连续函数的通用逼近器，并实验验证了 CLIP 能够捕捉传统 MPNN 无法区分的结构特征，并且在基准图分类数据集中表现最佳。

Dec, 2019

这篇研究论文讨论了网络科学中一个重要的问题 —— 发现社群结构的方法和应用，分析了该问题的主要元素和当前已有的各种方法，重点介绍了统计物理学家们开发的技术。

Jun, 2009

本文描述了一种快速检测具有社群结构的网络的新算法，并给出了各种应用实例，比之前的算法更加高效。

Sep, 2003

新的信息理论方法揭示加权和定向网络中的社区结构，例如 6000 多种期刊的引用模式，发现多中心组织以及学科之间的定向引用模式。

Jul, 2007

对于给定的图形应用 NP-hard Cluster Editing 问题的标准算法可能会产生偏向于数据子组（例如人口群体）的解决方案，我们提出了一种修改公平性约束条件，以确保每个子组的修改次数与其大小成比例，模型在现实社交网络上的经验分析表明，修改公平性的代价惊人地低。

Dec, 2021