大规模图数据管理与分析 课件 05-图上的可达性查询

图上的路径查询图上的可达性查询第五章2可达性：问题定义3

[1]

JONESND.Space-boundedreducibilityamongcombinatorialproblems.JournalofComputerandSystemSciences,1975,11(1):68-85.可达性：示例4

基础可达性算法:广度优先遍历（BFS）Part25图上经典的遍历算法2026/4/176广度优先遍历（Breadth-firstsearch,BFS）使用队列维护当前节点序列每次取队首结点，逐一访问其出邻居并放入队尾深度优先遍历（Depth-firstsearch,DFS）使用栈维护当前节点序列每次取栈顶结点，访问其下一个出邻居并放入栈顶，只有当前结点无下一个出邻居可访问时才将其出栈用于可达性的BFS2026/4/177

用于可达性的BFS2026/4/178

其他基于遍历的基础可达性算法

2026/4/179基于索引的可达性算法Part310可达性索引（Reachability

Index）11尽管上述基础可达性算法的时间复杂度已经是关于图规模线性的（若图的总结点数为𝑛、总边数为𝑚，则上述算法的渐近时间复杂度为𝑂(𝑛+𝑚)），但在大规模图上，其运行时间往往仍然较长

为了进一步加速查询，近年来许多研究工作选择了预计算可达性索引可达性索引：查询前对图离线预计算所得的图上全部或部分可达性信息（全部可达性信息即任意点对之间是否可达的信息）为了在查询处理过程中把索引利用起来，查询算法也需要作出相应的调整纯索引（label-only）算法：仅需查找索引、不需再访问图数据索引-遍历混合(label+G)算法：既需查找索引、也需在图上做一部分遍历区间标签（Interval

Labeling）2026/4/1712

区间标签（Interval

Labeling）2026/4/1713建立生成树与计算区间同时进行区间标签（Interval

Labeling）2026/4/1714

示例有向图的区间标签可达性的充分非必要条件支配关系绘图（DominanceDrawing）

2026/4/1715

支配关系绘图（DominanceDrawing）

2026/4/1716以d维空间中的支配关系表示图中可达性关系：以d次拓扑排序的序号分别作为d维空间中的各维坐标由于拓扑排序仅在有向无环图（directedacyclicgraph,DAG）上有意义，为了在一般的有向图上使用支配关系绘图索引加速可达性查询，需要先将一般的有向图转化为DAG

将一般有向图转化为DAG的步骤：找出原图中所有强连通分量（stronglyconnectedcomponent,SCC），并存储每个结点到所属SCC的对应关系，结点𝑣对应的SCC记作𝑆𝐶𝐶(𝑣)将原图中的每个SCC映射为DAG中的一个结点只要原图中某个SCC中的任意结点有到另一个SCC中任意结点的边，则DAG中这两个SCC映射到的结点连相应方向的边

支配关系绘图（DominanceDrawing）

2026/4/1717转化为DAG支配关系绘图（DominanceDrawing）

2026/4/1718构建支配关系绘图索引：在上述DAG上运行d次拓扑排序，每个结点在各次拓扑排序中获得的序号构成其在d维空间中的坐标

左图一种可能的支配关系绘图索引（拓扑排序可能有多种，因此非唯一）支配关系绘图（DominanceDrawing）

2026/4/1719

可达性的必要非充分条件支配关系绘图（DominanceDrawing）

2026/4/1720

可达性的必要非充分条件集合包含测试（Set-ContainmentTesting）2026/4/1721

可达性的必要非充分条件

集合包含测试（Set-ContainmentTesting）2026/4/1722实际上，采用集合包含测试索引的实用可达性算法1并不会存储所有可达结点的集合而是从中随机抽样，并利用独立置换（IndependentPermutation）的性质构造判断集合不包含(即𝐼𝑛(𝑢)⊈𝐼𝑛(𝑣)或𝑂𝑢𝑡(𝑣)⊈𝑂𝑢𝑡(𝑢))的等价条件

[2]

WEIH,YUJX,LUC,ReachabilityQuerying:AnIndependentPermutationLabelingApproach.TheVLDBJournal,2018,27(1):1-26.DOI:10.1007/s00778-017-0468-3.两跳标签（2-Hop

Labeling）2026/4/1723

两跳标签（2-Hop

Labeling）2026/4/1724

左侧DAG的其中一种两跳标签（非唯一）两跳标签（2-Hop

Labeling）2026/4/1725

两跳标签（2-Hop

Labeling）2026/4/1726

两跳标签（2-Hop

Labeling）2026/4/1727第7、18行：发现𝑗<𝑖（访问的结点较当前结点顺序更靠前）时跳过-

剪枝条件1第9、20行：检查访问的结点与当前结点的现有索引项是否已能推导出两者间的可达关系，若能则跳过-

剪枝条件2两跳标签（2-Hop

Labeling）2026/4/1728

[3]

COHENE,HALPERINE,KAPLANH,ReachabilityandDistanceQueriesvia2-HopLabels.SIAMJournalonComputing,2003,32(5):1338-1355.DOI:10.1137/S0097539702403098.不基于索引的高效可达性算法Part429动态图给可达性索引带来的挑战2026/4/1730目前，最先进的基于索引的算法在上亿点边的静态大图上查询时间已能达到微秒级别

近年兴起的动态图数据：电子商务图、社交网络……例如，在购物节等销售高峰期，阿里巴巴电子商务图每秒的更新量高达两万条边[4]可达性查询可以帮助检测电子商务中的欺诈活动、在社交网络上实施访问控制等在图数据高度动态的场景下，可达性索引方法难以提供足够高的查询效率静态索引在图更新时需要重建，产生显著的开销更新频繁时，支持动态更新的索引的维护成本也仍然很高不基于索引的可达性算法的设计目标：在摒弃索引维护成本的基础上，获得显著优于基础可达性算法的效率[4]

QIUX,CENW,QIANZ,Real-timeconstrainedcycledetectioninlargedynamicgraphs.ProceedingsoftheVLDBEndowment,2018,11(12):1876-1888.ARROW[5]2026/4/1731基本思想：从源结点、目标结点分别发起前向、后向随机游走，若来自两个方向的随机游走访问了相同结点，则返回真，否则返回假近似算法，可能导致假阴性：有限次的随机游走不一定能够恰好覆盖连接可达点对的路径无法用于对查询结果准确性有严格要求的应用场景，如欺诈检测在特定结构的图上，可以通过控制随机游走的数量、长度等参数，为查询准确率提供理论上界当准确率要求不高时，ARROW的执行速度显著快于BFS[5]

SENGUPTAN,BAGCHIA,RAMANATHM,ARROW:ApproximatingReachabilityUsingRan-domWalksOverWeb-ScaleGraphs//2019IEEE35thInternationalConferenceonDataEngineer-ing(ICDE).Macao,Macao:IEEE,2019:470-481[2021-01-03].IFCA[6]2026/4/1732不基于索引的准确可达性算法基本思想：加速在社区中的可达性搜索社区：内部连接稠密、外部连接稀疏的子图；许多真实图都有社区结构由于社区内部的稠密连接，社区内的点对往往通过多条路径可达，而可达性查询只要求确认点对之间是否存在一条路径，许多边不需要访问基于PersonalizedPageRank（PPR）估计算法，提出了一种概率引导的双向搜索策略来尽量规避社区中多余的边访问原理：估计算法能够高效地找出任意节点周围PPR最高的节点集合，近似为该节点周围的社区社区收缩策略：当已访问的结点集合形成社区时，IFCA将它们收缩成一个超结点，并在缩减后的图上重新初始化搜索，以加速跨社区查询的处理[6]

YuePang,LeiZou,YuLiu:IFCA:Index-FreeCommunity-AwareReachabilityProcessingOverLargeDynamicGraphs.ICDE2023:2220-2234.IFCA[6]2026/4/1733

IFCA[6]2026/4/1734第二步：把发现的社区收缩成一个超节点，以超节点为新的起点继续做概率引导的搜索IFCA[6]2026/4/1735第三步：多次进行社区收缩后，图变得越来越稀疏、社区越来越少。代价模型指导何时切换到双向BFS能最快地完成查询IFCA[6]2026/4/1736灰色部分为图数据及索引更新时间；其他部分为不同方法的查询时间可见不基于索引的方法在更新时间上显著优于基于索引的方法可达性查询的变种问题Part537可达性查询的变种问题2026/4/1738以上所讨论的可达性问题定义仅考虑了图的拓扑结构有时候，图蕴含着更丰富的语义信息，譬如边所代表的关系类型、边存在的时间区间等。如果将这些语义信息纳入考虑，则会得到可达性查询的各种变种形式处理可达性查询的变种问题往往以经典可达性的算法框架为基础来支持相应的额外语义，并添加针对特定场景的优化带标签约束的可达性查询2026/4/1739

带标签约束的可达性查询：算法2026/4/1740基于地标节点（landmark

vertices）索引的算法[7]选取部分节点作为地标，预计算它们到图中所有其他节点是否通过每种边标签集合可达，以此作为索引查询时，从起始节点开始搜索，一旦抵达地标节点，即可马上判定是否带标签约束可达除此之外，还有改造两跳索引以适应于带标签约束的可达性的算法[8]等

一个地标节点

地标索引…?[7]

L.D.J.Valstar,G.H.L.Fletcher,andY.Yoshida,“LandmarkIndexingforEvaluationofLabel-ConstrainedReachabilityQueries,”p.14,2017.[8]Y.Peng,X.Lin,Y.Zhang,W.Zhang,andL.Qin,“AnsweringReachabilityandK-ReachQueriesonLargeGraphswithLabel-Constraints,”p.29,2021.时序图上的可达性查询2026/4/1741

时序图上的快照可达性查询2026/4/1742

某段时间内两个实体间是否有关联如：尝试找出某个社会热点流行期间与其中心人物的账号相关联的账号

[1,2][2,5][9,11][2,7][3,8]

示例：时序图上的链式可达性查询2026/4/1743

路线规划两个地点所对应的结点链式可达即代表它们之间存在一条可行的交通路线

[1,2][2,5][9,11][2,7][3,8]

示例：更复杂的路径查询：正则路径查询Part644正则路径查询：问题定义45

正则路径查询：示例46PersonPersonPersonPostfollowsfollowsfollowscreateslikes

基于自动机的正则路径查询算法47

有穷自动机数据图乘积自动机

起始状态接受状态每个正则路径查询对应一个有穷自动机对有穷自动机和数据图求乘积自动机；其中所有可达的起始-接受状态对所对应的数据图上的节点对，即为正则路径查询的结果无需提前显式构建乘积自动机，可以通过在数据图和查询自动机上同步做标签一致的遍历，实现在线懒惰构建基于扩展关系代数的正则路径查询算法48关系代数（relational

algebra,RA）足以表达正则路径查询中除克林闭包（Kleene

closure）外的所有操作符（若将将数据图中拥有每种边标签的所有边均看作一张含有其起点和终点的两列表）阿尔法关系代数（alpha-RA）在关系代数基础上扩展支持克林闭包，可以表达任意正则路径查询基于扩展关系代数的正则路径查询算法49

+st自底向上传递结果表到达内部节点时，则按照上述公式对孩子结果表执行操作参考文献50[1]JONESND.Space-boundedreducibilityamongcombinatorialproblems.JournalofComputerandSystemSciences,1975,11(1):68-85.[2]

WEIH,YUJX,LUC,ReachabilityQuerying:AnIndependentPermutationLabelingApproach.TheVLDBJournal,2018,27(1):1-26.DOI:10.1007/s00778-017-0468-3.[3]

COHENE,HALPERINE,KAPLANH,ReachabilityandDistanceQueriesvia2-HopLabels.SIAMJournalonComputing,2003,32(5):1338-1355.DOI:10.1137/S0097539702403098.[4]

QIUX,CENW,QIANZ,Real-timeconstrainedcycledetectioninlargedynamicgraphs.Proceedings