一、图的表示
定义一（图）
图包含节点和边，其中，节点表示实体，边表示实体间的关系。
节点和边的信息可以是类别型的——标签，也可以是数值型的——属性。
定义二（图的邻接矩阵）
分三种情况：
1.无向图：无向图的邻接矩阵是对称的。
2.无权图：各条边的权重被认为是等价的，即认为各条边的权重为。
3.有权图：对应的邻接矩阵通常被记为：
若边不存在时，边的权重为
二、图的属性
1.结点的度（degree）
- 对于有向有权图，结点
的出度等于从
- 无向图是有向图的特殊情况，结点的出度与入度相等。
- 无权图是有权图的特殊情况，各边的权重为
，那么结点
结点，入度记为
，出度记为
。
2.邻接结点（neighbors）
- 结点
- 结点
跳远的邻接节点指的是到结点
跳远的邻接节点包含了自身）。
3.行走（walk）
，这是一次“行走”，它是一次从节点
出发，依次经过边
，最终到达节点
的“行走”。
在“行走”中，节点是运行重复的。
4.路径（path）
“路径”是结点不可重复的“行走”。
5.子图（subgraph）
6.连通分量（connected component）
给定图是图
的子图。记属于图
但不属于
图的结点集合记为
。如果属于子图中的任意结点对之间存在至少一条路径，但不存在一条边连接属于子图的结点与属于这个集合的结点，那么图
是图
的连通分量。
7.连通图（connected graph）
当一个图只包含一个连通分量，即其自身，那么该图是一个连通图。
8.最短路径（shortest path）
结点对之间的最短路径。
9.直径（diameter）
给定一个连通图，其直径为其所有结点对之间的最短路径的最小值。
10.拉普拉斯矩阵（Laplacian Matrix）
给定一个图
其邻接矩阵为
11.对称归一化的拉普拉斯矩阵（Symmetric normalized Laplacian）
三、图的种类
- 同质图（Homogeneous Graph）：只有一种类型的节点和一种类型的边的图。
- 异质图（Heterogeneous Graph）：存在多种类型的节点和多种类型的边的图。
- 二部图（Bipartite Graphs）：节点分为两类，只有不同类的节点之间存在边。
四、图结构数据上的机器学习
1.节点预测：预测节点的类别或某类属性的取值
例子：对是否是潜在客户分类、对游戏玩家的消费能力做预测
2.边预测：预测两个节点间是否存在链接
例子：Knowledge graph completion、好友推荐、商品推荐
3.图的预测：对不同的图进行分类或预测图的属性
例子：分子属性预测
4.节点聚类：检测节点是否形成一个社区
例子：社交圈检测
5.其他任务
图生成：例如药物发现
图演变：例如物理模拟
五、应用神经网络于图面临的挑战
过去的深度学习应用中，我们主要接触的数据形式主要是这四种：矩阵、张量、序列（sequence）和时间序列（time series），它们都是规则的结构化的数据。然而图数据是非规则的非结构化的，它具有以下的特点：
- 任意的大小和复杂的拓扑结构；
- 没有固定的结点排序或参考点；
- 通常是动态的，并具有多模态的特征；
- 图的信息并非只蕴含在节点信息和边的信息中，图的信息还包括了图的拓扑结构。
以往的深度学习技术是为规则且结构化的数据设计的，无法直接用于图数据。应用于图数据的神经网络，要求 - 适用于不同度的节点；
- 节点表征的计算与邻接节点的排序无关；
- 不但能够根据节点信息、邻接节点的信息和边的信息计算节点表征，还能根据图拓扑结构计算节点表征。
