图机器学习基础知识

课程和PPT主页

图的基本概念

图（Graphs）是一种用于描述和分析具有关系或相互作用的实体的通用语言。

现实生活中存在很多种类型的图，例如：



广义的图主要可以分为两种：

• 网络，Networks(也称为自然图，Natural Graphs)：
  • 社交网络（Social networks）：社会是一个由70亿+个人组成的集合
  • 交流和交易网络（Communication and transactions）
  • 生物医学（Biomedicine）
  • 大脑连接网络（Brain connections）：我们的思想隐藏在数十亿个神经元之间的联系中
• 图（作为一种表示方式）
  • 信息/知识网络（Information/knowledge）
  • 软件（Software）
  • 相似性网络（Similarity networks）：连接类似的数据点
  • 关系结构（Relational structures）：分子，场景图，三维形状，基于粒子的物理模拟

不过在很多时候网络和图之间的区别是模糊的

现代机器学习

现代深度学习主要针对简单的序列（主要文本和音频）和网格数据（图片），即欧式数据。

但是主流的深度学习技术不能处理图数据（非欧式空间数据），下图左边。
非欧式空间数据特点为：

• 任意的大小和复杂的拓扑结构（即没有像网格这样的空间局部性）
• 无固定的节点排序或参考点
• 通常具有动态特性，并具有多模态特征
  

基于图的深度学习

图神经网络主要框架如下：

图表示学习

（类似降维操作，在低维空间中节点的表示会变得更加的紧凑。）

图机器学习的应用

图机器学习应用的任务主要可以分为以下四大类：

• 节点级任务常见的有：蛋白质折叠（Protein Folding）
• 边级任务常见的有：推荐系统（Recommender Systems），药物副作用检测（Drug side Effects）
• 子图级任务常见的有：交通预测（Traffic Prediction）
• 图级任务常见的有：药物发现（Drug Discovery）

典型的图机器学习的任务有：

• 节点分类（Node classification）：预测节点的属性
  • 对在线用户/项目进行分类
• 链接预测（Link prediction）：预测两个节点之间是否存在边。
  • 知识图完成情况
• 整图分类（Graph classification）： 对不同的图进行分类
  • 分子属性预测
• 聚类（Clustering）：检测节点是否形成了一个社区
  • 社交圈检测
• 图生成（Graph generation）：药物的发现
• 图演化（Graph evolution）：物理模拟

图的基础知识

图的构成

一个图主要由节点和边构成，有些图还会存在节点特征、变特征等组件。

一些常见的图：

图可分为有向图（Directed Graph）和无向图（Undirected Graph）：

图中有一个重要的概念-度：

二部图 Bipartite graph

折叠网络 “Folded” networks

图的表示

图可使用邻接矩阵进行表示，缺点是邻接矩阵通常是稀疏的。

图的第二种表示方法是使用“节点对”列表进行表示：

对于大图或者稀疏图一般使用邻接表进行表示：

节点和边的属性

节点和边的属性的可能有：

图加了节点和边的属性之后，可以表达更多的信息：

连通图和非连通图

具有多个连通分量的网络的邻接矩阵可以由分块对角线形式编写，因此非零元素被限制在正方形内，其他元素都为零。

强连通图和弱联通图

强连通分量：