一、背景介绍
1.1 图论基础
定义一（图的邻接矩阵）：
给定一个图G = { V , E } \mathcal{G}=\{\mathcal{V}, \mathcal{E}\}G={V,E}，其对应的邻接矩阵被记为
表示存在从结点v i v_iv
i
到v j v_jv
j
的边，反之表示不存在从结点v i v_iv
i
到v j v_jv
j
的边。
在无向图中，从结点v i v_iv
i
到v j v_jv
j
的边存在，意味着从结点v j v_jv
j
到v i v_iv
i
的边也存在。因而无向图的邻接矩阵是对称的。
在无权图中，各条边的权重被认为是等价的，即认为各条边的权重为1 11。
对于有权图，其对应的邻接矩阵通常被记为W ∈ { 0 , 1 } N × N \mathbf{W} \in\{0,1\}^{N \times N}W∈{0,1}
N×N
，其中W i , j = w i j \mathbf{W}_{i, j}=w_{ij}W
i,j
=w
ij
表示从结点v i v_iv
i
到v j v_jv
j
的边的权重。若边不存在时，边的权重为0 00。
一个无向无权图的例子：
其邻接矩阵为：
定义二（拉普拉斯矩阵，Laplacian Matrix）：
给定一个图G = { V , E } \mathcal{G}=\{\mathcal{V}, \mathcal{E}\}G={V,E}，其邻接矩阵为A AA，其拉普拉斯矩阵定义为L = D − A \mathbf{L=D-A}L=D−A，其中度矩阵 D = d i a g ( d ( v 1 ) , ⋯ , d ( v N ) ) \mathbf{D=diag(d(v_1), \cdots, d(v_N))}D=diag(d(v
1
),⋯,d(v
N
))。
定义三（对称归一化的拉普拉斯矩阵，Symmetric normalized Laplacian）：
给定一个图G = { V , E } \mathcal{G}=\{\mathcal{V}, \mathcal{E}\}G={V,E}，其邻接矩阵为A AA，其规范化的拉普拉斯矩阵定义为
1.2 拉普拉斯矩阵的变体
节点数为n nn的简单图G GG，A AA是G GG的邻接矩阵，则如上面介绍的那样，G GG的拉普拉斯矩阵即L = D − A L=D-AL=D−A。
（1）对称归一化后的拉普拉斯矩阵：
（2）随机游走归一化的拉普拉斯矩阵：
1.3 拉普拉斯矩阵的优良性质：
拉普拉斯矩阵是半正定对称矩阵
对称矩阵有n个线性无关的特征向量，n是Graph中节点的个数 ⇒ \Rightarrow⇒ 拉普拉斯矩阵可以特征分解
半正定矩阵的特征值非负
对称矩阵的特征向量构成的矩阵为正交阵 ⇒ U T U = E \Rightarrow U^{T} U=E⇒U
T
U=E
1.4 GCN为啥要用拉普拉斯矩阵
拉普拉斯矩阵可以谱分解（特征分解）GCN是从谱域的角度提取拓扑图的空间特征的。
拉普拉斯矩阵只在中心元素和一阶相邻元素处有非零元素，其他位置皆为0.
传统傅里叶变换公式中的基函数是拉普拉斯算子，借助拉普拉斯矩阵，通过类比可以推导出Graph上的傅里叶变换公式。
二、Python代码实现
这是networkX库对稀疏矩阵A的处理方式，有少量改进（将所有内容保持稀疏）：
n,m = A.shape diags = A.sum(axis=1) D = sps.spdiags(diags.flatten(), [0], m, n, format='csr') D - A
numpy和scipy两个库中模块中都提供了线性代数的库linalg，但scipy的linalg的更全面一些。
# laplacian矩阵 import numpy as np def unnormalized_laplacian(adj_matrix): # 先求度矩阵 R = np.sum(adj_matrix, axis=1) degreeMatrix = np.diag(R) return degreeMatrix - adj_matrix # 对称归一化的laplacian矩阵 def normalized_laplacian(adj_matrix): R = np.sum(adj_matrix, axis=1) R_sqrt = 1/np.sqrt(R) D_sqrt = np.diag(R_sqrt) I = np.eye(adj_matrix.shape[0]) return I - np.matmul(np.matmul(D_sqrt, adj_matrix), D_sqrt)
matlab的代码实现为：
L = diag(sum(A,2)) - A % or L=diag(sum(A))-A because A is symmetric
那么如何求矩阵的特征值呢——利用numpy的linalg.eig：
# !/usr/bin/python ## -*-coding:utf-8 -*- import numpy as np A = np.array([[3,-1],[-1,3]]) print('打印A：\n{}'.format(A)) a, b = np.linalg.eig(A) print('打印特征值a：\n{}'.format(a)) print('打印特征向量b：\n{}'.format(b))
得到特征值和特征向量：
打印A： [[ 3 -1] [-1 3]] 打印特征值a： [4. 2.] 打印特征向量b： [[ 0.70710678 0.70710678] [-0.70710678 0.70710678]]
三阶矩阵试试，回归考研线代的题目：
import numpy as np A = np.array([[2,-3,1],[1,-2,1],[1,-3,2]]) print('打印A：\n{}'.format(A)) a, b = np.linalg.eig(A) print('打印特征值a：\n{}'.format(a)) print('打印特征向量b：\n{}'.format(b))
结果如下，看结果的特征向量矩阵，每一列代表一个一个特征向量，都是
打印A： [[ 2 -3 1] [ 1 -2 1] [ 1 -3 2]] 打印特征值a： [2.09037533e-15+0.00000000e+00j 1.00000000e+00+5.87474805e-16j 1.00000000e+00-5.87474805e-16j] 打印特征向量b： [[0.57735027+0.j 0.84946664+0.j 0.84946664-0.j ] [0.57735027+0.j 0.34188085-0.11423045j 0.34188085+0.11423045j] [0.57735027+0.j 0.17617591-0.34269135j 0.17617591+0.34269135j]]
三、关于图Fourier变换
根据卷积原理，卷积公式可以写成
正、逆Fourier变换
一阶导数定义
拉普拉斯相当于二阶导数
在graph上，定义一阶导数为
对应的拉普拉斯算子定义为
假设D DD为N × N N\times{N}N×N的度矩阵(degree matrix)
A为N × N N\times{N}N×N的邻接矩阵(adjacency matrix)
那么图上的Laplacian算子可以写成
标准化后得到
定义Laplacian算子的目的是为了找到Fourier变换的基。
传统Fourier变换的基就是Laplacian算子的一组特征向量
类似的，在graph上，有
图拉普拉斯算子作用在由图节点信息构成的向量f ff上得到的结果等于图拉普拉斯矩阵和向量f ff的点积。
那么graph上的Fourier基就是L LL矩阵的n nn个特征向量U = [ u 1 … u n ] U=\left[u_{1} \dots u_{n}\right]U=[u
1
…u
n
]，L LL可以分解成L = U Λ U T L=U \Lambda U^{T}L=UΛU
T
，其中，Λ \LambdaΛ是特征值组成的对角矩阵。
传统的Fourier变换与graph的Fourier变换区别
将f ( i ) f(i)f(i)看成是第i ii个点上的signal，用向量x = ( f ( 1 ) … f ( n ) ) ∈ R n x=(f(1) \ldots f(n)) \in \mathbb{R}^{n}x=(f(1)…f(n))∈R
n
来表示。矩阵形式的graph的Fourier变换为
类似的graph上的Fourier逆变换为
