墨滴
德

德华

V1

2023/02/15阅读：10主题：兰青

复杂网络4-高级操作

高级操作

  • 图嵌入（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：

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

SkipGram
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. 枢纽型

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