# 图拉普拉斯（Graph Laplacian）

# 图拉普拉斯的定义

图拉普拉斯矩阵是基于图的邻接矩阵和度矩阵定义的。给定一个无向图 $G=(V,E)$, 其中$V$ 是节点的集合，$E$ 是边的集合。图的邻接矩阵 A 是一个$|V|×|V|$ 的矩阵，其中$A_{ij}=1$ 表示节点$i$ 和节点$j$ 之间存在边，否则$A_{ij}=0$

度矩阵$D$ 是一个对角矩阵，其对角元素$D_{ii}$ 表示与节点$i$ 连接的边的数量，即节点的度数。

• 无向图：在无向图中，顶点的度是指与该顶点直接相连的边的数量。
• 有向图：在有向图中，顶点的度可以分为入度（In-degree）和出度（Out-degree）。入度是指有多少条边指向该顶点，出度是指从该顶点出发的边的数量。

图拉普拉斯矩阵$L$ 的定义为：

$$L=D-A$$

这是对称矩阵，$L_{ii}$ 表示与节点$i$ 相连的边的数量，$L_{ij}$ 表示节点$i$ 和节点$j$ 之间是否有边存在（取负值）

# 图拉普拉斯的归一化

在实际应用中，通常使用归一化的图拉普拉斯矩阵，这有助于提高模型的稳定性和收敛性。

# 对称归一化图拉普拉斯矩阵

$$L_{sym}=I-D^{-1/2}AD^{-1/2}$$

其中，$I$ 是单位矩阵，$D^{-\frac{1}{2}}$ 是度矩阵的逆平方根。

# 度的逆平方根

$$\begin{gathered}\text{假设我们有一个度矩阵 }D\text{,它是一个对角矩阵}:\\D=\begin{pmatrix}d_1&0&0&\cdots&0\\0&d_2&0&\cdots&0\\0&0&d_3&\cdots&0\\0&0&\vdots&\ddots&\vdots\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&d_n\end{pmatrix}\\\text{度矩阵 }D\text{ 的逆的平方根 }D^{-1/2}\text{ 也是一个对角矩阵,它的定义如下}:\\D^{-1/2}=\begin{pmatrix}\frac1{\sqrt{d_1}}&0&0&\cdots&0\\0&\frac1{\sqrt{d_2}}&0&\cdots&0\\0&0&\frac1{\sqrt{d_3}}&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&\frac1{\sqrt{d_n}}\end{pmatrix}\end{gathered}$$

# 随机游走归一化图拉普拉斯矩阵

$$L_{rw}=I-D^{-1}A$$

# 图拉普拉斯在 GNN 中的应用

图拉普拉斯矩阵在 GNN 中被广泛应用，特别是在图卷积神经网络（GCN）中。GCN 的核心操作是通过邻接矩阵（或其变体）来对节点的特征进行聚合，并传播信息。具体来说，GCN 层的更新规则通常被表达为：

$$H^{(l+1)}=\sigma(\tilde D^{-1/2}\tilde A\tilde D^{-1/2}H^{(l)}W^{(l)})$$

# 邻接矩阵$A$ 和自环矩阵$\tilde A$

邻接矩阵$A$: 这是一个$N×N$ 的矩阵，其中$N$ 是图中节点的数量。矩阵中的元素$A_{ij}$ 表示节点$i$ 和节点$j$ 之间是否存在边，如果$i$ 和$j$ 之间有边，$A_{ij}=1$

自环矩阵 $ \tilde A=A+I$：在邻接矩阵的基础上加入了单位矩阵，从而确保在图卷积操作中每个节点不仅仅聚合其邻居节点的信息，还包括自身的信息。

# 度矩阵$D$ 和归一化度矩阵$\tilde D$

** 度矩阵：** 对角矩阵，其对角线上元素$D_{ii}$ 表示图中节点$i$ 的度数（即与节点$i$ 直接相连的边的数量）

** 归一化度矩阵$\tilde D$：** 加入自环后的度矩阵进行归一化。常见方法为取度矩阵的逆平方根，即\tilde D^

# 节点特征矩阵H^

在第$l$ 层的节点特征，矩阵的每一行对应一个节点的特征向量，列表示该节点的特征维度，这个矩阵反应了图中每个节点在某一层的特征表示。在 GCN 中随着层数的增加，节点的特征表示会逐渐聚合来自其邻居的信息。

# 可学习权重矩阵W^

这是第 $ l$ 层的可学习权重矩阵，用于将输入的节点特征进行线性变换。通过训练，模型会优化这个权重矩阵，使得在每一层中，节点特征的变换能够更好地表征节点的类别或其他任务相关的属性。

# 激活函数$\sigma$

这是一个非线性函数，用于引入非线性变换，使得模型能够学习复杂的模式。常见的激活函数包括 ReLU（Rectified Linear Unit）、Sigmoid、Tanh 等。在 GCN 中，激活函数通常应用于每一层的输出特征上，以增强模型的表达能力。

# 图傅里叶变换（Graph Fourier Transform）

# 定义

将图拉普拉斯矩阵分解，假设$L$ 是无向图拉普拉斯矩阵，其可以被分解为：

$$L=U\Lambda U^T$$

$U$ 是图拉普拉斯矩阵的特征向量构成的矩阵，每一列是一个特征向量

$\Lambda$ 是对角矩阵，对角元素是对应的特征值

# 图傅里叶变换

图傅里叶变换通过图拉普拉斯矩阵的特征向量将图信号从节点域变换到频域。对于一个图信号 $f$（一个大小为$N$ 的向量，其中$N$ 是图的节点数），其图傅里叶变换$\tilde f$ 定义为：

$$\tilde f=U^Tf$$

这里的$U^T$ 是特征矩阵的转置，也称为图傅里叶基

# 图傅里叶逆变换

与经典傅里叶变换类似，图傅里叶变换也是可逆的。通过图傅里叶逆变换，可以将频域信号转换回节点域。图傅里叶逆变换定义为：

$$f=U \tilde f$$

这意味着通过将频域的信号 $\tilde f$ 与 与图拉普拉斯特征向量矩阵 $U$ 相乘，可以恢复原始的图信号。

# CGN

# 图拉普拉斯正则化用于损失函数

$$\mathcal{L}=\mathcal{L}_{0}+\lambda\mathcal{L}_{\mathrm{reg}} ,\quad\mathrm{with}\quad\mathcal{L}_{\mathrm{reg}}=\sum_{i i}A_{ij}\|f(X_{i})-f(X_{j})\|^{2}=f(X)^{\top}\Delta f(X) .$$

• $\mathcal L$: 这是总损失函数，我们在训练过程中希望最小化它
• $\mathcal L_0$: 表示图中带标签的节点相关的主要损失函数， 通常是与带标签数据相关的标准损失函数。在半监督学习的背景下，这通常指的是对已知标签数据的损失，比如交叉熵损失。如果问题是分类任务，通常衡量的是模型预测的类别分布与实际标签之间的差距。
• $\lambda$: 正则化参数
• $\mathcal L_{reg}$: 正则化项
• $A_{ij}$: 图的邻接矩阵的元素。
• $f(X_i)和f(X_j)$: 节点$i和j$ 的特征表示。目的是让连接在一起的节点具有相似的表示
• $||f(X_{i})-f(X_{j})\|^{2}$: 表示两个节点之间的距离
• 最后的 $f (X)^{\top}\Delta f (X) $ 使用拉普拉斯算子重新表示正则化项
• $\Delta=D-A$: 表示无向图的飞归一化拉普拉斯量
• $f(X)$: 是一个函数，表示节点 X 的特征或嵌入向量。在图神经网络中可以表示神经网络层提取的节点特征表示，也可以是通过图卷积操作获得。

# 半监督分类

# 定义

半监督分类是一种机器学习方法，旨在利用少量标注数据（带标签的数据）和大量未标注数据（不带标签的数据）来构建分类器。与传统的监督学习依赖大量标注数据不同，半监督学习在标注数据有限的情况下，通过结合未标注的数据，能够提高模型的泛化能力和分类性能。

半监督分类的基本思想是，通过未标注数据帮助模型更好地捕捉数据的结构和分布特性，从而改进分类器的性能。具体而言，半监督学习假设相似的样本应该具有相同的标签，并且数据点之间的关系（如数据点之间的距离或相似性）能够反映标签的相似性。

# 常见的半监督分类方法

1. 自训练（Self-training）：
   • 这种方法首先使用标注数据训练一个初始分类器，然后用该分类器预测未标注数据的标签。将置信度较高的预测结果作为伪标签加入到标注数据集中，重新训练分类器。这个过程可以反复进行，逐步提高分类器的性能。
2. 共训练（Co-training）：
   • 共训练方法通常用于具有多种特征视角的数据集。它会训练两个或多个分类器，每个分类器使用不同的特征视角。然后，这些分类器相互为未标注数据打上伪标签，并相互迭代提升分类性能。
3. 图形模型（Graph-based methods）：
   • 在图形模型中，数据点被表示为图的节点，边表示数据点之间的相似性。通过图的结构，将标注数据的信息传播到未标注数据，以完成分类任务。
4. 生成对抗网络（GANs, Generative Adversarial Networks）：
   • 在半监督学习中，GANs 可以通过生成器生成虚假样本，并通过判别器区分真实样本和生成样本，同时对已标注数据进行分类。
5. 基于一致性正则化（Consistency Regularization-based methods）：
   • 这些方法假设模型在输入加噪声或其他变换后，输出结果应保持一致。通过对未标注数据添加噪声，迫使模型在面对不同的输入扰动时依然能产生一致的分类结果，从而提升模型的鲁棒性和准确性。

# 带标签数据

带标签数据是指每个数据样本都附带了对应的目标输出或答案，这个目标输出通常称为 “标签”。这些标签为模型提供了明确的监督信息，使其能够学习如何将输入数据映射到正确的输出。

例子：

• 图像分类：在一个猫狗分类任务中，带标签数据可能是一组图片，每张图片都标注为 “猫” 或 “狗”。
• 文本分类：在情感分析任务中，带标签数据可能是一组句子，每个句子都标注为 “积极” 或 “消极”。

# 不带标签数据（Unlabeled Data）

不带标签数据是指数据样本没有附带目标输出或答案。这意味着对于每个样本，模型并不知道其对应的标签或类别是什么。由于缺少标签，这些数据不能直接用于传统的监督学习。

例子：

• 图像分类：在相同的猫狗分类任务中，不带标签的数据可能是一组没有任何标签的图片，模型并不知道哪些图片是猫，哪些是狗。
• 文本分类：在情感分析任务中，不带标签的数据可能是一组句子，但模型不知道每个句子的情感是 “积极” 还是 “消极”。

# 图上的快速近似卷积

我们为特定的基于图的神经网络$f(X,A)$ 提供理论动机。我们考虑一个具有以下分层传播规则的多层图卷积神经网络（GCN）：

$$H^{(l+1)}=\sigma\Big(\tilde D^{-\frac{1}{2}}\tilde A\tilde D^{-\frac{1}{2}}H^{(l)}W^{(l)}\Big)$$