引言：近年来，作为一种新的图形数据学习技术，图形神经网络(GNN)受到了广泛关注。2023年底，发生了一件很有意思的事情，三篇综述论文同时发表在这个领域。这种“不约而同”体现了学术界对这项技术的认可。
事实上，在2023年的顶级学术会议中，与图神经网络相关的论文也占据了相当大的份额。我相信这种流行趋势在未来几年只会越来越多。
本文从“图”入手，带你了解图神经网络的概念和应用。
作者：刘忠玉，李彦霖，周洋
来源：华章科技
01图形(Graph)的基本定义是一个具有广泛含义的对象。在数学中，图是图论的主要研究对象；在计算机工程领域，图是一种常见的数据结构。在数据科学中，图被广泛用于描述各种关系数据。许多图学习理论关注于与图数据相关的任务。
通常，图表用于显示对象之间的关系。生活中有很多与此对应的现实系统，比如化学分子、通讯网络、社交网络等。事实上，任何包含二元关系的系统都可以用图来描述。因此，研究和应用图的相关理论具有重要的现实意义。
本文主要介绍了与图相关的一些基本概念，包括图的基本定义，图在计算机中的存储和表示方法以及遍历方法，图数据及其常见的应用场景，以及对图数据深度学习的简单介绍。
在数学中，图由顶点和连接顶点的边组成。顶点代表被研究的对象，边代表两个对象之间的特定关系。
图可以表示为顶点和边的集合，记为G=(V，E)，其中V是顶点的集合，E是边的集合。同时，我们假设图G的顶点数为N，边数为M(除非另有说明，文中所有的图都是这样表示的)。连接顶点vi，vjV的边被表示为(vi，vj)或eij。如图1-1所示，V={v1，v2，v3，v4，v5}，e={(v1，v2)，(v1，v3)，(v2，v4)，(v3，v4)，(v4，V5)}。
图1-1图G的定义
02图的基本类型1。有向图和无向图
如果图中的一条边具有方向性，则称为有向边eij=，其中vi是这条有向边的起点，vj是这条有向边的终点。包含有向边的图称为有向图，如图1-2所示。有向图对应无向图，无向图中的所有边都是无向边。我们可以认为无向边是对称的，同时包含两个方向：eij===eji。
图1-2有向图
2.未加权图和加权图
如果一个图的每条边都有一个实数与之对应，我们称这样的图为加权图，如图1-3所示。实数叫做相应边上的权重。在实际场景中，权重可以表示两地之间的距离或运输成本。通常，我们习惯于将权重抽象为两个顶点之间的连接强度。与未加权图相反，我们可以认为未加权图各边的权重是相同的。
图1-3加权图
3.连通图和不连通图
如果一个图中有孤立的顶点，而没有边与之相连，这样的图称为不连通图，如图1-4所示。相反，没有孤立顶点的图称为连通图。
图1-4断开图
4.偶图
二部图是一种特殊的图。我们把G中的顶点集V拆分成两个子集A和B，如果图中任意一条边eij都有viA，vjB或viB，vjA，则称图G为二部图，如图1-5所示。Bigraph是一种非常常见的图形数据对象，它描述了用户与商品、作者与论文这两类对象之间的交互。
图1-5二分图
03图形数据的应用场景我们所指的图形，在数学上更多的是一种理论色彩。在实际的数据场景中，我们通常把图称为网络。相应地，图的两个元素(顶点和边)也称为节点和链接，如社会网络和物流网络等众所周知的概念。
以达到统一性，并与神经网络中的“网络”概念相区别(虽然神经网络也是一个网络)。
图形是一种复杂的数据类型，分类很多。这里我们介绍四种最重要的类型：同形图、同构图、属性图和由非关系数据构造的图。
Co-composition: Co-composition是指图中只有一个节点类型和关系类型。共同组成是实际图形数据的最简单情况，例如由超链接组成的万维网。这种图形数据的所有信息都包含在邻接矩阵中。异形词：与同形词相反，异形词是指一个图中不止一种节点类型或关系类型。在现实场景中，我们通常研究的图形数据对象是多类型的，对象之间的交互也是多样的。因此，异构图可以更接近现实。属性图：与异构图相比，属性图给图数据增加了额外的属性信息，如图1-9所示。对于属性图，节点和关系都有标签和属性。这里，标签指的是节点或关系的类型，例如，节点的类型是“用户”，属性是节点或关系的附加描述信息，例如“用户”节点可以具有诸如名称、注册时间、注册地址等属性。属性图是工业图数据最常见的表示方式，可广泛用于各种业务场景的数据表示。非显式图：非显式图是指没有明确定义数据之间的关系，需要按照一定的规则或计算方法来表示数据之间的关系，然后将数据作为一种图数据来研究。比如计算机三维视觉中的点云数据，如果我们把节点之间的空间距离转换成关系，点云数据就会变成图形数据。图1-9属性图
当我们研究各种对象系统时，图形是一个非常重要的视角。在现实世界中，图数据的应用场景非常广泛。下面举几个例子来说明，如图1-10所示。
图1-10数据应用示例[1，19]
社交网络(Social networking)社交网络是一种非常常见的图表数据，它表示各种个人或组织之间的社交关系。图A如图1-10所示，显示了在线社交网络中用户对网络的关注度：用户是节点，用户之间的关注关系是边。这是典型的共构图，一般用于研究用户的重要性排名和相关的用户推荐。
随着移动互联网技术的发展，社交网络中加入了更加多样化的媒体对象，如短文本、视频等。使异构图可以完成更多样化的任务。
网上购物网上购物是互联网上的一种核心业务。在这种场景中，业务数据通常可以用用户-商品的二分图来描述。在图1-10所示的例子中，节点分为两类：用户和商品，已有的关系包括浏览、收藏和购买。
用户和商品之间可以有多种关系，既有收藏关系，也有购买关系。这种复杂的数据场景很容易用属性图来描述。电子购物催生了一个众所周知的技术应用——推荐系统。用户与商品的互动关系反映了用户的购物偏好。比如啤酒和纸尿裤的经典故事：喜欢买啤酒的人通常更喜欢买纸尿裤。
化学分子以原子为节点，以原子间的化学键为边。我们可以把分子作为一种图形数据来研究。分子的基本组成和内部关系决定了分子的各种物理化学性质。通常我们用它们来指导新材料和药物的研究任务，如图1-10的图C所示。
网络交通网络有多种形式。例如，在地铁网络中，每个站点作为一个节点，站点之间的连通性作为一条边，形成一张地图，如图1-10的图D所示。通常，在交通网络中，我们更关注与路径规划相关的问题：例如，最短路径问题，例如，我们将交通流量视为网络中节点的属性，以预测未来交通流量的变化。
场景图场景图是图像语义的描述。它把图像中的对象看作节点，把对象之间的关系看作边来构成一个图。场景可以将关系复杂的图像简化成关系清晰的语义图。场景有非常强大的应用场景，比如图像合成、图像语义检索、视觉推理等等。
图1-10中的图E展示了一个从场景图合成相关语义图像的例子。在这个场景图中，描述了五个对象：两个男人、一个孩子、一个飞盘、一个院子以及他们的关系。可见，场景图具有很强的语义表示能力。
电路设计我们可以以谐振器等电子器件为节点，以器件之间的连线为边，将电路设计抽象成一种图形数据。参考文献[1]将电路设计抽象为如图1-10的图F所示，然后基于图形神经网络技术对电路的电磁特性进行仿真拟合。与严格的电磁公式模拟相比，在可接受的误差范围内，可以大大加快高频电路的设计。
图数据的应用场景远不止这些，还有描述神经网络、传感器阵列网络、各种智能传感器组成的物联网的计算过程的计算图。事实上，如果要寻找真实数据对应的最具代表性的数据描述语言，那么graph应该是最具竞争力的候选。一般来说，图数据的应用跨度大，应用场景多，因此研究图数据具有广泛而重要的现实意义。
作为一种重要的数据类型，图数据的深度学习对图数据分析和学习的需求日益突出，许多图学习理论都聚焦于与图数据相关的任务学习。
谱图论[2]是图论与线性代数相结合的理论。基于这一理论，谱聚类相关算法[3]可用于解决图的分割或节点聚类问题。
统计关系学习[4]是一种结合关系表示和似然表示的机器学习理论。与传统的机器学习算法假设数据相互独立且同分布不同。统计关系学习打破了上述对数据的两个假设，更适合图形数据学习。
为了更好地拟合实际场景中的异构图数据，提出了异构信息网络[5]分析，挖掘异构图中更全面的结构信息和丰富的语义信息。
由于近年来深度学习在实际应用中取得的巨大成就，表征学习和端到端学习的概念越来越受到重视。为了从复杂的图形数据中学习到具有足够信息的矢量化表示，出现了大量的网络嵌入方法[6]。然而，网络表征学习很难提供一个具有表征学习和任务学习的端到端系统。基于此，图数据的端到端学习系统仍然是一个重要的研究课题。
由于图形数据本身结构的复杂性，直接定义一套支持推导的计算框架并不直观。与图形数据相对应的数据是图像、声音和文本，它们是在欧洲空间中定义的规则结构数据。基于这些数据的张量计算系统自然高效。
图1-11显示了图形数据和其他常见类型数据的比较。图像呈现规则的2D网格结构，与卷积神经网络的作用机制有很好的对应关系。文本是一种有规律的序列数据，这种序列结构对应着循环神经网络的作用机制。
图1-11图像和语音文本数据类型
受图形信号处理中卷积滤波定义的启发[7]，近年来发展了一套基于图形卷积运算的神经网络理论。本文将这些方法统称为图形神经网络(GNN[8-10])。先简单描述一下它的发展。
2005年，Marco Gori等人发表论文[11]，首次提出了图神经网络的概念。在此之前，处理图形数据的方法是在数据预处理阶段将图形转换成一组矢量。这种处理方法最大的问题是图中的结构信息可能会丢失，得到的结果会严重依赖于图的预处理。GNN的提出是为了在图形数据上直接框定学习过程。
随后，在2009年的两篇论文[12，13]中，它进一步阐述了图神经网络，并提出了一种监督学习方法来训练GNN。然而，这些早期的研究是迭代的，通过递归神经网络传播邻居信息，直到它们达到稳定和固定的状态，以学习节点的表示。这种计算方法耗费大量资金，相关研究开始关注如何改进这种方法以减少计算量。
2012年前后，卷积神经网络开始在视觉领域取得显著成就，于是人们开始考虑如何将卷积应用于图神经网络。2013年，布鲁纳等人首次将卷积引入到图形神经网络中，并基于引文[14]中频域卷积运算的概念开发了图形卷积网络模型，首次将可学习的卷积运算用于图形数据。
此后，有人提出对这种基于频域图形卷积的神经网络模型进行改进和扩展。而基于频域卷积的方法需要同时处理整个图形，需要承受矩阵分解的高复杂度时间，使得学习系统难以扩展到大规模图形数据的学习任务，于是基于空间域的图形卷积被提出并逐渐流行。
2023年，Kipf等人[15]简化了频域图形卷积的定义，使图形卷积的运算可以在空域中进行，大大提高了图形卷积模型的计算效率。同时，得益于卷积滤波的高效率，图卷积模型在很多与图数据相关的任务中取得了显著的成绩。
近年来，基于空间图形卷积[16-18]的神经网络模型的更多变体得到了发展，我们将这些方法统称为GNN。各种GNN模型的出现，大大加强了学习系统对各种图形数据的适应性，也为各种图形数据的任务学习打下了坚实的基础。
从此，图数据和深度学习第一次真正结合起来。GNN的出现实现了图数据端到端的学习模式，为图数据众多应用场景中的任务提供了极具竞争力的学习方案。
在本文的最后，我们给出了一个与图数据相关的任务分类作为结尾。
1.节点级的任务。
节点级的任务主要包括分类任务和回归任务。虽然这类任务是预测节点的属性，但是很明显模型不应该建立在单个节点上，还应该考虑节点之间的关系。节点层面的任务很多，包括论文引用网络中论文节点的分类，工业在线社交网络中用户标签的分类，恶意账号检测等。
2.链接级别的任务
边缘层的任务主要包括边缘分类和预测。边缘的分类是指预测边缘的一些性质；边缘预测是指两个给定节点之间是否会形成边缘。常见的应用场景，比如在社交网络中，以用户为节点，将用户之间的注意力关系建模为边，通过边预测实现社交用户的推荐。目前，边缘层的任务主要集中在推荐业务上。
3.图形级的任务
图级的任务不依赖于一个节点或一条边的属性，而是基于图的整体结构实现分类、表示和生成的任务。目前，图级的任务主要应用于自然科学研究领域，如药物分子和酶的分类。
参考
[1]张g，何h，卡塔比d。电路-GNN:面向分布式电路设计的图神经网络[C]//机器学习国际会议，2023: 7364-7373.
[2]钟福瑞光谱图论。美国数学学会，1997年。
[3]冯卢克斯伯格。谱聚类教程[J]。统计与计算，2007,17(4): 395-416。
[4]柯勒d，弗里德曼eroski S，等。统计关系学习导论[M]。麻省理工学院出版社，2007年。
[5]石c，李y，张j，等。异构信息网络分析综述[J]。电气电子工程师学会知识与数据工程汇刊，2023,29(1): 17-37。
[6]崔平，王x，裴军，等。网络嵌入研究综述[J]。电气电子工程师学会知识与数据工程汇刊，2023,31(5): 833-852。
[7]舒曼迪，纳朗斯凯，弗罗沙p，等。图上信号处理的新兴领域：将高维数据分析扩展到网络和其他不规则领域[J]。电气电子工程师学会信号处理杂志，2013,30(3): 83-98。
[8]周，崔，张，等。图形神经网络：方法与应用综述[J]。arXiv预印本arXiv:1812.08434，2023 .
[9]张中，崔平，朱伟。基于图的深度学习研究综述[J]。arXiv预印本arXiv:1812.04202，2023 .
[10]吴，潘，陈，等。图神经网络综述[J]。arXiv预印本arXiv:1901.00596，2023 .
[11]戈里米、蒙法迪尼克、斯卡塞利弗一种在图域中学习的新模型[C]//2005年会议录年电气电子工程师学会神经网络国际联合会议IEEE，2005年。年，2: 729-734。
[12]米凯丽A。用于图的神经网络：一种上下文构建方法[J]。电气电子工程师学会神经网络汇刊，2009,20(3): 498-511。
[13]斯卡塞利f，戈里m，Tsoi A C，等。图神经网络模型[J]。神经网络汇刊，2008,20(1): 61-80。
[14]布鲁纳j，扎伦巴w，Szlam A，等。图的谱网络和局部连通网络[J]。arXiv预印本arXiv:1312.6203，2013 .
[15]基普夫TN韦林基于图卷积网络的半监督分类[J]。arXiv预印本arXiv:1609.02907，2023 .
[16]汉密尔顿W、英Z、莱斯科维奇大型图上的归纳表征学习[C]//神经信息处理系统进展。2023: 1024-1034.
[17]韦利科维p，库库鲁尔g，卡萨诺瓦一，等。图形注意网络[J]。arXiv预印本arXiv:1710.10903，2023 .
[18]吉尔默J，舍恩霍尔茨S，赖利P等。量子化学中的神经信息传递[C]//第34届机器学习国际会议录-第70卷。JMLR .org，2023: 1263-1272 .
[19]约翰逊j，古普塔一，飞飞我。从场景图生成图像[C]//IEEE计算机视觉和模式识别会议录.2023: 1219-1228.
延伸阅读《深入浅出图神经网络》
推荐语：极验人工智能图项目团队倾力之作！从原理、算法、实现、应用四个维度详细讲解图神经网络，理论与实践相结合。白翔、俞栋等学术界和企业界领军人物强烈推荐。
关于作者：刘忠雨，毕业于华中科技大学，资深图神经网络技术专家，极验科技人工智能实验室主任和首席技术官。在机器学习、深度学习以及图学习领域有6年以上的算法架构和研发经验，主导研发了极验行为验证、深知业务风控、叠图等产品。
李彦霖，毕业于武汉大学，极验人工智能实验室技术专家。一直从事机器学习、深度学习、图学习领域的研究工作。在深度神经网络算法研发、图神经网络在计算机视觉以及风控中的应用等领域实践经验丰富。
周洋，工学博士，毕业于武汉大学，目前在华中师范大学任教。曾受邀到北卡罗莱纳大学访学，长期在大数据挖掘前沿领域进行探索和研究，并应用于地理时空大数据、交通地理等诸多方向，已发表SCISSCI及核心期刊论文10余篇。
