Accelerating Graph Adjacency Matrix Multiplications with Adjacency Forest - todo314 @ ウィキ

Accelerating Graph Adjacency Matrix Multiplications with Adjacency Forest

• Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, Masaaki Nagata
• SDM 2014

概要

• AXみたいな行列計算を高速にしたい
• Aの列中の値が同じ（確率遷移行列とか）だと余分な計算を省ける
• さらにAを分解して個々に省略手法を適用できる
• 3倍位速くなった

提案手法 Single Tree Adjacency Forest(STAF)

• Column-scaled nonzeros property
  • 行列の各列j中の値＝0 or cj
  • こんなやつ $$ A = \left( \begin{matrix} 0&0&0.33&0.5 \\ 0.5&0.33&0.33&0.5 \\ 0.5&0.33&0.33&0 \\ 0&0.33&0&0 \end{matrix} \right) $$
  • 他にもdocument-wordのバイナリ行列とか色々
• 隣接リスト形式で行毎に持っているとする
• と、接尾辞が同じ所をまとめて計算できる
• 例: 右上の $$0x_1 + 0x_2 + 0.33x_3 + 0.5x_4$$ と $$0.5x_1 + 0.33x_2 + 0.33x_3 + 0.5x_4$$
  • $$ 0.33x_3 + 0.5x_4 $$をまとめて計算して、左に伝搬する感じにすると良い、演算回数が減る
  • 論文中の木で表現した図を見たほうが早い
• 構築はTrieと同じノリ

• あまり良くないので、もうちょい頑張る
• Aを列で分割する
• $$ A^{(1)} = \left( \begin{matrix} 0&0&0&0 \\ 0.5&0.33&0&0 \\ 0.5&0.33&0&0 \\ 0&0.33&0&0 \end{matrix} \right), $$ $$ A^{(2)} = \left( \begin{matrix} 0&0&0.33&0.5 \\ 0&0&0.33&0.5 \\ 0&0&0.33&0 \\ 0&0&0&0 \end{matrix} \right) $$
• それぞれに対して適用、分割した結果のマージはちょっと考えれば出来る
• どうやって分割するのか？
• 難しいので、ヒューリスティックなスコア関数を作って貪欲に振り分け

実験

• PPRとNMF
• 最大で300%高速化

まとめ

• もうちょい行けそう
• 列（というかindex）の順番もすごく大事（に見える）なので、そこを含めた分割をするといいのかな？

PageRank SDM 行列計算

2017/01/19