论文标题
Multigraph Fusion for Dynamic Graph Convolutional Network
论文作者、链接
作者：
Gan, Jiangzhang and Hu, Rongyao and Mo, Yujie and Kang, Zhao and Peng, Liang and Zhu, Yonghua and Zhu, Xiaofeng
链接：https://ieeexplore.ieee.org/abstract/document/9775637/
Introduction逻辑（论文动机&现有工作存在的问题）
图卷积神经网络GCN——现有的GCN都关注于表征学习，即，设计不同的卷积操作——现实场景下，由于噪音和异常值的影响，初始图常常会有一些错误的链接，这会导致特征学习的效果变差——于是，提高初始图的质量可以提高GCN的性能——图学习的目的是，可以输出高质量的图谱以保证表征学习的质量——图的质量可以由很多因素影响，诸如：噪音，原始数据的冗余，数据结构的保存情况等。
噪音和冗余情况对图学习的效果有直接的影响——传统方法是设计一些方法，来移除或减少噪音和冗余所带来的影响，包括：特征选择和子空间学习——但是往往不注重原始的高维数据的噪音和冗余情况，限制了模型的鲁棒性
现有的GCN方法都注重于保存数据的局部结构——然而现实数据往往是复杂的，单独的特征很难有效的捕捉数据的内在结构——传统的方法中证明了，局部结构和全局结构对于图学习来说都十分的重要，它们互相提供了完备的信息——局部结构描述了原始数据的内在组织关系，全局结构反映了原始数据的全局信息——同时考虑局部和全局信息可以使得模型更加的鲁棒
本文提出了一个新颖的GCN模型，包括以下特点：1）融合原始高维数据在低维空间的多重局部图谱，同时尽可能移除噪音和冗余；2）融合了局部和全局图，以生成输入到GCN的原始图谱。第一个融合集成了多重局部图谱中的共通信息，以保证局部结构中边的正确性；第二个融合，目的是试图从全局图中找到局部图的缺失的边。此外，该方法还同时学习了将原始高维数据转换为其低维空间的投影矩阵、两种图结构以及所有样本的表示。因此，每一个变量的更新都会推动表征学习的自适应调整，从而保证我们所提出的方法输出具有识别度的表征。
论文核心创新点
1）新的GCN方法，从原始数据的低维空间中联合指导图学习和表征学习。
2）图融合机制，动态学习图的权重，保证边的正确性以及找到缺失的边
相关工作
图学习
现有图学习方法主要分为传统图方法和深度图方法，图的类别主要分为静态图和动态图。
图融合
图融合是通过多个特征表达或者多重图结构，来生成一个通用的图结构。传统的图融合方法，应用一个图学习方法来实现图融合，该方法最小化期望的公共图和预定义的多个图之间的差异。
论文方法
论文动机
本文用到标识符如下：
给定一个初始化图谱以保存图结构的所有样本的特征矩阵，其中分别代表样本的数量和特征维度。GCN将都作为输入，通过数个隐藏层和一个全连接层，输出的新的特征表达，其中是类别数目。
GCN中的第层所学到的特征表达为：
其中代表第层隐藏层的输出特征，是的对角矩阵，是中的第列元素的的和。是权重矩阵，需要在第层中训练。是第层中隐藏单元的数目。是激活函数。GCN的最后一层是使用softmax函数构成的分类层，公式如下：
其中代表第层隐藏层的权重矩阵，并且是隐藏层的数目。GCN的权重参数通过最小化下面的交叉熵损失，来进行训练的：
其中是标签集，分别代表第个类的第个样本的真是标签和预测标签。
最近提出了动态GCN的方法，将图学习和表征学习结合到一个统一的模型中。更新的表征可以用来优化图，可以产生更具有区别度的表征。将传统机器学习中的图学习技术，作为一个正则项加到原始的GCN方法中，即，。具体来说，给定一个初始图谱，正则项定义如下：
其中是基于初始图谱更新的图谱，代表F范数。最后DGCN总的目标函数如下：
其中，是一个非负参数。通过对这条损失的最小化，图谱以及新的表征会交替的进行更新。如此一来，虽然图的质量比较低，但是模型最后会输出原始数据有区分度的表征。
DGCN花了很多注意力于修改正则化项，以解决各种各样的需求。但是仍有两点缺点：1）对于初始图和更新图，在公式5中的第二项，都是从原始数据中学习到的；2）很多基于GCN的方法都关注于样本的局部结构的学习，忽略了全局结构。
多重图学习
本文提出的模型如图1所示。
首先，作者提出了一个映射矩阵，将原始数据通过映射到低维数据（其中），由此尽可能移除噪音和异常值。其次，通过作者提出了多重图融合方法，来探索局部和全局的数据结构。具体来说，使用多重KNN图以学习数据的局部结构（其中是图的数量），并且通过字表达方法来学习全局图谱。比起其他现有的方法，多重图融合方法可以捕捉中各种各样的图谱结构，多重图可以提供丰富的边信息。最后将图学习和表征学习融合到一个统一的网络中，实现对图谱结构和数据表征的动态更新。
初始图生成
使用KNN图方法以生成初始的多重图。两个样本的相似性定义如下：
其中，是非负的参数。在计算所有样本的相似性之后，为每一个样本保持top-k的邻居的相似性，然后将其他的相似性全部设置为0，以得到稀疏KNN图，即，对于的初始图
重复上述操作可以得到个初始图，设置不同的k值。图谱保存了局部信息的同时每个结点都只链接了k个邻居结点。使得以保证学习到的图谱是不对称的。
局部结构学习
数据的局部结构，即，数据集的局部邻居关系对维护高维数据的流形结构十分重要，通常通过每个数据点的最近k个邻居点来表征该点。传统的局部学习方法，包括局部保留映射(locality preserving projection ，LPP)以及局部线性嵌入(locally linear embedding ,LLE)。但是这些方法有以下缺点：1）k的取值难以决定；2）初始的KNN图是从原始数据中学习得到的。因此，作者建议用以下目标函数从原始数据的低维空间中更新初始kNN图：
其中是一个非负的参数，代表一个全是1的向量。是初始图谱更新过后的图谱，是映射矩阵，可以将高维数据映射到低维空间。在公式7中，图和映射矩阵是交替进行更新的。考虑到所有的初始图都是从原始数据中学习到的，于是其中会包含大量的噪音和异常值，我们可以使用低维数据来更新他们。
全局结构学习
在公式7中，仅仅考虑了数据的局部结构信息。其他研究表明全局结构的信息也是十分重要的，原因在于全局结构信息可以有效的包含具有区分度的信息，可以从局部信息之外提供更加完备的信息，以捕捉数据的内在结构。自表示的特点已经在许多实际项目上应用了，证明了其有能力去捕捉数据的全局结构。具体来说，自表示特点假设每一个数据点可以从其他所有的样本点的加权线性组合中求得，即，，其中代表一个在与之间的加权的系数向量，是噪音偏置。为此，作者提出了以下目标函数来指导全局结构的学习：
其中，是一个非负可调参数。在公式8中，第一项是用来生成稠密图，但是在全局图上使用正则化会在保存全局结构的情况下促使生成稠密的特征表示。
局部和全局保留性学习
公式7和8，分别指导局部结构学习以及全局结构学习。不仅如此，这两种学习都是基于低维数据。因此，在本文中，作者将局部结构学习和全局结构学习与投影矩阵学习相结合，有以下损失函数：
其中是的拉普拉斯矩阵，是全部元素为1的向量，是矩阵的秩。在公式9中，还有个变量，即，和，其中是一个可训练的参数，由反向传播进行参数更新，根据公式10进行更新。公式9的优化过程如下所示
首先，固定的值，对通过公式7进行优化。为了减小复杂度，对进行近似优化：
其中是激活函数。如果是不可得到的，着将其设为1。在优化过后，得到了基于低维特征的更新后的图谱，而不是与DGCN相同的高维特征图谱。而且映射矩阵以及图都可以交替进行优化，在指导动态图学习的过程中考虑了局部结构和全局结构。
目标函数
联合学习局部图谱和全局图谱，去得到GCN的输入图，公式如下：
其中，，代表的权重，是一个可调参数，用于控制两种图谱的比重。
在公式11中，将多重局部图谱与一个全局图谱加权结合起来。参数可以被调整，参数可以由以下公式获得：
公式12中，每一个局部图都有独立的贡献。不仅如此，的值越大代表越重要。
总的目标函数如下：
其中是非负的可调参数。
总的目标函数对图融合进行了两次指导，如图2所示
第一次融合将所有的稀疏图结合起来，以保存局部结构，并且参数自动的学习每一个图的系数。
特别地1）如果有一些边只存在于一部分图谱中，第一次融合则给它们赋予一个小的甚至是0值的权重。因此，我们可以视为含噪音的边被移除了
2）如果有一些边，发现存在于一些稀疏图中且有比较大的权值，第一次融合则会保留这些权值，并将它们视为跨视图的完备信息
3）如果有一些边存在于大部分视图中，第一次融合将其视为所有局部图中的共同信息，并将其保留在中。
于是就是一个高质量的图谱，保存了局部结构但仍然会缺失一些边。
第二次融合集成了局部图谱和全局图谱以解决下列的问题。特别地，共同信息（即，之间共同的边）和补充信息（即，只存在于一方的信息）被输出了。 因此，作者提出的方法进行了两次图融合，以保证学习到的图的质量。
消融实验设计
不同图谱的敏感性
降维的有效性
参考链接
发表评论