一、业务场景中的“大”图
立足于数据中台，我们每天都需要处理超大规模的数据，当我们落地图计算时也不例外。这里的“大”图有两层含义，一是图的数量特别多，举一个典型的例子，我们每天都要从近千亿的采集日志中提取百亿级别的图，然后在规定的时间内完成分析和计算。那么在这个数据规模下，一些比较通常概念下的指标计算也变得非常棘手。
另外一个是单图的规模特别大。以用户商品交互网络为例，因为网络中的实体类型特别多，用户的行为又特别丰富。对于这种类型的图，我们经常会遇到几十亿的节点上沉淀了上万亿关系的边。
那么针对这两类问题我们是怎么解决的呢？
马老师曾经说过，“small is powerful”。我们的思路也很类似，都是从子图出发。对于“图的数量多”的情况，我们就需要看一下它的基本组成成分，以及是否有显著的结构特征，然后我们再设计高并发的算法。
对于“图的规模大”的情况，就需要有一个良好的子图抽样系统，从一个大图中提取出我们需要的子图，然后再完成后面的分析和计算。
二、基于子图挖掘的设备识别解决方案
下面我将就“图的数量多”和“图的规模大”这两类问题的典型场景展开讲述。
设备标识符是移动互联网领域中非常基础，同样也非常重要的一个信息，它的本质是对一个物理设备的具体描述。然后我们才能通过设备识别服务，对用户做一些个性化推荐、用户口径统计以及广告转化中的归因分析等等。
但实际上因为种种原因，整个移动互联网上有多种解决方案在市场上并行。那就会导致我们在采集日志中会对同一个物理设备采集到多个设备识别符。
下面举个例子，在正常的一个采集日志中，我们通常会采集设备标识符和用户行为商品信息等等，这里我们只需要关注设备标识符。如果两个设备标识符出现在同一条日志中，我们就认为它产生了连边。如果一条采集日志中有多个设备标识符，我们就认为它是一个全连接的结构。
汇总一段时间的数据，其实就可以可视化出一个结果。就是我们希望把所有属于同一台物理设备的设备标识进行聚合，满足广告外投、用户画像等下游需求。
从下图中我们可以看到它包含了多个连通分量，那联通分量是有多少呢？大家可以想一想整个移动互联网领域的设备有多少，问题的规模就会有多少，它们是成正比的。
第一是设备网络显著子图挖掘：基于采集特性，设备网络世界中是否存在显著的子图模式？ 大簇是否存在超家族特性？第二是超大规模联通分量识别：在降本增效的大背景下，如何稳定高效支撑千亿规模的联通分量识别？第三是大簇分解问题：针对一个设备大簇，如何对其进行切割，使得分割结果准确&稳定？
那么如何解决以上三个问题呢？其实它们有一个共性，就是需要子图的匹配能力。也就是在一个给定的大图里面找到与一个给定小图同构的子图。
以下图为例，假设有两个需要查询的小图，和两个待查询的大图。从图中我们可以看到，T1中包含一个Q1，T1包含一个Q2。简单来说这个算法的能力就是在输出T1包含几个Q1和Q2，然后我们会记录下它的个数和实例。
针对这种问题我们自研了的基于ODPS的子图模式匹配算法，我们采取了一种分解再合并的算法思路。
比如下图中的例子，上面是一个小图，下面是一个待查询的大图。我们首先会按照一定的模式把上方的小图分解成多个三元组，然后通过类似的方式，把下面的大图也分解成三元组。接着对小图进行合并，使它回归到原始的结构。
在小图的合并过程中我们发现，下面两个节点相同，且上面两个节点不同的进行了合并，合并后可以看到们它们回归到了原始的结构中。对于大图分解后的结构，我们按照这种条件进行合并，如果合并成功了，那就说明大图中也有一个相同的实例。
那么对于一些比较简单的结构，一次迭代可能就可以完成。对于一些稍微复杂的结构，通过两次迭代也几乎能够满足所有结构。
下面来说下显著模式挖掘与子图匹配算法。由于采集日志中一条数据最多采集的设备ID类型是有限的，因此需要考虑的子图规模具有上限。对于节点规模比较小的子图，我们可以穷举出它所有的结构。对于节点<=4的motif，一般只保留p1-p8这八种结构。对于size 为5和6的 motif，仅考虑全连接结构。最终我们需要考虑的图结构也就是从p1-p10这十种结构。
下图是基于某个真实业务统计的结果，首先看下链式的结构。长度为2，节点个数为3的链式结构，占p1-p10所有结构的7.8%；长度为3，节点个数为4的链式结构占比骤降到了1.3%；长度为4，节点个数为5的链式结构占比几乎到了0。这就可以说明整个链式结构在设备网络中是很难出现的。
所以就进一步证明了，一个大簇的网络直径一旦超过5，它就一定是有问题的，我们要对其进行拆解。
接下来我们再来看一下全连接的结构。从图中我们可以看到p3-p6的全连接结构占比已经超过了60%，这就说明这个设备网络的连接其实是偏稠密的。
对于size为5和6的全连接结构，虽然它的总体占比比较低，但是如果我们只考虑size 为5的motif，这种全连接的结构占比就高达98.4%。所以对于这种类型我们只需要考虑全连接结构，不需要再去穷举出其他size 为5的motif类型。
接下来介绍下该怎么去识别超大规模的图连通分量。这个问题的特点是，第一，整个网络中全连接的子图比较多，它会有非常多全连接的小簇。在大簇中它又包含了很多全连接的子图。
第二，小图占比比较大。小簇代表了一个比较正常的物理设备，在非孤立簇中小簇的占比为84%。也就是如果我们能把连通分辨先识别出来，那么整个设备识别问题，我们就已经解决84%了。第三，操作的时效性要求特别高。这一步操作是所有下游任务的基础，我们必须在保证的时间内完成计算。
那么我们的思路是什么呢？首先要对全连接子图这种比较稠密的结构进行化简，在不影响连通性的情况前提下把复杂的结构转变成简单的结构。
第二步，我们可以先把这些小簇识别出来。这样就不需要再让它进入下一步联通分量识别的任务，减轻下游的压力。第三步，我们会把一些大簇难以识别的问题交给一些成熟的图计算平台。
刚才第一步提到的化简，我们是采用了一种叫做Star Compression的算法。它的目的是在不改变连通性的前提下，对图中的边进行压缩，这是一个迭代式的算法。它的核心是把一个稠密的连接，通过几步迭代的方式，最终转变成星状的结构，所以叫做star compression。通常对于节点为5左右的小簇，经过两次迭代，可以保证收敛。稀疏子图的匹配要比稠密子图匹配更高效，方便利用GPS的能力。
先看一下第一行数据，可以想一下双十一期间整个淘宝的流量有多大，平常我们就可能要面临千亿级别的采集日志，在其基础上做连通分量的识别。在过往的时间内，调度高峰期计算资源紧张的情况下，其实没有现成的图计算引擎接口，可以hold住这么大的吞吐数据量。
所以我们必须要给下游的图计算引擎减轻压力，经过Compression图压缩，子图识别之后，可以发现其实已经过滤掉约87%的边了。剩下交给第三方图计算平台的压力就小了很多。
通过这种方法，大约有一百多亿的边进入下游的图计算引擎，从而保证联通分量识别的稳定性和可靠性。对于一些比较小的业务，通常通过一轮的迭代就可以达到比较好的结果。
这是设备识别，它是一个比较稠密的网络。其实我们还实现了在一些偏sparse的网络，比如说分享关系。两个用户分享了同样一个商品，我们就给他建立一条边， 也就是a给b分享，b和c分享，a和c还有分享，对于这种稀疏的分享关系，只需要利用子图识别的能力，就可以得到很大数据量的下降。
接下来是设备大簇拆解问题。现实世界中这个情况总是非常复杂的，整个移动互联网领域也是这样，我们每天的流量中包含了用户各种复杂的行为，比如换机、恶意的流量、山寨机，甚至不是物理设备，是一些软件生成的流量。
这些行为就会产生非常多的噪声边，就可能把很多无关设备连接到了一起，形成大簇。这里我们就希望能找到一种可解释、稳定的方式对大簇进行拆解，得到背后真正的物理设备。
这是一个图例，假设这是一个规模还可以的大簇。我们将它拆解成若干个具体的物理设备，这些拆解结果就直接影响了你整个移动设备的口径统计，以及不同系统对接时转换的准确性。
那么设备大簇拆解的挑战又有有哪些呢？第一，设备大簇是非常多样的。即使节点数量相似，结构相似，但排列组合不同，大簇也可能存在一定的差异。
第二，设备大簇的规模非常庞大。以一个业务单日新增的大簇来看，如果把大簇定义为20以上，那么单日新增的大簇就会有约20万个，这就影响了百万个具体物理设备的聚合结果。如果拉长时间周期，就有可能直接影响了上亿的设备识别结果。
那么对于大簇要如何拆解呢？我们的思路是，大簇并不是无序随机产生的，而是多个超家族成员通过异常的连边产生的组合。那么这个问题就变成怎么识别哪些节点属于正常结构，哪些节点属于异常的连接边。
这就需要我们对整个网络进行角色定义，对网络中的节点进行特征提取。这是一个问题的一体两面，一个合适的定义，它影响着我们怎么给节点抽取特征，抽取特征的好坏就影响着分类的结果。最终通过多轮的迭代，我们把大簇拆解的问题转变成了一个对图中节点分类的问题。
回到大簇的问题，我们定义了三种角色。第一个叫做D-CoreClique，是指一个紧密连接的团体；被多个更大的团体所共享；团体内成员的边权重大于他们与团体外成员的边权。
第二个叫做Peripherals，是指与多个同类共享同一个CoreClique。第三个叫做D-Connector，在一个图中起桥梁作用；通常连接多个CoreClique。如果能够把这些角色识别出来，再基于一些策略的拆解就变得比较容易起来。
刚才在跑联通分量识别的时候，我们已经用了GPS子图匹配的能力。所以对于每个节点我们已经保留了该节点的结构信息，那么这个信息在这里其实就发挥了用处，我们可以把每个节点它自身及它邻居的结构信息汇聚起来去做分类任务。
三、离线子图采样系统Graph View
离线子图采样系统主要用于从一个大图中抽样出一个易分析的子图。在推荐领域图上法可以提效的核心原因，是通过扩散机制为下游人物汇聚更多的信息。在数据中台沉淀了如此多关系数据的情况下，当今降本增效的大环境下，我们第一步要做的就是存储统一和结构统一。
存储统一是指整个团队关系数据的使用仅此一份，从而避免下游因为各种需求的微小修改，而把数据备份多次，造成的巨大存储浪费。结构统一是指所有关系数据的存储范式必须是一致的，这样方便我们后续做一些模块接口的开发。
当我们做完结构统一和存储统一之后，其实我们背后就有了一张非常规范的异质信息网络。在平常的任务中，我们并不需要去总览这个大图的信息，我们只需要根据指定的路径找到一些我们感兴趣的小图就好了。
在GraphView里，我们根据自己的业务特性，设计了三种模式。第一个是Path 模式，它可以从源节点出发，按照你指定的路径得到一个比较完整的图结构。第二个是Pair模式，它最终只输出头节点和尾节点的映射关系。第三个是End模式，只输出尾节点。
下面是个真实的案例，现在要给指定的人群做商品召回，召回逻辑就是先通过这个人群去找到他好友人群，然后我们看到这些好友人群买了什么商品，以及这些商品的相似商品是什么，这就是一个U2U2I2I的召回逻辑。在最新的GraphView版本上，我们测试了1万个用户，我们发现只需要约3.8分钟就可以得到最终的商品召回，其实也是对应了我们刚才介绍的End模式。
四、总结
今天跟大家介绍的主要是我们自建的一些图引擎。其实依托于阿里生态的一些比较成熟的计算平台，比如ODPS、GraphScope。我们根据自己的业务特点，提出了一些比如说连通分量识别，子图匹配、子图抽取这样一些不含业务语义的计算引擎。这些计算引擎其实和下游的比如说一些GNN推荐是无缝衔接的。最终在下游结合一些业务特征，我们就可以做出一些比较有意思的数据资产。
