图深度学习模型进展和在阿里搜索广告中的应用创新

近几年，图深度模型在工业界和学术界都备受关注，产生了大量的研究工作和工业应用。本文分别介绍了图深度学习的产生、发展和在工业界中的应用，同时，以阿里的Euler图深度模型框架和在搜索场景中的应用为例，介绍了这类方法在互联网场景中的应用，期望能给正在探索图深度模型应用的同行带来一些启发。

01 从深度学习到图深度学习

我们已经进入到数据时代，数据时代的重要特点之一是各种数据资源和互联网创新技术成为了推动人类社会经济发展的重要力量。一方面，随着互联网应用的推广，越来越多的生活、生产数据以数据化的形式被表达和记录；另一方面，深度学习方法借助复杂的模型结构，能够将大规模数据所蕴含的知识表达在模型中，在大数据场景下，产生了远优于传统的LR（logistic regression）、DT（decision tree）的效果，在很多国际比赛中不断的刷新榜单。

深度学习方法对数据的处理能力，结合云计算的计算能力，让机器处理、理解大规模数据成为了可能。近年来，随着数据规模和硬件计算力的迅速增长，深度学习技术在工业界被广泛应用并产生巨大的技术红利，让搜索、推荐这些技术，借助智能手机和PC载体，在人们的生产生活中起到了重要的作用，人们可以方便的搜索到自己感兴趣的新闻、话题、商品，也可以享受到智能推荐带来的便捷和欢乐。

图神经网络是深度学习中的一个重要研究分支，它作用在“图（graph）”结构数据上，通过结合深度学习的端到端学习能力和图中的关系信息，在图上进行学习和推断，更高效地学习数据内涵信息并进行适当推理，在提升传统深度学习方法效率的同时，有望推动解决关系推理（知识图谱中的问答推理）、可解释性等一系列难题。 由于图结构中，每个节点不仅具有标签，同时还有和其他节点的关联关系，在模型学习中引入这种关联关系信息能够提升模型的学习效率。 比如在一张社交网络图中，深度模型的目的是推断每个人的内容喜好，那么图中人和人的朋友关系会增强深度模型的推断能力，因为一个人的喜欢是会被朋友的喜好“影响”的。

通常，如图1所示，图像和文本可以通过将图像像素、文本单元之间的空间关系表示成图的边来生成图结构。由于这些空间关系比较规则，经典的MLP（multi-layer perceptron）、CNN（convolutional neural network）[3] 深度模型就能够处理。而现实世界中的图（例如：以社交网络的用户为节点、以朋友关系为边构造的图）常常具有更为复杂的关系，图上的每个节点没有固定的邻居个数，节点之间也没有明确的顺序关系，这种非欧空间下的数据表达难以直接应用卷积网络类方法，需要设计专门的图神经网络结构来处理这种数据 [4] 。

图1 (a)(b)图像和文本序列可以分别看作是二维和一维的、规则性很强的图结构；而(c)现实世界中的图结构会更加复杂

02 图深度学习的主流方法

在学术界，图神经网络领域的研究已经取得了不错的进展，也有很多学者对这个领域做了较全面的综述 [5] [6] ，我们这里将对图深度学习的发展脉络做出分析，并介绍发展过程中产生的部分代表性工作。

如上文提到，与规则的图像、文本图不同，现实世界的图本身是不规则的，那么如何用经典深度学习模型处理不规则的图结构？游走（walk）类方法 [7] [8] 给出了一类解决途径。这类方法首先通过在图节点上游走，生成节点序列，进而在节点序列上应用经典的深度学习方法进行处理。这类方法主要关注游走方法的选择，及在生成的节点序列上所使用的深度模型的优化。

从另一个角度出发，研究者们试图直接定义可以应用在图上的深度学习方法。早年的图深度学习方法分为两个主流的思路：空域（spatial-based）方法和频域（spectral-based）方法。空域类的方法通过在图中定义邻居的顺序并限制邻居个数，将本来规则性弱的图转换成适合经典MLP和CNN处理的规则图结构，从而在转换后的图上进行模型训练和推断。文献[9]设计了一个函数用于定义图节点的顺序并限制参与图卷积的邻居数量，从而可以使用CNN方法对于图进行处理。这类方法比较直观，但是缺少理论依据。而对于频类方法而言，由于频域的乘积对应于原始空域的卷积，这类方法 [10] [11] 将图表示成邻接矩阵形式，通过图傅立叶变换，将图转化到频域，在频域进行滤波（filter）操作，然后再通过反图傅立叶变换变换回空域。这类方法的一个核心问题就是如何设计频域中的滤波器（filter，矩阵形式），在文献[10]中，作者将滤波器矩阵表示成对角矩阵，而每个对角元素都要通过训练学习到，这就造成了参数过大、计算量不可控的问题。在文献[11]中，作者针对图提出了一种新的CNN（后被称为ChebNet），其中将滤波器矩阵的对角元素设计为图拉普拉斯矩阵的特征根的K次多项式，从而将参数量大幅度缩小。相对于空域方法，频域方法有非常完善的理论依据，然而，这些方法的计算过程需要对图进行特征分解，计算消耗量大，很难推广到大规模应用上去。

在2017年，Kipf等人对ChebNet做了进一步的简化，提出了GCN [12] ，而在简化的结果中发现其实 频域方法的极简形式就是对空域邻居的一个汇聚过程 。自此，频域和空域的方法结合到了一个统一的理论框架下，图神经网络处理大规模图成为了可能。目前，主流的研究方向有两个：

1）图网络聚合器的设计，通过设计不同的神经网络模型来实现不同的图结构聚合处理方式。代表性工作有

• a）图卷积网络GCN，借助图的拉普拉斯矩阵进行节点卷积，根据邻居节点的出/入度对邻居节点信息进行加权组合来获取当前节点的表征；
• b）图循环神经网络GraphLSTM [13] ，这种方法用于处理序列数据（比如交通枢纽数据），应用GRU、LSTM等循环神经网络进行节点表征更新；
• c）图注意力网络GAT [17] ，使用了注意力网络来对不同的邻居节点根据其属性与中心节点的关系进行自适应加权汇聚。

2）图数据本身的信息选择和结构挖掘，代表性工作有：

• a）GraphSAGE [13] ，这种方法为了节省计算资源，不再执行全邻居汇聚，而是对每个节点采样一部分代表邻居来参与汇聚，这种方法降低了对图结构的约束，实现了对未知节点的归纳式学习；
• b）FastGCN [14] 则进一步通过按层联合采样的方式降低节点规模，每一层的节点之间共享邻居，大大降低了计算复杂度；
• c）MixHop [15] 对图的高阶邻近性进行挖掘，每个节点不仅会采样直接相连的1跳邻居，还会采样多跳邻居，这种混合多跳邻居的聚合方式，让模型能够挖掘到更复杂的图结构信息。

03 图深度学习框架

以MLP、CNN等方法为代表的深度神经网络在工业界已经被广泛应用，并取得了很好的效果，也产生了像Tensorflow、PyTorch这样的被广泛应用的开源机器学习框架。然而，图神经网络目前在工业界还没有特别成熟的、被广泛使用的框架。虽然已有一些开源的图模型训练框架，比如亚马逊和纽约大学开发的DGL，但是这些框架都是单机模式，适合处理小规模的图数据，难以支撑实际大规模的应用场景。 从工业界实际应用的计算需求出发，建立一套能够应用于大规模数据场景、具有高效计算能力的图神经网络计算框架将在推进人工智能技术在产业界的应用中产生重大作用。 这里，我们将以阿里的Euler深度图学习平台（https://github.com/alibaba/euler）为例，介绍图深度学习框架构建和实际应用中的一些思考。

在设计能够应用于工业界图数据的图深度神经网络时，需要考虑对以下核心能力的支持：

1）大规模分布式学习能力。由于工业界的图规模较大，往往具有数十亿节点和数百亿边，有些场景甚至可以到数百亿节点和数千亿边，单机完成这样规模的图数据训练是不可行的。

2）支持复杂异构图的表征。工业界的图关系大都错综复杂，体现在节点异构、边关系异构，另外节点和边上可能有非常丰富的属性，这使得一些常见的图神经网络很难学到有效的表达。

3）灵活拓展的能力。图深度神经网络框架是一个基础设施，若底层处理逻辑尽可能对于用户透明，那么将方便用户进行二次开发。

Euler图深度学习框架于2019年开源，是工业界首个支持大规模分布式训练的深度图学习平台，截止目前已有2.7K个Github Star。 整个框架可以抽象为图引擎层（Euler engine）和算法实现层（algorithm package）两个层次，可以快速在算法实现层扩展一个图学习算法，并且Euler也内置了大量的算法实现供大家直接使用。在图结构存储和图计算的抽象上均良好地支持异构点、异构边类型的操作，并支持丰富的异构属性，可以很容易的在图学习算法中进行异构图的表征学习。具体来说，Euler的架构设计如图(2)所示。

图2 Euler图深度神经网络开源框架的架构图

Euler采用了分布式的存储架构存储超大规模图（数十亿节点，数百亿边）。在图加载时，整张图在引擎内部被切分为多个子图，每个计算节点被分配一个或几个子图进行加载。为了充分利用各个计算节点的能力，在进行图的操作时，顶层操作被分解为多个对子图的操作由各个节点并行执行。其次，我们引入了多副本（replica）的支持，从而用户可以灵活平衡分片（shard）与副本的数量，以取得更佳的服务能力。最后，我们针对图表示学习优化了底层的图存储数据结构与操作算法，能使得单机的图操作性能获得数倍的提升。

然后，由于图学习算法的多样性以及业务的复杂性，固定的某几种甚至几十种算法实现无法满足用户的所有需求。所以在Euler设计中，我们围绕底层系统的核心能力着重设计了灵活强大的图操作算子，且所有算子均支持异构图操作。用户可以利用它来快速搭建自己的算法变体，满足独特的业务需求。Euler分布式图引擎为多种图操作包括全局带权采样节点和边、基于给定节点的邻居操作和节点/边的属性查找，提供了API。

最后，我们也在Euler中实现了多种流行的图深度学习算法，感兴趣的读者可以通过https://github.com/alibaba/euler获得更多信息。

04 阿里搜索广告应用中的使用实例

通过将搜索词Query，广告Ad和自然商品作为节点构建一个大规模图（见图3左上角），图中的边表示点击或者共同点击关系，比如有消费者搜索了“连衣裙”，然后点击了商品A和商品B，那么连衣裙和A、B之间就建设连边，同时A和B之间也建立连边。经过这样的构图，我们不难发现，当一个Query搜索后，如果消费者对某个商品C感兴趣，那么Query和商品C之间在这个图上很可能存在一条联通路径。通过在图上做图深度学习（graph embedding，图嵌入技术），每个节点的向量可以表示该节点中的结构特点，即跟这个节点联接比较紧密的节点会和该节点向量非常相似。

• 本文地址：图深度学习模型进展和在阿里搜索广告中的应用创新
• 本文版权归作者和AIQ共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出

从这个角度出发，我们设计了下文中介绍的，阿里搜索广告中基于图深度模型搭建的广告检索模块SMAD（Scalable Multi-view Ad Retrieval） [16] 。该方法使用图嵌入技术来得到Query和Ad的表征，然后通过ANN搜索（Approximate Nearest Neighbor search）来检索相关广告，从而在保证计算效率的同时使用图模型的表征能力优势提升匹配效果。

图3 搜索广告系统架构，包含了广告检索和广告排序两个阶段。在广告检索阶段，我们提出了SMAD检索算法，通过图学习的方式来学习用户搜索和广告之间的匹配关系

如图3左上所示，SMAD方法有三个核心模块：

1）大规模图构建模块。在SMAD中，Query-Item-Ad图由三种类型的节点组成，包括Query、Item和Ad，每个节点都包含ID、类目、品牌、价格等特征。图中包含三种类型的边：

• a）点击关系边。给定在一个用户搜索请求下的点击序列 s=(c_1, c_2,...,c_m) ，其中 c_i(i \in [1, m]) 代表被点击的自然商品（item）或广告商品（ad）。我们在两个被点击的Item（或Ad）节点c_i 和c_i(i,j \in [1,m]) 之间建立共同点击边，以及在每个被点击节点 c_i与Query节点q 之间建立点击边，如图3所示。* b）文本相似关系边。我们计算Query和Item/Ad标题之间的Jaccard相似性，以其作为权重来建立文本相似边。每日新增的广告可以通过这种方式加入图，实现冷启动。
• c）共同竞价关系边。广告主通常会为每个广告指定一组<竞价词，价格>，用来表达他们希望触达的流量和此广告被用户点击时支付的金额。如果两个广告至少有一个相同的竞价词，那么在它们之间建立一条共同竞价边。

2）模型训练模块（Parallel DNN）。在图中进行游走，采样节点序列，进而用这些序列来训练深度模型。具体来说，假设一个长度为3的游走序列为 v_1 -> v_2 -> v_3 ，这里 v_{1 \sim 3} 表示图中的节点，对于节点 v_i 来说，它对应的两个正样本节点为 v_2 和 v_3 ；而负样本是通过随机节点采样获取。基于采样获得的正负样本训练模型。由于图中包含多种关系，我们会针对每种关系做游走和正负样本采样，用于训练不同的子模型，即当判断两个节点v_i 和 v_j 间是否存在共同点击关系，我们会针对和的几种关系子模型的预估结果加权值来判断。

3)在线推断模块。基于学习到的ad和query表征，在线进行近邻向量检索，返回与query最相关的ad集合作为召回结果。

我们基于Euler框架实现了上述三个模块，在亿级别节点的图数据上的训练只需要几个小时的时间。线上应用表明图模型的引入确实大幅的提升了线上系统的效果，我们在线对比了包括simrank等方法，本文方法带来了1.5%以上的点击率提升，证明了这种方法确实能够帮助消费者找到更喜欢的商品推荐，感兴趣的读者可以阅读文献[16]来了解更多数据分析结果。

05 总结

图深度学习已经发展成为学术界非常火热的一个课题，在工业界也找到了不少应用点。图深度学习领域博大精深，无论是技术研究还是技术应用，都还有大量未解的问题待我们去探讨，比如：如何进行在线图推断，如何设计更加适合图的表示方法，如何把图的推理能力真正的融合到模型学习中。在图的表示层面，阿里探索了双曲空间在图表示上的应用(https://github.com/alibaba/Curvature-Learning-Framework)，并取得了一定的效果，这只是这个方向探索的一个开始，期待未来在图深度学习领域有更多的突破，有更多的成果产出。

• 本文已发表在《中国计算机学会通讯》2022年第5期

参考文献

[1] https://en.wikipedia.org/wiki/Six_degrees_of_separation#cite_note-AFC-NA-21-15.

[2] Milgram S. The Small World Problem [J]. Psychology Today. Ziff-Davis Publishing Company. 1967.

[3] Goodfellow I, Bengio Y, and Courville A. Deep learning [M]. MIT press, 2016.

[4] Henaff M, Bruna J and LeCun Y. Deep convolutional networks on graph-structured data [C]. arXiv preprint arXiv:1506.05163. 2015.

[5] Zhou J, Cui G, Hu S, Zhang Z, Yang C, Liu Z, Wang L, Li C and Sun M. Graph neural networks: A review of methods and applications [J]. AI Open, 2020, 57-81.

[6] Cai H, Zheng V, and Chang K. A comprehensive survey of graph embedding: Problems, techniques, and applications [J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 1616-1637.

[7] Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations [C]. ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2014.

[8] Grover A, Leskovec J. node2vec: Scalable feature learning for networks [C]. ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2016.

[9] Niepert M, Ahemed M, Kutzkov K. Learning Convolutional neural Network for Graphs [C]. International conference on machine learning, 2016.

[10] Bruna J, Zaremba W, Szlam A, Lecun Y. Spectral Networks and Deep Locally Connected Networks on Graphs [C]. Internetional Conference on Learning Representations, 2013.

[11] Deffererard M, Bresson X, Vandergheynst P. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering [C]. Advances in Neural Information Processing Systems, 2016.

[12] Kipf T, Welling M. Semi-supervised classification with graph convolutional networks [C]. Internetional Conference on Learning Representations, 2017.

[13] Hamilton W, Ying R and Leskovec J. Inductive representation learning on large graphs [C]. In Advances in Neural Information Processing Systems, 2017, 1025–1035.

[14] Chen J, Ma T and Xiao C. Fastgcn: fast learning with graph convolutional networks via importance sampling [J]. arXiv preprint arXiv:1801.10247, 2018.

[15] Abu-El-Haija S, Perozzi B, Kapoor A, Alipourfard N, Lerman K, Harutyunyan H, Ver Steeg G and Galstyan A. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing [C]. International conference on machine learning. 2019, 21-29.

[16] Wen S, Chen Y, Yang Z, Zhang Y, Zhang D, Wang L and Zheng B. SMAD: Scalable Multi-view Ad Retrieval System for E-Commerce Sponsored Search [B]. International Conference on Information and Knowledge Management. 2021.

[17] Veličković P, Cucurull G, Casanova A, Romero A, Lio P and Bengio Y. Graph attention networks [C]. arXiv preprint arXiv:1710.10903. 2017.