Unit1 图的概述

1.1图的基本定义

基本类型：由顶点（Vertex）和边（Edge）构成；类型包含有向图和无向图，加权图（边有权重）和非加权图，连通图和非连通图（btw 书中1.4的图栗子就错了 无语.jpg）

度：顶点vi的度（Degree），记为deg（vi），有向图中的度是出入度之和

k阶邻居：Vi和Vj的距离（最短路径）为k（k条边），则Vi是Vj的k阶邻居

k阶子图：只能靠图（1.1）理解

1.1 绿色部分是顶点V1的2阶子图

1.2 图的存储与遍历

邻接矩阵（Adjacency matrix）：描述顶点之间的关联，通常用稀疏矩阵表示，且无向图是对称矩阵

关联矩阵（Incidence matrix）：描述顶点与边之间的关联，也可以用稀疏矩阵表示

图的遍历算法：

A. 深度优先搜索（DFS，Depth-First-Search）

B. 广度优先搜索（BFS，Breadth-First-Search）

以下图（1.2）为例，A的顺序是v1→v2→v4→v5→v3，B的顺序是v1→v2→v3→v4→v5

1.2 一个栗子

1.3 图数据的应用场景

1.3 图数据应用实例

图数据的四个类别：

A. 同构图（Homogeneous Graph）：指图中的节点类型和关系类型都仅有一种，如由超链接关系所构成的万维网（单纯的社交网络

B. 异构图（Heterogeneous Graph）：与同构图相反，指图中的节点类型或关系类型多于一种，更贴近现实

C. 属性图（Property Graph）：相较于异构图，给图数据增加了额外的属性信息，对于一个属性图而言，节点和关系都有标签（Label）和属性（Property），广泛适用于多种业务场景下的数据表达（电子购物）

D. 非显式图（Graph Constructed from Non-relational Data）：指数据之间没有显式地定义出关系，需要依据某种规则或计算方式将数据的关系表达出来，如计算机3D视觉中的点云数据

1.4 图数据深度学习

衍生一系列理论知识：图学习（Graph Learning）/谱图理论（Spectral Graph Theory）/统计关系学习（Statistical Relational Learning）/异构信息网络（Heterogeneous Information Network）/网络表示学习（Network Embedding）

图数据的任务分类：

A. 节点层面（Node Level）的任务：主要包括分类任务和回归任务。这类任务虽然是对节点层面的性质进行预测，但是不应该将模型建立在一个个单独的节点上，节点的关系也要考虑。包括学术上使用较多的对论文引用网络中的论文节点进行分类，工业界在线社交网络中用户标签的分类、恶意账户检测等。

B. 边层面（Link Level）的任务：包括边的分类和预测任务。边的分类是指对边的某种性质进行预测；边预测是指给定的两个节点之间是否会构成边。常见的应用场景比如在社交网络中，将用户作为节点，用户之间的关注关系建模为边，通过边预测实现社交用户的推荐。

C.图层面（Graph Level）的任务：图层面的任务不依赖于某个节点或者某条边的属性，而是从图的整体结构出发，实现分类、表示和生成等任务。目前，图层面的任务主要应用在自然科学研究领域，比如对药物分子的分类、酶的分类等。