【论文复现】Computing label constraint reachability in graph databases SIGMOD2010

2024-01-17 10:07:34

Computing label constraint reachability in graph databases --SIGMOD2010

本文章是课程《高级算法》的实验 5 ：论文复现，现整理发博文。代码还在 debug （不知为何和原作者的结果不一致），之后发到 github 。

问题

给一张有向图，每条边有一个边权。每次询问给定 u，v，和一个边权集合，问 u 到 v 只走权值在这个集合的边能否到达。

算法思路

在有向图中找到一颗树形图（应该是森林，但我们总能建立虚根使其为树形图），之后所有边分为树边和非树边。

一些定义

一条路径为 p。
路径p上所有边权值的并集为 $L(p)$ 。
$P_s$ 表示仅当一条边是树边的路径。
$P_e$ 表示仅最后一条边是树边的路径。
$P_n$ 表示第一条边和最后一条边都不是树边的路径。
$M‘(u,v)$ 表示所有的 $L(p)$ 使得 $p$ 是从 $u$ 到 $v$ 的路径。即是一个 label 集合的集族。
$M(u,v)$ 表示 $M‘(u,v)$ 中去除包含关系的集族（显然只需要保留这些即可回答问题）。
$M_s (u,v)$ 为 $M(u,v)∩\{L(p)|p∈P_s\}$ 。
$M_e (u,v)$ 为 $M(u,v)∩\{L(p)|p∈P_e\}$ 。
$NT(u,v)$ 为 $M(u,v)∩\{L(p)│p∈P_n \}-M_s (u,v)-M_e (u,v)$ 。
$M^T (u,v)$ 为 $M(u,v)-M_e (u,v)$ 。
生成的树形图是T。

转化成最大树形图问题

定理2：T 和 NT 可以表示 M。
证明：u 到 v 的路径显然是 u 先走树上的子树（ T 上的路径），再任意走到 v 在树上的祖先（ NT 上的路径），再走树边到 v（ T 上的路径）。

最大的开销是 NT ，而 NT 和树边有关，即与 T 的生成有关。故我们需要找到一个最优的树形图 T 使得 NT 的开销最小。思路是对每条边加一个边权，然后找最大树形图。
定义 (v’,v) 的边权为：

\[w(v‘,v)=\sum_{u \in V}|(M(u,v‘)⊙ \{\lambda(v‘,v)\}) ∩ M(u,v)| \]

其中 ⊙ 意为：$\{s_1,s_2\} ⊙\{s‘_1,s‘_2,s‘_3\} = \{s_1 ∪ s‘_1,s_1 ∪s‘_2,... ,s_2 ∪ s‘_3\}$ 。容易发现它的意思是：如果选中该边作为树形图的边，那么它的代价是以它结尾的路径labels之和，即

\[w(v‘,v)=\sum_{u \in V}|M_e(u,v)| \]

注意到我们想要优化的是 $NT(u,v)=M(u,v)-M_s (u,v)-M_e (u,v)=M^T (u,v)-M_s (u,v)$ ，所以当我们最大化树形图权值和时，相当于最小化 $M^T (u,v)$ 之和，其是 NT 的一个上界。
为了优化时空复杂度，我们的目标变成寻找最大树形图的问题。

优化边权计算

注意到计算边权十分麻烦且复杂度很高，所以我们采用随机抽样的方式。首先建立目标：

\[P(\frac{W(T_o)-W(T)}{W(T_o)} \le \theta) \ge 1 - \delta \]

其中 $W(T_o)$ 表示真实边权的最大树形图，$W(T)$ 表示通过随机抽样计算边权得到的最大树形图的权值。即给定一个置信水平和相对误差，我们希望找到一个满足上式的树形图。

下面考虑抽样。对于边 $(v‘,v)$ ，我们做 n 次抽样 $u_1,u_2,…,u_n$ 。计算

\[X_{e,i}=|(M(u_i,v‘)⊙ \{\lambda(v‘,v)\}) ∩ M(u_i,v)| \]

取 $X‘_e = \frac 1 n \sum_{1\le i \le n} X_{e,i}$ ，发现它的期望是 $X_e=w(v‘,v)/|V|$ 。

根据Hoeffding and Bernstein bound和empirical Bernstein bound，我们得到这样的概率分析：

\[P(|X‘_e-X_e|\le \epsilon_{e,n}) \ge 1-\delta‘, \epsilon_{e,n} = \sigma_{e,n}^2\sqrt{\frac {2 \ln \frac 3 {\delta‘} }{n}} + \frac {3 R \ln \frac 3 {\delta‘} }{n} \]

其中 $\sigma_{e,n}^2$ 是 n 次取样的方差。所以当给定 $δ‘$ 时（即置信水平）时，边的估计满足以上式子。发现其是随着 n 变大而误差逐渐变小的。根据边的误差分析，当 $\delta‘ = \frac {\delta} {|E|}$ 时，我们可以通过 union bound 得到整棵树形图的误差分析

\[P(\and_{e \in E(G)} |X‘_e-X_e|\le \epsilon_{e,n} ) \ge 1 - \delta \]

为了保证找到的树形图是比较优的，每条边我们要保存两个值：对其边权的估计和方差。前者服务于树的构建，后者服务于误差的分析。

当满足以下条件时，我们称找到了一个较优的生成树。

\[\frac {2\Delta_n(T‘)}{W_n(T)-\Delta_n(T‘)} \le \theta, \text{where } W_n(T) \ge \Delta_n(T‘) \]

算法流程

图来自论文的伪代码。

这是一个 lasvegas 算法，可以证明当 |Σ| 足够小时取样次数很少。实际上与 $C(|Σ|,2)$ 呈线性。为了计算每条边的边权，我们需要计算 $M(u_i,v)$ ，即 SingleSourcePathLabel 算法。这其实是一个 $bellman-ford$ 的修改。该算法的复杂度是 $O(n|V||E|* C(|Σ|,|Σ|/2)+n/n_0 (|E|+|V| \log?|V| )) $ 。于是我们找到了一个较优的生成树T。

（注意求最小树形图的复杂度是 tarjan 对 ChuLiu 的优化的算法复杂度）

现在考虑如何计算 NT ：固定 u ，对于所有的 v ，计算 $NT(u,v)$ 。这个东西的计算与 SingleSourcePathLabel 类似。定义三个数组：$M_s [v]$ 表示第一条边为树边的 path-labels ，$M_e [v]$ 表示第一条边为非树边且最后一条边为树边的 path-labels ，$NT(u,v)$ 表示第一条边和最后一条边均为非树边的 path-labels 。我们在做和 SingleSourcePathLabel 相同的搜索时，根据走的边的种类不同可以轻松维护这三个数组。这里的复杂度和 SingleSourcePathLabel 相同。

快速回答询问

对于一次询问，给定 $A?Σ$ 和 u、v，如何判断答案？
朴素方法：由定理2可知，路径分为三段，所以我们可以暴力找断点。这显然不优。

为了简化计算，我们考虑这样两个问题：

找 $u‘∈Succ(u),v‘∈Pred(v)$ ，使得 $NT(u‘,v‘)≠?$ 。其中 Succ 和 Pred 表示子树和祖先集合。

对树做 dfs 序，子树关系变成一个区间。我们记录 u 在 dfs 序中管辖的区间是 $[l_u,r_u]$ ，那么对于 $NT(u,v)≠?$ ，我们将其映射到四维空间中的一个点，具体来说是 $(l_u,r_u,l_v,r_v)$ 。
每次给定 u 和 v ，寻找这种 $u‘,v‘$ ，就变成一个四维空间上的范围查找问题，可以用 k-dtree 或者 range-search tree 分别在 $O(n \log^2?n )-O(n^{3/4}+k)$ ，$O(n \log^3?d )-O(\log^4?n+k)$ 的时间内完成。
快速计算 $L(P_T (u,u‘ ))$ 。即给定一个树上路径，求它的path-label。

由于一定是从上到下的，于是对字符集中每个字符搞个前缀和，询问的时候一减就行了

实验

没啥好说的，去看论文吧。