图索引之2-hop cover

2-hop cover出自<Reachability and distance queries via 2-hop labels>这篇论文,论文的内容在<Managing and Mining Graph Data>这本书的第6章GRAPH REACHABILITY QUERIES部分中有提及。这一章内容是香港中文大学的两位老师组织的。

这一篇论文的内容比较晦涩,通篇图比较少,形式化的定义、证明、引理所占的篇幅比其它论文要多。

背景

很多图相关的应用中会有判断两点之间是否可达和求两点之间距离的需求,这篇论文提出的对点进行labeling的方法可能很快地响应这种需求。当然这篇论文关注的是静态图,没有提到有更新的场景。

内容

2-hop labels

这一部分讲了很多定义,关于Labeling的。Labeling可以简单地理解为对于某一个点u,把图中其它的一些点的集合作为u的标签,然后标签中还可能有这些点到u的距离的信息。

对于每一个顶点u,在预处理阶段都会计算出相应的L(u),这样如果要找到u和v之前的可达性或者距离,就可以通过L(u)L(v)来计算得出。

Definition 3.1. (Distance labelings)

such that for every u, v ∈ V , if F(L(u), L(v)) = (d, e), then d = δ(u, v), the distance from u to v in the graph. If d = ∞, then e = Ø. Otherwise, e is the first edge on a (shortest) path from u to v in the graph.

这个定义的意思是每个点u都会有自己的labeling,记为L(u)。那么我们计算两个点u, v之间的距离的时候,就可以直接通过L(u)L(v)计算出来。

Definition 3.2. (2-hop distance labeling)

A 2-hop distance labeling of G assigns to each vertex v ∈ V a label L(v) = (Lin(v), Lout(v)), such that Lin(v) is a collection of pairs (x, δ(x, v))

这里对L(v)做了更细致的描述了,区分了Lin(v)和Lout(v)。对于每一种集合,不仅包括了相关的点,还包含了相关的距离。

Definition 3.3. (Steiner 2-hop distance labeling)

A Steiner 2-hop distance labeling is a labeling in which Lin(v) and Lout(v) consists of pairs of the form
(x, d(x, v)) and (x, d(v, x)), respectively, where x ∈ X, d(x, v), d(v, x) ∈ \R , and X is some arbitrary finite set.

如果X = V, d(x, v) = δ(x, v),那么Steiner 2-hop distance labeling就是2-hop distance labeling了。

Definition 3.4. (2-hop reachability labeling)

A 2-hop reachability labeling of G assigns to each vertex v ∈ V a label L(v) = (Lin(v), Lout(v)), such that Lin(v), Lout(v) ⊆ V and there is a path from every x ∈ Lin(v) to v and from v to every x ∈ Lout(v).

对于前面的定义中,Lin(v)中的顶点不一定需要和v相连的,2-hop reachability labeling 加强了限制。

2-hop covers

这部分是最主体的内容了,基本上铺垫了最后算法实现部分需要的所有知识。

Definition 4.1. (2-hop cover)

A collection of hops H is said to be a 2-hop cover of P if for every u, v ∈ V such that Puv ≠ Ø, there is a
path p ∈ Puv, and two hops (h1, u) ∈ H and (h2, v) ∈ H, such that p = h1h2.

这个可以满足搜索Reachibility之后满足Path的需求了。通过2-hop cover我们可以构造出2-hop labels,同样的,通过2-hop labels我们也可以构造出2-hop cover。然后后面的篇幅重点是要讲,要怎么样找到最小的2-hop cover

Definition 4.3. (Densest subgraph)

Given an undirected graph G = (V, E), find a subset S ⊆ V for which the average degree in the subgraph induced by S is maximizedi.e., a set that maximizes the ratio |E(S)| / |S|, where E(S) is the set of edges connecting two vertices of S.

在现在这一部分提最稠密子图主要是为了说明找到最稠密子图的方法,然后引申出找到最小的2-hop cover的方法,但是感觉并没有什么联系。后面会频繁地用到Densest subgraph这个概念的:

This algorithm iteratively removes a vertex of minimum degree from the graph. This generates a sequence of n subgraphs of the original graph. The algorithm returns the densest of these subgraphs.

迭代地从图中移除最小度数的点,这样就形成了n个子图。然后还提到了2-approximation algorithm

提到了Set Cover Problem,这个问题的目标是:

The goal is to find a subset U ⊆ S, such that US∈U S = T, and ΣS∈U w(Si) is minimized.

这个问题贪心算法的过程是这样的:

We maintain the set of uncovered elements T’, which is initialized to T’ = T. In each iteration of the algorithm, we add to U a set S, which maximize the ratio |S∩T’|/w(S) . We iterate until T’ = Ø.

对于简化的Set Cover Problem,就是给定一个集合T,和这个集群的一些子集,要找到最小个数的子集,让他们能cover住T,w(S)≡1。假设没有被Cover住的集合是T’,这个贪心算法迭代的含义就是找到那个和T’有最多交集的子集。

假设我们需要Cover的集合是T = { (u, v) | Puv ≠ Ø },T是图中所有可达的顶点对。

现在定义对于每一个顶点w,有这样一个集合: S(Cin, w, Cout) = { (u, v) ∈ T | u ∈ Cin , v ∈ Cout , w ∈ Buv }

这个集合的意思是通过顶点w,找到列多的顶点对(u, v),让w位于u到v的路径中。可以这样来理解,Cin是x -> w的所有点,Cout是w -> x的所有点。然后对于这个集合,定义它的权重为:|Cin| + |Cout |。然后我们称 w 是这个集合的中心。

然后我们就可以使用上面Set Cover Problem一样的贪心算法,现在的迭代条件是使:

|S(Cin, w, Cout) ∩ T’| / (|Cin| + |Cout |)

这个值最大。

算法实现

首先引入了center-graph的这个概念,这个很有意思,对于每一个点都会构建出一个center-graph。在这个 center-graph (cg) 中(假设我们现在构建的是节点wcenter-graph):

  • cg中的节点是以whandle的hop
  • cg中的边可以认为是经过w的path

approximate densest subgraph (ADS) 的实现:

把节点按照剩下的degree进行排序(初始化的时候可以使用bucket-sort),

不同的center graph中的边,如果对应的path已经被选中了,那么就认为是covered,可以从center-graph中移除了。所以对于ADS来说,在某一个center-graph中进行selection,会导致从其它的center-graph中删除边。

We iteratively select subsets of hops and edges which constitute an (approximate) densest subgraph in some center-graph.

先在heap中维护所有的center,对于某一个center,对应的key是 |E(Gc)| / |Gc|,就是Gc中的边数除以顶点数(是不是很熟悉,又是Densest subgraph相关的概念)。

每次从heap中找到拥有最大keycenter;如果上次的ADS computation从Gc中移除了一些边,那么需要重新计算key,然后把c放入到heap中;如果选择出来的Gc没有被操作过,那么就从Gc中找到Densest subgraph,添加selection中,然后把Gc剩下的部分再放到heap中。

总结

2-hop cover由于是解决reachability和distance问题的,所以是path-based索引。后面在这个基础上还延伸出了基于动态图的2-hop cover和类似的3-hop cover。之前交流比较naive的关于path index的想法时,也在想类似的减少索引数据量的方法,2-hop cover是一个很好的启发。