图数据结构概述

图数据

一个广义上的图数据$G$可以用下式描述：

$$G=（U,V,E,I）$$

节点属性：$V=(v_1,v_2,\cdots ,v_n)$，$v_n$是每个节点的特征向量，$n$为节点数；

连接关系：$I\subseteq \{(x,y)\mid (x,y)\in V^2\wedge x\ne y\}$，使用邻接列表的方式描述连接关系，$x$和$y$是边两端的节点，且$x$和$y$不相等（不能与自身相连）；

$E$代表边属性，描述连接边的特征；$U$代表全局属性，描述整个图的特征。在某些情况下$E$、$U$可以不设置，此时的图数据简化为$G=(V,I)$，也就是只包含节点信息和连接关系，具体的选择和训练学习任务有关。

以乙酸分子为例说明二维分子结构的图表示方法：

为了描述节点的连接关系，有邻接矩阵和邻接列表两种方式：

1）邻接矩阵，如果用一个矩阵来表示图节点的连接关系，矩阵的行和列分别是节点索引。如果图包含$N$个节点，那么邻接矩阵大小就是$N\times N$，矩阵$\mathrm{第}(i,j)$个元素为$1$就表示节点$i$和节点$j$有连接。这种表示方法简单且直观，但是当图的节点数增加时，矩阵会变得非常稀疏，存在大量空间资源浪费，面对特别大量的节点时，图的邻接矩阵将难以计算。

2）邻接列表，如上文提到的连接集$I\subseteq \{(x,y)\mid (x,y)\in V^2\wedge x\ne y\}$就是邻接列表的表述形式，他只存储有连接关系的节点索引，连接$(i,j)$表述节点$i$和节点$j$相连。对于连接的方向，在有向图和无向图中有不同表述方法，在PyG和DGL库中都使用邻接列表来存储节点连接关系。

图的一些概念

边的方向性

无向边：边$(v_i,v_j)$与$(v_j,v_i)$等价，关系是双向的（如 “朋友关系”），对应的图称为无向图。

有向边：边$(v_i,v_j)$表示从$v_i$到$v_j$的单向关系（如 “关注”“引用”），对应的图称为有向图。

边的权重

边可以带有数值属性（如社交网络中 “互动频率”、交通网络中 “距离”），称为加权图；无权重的图称为无权图。

边的类型

边可以有语义类型（如知识图谱中 “父子”“属于” 等关系），对应的图称为异质图（节点也可能有不同类型）；边类型单一的图称为同质图。

节点的度

无向图中，节点$v_i$的度$d(v_i)$是与它相连的边的数量（如朋友数量）。有向图中，分为入度（指向该节点的边数）和出度（从该节点出发的边数）。

邻居

与节点$v_i$直接相连的节点称为其一阶邻居$N(v_i)$；邻居的邻居称为二阶邻居，以此类推。

路径

从节点$v_i$到$v_j$的一系列边组成的序列（如$v_i\to v_k\to v_j$），路径的长度是边的数量。

连通性

若图中任意两个节点之间都存在路径，则称为连通图；否则为非连通图，其中的最大连通子图称为连通分量。

子图

由原图的部分节点和边组成的图（需满足边的两个端点都在子图节点中），记为$G^{\prime }=(V^{\prime },E^{\prime })$，其中$V^{\prime }\subseteq V$，$E^{\prime }\subseteq E$。

图的应用领域

下面举一些图数据在不同领域的应用：