我所知道的GNN图神经网络
导语: I have a graph, a neuralised graph. 我有一个图，一个神经网络化的图。
作者简介：如算法“百晓生”，熟悉各类算法原理，典故，应用，背后八卦，心中有一本算法的“兵器谱”，又如算法“扫地僧”利用所在各公司的各种资源，或依托具体业务积累落地经验，或求教于业界大佬行业经验，或旁听于公司邀请的科学家。偶有所得，便欣然忘食。平生所爱，唯算法和剑法，情不知所起，一往而深。
本篇文章缘起：最近听了科技部高端外专项目请的GNN大牛Xavier Bresson的系列讲座，非常激动难得有人从GNN背后的图谱论，图群论，计算复杂性，工业界落地优先级等方面进行深入探讨，本文也借用和整理了一些Xavier的讲义。又有某微信算法团队邀请做了个GNN分享，所以将分享整理成文。进行发表。目前GNN大火，内外网各类文章非常多，让人眼花缭乱，多是侧重模型模块的堆叠和组合，或是在特定场景下的应用而展开，很多时候GNN对于算法同学自己来说都是黑盒缺乏了解，知其然不知其所以然，又如何让业务同学接受模型跑出来的结果，不想从炼金术升华为化学家的巫师不是好的算法工程师。鲜有文章能从图论的数学和算法脉络，以及和深度学习技术汇合来进行阐述，说外功者多，谈内功者少，在下不才，偶有所得，做些这方面的尝试。
本人做过的一些微小贡献：
1）风控率先落地一个实时的GNN在线推理服务；应用AWS Deep Graph Library和图数据库Nebula搭建了，一个社区反作弊网络和电商反交易黄牛网络。
2）蓄水池抽样算法在图数据库上使用；和Nebula合作应用蓄水池抽样算法来解决经典的热点问题, 众所周知蓄水池抽样算法最大优势是在内存一定的情况下可以等概率抽取。
3）AWS Deep Graph Library和Nvidia的合作，促使了GPU优化GNN表现进展。最早发现模型使用GPU等待闲置时间过长，因为GNN的本身神经网络是比较简单的，拉英伟达和AWS AI Lab的人联合诊断问题，后来英伟达帮助DGL实现了在GPU上的Sampler抽样，大大加快了速度和GPU使用率，将更多的计算移到GPU计算成为趋势。相关情况，在11月9日的英伟达大会上，黄仁勋有介绍。
4）参与事业群的GNN相关项目
首先我要说的是， 有很老的段子，说当科学家登上一座高山后，却发现神学家早就坐在这里。其实像GNN这个领域，当计算机科学家或是说机器学习科学家爬上了一座山峰以后，数学家已经等了我们几十年。大约快30年前，图论学家就开始研究local 算法，例如图上Global Information from local observation, 通过局部的随机游走来推测图的整体性质。当所有的点一起做Local算法的时候，其实就是分布式算法了，比如经典的消息传递Message Passing, 以及Pregel分布式图计算架构，以及GNN的每个点取自我网络，都是所有的点一起做local计算。图论学家很早就开始图上随机游走的研究，通过图上随机游走来进行计算，计算离散对象的体积，研究图上随机游走的收敛速度，如何获得指定分布等一系列问题。大家熟知的Pagerank, 就是图上马尔可夫过程。GNN在大图上有一系列的采样操作，其实都可以放在随机游走和蒙特卡洛模拟框架下来看。另外Bounded Degree就是点的邻居数有上界时候的场景下，各种本来计算复杂度高NP完全或是NP难的问题，往往有线性时间或者高效近似算法。上次有个业界AI Lab的朋友还问我，现实中Bounded Degree场景多吗，我只能说现实中都是Bounded Degree的，大家细品。
外现在常用的深度学习Embedding技术，其实图论学家很早就开始应用，著名数学家Lovasz最早开拓性的应用图的几何表示方法，把图embed到一个球面上应用不动点定理证明了Kneser猜想（这个方法最近还被Deepmind的运用证明了GNN的Aggregator学习能力上限），以及给予每个点一个坐标来证明了著名的信息论仙农猜想，最早开出了图的几何表示这门高深的学问。同时在论述离散和连续关系的文章中，也说了“embedding"技术将会是非常自然和厉害的技术来学习离散结构。现在五花八门的各种深度学习和GNN学习获得的点的向量值，不就是在做这样一件事情吗？笔者多年以前读到这段还是很难理解的，今天一切都是那么自然，Lovasz在那里等了这么多年。当然目前还有一些GAP，数学家都是非常明确图被Embedding到了什么几何对象上，而目前GNN学到了点的向量值以后并不清楚到底embed到了什么几何对象上，目前丘成桐和顾险峰对于CNN之类的深度学习到底embed到了什么流形空间上是有研究的。GNN感觉还比较难。
GNN技术主要有谱方法和空间方法两种，有人形象地把空间方法说成剑宗，用技巧解决问题。而谱方法说成气宗，需要一定的数学功底，一般计算机专业或是统计背景的同学不了解相关领域，基本公式一看就一头雾水。其实可以把谱方法看成是GNN的理论基础，而空间方法是谱方法的特殊形式和算法实现。当然理想的情况，就如令狐冲本是气宗弟子，受了剑宗高人风清扬的指点，又有内功易筋经，又有技巧极强，破尽天下拳法，掌法，剑法，刀法一切兵器的独孤九剑外功。
其实首先是图的谱方法，帮助大家把CNN的那套方法可以发展到GNN上，大家知道CNN的卷积邻居点是有空间顺序的，而且邻居点数量是固定的，图显然不符合这个要求。那么怎么办呢。大家开始运用傅里叶变化来觉得这个问题，把图傅里叶变换到频率空间，然后过一个滤波器，再转化回来。
这时候图的谱方法就引入，有本著名的书《图的谱论》是著名数学家Fan Chung金芳蓉写的，非常经典。笔者十多年前旁听过她的讲座，回答了随机游走可以用来计算的问题。一晃这么多年过去，青春逝去，唯有公式是永恒的，还有了新的应用。图的谱论主要解决了GNN谱方法对应滤波器的Smoothness问题，保证了CNN一样要求的局部性。
图的谱论是一个已经至少有几十年历史的图论分支，我们可以用各种矩阵来表示一个图点和点的边关系。这个矩阵的性质，例如特征值和特征向量，可以反应图的各种性质。拉普拉斯实际上就是计算一个点和周围点平均值的差异。十多年前初看Fan Chung的书，笔者一头雾水，很快开车到流形上，后来学了离散微分几何以后，就知道了图上拉普拉斯就是连续空间的Laplace-Beltrami Operator, 也验证了Lovasz说的，离散和连续就是一个硬币的两面。
图上拉普拉斯操作的解释，一般有组合拉普拉斯，标准化拉普拉斯和随机游走拉普拉斯。标准化拉普拉斯的好处是满足Hermite矩阵的特征值是实数。这些知识，算法的同学多有耳闻，但是因为工程门槛，少有应用，后续我们争取在算法中台产品上集成这些操作。
谱方法也经历了几个阶段，一开始最简单的就是学一个对角线矩阵，无法保证CNN那样的局部性Local学习，而且学习参数和学习复杂度很高，后来开始应用多项式方式来逼近，使得每个点的Local学习变得可能，又降低了学习参数和学习复杂度。对逼近的多项式进行低阶保留截断实际上就是空间方法。
但是看到这里大家会发现，CNN是存在异向性的，不同方向的邻居点是不同的，但是GNN还是同向性，不同邻居点都是同向性的。后面这个问题会解决。
接下来我们看看空间方法，空间方法经历了几个阶段，所有的点一视同仁，自身和邻居点有差异例如GraphSage,差异化所有的邻居点和自身。
GNN和图的同构问题的联系被挖掘和注意到，衡量GNN的学习能力可以看成是，是否能区分非同构的邻居结构。
解决异向性问题的几种方法，边上有特征值，边上有深度学习的门技术，Attention机制的引入，都能让GNN如CNN那样具有异向性特征。
比较有趣的是一个重要进展，残差，门，BN等深度学习技术都可以运用到GNN当中来，同时看见效果的提升。
残差门GCN和AWS的Deep Graph Library实现，大家可以发现一个好的上层封装，Model Zoo和针对GNN的各种优化是太重要了，尤其是大部分一线业务算法同学都不是数学和代码Geek，比较难从零推出模型和实现代码，而是需要针对业务问题快速建模，快速尝试已经知道的各种算法元素和积木，通过实验方法来得出结果。这个也是我们后面做GNN中台算法产品要努力的方向。
AWS的Deep Graph Libarary运用GPU技术优化了BN等深度学习运算。可以发现我们总是在算力和学习能力中取得平衡，可以预见深度学习技术的引用也提升了模型泛化能力。
Transformer也被运用到了GNN上，可以直观的理解，每个点的Q值也就是Query值和邻居点的K值，也就是Key值去算Match程度。同时图的拉普拉斯矩阵分解的特征向量值对应成坐标值。
目前把GNN的架构分为Message Passing GNN和WL GNN两种。
我们总是希望GNN具备可以区分非同构图能力，WL算法是一个必要条件保证两个图同构。
曾经有一个很火的公众号文章介绍了WL算法发明人背后的故事，其实专业内行圈里从来没有人忘记过。
GCN简单的编年史
下面这个图很好比较了GNN的表达学习能力，可以看见我们熟知的几个GNN模型表达能力都是弱于一阶的WL测试算法，也可以提升阶数来获得更高学习能力的WL GNN。
目前大家建立了一个Graph Open Benchmarking数据集来测试不同的GNN模型表示。发现实际上Message Passing的GNN还是超过了WL GNN。当然原因也是图的同构计算复杂无法在中等规模数据集上运行。WL GNN还在初级阶段。Message Passing GNN得益于深度学习的BN和残差技术。异向性的实现也改进了GNN的表现。
目前推荐场景使用GNN都是对于边的预测，最好是能够把两个点的相似度和距离放入特征计算，但是这样需要平方级的计算复杂度。对于边的预测很容易构造反例来证明其容易失败。如果能加入点的位置编码就能解决这个问题。
目前推荐场景使用GNN都是对于边的预测，最好是能够把两个点的相似度和距离放入特征计算，但是这样需要平方级的计算复杂度。对于边的预测很容易构造反例来证明其容易失败。如果能加入点的位置编码就能解决这个问题。
如果能给每个点一个唯一的ID作为位置编码的话，那么可以证明message passing GNN就可以超越一阶WL测试算法。同时messaage passing GNN也是图灵完备（简单想象可以近似任意函数）当神经网络深度超过图的直径，同时足够宽了以后，且每个点都是唯一编码。也可以使用拉普拉斯位置编码，拉普拉斯矩阵分解是复杂的，当然可以使用近似算法。笔者在实际工作中，也发现了邻居点如果社交影响力不一样，确实需要区分对待。可以考虑应用随机游走生成不同点和影响力正相关的向量值来近似代替位置编码，而且针对大图的这套计算，大厂都是比较成熟的了。
最后笔者谈下Deep Mind在GNN方面的进展。笔者感觉Deep Mind从真正推动人工智能发展的角度出发，追求高，立意高，成果自然也高。主要三个方面：
一）神经网络化计算机科学家- 传统算法和图神经网络打通
二）Aggregator算法的优化升级
三）Graph nets框架和TF-GNN
比如经典的最短路径问题，可以转化为一个GNN学习问题，比如大家想象最短路径算法不断经典从周围点迭代最短路径，就是一个min函数, 就是和周围点message passing下，神经网络拟合一个min函数。Deep Mind列举的经典组合算法的缺点和局限性，我是非常有感慨的，笔者曾在某厂某供应链算法团队工作过，一开始以为上接某电商，下接某物流，大量优化问题，我擅长又喜欢的组合优化算法可以大显神威。但是现实问题有时候不需要严格按照标准约束定义，比如旅行商TSB问题不需要每个边真的只走一边，Matching匹配问题不需要真的严格匹配，可以relax约束。另一方面求解的目标函数，需要加上各种正则化项和不同业务目标综合等等。也就是说现实中组合优化问题的约束和目标都不是精确的数学结构，这也是图灵奖得主John Hopcroft作为图论算法大牛曾和笔者说，他的时代过去了，以后不再是精确数学结构的求解，而是概率推断和近似。这个时候GNN神经网络框架就可以在一个Learning框架下输出结果。当然GNN运用于组合优化问题求解，在结果上已经逼近了Gurobi等商业软件，但是不像经典近似算法那样把近似的Factor求解出来。这也是需要计需努力的地方。
另外Deep Mind证明了当特征值是连续值时候的Aggregator能力上限，当Aggregator数量小于一定数量时候，是无法保证不同图结构可以满足入射的，运用了前面提过的Lovasz最早使用过的Borsuk-Ulam定理在图论猜想证明。提出了Moments也就是升阶方法，在公开数据集测试上超过了其它GNN模型。笔者是非常欣赏这个方向，大家很多时候都专注于搭乐高积木那样的模型组合叠加，而对Aggregator和Sampler这些基础算子缺乏研究和拓展，同时这些算子如何运用GPU去高效实现也是非常有趣的领域。笔者后续在GNN上的工作将沿着这些方向，不追求复杂性的乐高积木叠加，而是基础算子的突破。
笔者本科时候读过的经典书籍，使用Borsuk-Ulam定理在图论和组合学上，没想到多年以后在GNN这里遇上了。
最近Google又推出了Tensorflow GNN, 就像Keras至于TF那样，大家可以轻松自如定义和实现GNN. 这里有Deep Mind的参与。
当然GNN还有大量的主题没有涉及，比如GNN的可解释性问题，很多时候尤其是风控可解释性是制约模型被业务使用的卡脖子问题。另外GNN的反例攻击鲁棒性，笔者最近和一个学术合作者建议了把Cost纳入考虑，比如不同的黑产绕过手段，真边假点，假边真点，假边假点，真边真点都有不同的Cost，提升黑产成本也是风控重要问题，黑产总不能为了多薅一个红包而多买一个手机。如果将来做一个模型都能预估绕过的最小Cost也是风控模型一个有趣的方向。本文主要是从神经网络的结构出发来说，现实中还有个重要问题就是如何训练，训练又是一个更难的问题，进入了调（炼）参（丹）环节。边的预测如何进行合适高效的负采样在社交网络上也是有趣和有深度问题。还有社交网络小世界特性引发的over smoothess问题也是方向。
追求技术的人有时候又是寂寞的，就像王实甫写《西厢记》，”寄语茫茫天涯,何处锦绣才子,吾欲与君挑灯促席,浮白欢笑,唱之,诵之,讲之,辩之,叫之,拜之,世无解者,烧之,哭之. “ 笔者寥寥数语，阐述我所知道的GNN，也是"嘤其鸣矣，求其友声"希望能找到志同道合的同事们。
