Graph Crest Meeting @ 東工大

以下、渡部君議事録
--
CREST meeting

uno先生
情報学研究所
グラフネットワーク、離散構造アルゴリズムの研究
計算量（オーダ）、ビッグデータの高速処理


計算量 ( n=1億(現在)→10億(将来) )
｜NP-comp
｜n^3 ( 藤澤先生 )
｜
｜【n^2】 ← 重要 !!
｜ クラスタリング,etc..
｜ m*n^1/2
｜n log n ( Google )
｜n
｜log n
｜ web-service


データと問題
・系列データ
→具体的なタスクはなにか？定まっていない。
・離散＆グラフ (中心性やクラスタリング、直径)
→過去、最大流からクラスタリング、最小カットを求めるモデルもあったが…
→得られる解が求めたい解と食い違っていることが多々ある（グラフ全体に関して）。
→グラフ全体の評価よりも局所的な分析の方が重要性が高い。

藤沢先生、避難シュミレーションでは局所的なものよりグラフ全体によるものの影響が大きい？
→京都市などのグラフはグラフ全体が関与する（グラフの性質によるものである）
→全部が全部ではないが最大流、最小費用流がネットワークに役立ちにくい？

・マッチング問題（１対１の暗号化、匿名化 anonimization)（一対一）
→アルゴリズムの開発はされているがスケールが大きいと動かせない（せいぜい１万件程度？）
→暗号化をしても情報を公開してもよいのか？政治的問題。
鈴村先生、グラフの分割性は高いのでは？
→それほど並列性は高くない？
→sensitiveなものなのであまりデータがない

・最小費用流（マッチングの拡張）割り当てが解ける（多対多）　　　行列の最小固有値問題

→大規模スケールで有用な単純なアルゴリズムしかモデル化に利用されない（KMeans,BFS,etc…）
→目的解を得るためための様々なアルゴリズムの構築が必要
→高度なクラスタリングアルゴリズムなら目的解（グラフの性質、局所性）を見つけれる
→がオーダーが問題で大規模データに対応できない
→KMeansなら動くは動くが…十分な目的解は得られない...

脇田先生、スーパーノードを除外して考えてみるのは？

・大規模ストリーム処理
データ解析に時間の概念をいれる、
データを変化するものとして考えなければならない
データを捨てる。genom generator？爆発的なデータは？
→メモリ上にのらないデータはSSDなど。
→モデルによる。場合によりけり。

バッチならできる処理も（定数メモリに対して無限（高速）に流れてくるデータ）には対応できない
→ストリーム処理
誰が誰と通信を行っているか解析（sparseな行列ならば可能になる）
→あるデータにメモリで処理できる枠を決め、時間軸をずらせば実現できるので工学的にストリームと違いがない？
→ストリーミングアルゴリズムはあまり将来性がない？ ストリーミングでは粒度が細かすぎる、
問い合わせの頻度が高いものはインクリメンタルなアルゴリズムはおもしろい。

・大規模ストレージ
cps (cyber phisical system)
実システムにたくさんのセンサーを置いて、人間や経済の動向などを分析するシステム
アプリケーションによるが系列データとは限らない。
今まで見えなかったデータを見たいという要望（例：人の動向からどの程度運動不足の人がいるか）
事故が起きる→過去のデータは使わないが→cpsでどこの交差点で事故が起きやすいかがわかるようになる
時間の軸は

２次記憶を利用すると大規模データは手に負えない。
メモリとSSDの階層化はアルゴリズム屋は考えてない。理論の方向から難しいのでは？
メモリに収まっても時間がかかりすぎる場合も。
ネットワーク型のアルゴリズムは並列化がむずかしい

- - - - - - - - - -
集合の類似性を調べるアプリケーションについて
たくさん（１億）のデータから前後のつながり？から単語の意味が似ているなど。
頻度の高いデータを外すことで計算量を減らす→３,４日かかる
|A∩B| / |A∪B|
このような考えはグラフ解析そのものに用いるのではなくグラフに関するものの高速化アルゴリズムに使える？
- - - - - - - - - -

・グラフ視覚化
大規模なグラフに関してはあまり議論されていない（バネモデル）
ゲノムではドットプロット
上の類似性が調べられれば十分できる
大規模なデータを可視化しても人間には直感的に理解出来ないので
うまく表現できるようなモデル、方法を考える必要があるのではないか？

藤澤先生、グラフが理解できるような技術者を養成！訓練によって見えるようになるかも！
脇田先生、26日にitohさんがくる？

クリークぐらい密な情報は必要ない。密な情報は求められていない。


ネットフリックス
想像技術、作り込み
個々のデータを集めてきたパラメータを変えてチューニング→動いた人が勝ち？

雁瀬さん
グラフのデータを抜き出してきたときにそれが有用かそうでないかの判定は？
少なくとも、といった条件を抜き出しておく。主観の問題がある？
グラフ処理は並列化しにくいが、グラフに対して前処理を行う場合は？
→前処理を行っても2転3転計算し直し、速度があがらない場合がおおい

遠藤先生
コンピュータが大きくなってグラフ解析は有用になるか？
知識抽出の世界の人にはあまり全体を意識していない（局所的なものだけ）
グラフアルゴリズムは並列化しにくいものが多い
並列化によって精度が下がってしまうものは許容されるか？
アプリケーションによる。クラスタリングなら許容される？
近似は？
近似によって受け入れられないものもある（バイオ）一方ヒューリスティックな解法を使っていたり。
自然言語処理分野では結果のみを意識するので途中の近似による
TSUBAMEの運用、ネットワークの可視化