Compact and Scalable
Graph Neighborhood Sketching(KDD’16)

秋葉 拓哉 (Preferred Networks)
⽮野 洋祐 (リクルートホールディングス)2016/08/09 @ ERATO 感謝祭 Season III

1

現代の⼤規模グラフの例

ウェブグラフソーシャルグラフ

秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)などなど……

2

グラフから得たい情報
1. 頂点の重要度
2. 頂点間の類似度・関連度
3. グラフの性質
4. ……
例：▶ 検索サービス (Web 検索, SNS 内の検索)▶ ソーシャルメディア解析
テキストのみからは得にくい情報がある

秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

3グラフ上のクエリ処理
1. 索引構築–

グラフからデータ構造を前計算しておき–それを⽤いて質問に⾼速に答える

2. クエリ応答

queries

Graph𝑠", 𝑡" , 𝑠%, 𝑡% , …

Indexanswer
Reachable!
秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

4グラフ上のクエリ処理
1. 索引構築–

グラフからデータ構造を前計算しておき–それを⽤いて質問に⾼速に答える

2. クエリ応答

⽬標: 良好なトレードオフ
スケーラビリティ
前計算時間
データサイズ

秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

クエリ性能
クエリ時間
精度

5

グラフのインデクシング・スケッチング
これまでの多くの研究▶ 特定の問題のみを扱う索引– 例：最短経路のみ，近接中⼼性のみ▶ 理論的な bound なし– 計算量 and/or 精度

All-Distances Sketches (ADS) [Cohen’97, Cohen’15]▶ 様々な値を推定できる▶ 精度保証有りで答えられる▶ ほぼ線形時間で計算・データはほぼ線形空間

理論的には極めて理想的な性質
秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

6

ADS で推定可能な指標▶ Neighborhood Function▶ Shortest-Path Distance▶ Closeness Centrality▶ Closeness Similarity▶ Average Distance, Effective Diameter▶ Reverse Ranking, Reverse 𝑘-NN
▶ Continuous-Time Influence▶ …...

秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

7

ADS の問題点
理論的には「ほぼ線形」であっても実⽤的にはかなりサイズが⼤きい
例▶ 7M 頂点，200M 辺のウェブグラフ
▶ グラフ⾃体は 800MB▶ ADS は 4GB（𝑘 = 16）
控えめな精度パラメータでもグラフ⾃体より随分⼤きい
秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

8

提案⼿法：Sketch Retrieval ShortcutsADS より⼩さく，ADS と同等の推定性能
Sketch Retrieval Shortcuts (SRS)▶ ADS より⼩さいスケッチ：1/3 〜 1/10
▶ 各頂点の ADS を瞬時に復元：数 ms▶ 復元した ADS を⽤いて同様の推定が可能

秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

9

⽬次
1: イントロダクション（ここまで）
2: All-Distances Sketches [Cohen+’15]
3: Sketch Retrieval Shortcuts
4: 実験結果

秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

10

All-Distances
Sketches [Cohen’15]
Part 211

前提C

グラフ 𝐺 = 𝑉, 𝐸 を持っている（無向グラフと仮定）

𝑛 = 𝑉 ,𝑚 = 𝐸

ADB

全頂点 𝑣 ∈ 𝑉 に対して，
スケッチ 𝐀𝐃𝐒 𝒗 を前計算＆保存する．
これを使って⾊々する．

秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

12

ADS の使い⽅
前計算

持っているグラフデータから，全頂点の ADS を計算する．
スケッチ: 𝐀𝐃𝐒 𝒗 𝒗∈𝑽

使⽤
ADS を使って⾊々な値を⾼速に推定する．
推定可能：Neighborhood Function, Shortest-Path Distance, Closeness Centrality, Closeness Similarity,
Average Distance, Effective Diameter, Reverse Ranking, Reverse 𝑘-NN, Continuous-Time Influence, …...

秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

13

All-Distances Sketches の定義
60.13
91030.26

0.28

ADS(𝑣) A∈B0.81
820.8350.19

0.49170.96

0.18

40.32

ランク (後述)
6660.13

0.13

0.13

91030.26

9100.28

30.26

0.81

2170.18

40.32

ADS 1 =
2, 7, 60.81
820.83

50.19

0.49

0.96

0.28

80.83

50.19

30.26

0.81

82

9100.28

1

70.96

0.18

50.19

0.49

40.32

ADS 2 =
1, 3, 6, 7

秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

0.83

0.49

170.96

0.18

40.32

ADS 3 =
2,5,6,714

All-Distances Sketches の定義
定義 1ADS 𝑣 ≔ 𝑢 𝑟 𝑢 < k IJ
H ΦLM 𝑣

定義 2
任意の距離 𝑑 に対する近傍関数 𝑁P 𝑣 のBottom-k MinHash の和集合？？？
秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

15

ランク（ハッシュ関数）▶ 𝑟 𝑣 ：各頂点の乱数ハッシュ値 [0, 1]「ランク」と呼びます
イメージ：
ランクの⼩さい頂点ほど偉い！
▶ 偉い＝保存されやすい（Min-Hash でもハッシュ値最低のやつが保存されていた）

秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

16

ADS(𝒗) の視覚的な説明
𝑘 = 3 の例

ADS 𝑣 =(MinHash 同様にパラメータがある）

距離順に頂点を⾒て⾏って，今まで⾒た頂点の中でrank が k 番⽬以内ならADS に含む

ランク性質•••

⾃分より左下に点が𝑘 個未満の頂点

𝒗 からの距離

ランク⼩さい⽅から 𝑘 個は必ず含まれる近い⽅から 𝑘 個も必ず含まれる
遠くなってゆくほど含まれにくくなっていく

秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

17

ADS のサイズADS 𝑣≅ 𝑘 1 + ln 𝑛 − ln 𝑘 = 𝑂 𝑘 log 𝑛𝒌 を⼤きくするほどスペースを使う

よって，合計の使⽤メモリは：

しかし精度が良くなる（後述）𝑂 𝑘𝑛 log 𝑛𝑘 を定数とすると，スペースは頂点数にほぼ線形（→ 理論的には⾼いスケーラビリティ）
秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

18

ADS の計算
詳細は省略しますが難しくない
1. 枝刈り Dijkstra を全頂点から実⾏
2. 動的計画法
𝑂 𝑚 + 𝑛 log 𝑘 𝑘 log 𝑛 時間で構築可

秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

19

ADS による近接関数の推定
HIP Estimator [Cohen, PODS’14]

𝑛ZP 𝑣 =

[M∈^_` A , Pa A,M bP

𝜏M𝒖ランク

各 𝑢 について，
そいつより左で 𝑘 番⽬に⼩さいランク

1
𝜏M

3

𝑘=32

1𝒗 からの距離
秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

20

ADS による近接関数の推定
HIP Estimator𝑛ZP 𝑣 =[M∈𝐀𝐃𝐒 𝒗 , Pa A,M bP

1
𝜏M𝒗 の ADS だけから推定可精度

𝐶𝑉 ≤ 1/ 2(𝑘 − 1)
（CV = 標準偏差 / 平均）

秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

Sketch Retrieval
Shortcuts （提案⼿法）
Part 322

概要：Sketch Retrieval Shortcuts
アイディア
1. ADS を新たなグラフ 𝐺^_` とみなす
2. 𝐺^_` から ADS(𝑣) を取得するアルゴリズムを定義
3. 取得アルゴリズムが正しく動作するために必要⼗分な辺のみにする
ADS の全体よりも遥かに⼩さいデータ構造となるがADS が瞬時に取得できる！
秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

考え⽅：ADS 取得の難しさ
前提：頂点 v の ADS(v) を必要に応じて取り出したい▶ 全頂点保存しておく → 容量多すぎ▶ 前処理なし → グラフ全体の探索が必要，遅すぎ
下図のように，「⾶び地」があるので，グラフ全体を調べる必要がある

うまく中間を取れないか？
666

0.13

0.13

0.13

910

30.26

9100.28

30.26

0.81
20.26

20.81

0.49

20.83

50.19

50.19

0.49

0.49

1717170.96

0.18

0.96

0.18

0.96

0.18

40.32(a) A graph.

0.28

80.83

530.8180.19

9100.28

40.32(b) The vertices in A(1).

40.32(a) ADSs as a gra

Figure 1: Examples of a graph and an ADS (k = 2).

Figure 2: AD

generalidea underlying
SRSs
is to overcome the need
秋葉+, Compact and ScalableTheGraph
Neighborhood
Sketching(KDD’16)from u to v for the reac
ADS entries with dist考え⽅：制限された探索による ADS 取得

Algorithm 1: Retrieving the ADS

Procedure Retrieve-ADS(B, u, k)
⽬標：ADS 取得時にちょっと計算をしてもいいA
an empty all-distances sketc
Qa priority queue with only owhile
Q is not empty do▶ グラフ全体の探索をしたくない(, v)Q.Pop;
123
4

⼤規模なグラフのサイズに⽐例した計算量は無謀

uv

if u 62 A and r(v) < ⇡(u, v) t
Add (v, uv ) to A;
for all ( vw , w) 2 B(v) do
Q.Push( uv + vw , w)

5

▶ ADS 内の頂点のみを訪れる探索で取得できるか？
678

勿論，これは元のグラフ上では実現できない

return A;

966

6

60.13

0.13

0.13

0.13
2

91030.26

100.28

30.26

0.81

9100.280.26

0.19

20.19

70.96

0.18

20.83

50.49
120.190.32(a) A graph.

1

70.96

0.18

140.32(b) The vertices in A(1).

Figure 1: Examples of a graph and an ADS (k = 2).

0.96

7
1
0.18
0.96

9 10

3 10
0.26
0.81

0.280.26
28

8
2
0.83
0.19

0.83

55

0.19 0.49

0.49

40.283
0.81

80.83

510
3
0.26
0.81

0.81

8
2

92
2

0.

0.49
740.18

10.96
47 1
0.18
0.96

0.32

0.32

(a) ADSs(a)as aRetrieving
graph.
(b) SRSs asA(1).
(b)aFigure 2: ADSs and SRSs as grap
Figure 3: Retrieval of AD

from u to v for the reachability property, and B
The general idea underlying SRSs is to overcome the needwith a plain ADS as mentioned in Se
秋葉+,Compactand
Scalable
Graph
Neighborhood
Sketching(KDD’16)
ADS entries with distance at most di 25
that hfor a full search on a graph and realize the retrieval of analgorithm Retrieve-ADS is explained考え⽅：グラフとしての ADS と SRS

Algorithm 1: Retrieving the AD

Procedure Retrieve-ADS(B, u, k)
ADS 内の頂点のみを訪れる探索をしたい？
Aan empty all-distances ske
Qa priority queue with onlywhile
Q is not empty do▶ ADS をグラフだと思うと，これは成功する(, v)
Q.Pop;
1234

当然．全 ADS 内の頂点に 1 hop で到達．

uv

if u 62 A and r(v) < ⇡(u, v)
Add (v, uv ) to A;
for all ( vw , w) 2 B(v)Q.Push( uv + vw , w

5▶ 無くても成功する辺がいっぱいある
return A;▶ 必要最低限の辺に選別したのが SRS（提案⼿法）
678

96

60.13

0.13

60.13

2910

30.26

9100.28

30.26

0.81

0.19

220.190.49

170.960.18

50.32(a) ADSs as a graph.

170.960.18(b) SRSs as a graph.

Figure 2: ADSs and SRSs as graphs.
fromto v for andthe Scalable
reachability
and Bi (u) contains
秋葉+,uCompact
Graphproperty,
Neighborhood
Sketching(KDD’16)

20.83

50.19

0.32

0.26
824

10

0.28

20.83

0.49

40.81

80.83

53

0.26

0.81

82

910

0.28

0.49
170.96

0.18

14

0.96

0.32

(a) Retrieving A(1).

(Figure 3: Retrieval of A

with a plain ADS as mentioned in S26
algorithm Retrieve-ADS is explaine

Add (v, uv ) to A;
for all ( vw , w) 2 B(v) do
Q.Push( uv + vw , w);

6

アルゴリズム：SRS から ADS を取得
78

return A;

9

Algorithm 1: Retrieving the ADS of vertex u

6Algorithm 2: 6Constructing SRSs from ADSs
(naive).
0.13

Procedure Retrieve-ADS(B, u, k)
1Aan empty all-distances sketch;2Q
a priority queue with only one element (0, u);3while Q is not empty do4( uv , v)
Q.Pop;
5
if u 62 A and r(v) < ⇡(u, v) then6
Add (v, uv ) to A;
7for all ( vw , w) 2 B(v) do
8Q.Push( uv + vw , w);
9return A;

0.13

Procedure Construct-SRS-Naive(G= (V, E), A, k)
9910
10331B[u];forallu2V;
0.28
0.28
0.26
0.26
0.81
2T 0.81{(2 uv , v, u) | (v,uv ) 2 A(u)};82 Sort T ;230.83550.190.19
4for ( uv , v,u)
2Tdo
0.49
0.49
5Retrieve-ADS(B,1u, k);
7A
710.180.18) to B[u];0.96
6if (v, uv )4 62 A then 0.96
Add (v, uv
47

return B;

0.32(a) Retrieving A(1).

80.83

0.32

(b) Retrieving A(2).

Figure 3: Retrieval of ADSs from SRSs.

5. CONSTRUCTION VIA ADS

we study
construction
algorithms
for retrieval
SRSs. Inwith a Then,
plain ADS
as mentionedin Section
3.2. The
this section,
we designthat
construct 1.
SRSs
fromalgorithm
Retrieve-ADS
is algorithms
explained asAlgorithm
Note
0.13
0.13
ADSs.
First,
weexplain
thebasicalgorithm
withourretrievethat, unless otherwise stated, sorting and priority queues on
9910
10330.28
0.28
and-verify
principle, which
to all of
our construc0.26
0.26
tuplesuse the ascendingorder isincommon
lexicographic
comparison.
0.81 20.81
88tionalgorithms.
Second,wespeedupthealgorithm
by inTo retrieve the ADS of vertex u, in general, the retrieval
220.830.83
55
troducingeager aentry
generation.
0.19
0.19
algorithm
conducts
prunedversion of Dijkstra’s algorithm
0.49
0.49
from u on the SRSs such that it only visits vertices in A(u)77115.1 3).Basic
Algorithm
0.18
0.18
0.96
0.96
44(FigureWe startwith an empty sketch A, and entries
0.32
0.32
重要：ADS に含まれるか否かは探索中の情報のみで判断可能！
We knowthat SRSs
are ofrecursively
are added
in increasing
order
distancesdefined,
to buildandA. theFor inclusion
ofpairs
withlongerdistances
depends
on
pairs
with
(a) Retrieving A(1).
(b) Retrieving A(2).
each visited vertex v with distance uv , we check whether
shorterdistances.forTherefore,
in general,we) needcon(v, uv) is necessaryA, i.e., whether(v, vushouldtobe
Figure%3: Retrieval of ADSs from SRSs.
structSRSs
inascendingorderofdistances.
Algorithm
included in A(u) (Line 5). As A contains all the entries 2outlines
Construct-SRS-Naive,our ⇡(u,first v)
construcin A(v)withalgorithm
smaller distancesat this point,can
グラフサイズの依存が polylog!
tion
algorithm.
Itexamines
theentriesofall
thewith a plain ADS as mentioned in Section 3.2. The retrieval be computed from A. We can use a priority queueADSs
that inascendingorder ranksof distances.
checkeachentry
algorithm Retrieve-ADS is explained as Algorithm 1. Note manages
the top-kin A to Weobtain⇡(u,v) ADS
quickly.
If todetermine
whetheritisnecessaryfortheSRSs,
and
ifso,
that, unless otherwise stated, sorting and priority queues on v is unnecessary for A, we prune the search and do nothing. weadd it. we add v to A and expand the search by entries intuples use the ascending order in lexicographic comparison. Otherwise,
秋葉+,
Compactand
Scalable
Graph
NeighborhoodSketching(KDD’16)
The tricky
partof this algorithmis that,even
for27conTo retrieve the ADS of vertex u, in general, the retrieval B(v). Notethat thelexicographic
comparisonin thepriority
66▶ SRS 上で Dijkstra のアルゴリズムを実⾏する▶ ただし，ADS に含まれない頂点は訪問しない▶ 𝑂g 𝑘時間で動作アルゴリズム：グラフから SRS 構築

ertex uAlgorithm 2: Constructing SRSs from ADSs (naive).

ment (0, u);

3.81

718

Procedure Construct-SRS-Naive(G = (V, E), A, k)1
B[u]; for all u 2 V ;2T{( uv , v, u) | (v, uv ) 2 A(u)};構築時に取得の3
Sort T ;アルゴリズムを利⽤4for ( uv , v, u) 2 T do
5ARetrieve-ADS(B, u, k);
6if (v, uv ) 62 A then Add (v, uv ) to B[u];7return B;

5. CONSTRUCTION VIA ADS▶ 全 ADS を距離が短い順にソート

Then, we study construction algorithms for SRSs. In
this section, we design algorithms that construct SRSs from
0.13
ADSs. First, we explain the basic algorithm with our retrieve90.28
and-verify principle, which is common to all of our construcSRS8 を⼩さい距離の部分から構築してゆくtion algorithms. Second, we speed up the algorithm byin枝刈りラベリング法
0.83
5troducing eager entry generation.
[Akiba+,SIGMOD’13]と類似
6▶ 各エントリを SRS に⼊れるかを判定▶ 判定には取得アルゴリズムを利⽤
5.1 Basic Algorithm
0.49

40.32

取得によって既にそのエントリが得られるのであれば必要ない
We know that SRSs are recursively defined, and the in-clusion of pairs with longer distances depends on pairs withshorter distances. Therefore, in general, we need to con秋葉+,CompactandScalable(KDD’16)om SRSs.
struct Graph
SRSsNeighborhoodin ascendingSketchingorder ofdistances. Algorithm 2rieving A(2).

28省略すること
定義と性質▶ SRS の数学的定義とその性質
構築アルゴリズム▶ より⾼速な構築アルゴリズム▶ ADS を経由しない省メモリな構築アルゴリズム▶ 並列化
更なるサイズ縮減▶ 元グラフでの近傍は除去する
秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

29

実験結果
Part 430

サイズIndex size (MB)104103▶ ADS：通常の ADS

ADS
ADS-c
SRS
SRS-i

▶ ADS-c：ADS + LZ 圧縮 (snappy)

102▶ SRS：通常の SRS

101▶ SRS-i ：SRS + implicit neighbor100

データ：com-DBLP (|𝑉| = 0.3M, |𝐸| = 2M)
4

1664256k▶ 汎⽤圧縮アルゴリズムはほぼ効果なし
各 ADS が短く，反復が少ないため▶ SRS は 𝑘 が⼤きいほど ADS との差が⼤きい
𝑘 = 256 で 10 倍以上の差秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

Time (µs)

復元時間105104103

ADS-c
SRSSRS-i▶ ADS-c：ADS + LZ 圧縮 (snappy)▶ SRS：通常の SRS▶ SRS-i ：SRS + implicit neighbor102101

データ：com-DBLP (|𝑉| = 0.3M, |𝐸| = 2M)

100
10-1

41664256k▶ ⼤きい 𝑘 でも数 ms 程度
𝑘 = 256 で 8ms 程度▶ 復元後は通常の ADS と同様に指標の推定が可能
秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

構築時間
Time (s)10410310▶ ADS-c：ADS + LZ 圧縮 (snappy)

ADS
ADS-c
SRS
SRS-d▶ SRS：ADS 経由の構築▶ SRS-d ：直接構築（省スペース）2101

データ：com-DBLP (|𝑉| = 0.3M, |𝐸| = 2M)
416

64256

kスケーラビリティ▶ 3M 頂点，200M 辺のソーシャルグラフ
▶ 7M 頂点，200M 辺のウェブグラフ
▶ 数時間〜10時間 (𝑘=16)
秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

まとめ34

まとめ
背景：All-Distances Sketches の有⽤性と課題▶ 理論的には優れた性質を持つグラフスケッチ▶ しかし，実⽤的には，サイズがとても⼤きい

提案⼿法：Sketch Retrieval Shortcuts▶ ADS より⼩さいスケッチ：1/3 〜 1/10
▶ 各頂点の ADS を瞬時に復元：数 ms▶ 復元した ADS を⽤いて元と同様の推定が可能

秋葉+, Compact and Scalable Graph Neighborhood Sketching (KDD’16)

35