Clustering Large Attributed Graphs: A Balance between Structural and Attribute Similarities

社交网络、传感器网络、生物网络和许多其它信息网络都可以建模为一个大图。图顶点表示实体，图边表示他们的关系或交互。在许多大图中，通常每个图顶点都关联有一个或多个属性来描述其属性。在许多应用领域，图聚类技术对于检测大图中连接紧密的组以及理解和可视化大图非常有用。图聚类的目标是基于各种标准，如顶点连通性或邻接相似性，将大图中的顶点划分为不同的簇。现有的许多图聚类方法主要关注拓扑结构进行聚类，而很大程度上忽略了通常是异构的顶点属性。本文提出一种新的图聚类方法​SA-Cluster，它通过统一的距离度量在结构和属性相似性之间实现了良好的平衡。我们的方法将于属性相关的大型图划分为​k个簇，以便每个簇都包含具有同质属性值的密集连接子图。提出了一种有效的方法来自动学习结构相似性和属性相似性的贡献程度。理论分析表明，​SA-Cluster通过迭代聚类细化快速收敛。

背景：

如今，许多信息网络可用于分析，包括社交网络、传感器网络和生物网络。作为一个特定示例，社交网络正随着社交应用和媒体的出现和快速普及而迅速扩展。图作为一种富有表现力的数据结构，通常用于对上述许多应用领域中对象之间的结构关系进行建模。图聚类是一个有趣且有挑战性的研究问题，最近受到了广泛的关注。在大规模的图上进行聚类，旨在将图划分为若干个密集连接的组件。这对于理解和可视化大型图非常重要。图聚类的典型应用包括社交网络中的社区检测，或是蛋白质相互作用网络中相关的蛋白质模块识别等。许多现有的图聚类方法主要关注图的拓扑结构，以便每个分区都实现一个内聚的内部结构。此类方法包括基于归一化割集的聚类、模块化或结构密度。另一方面，最近提出的图摘要方法旨在根据属性相似性对图进行分区，以便将具有相同属性值的所有节点分组到一个分区中。

图聚类与传统关系数据聚类之间的主要区别在于，图聚类基于连通性（例如，两个节点之间的可能路径数）或结构相似性（例如，两个节点的公共邻居数）来度量节点相似度，而关系数据聚类主要基于属性相似性（例如，两个属性向量之间的欧几里得距离）来度量两个数据点之间的距离。

在由许多实际应用形成的信息网络中，图拓扑结构和节点属性都是分析的重要特征。例如，在社交网络中，顶点属性描述了一个人的角色，而拓扑结构则表示一圈人之间的关系。为了将一个大图划分为集群，将那些紧密连接且具有相似特征的节点分配到同一个集群中是自然而然的。然而，上面提到的现有的图聚类和概括方法只考虑图属性的一个方面，而忽略了另一个方面（即只考虑节点属性或只考虑拓扑关系）。因此，由此生成的簇要么在簇内具有相当随机的顶点属性分布（只考虑拓扑关系），要么具有相当松散的簇内结构（只考虑节点属性）。理想的图聚类应该生成拓扑关系与节点属性都相似的簇类即平衡拓扑结构相似与节点属性相似。

示例：

在上图中，图1(a)展示了一个合著者图的示例，图中一个顶点表示一个作者，一条边表示两个作者之间的合著者关系。此外，每个作者都有一个作者ID和一个或多个主要主题。研究主题被认为是描述顶点属性的一个属性。其中，作者​r_1 \to r_7研究XML，作者​r_9\to r_{11}研究Skyline，​r_8研究两者。那么给定簇类数量​k=2，我们可以根据聚类标准以多种可能的方式将图划分为两个簇类。

• 基于结构的聚类。图1(b)展示了基于顶点连通性（即合著者关系）的聚类结果。聚类内的作者紧密相连。然而，在一个聚类中，作者研究主题截然不同；例如，其中一半从事XML的研究，另一半从事Skyline的研究。
• 基于属性的聚类。图1(c)展示了基于属性相似性的另一种聚类结果，即主题。簇类中的作者研究相同的主题。然而，由于分区，合著者关系丢失，因此作者在其中一个簇类中相当孤立，也就是丢失了合著者之间的关联。
• 基于结构和属性的聚类。图1(d)展示了基于结构和属性信息的聚类结果。该剧类结果平衡了结构和属性相似性：一个簇内的作者紧密相连；同时，他们在研究主题上是同质的。这是我们希望在这项工作中实现的结果。

SA-Cluster:

我们在本文中研究的问题是基于结构和属性相似性对具有顶点属性的大规模图进行聚类。我们将具有顶点属性的此类图称为属性图。目标是将属性图划分为​k个具有结构与属性都相似的簇类。这个问题颇具挑战性，因为结构相似性和属性相似性是两个看似独立甚至相互冲突的目标；在上述的示例中，彼此合作的作者可能具有不同的属性，例如研究课题、职位、隶属关系等；而从事相同课题的作者可能来自不同的组，因此他们从未合作甚至可能竞争。如何平衡这两个目标尚不清楚。一种可能的解决方案是设计两个顶点​v_i和​v_j之间的距离函数，如下所示：

d(v_i,v_j) = \alpha\cdot d_S(v_i,v_j)+\beta\cdot d_A(v_i,v_j)

其中​d_S(v_i,v_j)与​d_A(v_i,v_j)分别表示对于两个顶点之间的结构距离与属性距离的度量，而​\alpha与​\beta是加权因子。虽然这种方法简单，但是难以设置、调整参数以解释加权距离函数。对于图1(a)中的示例，用户不清楚合著者关系的权重应大于还是小于研究主题相似性的权重。

在本文中，我们寻求通过图增强将结构相似性和属性相似性整合到一个统一的框架中。我们将一组属性顶点插入到图​G中。属性顶点​v_{jk}表示“属性-值”对​(\alpha_j , \alpha)。如果一个顶点​v_i在属性​\alpha_j上的值为​\alpha_{jk}，则在​v_j和​v_{jk}之间添加一个属性边。为了避免混淆，原始顶点成为结构顶点，原始边成为结构边。通过这种图增强，我们将属性相似性表示为途中的顶点邻域：共享属性值的两个顶点通过一个公共属性顶点连接。在扩充图中，两个结构顶点​v_i和​v_j如果通过许多其他结构顶点连接，或者如果他们共享许多公共属性顶点作为邻居，或者两者兼有，则它们是接近的。然后，我们能够设计一种距离度量方法，它通过结构边和属性边来估计图中顶点对之间的接近程度。接着，我们可以依据随机游走距离进行图聚类。在这个问题设定中，我们确定了以下挑战。

1. 调整结构相似性和属性相似性的贡献度。结构边和属性边是不同类型的，在随机游走路径中可能具有不同的重要程度。不同的属性也可能由于其不同的聚类倾向而在随机游走距离中具有不同的贡献。例如，研究主题可能是将具有相似主题的研究人员分组的一个很好的属性，而诸如从属关系和性别之类的属性可能没有良好的聚类倾向。为了对属性的贡献度建模，我们为每个属性分配一个权重。然后，我们需要一种机制来区分不同属性边的权重，并且需要一种学习算法来在我们呢对图进行分区时自动调整权重。

2. 保证聚类收敛。我们将设计一个聚类目标函数，并旨在对其进行改进以实现收敛。但随着属性边权重的调整，随机游走距离会发生改变。因此，如果我们将图聚类过程和属性边权重调整交替进行，以逐步改善聚类质量。

3. 快速随机游走距离计算。为了使用邻域随机游走模型，我们必须对归因图的转移概率矩阵执行矩阵乘法，以计算成对顶点接近度的数值。由于矩阵乘法计算成本高，我们需要设计一些矩阵运算优化技术来提高效率。

本文主要贡献：

1. 我们研究了对大型属性图进行聚类的问题。我们提出了一种统一的距离度量来结合结构相似性和属性相似性。将属性顶点和边添加到原始图中，以连接共享属性值的顶点。因此，如果顶点共享属性值，则它们会变得更近。使用邻域随机游走模型通过结构和属性边来测量增强图上的顶点接近度。（一种基于邻域随机游走的模型被用来通过结构和属性边测量增强图中顶点的接近度。）==通过结构和属性边使用一种基于邻域随机游走的模型测量增强图中顶点的相似程度==
2. 提供理论分析，以量化属性相似性对用于测量顶点接近度的统一随机游走距离的贡献。
3. 提出一种权重自适应方法来学习随机游走距离中不同属性的贡献度。我们还证明了属性边权重被调整为聚类收敛的方向。
4. 我们还设计了一些基于矩阵诺伊曼级数的技术，以加快随机游走距离计算的矩阵计算方法。它将矩阵乘法的时间复杂度从​O(l)减少到​O(\log_2l)，其中​l是随机游走的长度限制。
5. 我们使用大规模真实社交图对我们提出的聚类方法进行了广泛的评估，证明了我们的方法能够将图划分为具有内聚结构与同质属性值的高质量簇类。此外，我们通过实验表明，我们的聚类算法收敛得非常快。

1. 问题描述

属性图可以通过​G(V,E,\Lambda)进行表示，其中​V是图中的顶点集合，​E是图中的边的集合，​\Lambda = \{\alpha_1,\dots,\alpha_m\}是与​V中顶点相关的​m个属性集合，用于描述顶点的属性。每个顶点​v_i\in V都与一个属性向量​[\alpha_1(v_i),\dots,\alpha_m(v_i)]相关联，其中​\alpha_j(v_i)是顶点​v_i在属性​\alpha_j上的属性值。我们通过​|V| = N表示顶点集合中的顶点数量。

属性图的聚类目的是将属性图​G划分为​k个不相交的子图​G_i = (V_i,E_i,\Lambda)，其中​V = \cup_{i=1}^{k}V_i且对于任一​i\ne j，​V_i\cap V_j = \phi。属性图的理想聚类结果应在以下两个属性之间取得良好的平衡：1. 一个簇类中的顶点在结构上彼此接近，而不同簇类之间的顶点彼此远离。2. 一个簇类中的顶点具有相似的属性值，而不同簇类之间的顶点可能具有非常不同的属性值。

在属性图聚类问题中，有两个主要问题：1. 距离度量 2. 聚类算法

2. 属性图聚类中的距离

2.1 结构相似度评估

在一个大的图​G中，一些顶点彼此靠近，而另一些顶点则基于连通性而彼此相距甚远。如果有多条路径连接两个顶点​v_i和​v_j，那么很容易从​v_i到达​v_j；反之亦然。从这个角度来说，我们称​v_i和​v_j是接近的。另一方面，如果​v_i与​v_j之间几乎没有路径，那么它们就是相距较远的。在本文中，我们使用邻域随机游走距离来测量顶点接近度。

定义一：邻域随机游走距离

令​P为图​G的​N\times N转移概率矩阵，给定​l为可随机游走的长度，​c\in(0,1)为重新游走概率，则从​v_i到​v_j的随机游走距离​d(v_i,v_j)定义为：

上式中，​\tau是从​v_i到​v_j的一条长度为​length(\tau)的路径，并且其转移概率为​p(\tau)

邻域随机游走距离的矩阵形式为：

此处，​P是图​G的转移概率矩阵，​R是邻域随机游走距离矩阵。​c(1-c)^{\gamma}表示在不重新开始得情况下回到​\gamma步的概率。根据该式，随机游走距离矩阵的递归形式为：

那么，顶点​v_i与​v_j之间的结构相似度​d_S(v_i,v_j)：

此处需要注意的是，在邻域随机游走中，我们只考虑长度为​l的随机游走，即随机游走仅在具有重启概率​c的顶点的​l步邻域中进行。当​l\to\infty时，邻域随机游走与现有工作中定义的带重启的随机游走相同。

2.2 统一距离度量

在属性图中，每个顶点都与一组属性​\Lambda = \{\alpha_1,\dots,\alpha_m\}相关联，这些属性描述了顶点的特性。一种直接结合结构相似性与属性相似性的方法是使用加权距离函数，如​d(v_i,v_j) = \alpha\cdot d_S(v_i,v_j)+\beta\cdot d_A(v_i,v_j)中的两个加权因子​\alpha与​\beta。虽然这种方法很简单，但设置参数和解释加权距离函数并不容易。我们提出使用基于邻域随机游走模型的统一距离度量来组合结构相似性和属性相似性，而不是分别对结构相似性与属性相似性进行建模。在定义距离度量之前，我们先定义一个属性增强图。

定义二：属性增强图

给定一个属性图​G(V,E,\Lambda)，其中​\Lambda = \{\alpha_1,\dots,\alpha_m\}，属性​\alpha_i的域（可能值的集合）为​Dom(\alpha_i) = \{\alpha_{i1},\dots,\alpha_{in_i}\}，其中​|Dom(\alpha_i)| = n_i为属性​\alpha_i域的大小。属性增强图表示为​G_\alpha = (V \cup V_\alpha , E\cup E_\alpha)，其中​V_\alpha = \{v_{ij}\}_{i=1,j=1}^{m,n_i}是属性顶点集合。属性顶点​v_{ij}\in V_\alpha表示第​i个属性取第​j个数值。当且仅当​\alpha_j(v_i) = \alpha_{jk}，边​(v_i,v_{jk})\in E_\alpha，即结构顶点​v_i在属性​\alpha_j上取值为​\alpha_{jk}。称​(v_i,v_j)\in E为结构边，称​(v_i,v_{jk})\in E_{\alpha}为属性边。

在属性增强图中，我们添加了一组“虚拟”顶点​V_{\alpha}，其中每个虚拟顶点表示一个(属性，值)对应关系“对”。如果顶点​v_i在第​j个属性上取第​k个值，则在顶点​v_i\in V与顶点​v_{jk}\in V_\alpha之间加一条边。由于每个顶点​v_i\in V具有​m个属性值，因此在原始图​G中一共添加了​|V|\cdot m个属性边。

上图展示了在本文作者主题示例上的属性增强图。添加了表示主题“XML”与“Skyline”的两个属性顶点​v_{11}与​v_{12}。具有对应主题的作者分别以虚线连接到两个顶点。通过属性边，如果作者共享一个共同的主题，那么原本鼓励的作者会变得更加接近，例如作者​r_1和​r_5。

我们提出在属性增强图​G_\alpha上使用邻域随机游走模型来计算​V中顶点之间的统一距离。属性增强图​G_\alpha上的随机游走与原始图​G上的随机游走之间的一个重要区别是，如果两个顶点​v_i,v_j\in V在属性​\alpha_k上具有相同的属性值​\alpha_{kp}，那么它们将有一个新的公共邻居，即属性顶点​v_{kp}\in V_\alpha。因此在​v_i与​v_j之间存在一个通过​v_{kp}的随机游走路径。显而易见的是，两个顶点共享的属性值越多，那么在顶点之间存在的随机游走路径就越多。由于，​|Dom(\alpha_i)| = n_i，​\forall\alpha_i\in\Lambda，​|V\cup V_\alpha| = |V| + |V_\alpha| = N + \sum_{i=1}^{m}n_i。属性增强图的转移概率矩阵就是一个​|V\cup V_\alpha| \times |V\cup V_\alpha|的矩阵。转移概率矩阵​P_A(v_i,v_j)的定义如下。

结构边​(v_i,v_j)\in E与属性边​(v_i,v_{ij})\in E_\alpha属于不同类型，第​m个属性也可能具有不同的重要程度。因此，它们在随机游走距离中可能具有不同的贡献度。在不失一般的情况下，我们假设结构边具有​\omega_0权重，对应的每一个属性边​\alpha_1,\alpha_2,\dots,\alpha_m都有一个边的权重​\omega_1,\omega_2,\dots,\omega_m。因此，通过结构边从顶点​v_i到顶点​v_j的转移概率：

其中​N(v_i)表示​v_i的结构顶点邻居的集合。类似的，从​v_i通过属性边到​v_{jk}的转移概率：

从​v_{ik}通过属性边到​v_j的转移概率为：

最后，由于两个属性顶点之间没有边，因此两个属性顶点​v_{ip}和​v_{jq}之间的转移概率为0。

由于每个顶点在属性​\alpha_i上都有一个值，因此也应该满足以下约束：

结合上述公式，可以计算属性增强图​G_\alpha的转移概率矩阵​P_A。

上图显示了本文示例重所有结构顶点即作者​r_1 \to r_{11}与属性顶点即文章主题​v_{11}\to v_{12}集合上的转移概率矩阵。我们初始化​\omega_0 = \omega_1 = 1.0作为初始权重。后续会介绍一种自动调整这些边缘权重的机制。

定义三：统一邻域随机游走距离

设​P_A为属性增强图​G_\alpha的转移概率矩阵。给定​l为随机游走长度，​c\in(0,1)为重启概率，则​G_\alpha中从​v_i到​v_j的统一邻域随机游走距离​d(v_i,v_j)定义如下：

其中，​\tau为​v_i到​v_j得一个路径，该路径长度为​length(\tau)，转移概率为​p_A(\tau)。

属性增强图中邻域随机游走距离得矩阵形式：

其中，​P_A是图​G_\alpha的转移概率矩阵，​R_A是邻域随机游走距离矩阵。对于作者-主题而言，给定图上图中的​P_A，​c=0.2和​l=2，则​R_A^2(r_1,r_5) = 0.005，也就是说，​r_1与​r_5可以通过主题顶点XML在两步内以0.005的概率到达。另一方面，如果没有基于主题的属性边，则原始图​G上的随机游走距离对于任意​l，​R^l(r_1,r_5)=0，因为​r_1和​r_5在原始图中不可达。

2.3 统一距离的分析

3. 聚类算法

我们的聚类架构是基于统一的属性增强图​G_\alpha上的邻域随机游走模型，根据结构和属性相似性对属性图​G进行划分。在本节中，我们将通过回答以下问题来解决聚类过程中的挑战。基于对这些问题的回答，我们提出了一种基于属性图的自适应聚类算法。

1. 给定统一的随机游走距离来衡量顶点之间的相似性，我们应该使用哪种聚类方法？
2. 我们给结构边分配一个权重​\omega_0，给属性​\alpha_i上的属性边分配一个权重​\omega_i。不同类型的边在计算统一随机游走距离时可能具有不同的贡献度，因此我们可以假设​\omega_0 = \omega_1=\cdots = \omega_m。问题是，我们能否在聚类过程中自适应地学习权重以及如何学习？
3. 聚类的目标函数应该是什么？由于随机游走距离会随着权重地更新而受到影响，那么当我们迭代调整权重​\omega_1,\dots,\omega_m时，目标函数是否会收敛？

许多现有的图聚类划分方法仅关注拓扑结构或顶点属性。它们中的许多方法无法直接应用于聚类属性增强图，因为它们通常在同构图上工作，即具有相同类型的节点和相同类型边的图。在异构的属性增强图中，它们缺乏一种机制来区分和学习结构边和属性边的不同贡献。因此，它们缺乏一种机制来平衡结构和属性相似性。

在我们的属性图聚类问题中，统一邻域随机游走考虑了通过结构边和属性边的所有可能路径。由于属性边，两个顶点之间的属性相似性会使它们在属性增强图中更接近，从而导致随机游走距离增加。根据统一随机游走模型，如果随机游走距离很大，则两个顶点被分配到同一个簇类；而如果随机游走距离很小或为0，即它们之间几乎没有或没有邻域随机游走路径，则两个顶点属于不同的簇。

以随机游走距离作为成对相似度度量，我们可以在聚类过程中忽略原始图拓扑结构。我们的聚类框架遵循​K-Medoids聚类方法；我们选择一个簇中最中心的位置点作为质心，并将其余点分配给它们最接近的质心。在每次迭代中，边缘权重​\omega_1,\dots,\omega_m被调整以反映属性的聚类趋势。此过程重复进行，直至收敛。我们将分别讨论聚类过程中的每一步。

3.1 聚类质心初始化

对于诸如​K-means和​K-Medoids等划分式聚类算法的成功而言，良好的初始质心至关重要。我们没有随机选择初始质心，而是遵循从密度点角度识别良好初始质心的动机。如果一个顶点​v_i的​l步邻域是密集的，这意味着在​l步内可以从​v_i到达许多顶点。那么​v_i有很高的概率处于一个密集的簇类中。另一方面，如果一个顶点​v_i的​l步邻域是稀疏的，那么​v_i可能不是作为簇质心的一个好的候选者。首先我们定义影响函数。

定义四：影响函数

令​\sigma为用户指定的参数。一个顶点​v_i对另一个顶点​v_j的影响函数定义为：

影响函数​f_B^{v_j}(v_i)\in [0,1]衡量一个顶点对另一个顶点的影响程度。其原理为，​v_i对​v_j的影响程度与从​v_i到​v_j的随机游走距离成正比。从​v_i到​v_j的随机游走距离越大，则说明​v_i对​v_j的影响就越大。

定义五：密度函数

在图中，一个顶点​v_i的密度函数是​v_i对所有顶点的影响函数的总和：

如果一个顶点​v_i具有较大的密度值，则说明​v_i要么通过多条随机游走路径连接到很多顶点，要么​v_i与很多顶点共享属性值。

根据密度函数，我们将所有顶点按其密度值降序排列。然后从排序列表中选择前​k个顶点作为初始质心​\{c_1^0,c_2^0,\dots,c_k^0\}。

3.2 聚类过程

在第​t次迭代中的​k个质心​\{c_1^t,\dots,c_k^t\}，我们将图中每个顶点​v_i\in V分配给其最近的质心​c^*\in \{c_1^t,\dots,c_k^t\}，即与​v_i具有最大随机游走距离的质心​c^*：

当所有顶点都分配给某个簇时，质心将更新为每个簇中最中心位置的顶点。要找到这样的顶点，我们首先根据随机游走距离计算簇​V_i的平均点​v_i，即：

因此​R^l_A(\bar{v_i})是簇​V_i的平均随机游走距离向量，然后我们在簇​V_i中找到新的质心​c_i^{t+1}，如下所示：

因此，我们在​t+1次迭代中找到新的质心​c_i^{t+1}，其随机游走距离向量最接近聚类平均值。聚类过程迭代到目标函数收敛。

3.3 聚类目标函数

聚类的目标是最大化类内相似度，最小化类间相似度。我们根据这个总体目标设计我们的聚类目标函数。由于我们的距离度量是统一随机游走距离，我们将最大化类内随机游走距离。

定义六：顶点集距离

设​V_1和​V_2是两个顶点集。​V_1和​V_2之间的顶点集距离​d(V_1,V_2)定义为：

其中​d(v_i,v_j)=R^l_A(v_i,v_j)是​v_i和​v_j之间的统一邻域随机游走距离。此公式旨在定量测量图中两个顶点集之间的相似性程度。当​V_1和​V_2中的顶点距离较远或孤立时，顶点集距离度量将非常小。

定义七：图聚类目标函数

给定一个属性图​G(V,E,\Lambda)，属性边权重​W=\{\omega_1,\dots,\omega_m\}，随机游走长度限制​l，以及聚类数​k，图聚类的目标是找到图的​k个划分​\{V_i\}^k_{i=1}，其中​V_i对应于第​i个簇类，​V_i\cap V_j = \phi且​\cup_{i=1}^k V_i=V并使其最大化如下目标函数：

其中​\sum_{i=1}^{m}\omega_i=m并且​\omega_i\ge 0,i=1,\dots,m。

聚类问题可以简化为三个子问题：1. 聚类分配，2.簇类中心更新，3. 权重调整，目标是最大化目标函数。前两个问题已在上述过程讨论。第三个问题一将在后续进行说明。

定理：给定图​G的任意划分​\{V_i\}^k_{i=1}，存在唯一解​W^* = \{\omega_1^*,\dots,\omega^8_m\}其中​\sum_{i=1}^{m}\omega^*_i = m,\omega_i^*\ge 0,i=1,\dots,m使得目标函数最大化。

证明：略

3.4 权重自适应

定义七种通过最大化目标函数有约束的图聚类问题是一个线性规划问题。提出了一种自适应权重调整方法来迭代改进目标函数。我们设定​\omega_0=1.0，这是结构边的权重，并基于其迭代调整属性权重​\omega_1,\dots,\omega_m。令​W^t = \{\omega_1^t,\dots,\omega_m^t\}作为​t次迭代过程中的属性权重。我们初始化​\omega_1^0 = \omega_2^0=\cdots=\omega_m^0 = 1.0，使用增量权重​\triangle\omega_i^t对​\omega_i^t进行调整。他表示属性​\alpha_i在第​t次迭代与​t+1次迭代之间的权重更新。属性​\alpha_i在​t+1次迭代中的权重计算：

为了准确判断权重增量​\triangle\omega_i的大小，我们设计了一个多数投票的机制：如果一个簇内的大部分顶点在某个属性​\alpha_i上取值相同，则说明​\alpha_i具有较好的聚类倾向。然后​\alpha_i的权重​\omega_i增加；另一方面，如果集群内的顶点在某个属性​\alpha_i值的分布非常随机，那么​\alpha_i不是一个好的聚类属性，权重​\omega_i应该降低。我们定义了一个投票度量，用于确定两个顶点是否共享一个属性值。

然后通过计算与​\alpha_i上的质心共享属性值得簇内顶点数目来估计​\triangle\omega_i^t。共享属性值的顶点数目越多，​\triangle\omega_i^t越大。

其中分母确保在权重调整之后​\sum_{i=1}^{m}\omega_i^{t+1}=m仍然成立。而后，调整后的权重计算公式为：

调整后的权重可能会根据​\triangle\omega_i^t的数值增加，减小或保持不变。如果​\triangle\omega_i^t>\omega_i^t那么​\omega_i^{t+1}>\omega_i^t，也就是说，属性​i对随机游走距离做出了越来越大的贡献，类似的，如果​\triangle\omega_i^t<\omega_i^t，​\omega_i^{t+1}<\omega_i^t。

权重自调整的一个重要性质是，权重会向增加聚类目标函数数值的方向调整。这里我们简要说明一下这个性质：如果集群内的许多顶点在​\alpha_i上共享一个属性值，那么权重就会增加，即​\omega_i^{t+1}>\omega_i^t，另一方面，如果集群内的顶点在​\alpha_i上的属性值差异很大，那么权重就会减小。这个过程中一定会有一些权重随着更新而减小，还有一些权重会随着更新而增加。​\sum_{i=1}^{m}\omega_i^{t+1}=m是一个常数。由于一些增加的​\omega_i^{t+1}，在​\alpha_i上共享相同属性值的顶点之间的随机游走距离进一步增加。因此，这些顶点倾向于聚集到同一个簇中，从而增加了目标函数，即簇内随机游走距离的总和。这类似于“富者愈富，穷者愈穷”的原则，因为具有很好聚类倾向的属性将获得更大的权重，从而对随机游走距离产生更大的影响，而具有非常随机值的属性将具有较小的权重。得出结论，权重自调整策略使目标函数区域收敛。

3.5 聚类算法

输入：属性图​G，最大长度为​l的随机游走路径，​c重新开始概率，影响函数参数​\sigma，簇类数量​k。

输出：​k个簇类​V_1,\dots,V_k

step1：初始化属性边权重​\omega_1 = \dots = \omega_m = 1.0，设定结构边权重​\omega_0 = 1.0

step2：计算统一随机游走距离矩阵​R^l_A

step3：选择​k个具有高密度的初始质心

step4：重复以下步骤直到目标函数收敛：

1. 将每个顶点​v_i分配到一个簇​C^*，其中质心​c^*是通过​\arg\max_{c_j}{d(v_i,c_j)}确定。

2. 更新簇类质心到每个簇中最中心的点：

   R^l_A(v_i,v_j) = \frac{1}{|V|}\cdot\sum_{v_k\in V_i}{R^l_A(v_k,v_j)},\forall v_j\in V
   c_i^{t+1} = \arg\max_{v_j\in V_i}{\parallel R^l_A(v_j)-R^l_{A}(v_i)\parallel}

3. 更新属性边权重​\omega_1,\dots,\omega_m

   \omega_i^{t+1} = \frac{1}{2}(\omega_i^t+\triangle\omega_i^t) = \frac{1}{2}(\omega_i^t+\frac{\sum_{j=1}^{k}{\sum_{v\in V_j}vote_i(c_j,v)}}{\frac{1}{m}\sum_{p=1}^{m}{\sum_{j=1}^{k}{\sum_{v\in V_j}vote_p(c_j,v)}}})

4. 重新计算​R^l_A

step5：返回​k个簇类​V_1,\dots,V_k