深入浅出图神经网络|GNN原理解析☄学习笔记（一）图的概述-蒲公英云

深入浅出图神经网络|GNN原理解析☄学习笔记（一）图的概述

《深入浅出图神经网络》GNN原理解析☄学习笔记（一）图的概述

文章目录

- 《深入浅出图神经网络》GNN原理解析☄学习笔记（一）图的概述
- - 图的基本定义
  - - 图的基本类型
    - 邻居和度
    - 子图与路径
  - 图的存储与遍历
  - - 邻接矩阵和关联矩阵
    - 图的遍历
  - 图数据的应用场景
  - - 图数据类别
    - 图数据的应用场景
  - 图数据任务分类

图的基本定义

普遍表示如下，其中V(Vertex)表示顶点集，E(Edge)表示边集。通常用n表示顶点数，m表示边数。
G = ( V , E ) G=(V,E) G=(V,E)

一条连接顶点 v i ， v j ∈ V 的边记为 ( v i , v j ) 或者 e i j 一条连接顶点v_i，v_j∈V的边记为(v_i,v_j)或者e_{ij} 一条连接顶点vi，vj∈V的边记为(vi,vj)或者eij

图的基本类型

有向图和无向图
非加权图与加权图
连通图与非连通图
二部图，也称为二分图，如作者与论文、演员与电影

邻居和度

v i 的所有邻居为集合 N ( v i ) ，即 N ( v i ) = { v j ∣ e i j ∈ E , e j i ∈ E } v_i的所有邻居为集合N(v_i)，即N(v_i)=\{v_j|e_{ij}∈E , e_{ji}∈E\} vi的所有邻居为集合N(vi)，即N(vi)={ vj∣eij∈E,eji∈E}

以 v i 为端点的边的数目称为 v i 的度，记为 d e g ( v i ) = ∣ N ( v i ) ∣ 以v_i为端点的边的数目称为v_i的度，记为deg(v_i)=|N(v_i)| 以vi为端点的边的数目称为vi的度，记为deg(vi)=∣N(vi)∣

出度（Outdegree），入度（Indegree）

子图与路径

子图（Subgraph）
路径的长度： L ( P i j ) = ∣ P i j ∣ 路径的长度：L(P_{ij})=|P_{ij}| 路径的长度：L(Pij)=∣Pij∣

顶点的距离： d ( v i , v j ) = m i n ( ∣ P i j ∣ ) 顶点的距离：d(v_i,v_j)=min(|P_{ij}|) 顶点的距离：d(vi,vj)=min(∣Pij∣)

k 阶邻居：若 d ( v i , v j ) = k , 我们称 v j 为 v i 的 k 阶邻居 k阶邻居：若d(v_i,v_j)=k,我们称v_j为v_i的k阶邻居 k阶邻居：若d(vi,vj)=k,我们称vj为vi的k阶邻居

k 阶子图（ k − s u b g r a p h ）：一个顶点与它的小于等于 k 阶的邻居和边组成的子图 k阶子图（k-subgraph）：一个顶点与它的小于等于k阶的邻居和边组成的子图 k阶子图（k−subgraph）：一个顶点与它的小于等于k阶的邻居和边组成的子图

在这里插入图片描述

图的存储与遍历

邻接矩阵和关联矩阵

邻接矩阵（Adjacency matrix）：一个一维数组表示顶点集合，一个二维数组（v,v）表示邻接矩阵。

关联矩阵（Incidence matrix）：两个一维数组分别表示顶点集合和边集合，一个二维数组(v, e)表示关联矩阵。

在这里插入图片描述

图的遍历

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

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

详细算法见往期博客图论（graph）相关算法总结，内有详细示例和代码，此处不赘述。

图数据的应用场景

在实际的数据场景中，通常将图称为网络（Network），顶点和边分别称为节点（Node）和关系（Link）。

图数据类别

同构图（Homogeneous Graph）：图中的节点类型和关系类型都仅有一种，如万维网
异构图（Heterogeneous Graph）：图中的节点类型和关系类型多于一种
属性图（Property Graph）：相较于异构图，属性图中节点和关系都有标签（Label）和属性（Property）
非显式图（Graph Constructed from Non-relational Data）：数据之间没有显式地定义出关系，需要依据某种规则或计算方式将数据的关系表达出来，进而将数据当成一种图数据进行研究。