楠姐技术漫话：图计算的那些事

大家好，欢迎来到IT知识分享网。

不知道大家在平时的工作中

有没有听说过“图计算”这个名词

但大家一定在各工作汇报，技术分享中听说过“智能化”，“人工智能”这样的字眼

而我们今天要唠的这个图计算

就是人工智能领域内近几年炙手可热的前沿宠儿

也是我们风控反欺诈中常用的“大杀器”

在了解图计算之前

首先得了解什么是“图”

我们今天所说的图

其实是用于表示对象之间关联关系的一种数据结构

具有很强的抽象性和灵活性

在结构和语义等方面具有很强的表示能力

正是由于图结构丰富的表现力

在现实生活中有很多可以表示为“图”的例子

例如社交网络、道路网、金融交易等

研发或者算法相关的小伙伴们都知道

我们常用的机器学习和深度学习算法

大多都是用于处理一些规整、有序，或者结构化的数据

比如矩阵、图片、文本、序列等

且所处理的数据都是被假设是独立同分布的

然而图上的节点都是自然相连

这也就表明节点之间不是独立的

此时，今天我们要提的图计算就来了

它的核心正是为了将数据建模为图结构

并解决如何将问题解法转化为图结构上的计算问题

当算法任务涉及到多个体之间关联分析时

图计算往往能够使得问题能很自然地表示为一系列对图结构的操作和计算

但是图计算所需要解决的问题多种多样

难以使用一套计算模式解决所有的问题

接下来我们就来系统地盘一盘

关于图计算的那些事儿

— ★ —

比如，借助边是否有方向

图可以分为有向图和无向图

借助边是否有权重

图还能分为有权图和无权图

借助图中的点和边是否具有多种类型

图又能分为同构图和异构图

还有，借助图结构和图信息是否随时间变化

图能分为静态图和动态图

“度”和“邻居”

是涉及图节点的两个重要概念

节点的“度”是指的与之相连的节点个数

如果是有向图，还会区分“入度”、“出度”

节点的“邻居”则是指与之相连的其他节点

关于图的表示

还有几个基础概念是不得不提的

一个是“邻接矩阵”

用于量化表示节点之间的边关系

还有就是“节点特征”和“边特征”

用于表征节点和边的特有数值属性

无论多么复杂的图算法模型

都是基于这些基本概念进行的

提一个关于图的最基本的问题——节点表征问题

就是如何基于以上的图的信息和属性

对图中的节点或者边进行量化表示

在CV和NLP任务中

我们会设计CNN和RNN模块

来建模图像像素点和文本文字表征的信息

在图的表征学习中也是一样的思路

有了合理的节点向量表示

我们就可以探索各类下游任务

比如进行节点分类

找出那些拥有特殊表现或属性的节点

或者进行社群划分

找出那些聚集性最强、相似性最高的节点集合

另外，还可以进行链接预测、子图划分等各种下游任务

想借助图计算做什么

完全取决于你的实际需求

看到这里

就可以恭喜你

你已经入门图计算了

— ★ ★ —

图计算其实并不是新兴的算法

对它进行历史溯源的话

欧拉被认为是人类历史上最伟大的数学家之一

由于他对哥尼斯堡七孔桥问题的描述

图论学科便继而产生

在哥尼斯堡的一个公园里

有七座桥将普雷格尔河中两个岛与河岸连接起来

欧拉于1736年研究并证明了此问题

他把问题归结为“一笔画”问题

并证明一笔画的走法是不可能的

在他的研究过程中

就把问题中的陆地与桥分别抽象为点和边

并形成了一个简单的拓扑图

引出了关于图的基础概念

在那之后，出现了图论的一个早期应用——地区渲染（染色）

随着15—17世纪大航海时代的到来

以及法国大革命之后民族国家概念的兴起

世界各国都开始绘制更高精度的地图

而绘图中如何用最少的颜色来保证相邻的两个区域（国家、州、省）

用不同的颜色区别开来的问题就是个经典的图论问题

19世纪中叶，数学家们以手工计算的方式证明了“五色地图”的问题

而直到整整一个世纪之后的1976年

才在计算机的算力的帮助下初步证明了“四色地图”的可行性

并通过图计算优化后

以四色图取代了五色图

以上地图上色问题是数学中典型的NP完全问题

例如导航、资源调度、搜索和推荐引擎

然而这些场景所对应的大数据框架及解决方案

在最开始

并没有真正意义上使用原生化的图存储与计算模式

换句话说，人们依然在用列数据库

甚至文档数据库来解决图论问题

低效低维的工具被用来强行解决复杂高维的问题

那么它的用户体验可能很差或者是投入产出比极为糟糕

最近几年，随着互联网的发展

知识图谱逐步深入人心

图计算和图数据库的发展才开始重新受到重视

近半个世纪，也有很多图计算的算法问世

包括1956年出现的知名Dijkstra算法

研究解决了图的最短路径问题

更复杂的各类社区发现算法也应运而生

用于检测社区、客群、嫌疑人之间的关联

就是将图中的每一个顶点都表示成一个低维向量

并使该向量能够尽可能多的保存图的结构和内容信息

并可以作为特征用于后续的学习任务

如节点分类、链接预测等

这些工作针对同构图、异构图、属性图、动态图等不同类型的数据

提出了各式各样的方案

包括经典算法 DeepWalk、LINE、Node2Vec

这些算法的基本思路是基于随机游走生成数据

然后通过训练优化参数

产生概率模型

将经典神经网络模型如 RNN、CNN等扩展到了图数据上

与图表征学习试图学习出每个点的向量不同

图神经网络的目的其实是学习出聚合函数

所有点通过同一个函数就可以利用局部信息计算出自身的表征

即使是图结构发生变化，甚至是完全新的图

也能用原来的函数计算出有意义的结果

有关图神经网络，也已经诞生了一系列经典算法

— ★★★ —

最后，说些关于图计算的实际应用吧

当下许多大型互联网企业、金融科技公司

其实都离不开图计算技术

Google创始人Larry Page在20世纪末发明的PageRank

这是一种大规模页面、链接排序的算法

可以说，早期谷歌的核心技术就是一种浅层的并发图计算技术

还有Facebook，它的技术框架的核心是它的Social Graph

即朋友关联朋友再关联朋友

由此脸书建立了强大的社交关系网络

脸书开源了很多东西

但是这个核心的图计算引擎与架构从未开源过

如果你能回忆起2007-2008年爆发的世界金融危机

莱曼兄弟公司破产

当时高盛集团能全身而退

背后的真实原因是应用了强有力的图数据库系统——SecDB

而对于所有技术驱动的新型互联网公司

比如Paypal、易趣和许多我们国内的金融和电子商务公司

图计算也并不罕见

图的核心竞争力可以帮助他们揭示出数据的内部关联

最近十年以来

随着以深度学习为代表的人工智能技术广泛应用

图学习逐渐成为了一个热点话题

也在因果关系、可解释性方面取得了突破进展

现在，图学习也已进一步扩展应用

比如广告、金融风控、智能交通、医疗、智慧城市等各个领域

那就最后再说些金融反欺诈中的图计算应用例子

在金融、电商等涉及金钱交易的领域

总是不乏活跃在其中以谋取非法利益的黑产

比如薅羊毛、刷单、套现、虚假交易等

相比起个别用户自身偶发的套利行为

那些以团伙为单位在各业务场景下聚集操作作案的黑产团伙

他们的行为会对平台造成更大更严重的经济损失

而图计算正是识别团伙性案件的良方妙药

通过将万千用户、商户、设备、网络环境等作为节点

将使用、交易等信息作为关联信息建边

即可形成一个覆盖范围极广的异构图

再结合不同的应用背景确定识别目标

并挑选图计算模型、样本、标签等

即可进行一次有监督学习的图训练

最终在推理阶段对图中的节点或边进行其风险水平的概率输出

那就会有小伙伴说了

风控场景高质量样本标签太少了

问题不大，也有很多图模型可用于无监督学习

比如社群发现，就不需要任何标签信息

即可将关联最紧密的节点集合进行聚类

在我们的经验里

是识别黑产团伙最好用的图算法之一

再比如近几年热门的自监督学习、对比学习

应用于图计算领域则可以对图进行无监督预训练

从图结构、图属性自身的性质出发

为图节点学到具有良好表征能力的向量

可用于下游的各类风控智能模型中

— ★★★★ —

随着近期AIGC大模型的爆火出圈

人工智能又迎来了新一波浪潮

相比生成式的语言和视觉模型

图计算确实显得冷门一些

但楠姐相信好饭不怕晚

没有发光的日子都是在为发光做准备

也许会有一天，图计算也能迎来自己的热搜

—-写在最后—-

★ 本篇文章图片构思、创意、整体结构、后期修改，全部版权归京东楠姐所有，素材生成均源自于Midjourney以及楠姐原创提示词生成。楠姐出图不易，且并非完美，请勿未经允许用于其他场合及目的

★ 本篇文章图片创意均只为了说明及示意，且带有一定夸张和幽默元素，切勿对号入座哦~如有雷同，纯属巧合~无意冒犯~

★ 本篇文章文字均根据以下参考文献汇总撰写：

[1]. 马耀，汤继良. 图深度学习[M].电子工业出版社.

[2]. 张长水，唐杰，邱锡鹏[M]. 图神经网络导论[M].人民邮电出版社.

[3]. 知乎. 图计算发展简史[EB/OL]. https://zhuanlan.zhihu.com/p/

[4]. 百度. 大数据的基础——图计算的发展历程[EB/OL]. https://baijiahao.baidu.com/s?id=&wfr=spider&for=p

作者：京东科技 丁楠

内容来源：京东云开发者社区（未经授权请勿转载）