# Scalable Community Search over Large-scale Graphs based on Graph Transformer

# Community search

# 定义

在图（这里主要是指图论中的图，如社交网络图、网络图等）中，“community”（社区、社群）是指一组节点的集合。

一、结构特点

1. 内部紧密性
   • 社区内部的节点之间有相对紧密的连接。例如，在一个社交网络中，一个基于兴趣爱好形成的社区，其内部成员（节点）之间相互关注、互动频繁（边的连接较多）。以一个读书爱好者社区为例，社区中的成员可能会经常互相分享读书心得、推荐书籍，这些互动行为就体现在图结构中为节点之间存在较多的边。
   • 可以通过一些指标来衡量这种紧密性，如节点的度（与该节点相连的边的数量）。在一个社区中，节点的平均度可能会高于图中所有节点的平均度，这表明社区内部节点之间的连接较为丰富。
2. 相对独立性
   • 社区与图中其他部分（其他社区或孤立节点）的连接相对较弱。仍以社交网络为例，读书爱好者社区和体育爱好者社区之间的连接可能只是少数几个同时对读书和体育感兴趣的人，相比社区内部的连接要少得多。
   • 可以用边的密度来区分社区和非社区部分。社区内部边的密度较高，而社区与外部之间边的密度较低。

二、形成原因和意义

1. 形成原因
   • 共同属性或兴趣：在社交网络中，人们因为相同的爱好（如摄影、音乐）、背景（如校友、同事）等因素聚集形成社区。在信息网络中，比如网页之间因为主题相关（如都是关于科技新闻的网页）而构成一个社区。
   • 功能关联：在一些网络（如生物网络）中，基因或蛋白质之间由于功能上的协作关系而形成社区。例如，在一个细胞代谢网络中，参与同一种代谢途径的蛋白质会形成一个社区，它们共同完成特定的代谢功能。
2. 意义
   • 分析网络结构：有助于理解复杂网络的宏观结构。通过识别社区，可以将一个庞大复杂的图分解为相对简单的子结构进行研究。比如在研究互联网的拓扑结构时，识别出不同的自治系统（可以看作是一种社区）可以更好地理解网络的组织和信息流动方式。
   • 预测和推荐：在社交网络和推荐系统中，社区的存在可以用于预测用户行为和进行个性化推荐。如果一个用户属于某个社区，那么可以根据该社区其他成员的行为（如购买产品、访问网页等）来为这个用户推荐可能感兴趣的内容。在电商平台上，识别出购买某类商品的用户社区后，就可以向社区中的其他用户推荐相似的商品。

社区搜索旨在图结构中基于查询请求发现紧密相关的结点子集，这些结点子集在某种程度上形成了一个社区或群组.

# 与社区发现的区别

• 社区发现：通常使用相同的全局准则来决定一个子图是否可被视为一个社区，其准则是固定且预先确定的，关注的是对整个图进行静态的社区划分，不依赖于查询节点.
• 社区搜索：侧重于找到包含查询顶点的最有可能的社区，具有更高的个性化，允许查询用户指定更个性化的查询条件，使返回的社区更易于解释 ，并且在效率上更有优势，能够在子图上进行操作，而无需处理整个大规模图，尤其适用于从大数据图中查找特定社区.

# 摘要

# 基于图变换器的大规模图上可扩展社区搜索

Yuxiang Wang, Xiaoxuan Gou, Xiaoliang Xu 等

# 摘要

给定一个图$G$ 和一个查询节点$q$，社区搜索（CS）旨在从$G$ 中找到一个包含$q$ 且结构紧密的子图。CS 在许多现实应用中广泛使用，如在线推荐和专家发现。最近，基于学习的 CS 方法的兴起引起了广泛的研究兴趣，展示了神经解决方案的巨大潜力。然而，仍有优化空间：（1）它们通过经典方法（如独热编码、随机编码和位置编码）初始化节点特征，可能无法有效捕捉与社区紧密性相关的有价值特征。（2）对 GCN 或类似 GCN 的模型的依赖使得在扩展到大型图时面临挑战。（3）现有方法对动态图的适应性较差，通常需要从头重新训练。为了解决这些问题，我们提出了 CSFormer，一种基于图变换器的可扩展 CS 方法。首先，我们提出了一种基于$n$ 阶$h$ 指数的新颖$l$ 跳邻域社区向量来表示每个节点的社区特征，通过改变邻域范围$l$ 生成一系列特征向量。然后，我们构建一个变换器骨干网络来学习具有丰富社区特征的良好图嵌入，基于此执行基于预测 - 过滤的在线 CS，以有效地返回$q$ 的社区。我们将 CSFormer 扩展到动态图和各种社区模型。在七个真实世界图上的广泛实验表明我们的解决方案在有效性方面的优越性，例如，与最新的竞争对手相比，我们在$F1$ 分数上平均提高了$20.6\%$ 。

# CCS 概念

• 信息系统→基于图的数据库模型；信息检索查询处理。

# Introduction

# 引言

图在许多现实世界的信息网络（如社交网络和协作网络）中，普遍用于表示实体（即节点）及其关系（即边）[19, 32, 41, 54, 64, 77]。图数据挖掘已引起广泛的研究兴趣 [49]，其中社区搜索（CS）是一个基本问题 [5, 25, 73, 74]。给定一个图$G$ 和一个查询节点$q$，CS 旨在从$G$ 中找到一个包含$q$ 且紧密连接的子图。CS 在各种信息检索应用中广泛使用，如在线推荐 [7, 11, 17, 23, 27, 39, 45, 71]、专家发现 [63, 70] 和生物数据分析 [16, 28, 29, 43, 75]。例如，研究人员可以在协作网络（如 DBLP）上使用 CS 来根据返回的社区组织学术研讨会。在电影数据库（如 IMDB）中，为了给用户推荐电影，系统可以使用用户喜欢的一部电影作为查询执行 CS，并根据返回的电影社区推荐电影。

结构紧密性是衡量社区质量的一个重要指标。不同的社区模型（如$k$ - 核 [2, 14, 63, 68, 70]、$k$-truss [1, 33, 65] 和$k$ - 团 [15, 55, 62]）用于明确捕捉结构紧密性。图 1 展示了 DBLP 的一个快照，其中有 119 位研究人员，如果他们之前有过合作，则通过边相连。给定查询节点为图数据挖掘领域的著名研究人员 Jeffrey Xu Yu 教授，人们可以使用$k$ - 核（一个子图，其中每个节点的度$\geq k$）来表示他的研究社区，例如，用粗边连接的命名节点组成的子图。它包括来自同一研究领域的 21 位研究人员，且每位研究人员至少与其他 5 位研究人员合作过，显示出他们之间很强的紧密性。在衡量紧密性方面，[21] 将社区模型排序为 ++$k$ - 核 - truss - 团，其中表示比更紧密 ++。随着结构紧密性的增加，[21]。用计算效率会降低，顺序为 - 核 - truss - 团户可以根据自己的需求选择合适的模型。最近，基于学习的 CS 兴起，引起了广泛的研究兴趣。它利用社区标签进行监督学习，从而能够有效推断并高效检索社区。接下来我们简要讨论这类工作并提出我们研究的动机。基于学习的 CS 方法。在 [25] 中，作者提出了一个两阶段的基于近似最近邻搜索（ANNS）的图卷积网络（GCN）模型。它通过 GCN 将社区特征注入到图嵌入中。然后构建一个邻近图（PG）作为节点表示的索引，并在 PG 上进行近似最近邻搜索，以返回与查询最相似的节点作为社区成员。然而，PG 索引会引入额外的存储开销。相比之下，许多端到端的 CS 解决方案被提出以避免外部开销 [17, 24, 35, 37]。ICS - GNN [24] 训练一个节点分类模型并进行交互式 CS 以返回社区。QD - GNN [35] 利用 GCN 将查询节点$q$ 映射到一个社区向量，其中每个维度有一个二进制值，用于指示节点的社区参与情况。COCLE - P [37] 是一个基于对比学习的半监督解决方案。CGNP [17] 是一个基于图注意力网络（GAT）的任务通用节点嵌入函数用于聚类。上述解决方案的本质是使用 GNN（GCN 或类似 GCN 的模型）来捕捉结构特征，并基于社区标签完成模型训练。与基于图遍历的组合算法相比，灵活的学习和高效的在线推断展示了神经解决方案的巨大潜力。然而，它们仍然存在以下几个局限性.

# 局限性

1. 隐式结构特征常被忽视：上述解决方案主要依赖于显式图结构中的信息传播，使用独热编码、随机编码或位置编码进行向量初始化。然而，这些方法与社区紧密性的相关性较低，导致训练后的模型在与特定社区模型（如$k$ - 核和$k$-truss）相关的 CS 任务中表现不佳。
2. 对 GCN 或类似模型的依赖限制了处理大图的能力：原因有两方面：首先，像 QD - GNN 和 CGNP 这样的方法通过 GCN 嵌入节点的结构特征，邻接矩阵的大小（图形内存开销）主导了模型在大图上的可扩展性。此外，像 ICS - GNN 和 COCLE - P 这样的方法采用在图上提取或总结策略，以获得一个小子图或超图作为 GCN 或类似 GCN 模型的输入，从而实现对大图的可扩展性。然而，压缩图可能不可避免地导致全局结构特征的丢失，从而影响模型的推断效果。
3. 动态图中的模型失效问题：由于 GCN 或类似 GCN 的模型需要邻接矩阵作为输入，动态变化的图拓扑结构会改变邻接矩阵，使训练好的模型失效。

# 挑战与解决方案

我们预见到需要克服上述局限性的三个挑战，这促使我们研究基于 Transformer 的大规模图上可扩展 CS（CSFormer）。

1. 挑战一：++ 如何使用与社区紧密性高度相关的结构特征对图进行编码？++ 社区的结构紧密性与社区模型的定义高度相关。例如，$k$ - 核、$k$-truss 和$k$ - 团的结构紧密性由参数$k$ 控制。具体来说，$k$ - 核的$k$ 值与节点的度相关，即$k$ - 核中的每个节点必须至少有$k$ 个度$\geq k$ 的邻居 [23]；$k$-truss 的$k$ 值与每条边的支持相关，即$k$-truss 中的每个节点必须至少有$k - 1$ 条支持$\geq k - 2$ 的相邻边（引理 2）。提取与社区紧密性相关的特征对于促进 CS 任务很重要。在 §3.1 中，我们基于$n$ 阶$h$ 指数的概念为$k$ - 核社区模型提出了一种新颖的$l$ 跳邻域社区向量，使每个节点的初始特征向量包含更多与紧密性相关的信息。我们基于一个新的阶$h_{suf}$- 指数的概念将其扩展到$k$-truss 模型，该指数定义在边支持之上（§4.2）。在 §5.5 中，我们通过对比分析表明，所提出的方法比独热编码、随机编码和位置编码能更好地捕捉社区紧密性。
2. 挑战二：++ 如何使图学习模型适应大图而不牺牲全局结构特征？++GCN 和类似 GCN 的模型遵循聚合 - 传播方式来捕捉整个图的全局结构特征。为了提高在大图上的可扩展性，人们普遍认为通过采样、子图或超图技术减少图的大小是必要的 [24, 26, 37]。然而，这种减少可能会损害模型捕捉全局特征的能力，从而影响模型的质量。简而言之，在适应大图的同时保留全局特征涉及一个矛盾。这启发我们提出一种同时考虑这两个方面的新方法。我们构建一个带有基于注意力的读出函数的 Transformer 骨干网络，以处理$l$ 跳邻域社区向量序列，将核心度预测作为下游任务（§3.2）。参数$l$ 决定了用于训练的全局结构特征的范围（通常$l = 3$ 足以聚合丰富的全局信息）。Transformer 的使用使我们的方法能够适应大图，因为由于序列长度有限，注意力矩阵相当小。给定训练好的模型，我们在 §3.3 中提出一种基于局部预测 - 过滤的在线 CS 方法。
3. 挑战三：如何使图学习模型在一定程度上适应动态图？在现实应用中，图的拓扑结构通常会动态演变，例如，在社交网络中会有新用户引入新的关注关系。当图的拓扑结构变化适中时，我们期望提高模型的泛化能力，避免从头重新训练。在 §4.1 中，我们提出一种基于采样的方法来评估图的社区特征的变化程度。当图的变化适中时，我们的 1 - 邻域社区向量（§3.1）仍然可以很好地捕捉节点的社区特征。因此，我们可以采用与 §3.1 相同的过程对更新后的节点进行编码，并使用原始模型执行在线 CS 而无需重新训练。

# 贡献

我们的贡献总结如下：

1. 我们提出了一种基于$n$ 阶$h$ 指数概念的新颖邻域社区向量，以很好地捕捉与社区紧密性相关的结构特征，这有利于 CS 任务。
2. 我们提出了一种新的图学习方式，使用带有基于注意力的读出函数的 Transformer 编码器来处理所有节点的邻域社区向量序列，基于此通过轻量级核心度预测执行在线 CS。
3. 我们将我们的解决方案扩展到更一般的场景，包括动态图上的 CS 和具有各种社区模型的 CS。
4. 我们进行了广泛的实验来评估有效性和效率（§5.2 - 5.3）、案例研究（§5.4）、对比分析（§5.5）、参数敏感性（§5.6）和可扩展性分析（§5.7）。实验结果证明了我们解决方案的优越性。

# PRELIMINARYANDPROBLEM

# 预备知识与问题

我们考虑一个无向图$G=(V,E)$，其中$V$ 是节点集，$E$ 是边集。对于给定的节点$v\in V$，我们用$N(v)$ 表示其邻居节点，并使用$deg(v)=|N(v)|$ 来表示$v$ 的度。当$v$ 位于不同的图中时，我们将通过指定图的标识符来明确其度为$deg(v,G)$。作为第一步，在本文中，我们首先关注广泛研究的同构图。未来，我们将把我们的解决方案作为一个构建块，以支持更复杂的异构图。接下来，我们引入$k$ - 核模型来表示一个社区 [2, 22]，并在 §4 中将其扩展到其他模型。

# 定义 1（$k$ - 核 [4]）

给定一个图$G=(V,E)$ 和一个非负整数 $k$，$G$ 的$k$ - 核是最大子图 $H_k\subseteq G$，使得对于$\forall v\in H_k$ ，其度至少为$k$，即 $deg(v,H_k)\geq k$.

注意

$k$ 值越大，$H_k$ 的紧密性越强。然而，一个$k$ - 核可能是一个不连通的子图。例如，在图 2 (a) 中，3 - 核$H_3$（蓝色区域）由两个组件组成，这两个组件在$H_3$ 中通过节点和边不相连。这与社区的固有连通性约束 [25, 54] 不符，因此我们定义连通$k$ - 核如下。

# 定义 2（连通$k$ - 核 [54]）

给定一个图$G=(V,E)$ 和一个非负整数$k$，$G$ 的连通$k$ - 核是$k$ - 核$H_k$ 的一个连通分量$\hat{H}_k\subseteq H_k$ ，使得对于$\forall v\in\hat{H}_k$，$deg(v,\hat{H}_k)\geq k$。

由于

一个$H_k$ 通常包含多个$\hat{H}_k$ ，如有必要，我们添加一个上标来表示特定的一个为 $\hat{H}_k^i$。在图 2 (a) 中，$H_3$ 有两个连通 3 - 核 $\hat{H}_3^1$ 和$\hat{H}_3^2$ 。而$H_2$（不包括$v_{12}$ 的子图）只包含一个连通分量，所以$H_2=\hat{H}_2$。

# 在传统的社区搜索（CS）中

$k$ 是一个关键输入，用于指定查询节点$q$ 所属的社区。对于同一个$q$，通过提供不同的$k$，它可能属于不同的连通$k$ - 核。对于普通用户来说，指定合适的$k$ 是困难的。直观地说，最紧密的社区（具有最大的$k$）通常比其他具有较小$k$ 的社区更有价值 [65]。因此，我们接下来定义节点的核心度，并将其与连通$k$ - 核相结合，将本文研究的无$k$ 指定的 CS 问题形式化如下。

# 定义 3（核心度 [54]）

给定一个图$G=(V,E)$ 和一个节点$v\in V$，我们称$v$ 所属的$k$ - 核中的最大$k$ 为$v$ 的核心度，记为$k_{max}(v)$（简记为$k_{max}$）。

# 问题

给定一个图$G=(V,E)$ 和一个查询节点$q\in V$，我们的目标是找到一个子图$\hat{H}_k\subseteq G$ ，满足以下性质：

1. 查询参与性：$\hat{H}_k$ 包含$q$，即$q\in\hat{H}_k$.
2. 紧密性最大化：$\hat{H}_k$ 是一个连通$k$ - 核，其中$k = k_{max}(q)$。更准确地说，对于任何$k' > k_{max}(q)$，我们找不到另一个包含$q$ 的连通$k'$- 核$\hat{H}_{k'}$.
3. 社区最大化：对于任何$k' = k_{max}(q)$，我们找不到另一个连通$k'$- 核$\hat{H}_{k'}\supset\hat{H}_{k_{max}}$。这是因为连通$k$ - 核必须是一个连通分量（根据定义 2）.

示例 1

回顾图 2，如果我们将$v_5$ 和$v_8$ 作为查询节点（不提供特定的$k$），那么我们期望分别返回$\hat{H}_3^2$ 和$\hat{H}_3^1$ 作为社区。注意，$\hat{H}_3^2$ 和$\hat{H}_3^1$ 分别是$v_5$ 和$v_8$ 的最紧密社区，因为$k_{max}(v_5)=k_{max}(v_8)=3$.

显然 核心度小于等于度

# CS-ORIENTEDGRAPHTRANSFORMER

我们提出了一种面向社区搜索的图变换器模型（CSFormer），如图 3 所示。为了获得与社区搜索任务高度相关的代表性特征，我们提出了一个社区紧密性特征提取器，通过一系列新颖的邻域社区向量来初始化每个节点（§3.1）。为了适应大规模图，我们构建了一个带有基于注意力的读出函数的 Transformer 骨干网络，使用核心度预测作为下游任务来更新所有节点的邻域社区向量（§3.2）。结果，我们得到了一个训练良好的预测模型，能够有效地预测节点的核心度。由于与查询节点处于同一最紧密社区的所有节点的核心度必须$\ge k_{max}(q)$（引理 1），并且很可能位于 $q$ 的局部空间中 [36, 44, 65]，我们接着提出了一种基于局部预测 - 过滤的方法来高效地执行在线社区搜索（§3.3）.

# 紧密性特征提取器

在本节中，我们基于$n$ 阶$h$ 指数 [48] 的概念提出一种新颖的邻域社区向量，用于捕捉每个节点与社区紧密性相关的结构特征。

# $n$ 阶$h$ 指数

我们选择$n$ 阶$h$ 指数的原因在于它与节点的核心度密切相关，并且能够在线轻松计算，更多解释见定义 5。在此之前，我们首先给出$h$ 算子的定义。

# 定义 4（$h$ 算子）

考虑一个有限整数多重集$S$，函数$\phi_h:S\rightarrow\mathbb{N}_0$ 被定义为一个$h$ 算子，用于返回最大整数$h$，使得$S$ 中至少有$h$ 个元素$s$ 满足$s\geq h$。对于$S = \varnothing$ 的情况，我们定义$\phi_h(\varnothing)=0$.

# 定义 5（$n$ 阶$h$ 指数）

给定一个$h$ 算子$\phi_h(\cdot)$，节点$v\in V$ 的$h$ 指数定义为$h(v)=\phi_h(\{deg(u)|u\in N(v)\})$，其中$deg$ 表示节点的度，$N(\cdot)$ 表示节点的所有邻居。节点$v$ 的$n$ 阶$h$ 指数$h^n(v)$ 递归定义为

$$h^n(v)=\phi_h(\{h^{n - 1}(u)|u\in N(v)\})$$

其中$h^0(v)=deg(v)$.

对于$n = 0$ 和$n = 1$

$h^n(v)$ 的值分别表示$v$ 的度和$h$ 指数。随着$n$ 的增加，它收敛于$v$ 的核心度 [42]。更准确地说，我们说$h^n(v)$ 是$k_{max}(v)$ 的一个上界，即$h^n(v)\geq k_{max}(v)$.

示例 2

在图 3（左部分）中，

节点$v_7$ 的$h$ 指数（即$h^1(v)$）是$\phi_h(\{5,5,5,4,4\}) = 4$。

而$v_7$ 的 2 阶$h$ 指数是$\phi_h(\{h^1(v_6),h^1(v_{12}),h^1(v_{13}),h^1(v_{15}),h^1(v_8)\})=\phi_h(\{3,3,3,3,2\}) = 3$

注意，$n$ 阶$h$ 指数是$u$ 的核心度$k_{max}(v_7)=3$ 的一个上界，并且随着$n$ 的增加，这个上界会更紧.

一般而言

较大的$h^n(v)$ 通常表明$v$ 更有可能属于一个更紧密的社区，即具有更大的核心度$k_{max}(v)$，这表明$h^n(v)$ 与$v$ 的核心度紧密相关。此外，根据定义 5，$h^n(v)$ 可以通过从外到内的递归局部搜索有效地计算。因此，我们接下来设计一种基于$n$ 阶$h$ 指数的新颖邻域社区向量来表示节点的结构特征。

# 邻域社区向量

给定一个节点$v$ 和一个特定的$n$，$v$ 的邻域社区向量定义为$h^n(\cdot)$ 在$v$ 的所有邻居中的分布。

具体来说，我们使用所有节点$\in V$ 中最大的$h^n(\cdot)$ 值作为邻域社区向量的维度$d$。更准确地说，

这个向量的每个维度对应一个可能的$h^n(\cdot)$ 值，记为$h_x$。

因此，我们计算$v$ 的所有邻居（包括$v$ 本身）中每个$h_x$ 的出现频率，如公式 1 所示。然后，我们将其记录在$h_x$ 维度中。结果，我们得到了$v$ 的邻域社区向量，记为

$$\vec{v}=\{f(1,\{N(v),v\}),\cdots,f(d,\{N(v),v\})\}$$

其中

$$f(h_x,\{N(v),v\})=\frac{|\{u\in\{N(v),v\}|h^n(u)=h_x\}|}{|N(v)| + 1}$$

0 - 跳、1 - 跳、2 - 跳、3 - 跳

邻域社区向量$\vec{v}$仅基于$v$ 的 1 - 跳邻居的$h^n(\cdot)$ 进行初始化。为了提高$\vec{v}$的质量，合理的做法是从$v$ 的邻域聚合更多信息。因此，我们提出了$l$ 跳邻域社区向量。给定一个节点$v$，其$l$ 跳邻域社区向量$\vec{v}^l$ 通过公式 2 计算，其中$\vec{v}^0$ 是邻域社区向量本身.

$$\vec{v}^l=\frac{\vec{v}^{l - 1}+\sum_{u\in N(v)}\vec{u}^{l - 1}}{|N(v)+1|}（2）$$

公式 2 描述了一个聚合过程

其中$v$ 的$l$ 跳邻域（$l\geq1$）中所有节点与社区紧密性相关的结构特征将被注入到$v$ 的结构特征中。

示例 3

给定图 3（左部分）中的图，我们对所有节点的$l$ 跳邻域社区向量（$l\in[0,3]$）进行形式化，并在图 4 中提供了 16 个节点之间的成对余弦相似度热图。对于来自同一社区的节点，它们的相似度随着$l$ 的增加而增加，这意味着邻域社区向量可以很好地捕捉节点的紧密性特征。例如，对于$l = 3$，我们用两个红色椭圆标记了节点$\{v_7,v_{12},v_{13},v_{14},v_{15}\}$ 之间的成对相似度（$\geq0.95$），表明在这个例子中它们都属于同一个$\hat{H}_3$ 社区.

# 训练数据准备

通过设置不同的$l=\{1,\cdots,m\}$，我们可以得到$v$ 的各种邻域社区向量，以反映其在$G$ 的不同子图中的结构特征。很自然地，我们可以形成$v$ 的邻域社区向量序列，记为$V=[\vec{v}^1;\cdots;\vec{v}^m]\in\mathbb{R}^{m\times d}$，来表示其与紧密性相关的结构特征，这是与 Transformer 集成的关键（在 §3.2 中讨论）。给定一个图$G=(V,E)$，我们准备一个$|V|\times m\times d$ 的矩阵$v$ 作为训练数据。接下来，我们将展示如何通过下游的核心度预测任务将$V$ 输入到 Transformer 骨干网络中进行训练。

# 基于 Transformer 的核心度预测

Transformer 骨干网络由一系列连续的 Transformer 编码器构成，每个编码器包含多头自注意力（Multi-Head Self-Attention，MSA）和位置前馈网络（Position-Wise Feed-Forward Network，FFN）[6]。MSA 用于捕捉输入标记（在我们的情境中，节点的邻域社区向量就是输入标记）之间的语义相关性。对于节点$v$，其每个邻域社区向量$\vec{v}^i\in V$（$i\in[1,m]$）是$m$ 个标记中的一个。FFN 用于对 MSA 输出向量进行非线性变换，这有助于模型更好地捕捉序列中不同位置的语义关系和特征.

给定训练数据V\in\mathbb{R}^

我们将其划分为$\frac{|V|}{b}$ 个批次，批次大小为$b$，然后依次将这些批次输入到 Transformer 中进行训练.

# Transformer 编码

我们展示一批节点中每个节点$a$ 的序列向量$V$ 的 Transformer 编码过程。首先，我们使用一个可学习的线性投影将$V$ 映射到 Transformer 的隐藏维度$d$，如公式 3 所示，其中$E\in\mathbb{R}^{d\times\bar{d}}$ 是一个可学习的矩阵。我们将投影后的矩阵作为 Transformer 编码器第 0 层的输入，记为$\tilde{V}^0$，并且$\tilde{V}_i^0=\vec{v}^iE$ 是第$i$ 个标记.

$$\tilde{V}^0=[\vec{v}^1E;\vec{v}^2E;\cdots;\vec{v}^mE]$$

然后

我们将投影后的序列输入到 Transformer 编码器中，如公式 4 和 5 所示，其中$t$ 表示 Transformer 的第$t$ 层。我们按照 [56, 69] 实现 Transformer 编码器，其中在 MSA 和 FFN 块之前应用层归一化（LayerNorm，LN）。由于 MSA、FFN 和 LN 在 Transformer 相关研究中已被广泛介绍，我们建议读者参考 [6, 56, 69] 以获取更多详细信息。

$$\overline{V}^t = MSA(LN(\tilde{V}^{t - 1}))+\tilde{V}^{t - 1}$$

$$\tilde{V}^t = FFN(LN(\tilde{V}^{t}))+\tilde{V}^{t}$$

Transformer 编码器对输入$\overline{V}^0$ 的$t$ 层输出是一个矩阵$\tilde{V}^t\in\mathbb{R}^{d\times\tilde{d}}$，包含$m$ 个标记。我们接下来应用一个基于注意力的读出函数将$m$ 个标记聚合为一个$d$ 维向量$\vec{v}'$，如公式 6 所示，其中$\alpha_i$ 是第$i$ 个标记的归一化注意力系数，通过公式 7 计算。

$$\vec{v}'=\tilde{V}_0^t+\sum_{i = 1}^{m}\alpha_i\tilde{V}_i^t$$

$$\alpha_i=\frac{exp((\tilde{V}_0^t\parallel\tilde{V}_i^t))W^{\top}}{\sum_{i = 1}^{m}exp((\tilde{V}_0^t\parallel\tilde{V}_i^t))W^{\top}}$$

# 训练与核心度预测

将核心度预测作为训练的下游任务。给定一批训练数据（$b$ 个节点的序列）作为上述 Transformer 编码器的输入，我们得到$b$ 个节点的编码向量$[\vec{v}_1';\cdots;\vec{v}_b']\in\mathbb{R}^{b\times d}$。

对于每个$\vec{v}_i'$，我们将其输入到一个多层感知器中以获得预测向量$\vec{y}_{\bar{z}}$。每个维度$j\in[1,d]$ 填充一个软标签（通过 softmax 获得），表示节点$v_i$ 具有核心度$k_{max}(v_i)=j$ 的概率。然后，我们使用负对数似然损失函数 [78]（公式 8）来更新 CSFormer，其中$\vec{y}_i$ 是真实的社区向量，其中只有一个维度的值为 1（表示$v_i$ 的核心度），其他维度为 0。

$$\mathcal{L}(\vec{y},\vec{y}^*)=-\sum_{i = 1}^{b}\vec{y}_i\log\vec{y}_i^*$$

# 在线社区搜索

此部分主要介绍了如何基于训练好的 Transformer 骨干网络，通过预测 - 过滤的方式高效地执行在线社区搜索，以找到包含查询节点的最紧密社区。

# 算法流程

1. 输入与初始化
   • 算法接受一个图$G=(V,E)$ 和一个查询节点$q$ 作为输入。
   • 首先，通过公式 2 构造$q$ 的$l$ 跳邻域社区向量（$l$ 的值可根据具体情况设定，如对于小规模图$l = 6$，大规模图$l = 3$）。这一步骤利用了之前在紧密性特征提取器中定义的方法，获取查询节点周围一定范围内节点的特征信息，这些信息将作为后续判断节点是否属于目标社区的重要依据。
2. 核心度预测与节点筛选
   • 接着，使用训练好的模型预测$q$ 的核心度$k_{max}^*(q)$。
   • 从$q$ 开始进行$r$ 跳广度优先搜索（BFS），得到子图$G_q$，$G_q$ 中的节点作为初始的候选节点集。然后，对于$G_q$ 中的每个节点$v$，同样通过训练好的模型预测其核心度$k_{max}^*(v)$。根据引理 1，如果$k_{max}^*(v)<k_{max}^*(q)$，则将$v$ 从$G_q$ 中移除，因为这样的节点不太可能属于包含$q$ 的最紧密社区。引理 1 指出，包含查询节点的最紧密社区中的所有节点的核心度必须大于等于查询节点的核心度，这是筛选节点的重要理论依据。
3. 返回结果
   • 经过上述筛选后，返回$G[V_{G_q}]$，即$V_{G_q}$ 的导出图，它就是包含查询节点$q$ 的最紧密社区。

# 原理与优势

1. 基于局部性原理
   • 该方法基于小世界理论，认为社区成员具有很强的访问局部性，即两个节点如果位于彼此的局部空间中，则更有可能属于同一社区。所以通过在查询节点$q$ 的局部范围内（$r$ 跳内）进行搜索和筛选，能够高效地找到与$q$ 紧密相关的社区，避免了在整个图上进行搜索的高成本操作。
2. 高效性与准确性
   • 通过预测 - 过滤的方式，在早期就排除了大量不太可能属于目标社区的节点，减少了后续计算量，提高了搜索效率。同时，由于基于 Transformer 学习到的节点特征和核心度预测模型，能够更准确地判断节点是否属于紧密社区，从而提高了搜索结果的准确性。例如，在实际应用中，对于一个大规模社交网络中的用户查询，能够快速且准确地找到其所在的具有高度凝聚力的社区，如基于用户兴趣或社交关系形成的社区。

# 对用户输入特定$k$ 的支持

算法还考虑了用户输入特定$k$ 值的情况。如果$k<k_{max}(q)$，只需从$q$ 的$r$ 有界子图中过滤出预测核心度$\geq k$ 的节点；若$k>k_{max}(q)$，则可能无法找到包含$q$ 的符合要求的社区，因为$q$ 所属的最紧密社区是$k_{max}$- 核，这体现了算法在不同用户需求下的灵活性和适应性。

# EXTENSION

We extend our CSFormer to more general scenarios: (1) CS on dynamic graphs and (2) CS with different community models.

# 扩展到动态图

在现实世界的应用中，图通常会动态更新。之前依赖于 GCN 或类似 GCN 模型的研究在处理图的拓扑结构动态变化时存在问题。这是因为拓扑结构的变化会导致邻接矩阵的维度发生变化，从而使训练好的模型失效。

与传统方法对比

传统方法由于依赖于固定结构的邻接矩阵，当图发生动态变化（如节点或边的增加、删除）时，需要重新训练模型，这在实际应用中往往是低效且不现实的，尤其是对于大规模动态图。例如，在社交网络中，新用户的加入或用户之间关系的变化（如关注、取关）会频繁改变图的结构，如果每次都重新训练模型，计算资源和时间成本将非常高昂。

# CSFormer 在动态图中的优势

1. 基于邻域社区向量的适应性
   • 我们的 CSFormer 具有一定程度的动态图泛化能力，因为它不依赖于邻接矩阵，而是依赖于在 §3.1 中讨论的邻域社区向量。邻域社区向量能够通过节点的局部邻域信息捕捉其社区特征，这些特征相对稳定，不太容易受到图中局部拓扑变化的影响。例如，在一个科研合作网络中，新加入的研究人员（新节点）可能只会对其直接邻居的社区特征产生较小的影响，而不会像在基于邻接矩阵的方法中那样导致整个模型失效。
2. 模型重用策略
   • 当图更新时，如果节点的邻域社区向量在更新前后相似，那么训练好的 CSFormer 可以直接用于处理更新后的图，无需重新训练。例如，在图 5 中，当插入节点$v_8$ 时，其他节点（如$v_2$ 和$v_6$）的$h$ 指数并未改变，这意味着它们的邻域社区向量基本不变。在这种情况下，原本用于处理原始图的模型仍然可以有效地预测$v_8$ 的核心度，因为模型已经学习到了这些相似的结构特征，从而实现了模型的重用，提高了处理动态图的效率。

# 评估动态图变化程度的方法

为了确定在动态图中是否需要重新训练模型，我们提出了一种简单的评估方法。可以从图中随机抽取一个样本节点，然后评估这些节点中结构特征（例如基于$h$ 指数的邻域社区向量）略有变化的节点比例。如果这个比例较小，通常意味着可以考虑重用模型；反之，如果比例较大，则可能需要重新训练模型。在实验研究 §5.7 中，我们将研究 CSFormer 在不同更新强度的动态图上的可扩展性，通过实际的实验数据来验证和分析 CSFormer 在动态图场景下的性能表现，包括在不同更新策略（如仅节点插入、仅节点删除、节点插入和删除混合）下的有效性（如通过$F1$ 分数衡量）等指标，进一步展示 CSFormer 在处理动态图方面的优势和局限性，为实际应用提供参考依据。

# 扩展到$k$-truss 社区模型

除了$k$ - 核模型，$k$-truss [33] 是另一种流行的模型（见定义 7），其同样旨在衡量社区的结构紧密性。我们的 CSFormer 可以通过对整个框架进行小的修改，轻松扩展以适应$k$-truss 模型。我们首先从与$k$-truss 模型相关的一些必要定义开始。

# 定义 6（支持 [57, 72]）

给定一条边$e_{uv}\in E$，我们定义$e_{uv}$ 的支持为包含$e_{uv}$ 的三角形的数量，即$\sup(e_{uv}) = |\Delta_{uvw}|$，其中$w\in V$ 是$u$ 和$v$ 的共同邻居。因此，$\sup(e_{uv})$ 可以通过$|N(u)\cap N(v)|$ 计算得到。

# 定义 7（$k$-truss[33, 72]）

给定一个图$G$ 和一个整数$k\geq2$，$k$-truss 被定义为$G$ 中最大的子图$T_k\subseteq G$，其中每条边的支持至少为$k - 2$，即$\sup(e)\geq k - 2$。

# 定义 8（连通$k$-truss）

给定一个图$G=(V,E)$ 和一个非负整数$k$，$G$ 的连通$k$-truss 是$k$-truss$T_k$ 的一个连通分量$\hat{T}_k\subseteq T_k$，使得对于$\forall e\in\hat{T}_k$，$\sup(e)\geq k - 2$.

# 定义 9（Trussness [31, 57]）

给定一个图$G=(V,E)$ 和一个节点$v\in V$，我们称$v$ 所属的$k$-truss 中的最大$k$ 为$v$ 的 trussness，记为$k_{max}^t(v)$（简记为$k_{max}^t$）。

我们按照与$k$ - 核模型相同的思路为$k$-truss 模型提取结构特征。

具体来说

我们首先基于边支持提出一个新的$h_{sup}$ 算子，然后形式化一个新的$n$ 阶$h_{sup}$- 指数，这是反映节点结构特征的基础。我们先给出一个引理如下，然后定义$h_{sup}$ 算子和$n$ 阶$h_{sup}$- 指数。

# 引理 2

假设一个节点$v$ 属于一个$k$-truss$T_k$，那么$v$ 至少有$k - 1$ 条相邻边的支持$\sup(e)\geq k - 2$。

# 证明

由于$v$ 属于$T_k$，存在至少一条$v$ 的相邻边，记为$e_{vu}$ 也在同一个$T_k$ 中，其中$u$ 是$v$ 的邻居。根据定义 7，$e_{vu}$ 的支持$\sup(e_{ou})\geq k - 2$，这表明$v$ 和$u$ 至少有$k - 2$ 个共同邻居属于同一个$T_k$。对于每个共同邻居$w$，边$e_{vw}$ 仍然满足$\sup(e_{vw})\geq k - 2$ 的约束。因此，对于节点$v$，它至少有$k - 1$ 条相邻边的支持$\sup(e)\geq k - 2$。

# 定义 10（$h_{sup}$ 算子）

考虑一个有限整数多重集$S$，函数$\phi_{h_{sup}}:S\rightarrow\mathbb{N}_0$ 是一个$h_{sup}$ 算子，用于返回最大整数$h_{sup}-1$，使得$S$ 中至少有$h_{sup}-1$ 个元素$s$ 满足$s\geq h_{sup}-2$。对于$S=\varnothing$，我们定义$\phi_{h_{sup}}(\varnothing)=0$。

# 定义 11（$n$ 阶$h_{sup}$- 指数）

给定一个$h_{sup}$ 算子$\phi_{h_{sup}}(\cdot)$，节点$v\in V$ 的$h_{sup}$ 指数定义为$h_{sup}(v)=\phi_{h_{sup}}(\{\sup(vu)|u\in N(v)\})$，其中$\sup(\cdot)$ 表示边的支持，$N(\cdot)$ 表示节点的所有邻居。节点$v$ 的$n$ 阶$h_{sup}$- 指数$h_{sup}^n(v)$ 对于$n\geq2$ 递归定义为$h_{sup}^n(v)=\phi_{h_{sup}}(\{h_{sup}^{n - 1}(u)|u\in N(v)\})$，即$h_{sup}^1(v)$ 就是$h_{sup}$ 指数$h_{sup}(v)$。

# 与$n$ 阶$h$ 指数类似

$n$ 阶$h_{sup}$- 指数是 trussness 的上界。因此，我们通过将公式 1 中的$n$ 阶$h$ 指数替换为$n$ 阶$h_{sup}$- 指数来为$k$-truss 建立邻域社区向量。然后，我们可以通过公式 2 为$k$-truss 形式化一个新的$l$ 跳邻域社区向量。

# 给定上述为$k$-truss 重新定义的结构特征

我们生成一组训练数据并将其输入到我们的 Transformer 骨干网络中，使用 trussness 预测作为下游任务来训练模型。接下来，我们按照算法 1 的过程执行在线社区搜索。值得一提的是，我们对算法 1 进行了修改以提高结果的质量。考虑以下示例：给定一个节点$v$ 及其一个邻居$u$，如果它们都有$k_{max}^t(\cdot)\geq k_{max}^t(q)$，但边$e_{uv}$ 的支持$\sup(e_{uv})<k_{max}^t(q)-2$，那么$e_{uv}$ 必须被排除在$q$ 的连通$k_{max}^t(q)$-truss 社区之外。因此，我们在算法 1 的第 9 行之后添加了一个基于上述条件的连通性检测，并返回$q$ 的连通分量作为结果。

# 时空复杂度

# 时间复杂度计算

1. 训练时间复杂度
   • 计算训练时间复杂度时，主要考虑 Transformer 骨干网络的计算开销，因为其在训练过程中占据主导地位。
   • 在 Transformer 中，计算复杂度主要来源于多头自注意力（MSA）模块。对于一个包含$|V|$ 个节点的图，将其输入数据$V$ 划分为$\frac{|V|}{b}$ 个批次，每个批次大小为$b$。
   • 在计算 MSA 时，对于每个节点的每个邻域社区向量（共$m$ 个），都需要与其他向量进行注意力计算。计算注意力时，对于长度为$m$ 的序列，计算复杂度为$O(m^2)$。但由于采用了多头注意力机制，设头数为$h$，则总的计算复杂度为$O(h\times m^2)$。这里为了简化分析，假设$h$ 与其他参数的关系不大，在后续分析中暂不考虑其影响（实际中$h$ 通常是一个较小的常数）。
   • 此外，对于每个节点，还需要进行线性投影（公式 3）、层归一化（LN）以及位置前馈网络（FFN）的计算。线性投影和 LN 的计算复杂度相对较低，可视为常数级操作，主要的计算开销仍在 MSA 和 FFN 中。FFN 的计算复杂度为$O(md^2)$（其中$d$ 为隐藏维度）。综合起来，对于一个批次内的计算复杂度约为$O(bm^2 + bmd^2)$。由于$m$ 通常较小（通过合理设置$l$ 值来控制），与$d$ 相比，$m^2$ 的增长速度更快，所以在实际分析中可近似认为计算复杂度为$O(bm^2d)$。
   • 考虑到整个图的训练需要遍历所有批次，因此总的训练时间复杂度为$O(\frac{|V|}{b}\times bm^2d)=O(|V|m^2d)$。又因为$m = l + 1$（$l$ 为跳数，加上自身节点共$l + 1$ 个向量），所以最终训练时间复杂度为$O(b(l + 1)^2d)$。
2. 在线查询时间复杂度
   • 在在线社区搜索（算法 1）中，查询时间主要花费在两个部分：一是构造查询节点$q$ 的$l$ 跳邻域社区向量（公式 2），二是对$q$ 的$r$ 跳范围内的节点进行核心度预测和筛选。
   • 构造$l$ 跳邻域社区向量时，对于每个跳数$i$（$i$ 从 1 到$l$），需要遍历$q$ 的邻居节点，计算复杂度为$O(deg(q)\times l)$（其中$deg(q)$ 为$q$ 的度）。通常$deg(q)$ 是一个较小的值（相对于图的规模$|V|$），在大规模图中，$l$ 的取值也相对较小（如$l = 3$ 或$6$），所以这部分的计算复杂度相对较低。
   • 在核心度预测和筛选阶段，需要对$q$ 的$r$ 跳范围内的节点进行预测和比较。最坏情况下，$r$ 跳范围内的节点数量可能达到$|V|$（当图是完全连通时），但在实际的稀疏图中，这个数量通常远小于$|V|$。设平均情况下$r$ 跳范围内的节点数量为$k$（$k\ll|V|$），则预测核心度的计算复杂度为$O(kd)$（$d$ 为隐藏维度），筛选节点的比较操作复杂度为$O(k)$。因此，在线查询时间复杂度大致为$O(deg(q)\times l + kd + k)$，在实际情况中，主要的计算开销来自于核心度预测部分，即$O(kd)$。

# 空间复杂度计算

1. 模型参数空间复杂度
   • 空间复杂度主要由两部分组成，首先是模型参数部分。Transformer 编码器中的参数主要来自于多头自注意力（MSA）和位置前馈网络（FFN）。
   • 在 MSA 中，对于每个头，需要有$d\times d$ 的权重矩阵（用于计算查询、键和值），共$h$ 个头，所以 MSA 的参数复杂度为$O(hd^2)$。在 FFN 中，有两个线性层，参数复杂度为$O(2d^2)$。综合起来，Transformer 编码器一层的参数复杂度为$O((h + 2)d^2)$。设 Transformer 编码器有$n$ 层，则模型参数的空间复杂度为$O(3nd^2)$（这里$3$ 是一个近似系数，包含了 MSA 和 FFN 的主要参数部分）。
2. 计算过程中的中间数据空间复杂度
   • 另一部分空间复杂度来自于计算过程中的中间数据，主要是注意力矩阵和隐藏节点表示。
   • 在计算注意力时，需要存储注意力矩阵，其大小为$b\times m\times m$（$b$ 为批次大小，$m = l + 1$），所以注意力矩阵的空间复杂度为$O(bm^2)=O(b(l + 1)^2)$。同时，在 Transformer 编码过程中，每个节点的隐藏表示维度为$d$，对于一个批次内的节点，隐藏表示的空间复杂度为$O(bd)$。综合起来，这部分的空间复杂度为$O(b(l + 1)^2 + bd)$。
   • 因此，总的空间复杂度为模型参数空间复杂度与计算过程中间数据空间复杂度之和，即$O(b(l + 1)^2 + bd + 3nd^2)$.