图神经网络和图卷积也是我第一次接触的内容。图是一种具有内在结构的数据的超常规表示。
从图像开始是最直观的过渡。因为图像是高度结构化的数据。它们的组件（像素）以有意义的方式排列。如果改变像素的结构方式，图像就失去了其含义。此外，图像具有非常强的局部性概念。
图片的像素被排列成一个网格，这就是图像的结构。由于结构很重要，因此设计过滤器来将像素邻域的表示分组是有意义的。这些过滤器就是卷积（在CNN的篇章中学习过）。像素还具有一个（灰度）或多个强度通道。以一般形式来说，每个像素都有一个描述它的特征向量。因此，通道强度可以被看作是图像的信号。
理解图的关键概念，分解结构和信号（特征）这两个概念。结构是一种位置关系，一种前后相邻的方法，信号是内容，是特征，是强弱信息。类似的自然语言处理，也有结构和信号。
学习算法中，一个图由节点（nodes）和边（edges）组成。节点代表图中的实体，例如人、物体、事件等，而边表示节点之间的关系或连接。在一些情况下，边可以有权重，表示连接的强度或相关性。
在图神经网络中，图的表示通常使用邻接矩阵（Adjacency Matrix）来表示图的连接关系。这和数据结构中的图类似。除了邻接矩阵外，图神经网络还需要节点特征矩阵（Node Feature Matrix）。节点特征矩阵包含了每个节点的特征信息，例如节点的属性、文本表示或其他向量化的特征。这些特征向量描述了节点的属性，是图神经网络进行学习和推断的关键。
在图神经网络中，我们的目标是学习一个映射函数，将图中的节点和边的表示映射到某个输出。这个映射函数通常由多层神经网络组成，每一层可以通过信息传递和聚合来融合邻近节点的信息。这样的设计使得图神经网络能够有效地利用图的结构和节点的特征进行学习和推断。
总之，图神经网络是一种用于处理图数据的机器学习模型，它利用图的结构和节点的特征来学习和推断图中的信息。通过有效地表示图的连接关系和节点的属性，图神经网络可以在各种领域中应用，例如社交网络分析、推荐系统、生物信息学等。
度矩阵（Degree Matrix）是图论中一个重要的概念，用于表示图中节点的度（degree）信息。节点的度是指与该节点相连的边的数量。在无向图中，节点的度等于与其相邻的节点的数量；在有向图中，节点的度分为入度（In-Degree）和出度（Out-Degree），分别表示指向该节点的边的数量和由该节点指向其他节点的边的数量。
度矩阵是一个对角矩阵，其对角线上的元素表示每个节点的度。对于一个包含 N 个节点的图，其度矩阵的形式为：
D = | d_1 0 ... 0 |
| 0 d_2 ... 0 |
| ... ... ... ... |
| 0 0 ... d_N |
其中，d_i 表示第 i 个节点的度。
度矩阵在图的分析和图算法中具有重要的作用。例如，在图神经网络中，度矩阵常用于标准化邻接矩阵，以便在图卷积等操作中更好地考虑节点的度对图的影响。度矩阵还可以用于计算图的拉普拉斯矩阵等其他重要的图论概念。
代码实现：
import torch
#rand binary Adj matrix
a = torch.rand(3,3)
a[a>0.5] = 1
a[a<=0.5] = 0
def calc_degree_matrix(a):
return torch.diag(a.sum(dim=-1))
d = calc_degree_matrix(a)
print("A:" ,a)
print("D:", d)
# A: tensor([[1., 0., 0.],
# [1., 0., 1.],
# [0., 0., 0.]])
# D: tensor([[1., 0., 0.],
# [0., 2., 0.],
# [0., 0., 0.]])
首先生成的是一个3乘以3大小的随机矩阵，元素大小在0到1之间，通过处理将它转换为二进制的邻接矩阵，表示一个随机图的连接关系。
接下来定义的函数calc_degree_matrix用于计算邻接矩阵的度矩阵，对于每个节点的相连的边的数量标注在对角线上。
dim=-1表示沿着最后一个维度求和。是因为在邻接矩阵中，通常最后一个维度对应着图中的节点。在大多数情况下，我们将邻接矩阵定义为一个二维张量，其中的每一行或每一列对应着图中的一个节点。因此，沿着最后一个维度求和，实际上是对每个节点的连接关系进行求和，从而得到每个节点的度。
在实际应用中，我们通常希望对每个节点的连接关系进行统计，以了解其在图中的连接情况。因此，沿着最后一个维度求和是一种自然的选择，可以直接得到每个节点的度信息。
图拉普拉斯（Graph Laplacian）是图论中的一个重要概念，用于描述图的结构和性质。它有几种不同的定义，其中最常见的是标准化的对称拉普拉斯矩阵。在给定一个图 G 的情况下，其标准化的对称拉普拉斯矩阵 L 定义为：L = D - A
其中，A 是图 G 的邻接矩阵，D 是度矩阵，定义为对角矩阵，其对角线上的元素为每个节点的度。这两个在前面的代码中计算过了。对于无向图，度矩阵 D 的对角线元素是节点的度；对于有向图，D 的对角线元素分别是节点的入度和出度之和。
标准化的对称拉普拉斯矩阵具有许多重要的性质和应用。例如，它是半正定矩阵，其特征值非负；它的零特征向量对应于图的连通分量；它与图的谱图论密切相关，可以用于图的划分、聚类、降维等任务。
标准化的拉普拉斯矩阵对图中节点的度进行了归一化处理，使得在不同规模的图中能够更好地比较节点之间的关系。这样可以减少节点度数对图算法的影响，提高算法的稳定性和鲁棒性。比如有一个邻接边的节点和一百个邻接边的节点就会不平衡。
在图卷积网络（Graph Convolutional Networks，GCN）等图神经网络模型中，标准化的拉普拉斯矩阵被用作节点的邻接矩阵，用于表示节点之间的关系，并通过将节点的特征与标准化的拉普拉斯矩阵进行乘积或其它操作，可以实现节点特征的传播和信息聚合。
总之，图拉普拉斯是描述图结构和性质的重要工具，在图论、机器学习和网络科学等领域有着广泛的应用。
未标准化的图拉普拉斯：它只是在之前的代码的计算的基础上，进行了一次减法运算。
import torch
#rand binary Adj matrix
a = torch.rand(5,5)
a[a>0.5] = 1
a[a<=0.5] = 0
def calc_degree_matrix(a):
return torch.diag(a.sum(dim=-1))
def create_graph_lapl(a):
return calc_degree_matrix(a)-a
print("A:", a)
print("L:", create_graph_lapl(a))
# A: tensor([[1., 0., 1., 0., 1.],
# [0., 0., 1., 1., 0.],
# [0., 1., 0., 1., 1.],
# [1., 0., 0., 0., 0.],
# [0., 0., 1., 0., 0.]])
# L: tensor([[ 2., 0., -1., 0., -1.],
# [ 0., 2., -1., -1., 0.],
# [ 0., -1., 3., -1., -1.],
# [-1., 0., 0., 1., 0.],
# [ 0., 0., -1., 0., 1.]])
标准化图拉普拉斯：
import torch
#rand binary Adj matrix
a = torch.rand(5,5)
a[a>0.5] = 1
a[a<=0.5] = 0
# 对邻接矩阵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
print("A: ", a)
print("L_norm: ", create_graph_lapl_norm(a))
# A: tensor([
# [0., 0., 0., 1., 1.],
# [1., 1., 1., 1., 1.],
# [0., 1., 0., 0., 0.],
# [1., 0., 1., 1., 0.],
# [0., 1., 0., 0., 0.]
# ])
# L_norm: tensor([
# [1.0000, 1.0000, 1.0000, 0.5918, 0.2929],
# [0.6838, 0.8000, 0.5528, 0.7418, 0.5528],
# [1.0000, 0.5528, 1.0000, 1.0000, 1.0000],
# [0.5918, 1.0000, 0.4226, 0.6667, 1.0000],
# [1.0000, 0.5528, 1.0000, 1.0000, 1.0000]])
难点在于torch.ones(size) - (D_norm @ a @ D_norm)将全1的矩阵减去标准化的度矩阵与邻接矩阵的乘积。这个操作实际上是在计算图的拉普拉斯矩阵的拉普拉斯特征值为1的情况下的拉普拉斯矩阵。因此，得到的结果是一个描述了图的结构信息的矩阵，称为标准化的图拉普拉斯矩阵。
这里分解一下数学。D_norm @ a @ D_norm 的求解结果是下面这样的矩阵，用1减去它就是最终结果。
tensor([[0.0000, 0.0000, 0.5774, 0.0000, 0.0000],
[0.5000, 0.2500, 0.2887, 0.0000, 0.3536],
[0.5774, 0.0000, 0.0000, 0.2582, 0.4082],
[0.4472, 0.2236, 0.2582, 0.2000, 0.3162],
[0.7071, 0.0000, 0.4082, 0.0000, 0.0000]])
D_norm 是标准化度矩阵，它是度矩阵的逆的平方根的对角矩阵。对于度矩阵 D，其对角线元素为每个节点的度，标准化度矩阵 D_norm 的对角线元素为每个节点度的倒数的平方根。可以用来进行整个矩阵的标准化。它的输出如下这种形式：(我没有加seed可能我们计算出来的不一样，这没关系)，注意它对角线上的元素被归一化了。
tensor([[0.5774, 0.0000, 0.0000, 0.0000, 0.0000],
[0.0000, 0.7071, 0.0000, 0.0000, 0.0000],
[0.0000, 0.0000, 0.5774, 0.0000, 0.0000],
[0.0000, 0.0000, 0.0000, 0.5774, 0.0000],
[0.0000, 0.0000, 0.0000, 0.0000, 0.7071]])
在问题中，我们对邻接矩阵 a 的左右两侧分别乘以标准化度矩阵 D_norm，这个过程可以理解为对邻接矩阵的每一行和每一列进行了标准化操作。
具体来说：
整个过程中，左右两侧的操作都是为了实现邻接矩阵的归一化，使得每个节点的相邻节点对图的影响更加均衡。左右两侧的操作都是标准化，只是分别针对了邻接矩阵的行和列维度。
补充1:对于标准化和归一化的再次澄清，标准化是将维度缩放到0，1尺度，归一化不一定，它可是自己规定一个最大最小尺度。
补充2:在文章最后补充了数学中关于矩阵逆的意义和计算方法。
对于一个矩阵，其特征值和特征向量是一对重要的概念。特征向量是一个非零向量，当被该矩阵作用后，只发生缩放而不改变方向；而特征值是一个标量，表示特征向量被缩放的程度。特征值和特征向量对于矩阵的理解和分析具有重要作用，它们可以提供关于矩阵的结构和性质的信息。
拉普拉斯矩阵通常定义为度矩阵（Degree Matrix）与邻接矩阵（Adjacency Matrix）之间的差，如刚刚输出的 L。反映了图的拓扑结构和连接方式。拉普拉斯矩阵的特征值和特征向量也被称为拉普拉斯特征值和拉普拉斯特征向量。它们对于图的结构和连接性质提供了重要的信息。
在拉普拉斯矩阵的特征值中，零特征值具有重要的意义。零特征值的个数等于图的连通分量的个数，因此零特征值可以用来判断图的连通性。如果一个图有多个连通分量，那么零特征值会对应多个线性无关的特征向量，从而反映了图的分割情况。
L: tensor([
[ 2., 0., -1., 0., -1.],
[ 0., 2., -1., -1., 0.],
[ 0., -1., 3., -1., -1.],
[-1., 0., 0., 1., 0.],
[ 0., 0., -1., 0., 1.]
])
标准的拉普拉斯矩阵的特征值是非负实数，特征向量则对应着图中的某种模式或者振动。
L_norm: tensor([
[1.0000, 1.0000, 1.0000, 0.5918, 0.2929],
[0.6838, 0.8000, 0.5528, 0.7418, 0.5528],
[1.0000, 0.5528, 1.0000, 1.0000, 1.0000],
[0.5918, 1.0000, 0.4226, 0.6667, 1.0000],
[1.0000, 0.5528, 1.0000, 1.0000, 1.0000]])
拉普拉斯矩阵的零特征值数量，对应有几个连通分量，零特征值的数量等于该图的连通分量的数量。这个概念涉及到图的连接性和拓扑结构。
一个连通分量指的是图中的一个子图，其中的任意两个节点之间都有路径相连。如果一个图是连通的，则整个图就是一个连通分量。但如果一个图由多个不相连的子图组成，则每个子图就是一个连通分量。
因此，当一个图具有多个连通分量时，它的零特征值的数量就等于它的连通分量的数量。每个零特征值对应一个线性无关的特征向量，这些特征向量反映了图中每个连通分量的结构。
两个分离的子图中的节点之间没有直接的路径相连，无法从任意一个节点出发经过一系列的边访问到其他所有节点。换句话说，子图中的节点形成了一个孤立的集合，彼此之间无法直接通信或到达。
如果说，一个图只有单个零特征值，表示整个图是连通的，即从图中的任意一个节点出发，都可以通过遍历图的边访问到所有其他节点。这种情况下，图中的节点之间存在通路，可以通过一定的步骤相互到达，从而可以实现信息传递和遍历。Petersen图是一个有名的网络图，它是连通图，并且它有一个零特征值。下面的代码中绘制的Petersen图，都是一个具有单个零特征值的图形，可以测试看看，他们都是连通的，意味着从任意一个节点出发，你可以通过一定的步骤访问到所有其他节点。
import matplotlib.pyplot as plt
import networkx as nx # 导入网络图库networkx
# 创建一个Petersen图，它是一个小型的非常有名的图
G = nx.petersen_graph()
# 绘制Petersen图，subplot(121)表示将图绘制在1x2的网格中的第1个位置
plt.subplot(121)
nx.draw(G, with_labels=False, font_weight='bold')
# 绘制图G，with_labels=False表示不显示节点标签，font_weight='bold'表示节点标签使用粗体显示
# 绘制带有壳形状的Petersen图，subplot(122)表示将图绘制在1x2的网格中的第2个位置
plt.subplot(122)
nx.draw_shell(G, nlist=[range(5, 10), range(5)], with_labels=False, font_weight='bold')
# 绘制图G，nlist参数指定每个壳中节点的排列顺序，with_labels=False表示不显示节点标签，font_weight='bold'表示节点标签使用粗体显示
# 定义绘图参数
options = {
'node_color': 'blue', # 节点颜色为蓝色
'node_size': 100, # 节点大小为100
'width': 2, # 边的宽度为2
}
# 绘制随机布局的Petersen图，subplot(221)表示将图绘制在2x2的网格中的第1个位置
plt.subplot(221)
nx.draw_random(G, **options) # 绘制图G，**options表示传递绘图参数
# 绘制圆形布局的Petersen图，subplot(222)表示将图绘制在2x2的网格中的第2个位置
plt.subplot(222)
nx.draw_circular(G, **options)
# 绘制谱布局的Petersen图，subplot(223)表示将图绘制在2x2的网格中的第3个位置
plt.subplot(223)
nx.draw_spectral(G, **options)
# 绘制带有壳形状的Petersen图，subplot(224)表示将图绘制在2x2的网格中的第4个位置
plt.subplot(224)
nx.draw_shell(G, nlist=[range(5,10), range(5)], **options) # 绘制图G，nlist参数指定每个壳中节点的排列顺序，**options表示传递绘图参数
# 显示绘图结果就可以看到你的图了
plt.show()
在数学和物理学中，谱是一种特征分解的概念，用于描述线性操作符的性质。谱包含了这个操作符的特征值和特征向量，它们提供了关于操作符行为和结构的重要信息。
在线性代数中，一个矩阵的谱是指其特征值的集合。特征值是矩阵乘法的特定操作符的根本特征，它们描述了这个操作符对某些向量进行缩放的程度。特征向量是与特征值相关联的向量，它们描述了在操作符作用下发生的线性变换。
在物理学中，谱也指的是某些物理系统的特征分解。例如，原子的光谱是指原子在不同频率下发射或吸收光子的模式，它提供了关于原子结构和能级的信息。
总之，谱是一种用于描述线性操作符或物理系统特征的工具，它包含了特征值和特征向量，并提供了对系统行为和结构的深入理解。
谱图像分割是一种基于图拉普拉斯算子的图像分割技术，它利用了图的谱特性来将图像分成不同的区域。
这个过程主要包括：
构建相似性图： 首先，将图像转换为图形表示，其中每个像素作为图的节点，相邻像素之间的相似性作为边的权重。这个相似性通常基于像素之间的颜色、亮度、纹理等特征。
构建拉普拉斯矩阵： 利用相似性图构建图的拉普拉斯矩阵。拉普拉斯矩阵是描述图结构和连接性的重要工具，它的特征值和特征向量可以提供关于图的拓扑结构和分割的信息。
计算特征向量： 对图的拉普拉斯矩阵进行特征值分解，得到其特征值和特征向量。通常，取前几个非零特征值对应的特征向量作为特征空间。
谱聚类： 利用特征向量进行谱聚类，将图像中的像素划分为不同的区域。谱聚类是一种基于图谱特征的聚类方法，它将图像分割问题转化为图上的点聚类问题，通过优化特定的目标函数来实现。
后处理： 对聚类结果进行后处理，例如合并相似的区域、去除噪声等，以得到最终的分割结果。
以下是一段进行谱图分割的代码：
import numpy as np
from scipy import misc
from skimage.transform import resize
import matplotlib.pyplot as plt
from numpy import linalg as LA
from scipy.sparse import csgraph
from sklearn.feature_extraction.image import img_to_graph
from sklearn.cluster import spectral_clustering
re_size = 64 # 重采样的大小
img = misc.face(gray=True) # 获取一张灰度图像
img = resize(img, (re_size, re_size)) # 调整图像大小
mask = img.astype(bool) # 创建一个与图像相同大小的布尔掩码
graph = img_to_graph(img, mask=mask) # 将图像转换为图形表示
# 取梯度的减小函数：我们使其依赖于梯度的程度较弱
# 分割接近于沃罗诺伊
graph.data = np.exp(-graph.data / graph.data.std()) # 使用图的标准差计算梯度的指数函数
labels = spectral_clustering(graph, n_clusters=3) # 使用谱聚类对图像进行分割，将其划分为3个簇
label_im = -np.ones(mask.shape) # 创建一个与掩码相同大小的数组，并初始化为-1
label_im[mask] = labels # 将聚类标签应用到掩码上
# 显示原始图像
plt.figure(figsize=(6, 3))
plt.imshow(img, cmap='gray', interpolation='nearest')
# 显示分割后的图像
plt.figure(figsize=(6, 3))
plt.imshow(label_im, cmap=plt.cm.nipy_spectral, interpolation='nearest')
plt.show()
图是由节点（顶点）和边（连接节点的线）组成的数学结构。根据边的性质和图的结构，图可以分为多种类型，主要包括：
这些分类类型可以帮助我们更好地理解图的结构和性质，以及在不同场景下选择合适的图模型和算法进行分析和处理。
是一种常用的稀疏矩阵的表达方式。Coordinate Format。
举一个代码例子就明白了：
import numpy as np
import scipy.sparse as sparse
# 定义行索引数组
row = np.array([0, 3, 1, 0])
# 定义列索引数组
col = np.array([0, 3, 1, 2])
# 定义数据数组
data = np.array([4, 5, 7, 9])
# 使用COO格式创建稀疏矩阵
mtx = sparse.coo_matrix((data, (row, col)), shape=(4, 4))
# 将稀疏矩阵转换为密集矩阵并打印输出
print(mtx.todense())
# output
matrix([[4, 0, 9, 0],
[0, 7, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 5]])
COO格式简单易懂。然而，对于执行矩阵操作来说效率不高，特别是对于大型稀疏矩阵而言，因为它需要显式存储非零元素的索引。
矩阵的逆： 对于一个方阵 A，如果存在一个矩阵 A^−1，使得 A x A^−1 = A^−1 × A = I，其中 I 是单位矩阵，那么称矩阵 A 可逆，A^−1 就是 A 的逆矩阵。逆矩阵可以看作是原矩阵的倒数，它可以用来解线性方程组和进行线性变换的逆操作。这种操作在一般的数学运算中也是一样的，一个数字和它的倒数相乘结果也是1，这个1可以当做一个单位。
总之一个矩阵的逆就是它的倒数。
矩阵的逆可以通过多种方法进行计算，包括高斯消元法、LU分解、QR分解、特征值分解等。每种方法都有其适用范围和计算复杂度，选择合适的方法取决于矩阵的特性和计算需求。
二阶行列式可以通过公式直接计算：
A = [[a, b],
[c, d]]
A^-1 = 1 / (ad - bc) x [[d, -b],[-c, a]]
三阶以上使用初等变换法：