拉普拉斯矩阵是图论中用到的一种重要矩阵，给定一个有n个顶点的图 G=(V,E)，其拉普拉斯矩阵被定义为 L = D-A，D其中为图的度矩阵，A为图的邻接矩阵。例如，给定一个简单的图：
邻接矩阵A为：
\[\begin{pmatrix} 0&1&0&0&1&0\\\\1&0&1&0&1&0\\\\0&1&0&1&0&0\\\\0&0&1&0&1&1\\\\1&1&0&1&0&0\\\\0&0&0&1&0&0 \end{pmatrix}\]把A的每一列元素加起来得到N个数(其实也就是每个结点的度)，然后把它们放到对角线上，组成一个$N×N$的对角矩阵，记为度矩阵D：
\[D = diag(deg(1),deg(2),....deg(n))\] \[\begin{pmatrix} 2&0&0&0&0&0\\\\0&3&0&0&0&0\\\\0&0&2&0&0&0\\\\0&0&0&3&0&0\\\\0&0&0&0&3&0\\\\0&0&0&0&0&1 \end{pmatrix}\]根据拉普拉斯矩阵的定义$L = D-A$，可得拉普拉斯矩阵$L$为：
\[\begin{pmatrix} 2&-1&0&0&-1&0\\\\-1&3&-1&0&-1&0\\\\0&-1&2&-1&0&0\\\\0&0&-1&3&-1&-1\\\\-1&-1&0&-1&3&0\\\\0&0&0&-1&0&1 \end{pmatrix}\]同时，也可以用以下公式定义$L$：
\[L_{i,j} = \begin{cases} deg(v_i), & if \ i=j &\\ -1, & if \ i≠j \ and \ v_i \ is \ adjacent \ to \ v_j &\\ 0, & otherwise\\ \end{cases}\]显然，拉普拉斯矩阵都是对称的。此外，另外一种更为常用的拉普拉斯矩阵形式是归一化的拉普拉斯矩阵（Symmetric normalized Laplacian），定义为：
\[L^{sym} := D^{-1/2}LD^{-1/2} = I - D^{-1/2}AD^{-1/2} = UΛU^{T}\]该矩阵中的元素由下面的式子给出：
\[\begin{cases} L_{i,j}^{sym} = 1, & if \ i=j \ and \ deg(v_i)≠0 &\\ -\frac{1}{\sqrt{deg(v_i)deg(v_j)}}, & if \ i≠j \ and \ v_i \ is \ adjacent \ to \ v_j &\\ 0, & otherwise\\ \end{cases}\]其中，$U$是图的拉普拉斯矩阵L的特征向量矩阵。$Λ$是拉普拉斯矩阵$L$的特征值组成的对角矩阵，$U^{T}$是$U$的转置。
为什么GCN要用拉普拉斯矩阵？这是因为拉普拉斯矩阵具有很多良好的性质，这里举例三个与GCN有关的点：
- 拉普拉斯矩阵是对称矩阵，可以进行特征分解(谱分解)，这就和GCN的spectral domain对应上了；
- 拉普拉斯矩阵只在中心顶点和一阶相连的顶点上(1-hop neighbor)有非0元素，其余之处均为0；
- 通过拉普拉斯算子与拉普拉斯矩阵进行类比。
拉普拉斯矩阵的谱分解（特征分解）
GCN的核心基于拉普拉斯矩阵的谱分解，阵的谱分解，特征分解，对角化都是同一个概念。
不是所有的矩阵都可以特征分解，其充要条件为n阶方阵存在n个线性无关的特征向量。
但是拉普拉斯矩阵是半正定对称矩阵（半正定矩阵本身就是对称矩阵，此处这样写为了和下面的性质对应，避免混淆），有如下三个性质：
- 对称矩阵一定n个线性无关的特征向量
- 半正定矩阵的特征值一定非负
- 对阵矩阵的特征向量相互正交，即所有特征向量构成的矩阵为正交矩阵。
逆矩阵
逆矩阵（inverse matrix），又称反矩阵。在线性代数中，给定一个n阶方阵$A$，若存在一n阶矩阵$B$，使得$AB=BA=I_n$，其中$I_n$为n阶单位矩阵，则称A是可逆的，且B是A的逆矩阵，记作$A^{-1}$
只有方阵（n×n的矩阵）才可能有逆矩阵。若方阵 $A$的逆矩阵存在，则称 $A$为非奇异方阵或可逆方阵。
单位矩阵
在线性代数中， $n$阶单位矩阵，是一个$n×n$的方形矩阵，其主对角线元素为1，其余元素为0。单位矩阵以 $I_n$表示；如果阶数可忽略，或可由前后文确定的话，也可简记为$I$（或者E）
\[I_1 = \begin{bmatrix} 1 \end{bmatrix}, I_2 = \begin{bmatrix} 1&0\\\\0&1 \end{bmatrix}, I_3 = \begin{bmatrix} 1&0&0\\\\0&1&0\\\\0&0&1 \end{bmatrix}, ...., I_n = \begin{bmatrix} 1&0&..&0 \\\\ 0&1&..&0 \\\\ ..&..&..&.. \\\\ 0&0&..&1 \end{bmatrix}\]特征分解
特征值与特征向量的基础理论
特征分解（Eigendecomposition），又称谱分解（Spectral decomposition）是将矩阵分解为由其特征值和特征向量表示的矩阵之积的方法。需要注意只有对可对角化矩阵才可以施以特征分解。
$N$维非零向量$v$是$N×N$的矩阵$A$的特征向量，当且仅当下式成立： $Av$ = λ$v$
其中 λ 为一标量，称为 $v$ 对应的特征值。也称 $v$ 为特征值 λ 对应的特征向量。也即特征向量被施以线性变换 $A$只会使向量伸长或缩短而其方向不被改变。
由上式可得： \(p(λ) := det(A-λI) = 0\)
称多项式 p(λ) 为矩阵的特征多项式。上式亦称为矩阵的特征方程。特征多项式是关于未知数 λ 的 N 次多项式。由代数基本定理，特征方程有 N 个解。这些解的解集也就是特征值的集合，有时也称为“谱”（Spectrum）。
我们可以对多项式 p 进行因式分解，而得到
\[p(λ) = (λ-λ_1)^{n_1}(λ-λ_2)^{n_2}...(λ-λ_k)^{n_k}=0\]其中： \(\sum_{i=1}^{k} n_i = N\)
对每一个特征值 λi ，都有下式成立： \((A-λ_{i}I)v=0\)
矩阵的特征分解
另A是一个N×N的方阵，且有N个线性独立的特征向量\(q_i(i=1,2....,N)\)。这样，A就可以被分解为： \(A = QΛQ^{-1}\)
其中$Q$是$N×N$方阵，且其第i列为$A$的特征向量$q_i$。$Λ$是对角矩阵，其对角线上的元素为对应的特征值，也就是$Λ_{ii}=λ_i$。这里需要注意只有可对角化矩阵才可以作特征分解
一般来说，特征向量$q_i(i=1,2….,N$)一般被单位化
哈达玛积(Hadamard product)
哈达玛积(Hadamard product)是矩阵的一类运算，若$A=(a_{ij})$和$B=(b_{ij})$是两个同阶矩阵，若$c_{ij}=a_{ij}×b_{ij}$,则称矩阵$C=(c_{ij})$为$A$和$B$的哈达玛积，或称基本积。
设定A,B∈C^{m×n}且A=(a_{ij}),B=(b_{ij})，称$m×n$矩阵为矩阵A和矩阵B的哈达玛积，记作A⊙B
\[A = \begin{bmatrix} a_{11}&a_{12}&...&a_{1n} \\\\ a_{21}&a_{22}&...&a_{2n} \\\\ .&.&...&. \\\\ .&.&...&. \\\\ a_{m1}&a_{m2}&...&a_{mn} \end{bmatrix}, B = \begin{bmatrix} b_{11}&b_{12}&...&b_{1n} \\\\ b_{21}&b_{22}&...&b_{2n} \\\\ .&.&...&. \\\\ .&.&...&. \\\\ b_{m1}&b_{m2}&...&b_{mn} \end{bmatrix}, A⊙B = \begin{bmatrix} a_{11}b_{11}&a_{12}b_{12}&...&a_{1n}b_{1n} \\\\ a_{21}b_{21}&a_{22}b_{22}&...&a_{2n}b_{2n} \\\\ .&.&...&. \\\\ .&.&...&. \\\\ a_{m1}b_{m1}&a_{m2}b_{m2}&...&a_{mn}b_{mn} \end{bmatrix}\]Chebyshev多项式
第一类Chebyshev多项式，由递推式 \(T_0(x)=1,T_1(x)=x,T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)\) 所确立的一系列多项式称为第一类Chebyshev多项式
第二类Chebyshev多项式，由递推式 \(U_0(x) = 1, U_1(x) = 2x,U_{n+1}(x) = 2xU_n(x)-U_{n-1}(x)\)
第一类Chebyshev多项式的相关简单性质
\[T_n(x)= cos(n*arccosx), -1 ≤ x ≤ 1\]由此可得到以下性质：
性质1：$ T_n(cosθ) = cosnθ$
由性质1可递推归纳得到:
性质2：Chebyshev多项式$T_n(x)$是n次代数多项式。
性质3：Chebyshev多项式$T_n(x)$的最高次幂项$x^n$的系数为$2^{n-1}$
性质4：$|x|≤1$时有$|T_n(x)|≤1$(由性质1得出)