图神经网络task1

图神经网络task1

1 图神经网络简介

在过去的深度学习应用中,我们接触的数据形式主要是这四种:矩阵、张量、序列(sequence)和时间序列(time series)。然而来自现实世界应用的数据更多地是图的结构,如社交网络、交通网络、蛋白质与蛋白质相互作用网络、知识图谱和大脑网络等。图提供了一种通用的数据表示方法,众多其他类型的数据也可以转化为图的形式。此外,大量的现实世界的问题可以作为图上的一组小的计算任务来解决。推断节点属性、检测异常节点(如垃圾邮件发送者)、识别与疾病相关的基因、向病人推荐药物等,都可以概括为节点分类问题。推荐、药物副作用预测、药物与目标的相互作用识别和知识图谱的完成(knowledge graph completion)等,本质上都是边预测问题。

同一图的节点存在连接关系,这表明节点不是独立的。然而,传统的机器学习技术假设样本是独立且同分布的,因此传统机器学习方法不适用于图计算任务。图机器学习研究如何构建节点表征,节点表征要求同时包含节点自身的信息和节点邻接的信息,从而我们可以在节点表征上应用传统的分类技术实现节点分类。图机器学习成功的关键在于如何为节点构建表征。深度学习已经被证明在表征学习中具有强大的能力,它大大推动了计算机视觉、语音识别和自然语言处理等各个领域的发展。因此,将深度学习与图连接起来,利用神经网络来学习节点表征,将带来前所未有的机会。

然而,如何将神经网络应用于图,这一问题面临着巨大的挑战。首先,传统的深度学习是为规则且结构化的数据设计的,图像、文本、语音和时间序列等都是规则且结构化的数据。但图是不规则的,节点是无序的,节点可以有不同的邻居节点。其次,规则数据的结构信息是简单的,而图的结构信息是复杂的,特别是在考虑到各种类型的复杂图,它们的节点和边可以关联丰富的信息,这些丰富的信息无法被传统的深度学习方法捕获。

图深度学习是一个新兴的研究领域,它将深度学习技术与图数据连接起来,推动了现实中的图预测应用的发展。然而,此研究领域也面临着前所未有的挑战。

注:以上内容整理自“Deep Learning on Graphs: An Introduction”!!!

2 环境配置

在谷歌colab上搭建环境

!python -V

!nvcc --version

%%bash 

MINICONDA_INSTALLER_SCRIPT=Miniconda3-4.5.4-Linux-x86_64.sh
MINICONDA_PREFIX=/usr/local
wget https://repo.continuum.io/miniconda/$MINICONDA_INSTALLER_SCRIPT
chmod +x $MINICONDA_INSTALLER_SCRIPT
./$MINICONDA_INSTALLER_SCRIPT -b -f -p $MINICONDA_PREFIX

!which conda 

%%bash

conda install --channel defaults conda python=3.6 --yes
conda update --channel defaults --all --yes

import sys
_ = (sys.path
        .append("/usr/local/lib/python3.6/site-packages"))
        
sys.path

!conda install pytorch torchvision torchaudio cudatoolkit=11.1 -c pytorch -c nvidia

!python -c "import torch; print(torch.__version__)"

!python -c "import torch; print(torch.version.cuda)"

!source ~/.bashrc

!conda info -e 

!source activate

!pip install torch-scatter -f https://pytorch-geometric.com/whl/torch-1.8.0+cu111.html
!pip install torch-sparse -f https://pytorch-geometric.com/whl/torch-1.8.0+cu111.html
!pip install torch-cluster -f https://pytorch-geometric.com/whl/torch-1.8.0+cu111.html
!pip install torch-spline-conv -f https://pytorch-geometric.com/whl/torch-1.8.0+cu111.html
!pip install torch-geometric

3 简单图论

定义一(图)

  • 一个图被记为 G = { V , E } \mathcal{G}=\{\mathcal{V}, \mathcal{E}\} G={V,E},其中 V = { v 1 , … , v N } \mathcal{V}=\left\{v_{1}, \ldots, v_{N}\right\} V={v1​,…,vN​}是数量为 N = ∣ V ∣ N=|\mathcal{V}| N=∣V∣ 的结点的集合, E = { e 1 , … , e M } \mathcal{E}=\left\{e_{1}, \ldots, e_{M}\right\} E={e1​,…,eM​} 是数量为 M M M 的边的集合。
  • 图用节点表示实体(entities ),用边表示实体间的关系(relations)。
  • 节点和边的信息可以是类别型的(categorical),类别型数据的取值只能是哪一类别。一般称类别型的信息为标签(label)
  • 节点和边的信息可以是数值型的(numeric),类别型数据的取值范围为实数。一般称类别型的信息为属性(attribute)
  • 大部分情况中,节点含有信息,边可能含有信息。

定义二(图的邻接矩阵)

  • 给定一个图 G = { V , E } \mathcal{G}=\{\mathcal{V}, \mathcal{E}\} G={V,E},其对应的邻接矩阵被记为 A ∈ { 0 , 1 } N × N \mathbf{A} \in\{0,1\}^{N \times N} A∈{0,1}N×N。 A i , j = 1 \mathbf{A}_{i, j}=1 Ai,j​=1表示存在从结点 v i v_i vi​到 v j v_j vj​的边,反之表示不存在从结点 v i v_i vi​到 v j v_j vj​的边。

  • 无向图中,从结点 v i v_i vi​到 v j v_j vj​的边存在,意味着从结点 v j v_j vj​到 v i v_i vi​的边也存在。因而无向图的邻接矩阵是对称的

  • 无权图中,各条边的权重被认为是等价的,即认为各条边的权重为 1 1 1

  • 对于有权图,其对应的邻接矩阵通常被记为 W ∈ { 0 , 1 } N × N \mathbf{W} \in\{0,1\}^{N \times N} W∈{0,1}N×N,其中 W i , j = w i j \mathbf{W}_{i, j}=w_{ij} Wi,j​=wij​表示从结点 v i v_i vi​到 v j v_j vj​的边的权重。若边不存在时,边的权重为 0 0 0。

    一个无向无权图的例子:

    图神经网络task1

    其邻接矩阵为:
    A = ( 0 1 0 1 1 1 0 1 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 ) \mathbf{A}=\left(\begin{array}{lllll} 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \end{array}\right) A=⎝⎜⎜⎜⎜⎛​01011​10100​01001​10001​10110​⎠⎟⎟⎟⎟⎞​

图的属性

定义三(结点的度,degree)

  • 对于有向有权图,结点 v i v_i vi​的出度(out degree)等于从 v i v_i vi​出发的边的权重之和,结点 v i v_i vi​的入度(in degree)等于从连向 v i v_i vi​的边的权重之和。
  • 无向图是有向图的特殊情况,结点的出度与入度相等。
  • 无权图是有权图的特殊情况,各边的权重为 1 1 1,那么结点 v i v_i vi​的出度(out degree)等于从 v i v_i vi​出发的边的数量,结点 v i v_i vi​的入度(in degree)等于从连向 v i v_i vi​的边的数量。
  • 结点 v i v_i vi​的度记为 d ( v i ) d(v_i) d(vi​),入度记为 d i n ( v i ) d_{in}(v_i) din​(vi​),出度记为 d o u t ( v i ) d_{out}(v_i) dout​(vi​)。

定义四(邻接结点,neighbors)

  • 结点 v i v_i vi​的邻接结点为与结点 v i v_i vi​直接相连的结点,其被记为** N ( v i ) \mathcal{N(v_i)} N(vi​)**。
  • **结点 v i v_i vi​的 k k k跳远的邻接节点(neighbors with k k k-hop)**指的是到结点 v i v_i vi​要走 k k k步的节点(一个节点的 2 2 2跳远的邻接节点包含了自身)。

定义五(行走,walk)

  • w a l k ( v 1 , v 2 ) = ( v 1 , e 6 , e 5 , e 4 , e 1 , v 2 ) walk(v_1, v_2) = (v_1, e_6,e_5,e_4,e_1,v_2) walk(v1​,v2​)=(v1​,e6​,e5​,e4​,e1​,v2​),这是一次“行走”,它是一次从节点 v 1 v_1 v1​出发,依次经过边 e 6 , e 5 , e 4 , e 1 e_6,e_5,e_4,e_1 e6​,e5​,e4​,e1​,最终到达节点 v 2 v_2 v2​的“行走”。
  • 下图所示为 w a l k ( v 1 , v 2 ) = ( v 1 , e 6 , e 5 , e 4 , e 1 , v 2 ) walk(v_1, v_2) = (v_1, e_6,e_5,e_4,e_1,v_2) walk(v1​,v2​)=(v1​,e6​,e5​,e4​,e1​,v2​),其中红色数字标识了边的访问序号。
  • 在“行走”中,节点是运行重复的。
图神经网络task1

定理六

  • 有一图,其邻接矩阵为 A \mathbf{A} A, A n \mathbf{A}^{n} An为邻接矩阵的 n n n次方,那么 A n [ i , j ] \mathbf{A}^{n}[i,j] An[i,j]等于从结点 v i v_i vi​到结点 v j v_j vj​的长度为 n n n的行走的个数。

定义七(路径,path)

  • “路径”是结点不可重复的“行走”。

定义八(子图,subgraph)

  • 有一图 G = { V , E } \mathcal{G}=\{\mathcal{V}, \mathcal{E}\} G={V,E},另有一图 G ′ = { V ′ , E ′ } \mathcal{G}^{\prime}=\{\mathcal{V}^{\prime}, \mathcal{E}^{\prime}\} G′={V′,E′},其中 V ′ ∈ V \mathcal{V}^{\prime} \in \mathcal{V} V′∈V, E ′ ∈ E \mathcal{E}^{\prime} \in \mathcal{E} E′∈E并且 V ′ \mathcal{V}^{\prime} V′不包含 E ′ \mathcal{E}^{\prime} E′中未出现过的结点,那么 G ′ \mathcal{G}^{\prime} G′是 G \mathcal{G} G的子图。

定义九(连通分量,connected component)

  • 给定图 G ′ = { V ′ , E ′ } \mathcal{G}^{\prime}=\{\mathcal{V}^{\prime}, \mathcal{E}^{\prime}\} G′={V′,E′}是图 G = { V , E } \mathcal{G}=\{\mathcal{V}, \mathcal{E}\} G={V,E}的子图。记属于图 G \mathcal{G} G但不属于 G ′ \mathcal{G}^{\prime} G′图的结点集合记为 V / V ′ \mathcal{V}/\mathcal{V}^{\prime} V/V′ 。如果属于 V ′ \mathcal{V}^{\prime} V′的任意结点对之间存在至少一条路径,但不存在一条边连接属于 V ′ \mathcal{V}^{\prime} V′的结点与属于 V / V ′ \mathcal{V}/\mathcal{V}^{\prime} V/V′的结点,那么图 G ′ \mathcal{G}^{\prime} G′是图 G \mathcal{G} G的连通分量。

    图神经网络task1

    左右两边子图都是整图的连通分量。

定义十(连通图,connected graph)

  • 当一个图只包含一个连通分量,即其自身,那么该图是一个连通图。

定义十一(最短路径,shortest path)

  • v s , v t ∈ V v_{s}, v_{t} \in \mathcal{V} vs​,vt​∈V 是图 G = { V , E } \mathcal{G}=\{\mathcal{V}, \mathcal{E}\} G={V,E}上的一对结点,结点对 v s , v t ∈ V v_{s}, v_{t} \in \mathcal{V} vs​,vt​∈V之间所有路径的集合记为 P s t \mathcal{P}_{\mathrm{st}} Pst​。结点对 v s , v t v_{s}, v_{t} vs​,vt​之间的最短路径 p s t s p p_{\mathrm{s} t}^{\mathrm{sp}} pstsp​为 P s t \mathcal{P}_{\mathrm{st}} Pst​中长度最短的一条路径,其形式化定义为
    p s t s p = arg ⁡ min ⁡ p ∈ P s t ∣ p ∣ p_{\mathrm{s} t}^{\mathrm{sp}}=\arg \min _{p \in \mathcal{P}_{\mathrm{st}}}|p| pstsp​=argp∈Pst​min​∣p∣
    其中, p p p表示 P s t \mathcal{P}_{\mathrm{st}} Pst​中的一条路径, ∣ p ∣ |p| ∣p∣是路径 p p p的长度。

定义十二(直径,diameter)

  • 给定一个连通图 G = { V , E } \mathcal{G}=\{\mathcal{V}, \mathcal{E}\} G={V,E},其直径为其所有结点对之间的最短路径的最小值,形式化定义为

diameter ⁡ ( G ) = max ⁡ v s , v t ∈ V min ⁡ p ∈ P s t ∣ p ∣ \operatorname{diameter}(\mathcal{G})=\max _{v_{s}, v_{t} \in \mathcal{V}} \min _{p \in \mathcal{P}_{s t}}|p| diameter(G)=vs​,vt​∈Vmax​p∈Pst​min​∣p∣

定义十三(拉普拉斯矩阵,Laplacian Matrix)

  • 给定一个图 G = { V , E } \mathcal{G}=\{\mathcal{V}, \mathcal{E}\} G={V,E},其邻接矩阵为 A A A,其拉普拉斯矩阵定义为 L = D − A \mathbf{L=D-A} L=D−A,其中 D = d i a g ( d ( v 1 ) , ⋯   , d ( v N ) ) \mathbf{D=diag(d(v_1), \cdots, d(v_N))} D=diag(d(v1​),⋯,d(vN​))。

定义十四(对称归一化的拉普拉斯矩阵,Symmetric normalized Laplacian)

  • 给定一个图 G = { V , E } \mathcal{G}=\{\mathcal{V}, \mathcal{E}\} G={V,E},其邻接矩阵为 A A A,其规范化的拉普拉斯矩阵定义为

L = D − 1 2 ( D − A ) D − 1 2 = I − D − 1 2 A D − 1 2 \mathbf{L=D^{-\frac{1}{2}}(D-A)D^{-\frac{1}{2}}=I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}} L=D−21​(D−A)D−21​=I−D−21​AD−21​

图的种类

  • 同质图(Homogeneous Graph):只有一种类型的节点和一种类型的边的图。
  • 异质图(Heterogeneous Graph):存在多种类型的节点和多种类型的边的图。
  • 二部图(Bipartite Graphs):节点分为两类,只有不同类的节点之间存在边。

Data类的构建

# Data类的构造函数:
class Data(object):
    def __init__(self, x=None, edge_index=None, edge_attr=None, y=None, **kwargs):
        r"""
        Args:
            x (Tensor, optional): 节点属性矩阵,大小为`[num_nodes, num_node_features]`
            edge_index (LongTensor, optional): 边索引矩阵,大小为`[2, num_edges]`,第0行为尾节点,第1行为头节点,头指向尾
            edge_attr (Tensor, optional): 边属性矩阵,大小为`[num_edges, num_edge_features]`
            y (Tensor, optional): 节点或图的标签,任意大小(,其实也可以是边的标签)
        """
        self.x = x
        self.edge_index = edge_index
        self.edge_attr = edge_attr
        self.y = y

        for key, item in kwargs.items():
            if key == 'num_nodes':
                self.__num_nodes__ = item
            else:
                self[key] = item
上一篇:质数判断与质数筛法


下一篇:SZTUOJ 1018.素数