1.1.2 由一道面试题引发的思考

在现实生活中，绝大多数人具备图的思维方式吗？我们来看看下面这个问题：构造一张图（由顶点、边构成），使图里包含5个三角形，且只再增加1条边就能让三角形的个数增加为10。

补充信息：这张图中，顶点代表账户，边代表账户间的转账交易，账户间可以有多笔交易。所谓的三角形就是由3个账户间的交易形成的原子级三角形，原子级是指三角形不可嵌套，三角形的每条边都是不可分割的，也就是说，1条边仅对应1笔转账交易。

我们来分析一下这个题目的关键：只增加1条边，三角形却要增加5个。也就是说，先前有5个三角形，它们若能共用1条边，那么再增加1条这样的边，就会形成5个新的三角形，而共用1条边也意味着这5个三角形也会共用2个顶点。分析至此，答案是不是呼之欲出了？

这是笔者从真实的业务场景中领悟并提炼出来的一道面试题，这道题让很多擅长百度或谷歌搜索以及刷题的应试者手足无措，90%的人在网上面试阶段看到这道题后都归于沉默，而9%的人会给出如图1-4所示的解答。

很显然，图1-4这个答案中间的竖线导致原子边被切割了，同时也引入了多个无用的顶点，它完全不符合只增加1条边的限制条件。给出这种答案的人大抵没有仔细读题。

这个问题好的地方在于，它可以有很多个答案，不一而足。例如图1-5所示的答案，这样构图可谓用心良苦，虽然略显复杂，但本质上完全符合上面的分析：固定2个顶点，连接1条边，出现了5个新的三角形。然而，如此辛苦的构图实际上也是平面化（低维化）的，它牵涉的点、边数量比较多。

有没有更简洁的方案呢？答案是有。图1-6所示的7个顶点（A～G）已经形成了5个三角形，如果在A、B间再新增1条边，就形成了10个三角形，包含5个新增的三角形。为了在二维平面内表达这个高维空间，我们用虚线表示被遮盖部分的边。

很显然，这个方案用了较少的点和边。它最巧妙的地方在于在顶点A、B之间新增的边，很多人觉得不可思议，但是如果仔细读问题，A、B是两个账户，账户之间完全可以存在多笔交易，这其实已经在暗示解题的思路了。

那么，按照这个思路继续探寻下去，如何构造一个使用更少的点和边的图来解这个题目呢？

图1-7所示的解决方案仅使用了4个顶点与7条边就构造出了5个三角形。增加8号边之后，能形成5个新的三角形。这个解法的聪明之处在于顶点A、C、B之间由1～5号边所形成的4个三角形复用了1、2、3、4这几条边。因此，图的上半部分有4个三角形，下半部分有1个三角形，它们共用了边A、B（5号边），只要在A、B之间新增1条边，全图的三角形数量就会翻倍。这是相当巧妙的构图逻辑。

类似地（触类旁通），如果我们可以构造一张图，上面包含3个三角形，下面包含2个三角形，两部分共享一条边，同样可以达到类似的效果。聪明的读者可以尝试画出这张图的样子。目前已知最精简的构图如图1-8所示，它只用了3个顶点和8条边。聪明的读者如果可以想到更极致的方案，欢迎联系笔者。

现在我们探究一下这个题目背后所蕴含的图的意义。在银行业中，以零售转账为例，大型商业银行中有数以亿计的借记卡账户，这些账户每个月有数以亿计的交易（通常交易的数量会数倍于账户数量）。如果以卡账户为顶点，以账户间的交易为边，就构造成了一张有数以亿计点和边的大图。如何衡量这些账户之间连接的紧密程度呢？或者说，如何判断这张图的拓扑空间结构呢？类似地，在一张SNS社交网络图中，顶点为用户，边为用户间的关联关系，如何衡量这个社交图谱的拓扑结构或紧密程度呢？

三角形是表达紧密关联关系的最基础的结构。如图1-9的社交网络图谱（局部）所示，两个框内的4个顶点间都构成了16个（2×2×2+2×2×2）三角形。从空间结构上看，它们之间的紧密程度也更突出。

上面提到的银行转账账户间所形成的三角形的个数，很大程度上可以表示银行账户间某种关联关系的紧密程度。2020年某季度，某股份制银行的转账数据形成了2万亿个三角形，而顶点与边的数量都在10亿以内，也就是说平均每个顶点都参与到了上千个转账三角关系中。这个数字是非常惊人的，但我们仔细分析就会发现，如果少量的顶点之间存在多个转账关系，例如A、B、C三个顶点，如果它们两两之间都存在着100条边，那么总共就构成了100万个三角形。类似地，A与B两个顶点之间存在一个关系，它们各自分别与另外1000个账户存在一个转账关系，A、B之间每增加一条边就会增加1000个三角形。

当然，无论是转账交易数据、社交网络数据、电商交易数据还是数字货币流转数据，数据所形成的网络（图）用数学语言来定义都是一个拓扑空间（Topological Space）。在这个拓扑空间中，我们关心的是数据之间的关联性、连通性、连续性、收敛性、相似度（哪些节点或节点集合的行为、特征等指标更为相似）、中心度、影响力以及传播的力度（深度、广度）等。用拓扑空间内数据关联的方法来构造的图可以完全还原并反映真实世界中我们是如何记录并认知世界的。如果一个拓扑空间（一张图）不能满足对异构、多源、多维、多模态的数据的描述，那么就要构造另一张图来表达—结果就是天然地形成了一个多图的数据集合。每一张图可以看作从一个（或多个）维度或领域（如知识领域、学科知识库等）对某个数据集的聚类与关联，区别于传统关系型数据库的二维关系表的方式，每一张图可以是多张关系表的某种关联组合。

在图上，不再需要二维关系表操作中的表连接（Table Join）操作，而是用图上的路径或近邻类操作来取代。我们知道，表连接的最大问题是在复杂、多表查询模式下会出现的笛卡儿积（Cartesian Product，又称直积）挑战。尤其是在大表中，这种乘积的计算代价是极大的，参与表连接的表越多，它们的乘积就越大。例如，3张表X、Y、Z的直积计算量是{X}×{Y}×{Z}，如果X、Y、Z各有100万、10万、1万行，计算量就是1000万亿，这是个天文数字。在很多情况下，关系型数据库批处理缓慢的一个主要原因就是需要处理各种多表连接的问题。这种低效性实际上是因为关系型数据库（以及它配套的查询语言SQL）无法在数据结构层面做到完全反映真实世界。

人类大脑的存储与计算从来不会在遍历和穷举时通过笛卡儿积在计算上浪费时间，但是当我们被迫使用关系型数据库以及Excel表格的时候，经常需要极为低效地做反复遍历和乘积的事情。在图上则不会出现这种问题—在最坏的情况下，你可能需要以暴力的方式在图上遍历一层又一层的邻居，但它的复杂度依然远远低于笛卡儿积（例如，1张图有1000万个点和边，遍历它的复杂度最大就是1000万—任何显著高于其最大点和边数量的计算复杂度都是图数据结构、图算法或图系统架构设计失败的体现）。

看到这里，熟悉数仓的读者可能会质疑通过极致的优化，数仓是可以尽可能避免笛卡儿积现象的，并且能做到各种计算优化与存储进程的加速。然而，数仓是通过对数据不断地进行分表，构建中间表、码表，分层，预计算，缓存结果等一系列操作来实现所谓的优化和加速的。换言之，数仓更适用于数据流转模式相对固定、静态的查询，如果查询模式高度灵活且动态，数仓是无力承载的。究其根本，是因为整个关系型查询SQL计算与分析的逻辑都是建立在二维表基础之上的，如我们先前所述，用低维来表达高维，注定会遇到效率、灵活性甚至黑盒与不可解释性等诸多问题。

值得一提的是，人的思维方式就是图的思维方式。可以比拟、还原人的思维方式的图数据库或图计算的方式，我们称为原生图（Native Graph）。通过原生图的计算与分析，我们可以让机器具备像人类一样的高效关联、发散、推导、迭代的能力，而让机器拥有这样的能力的基础在广义上就是图查询与分析算法，简称图算法。

所谓原生图，是相对于非原生图而言的，在本质上指图数据是如何以更高效的方式进行存储和计算的。非原生图使用的可能是关系型数据库、列数据库、文档数据库或键值数据库来存储图数据；而原生图使用的是更为高效的存储（及计算）方式来为图计算与查询服务。

原生图构建的当务之急是数据结构，这里要引入一个新的概念—无索引近邻（Index-Free Adjacency）。这个概念既和存储有关，也和计算有关。简而言之，无索引近邻数据结构相对于其他数据结构的最大优势是，在图中访问任一数据所需的时间复杂度为O（1）。例如，从任一节点出发访问它的1度近邻的时间复杂度是O（1），反之亦然。而这种最低时间复杂度的数据访问恰恰就是人类在大脑中搜寻任何知识点并关联发散出去时所采用的方式。这种数据结构显然和传统数据库中常见的基于树状索引的数据结构不同，从时间复杂度上看是O（1）与O（logN）[1]的区别。而在更复杂的查询或算法实现中，这种区别会放大为O（K）与O（NlogN）或者更大（K≥1，通常小于10或20，但一定远远小于N，假设N是图中顶点或实体的数量）。这就意味着在复杂迭代运算的时效性上会出现指数级的差距，在图上如果是1s完成，传统数据库则可能需要1h、1天或更久（或者无法完成）—这意味着，传统数据库或数仓中的那些动辄T+1的批处理操作可以以T+0甚至纯实时的方式瞬间完成！

当然，数据结构只是解决问题的一个方面，我们还需要从架构（如并发、高密度计算）、算法并发优化、代码工程优化等多个维度去让图数据库真的腾飞。有了原生图存储与高并发、高密度计算在底层算力上的支撑，图上的遍历、查询、计算与分析可以得到进一步的飞跃。如果传统的图数据库号称比关系型数据库快1000倍，那么飞跃之后的图要快100万倍！