1. 背景

本文将简短阐述下GCN的推导与传播过程，帮助快速理解；

GCN是做什么的，有什么用？

深度学习一直都是被几大经典模型给统治着，如CNN、RNN等等，它们无论再CV还是NLP领域都取得了优异的效果，那这个GCN是怎么跑出来的？是因为我们发现了很多CNN、RNN无法解决或者效果不好的问题——图结构的数据。

回忆一下，我们做图像识别，对象是图片，是一个二维的结构，于是人们发明了CNN这种神奇的模型来提取图片的特征。CNN的核心在于它的kernel，kernel是一个个小窗口，在图片上平移，通过卷积的方式来提取特征。这里的关键在于图片结构上的平移不变性：一个小窗口无论移动到图片的哪一个位置，其内部的结构都是一模一样的，因此CNN可以实现参数共享。这就是CNN的精髓所在。

再回忆一下RNN系列，它的对象是自然语言这样的序列信息，是一个一维的结构，RNN就是专门针对这些序列的结构而设计的，通过各种门的操作，使得序列前后的信息互相影响，从而很好地捕捉序列的特征。

上面讲的图片或者语言，都属于欧式空间的数据，因此才有维度的概念，欧式空间的数据的特点就是结构很规则。但是现实生活中，其实有很多很多不规则的数据结构，典型的就是图结构，或称拓扑结构，如社交网络、化学分子结构、知识图谱等等；即使是语言，实际上其内部也是复杂的树形结构，也是一种图结构；而像图片，在做目标识别的时候，我们关注的实际上只是二维图片上的部分关键点，这些点组成的也是一个图的结构。

图的结构一般来说是十分不规则的，可以认为是无限维的一种数据，所以它没有平移不变性。每一个节点的周围结构可能都是独一无二的，这种结构的数据，就让传统的CNN、RNN瞬间失效。所以很多学者从上个世纪就开始研究怎么处理这类数据了。这里涌现出了很多方法，例如GNN、DeepWalk、node2vec等等，GCN只是其中一种，这里只讲GCN，其他的后面有空再讨论。

GCN，图卷积神经网络，实际上跟CNN的作用一样，就是一个特征提取器，只不过它的对象是图数据。GCN精妙地设计了一种从图数据中提取特征的方法，从而让我们可以使用这些特征去对图数据进行节点分类（node classification）、图分类（graph classification）、边预测（link prediction），还可以顺便得到图的嵌入表示（graph embedding），可见用途广泛。因此现在人们脑洞大开，让GCN到各个领域中发光发热。

2. 图的定义

图是用以表示实体及其关系的结构，记为 G=(V,E) 。图由两个集合组成，一是节点的集合 V ，一个是边的集合 E 。 在边集 E 中，一条边 (u,v)连接一对节点 u 和 v ，表明两节点间存在关系。关系可以是无向的， 如描述节点之间的对称关系；也可以是有向的，如描述非对称关系。例如，若用图对社交网络中人们的友谊关系进行建模，因为友谊是相互的，则边是无向的； 若用图对Twitter用户的关注行为进行建模，则边是有向的。图可以是 有向的 或 无向的 ，这取决于图中边的方向性。

图可以是 加权的 或 未加权的 。在加权图中，每条边都与一个标量权重值相关联。例如，该权重可以表示长度或连接的强度。

图可以是 同构的 或是 异构的 。在同构图中，所有节点表示同一类型的实体，所有边表示同一类型的关系。 例如，社交网络的图由表示同一实体类型的人及其相互之间的社交关系组成。

3. GCN定义

假设数据中有N个节点（node），每个节点都有自己的特征，我们设这些节点的特征组成一个N×D维的矩阵X，然后各个节点之间的关系也会形成一个N×N维的矩阵A，也称为邻接矩阵（adjacency matrix）。X和A便是我们模型的输入。

GCN也是一个神经网络层，它的层与层之间的传播方式是：

其中

• \\tilde{A}=A+I，I是单位矩阵
• \\tilde{D}是\\tilde{A}的度矩阵（degree matrix），公式为 \\tilde{D}_{ii}=\\sum j\\tilde{A}_{ij}
• H是每一层的特征，对于输入层的话，H就是X
• σ是非线性激活函数

将其展开后，每个节点的更新函数如下：

其中，N(i) 是目标节点 i的邻居节点集合，c_{ji}是 i 和 j对应节点度数的平方根的乘积，即 c_{ji} = \\sqrt{|\\mathcal{N}(j)|}\\sqrt{|\\mathcal{N}(i)|}, \\sigma 为激活函数。

我们可先将注意力集中在第一个公式。可先暂时不考虑为什么要这样去设计一个公式。

现在只用知道： \\tilde{D}^{-{1/2}} \\tilde{A} \\tilde{D}^{-{1/2}} 这个部分，是可以事先算好的，因为 \\tilde{D}由A计算而来，而A是我们的输入之一。

上图中的GCN输入一个图，通过若干层GCN每个node的特征从X变成了Z，但是，无论中间有多少层，node之间的连接关系，即A，都是共享的。

假设我们构造一个两层的GCN，激活函数分别采用ReLU和Softmax，则整体的正向传播的公式为：

最后，我们针对所有带标签的节点计算cross entropy损失函数：

就可以训练一个node classification的模型了。由于即使只有很少的node有标签也能训练，作者称为半监督分类。

当然也可以用这个方法去做graph classification、link prediction，只是把损失函数给变化一下即可。

4. 公式演进

作者博客(见附录)给出了一个由简入繁的过程来解释：

我们的每一层GCN的输入都是邻接矩阵A和node的特征H，那么我们直接做一个内积，再乘一个参数矩阵W，然后激活一下，就相当于一个简单的神经网络层嘛，是不是也可以呢？

实验证明，即使就这么简单的神经网络层，就已经很强大了。这个简单模型应该大家都能理解吧，这就是正常的神经网络操作。

但是这个简单模型有几个局限性：

• 只使用A的话，由于A的对角线上都是0，所以在和特征矩阵H相乘的时候，只会计算一个节点的所有邻居的特征的加权和，该节点自己的特征却被忽略了。因此，我们可以做一个小小的改动，给A加上一个单位矩阵I，这样就让对角线元素变成1了。
• A是没有经过归一化的矩阵，这样与特征矩阵相乘会改变特征原本的分布，产生一些不可预测的问题。所以我们对A做一个标准化处理。首先让A的每一行加起来为1，我们可以乘以一个 D^{-1} ，D是度矩阵。我们可以进一步把D^{-1} 拆开与A相乘，得到一个对称且归一化的矩阵： D^{-1/2}AD^{-1/2} 。

通过对上面两个局限的改进，我们便得到了最终的层特征传播公式：

其中 \\hat{A}=A+I , \\hat{D} 为 \\hat{A} 的degree matrix。

公式中的 D^{-1/2}AD^{-1/2} 与对称归一化拉普拉斯矩阵十分类似，而在谱图卷积的核心就是使用对称归一化拉普拉斯矩阵，这也是GCN的卷积叫法的来历。

原论文中给出了完整的从谱卷积到GCN的一步步推导，后面再讲，有兴趣可以往后看。

最后是效果：

作者做了一个实验，使用一个俱乐部会员的关系网络，使用随机初始化的GCN进行特征提取，得到各个node的embedding，

而这种聚类结果，可以和DeepWalk、node2vec这种经过复杂训练得到的node embedding的效果媲美了。

还没训练就已经效果这么好，那给少量的标注信息，GCN的效果就会更加出色。

因为即使不训练，完全使用随机初始化的参数W，GCN提取出来的特征就以及十分优秀了！

这跟CNN不训练是完全不一样的，后者不训练是根本得不到什么有效特征的。

5. DGL中代码实现

在DGL中，用户可以自定义地标准化 cjic_{ji}cji​: 首先将模型设置为 norm=none，然后将预先标准化过的 ejie_{ji}eji​ 传递给聚合函数。

5.1 类定义及参数说明

class GraphConv(nn.Module):
    r"""
    
    Parameters
    ----------
    in_feats : int
        Input feature size; i.e, the number of dimensions of :math:`h_j^{(l)}`.
    out_feats : int
        Output feature size; i.e., the number of dimensions of :math:`h_i^{(l+1)}`.
    norm : str, optional
        如何使用normalizer：
        (1)若为`'right'`, 则将聚合信息除以每个节点的入度(in-degrees)，相当于对聚合的信息做平均化
        (2)若为`'none'`,将不会使用任何normalizer。如上所述，用户可以将其置为none，然后借助e_{ji}实现
           自定义的normalizer
        (3)默认为`'both'`,即使用论文中定义的`c_{ji}` ，包括入度和出度进行normalizer
    weight : bool, optional
        If True, apply a linear layer. Otherwise, aggregating the messages without a weight matrix.
    bias : bool, optional
        If True, adds a learnable bias to the output. Default: ``True``.
    activation : callable activation function/layer or None, optional
        If not None, applies an activation function to the updated node features.
        Default: ``None``.
    allow_zero_in_degree : bool, optional
        If there are 0-in-degree nodes in the graph, output for those nodes will be invalid
        since no message will be passed to those nodes. This is harmful for some applications
        causing silent performance regression. This module will raise a DGLError if it detects
        0-in-degree nodes in input graph. By setting ``True``, it will suppress the check
        and let the users handle it by themselves. Default: ``False``.

    Attributes （parameters为传递的参数，attributes为类内部的参数）
    ----------
    weight : torch.Tensor
        The learnable weight tensor.
    bias : torch.Tensor
        The learnable bias tensor.

    Note
    ----
    Zero in-degree nodes will lead to invalid output value. This is because no message
    will be passed to those nodes, the aggregation function will be appied on empty input.
    A common practice to avoid this is to add a self-loop for each node in the graph if
    it is homogeneous, which can be achieved by:

    >>> g = ... # a DGLGraph
    >>> g = dgl.add_self_loop(g)

    Calling ``add_self_loop`` will not work for some graphs, for example, heterogeneous graph
    since the edge type can not be decided for self_loop edges. Set ``allow_zero_in_degree``
    to ``True`` for those cases to unblock the code and handle zere-in-degree nodes manually.
    A common practise to handle this is to filter out the nodes with zere-in-degree when use
    after conv.

5.2 init function()

def __init__(self,
             in_feats,
             out_feats,
             norm='both',
             weight=True,
             bias=True,
             activation=None,
             allow_zero_in_degree=False):
    super(GraphConv, self).__init__()
    if norm not in ('none', 'both', 'right'):
        raise DGLError('Invalid norm value. Must be either "none", "both" or "right".'
                       ' But got "{}".'.format(norm))
    self._in_feats = in_feats
    self._out_feats = out_feats
    self._norm = norm
    self._allow_zero_in_degree = allow_zero_in_degree

    if weight:
        self.weight = nn.Parameter(th.Tensor(in_feats, out_feats))
    else:
        self.register_parameter('weight', None)

    if bias:
        self.bias = nn.Parameter(th.Tensor(out_feats))
    else:
        self.register_parameter('bias', None)

    self.reset_parameters()

    self._activation = activation

5.3 forward() function

def forward(self, graph, feat, weight=None, edge_weight=None):
    r"""

    Description
    -----------
    Compute graph convolution.

    Parameters
    ----------
    graph : DGLGraph
        The graph.
    feat : torch.Tensor or pair of torch.Tensor
        If a torch.Tensor is given, it represents the input feature of shape
        :math:`(N, D_{in})`
        where :math:`D_{in}` is size of input feature, :math:`N` is the number of nodes.
        If a pair of torch.Tensor is given, which is the case for bipartite graph, the pair
        must contain two tensors of shape :math:`(N_{in}, D_{in_{src}})` and
        :math:`(N_{out}, D_{in_{dst}})`.
    weight : torch.Tensor, optional
        Optional external weight tensor.(将init()方法中的weight置为none，)
    edge_weight : torch.Tensor, optional
        Optional tensor on the edge. If given, the convolution will weight
        with regard to the message.

    Returns
    -------
    torch.Tensor
        The output feature

    Raises
    ------
    DGLError
        Case 1:
        If there are 0-in-degree nodes in the input graph, it will raise DGLError
        since no message will be passed to those nodes. This will cause invalid output.
        The error can be ignored by setting ``allow_zero_in_degree`` parameter to ``True``.

        Case 2:
        External weight is provided while at the same time the module
        has defined its own weight parameter.

    Note
    ----
    * Input shape: :math:`(N, *, \\text{in_feats})` where * means any number of additional
      dimensions, :math:`N` is the number of nodes.
    * Output shape: :math:`(N, *, \\text{out_feats})` where all but the last dimension are
      the same shape as the input.
    * Weight shape: :math:`(\\text{in_feats}, \\text{out_feats})`.
    """
    with graph.local_scope():
        if not self._allow_zero_in_degree:
            if (graph.in_degrees() == 0).any():
                raise DGLError('There are 0-in-degree nodes in the graph, '
                               'output for those nodes will be invalid. '
                               'This is harmful for some applications, '
                               'causing silent performance regression. '
                               'Adding self-loop on the input graph by '
                               'calling `g = dgl.add_self_loop(g)` will resolve '
                               'the issue. Setting ``allow_zero_in_degree`` '
                               'to be `True` when constructing this module will '
                               'suppress the check and let the code run.')
                
        # copy_src（已被copy_u取代）为内置消息函数，将源节点的特征h复制并发动到mailbox，表示为m
        aggregate_fn = fn.copy_src('h', 'm')
        
        # 边的权重
        if edge_weight is not None:
            assert edge_weight.shape[0] == graph.number_of_edges()
            graph.edata['_edge_weight'] = edge_weight
            # 若考虑edge weight，则聚合函数为源节点特征乘以边的权重，结果保存为m
            aggregate_fn = fn.u_mul_e('h', '_edge_weight', 'm')

        # (BarclayII) For RGCN on heterogeneous graphs we need to support GCN on bipartite.
        feat_src, feat_dst = expand_as_pair(feat, graph)
        if self._norm == 'both':
            # clamp函数用于约束返回值到A和B之间，若value小于min，则返回min；
            # 若value大于max，则返回max，起到上下截断的作用。
            degs = graph.out_degrees().float().clamp(min=1)
            # degs的-0.5次方
            norm = th.pow(degs, -0.5)
            # (1,) * (feat_src.dim() - 1)：假设feature为单个向量，则feat_src.dim()为2，最后运算结果为(1,)
            # 若feat_src.dim()为3，则(1,) * (feat_src.dim() - 1) = (1,1)
            # norm.shape + (1,)，表示在原先维度的基础上，扩展以为，其值为1
            shp = norm.shape + (1,) * (feat_src.dim() - 1)
            # norm reshape之后便于点乘
            norm = th.reshape(norm, shp)
            # 假设norm原始shape为[n],reshape后为[n,1],而feat_src shape为[n,in_feat]
            feat_src = feat_src * norm

        if weight is not None:
            if self.weight is not None:
                raise DGLError('External weight is provided while at the same time the'
                               ' module has defined its own weight parameter. Please'
                               ' create the module with flag weight=False.')
        else:
            weight = self.weight

        if self._in_feats > self._out_feats:
            # mult W first to reduce the feature size for aggregation.
            if weight is not None:
                # th.matmul：矩阵乘法
                feat_src = th.matmul(feat_src, weight)
            graph.srcdata['h'] = feat_src
            graph.update_all(aggregate_fn, fn.sum(msg='m', out='h'))
            rst = graph.dstdata['h']
        else:
            # aggregate first then mult W
            graph.srcdata['h'] = feat_src
            graph.update_all(aggregate_fn, fn.sum(msg='m', out='h'))
            rst = graph.dstdata['h']
            if weight is not None:
                rst = th.matmul(rst, weight)

        if self._norm != 'none':
            degs = graph.in_degrees().float().clamp(min=1)
            if self._norm == 'both':
                norm = th.pow(degs, -0.5)
            else:
                norm = 1.0 / degs
            shp = norm.shape + (1,) * (feat_dst.dim() - 1)
            norm = th.reshape(norm, shp)
            rst = rst * norm

        if self.bias is not None:
            rst = rst + self.bias

        if self._activation is not None:
            rst = self._activation(rst)

        return rst

注意这里在计算norm的时候，先对所有feat_src计算了out_degree，然后聚合后将最终结果计算了in_degree。在论文中，是假设所有图为无向图的，而在DGL中，构建无向图的方法是节点之间添加双向边，如此一来，DGL中对不同图的GCN实现可分为以下情况：

• 无向图：每个节点的 degree = out_degree = in_degree，DGL适用；
• 二部图：源节点只有出度，目标节点只有入度，虽然为有向图，DGL仍适用；
• 有向图：DGL在有向图上进行graphconv，实际上是对原始的GCN论文做了拓展，在计算norm时，仅仅计算了源节点的出度和目标节点的入度（相关理论支持有待进一步研究，如为何不同时计算所有节点的入度和出度？也许只是为了代码简洁，将所有情况用一套代码实现？）

6. 理解与推导GCN

图卷积神经网络主要有两类，一类是基于空间域或顶点域vertex domain(spatial domain)的，另一类则是基于频域或谱域spectral domain的。

通俗点解释，空域可以类比到直接在图片的像素点上进行卷积，而频域可以类比到对图片进行傅里叶变换后，再进行卷积。

spectral domain：频域方法(谱方法/频域)

这就是谱域图卷积网络的理论基础了。这种思路就是希望借助图谱的理论来实现拓扑图上的卷积操作。GCN主要是借助于图的拉普拉斯矩阵的特征值和特征向量来研究图的性质，这与谱聚类的思想不谋而合，不妨先了解下谱聚类。从整个研究的时间进程来看：首先研究GSP（graph signal processing）的学者定义了graph上的Fourier Transformation，进而定义了graph上的convolution，最后与深度学习结合提出了Graph Convolutional Network。
基于频域卷积的方法则从图信号处理起家，包括 Spectral CNN[5], Cheybyshev Spectral CNN(ChebNet)[6], 和 First order of ChebNet(1stChebNet)[7]等

vertex domain(spatial domain)：顶点域(空间域/空域)

基于空域卷积的方法直接将卷积操作定义在每个结点的连接关系上，它跟传统的卷积神经网络中的卷积更相似一些。在这个类别中比较有代表性的方法有 Message Passing Neural Networks(MPNN)[1], GraphSage[2], Diffusion Convolution Neural Networks(DCNN)[3], PATCHY-SAN[4]等。

6.1 拉普拉斯矩阵

Graph Fourier Transformation及Graph Convolution的定义都用到图的拉普拉斯矩阵，那么首先来介绍一下拉普拉斯矩阵。拉普拉斯矩阵(Laplacian matrix) 也叫做导纳矩阵、基尔霍夫矩阵或离散拉普拉斯算子，主要应用在图论中，作为一个图的矩阵表示。
对于图 G=(V,E)，其Laplacian 矩阵的定义为 L=D−A，其中 L 是Laplacian 矩阵， D 是顶点的度矩阵（对角矩阵），对角线上元素依次为各个顶点的度，A 是图的邻接矩阵。
这里要说明的是：常用的拉普拉斯矩阵实际有三种：

• L=D−A定义的Laplacian 矩阵更专业的名称叫Combinatorial Laplacian
• L^{sys}=D^{-1/2}LD^{-1/2}
  定义的叫Symmetric normalized Laplacian，很多GCN的论文中应用的是这种拉普拉斯矩阵
• L^{rw}=D^{-1}L
  定义的叫Random walk normalized Laplacian

为什么GCN要用拉普拉斯矩阵？
拉普拉斯矩阵矩阵有很多良好的性质，主要有三点：
(1)拉普拉斯矩阵是对称矩阵，可以进行特征分解（谱分解），这就和GCN的spectral domain对应
(2)拉普拉斯矩阵只在中心顶点和一阶相连的顶点上（1-hop neighbor）有非0元素，其余之处均为0
(3)通过拉普拉斯算子与拉普拉斯矩阵进行类比

6.2 拉普拉斯矩阵的谱分解（特征分解）

GCN的核心基于拉普拉斯矩阵的谱分解。
矩阵的谱分解，特征分解，对角化都是同一个概念。不是所有的矩阵都可以特征分解，其 充要条件为n阶方阵存在n个线性无关的特征向量。
但是拉普拉斯矩阵是半正定对称矩阵，有如下性质：

• 对称矩阵一定n个线性无关的特征向量
• 半正定矩阵的特征值一定非负
• 对阵矩阵的特征向量相互正交，即所有特征向量构成的矩阵为正交矩阵。
• 特征值中0出现的次数就是图连通区域的个数。
• 最小特征值是0，因为拉普拉斯矩阵（普通形式：L=D−A）每一行的和均为0，并且最小特征值对应的特征向量是每个值全为1的向量；
• 最小非零特征值是图的代数连通度。

由上可以知道拉普拉斯矩阵一定可以谱分解，且分解后有特殊的形式。

对于拉普拉斯矩阵其谱分解为：

6.3 拉普拉斯算子

定义：拉普拉斯算子是n维欧几里德空间中的一个二阶微分算子，定义为梯度（∇f）的散度（∇⋅f，即∇f⋅f）。因此如果f是二阶可微的实函数，则f的拉普拉斯算子Δ定义为：

ff的拉普拉斯算子也是笛卡尔坐标系xixi中的所有非混合二阶偏导数：

函数ff的拉普拉斯算子也是该函数的海塞矩阵(是一个多元函数的二阶偏导数构成的方阵)的迹：

拉普拉斯算子(Laplacian operator) 的物理意义是空间二阶导，准确定义是：标量梯度场中的散度，一般可用于描述物理量的流入流出。比如说在二维空间中的温度传播规律，一般可以用拉普拉斯算子来描述。

拉普拉斯矩阵也叫做离散的拉普拉斯算子。

6.4 卷积

在泛函分析中，卷积是通过两个函数f(x)和g(x)生成第三个函数的一种算子，它代表的意义是：两个函数中的一个(取g(x))函数，把g(x)经过翻转平移,然后与f(x)相乘，得到的一个新的函数，对这个函数积分，也就是对这个新的函数求它所围成的曲边梯形的面积。

设f(t)g(t)是两个可积函数，f(t)与g(t)的卷积记为f(t)∗g(t)，它是其中一个函数翻转并平移后与另一个函数乘积的积分，是一个自变量是平移量的函数。也就是：

6.5 傅里叶变换

傅里叶级数其实就是用一组sin，cos的函数来逼近一个周期函数，那么每个sin，cos函数就是一组基，这组基上的系数就是频域，会发现随着频域越来越多（基越来越多），函数的拟合就越准确。
假设f(x)周期为T，其傅里叶级数可以写作：

其中

利用欧拉公式e^{ix}=cos x+i sinx
我们发现cosx,sinx可表示成

得到了傅里叶变换就是

傅立叶级数是基于周期函数的，如果我们把周期推广到T=∞，那么也就变为了非周期函数，这就是傅立叶变换。

其实可以发现这个对信号f(x)的傅立叶变换F(ω)形式上是f(x)与基函数e^{−iωx}
的积分，本质上将函数ff(x)映射到了以e^{−iωx}
为基向量的空间中。

6.6 从传统的傅里叶变换、卷积到Graph上的傅里叶变换及卷积

把传统的傅里叶变换以及卷积迁移到Graph上来，核心工作其实就是把拉普拉斯算子的特征函数 e^{−iωx}
变为Graph对应的拉普拉斯矩阵的特征向量。

(1)推广傅里叶变换

(a)Graph上的傅里叶变换
传统的傅里叶变换定义为：

信号 f(t) 与基函数 e^{−iωx}
的积分，那么为什么要找e^{−iωx}
作为基函数呢？从数学上看，e^{−iωx}
是拉普拉斯算子的特征函数（满足特征方程）,ω就和特征值有关。
广义的特征方程定义为：

其中AA是一种变换，VV是特征向量或者特征函数（无穷维的向量）， λλ是特征值。
e^{−iωx}
满足：

当然e^{−iωx}
就是变换Δ的特征函数，ω和特征值密切相关。

处理Graph问题的时候，用到拉普拉斯矩阵，自然就去找拉普拉斯矩阵的特征向量了。

L是拉普拉斯矩阵，V是其特征向量，自然满足下式

离散积分就是一种内积形式，仿上定义Graph上的傅里叶变换：

f是Graph上的 N 维向量， f(i)与Graph的顶点一一对应， ul(i)表示第l个特征向量的第 i个分量。那么特征值（频率）λl下的， f 的Graph 傅里叶变换就是与 λl 对应的特征向量 ul 进行内积运算。

利用矩阵乘法将Graph上的傅里叶变换推广到矩阵形式：

即f在Graph上傅里叶变换的矩阵形式为：

(b)Graph上的傅里叶逆变换

类似地，传统的傅里叶逆变换是对频率ω求积分：

迁移到Graph上变为对特征值λl求和：

利用矩阵乘法将Graph上的傅里叶逆变换推广到矩阵形式：

即f在Graph上傅里叶逆变换的矩阵形式为：

(2)推广卷积

在上面的基础上，利用卷积定理类比来将卷积运算，推广到Graph上。
卷积定理：函数卷积的傅里叶变换是函数傅立叶变换的乘积，即对于函数f(t)与h(t)两者的卷积是其函数傅立叶变换乘积的逆变换：

类比到Graph上并把傅里叶变换的定义带入，f与卷积核h在Graph上的卷积可按下列步骤求出

ff的傅里叶变换为\\hat f = U^T f

卷积核h的傅里叶变换写成对角矩阵的形式即为：

\\hat h(\\lambda_l)=\\sum_{i=1}^N h(i)u_l^*(i)
是根据需要设计的卷积核hh 在Graph上的傅里叶变换。

在处理Graph时，用到的是傅里叶变换的离散形式。由于拉普拉斯矩阵进行谱分解以后，可以得到n个线性无关的特征向量，构成空间中的一组正交基，因此归一化拉普拉斯矩阵算子的特征向量构成了图傅里叶变换的基。图傅里叶变换将输入图的信号投影到了正交空间，相当于把图上定义的任意向量，表示成了拉普拉斯矩阵特征向量的线性组合。

两者的傅立叶变换乘积即为：

再乘以U求两者傅立叶变换乘积的逆变换，则求出卷积：

注：很多论文中的Graph卷积公式为：(f*h)_G=U((U^Th) \\bigodot (U^T f))
。其中⨀表示Hadamard product（哈达马积），对于两个维度相同的向量、矩阵、张量进行对应位置的逐元素乘积运算。其实与上式是完全相同的。

6.7 Deep Learning中的Graph Convolution

Deep learning 中的Graph Convolution直接看上去会和之前推导出的图卷积公式有很大的不同，但是万变不离其宗，都是根据下式来推导的：

Deep learning 中的Convolution就是要设计含有trainable共享参数的kernel。
上式计算量很大，因为特征向量矩阵U 的复杂度是O(N2)O(N2)。此外，对于大型图来说，LL特征值分解的计算量也很大。
基于上面最原始的卷积公式，深度学习中的GCN主要是从下面几篇文章演变而来的（引用次数都很高），值得深入探讨：

• 【1】Bruna, Joan, et al. “Spectral networks and locally connected networks on graphs.” 源于ICLR 2014（被引740次）
• 【2】Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. “Convolutional neural networks on graphs with fast localized spectral filtering.” 源于NIPS 2016（被引997次）
• 【3】Hammond, David K., Pierre Vandergheynst, and Rémi Gribonval. “Wavelets on graphs via spectral graph theory.” Applied and Computational Harmonic Analysis 30.2 (2011)（被引874次）
• 【4】Kipf, Thomas N., and Max Welling. “Semi-supervised classification with graph convolutional networks.” 源于ICML 2017 （被引1537次）

6.8 总结

为什么GCN要用拉普拉斯矩阵？

拉普拉斯矩阵是对称矩阵，可以进行特征分解（谱分解）
由于卷积在傅里叶域的计算相对简单，为了在graph上做傅里叶变换，需要找到graph的连续的正交基对应于傅里叶变换的基，因此要使用拉普拉斯矩阵的特征向量。

为什么拉普拉斯矩阵的特征向量可以作为傅里叶变换的基？

傅里叶变换一个本质理解就是：把任意一个函数表示成了若干个正交函数（由sin,cos 构成）的线性组合。 graph傅里叶变换也把graph上定义的任意向量ff，表示成了拉普拉斯矩阵特征向量的线性组合，即：

怎么理解拉普拉斯矩阵的特征值表示频率？

在graph空间上无法可视化展示“频率”这个概念，那么从特征方程上来抽象理解。
在由Graph确定的nn维空间中，越小的特征值λlλl表明：拉普拉斯矩阵LL其所对应的基ulul 上的分量、“信息”越少，那么当然就是可以忽略的低频部分了。
其实图像压缩就是这个原理，把像素矩阵特征分解后，把小的特征值（低频部分）全部变成0，PCA降维也是同样的，把协方差矩阵特征分解后，按从大到小取出前K个特征值对应的特征向量作为新的“坐标轴”。

Ref

1. https://zhuanlan.zhihu.com/p/71200936
2. https://lizitong67.github.io/2021/03/14/DGL%E6%BA%90%E7%A0%81%E8%A7%A3%E6%9E%90-GCN/
3. https://arxiv.org/abs/1609.02907
4. http://tkipf.github.io/graph-convolutional-networks/
5. https://docs.dgl.ai/en/0.6.x/api/python/nn.pytorch.html
6. https://docs.dgl.ai/en/0.6.x/tutorials/models/1_gnn/1_gcn.html
7. https://www.cnblogs.com/hellojamest/p/11678324.html
8. https://zhuanlan.zhihu.com/p/112277874
9. https://blog.csdn.net/yyl424525/article/details/100058264