非参数关系模型下的社交网络挖掘

### 非参数关系模型下的社交网络挖掘 #### 1. 引言 随着新型社交网络数据的日益丰富，如引文网络（DBLP、Citeseer）、社交网站（Facebook）和社交媒体网站（Last.fm）等，社交网络挖掘变得愈发重要。社交网络通常包含大量的对象，并通过复杂的网络相互连接。一般来说，社交网络数据可以用社交图来表示，例如一个简单的社交网络中包含人物、人物简介（如性别），人物之间通过友谊关系相互连接。社交网络挖掘的一些有趣应用包括社区发现、关系预测和社交推荐等。 统计关系学习（SRL）是机器学习研究的一个新兴领域，它试图将富有表现力的知识表示形式与统计方法相结合，以在关系网络上进行概率推理和学习。对于每个潜在的边，会引入一个随机变量来描述边的状态。例如，人物 1 和人物 2 之间的边对应的随机变量，如果两人是朋友则为“是”，否则为“否”。对象（如人物 1）和对象属性（如男性）之间的边也与一个随机变量相关，其值描述了人物的简介。在这个示例中，所有变量都是二进制的。为了推断感兴趣的量，如人物 1 和人物 2 是否为朋友，我们需要学习随机变量之间的概率依赖关系。这里假设友谊取决于相关人物的简介（性别）。 在简单的社交网络关系模型中，友谊是由相关对象的简介局部预测的：一个人是否是另一个人的朋友仅取决于这两个人的简介。在参数固定且给定父属性的情况下，所有友谊相互独立，无法考虑友谊之间的相关性，即协同效应。为了解决这个限制，可以通过结构学习来获得非局部依赖关系，但在复杂的关系网络中进行结构学习是一个难题。也可以像文献[24]中提出的那样，为每个人引入一个隐藏变量来实现非局部依赖关系。隐藏变量的状态代表人物的未知属性，例如与某些人交朋友的特定习惯。一个人的隐藏变量是其简介的唯一父节点，也是该人可能参与的友谊关系的父节点之一。由于隐藏变量至关重要，这个模型被称为隐藏关系模型（HRM）。在关系领域中，不同类别的对象通常需要在隐藏表示中具有特定类别的复杂性。因此，使用狄利克雷过程（DP）混合模型这种非参数方法是合理的，在该模型中，每个对象类可以以自组织的方式优化其自身的表示复杂性。从概念上讲，HRM 模型中隐藏变量的状态数量变为无限。实际上，DP 混合采样过程只占用有限数量的组件。隐藏关系模型和 DP 混合模型的结合就是无限隐藏关系模型（IHRM）。 本文探索了使用 IHRM 对复杂社交网络进行建模和分析，用于社区检测、链接预测和产品推荐。我们提出了两种高效的推理方法：一种是带有截断破棍构造（TSB）的分块吉布斯采样，另一种是带有 TSB 的平均场近似。我们对三个社交网络数据集进行了实证分析：桑普森修道院数据、伯纳德和基尔沃思数据以及 MovieLens 数据。 #### 2. 模型描述 ##### 2.1 隐藏关系模型 一个简单社交图的隐藏关系模型（HRM）如图 2 所示。HRM 模型的基本创新之处在于为每个对象（这里是人物）引入一个隐藏变量，在图中用 Z 表示。可以将它们视为人物的未知属性。然后我们假设一个人的属性仅取决于该人的隐藏变量，而一种关系仅取决于参与该关系的人物的隐藏变量。这意味着如果隐藏变量已知，那么人物属性和关系都可以得到很好的预测。 给定图 2 所示的 HRM 模型，信息可以通过相互连接的隐藏变量传播。例如，要预测人物 2 是否会成为人物 3 的朋友，即预测关系 R2,3。这个概率是基于以下证据计算的： 1. 直接相关人物的属性，即 G2 和 G3； 2. 与感兴趣人物相关的已知关系，即关于人物 2 的友谊 R2,1 和 R2,4，以及关于人物 3 的友谊 R1,3 和 R3,4； 3. 通过隐藏变量传递的高阶信息，例如通过 Z1 和 Z4 传播的关于 G1 和 G4 的信息。 如果人物的属性信息丰富，那么这些属性将决定人物的隐藏状态，从而主导关系 R2,3 预测概率的计算。相反，如果人物的属性信息较弱，那么一个人的隐藏状态可能由他与其他人的关系以及这些人的隐藏状态决定。通过引入隐藏变量，信息可以在由关系结构定义的基础网络中全局分布。这减少了对广泛结构学习的需求，而在关系模型中，由于潜在父节点的数量巨大，结构学习尤其困难。 此外，HRM 提供了对关系数据的聚类分析。一个对象的隐藏变量的状态对应于其聚类分配。这可以看作是共聚类模型的推广。HRM 可以应用于具有多个对象类和多个关系类的领域。此外，关系可以是任意阶的，即 HRM 不限于仅处理二元和一元关系。 现在我们通过引入图 2 中的变量和参数来完善这个模型。每个人都有一个隐藏变量 Zi。Zi 的状态指定了人物 i 的聚类。设 K 表示聚类的数量。Z 遵循参数向量为 π = (π1, ..., πK)（πk > 0，∑k πk = 1）的多项分布，它指定了一个人属于某个聚类的概率，即 P(Zi = k) = πk。π 有时被称为混合权重，它是从具有超参数 α0 的共轭狄利克雷先验中抽取的。 所有人物属性都被假设为离散的多项变量（或者对于二进制情况为伯努利变量）。因此，一个特定的人物属性 Gi 是从具有参数 θk 的多项（或伯努利）分布中抽取的样本，其中 k 表示人物的聚类分配。θk 有时被称为混合组件，它与聚类 k 相关联。对于所有人物，总共有 K 个混合组件 Θ = (θ1, ..., θK)。聚类 k 中的每个人都继承了混合组件，因此我们有：P(Gi = s|Zi = k, Θ) = θk,s（θk,s > 0，∑s θk,s = 1）。这些混合组件是独立地从先验 G0 中抽取的。为了计算效率，我们假设 G0 是具有超参数 β 的共轭狄利克雷先验。 现在考虑关于关系（FriendOf）的变量和参数。关系 R 被假设为具有两个状态的离散变量。两个人（i 和 j）之间的特定关系 Ri,j 是从具有参数 φk,ℓ 的二项分布中抽取的样本，其中 k 和 ℓ 分别表示人物 i 和人物 j 的聚类分配。总共有 K × K 个参数 φk,ℓ，每个 φk,ℓ 都是独立地从先验 Gr0 中抽取的。为了计算效率，我们假设 Gr0 是具有超参数 βr 的共轭贝塔分布。 从混合模型的角度来看，HRM 模型中最有趣的项是 φk,ℓ，它可以被解释为相关混合组件。如果人物 i 被分配到聚类 k，即 Zi = k，那么这个人不仅继承了 θk，还继承了 φk,ℓ，ℓ = {1, ..., K}。 ##### 2.2 无限隐藏关系模型 由于隐藏变量在 HRM 模型中起着关键作用，我们期望 HRM 模型可能需要隐藏变量具有灵活的状态数量。再次考虑社交图的例子。在关于过去友谊的信息很少的情况下，所有人可能看起来都一样；随着可用信息的增加，可能会发现人物中的某些聚