ICDM 2019最佳论文：从图片、文本到网络结构数据翻译，一种新型的多属性图翻译模型

文中还提出了一种特殊形式的基于拉普拉斯图频谱的正则化方法，来学习和保持图节点和边属性的一致化。最后，在对合成和实际应用数据（物联网安全优化，化学反应预测）的大量实验证明该方法的有效性和广泛性。 

论文链接：http://mason.gmu.edu/~lzhao9/materials/papers/ICDM_2019_NEC_DGT-final.pdf

背景

在将输入数据（例如图像，文本）「转换」为对应的输出数据的过程中会遇到许多与结构化预测有关的问题，需要学习从输入域到目标域的转换映射。例如，图像处理和计算机视觉中的许多问题都可以看作是从输入图像到相应输出图像的「翻译」。这种翻译问题非常重要并且有极为广泛的，但实际上却极为困难，近年来引起了越来越多的关注。

传统研究只考虑特定结构类型的数据翻译（转换）问题，然而在许多实际应用中，需要处理比网格和序列更灵活的结构的数据，因此需要更强大的转换技术来处理更通用的图结构数据。现有图结构翻译模型有两种形式，第一种假设来自输入域和目标域的图共享相同的图拓扑结构，但是无法建模或预测图拓扑的变化, 例如对交通网络中节点处车流量的预测 [1]。第二种只考虑预测图结构的变化，不考虑节点属性的变化过程 [2]。

因此，现有的工作要么根据固定的拓扑结构预测节点属性，要么根据固定的节点属性预测边的属性。但是，在许多实际应用中，节点属性和边属性都可以更改。在本文中，这种通用问题被称为多属性图转换，其在现实世界中有着重要应用范围，例如从生物结构到功能性脑神经的网络转换和物联网安全优化问题。

问题概述

首先将输入图定义为 ，其中 是 N 个图节点的集合，而 是 M 个边的集合。 是代表边属性的张量，而 K 是边属性的维数。 是表示节点属性的矩阵，其中 D 是节点属性的维数。同样，我们将目标图定义为 。请注意，目标图和输入图的节点属性和边属性均不同。此外，可能存在向量 C 提供有关转换过程的一些环境信息。因此，多属性图转换可以被定义为学习一种映射：

 多属性图转换问题需要考虑一些独特的因素对结果的影响，如图 2 所示：1）边与边的交互：在目标域中，边属性可能会受到其邻接边在输入域中的属性的影响，如图 2(a)。2）节点与边的交互：在目标域中，边的属性可能会受输入域中其两个邻接节点的属性的影响，如图 2(b)。3）节点与节点的交互：对于给定的节点，其在输入域中的属性; 可能会直接影响该节点在目标域中的属性，如图 2(c)。4）边与节点之间的交互：对于给定节点，其在输入域中的相关边属性可能会影响其在目标域中的属性，如图 2(d)。5）频谱图属性：一幅图中的节点和边之间会存在复杂的关系，如频谱图所反映，在输入域和目标域中节点与边具有某些持久性或一致性，这在许多实际应用中也已得到验证，例如人的大脑网络，如图 2(e)。如何将以上四种交互模式都融入到模型当中是整个问题的难点之一。

  模型概括

本文所提出的 NEC-DGT (Node-Edge Co-evolution Deep Graph Translation) 在输入图和上下文信息的条件下对目标域图进行预测。但是，这种从输入图到最终目标图的转换过程可能会经历边缘和节点之间一系列不同类型的交互。为了学习这种复杂的过程，该文章提出了如图 3 所示的 NEC-DGT 双路径多模块。具体地说，将输入图的节点和边的属性作为输入，经历若干模块最终输出目标图的节点属性和边属性。每一模块都包含有节点转换路径和边转换路径。并利用 skip-connection 的跨模块的连接结构（图 3 中的黑色虚线）来处理图转换过程的异步特性，从而确保最终转换的结果充分利用了每一模块信息的各种组合。为了训练该图神经网络模型，基本的损失函数最小化如下：

拉普拉斯图频谱正则化

1. 基于边和节点的转换路径，我们可以分别生成节点和边缘属性。但是，由于这些生成的节点和边属性是在不同的路径中分别预测的，因此它们的模式可不一致。为了探索和确保边和节点模式的复杂关系，我们提出了一种基于非参数的图拉普拉斯算子图频谱正则化的正则化方法。我们回顾传统的拉普拉斯正则化表达式为: 

传统的拉普拉斯正则化基于非常严格的约束即相连的节点拥有相似的节点属性，但显示应用 中节点属性和边的连接之间有更为复杂的关系。因此，我们用一个非参数的形式去表示图的拉普拉斯：

因此 非参数的图频谱正则化表示为：

2. 目前的正则化复杂度是 O（N），与图节点的数量线性相关，为了进一步提高该正则化的可扩展性，降低复杂度，我们提出一种基于切比雪夫多项式的可扩展近似的图拉普拉斯表示，如下：

3. 为了确保学习到的图频谱在不同模块生成的图之间的保持一定程度的一致（整个过程产生的图同属一种类型，如人脑网络，化学物质结构，社交网络等），该文章提出的图频率正则化不仅允许保持相似性，还允许在某种程度上保留每个块模式的专有属性。具体来说，对于学习到的频率（卷积核），有些对建模节点和图之间的关系很重要，而有些则不然，导致的稀疏的模式。因此，在多任务学习的启发下，我们使用 L2-1 范数作为正则化学习了频率的稀疏模式：

实验结果

本文分别在人造数据集和两个实际数据集上进行了实验，并分别与三类方法（共 7 种）进行了对比。其中 NEC-DGT（no reg) 作为 baseline 表示该模型不加正则化环节。

1. 基于参数衡量的各个数据集的实验结果：

 

实验结果表明，NEC-DGT 是现在唯一一个可以进行多属性图转换的模型，并且分别在节点属性和边属性的预测任务中超过其他单任务模型。与 NEC-DGT（no reg) 的对比表示，所提出的图频谱正则化对学习过程非常重要。

2. 物联网安全优化任务案例分析：

图 7 研究了 NEC-DGT 输入图，实际目标图和生成目标图的三种情况。绿色节点表示未感染的设备，红色节点表示已感染的设备。每个边的宽度反映了两个设备之间的距离。在第一行中，在生成的目标图和实际目标图中，设备 4 和 6 均恢复正常，而设备 19 受到攻击并与其他设备隔离。它验证了我们的 NEC-DGT 成功地找到了转换节点的规则，并且执行了像真正的限制过程一样的操作。在第二行，设备 8 将病毒传播到设备 38，该传播也同样出现在由 NEC-DGT 生成的图中。此外，NEC-DGT 不仅可以正确预测节点属性，还可以同时发现边属性的变化，例如 在第三行，在生成的目标图和实际目标图中都切断了受损设备 10 的大多数连接。

本文提出的 NEC-DGT 模型的代码和数据网络链接已在论文中公开，欢迎使用。

欢迎邮件联系 xguo7@gmu.edu 或者 lzhao9@gmu.edu.

文献：

[1] Yu, B., Yin, H., & Zhu, Z. (2017). Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. arXiv preprint arXiv:1709.04875.

[2] X. Guo, L. Wu, and L. Zhao,「Deep graph translation,」arXiv preprint arXiv:1805.09980, 2018.