S'S ALGORITHM

图卷积神经网络以及代码实现 Graph Convolutional Networks

---

这个主题比较难，但是通过代码可以更好的理解。

图任务类型：图分类和节点分类

图任务类型主要分为图分类（Graph Classification）和节点分类（Node Classification）两种。

1. 图分类（Graph Classification）：
   • 在图分类任务中，整个图被视为输入，目标是对整个图进行分类或预测。通常情况下，图分类任务要求对图的拓扑结构和节点属性进行分析，以确定图所属的类别或标签。例如，社交网络中的社区检测、蛋白质相互作用网络中的功能预测等都是图分类的应用场景。在这种任务中，每个图通常有一个单独的标签或类别。
   • 这种分类是标准的监督问题。因为他们都一定有一个标签的。
2. 节点分类（Node Classification）：
   • 在节点分类任务中，重点是对图中的每个节点进行分类或预测。这意味着每个节点都有一个相应的标签或类别，并且任务的目标是预测节点的类别。例如，社交网络中预测用户的兴趣、知识图谱中预测实体的类型等都属于节点分类任务。在这种任务中，通常会利用节点的邻居信息和节点属性来进行分类。
   • 这种分类问题可能是半监督问题，因为可能图中的很多节点的标签是缺失的，我们的目的可能是给这些节点打标签。比如你的脸书社交网络，突然冒出了可能的关系人，那可能是模型在给你分类了。

图卷积层（Graph Convolutional Layer）

图卷积层（Graph Convolutional Layer）是一种用于图神经网络的核心层，用于学习节点表示的一种方法。图卷积层的形成主要涉及以下步骤：

• 图卷积操作是一种用于在图结构上进行滤波操作的方法，类似于传统卷积神经网络中的卷积操作。它通过聚合节点的邻居信息来更新节点的表示。常见的图卷积操作包括基于邻居节点的加权和或聚合，通常采用邻接矩阵来表示图的连接结构。
• 在图卷积层中，每个节点都有一个表示（或特征向量），表示节点的属性或特征。这些表示通常以矩阵的形式输入到图卷积层中，并在每个图卷积操作中被更新和调整。
• 为了增加模型的深度和复杂度，可以堆叠多个图卷积层来构建深层图神经网络。在这种情况下，每个图卷积层的输出将作为下一层的输入，形成一个多层的图卷积网络结构。
• 通过以上步骤，可以形成一个完整的图卷积层，用于学习和提取图数据中的特征表示，并应用于各种图结构数据的任务中，如节点分类、图分类、链接预测等。

比如最简单的图神经网络计算是将输入特征矩阵 X 乘以邻接矩阵 A，然后再乘以权重矩阵 W，得到输出特征矩阵 Y。这种形式的计算考虑了图的结构和节点特征，并利用权重矩阵进行信息的线性变换。

Y = (AX)W

在这种计算中，不仅考虑了节点的特征 X，还考虑了图的结构/连接性 A。这意味着计算结果不仅依赖于节点自身的特征，还考虑了节点之间的连接关系。邻接矩阵 A 通常是二进制的，表示节点之间的连接关系。但是，它缺乏对连接关系的具体解释，仅仅表示了节点之间的连接或不连接的关系。

图卷积操作可以理解为将图的操作符（邻接矩阵）与图信号（节点特征）相乘，得到每个节点邻域的加权和。这种操作可以使用简单的矩阵乘法来表示，从而实现了对节点邻域信息的聚合。

这种计算，是图神经网络中的基本计算方式。

图卷积通常使用归一化的拉普拉斯矩阵：

因为它具有良好的数学性质并且能够更好地保留图结构的局部性。归一化的拉普拉斯矩阵定义如下：

假设有一个图 G=(V,E)，其中 V 是节点集合，E 是边集合。对于节点 i 和 j 之间的边 (i,j)，我们定义无向图的拉普拉斯矩阵 L 为：

L = D − A

其中，D 是度矩阵，A 是邻接矩阵。度矩阵是一个对角矩阵，其中第 i 个对角元素是节点 i 的度数（即与节点 i 相连的边的数量）。邻接矩阵 A 是一个对称矩阵，其中 A[i, j] 表示节点 i 和 j 之间是否有边相连。

对于归一化的拉普拉斯矩阵，我们使用下面的公式：

L_norm = (D^-1/2)L(D^-1/2)

这两个公式在上一篇的图神经网络数学基础中用代码实现过了可以去查看。

这样做的目的是归一化每个节点的邻居，以便在图卷积操作中平等对待不同节点的邻居。归一化的拉普拉斯矩阵可以在图卷积操作中用来捕捉节点的局部结构和邻居信息。

（Option）谱图卷积神经网路的背景理论 spectral graph convolutional networks

谱图卷积网络（Spectral Graph Convolutional Networks，GCNs）是一种设计用于处理图结构数据的神经网络。它们受到了卷积神经网络（CNNs）在图像数据上的应用的启发，但是将其适应到了图结构上，而不是常规的网格。

1. 图拉普拉斯矩阵：图拉普拉斯矩阵是谱图理论中的基本对象。它是从图的邻接矩阵派生而来的，捕捉了图的结构特性。拉普拉斯矩阵可以以不同的方式定义，例如非归一化拉普拉斯、归一化拉普拉斯或对称归一化拉普拉斯。

2. 图傅里叶变换：就像傅里叶变换在信号处理中将信号分解成不同的频率分量一样，图傅里叶变换将定义在图上的信号分解成不同的图频率分量。图拉普拉斯矩阵的特征向量构成了图傅里叶变换的基，相应的特征值代表图频率。

3. 谱图理论：谱图理论通过图拉普拉斯矩阵的特征值和特征向量来研究图的性质。它提供了对各种图属性的洞察，如图的连通性、图的划分和图的聚类。谱方法利用特征值和特征向量来分析和操作图结构数据。

4. 图卷积网络（GCNs）：GCNs将卷积层的概念从常规网格推广到图结构上。它们通常在谱域操作，其中图信号通过图傅里叶变换进行变换，然后在谱域中进行滤波，最后将其转换回原始域。这种谱滤波操作使得GCNs能够从图结构数据中捕获局部模式和结构信息。

通过结合图拉普拉斯矩阵、图傅里叶变换和谱图理论的原理，谱图卷积网络为学习图结构数据的表示提供了一个强大的框架。它们在各种领域中都有应用，包括节点分类、链接预测和图生成。

切比雪夫展开近似图信号的卷积操作 The recurrent Chebyshev expansion

循环切比雪夫展开是一种用于近似图卷积操作的技术，特别是在谱图卷积网络（GCN）中。它通过利用切比雪夫多项式来近似图信号的卷积操作，从而实现了高效的图卷积层。

这种展开方法的关键思想是使用切比雪夫多项式来逼近图拉普拉斯矩阵的函数。切比雪夫多项式具有良好的近似性质，在给定区间上能够有效地逼近复杂的函数。总的来说它的目的是为了简化计算。

具体来说，循环切比雪夫展开的步骤如下：

1. 归一化图拉普拉斯矩阵：首先，对图拉普拉斯矩阵进行归一化处理，以确保其特征值范围在[-1, 1]之间。

2. 选择切比雪夫多项式的阶数：确定展开的阶数，即切比雪夫多项式的最高次数。通常，选择一个适当的阶数来保证展开的精度。

3. 计算切比雪夫多项式：利用循环切比雪夫多项式的递归定义，计算出对应阶数的切比雪夫多项式。

4. 展开图卷积操作：将图卷积操作近似为切比雪夫多项式与图信号之间的乘积，在频谱域中进行滤波操作。这样可以有效地减少计算量，同时保持较高的近似精度。

通过循环切比雪夫展开，可以实现高效的图卷积操作，从而加速图神经网络的训练和推理过程。这种方法在处理大规模图数据时特别有用，可以有效地处理高维度的图结构信息。

对特征值进行光谱过滤 under the hood: spectral filtering on the eigenvalues

对特征值进行光谱过滤是指在谱图卷积网络（Spectral Graph Convolutional Networks，GCN）中，利用图信号的频谱信息进行滤波操作，以实现图卷积的计算。在这种方法中，我们将图信号的频谱表示与滤波器的频谱表示进行乘积，从而实现对图信号的局部滤波。

具体来说，谱图卷积网络利用图信号的拉普拉斯矩阵的特征值和特征向量来进行滤波操作。首先，将图信号表示为拉普拉斯矩阵的特征向量的线性组合，然后对特征向量进行光谱滤波。光谱滤波是一种基于频谱分析的滤波方法，它可以根据信号的频谱特性对信号进行加权处理。

在谱图卷积网络中，滤波器通常表示为一组学习得到的参数，可以通过训练来优化。这些滤波器在频谱域中对图信号进行加权处理，以提取图的局部特征信息。通过对特征值进行光谱过滤，谱图卷积网络可以实现对图结构的有效表征和学习，从而在图数据上实现高效的机器学习任务。

使用代码图解图卷积方法

import torch
import torch.nn as nn

def create_adj(size):
    # 创建大小为size*size的随机邻接矩阵
    a = torch.rand(size,size)
    a[a>0.5] = 1
    a[a<=0.5] = 0

    # 将对角元素设为零，仅用于说明
    for i in range(a.shape[0]):
        for j in range(a.shape[1]):
            if i==j:
                a[i,j] = 0
    return a

def calc_degree_matrix(a):
    # 计算度矩阵
    return torch.diag(a.sum(dim=-1))

def create_graph_lapl(a):
    # 创建图拉普拉斯矩阵
    return calc_degree_matrix(a)-a

def calc_degree_matrix_norm(a):
    # 计算标准化度矩阵
    return torch.diag(torch.pow(a.sum(dim=-1),-0.5))

def create_graph_lapl_norm(a):
    # 创建归一化图拉普拉斯矩阵
    size = a.shape[-1]
    D_norm = calc_degree_matrix_norm(a)
    L_norm = torch.ones(size) - (D_norm @ a @ D_norm )
    return L_norm

# 以上为止都是上一篇理论篇中有过的内容
def find_eigmax(L):
    # 寻找拉普拉斯矩阵的最大特征值
    with torch.no_grad():
        e1, _ = torch.eig(L, eigenvectors=False)
        return torch.max(e1[:, 0]).item()

def chebyshev_Lapl(X, Lapl, thetas, order):
    """
    使用切比雪夫多项式展开计算图拉普拉斯矩阵的多项式函数。
    
    参数:
        X: 输入特征矩阵，形状为 (节点数, 输入特征维度)。
        Lapl: 图拉普拉斯矩阵。
        thetas: 切比雪夫多项式的系数参数。
        order: 切比雪夫多项式的阶数，表示展开的次数。
        
    返回:
        y_out: 计算得到的图卷积输出特征矩阵，形状为 (节点数, order * 输入特征维度)。
    """
    list_powers = []
    nodes = Lapl.shape[0]

    # 将输入特征矩阵转换为浮点型
    T0 = X.float()

    # 寻找图拉普拉斯矩阵的最大特征值
    eigmax = find_eigmax(Lapl)
    # 对图拉普拉斯矩阵进行重新缩放，使其值范围在[-1, 1]之间
    L_rescaled = (2 * Lapl / eigmax) - torch.eye(nodes)

    # 计算切比雪夫多项式的各阶结果
    y = T0 * thetas[0]
    list_powers.append(y)
    T1 = torch.matmul(L_rescaled, T0)
    list_powers.append(T1 * thetas[1])

    # 迭代计算切比雪夫多项式的各阶结果
    for k in range(2, order):
        T2 = 2 * torch.matmul(L_rescaled, T1) - T0
        list_powers.append((T2 * thetas[k]))
        T0, T1 = T1, T2
    
    # 将多项式函数连接起来
    y_out = torch.stack(list_powers, dim=-1)
    y_out = y_out.view(nodes, -1)
    return y_out


features = 3
out_features = 50
a = create_adj(10)
L = create_graph_lapl_norm(a)
x = torch.rand(10, features)
power_order = 4 # p-hops
thetas = nn.Parameter(torch.rand(4))

out = chebyshev_Lapl(x,L,thetas,power_order)

print('cheb approx out powers concatenated:', out.shape)
# 输出特征数为 power_order * features
linear = nn.Linear(4*3, out_features)

layer_out = linear(out)
print('Layers output:', layer_out.shape)

输出：

cheb approx out powers concatenated: torch.Size([10, 12])
Layers output: torch.Size([10, 50])

这段代码实现了基于切比雪夫多项式展开的图卷积神经网络的计算过程。以下是代码中各部分的解释：

1. create_adj(size): 创建一个随机邻接矩阵，大小为 size x size，用于表示图的连接关系。

2. calc_degree_matrix(a): 计算给定邻接矩阵的度矩阵，用于表示每个节点的度数。

3. create_graph_lapl(a): 根据给定的邻接矩阵创建图拉普拉斯矩阵，用于表示图的结构特征。

4. calc_degree_matrix_norm(a): 计算给定邻接矩阵的标准化度矩阵，用于归一化图的结构特征。

5. create_graph_lapl_norm(a): 根据给定的邻接矩阵创建归一化图拉普拉斯矩阵，用于归一化表示图的结构特征。

6. find_eigmax(L): 寻找给定图拉普拉斯矩阵的最大特征值。

7. chebyshev_Lapl(X, Lapl, thetas, order): 使用切比雪夫多项式展开计算给定图拉普拉斯矩阵的多项式函数。

8. features = 3: 输入特征的数量。

9. out_features = 50: 输出特征的数量。

10. thetas = nn.Parameter(torch.rand(4)): 定义切比雪夫多项式的系数参数。

11. out = chebyshev_Lapl(x,L,thetas,power_order): 使用切比雪夫多项式展开计算图卷积。

12. linear = nn.Linear(4*3, out_features): 定义线性层，用于将多项式函数的输出转换为所需的输出特征数量。

13. layer_out = linear(out): 应用线性层，得到图卷积网络的最终输出。

输出结果表示了图卷积网络中的两个关键维度：

1. cheb approx out powers concatenated: torch.Size([10, 12])：这个输出表示经过切比雪夫多项式展开后的图卷积层的输出特征矩阵的大小。具体来说，第一个维度是节点数，第二个维度是展开后的特征维度，也就是切比雪夫多项式的阶数乘以输入特征的维度。在这个例子中，共有10个节点，展开了4阶切比雪夫多项式，每个节点的特征维度为3，所以输出的大小为 [10, 12]。

2. Layers output: torch.Size([10, 50])：这个输出表示了经过线性层后的最终输出特征矩阵的大小。在这个例子中，线性层将输入特征从12维映射到50维，因此输出的大小为 [10, 50]。

这段代码实现了基于切比雪夫多项式展开的图卷积操作，并且可以通过参数化的方式学习多项式的系数，从而实现对图数据的有效特征提取和学习。

基于 PyTorch 的 GCN 实现：Implementation of a GCN

代码的目标是实现一个简单的1-hop图卷积网络（GCN）层，并在一个小型图数据集上进行训练。

选择了MUTAG数据集作为示例，这是一个小型的图数据集，包含188个图，每个图节点的标签从0到6不等，用作一个独热编码的特征向量。将其中的150个图用于训练，剩余的用于验证。最终目标是对图进行二分类。

首先实现一个简单的图卷积层，然后将其应用到网络中进行训练。最终的结果将以准确率的形式呈现。

输出方式和一般的训练相似：

Epoch: 220, Train Acc: 80.0000, Val Acc: 73.6842
Epoch: 230, Train Acc: 76.6667, Val Acc: 65.7895
Epoch: 240, Train Acc: 75.3333, Val Acc: 71.0526

Finished training. Best obtained val score: 78.9474

训练的笔记本在projects-drafts文件夹里。