1、图基础知识介绍
1、 图基础知识
1.1 图的定义
1.1.1 图的组成
图由两个元素组成：节点和关系
每个节点代表一个实体（人、地、事物、类别或其他数据），每个关系代表两个节点的关联方式
1.1.2 图论中的数学符号含义
D:度矩阵
A：邻接矩阵
W：变换矩阵（主要用于将输入特征映射到输出特征）
H：特征矩阵
N(i)：节点i的邻居节点集合
对邻居结点的操作是通过邻接矩阵乘以特征矩阵实现的。比如：
对邻居求和：A*H
对邻居求平均mean（A）* H
对邻居做max-pooling: max（A*H）
1.1.3 图的表示
一个图可以定义为G =（V，E），V表示图中的节点集合，E是边的集合，E中的每条边e=(v,w),v和w都是V中的顶点
子图：V和E的子集
赋权图：带权重的图
1.2 图的分类
无向图：两个顶点之间的边没有方向
有向图：两个顶点之间的边有方向
同构图：图中的节点类型和关系类型仅有一种
异构图：图数据对象是多类型的，交互关系也是多样化的
属性图：相比较于异构图，图数据增加了额外的属性信息
非显示图：数据之间没有显示地定义出关系，需要依据某种规则或者计算方式将数据的关系表达出来
时空图：时空图是一种特征矩阵 X 随时间变换的图
二部图（二分图）：可以分为两部分，且内部无边
1.3 度degree
1）对于无向图，顶点v的度是指和v相关联的边的数目。
2）对于有向图，以顶点v为头的边的数目称为v的入度
1.3.1 节点重要性指标
网络中一个节点的价值首先取决于这个节点在网络中所处的位置，位置越中心其价值越大。在社会网络分析中，常用”中心性“来表示。最直接的度量是度中心性，即一个节点的度越大就意味着这个节点越重要
1）度中心性(Node Centrality)
2）介数重要度(Betweennness Centrality)
3）接近中心性(Closeness Centrality)
4）特征向量重要度(Eigenvector Centrality)
1.4 连接关系表示
1.4.1 邻接矩阵
邻接矩阵表示顶点间关系，是n阶方阵（n为顶点数量）。邻接矩阵分为有向图邻接矩阵和无向图邻接矩阵。无向图邻接矩阵是对称矩阵，而有向图的邻接矩阵不一定对称。顶点之间有连接关系的在矩阵对应位置值为1。
1.4.2 度矩阵
度矩阵是对角阵，对角上的元素为各个顶点的度。顶点Vi的度表示和该点相关联的边的数量。
1.4.3 关联矩阵
关联矩阵用一个矩阵来表示各个点和每条边之间的关系。
对于一个无向图G，bij表示在关联矩阵中点i和j之间的关系，若两点是相连的，则bij=1。列是边，行是点。每一行值的总和为该点的度,每一列的和为2
1.4.4 连接列表和邻接列表
1）邻接列表
左边节点连接右边所有节点，例如下面显示的连接关系，左节点与右面所有节点相连
1: 2，3
2：1，5，6
2）连接列表
两个列表，左边连接右边，或者上面连接下面
总结：邻接列表比连接列表占用空间更少
1.4.5 拉普拉斯矩阵(Laplacian matrix)
1）概述
也称为导纳矩阵、基尔霍夫矩阵或离散拉普拉斯算子
主要应用在图论中，作为一个图的矩阵表示。
表示为：L = D - A，也可以写作
下面的图对应公式
1.5 连通图和非连通图
连通图：对于一个无向图，如果任意的节点能够通过一些边到达节点，则称为连通图
非连通图：有至少一个点无法连接上的叫非连通图
1.6 连通分量
无向图G的一个极大连通子图称为G的一个连通分量（或称连通分支）。
连通图只有一个连通分量
非连通的无向图有多个连通分量
1.7 连通性
强连通图：给定有向图G=（VE），并且给定该图G中的任意两个节点u和v，如果节点u与v相互可达，及至少存在一条路径可以由节点u开始，到节点v终止，同时至少存在一条路径可以由节点v开始，
弱连通图：至少有一对节点不满足单向连通，但去掉边的方向后从无向图的观点看是连通图，则称为弱连通图
1.8 图直径
任意两个顶点之间距离的最大值
1.9 周期性图和非周期性图
假设k是一个大于1的自然数，如果从有向图的一个结点出发返回到这个结点的路径的长度都是k的倍数，那么称这个结点为周期性结点。 如果一个有向图不含有周期性结点，则称这个有向图为非周期性图 （aperiodic graph），否则为周期性图。
1.10 图的遍历（graph Travelsal）
从图的顶点出发，沿着图中的边访问每个顶点且只访问一次。
两种方式：深度优先搜索和广度优先搜索
1.10.1 深度优先搜索：是一个递归算法，有回退过程。
1.10.2 广度优先搜索
2、数据域（欧几里得数据与非欧几里得数据）
2.1 欧几里得数据
一类具有平移不变形的数据。常见这类数据有图像、文本、语言。
2.1.1 特点
- 图像中的平移不变性：即不管图像中的目标被移动到图片的哪个位置，得到的结果（标签）应该相同的。
-
卷积被定义为不同位置的特征检测器。
2.2 非欧几里得数据
一类不具有平移不变性的数据。这类数据以其中的一个为节点，其邻居节点的数量可能不同。常见这类数据有知识图谱、社交网络、化学分子结构等等。
不具备平移不变性，不能利用卷积核去提取相同的结构信息，所以卷积神经网络对于这类数据无能为力。所以衍生出了处理这类数据的网络，即图神经网络。
3、超图（Hypergraph）
3.1 定义
我们所熟悉的图，它的一条边（edge）只能连接两个顶点（vertice）；
超图是对图的概括，其中一条边可以连接任意数量的顶点。
人们定义它的一条边（hyperedge）可以和任意个数的顶点连接。图与超图的对比示意图如下
3.2 k-均匀超图（k-uniform hypergraph）
从超图中引申出来的一个概念就是k-均匀超图（k-uniform hypergraph），它是指超图的每条边连接的顶点数相同，个数都为k。其中的2-均匀超图就是我们平常所见到的传统意义上的图。所以图是超图的一种特殊类型。
4、空域、谱域、时域、频域
4.1 时域（time domain）
自变量是时间,即横轴是时间,纵轴是信号的变化。其动态信号x（t）是描述信号在不同时刻取值的函数。
4.2 频域（frequency domain）
任何一个波形都可以分解成多个正弦波之和。每个正弦波都有自己的频率和振幅。所以任意一个波形信号有自己的频率和振幅的集合。频率域就是空间域经过傅立叶变换的信号
自变量是频率,即横轴是频率,纵轴是该频率信号的幅度,也就是通常说的频谱图。
4.3 空域（spatial domain）
- 定义： 空域指的是数据的原始表示，通常是在数据的自然坐标系统中进行处理。
- 特点： 在空域中，数据表示为其直接的空间坐标或像素值。对于图像而言，空域处理是基于图像的像素级别进行的
- 信号中，指将信号转换为空间坐标的域，通过对空间坐标的分析来研究信号的空间特性。在空域中，信号可以表示为在不同空间位置上的强度。
- 像素域中，在空域的处理就是在像素级的处理，如在像素级的图像叠加。通过傅立叶变换后，得到的是图像的频谱。表示图像的能量梯度
4.4 谱域（spectral domain）
- 定义： 谱域指的是将数据表示为频率成分的集合，通过变换将信号从时间或空间域转换到频率域。
- 特点： 在谱域中，信号的特征通过频率表示，而不再是在原始的空间坐标中。傅里叶变换是常用的将信号从空域转换到谱域的方法。
4.5 谱域和频域的区别
- 谱域是对函数进行空间维度的傅氏变换
- 频域是对函数进行时间维度的傅氏变换
5、图数据的应用
5.1 图比较：确定两图之间的相似度
传统方法：基于集合的，基于子图的，基于核的算法
5.2 图分类
主要有两类：顶点分类和整图分类
5.3 链接预测
5.4 图聚类：边的结构最主要
分组的原则为：在形成的簇内部有许多边，而簇之间的边相对就少一些
主要有两类图聚类方法：图内聚类和图间聚类方法
6、表示学习
从数据中得到判别性特征的方法，减少机器学习算法对特征工程的依赖
目标
学习到一个映射：f：X→R^d，将输入映射到一个稠密的低维向量空间
6.1 表示学习分类
1）离散表示与分布式表示
离散表示：one-hot编码，词袋模型就是以此为基础构架
分布式表示：RGB表示颜色的方法
2）端到端的表示学习方法
3）基于重构损失的方法
4）基于对比损失的方法
6.2 自编码器-基于重构的方法（Auto-Encoder）
6.2.1 介绍
自编码器是一种表示学习模型，以输入数据为参考，是一种无监督学习模型，可以用于数据降维和特征提取。将输入映射到某个特征空间，再从这个特征空间映射回输入空间进行重构。训练完成后，使用编码器进行特征提取。
encoder 编码器：输入数据提取特征
decoder解码器：基于提取的特征重构出输入数据
从上图可以看出，自编码器模型主要由编码器（Encoder）和解码器（Decoder）组成，其主要目的是将输入x转换成中间变量y，然后再将y转换成x_，然后对比输入x和输出x_，使得他们两个无限接近。
6.2.2 自编码器分类
两大类：欠完备自编码器和过完备自编码器
2.2.1 欠完备自编码器
输入x，隐藏层状态h，输出为x~
限定 h 的维度比 x 小，符合这种条件的称为欠完备自编码器
2.2.2过完备自编码器
当编码器的维度大于输入维度，称为过完备自编码器
这种编码器必须增加限制，否则学不到任何有用的信息
常用的方法为增加正则化约束，下面介绍几种常见的正则化编码器
6.2.3 去噪自编码器
改进之处在于原始输入的基础上加入噪声，迫使编码器不能简单学习恒等变换，必须从加噪声的数据中提取出有用信息用于恢复数据
具体做法是随机将一些输入置为0，得到了加入噪声的输入x作为编码器的输入，解构出不带噪声的数据x，损失函数为
6.2.4 稀疏自编码器
除在输入加噪声，在损失函数上加正则项使得模型学习到有用的特征
以限制神经元的活跃度来约束模型，尽可能使大部分神经元不活跃
6.2.5 变分自编码器 VAE（Variational Auto-Encoder）
2.5.1 VAE概述
原理：本质是生成模型
目标：建模样本的分布P(x)，训练完成后，使用解码器生成样本
VAE变分自动编码器作为AE的变体，它主要的变动是对编码(code)的生成上。编码(code)不再像AE中是唯一映射的，而是具有某种分布，使得编码(code)在某范围内波动时都可产生对应输出。
2.5.2 为什么需要VAE
传统的AE只能生成 similar image
2.5.3 原理
在编码过程中，增加一些限制，迫使生成的隐向量能够粗略遵循一个标准正态分布（一般遵循高斯分布）
2.5.4 损失函数
2.5.5 编码过程
2.5.6 与自编码器相比
- AE是一种无监督的表示学习方法，VAE是一种生成模型
- AE隐空间不连续
6.2.6 神经网络自编码器三大特点
1、自动编码器是数据相关的（data-specific 或 data-dependent），这意味着自动编码器只能压缩那些与训练数据类似的数据。例如人脸训练数据只能预测人脸相关，不能预测花草
2、自动编码器是有损的，意思是解压缩的输出与原来的输入相比是退化的
3、自动编码器是从数据样本中自动学习的，这意味着很容易对指定类的输入训练出一种特定的编码器，而不需要完成任何新工作。
6.2.7 自编码器的应用
2.7.1 特征降维
从直观上来看，自动编码器可以用于特征降维，类似主成分分析PCA，但是其相比PCA其性能更强，这是由于神经网络模型可以提取更有效的新特征
2.7.2 特征提取
自动编码器学习到的新特征可以送入有监督学习模型中，所以自动编码器可以起到特征提取器的作用
实例：图片的压缩及还原
为什么要进行压缩：1、保证输入图片的大小一致；2、减少输入数据，提取图片中最具代表性的特征
3、基于对比损失的方法-Word2vec
对比损失：构建正负样本，最大化正样本之间的相似度，最小化负样本之间的相似度
详细解释见NLP词嵌入章节
7、图信号处理（graph Signal Processing，GSP）
7.1 图信号基本定义
是离散信号处理（Discrete Signal Processing，DSP）在图信号领域的应用
图信号：给定图G=(V,E)，V表示图中的节点集合，假设其长度为N，图信号则是一种描述V→R的映射，表示成向量的形式：x=[x1,x2,···，xn]^T，其中xi表示的是节点vi上的信号强度。
蓝色代表信号强度，这里的图信号只有一个通道，实际的图节点可能有很多通道
7.2 图的拉普拉斯矩阵
7.2.1 概述
拉普拉斯特征映射（Laplacian Eigenmaps）是一种不太常见的降维算法，它看问题的角度和常见的降维算法不太相同，是从局部的角度去构建数据之间的关系
拉普拉斯特征映射是一种基于图的降维算法，它希望相互间有关系的点（在图中相连的点）在降维后的空间中尽可能的靠近，从而在降维后仍能保持原有的数据结构
7.2.2 拉普拉斯矩阵（Laplacian matrix)）定义
也称为基尔霍夫矩阵, 是表示图的一种矩阵。
给定一个有n个顶点的图G=（V，E） ，其拉普拉斯矩阵被定义为:L=D-W
其中，D是图G的度矩阵，A是图G的邻接矩阵。L中的元素可定义为
7.2.3 拉普拉斯矩阵归一化方式
1）对称归一化的拉普拉斯矩阵(Symmetric Normalized Laplacian Matrix)
2）对称归一化的拉普拉斯矩阵(Symmetric Normalized Laplacian Matrix)
7.2.4 性质
- L是对称的
- L是半正定矩阵（每个特征值λ i ≥ 0 ）
- L的每一行每一列的和为0
- L的最小特征值为0
7.2.5 示例
7.3 图傅里叶变换
3.1 目标
将图信号由空域视角转换到频域视角
待补充
7.4 图滤波器
7.4.1 定义
对给定图信号的频谱中各个频率分量的强度进行增强或衰减的操作
7.4.2 性质
- 线性关系
- 滤波操作是顺序无关的
- 如果h(λ)≠0，该滤波操作是可逆的
7.4.3 常见的滤波器
