1. 图的基本概念

        对于接触过数据结构和算法的读者来说，图并不是一个陌生的概念。一个图由一些顶点也称为节点和连接这些顶点的边组成。给定一个图G=(V,E),  其 中V={V1,V2,…,Vn}  是一个具有 n 个顶点的集合。

1.1邻接矩阵

        我们用邻接矩阵A∈Rn×n表示顶点之间的连接关系。 如果顶点 vi和vj之间有连接，就表示(vi,vj)  组成了一条边(vi,vj)∈E, 那么对应的邻接矩阵的元素Aij=1,否则Aij=0。邻接矩阵的对角线元素通常设0。

1.2顶点的度

        一个顶点的度指的是与该顶点连接的边的总数。我们用d(v) 表 示顶点v的度，则顶点的度和边之间有关系：所有顶点的度之和是边的数目的2倍。

1.3度矩阵

        图 G 的度矩阵D是一个n×n的对角阵，对角线上的元素是对应顶点的度：

1.4 路径

        与数据结构的路径一样。

1.5距离

        如果从顶点u到顶点v的最短路径存在，则这条最短路径的长度称为顶点u 和顶点v 之间的距离。如果u 和 v 之间不存在路径，则距离为无穷大。

1.6邻居节点

        如果顶点vi和vj之间有边相连，则vi和vj互为邻接点, vi的邻接点集合写作Nvi 或N(vi)。如果vi到vj的距离为K, 则称vi为vj的K阶邻居节点。

1.7权重图

        如果图里的边不仅表示连接关系，而且具有表示连接强弱的权重，则这个图被称为权重图。在权重图中，邻接矩阵的元素不再是0,1,而可以是任意实数 Aij∈R。顶点的度也相对应地变为与该顶点连接的边的权重的和。由于非邻接点的权重为0,所以顶点的度也等价于邻接矩阵A对应行的元素的和。

1.8有向图

        如果一个图的每个边都有一个方向，则称这个图为有向图,反之则称为无向图。在有向图中，从顶点u 到 v 的边和从v 到 u 的边是两条不同的边。反映在邻接矩阵中，有向图的邻接矩阵通常是非对称的，而无向图的邻接矩阵一定是对称的Aij=Aji。

1.9图的遍历

        从图的某个顶点出发，沿着图中的边访问每个顶点且只访问一次，这叫作图的遍历。图的遍历一般有两种：深度优先搜索和宽度优先搜索。

1.10图的同构

        图的同构指的是两个图完全等价。两个图G=(V,E)  和图G¹=(V',E')   是同构的，当且仅当存在从V到V '的一 一映射 f, 使得对于任意的(u,v)∈E都有(f(u),f(v))∈E'。

2.简易图谱论

2.1 拉普拉斯矩阵

对于一个有n个顶点的图G, 它的拉普拉斯矩阵定义为L=D-A，其中，D 是图G的度矩阵，A是图G的邻接矩阵。L 中的元素可以定义为

通常，我们需要将拉普拉斯矩阵进行归一化。常用的有两种方式。

(1)对称归一化的拉普拉斯矩阵，公式省略

(2)随机游走归一化的拉普拉斯矩阵，公式省略

拉普拉斯矩阵如图所示：

拉普拉斯矩阵的性质如下：

（1）L  是对称的

（2) L是半正定矩阵(每个特征值λi≥0)

  (3) L的每一行每一列的和都是0

  (4)L 的最小特征值为0

2.2 拉普拉斯二次型

        拉普拉斯矩阵是半正定矩阵，这就意味着对任意一个n维非0向量z,zT（转置）Lz≥0 。  式子展开后为：

(2.1)

        di 是度矩阵D 的对角元素，di=d(vi)=1Ai j 。为了区分A中的边和非边元素，我们用wi j 表示 vi与vj连接时它们之间的权重。很显然，这个大于等于0的，所以L是半正定的。

        式(2.1)被称为拉普拉斯二次型，如果我们把z看作分布在一个图的各个顶点上的一个函数(或者信号),zTLz 则表示这个函数z的光滑程度。如果它的值很小，则说明z从一个顶点到另一个邻接点的 变化并不会很大。拉普拉斯二次型被广泛应用于机器学习领域，其中一个很常见的例子就是在半监督学习中作为正则项。除此之外，在图切分、 谱聚类、图稀疏化等应用中都发挥着重要作用。

2.3拉普拉斯矩阵与图扩散

        拉普拉斯矩阵的另一个重要作用是作为图上的离散拉普拉斯算子。假设在图上模拟一个热扩散的过程，φ(t)是图上每个顶点的热量分布，热量传播的速度和顶点之间的热量差成正比(根据冷却定律),于是在点vi 上这个扩散过程可以表示为：

        其中，δi j是一个指示变量，如果i=j, 则δi j=1, 否则δij=0。写成整个图 上的矩阵形式，可以得到（2.3），对比热传播方程

可知，-L 在式(2.3)中相当于拉普拉斯算子△(欧氏空间的二阶微分算子),所以L才被叫作(图)拉普拉斯矩阵。

2.4 图论傅里叶变换

        图论傅里叶变换将离散傅里叶转换延伸到处理图上的信号，它已经成为图信号分析的一个基础工具。简单地讲，图论傅 里叶变换就是基于图拉普拉斯矩阵将图信号从空域(顶点上)f(t) 转换到谱域 (频域)F(w) 的一种方法。那么如何把傅里叶变换迁移到图上呢?很自然地，我们把拉普拉斯算子的特征函数换成拉普拉斯矩阵的特征向量即可。

        对于一个n 个顶点的图G,  我们可以考虑将它的拉普拉斯矩阵L作为傅里叶变换中的拉普拉斯算子。因为L是实对称矩阵，可以进行如下所示的特征分解：L=UAU-¹（-1）=UAUT（转置）

其中，U 是一个正交化的特征向量矩阵UUT（转置）=UT（转置）U=I,A （没有中间的那一横）是特征值的对角阵 。U提供了一个图上完全正交的基底，图上的任意一个向量f 都可以表示成U中特征向量的线性组合：

其中，uL是 U 的第L个列向量，也是对应特征值λL的特征向量。如果我们用 这些特征向量替代原来傅里叶变换式中的基底，把原来的时域变为顶点上的空域，那么图上的傅里叶变换就变成

其中，λ表示第L个特征值，f(i)对应第i个节点上的特征，u(i)表示特征向量ul的第i个元素。推广到矩阵形式就是UT(转置）f。

图信号：定义在图的所有顶点上的信号φ:V→Rn。 可以将图信号当成一个n 维的向量φ∈Rn, 其中φi对应顶点vi上的值。

图论傅里叶变换：对于一个图信号φ^,图论傅里叶变换定义为φ=U-1（上标) φ=UTφ。

图论傅里叶逆变换：对于一个谱域上的图信号p,图论傅里叶逆变换定 义为Uφ^。

        很容易发现，图论傅里叶变换实际上和式是对应的，它本质上就是将一个向量变换到以拉普拉斯矩阵的特征向量为基底的新的空间中，这个空间也就是我们所说的谱域。图论傅里叶变换是可逆的，即Uφ^=UU-¹φ=φ。

        图论傅里叶变换为图信号在谱域上的处理提供了一个工具。在谱域上，我们可以定义各种图上的信号过滤器，并延伸到定义图上的卷积操作。