【复杂网络】高级操作

文章导航

× 文章目录

1. 1. 图嵌入
   1. 1.1. 概述
      1. 1.1.1. 算法
   2. 1.2. 比较框架
      1. 1.2.1. 概述
      2. 1.2.2. 几何Chung-Lu(GCL) 模型
      3. 1.2.3. 解GCL模型
      4. 1.2.4. 分歧分数算法
   3. 1.3. 示例
2. 2. 关系数据上的半监督学习
   1. 2.1. 简介（转导学习）
      1. 2.1.1. 应用-示例
   2. 2.2. 无向图
   3. 2.3. 其他图
      1. 2.3.1. 有向图
      2. 2.3.2. 枢纽/权威型网络
      3. 2.3.3. 混合图
   4. 2.4. 超图
      1. 2.4.1. 模型
      2. 2.4.2. 分类数据（应用）
3. 3. 超图模块度和聚类
   1. 3.1. 普通图聚类（回顾）
   2. 3.2. 超图模块度
      1. 3.2.1. 超图表示
      2. 3.2.2. 超图Chung-Lu模型
      3. 3.2.3. 超图模块度
   3. 3.3. 超图聚类
      1. 3.3.1. 概述
      2. 3.3.2. 示例
      3. 3.3.3. 证明
      4. 3.3.4. 算法
      5. 3.3.5. 实验

菲尔兹数学科学研究所 复杂网络2019夏令营课程 学习笔记

高级操作

• 图嵌入（Graph Embedding）
• 图半监督学习（SSL）
• 超图

图嵌入

Graph Embedding，也叫图表示学习(Network Representation Learning)

1. 图嵌入的快速概述
2. 一些算法：node2vec、LINE、Verse
3. 比较嵌入算法的框架
4. 示例

概述

目标：

• 将网络（节点）映射到向量（特征）空间

• 将相似节点映射到向量空间中的附近位置。“相似”可能有不同含义：
  • 图拓扑上较近
  • 图中相似的角色（例如：度相似）
  • 相似的节点属性

应用实例：

1. 特征学习（不是特征工程）
2. 可视化
3. 链接预测
4. 社区检测
5. 异常检测
6. 网络演化（动力学）

形式化描述：

• 输入：G = (V , E)
• 输出：特征向量

算法

——大部分算法基于随机游走和 用于词嵌入的 SkipGram 方法

• 词的语义由其上下文决定(A word can be characterized by the company it keeps)
• 相似上下文中的词（相近的词）具有相似的含义
• 考虑每个单词周围的窗口；构建“词向量”（例如：word2vec）
• 使用这些作为训练数据

SkipGram：

使用滑动窗口邻域对每个词上下文的相关词进行组合，构建“词向量”

DeepWalk（深度游走）：

• 单词——对应于节点
• 句子——对应于图 G 上的随机游走
• 句子中的词频呈现幂律分布——游走中的顶点也呈现幂律分布

node2vec：

• 定义了有偏随机游走（biased random walks）混合了广度和深度优先搜索
• 关键参数：
  • p：控制重新访问同一节点的概率（留在附近）
  • q：控制探索更远的概率

概率选择

• 参数允许在以下之间进行权衡：
  • 低 p：在本地探索；这将侧重于图形拓扑结构中的社区结构（同质性）；
  • 低q：探索更远；这允许捕获节点之间的一些结构相似性（例如：集线器hubs，网桥bridges）；

其他算法：

统计表见课件

在我们的测试中使用了：

1. node2vec：q=1，p各不相同
2. VERSE：来自相似性度量（具有个性化page rank）的多功能图嵌入算法：使用默认参数
3. LINE：Large-scale Information Network Embedding（大规模信息网络嵌入），它使用邻接矩阵的近似分解来尝试保留一阶和二阶邻近度

比较框架

• 我应该使用哪种嵌入算法？
• 如何选择参数？
• 我怎么知道这种嵌入算法对图的表示就好？
• GIGO：向量空间中的错误表示会导致错误的结果......

算法之间的结果可能会有很大差异，并且随着参数的选择也会有很大不同

核心：使用嵌入后的向量构建同分布随机图，比较随机图和原图的JS散度，若很小，说明相近，进而说明嵌入效果良好

概述

框架模型：

给定具有度分布 的 n 个顶点上图 G = (V , E) 及其顶点到 k 维空间的嵌入，。

• 我们的目标是为这个嵌入分配一个“分歧分数”(divergence score)。
• 分数越低，嵌入越好。这将使我们能够在不同的维度上比较多个嵌入的结果

总述：

• 非随机图表现出类似社区的结构，所以我们一般：
  1. 将节点分组为集群
  2. 测量簇之间和簇内的边缘密度
  3. 通过 计算散度分数 将其与嵌入（矢量）空间中空间模型的预测密度进行比较
  4. 选择得分最高的嵌入
• 我们的框架中有两个主要部分：
  1. 图拓扑视图：一个好的、稳定的图聚类算法；我们默认使用 ECG，但我们也尝试使用 Louvain 和 InfoMap
  2. 空间视图：我们引入了基于度分布 w 和嵌入 ε 的几何 Chung-Lu (GCL) 模型。

几何Chung-Lu(GCL) 模型

Chung-Lu 模型：（引子）

• 在原始的 Chung-Lu 模型中，每个集合 被独立采样为边，概率为：

• 它产生的分布保留了每个顶点的预期度数

几何Chung-Lu(GCL) 模型：

• 考虑预期的度分布：

• 以及节点 的嵌入，以便我们知道所有距离：

• 模型应该满足 ，g为递减函数，因此长边的出现频率应该低于短边

• 我们使用以下归一化函数 其中 是一个定值： ——我们使用裁剪（clipping）来强制 和/或
  • 当 α = 0 时，此模型退化为原始的 Chung-Lu 模型，忽略了节点对的距离
  • 参数 α 越大，对长边的厌恶越大
  • 因此，模型的唯一参数是 α ∈ [0, ∞)
  • 在实践中，我们会尝试一系列值并保持最佳拟合。

• GCL模型是基于顶点集 上的随机图 其中 vi, vj, 形成一条边的概率为：

  • 权重选择：

• 顶点vi的度期望为：

定理：当 G 中的最大度数小于所有其他顶点的度数之和时，仅有唯一的权重选择。

——由于 G 的每个连通分量都可以独立嵌入，我们可以假设 G 是连通的，因此 G 的最小度数至少为 1。因此，除非 G 是 n 个顶点上的星形，否则这个非常温和的条件是平凡的。

我们要做的，就是通过选择权重，使得度分布期望等于原图度分布。

解GCL模型

我们使用一个简单的数值近似程序

1. 从任意向量开始

2. 给定 ，如果我们以如下概率在 vi 和 vj 之间引入一条边：

3. 那么 vi 的度期望将是：（这对应于上小节度期望）

4. 通过用 替换 来调整权重，使 与 匹配
   • 这也会影响 的其他值，并且 其他部分的变化也会影响 自身。
   • 因此，我们让每个顶点向正确的方向迈出一小步
   • 这个过程很快收敛到理想状态：对于所有 i， 都非常接近 。

5. 迭代步骤：

   • 对于每个 i，1 ≤ i ≤ n，我们定义

   • 重复调整过程直到

   • 定义 ε = 0.1 、 δ = 0.001

分歧分数算法

计算嵌入分歧分数（embedding divergence score）的算法

给定 G = (V, E)，它在 V 上的度分布 w，以及它的顶点的嵌入，我们将执行接下来详述的五个步骤

• 通过算法，我们获得 ，嵌入的分歧分数
• 我们可以应用这个算法来比较几个嵌入算法的分歧分数指标，选出最好的（最小的）那个

第一步：

在 G 上运行一些稳定的图聚类算法以获得顶点集 V 的分区 ，一共产生 个社区 。

此教程中使用ECG，其实任何稳定的算法都可以。

第二步：

令：

• ：两个端点都在 中的边的比例
• ：一个端点在 中且另一个端点在 中的边的比例

定义： ——这些向量从 图 G 的角度表征分区 C，嵌入 不影响 和

---

——接下来我们在 α 的一系列值上重复步骤 3-4

第三步：

给定 ，使用的GCL 模型。

从这个模型，我们计算：

• ： 内边的比例期望
• ： 中一个端点和 中另一个端点的边的比例期望

定义： ——这些向量从 嵌入 的角度表征分区 C

第四步：

计算 和 之间的距离，以及 和 之间的距离

我们使用 Jensen-Shannon 散度 (JSD)： ——这是给定 α 的（分歧）分数。

第五步：

从重复的步骤 3-4，我们获得了一系列

选择

将分歧分数定义为： 总结：

• 为了比较同一个图 G 的多个嵌入，我们重复上面的步骤 3-5 并比较分歧分数（分数越低越好）。
• 步骤 1-2 只执行一次，因此我们对每个嵌入使用相同的图划分算法到 个社区

示例

• 空手道俱乐部：找到最适合嵌入的α值
• 足球比赛：使用分歧分数选择最合适的嵌入算法
• LFR 数据集：使用此方法选出的最好和最坏embedding算法效果

关系数据上的半监督学习

简介（转导学习）

我们使用一种转导学习（transductive learning）的方法:

• 没有显式地构造任何模型
• 学习是“基于数据”的
• 在图上使用正则化框架，正则化包含以下两种情况：
  1. 局部结构：与稀缺标记顶点一致
  2. 全局结构：所有顶点的平滑

形式化描述：

设，

设函数 ，同时定义两个函数的内积：

• 我们定义一个函数 满足：

  • 是一个依赖于G的泛函：平滑泛函

    ——取决于图的类型：无向、有向、联合链接(两者都有)

  • 编码先验知识(顶点标签)

    ——取决于要解决的问题：

    1. 二进制分类：
    2. 排序：
    3. 无监督：

  • :平滑度(smoothness)和一致性(consistency)之间的权衡

应用-示例

• 给出一个包含一些“有趣”实体的大型图
• 求解以放大附近的顶点

最终可以：

1. 获得未知实体的排名
2. 能可视化关键子图
3. 网络安全环境中的几个应用
   • 异常检测
   • 恶意软件检测
4. 图和超图通常太大，不适合直接分析或可视化

无向图

图模型：

• 设无向图为 是所有 的边权 的矩阵。
• 设D为节点度的对角线矩阵：

无监督N-cut问题：（回顾）

• 对于一个分割 其中： 这可以被视为具有转移概率 的随机游走：

• 这个问题可以通过松弛实值来解决 其中 且： 是(归一化)图拉普拉斯矩阵

——这被称为归一化谱聚类（normalized spectral clustering）

半监督问题：

概述：

• 拉普拉斯矩阵也出现在半监督问题中：

• 如果节点接近(很大)，那么它们应该有相似的标签()，以保持较小
• 在整个图上，这相当于保持较小

• 这可以看作是找到一个“平滑”函数f，它在图的密集区域中变化很小，但在稀疏区域中变化更大。

形式化描述：

• 现在假设顶点上有一些初始(种子)值y：

• 将半监督问题定义为关于图拓扑的“平滑性”和关于y的一致性之间的权衡，例如: 令 , 则有： 若 , 且 ,存在一个封闭式解： 其中:

  , 归一化图拉普拉斯矩阵

  , 平滑矩阵

求解：

可通过多种方式获得：

1. 迭代方法:

   • 从开始，

   • 迭代

2. 它可以写成一个 对角占优 的线性问题，其反演技术存在，且复杂度为，其中m为非零项的个数
3. 通过共轭梯度法

4. map-reduce框架具有良好的可伸缩性

其他图

有向图

形式化描述：

• 定义进出节点度： .

• 上的然随机游走的转换概率为：

• 设 为唯一平稳分布，即： 这需要定义一个传送随机游走（teleporting random walk）——用于描述随机游走的概率

• 考虑泛函：

• 正则化问题和之前一样 其中 是转移概率的矩阵， 平稳概率的对角矩阵。（和无向图的差别在平滑矩阵S上）

• 和之前一样: .

——这是对无向情况的推广。对于无向图，随机游走的概率是固定的： ——此时平滑矩阵退化为无向图情况：

枢纽/权威型网络

Hubs&Authorities graphs

概述：

考虑顶点的两种可能角色:

• 具有高“入度”的权威(authority)
• 具有高“出度”的枢纽(hub)

对于有向图， u是“枢纽”，v是“权威”

平滑矩阵：

1. 权威型：

   定义节点 和 相对于节点 的权威距离为： 由此我们建立了平滑矩阵：

2. 枢纽型

   我们同样定义相对于节点 的枢纽距离为： 平滑矩阵：

求解模型：

令 ，其中 , 我们可以得到： 对于枢纽型我们可以类似地得到 . 令： 我们可以像以前一样解决正则化问题：（带入平滑矩阵求解即可） 对于一个无向图： .

混合图

我们可以将平滑泛函推广为 其中 基于随机游走， 是“枢纽&权威”平滑

这允许3种衡量顶点“接近”的方式：

1. 存在一条短路径
2. 指向几个公共顶点
3. 由几个公共顶点指向

——2和3对于无向图是一样的

超图

模型

符号说明：

对于(无向)超图，定义:

• ：超边集合——超边为节点子集
• ：超边权值
• ：节点度