图神经网络学习日记（一）图基础知识

图的定义

图由节点集合 \(\mathcal{V}\) 和边集合 \(\varepsilon\) 组成，记作 \(\mathcal{G}=(\mathcal{V},\varepsilon)\)，节点 \(u\in \mathcal{V}\) 到节点 \(v\in \mathcal{V}\) 的边表示为 \((u,v)\in\varepsilon\).

图的表示

图可以由邻接矩阵 \(A\in \mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|}\) 表示，矩阵的行和列代表节点索引，矩阵元素 \(A[u,v]\) 表示节点 \(u\) 和节点 \(v\) 的连接情况，如果 \((u,v)\in \varepsilon\)，则 \(A[u,v]=1\)，否则 \(A[u,v]=0\)。

多关系图的分类

异构图

异构图可以通过节点类型将节点划分为不相交的子集，即\(\mathcal{V} = \mathcal{V}_1 \bigcup \mathcal{V}_2 \bigcup \cdots \bigcup \mathcal{V}_k\)，其中\(\mathcal{V}_i \bigcap \mathcal{V}_j = \emptyset, \forall \neq j\)。

多重图

多重图中的边只能连接不同类型的节点，即\((u,\tau_i,v)\in \varepsilon \rightarrow u \in \mathcal{V}_j,v \in \mathcal{V}_k \bigwedge j \neq k\)。在多重图中，通常假设图可以被分解为\(k\)个层级，每个节点可以属于一层或多层，每层代表唯一特定关系，表示本层内边的类型。

图机器学习任务

节点预测

提供训练集真实的标签\(\mathcal{V}_{train} \subset \mathcal{V}\)时，通过所有的节点\(u \in \mathcal{V}\)预测标签\(y_u\)应该属于哪种类型、类别或属性。

节点预测可通过显式利用节点之间的连接进行分类，如下几种节点之间的连接性质：

同质性

图中的节点与其邻居节点的属性相似，即节点有与邻居节点共享属性的趋势。

异质性

假定节点将优先连接到具有不同标签的节点。

结构等价性

具有相似局部结构的节点将具有相似的标签。

节点预测是有监督还是半监督任务？

非标准的半监督任务。

在半监督学习中，模型训练过程同时使用有标签数据和无标签数据，标准的半监督学习以独立同分布假设为前提，标准的监督学习在训练过程中不使用所有无标签的测试数据。节点分类任务中，图中节点全部都被使用，包括无标签节点，故节点分类任务是半监督学习，同时节点分类任务对一组相互连接的节点进行建模，打破了独立同分布假设，故节点分类是非标准的半监督任务。

关系预测

给定一组节点 \(\mathcal{V}\) 和部分边的集合 \(\varepsilon_{train}\) （\(\varepsilon_{train} \subset \varepsilon, \varepsilon\) 表示全体边的集合），利用这些给定信息推断缺失边的集合 \((\varepsilon \textbackslash \varepsilon_{train})\)。

社区发现

通过输入一张图 \(\mathcal{G}=(\mathcal{V},\varepsilon)\) 推断出潜在的社区结构。

社区发现常被类比为图领域的无监督学习中的聚类任务。

图预测

图预测包括对整张图进行分类、回归与聚类。

图分类或图回归任务中，数据集由多张不同图构成，图机器学习算法针对每张图进行独立预测，而不是预测图的组成部分。在图聚类任务中，目标是学习一个无监督的测量图与图之间相似性的策略。

图分类与图回归任务属于标准监督学习范畴。