本站服务

图像识别
图表示学习笔记
系统学习 机器学习 0 521
  • 主要目标: 将结点映射为向量表示的时候尽可能多地保留图的拓扑信息【低维、连续、稠密】
  • 主要分类:
    • 基于图结构的表示学习
    • 基于图特征的表示学习

基于图结构的表示学习

在我们的图表示学习中，我们希望Embedding出来的向量在图上"接近"时在向量空间也"接近"。对于第2个"接近"，就是欧式空间两个向量的距离；对于第一个"接近"，有多种解释:

  • 1-hop: 两个相邻的结点就可以定义为临近
  • k-hop: 两个k阶临近的结点也可以定义为临近
  • 具有结构性:
    • 结构性相对于异质性而言，异质性关注的是结点的邻接关系；
    • 结构性将两个结构上相似的结点定义为“临近”；
    • 比方说，某两个点是各自小组的中心，这样的两个节点就具有结构性

前置知识

Word2Vec

Word2Vec是一种广泛使用的自然语言处理技术，用于将单词表示为高维向量。

  1. 一般步骤：

    1. 准备数据集：首先需要准备一个包含足够文本的数据集，例如文章、书籍、网页或其他文本数据源。
    2. 预处理数据：数据集需要进行一些预处理，例如去除标点符号、停用词、数字等，并将所有单词转换为小写形式。
    3. 训练Word2Vec模型：使用预处理的数据训练Word2Vec模型。Word2Vec有两种模型：连续词袋模型【用AC来预测B】(Continuous Bag of Words[CBOW])和Skip-gram【用B来预测AC】模型，它们分别用于从上下文中预测目标单词和从目标单词预测上下文单词。选择哪个模型取决于特定任务和数据集。
    4. 获取单词向量：训练完成后，Word2Vec模型将返回每个单词的向量表示。可以使用这些向量来计算单词之间的相似度、执行聚类、分类、情感分析等任务。
    5. Fine-tune：如果您需要将Word2Vec应用于特定领域的任务（如医学或法律），则可以对Word2Vec进行微调，以使其更适合您的领域。
    6. 应用：使用Word2Vec生成的单词向量可以应用于各种自然语言处理任务，如文本分类、实体识别、机器翻译等。

  2. Word2Vec加速训练的方法:

    1. Negative Sampling

DeepWalk

  • 介绍: DeepWalk是一种基于图嵌入的算法，通过随机游走和skip-gram模型将图形中的节点表示为低维向量。这种算法是一种无监督学习方法，能够从节点之间的连接信息中捕捉节点之间的相似性。它可以用于处理各种节点相关任务，例如节点分类、节点聚类、相似节点检索等。
  • 步骤:
    • DeepWalk算法首先采用随机游走方法在图形上生成大量的节点序列:【同一个起始节点可能会生成不同的节点序列，这样可以增加节点之间的可达性，使得生成的节点序列更加全面】
      1. 选择一个起始节点。这可以是图中的任意节点，也可以是所有节点的随机采样;
      2. 按照一定的概率，从当前节点转移到它的一个邻居节点。这里的概率可以是均匀分布或基于节点之间的边权重分布;
      3. 重复步骤2，直到达到指定的序列长度或无法再继续扩展;
      4. 从上述序列中提取出所有的节点序列，这些节点序列可以用于后续的模型训练;
    • 然后，它使用skip-gram模型将节点序列转换为低维向量表示:
      • Skip-gram模型是一种神经语言模型，它的目标是学习出在给定上下文中出现概率最大的词语;
      • 在DeepWalk中，节点序列就是上下文，而节点本身就是词语。因此，使用skip-gram模型可以将节点序列转换为低维向量表示，这些向量可以用于节点分类、节点聚类、相似节点检索等任务;
  • 评价:
    • 正面:
      • 首个将深度学习和自然语言处理的思想用于图机器学习
      • 在稀疏标注节点分类场景下，嵌入性能卓越
    • 负面:
      • 均匀随机游走，没有偏向的游走方向，不科学(不如Node2Vec)
      • 需要大量随机游走序列训练
      • 基于随机游走，管中窥豹。距离较远的两个节点无法相互影响，看不到全图信息(不如GNN)
      • 无监督，仅编码图的连接信息，没有利用节点的属性特征
      • 没有真正用到神经网络和深度学习
  • 改进: 在随机游走实现过程中，可以使用DFS、BFS或Metropolis-Hastings(MH)算法等方法来实现随机游走。不同的方法可能会对生成的节点序列产生不同的影响。例如，DFS会更倾向于探索与起始节点相似的节点，而BFS则更倾向于探索与起始节点距离相近的节点。选择何种算法需要根据具体的应用场景和图的特征来决定。

Node2vec

Node2vec是一种用于学习图嵌入的算法，它能够将图中的节点表示为低维向量，以便进行机器学习任务。Node2vec基于随机游走思想，通过在图中执行随机游走来生成节点序列，并使用这些节点序列来学习节点的嵌入向量。

Node2vec与传统的随机游走算法相比，采用了一种更灵活的随机游走策略。该策略使用两个参数p和q来控制游走的行为。其中p控制是否向上一步的节点返回，q控制是否向远离上一步的节点移动，这使得 Node2vec 能够更好地保留图中的局部结构信息和全局结构信息。

具体而言，Node2vec的算法步骤如下:

  1. 对于每个节点 v，生成 t 次长度为 l 的随机游走序列；
  2. 根据节点序列，计算节点间的相似度（使用节点分类概率）；
  3. 使用相似度矩阵学习节点的嵌入向量。

Node2vec 通过引入节点分类概率来计算节点相似度，该概率考虑了节点在不同随机游走中出现的频率，从而更好地反映了节点之间的相似性。此外，Node2vec 采用了高效的优化算法，使得它可以处理大规模的图数据，并生成不同粒度的嵌入向量，以适应不同的机器学习任务。

虽然Node2vec 和 DeepWalk 都基于随机游走，但是Node2vec相比DeepWalk以下一些进步的地方：

  1. 更灵活的随机游走策略：DeepWalk使用的是固定的随机游走策略，即在图中随机游走，并根据出现的节点序列生成节点嵌入向量。Node2vec则提出了一种更灵活的随机游走策略，它可以根据节点类型的不同，调整随机游走的方向和长度，从而提高模型的表现力。

  2. 更好的节点相似性度量：DeepWalk 使用的是余弦相似度来度量节点之间的相似性，而 Node2vec 引入了一个称为“节点分类概率”的度量方法，它考虑了节点在不同随机游走中出现的频率，从而更好地反映了节点之间的相似性。

  3. 更强的可扩展性：Node2vec 使用了高效的优化算法，使得它可以处理更大规模的图数据。同时，Node2vec 可以生成不同粒度的嵌入向量，使得它可以适应不同的机器学习任务。

综上所述，Node2vec 相比 DeepWalk 在随机游走策略、节点相似性度量和可扩展性等方面有所改进，从而更适合处理大规模复杂的图数据。

案例分析

  1. 图a展示了原始的用户行为序列
  2. 图b基于这些用户行为序列构建了物品相关图，可以看出，物品A，B之间的边产生的原因就是因为用户U1先后购买了物品A和物品B，所以产生了一条由A到B的有向边。如果后续产生了多条相同的有向边，则有向边的权重被加强。在将所有用户行为序列都转换成物品相关图中的边之后，全局的物品相关图就建立起来了。
  3. 图c采用随机游走的方式随机选择起始点，重新产生物品序列。
  4. 图d最终将这些物品序列输入word2vec模型，生成最终的物品Embedding向量。

基于图特征的表示学习

在基于图特征的表示学习中，由于加入了结点的特征矩阵 (姓名、年龄、身高等这样的特征)，需要同基于图结构的表示学习区别开来。这一类的模型通常被叫做“图神经网络”。本质上，这些网络都属于MPNN(消息传递神经网络)

\[ \begin{aligned} \mathbf{h}_ v^0 & =\mathbf{x}_ v \\ \mathbf{h}_ v^k & =\sigma\left(\mathbf{W}_ k \sum_{u \in N(v)} \frac{\mathbf{h}_u^{k-1}}{|N(v)|}+\mathbf{B}_k \mathbf{h}_v^{k-1}\right), \forall k \in\{1, \ldots, K\} \\ \mathbf{z}_v & =\mathbf{h}_v^K \end{aligned} \]

为何不直接采用邻接矩阵拼接特征矩阵做输入训练MLP

  1. 对于很接近的图，哪怕只是节点增加了一个，也无法共用模型
  2. Isomorphism(同构)问题: 修改图的节点摆放顺序，图不变，但邻接矩阵变，因此临界矩阵不可以作为输入
  3. 参数量过大: O(|V|)

GCN

通过一种类似卷积的方法来实现节点之间的消息传递，公式如下:

\[ H^{(l)}=\sigma\left(D^{-\frac{1}{2}}(A+I) D^{-\frac{1}{2}} H^{(l-1)} W^l\right) \]

其中 \(A\) 是邻接矩阵, \(D=\operatorname{diag}\left(d_1, d_2, \ldots, d_n\right)\) 是顶点的度矩阵(对角阵), \(I\) 是单位阵, \(W\) 是神经网络层与层之间传播的系数矩阵。此外 \(H\) 表示的是该层的结点特征矩阵, 第一层的特征矩 阵 \(H_0\) 是原始的结点特征矩阵\(X\)。

GraphSAGE

原理:

聚合机制对比:

步骤:

  1. 对于每个节点，将其本身的特征向量作为第一层的特征向量，即 \(h_{v}^{0} = x_v\)。
  2. 对于每一层 \(k \in [1, K]\)，对每个节点\(v\)，选取其k阶邻居节点集合\(N_k(v)\)，然后将这些邻居节点的特征向量进行聚合，得到聚合后的特征向量\(z_{k}^{v}\)。
  3. 将 \(h_{k-1}^{v}\) 和 \(z_{k}^{v}\) 拼接在一起，得到下一层的特征向量 \(h_{k}^{v}\)。
  4. 重复步骤2和3，直到得到第K层的特征向量 \(h_{K}^{v}\)。
  5. 最后，对于节点\(v\)，采用一个全连接层将其特征向量转换成预测结果。

在这个过程中，GraphSAGE采用了采样和聚合的技术来加速计算。具体来说，对于每一层\(k\)，GraphSAGE依次对每个节点\(v\)的邻居节点进行采样，并对采样后的邻居节点进行聚合，得到聚合后的特征向量\(z_{k}^{v}\)。这样做能够提高计算效率，同时也能够减少模型的过拟合现象。

常见采样方法:

  • 直接采样：从中心节点的邻居节点中等概率地随机采样一定数量的节点。这种方法简单快速，但存在采样偏差的问题，可能会漏掉一些重要的邻居节点。
  • 随机游走采样：从中心节点出发进行随机游走，按照一定的概率分布采样邻居节点。这种方法更加全面，能够更好地覆盖节点的邻居信息，但需要花费更多的计算资源。

常见聚合方法:

  • Mean Aggregator：将邻居节点的特征向量取平均值作为该节点的新特征向量。
  • Max Pooling Aggregator：将邻居节点的特征向量取最大值作为该节点的新特征向量。

GAT

跟GCN相比，引入了注意力机制。说到底，GAT还是对邻居节点的信息赋予权重。

  1. 回顾GCN的流程

  2. 引入注意力概念 其中的\(a\)函数就可以有各种各样的设计，比如通过一个可学习的权重向量

  3. \(a\)函数的选择

    1. 直接计算内积
    2. 通过MLP学习
    3. \(\alpha_{ij}\)的学习
    4. 总的计算流程:

公式表达如下:

\[ h_{v_i}^l=W^l \sigma\left(\sum_{v_ j \in \mathcal{N}\left(v_i\right)} \alpha_{i j}^l h^{l-1}_{v_j}\right) \]

其中 \(\alpha_{i j}\) 是结点 \(v_i\) 与其相邻结点 \(v_j\) 之间的权重系数, \(\alpha_{i j}\) 的计算公式为:

\[ \alpha_{ij} = \frac{\exp(\operatorname{LeakyReLU}(a^{T} (Wh_i \cdot Wh_ j)))} {\sum_ {v_k\in N(v_i)} \exp(\operatorname{LeakyReLU}(a^T (Wh_ i \cdot Wh_ k))) } \]

矩阵角度的理解:

TGNN

时态图神经网络(TGNN: Temporal Graph Neural Network)在GNN的基础上进行了优化，主要用于处理动态图数据。与静态图数据不同，动态图数据包含时间维度，即图数据在不同时间点上的演化过程。

TGNN采用了一种自适应的方式来更新节点的表示，即每个节点的表示是由其周围节点的表示自适应地加权求和得到的。这种方式下，TGNN能够更好地捕捉节点之间的关系信息，提升模型的性能。

因此，相比于GNN，TGNN在处理图数据方面表现更加出色，能够更好地捕捉节点之间的关系信息，从而提升模型的性能。

相关问题

图的下采样

  1. 原理: 类似剪枝操作
  2. 图示

GCNCov参数计算

GCNCov是一种基于图卷积神经网络（GCN）的图卷积层，其参数计算如下：

假设输入特征矩阵为\(X\in\mathbb{R}^{N\times F}\)，其中\(N\)是节点数量，\(F\)是输入特征的维度。输入特征经过一个线性变换和ReLU激活函数得到节点的特征表示\(H\in\mathbb{R}^{N\times C}\)，其中\(C\)是GCNCov层输出特征的维度。

GCNCov层的参数包括权重矩阵\(W\in\mathbb{R}^{F\times C}\)和偏置向量\(b\in\mathbb{R}^{C}\)，其中\(W\)是GCNCov层的可训练参数，\(b\)是可选的偏置项。同时，GCNCov层还包括一个度矩阵\(D\)，其定义为\(D_{ii}=\sum_{j=1}^NA_{ij}\)，其中\(A\)是输入图的邻接矩阵。在GCNCov层中，\(D\)用于对输入特征进行归一化。

GCNCov层的输出特征矩阵\(Z\in\mathbb{R}^{N\times C}\)的计算公式如下：

\[ H=\widetilde{D}^{-\frac{1}{2}} \widetilde{A} \widetilde{D}^{-\frac{1}{2}} X W+b \]

其中\(\widetilde{A}=A+I_N\)，\(I_N\)是\(N\times N\)的单位矩阵，\(\widetilde{D}\)是\(\widetilde{A}\)的度矩阵。因此，GCNCov层的参数总数为\(FC+2C\)。

如何处理数据量很大的单个图

当数据集中只有一个大图时，训练GCN的方法可能需要进行一些特殊的处理，以便可以更有效地处理大规模图数据。

以下是一些可用于训练GCN的大规模图的技巧：

  1. 采样子图：可以使用图采样技术从大规模图中抽取一个子图进行训练。在每个训练迭代中，可以随机选择一些节点和它们的邻居来形成一个子图。这种方法被称为随机游走采样，是一种有效的方法来训练GCN模型。

  2. 分块图处理：可以将大规模图分成多个块，每个块都可以被看作一个小图。然后，可以将每个小图单独训练一个GCN模型，并在块之间共享参数。这种方法可以通过分块图处理技术来实现，这是一种将大规模图分成多个小块的技术。

  3. 并行计算：可以使用并行计算来训练GCN模型。对于大规模图数据，可以将图分成多个子图，然后使用多个计算机或GPU同时训练每个子图。这种方法被称为图并行计算，是一种有效的方法来训练大规模图的GCN模型。

  4. 内存优化：可以使用一些内存优化技术来训练大规模图的GCN模型。例如，可以使用稀疏矩阵表示图数据，这可以显著减少内存占用。还可以使用PyTorch中的一些内置函数来执行内存优化，例如torch.sparse模块中的函数。

  5. 可以使用分层采样的方式，通过分层的方式逐渐地采样子图，从而处理大规模的图数据。这样可以逐层递进的处理大规模图，同时避免在一次采样中处理太多的节点。

请注意，这些方法都可以结合使用，以获得更好的效果。同时，这些方法也有一些限制和适用条件，需要根据实际情况选择合适的方法。

编写
预览