Compressed indexes for string searching in labeled graphs (WWW '15)
Compressed indexes for string searching in labeled graphs (WWW '15)
Paolo Ferragina, Francesco Piccinno and Rossano Venturini.
概要
ラベル付きグラフの索引を作り、それに対して検索するというのはソーシャルネットワークや知識グラフを効率良く処理する上で重要になりつつある。 一方既存のグラフ索引手法はグラフの隣接関係だけしか扱っていない。この論文では各ノードに可変長文字列のラベルがついたグラフの索引手法を提案する。
Facebookのエンジニアによって開発されたUnicornというソーシャルグラフの索引プラットフォームがあるがこの論文ではそれをされに発展させる。 例えば「あるユーザの２近傍にいるユーザ（友達か友達の友達で）で特定のprefixをもつものをリストアップする」といったクエリに応答したい。これはFacebookなどで友人などを探すときに良く起こりうるシチュエーションである。 このようなクエリに対応するにあたって愚直に全てのユーザのprefixを見ていくというのは現実的でない。なぜなら第二近傍の頂点数は非常に大きくなることが多いからである。この論文では以下の問題を高速に処理するためのデータ構造とアルゴリズムを提案している。
- 隣接する頂点で指定されたprefixを持つものをリストアップ
- ２近傍の頂点で指定されたprefixを持つものをリストアップ
- ２近傍の頂点で指定されたprefixを持つもので各頂点にあらかじめ与えられているスコアが大きいk個をリストアップ
頂点番号を文字列の辞書順に並び替えてRange Queryをやる。スコアを考える場合はRange Maximum Queryを利用して高速化する。されにTop-Kを計算する上でヒューリスティクスをいれる。 各クエリにおいて最大20-50倍高速化できるらしい。
Global Diffusion via Cascading Invitations: Structure, Growth, and Homophily Ashton (WWW '15)
Global Diffusion via Cascading Invitations: Structure, Growth, and Homophily
Ashton (WWW '15)
Ashton Anderson, Daniel Huttenlocher, Jon Kleinberg, Jure Leskovec and Mitul Tiwari.
概要
ウェブサービスにおいてユーザが周りの人達をそのサービスに招待できる機能がある。 招待されて加入したユーザがさらに他の人をサービスに招待することで、招待による加入のカスケードが広い領域に起こっていく。この現象はウェブサイトの成長などにおいてとても重要なはずなのに今までほとんど研究されてこなかった。この論文ではLinkedInにおいて実際に起こった拡散について調べている。
招待によるカスケードはオンラインソーシャルネットワークにおけるカスケードよりもかなり長い期間によって起こっている。 招待する人と招待される人同士のローカルな同一性（所在地が同じなど）だけではなくカスケード全体での同一性があることを発見した。
実際にはアブストしか読んでいない。
Path Sampling : A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts (WWW '15)
Path Sampling : A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts (WWW '15)
Jha, Madhav Seshadhri, C. Pinar, Ali
概要
名前の通りパスをランダムサンプリングして４頂点の連結部分グラフの個数を近似計算するという論文。３頂点の連結部分グラフ（パスまたは三角形）の個数はグラフの構造を調べるのに役立ちデータマイニングなどに応用がある。Uganderら(WWW '13)によって、４頂点の連結部分グラフの個数を調べることでグラフの面白い性質を調べることが示された。
４頂点の連結部分グラフは組み合わせ爆発によって非常に大きくなるため厳密に計算しようとすると現実のグラフでは数日かかってしまう。この論文では長さ３のパスをサンプルしパス上の４頂点から誘導される部分グラフの個数を数えることで、各連結部分グラフのunbiased estimatorを得る。Chernoff boundによって近似率に対する保証を得ることができ、degeneracy orderingを用いた枝刈りによってさらに良い精度を得ることができる（？イントロだけだとよくわからない）。
実験結果により使用した全てのグラフにおいて相対誤差が1%に収まっていることが示された。Orkut (約２億辺）のグラフにおける計算が１分以内に終了するので非常に高速である。
感想
各個数の絶対値が大きくなるおかげでChernoff boundと相性が良さそう。 部分グラフの各サンプルは簡単に行えるので、良いサンプリング手法さえ考えられれば大勝利感がある。
The K-clique Densest Subgraph Problem (WWW '15)
The K-clique Densest Subgraph Problem (WWW '15)
Tsourakakis, Charalampos E
概要
多くの応用ではクリークに似た大きな部分グラフを見つけたい。適当に定式化するとMaximum-Clique問題との関係でNP-hardになってしまい近似計算すら難しくなってしまう。一方densest subgraphは多項式時間で検出するアルゴリズムが知られているが得られた部分グラフはクリークと比べると非常に疎であることが多い。
この論文ではdensest subgraphを一般化したk-clique densest subgraph問題というものを提案する。与えられたグラフ \(G = (V, E) \)に対して\(argmax_{S \subseteq V} \frac{t_k(S)}{|S|} \)を求めるのがk-clique densest subgraphである。\(t_k(S) \)はSに誘導される部分グラフに内部のk-cliqueの個数. \(k=2 \)のときこれはdensest subgraphと一致する。\(k = 3 \)のとき、すなわち三角形を含む割合が最も高い部分グラフで面白い結果がでるらしい。
このk-clique densest subgraphというのはdensest subgraphと同様に多項式時間で計算することができ、\(\frac{1}{k} \)近似の高速なアルゴリズムある。厳密な計算を高速に行うためにはMap-reduceを利用している。
Footballというグラフにおいてdensest subgraphと\(k = 3 \)でのk-clique densest subgraphを求めた結果、densest subgraphではグラフ全体を出力してしまい辺密度\(\frac{|E(S)|}{|S| \times (|S| - 1) \div 2 } \)が0.1くらいしかなかったがk-clique densest subgraphによってもとまった18頂点からなる部分グラフは辺密度が0.5くらいありかなりcliqueに近かった。
実際の応用例についても示したらしいがそこは読んでない。
Density-friendly graph decomposition (WWW '15)
Density-friendly graph decomposition (WWW '15)
Nikolaj Tatti and Aristides Gionis.
概要
k-core分解はグラフの階層的構造を見る上で基本的な操作として知られているが、 k-core分解で得られた部分グラフの内部が密になっているとは限らない。 この論文ではlocally-denseという指標をグラフに対して定義して、 k-core分解に似たlocally-dense decompositionというものを提案する。 locally-dense decompositionをO(|V|^2|E|)時間で求める実験的に高速なアルゴリズムと線形時間の２近似アルゴリズムを提案する。 locally-dense decompositionとcore decompositionを実行時間と得られた部分グラフのdensityを実験して比較した結果、locally-dense decompositionの方が良いということがわかった。（どのくらい良いかは読んでないのでわからない・・・）
locally-denseとは？
locally-denseとはその部分グラフの内部が外部より高いdensityを持つ部分グラフのこと。(部分グラフXのdensityは\(\frac{|E(X)|}{|X|} \)。 ) 部分グラフ\( W \subseteq V \)がlocally denseであるとは\(X \subseteq W \)と\(Y \subseteq V \setminus W \)で \( d(X, W \setminus X) \le d(Y, W) \)を満たすものが存在しないということ。( \(d(X, Y) = \frac{E(X) \cup E(X, Y)}{|X|} \) ) 雰囲気としては１つの頂点からスタートして順番に頂点を付け加えていったときに、最初の方に加えた頂点集合\( X \)の方が後で加えた頂点集合\( Y \)よりも高いdensityに貢献しているということだろうか。
locally-dense decompositionとは以下の性質を持つ。（詳細は知らない）
- より内側にある部分グラフの方が外側よりも密
- 一番内側にある部分グラフがdensest subgraphに対応
- 効率よく計算できる
Goldbergによる最小カットを用いたdensest subgraphの計算アルゴリズムを拡張して厳密計算できるらしい。
Spanning edge centrality: large-scale computation and applications (WWW '15)
Spanning edge centrality: large-scale computation and applications (WWW '15)
Charalampos Mavroforakis, Richard Garcia-Lebron, Ioannis Koutis and Evimaria Terzi.
概要
Spanning edge centralityは各辺を含んでいる全域木の割合がどのくらいであるかによって定まる辺の重要度の指標。 Spanning edge centralityは実際のネットワークにおける辺の重要度をうまく捉えているようであるにも関わらずあまり関心を集めて来なかった。 これはSpanning edge centralityの計算に非常に多くの時間を要していたためだと思われる。 この論文では既存の理論的成果をうまく組み合わせることによってほぼ線形時間の乱択近似アルゴリズムを提案する。 さらに実際のネットワークにおける実験によってSpanning edge centralityがノイズに対して強い耐性をもち、情報拡散における重要度を良く捉えていることを示す。
アルゴリズム
辺e={u, v}のspanning edge centralityがu-v間のeffective resistanceと等しいことを利用し各辺のspanning edge centralityを線形方程式で記述する。 これを解くとspanning edge centralityが求まるのだが厳密にやるとラプラシアン行列の擬似逆行列を求める必要があり頂点数の二乗よりおそくなってまずい。 提案手法では、以下のような道具を用いて計算を高速化している。
- effective resistanceが各頂点に対応する単位行列をBL-1 (Bは接続行列)で射影したベクトル同士の距離で表せることに着目。
- BL-1 e_uはm要素からなるベクトルなので、Jonson-inenstrausの補題を使って長さlog(n)のランダムベクトルを用いて低次元のベクトルに射影して距離の計算を高速化。
- L-1を用いてベクトルを射影する必要が出てくるのだが高速なSDDソルバを使えばほぼ線形時間でできる。
実験
辺を何％か増やしたり減らしたりして実験している。数％程度の変化ではspanning edge centralityは対して変化しない。一方betweenness centralityはめちゃくちゃ変わる。また、各centralityの高い辺集合を削除したときにICモデルによる情報拡散を見るとspanning edge centralityの高い辺を削除すると情報拡散が大きく減るということがわかる。betweenness centralityの場合は一番高い奴らよりもそこそこ高い辺を抜いた方が情報拡散が減る。
機械学習に出てくる指標（true positiveとか）
毎回混乱する。 true positive, false positive, true negative, false negative についてを見た。 prefixがtrueになっているのが正しい結果が得られているやつ。false positiveは本来正解と言ってはいけないにも関わらず判別器が正解と言ってしまったやつ。
