好的软件不是靠程序分析和错误检查来构建的，而是靠对的人。图已成为越来越重要的计算对象。图结构是对组关系的抽象，可以描述丰富的对象和关系。图计算的核心是如何将数据建模成图结构，以及如何将问题的解转化为图结构上的计算问题。当问题涉及到关联分析时，图计算往往可以使问题的求解自然地表达为对图结构的一系列操作和计算。例如，利用基于网页链接图结构的PageRank算法获取网页权重，作为搜索引擎排名的参考，利用图结构的用户行为数据获得精准的群体偏好分析和个性化产品推荐结果。1.什么是图计算？图计算是研究人类世界中事物与事物之间的关系，并对它们进行描述、表征、分析和计算的技术。这里的图是“图形”，而不是“图像”，它来源于数学中的图论。图是最灵活的连接方式，可以让实体之间不受限制地连接起来。图计算不仅仅是一种技术，更是一种认识世界的方式。图数据可以很好地描述事物之间的联系，包括描述联系的方向和属性。从数据结构的角度来看，图是事物之间关系的原生表达。在某种程度上，关系数据库应该称为表数据库，而图数据库应该称为关系数据库。广义的图计算是指基于图数据的各种处理，包括图数据库。图计算技术解决了传统计算模式下关联查询效率低、成本高的问题。完整描述问题域内的关系，具有丰富、高效、敏捷的数据分析能力。其特点如下：基于图抽象的数据模型图数据模型并行抽象图模型系统优化对于图计算，性能成本、容错机制和可扩展性都非常重要。2.从历史发展来看，图计算图计算可以追溯到1960年代的面向树结构的数据库，70、80年代出现了面向属性图的模型和技术，如LDM（LogicalDataModel).直到2007年，第一个商用图数据库Neo4j公司成立，标志着图计算进入发展阶段。图计算研究的真正开端是2004年谷歌开发的MapReduce大数据并行处理计算模型，该模型的引入对大数据并行处理产生了巨大的革命性影响。随后，在2006年，ApacheHadoop团队推出了Hadoop分布式文件系统(HDFS)和新的HadoopMapReduce框架。2009年，加州大学伯克利分校的AMP实验室开发了Spark系统。2010年以来，大规模分布式架构、多模态支持、图查询语言设计等图计算研究方向逐渐受到关注。Google提出了Pregel，一种针对图算法特点设计的分布式图计算系统，遵循BSP计算模型；之后，CMUSelectLaboratory的GraphLab项目组提出了GAS计算模型。.Pregel和GraphLab虽然都是针对迭代计算的复杂机器学习计算的处理框架，但是两者的实现方式走的是不同的路径：Pregel是基于大块消息传递机制，而GraphLab是基于内存共享机制已有对其他后续图计算系统的设计产生了深远的影响。谷歌于2012年5月提出知识图谱的概念，是一种全新的信息连接方式。它的基本单位是“实体-关系-实体”的三元组。塑造知识结构。知识图谱建立的核心是计算机的知识推理机制，图计算为其提供了重要的底层技术支持。2015年，随着数据量的快速增长和应用市场的逐步开放，对图计算系统的可扩展性和效率的需求持续增加。国内图计算领域的学术界和产业界开始逐步发力，发布了自己的图计算系统和平台，如清华大学的Gemini等。近年来，随着人工智能技术的发展，图神经网络也在业界大显身手。3、从框架模型看图计算图计算的框架基本遵循BSP（BulkSynchronousParallell）计算模型。BSP模式的批量同步（bulksynchrony）机制，其独特之处在于引入了超步（superstep）的概念。一个计算过程由一系列全局超步组成，每个超步包括三个阶段：并行计算（本地计算）、全局通信（非本地数据通信）和栅栏同步（等待通信行为结束）。BSP模式具有以下特点：计算逐个超步进行，有效避免了死锁；处理器和路由器分离，强调计算任务和通信任务的分离，而路由器只完成点对点的报文传输，不提供组装、复制、广播等功能，不仅隐藏了具体的互连网络拓扑结构，也简化了通信协议；采用同步方式硬件实现的全局同步和可控的粗粒度级别，执行紧耦合的同步Parallel算法。一些有代表性的图计算框架如下：Neo4j-APOC：基于图数据库，支持一些基本的图算法，分布式版本不开源。Pregel：2009年由谷歌提出，是图计算模型的奠基者，后来的很多作品都受到其思想的影响。不开源。Giraph：Facebook基于Pregel思想的开源实现。Gemini：清华大学在Pregel思想的基础上进行了多项改进，性能优异。只提供免费的demo，商业版不开源。KnightKing：专为Walker算法设计的图计算框架，不具有通用性。GraphX：Apache基金会基于Spark实现的图计算框架，社区活跃。GraphLab（PowerGraph）：商业软件，非开源。已被苹果收购。Plato：腾讯基于Gemini和KnightKing思想的C++开源实现。它是一个高性能、可扩展、可插拔的图计算框架。4.从算法的角度看图计算图算法是指利用指定的顶点和边求出答案的一种简单方法。无向图、有向图和网络可以使用许多常用的图算法。对于图数据，遍历算法（深度/广度优先）是其他算法的基础。典型的图算法包括PageRank、最短路径、连通分支、最大独立集、最小生成树和贝叶斯置信传播等。图的最小生成树往往代表最低成本或生命中的最小成本，Prim的算法和Kruskal的算法是常用的。社区发现、最短路径、拓扑排序、关键路径也有相应的算法。图算法包括多种数据分析技术，例如搜索、匹配、分类和评估。从算法结构来看，大致可以分为两类：以遍历为中心的算法和以计算为中心的算法。以遍历为中心的算法需要以特定的方式从特定的顶点遍历图，涉及大量的随机访问。以计算为中心的算法需要在一个迭代周期内进行大量运算，数据局部性相对较好。5.从计算机体系结构角度看图计算图计算一般是数据驱动的计算，运行前无法准确预测计算结构。形状上没有明显的花纹，难以高效优质地划分。现有的缓存机制只能加速局部性好的数据访问，大量数据的访问会使处理器频繁处于等待I/O的状态。图计算的工作负载是复杂的，没有单一的最具代表性的图计算负载。连接顶点的边只是无限数量的可能连接的一小部分，并且是高度不规则的。在图计算过程中，读写的时空局部性难以把握，带宽使用量难以预测。大多数算法可能占用不到50%的内存带宽。是什么限制了内存带宽的使用？处理器需要取指令，指令窗口之间有空间，寄存器操作数需要等到操作数可用，相关的依赖就会被释放。由于指令命中率高，内存层面的并行度可能会降低，难以充分利用平台的内存带宽。较低的缓存数据使用率意味着应用程序很难从空间局部性中获益，数据预取策略将失败。数据预取一般对性能提升有帮助，但也会产生很多无用的预取操作。对于内存带宽或缓存容量有限的应用，数据预取可能会造成一定的资源浪费。在多线程计算的情况下，如果触发了更高延迟的远程内存访问，多线程的好处也会被抵消。图计算需要什么样的处理器内核？一般采用小计算核心多、线程数高的架构，适合处理传统多核处理器不擅长的大规模计算。多图并发计算时，有两种策略：共享分配和独占分配。共享分配策略是指m个请求中的每一个都使用n个逻辑核并行处理，不同请求在逻辑核上的切换由OS管理。独占分配策略是指为每个请求分配n/m个逻辑核，使得逻辑核不需要在任务之间切换。独占分配策略更适合并发图计算，独占分配通常可以减少同一并发请求下的整体运行时间。重新排序缓存的低争用可能是独占策略在并发图计算场景下优于共享策略的原因。就图形计算产生的功耗而言，负载变化导致系统功率波动，会出现峰谷交错的情况。如果增加并发任务，将会改变峰谷比并增加功耗。一般来说，在CPU功耗方面，以计算为中心的算法平均每条指令消耗的能量更多，而以遍历为中心的算法则相反；平均能耗小，以遍历为中心的算法则相反。大多数基于图计算的应用都是内存受限的，但也存在受核心组件限制导致内存利用率不足的情况。足够的活动线程创建并发访问，这可能会提高利用率。需要更多的线程，但由于线程之间的不平衡可能无法有效使用，需要提供更具可扩展性的并行策略来优化多核处理器的高带宽内存使用。从指令和顶点计算的角度来看，功耗和能量消耗的行为是不同的。需要精确的功耗管理方法，大量调整可能不会有效。6、从系统看图计算根据大规模图计算系统的使用场景和计算平台架构的不同，可以分为单机内存图计算系统、单机外存图计算系统、分布式内存图计算系统和分布式图计算系统。外存图计算系统。单机内存图处理系统是运行在单机环境下，将所有图数据缓存到内存中的图处理系统。单机外存图处理系统是图处理系统运行在单机环境下，通过计算不断与内存、磁盘交互图数据的高效图算法。分布式内存系统是运行在分布式集群环境中的图处理系统，所有的图数据都加载到内存中。分布式核外图计算系统将单机核外系统扩展成集群，可以处理万亿边的图。7.从人工智能看图计算人工智能与图计算融合产生的图神经网络（GNN）是目前发展迅速的重要领域。各种实体之间的关系数据，它如何与神经网络结合？图神经网络使用表示学习，首先利用图的结构用向量表示每个节点或边，然后进一步使用神经网络进行处理。这扩大了神经网络的使用范围，将实体之间的关系带入了AI的处理中。图神经网络可以看作是图特征的学习过程，例如节点的代表特征或图级代表特征。通常，图属性和图结构作为输入，输出一组更新的节点表示。这个过程一般也称为图过滤操作。图过滤更新节点特征但不改变图结构。图神经网络的发展源于不同的理论动机。例如，如果把GNN看成是非欧距离的卷积提升，它是基于图信号发展起来的；大多数基于GNN的神经消息传递方法是由一种消息传递算法提出的，用于类比图模型中的概率推理。无论是谱方法还是基于空间的思想，图神经网络最终都可以统一在基于消息传递的框架下。GNN消息传递框架的基本思想是每个节点在每次迭代时聚合其邻居节点的信息。随着迭代次数的增加，每个节点包含图上更大范围的信息。例如，经过k次迭代，中心节点可以获得其k-hop邻域的信息。它的关键思想是基于图结构和已知特征信息生成节点表示。GNN利用图上的结构和节点特征信息生成深度嵌入表示，而传统的图嵌入方法仅利用图的结构信息通过查表生成层嵌入。7.1GNNVSMLP/CNN/RNN图数据中节点的邻居有两个特点，一是数量不确定，二是顺序不确定，所以MLP/CNN/RNN无法直接处理此类非欧数据并且只能用GNN建模。事实上，GNN可以看作是一种更泛化的模型。例如，RNN相当于线性图上的GNN，Transformer相当于完全图上的GNN。7.2GNNVSGraphEmbedding许多GraphEmbedding方法在GNN之前已经出现，并广泛应用于搜索服务的向量召回阶段。这类方法受到Word2vec的启发，从最初的Item2Vec到Node2Vec基于平衡同质性和Structural的改进，基于MetaPath2Vec的图异质性改进，引入属性数据缓解行为数据的稀疏性，这些方法都遵循Skip-克范式。与这些方法相比，GNN可以端到端的结合目标任务进行训练，而GraphEmbedding更像是预训练，其学习到的Embedding不一定与目标任务相关，尤其是在业务场景中样本量大。端到端训练得到的Embedding比预训练得到的Embedding更有效。GNN的分层网络结构便于与其他深度学习技术结合，如GCN+Attennotallow=GAT。GNN可以应用于Inductive任??务，即当图的结构发生变化时，增加一些新的节点。如果是GraphEmbedding方式，需要重新训练模型，GNN可以使用类似GraphSageNode-WiseSampling的方式。训练好的模型直接推断出新的节点，在消息传递的过程中可以使用各种特征。7.3GNNVSFeatureConcat&CollaborativeFiltering&ProximityLossFeatureConcat就是将特征拼接在一起，然后通过特征交叉学习一阶属性关联信息。CollaborativeFiltering也可以通过用户历史行为学习一阶行为关联信息。ProximityLoss是指在损失函数中加入正则项使得相邻节点更相似，但一方面是一种隐式方法，另一方面如果要保证学习到高阶相似关系，则需要添加更复杂的。K阶正则项也是GCN提出时的出发点之一。与这三种方法相比，GNN可以通过堆叠多个层来显式学习高阶关联信息。图神经网络的设计中有一个关键条件要满足，即置换不变性或置换等可变性，即设计的函数在处理图数据时不受节点顺序的影响，或者顺序输入和输出是一致的。.8.汇总图是最灵活的连接方式，让实体连接不受限制。图计算是研究如何在海量数据中高效计算、存储和管理图数据的领域。可应用于资本市场风险管理、生命科学研究、医疗服务、交通事故监测与应对等广泛的业务场景，智能基础设施管理等。高效处理大规模数据的图计算可以促进新兴应用领域的发展，例如社交网络分析，语义网分析，生物信息学网络分析和自然语言处理。【参考文献】《人工智能的图计算》，清华大学人工智能研究院，北京智远人工智能研究院，清华-工程院知识智能联合研究中心，2019-2https://zhuanlan.zhihu.com/graphComputinghttps://www.zhihu.com/column/c_1496512305013219328https://www.aminer.cn/oag2019https://www.oreilly.com/library/view/图算法/9781492047674
