DSOC研究員の吉村です. 最近はコンビニスイーツにハマってます. この時期 (執筆時点で10月ごろ) になると, 芋, 南瓜, 栗系の物を探しては色々試しています.
さて, 前回からしばらく空いてしまいましたが今回は「グラフ」についてです. 近年では GCN や, GraphSAGE などのグラフ学習手法が有名ですが, 今回はもう少し別の観点から「グラフ」と機械学習について見ていきたいと思います.
グラフとは
グラフについて説明します. グラフは頂点 (ノード) 集合 と, 枝 (エッジ) 集合
の組
で定義されます. 頂点は一つ一つの事例を表し, 枝は頂点同士の関係を表すことが多いです. ここで, 頂点集合の要素は
で, 枝集合の要素は
で表します. ここで述べたように, グラフを用いることで事例と事例との間の相互関係を直接的に表すことができるようになります. グラフで表すことができるものは, 分子構造, SNS ネットワーク, 共著者ネットワーク, www のリンクネットワーク, ルータネットワークなど多岐に渡ります.
グラフを扱う難しさ
グラフを扱う難しさの原因はその構造の特殊さ故に, 計算機上で効率よく扱う方法が自明ではないところにあると思います. それがなぜ難しさに繋がるのかというと, 大きなグラフを愚直に処理しようとすると, メモリ (空間計算量) の問題で処理できないということが頻繁に起こるためです. グラフを扱う方法として, 隣接行列 (adjacency matrix) を想像される方がいらっしゃると思いますが, ほとんどの場合その要素はスパースなので, これが効率の良い形であるとはなかなか言い難いです. 実際に, グラフ を愚直に (スパース性を無視して) 隣接行列としてメモリにのせると
の空間計算量になります. これは頂点数の二乗のオーダーで必要なメモリ数が増えていくということを意味します. 例えば, 頂点数を10万 (比較的小さなSNS程度) としても100億の要素の行列ができるというわけです. ほとんどの場合で
である (可能な枝に対して, 実際に張られている枝は非常にスパースである) にもかかわらずです. これでは, もう少しグラフが大きくなると, あっという間に一般的な計算機の上で処理することが困難になります. (クラウドの計算資源を用いれば数テラ程度であれば処理することは一応可能です.)
グラフを扱うパッケージ
グラフを扱うことができるパッケージはたくさんありますが, 前節の問題故に速度性能やメモリ性能はパッケージにかなり依存することに注意が必要です. 言い換えれば, もしかするとパッケージによっては大きなグラフもうまく扱ってくれて, 莫大な量のメモリ資源がなくとも, 処理できる可能性があるということです. 私は Python User なので Python でグラフを扱うことができるパッケージについていくつか紹介しておきます.
- NetworkX
- networkit (maintained by the Research Group Modeling and Analysis of Complex Systems of the Institute of Computer Science at the Humboldt-University of Berlin.)
- graph-tool
- PyTorch-BigGraph (created by Facebook Research.)
- Pytorch-geometric
- DGL
- Spektral
上記思い浮かぶものをいくつか挙げました. ネットワーク分析用のパッケージ (NetworkX, networkit, graph-tool) であったり, 深層グラフニューラルネットワーク用 のパッケージ (PyTorch-BigGraph, PyTorch-geometric, DGL, Spektral) であったりするので, 用途に合わせて使ってもらえると良いかと思います. ネットワーク分析用のそのほかのパッケージや資料についてはこちらが詳しいです. また, DGL については弊社研究員の李の連載ブログもあります.
グラフを取り扱う分野
グラフを取り扱う分野はたくさんあります. 本連載は機械学習に関する記事を書くという前提のもと行っておりますが, どんな分野があるか一通り確認しておきます. 概観を知っておくことで, 自らが解決したい課題に対する解決策を得るためにはどのあたりを探ればいいのかがわかってくると思います. 下記に私の理解を示しますが, 当然グラフを扱っているという部分は同じなので, 重複しているトピックが存在することを理解することも重要そうです.
グラフ理論 (Graph Theory)
グラフ理論は主に数学に背景を持つ分野です. (ドメインに依らず) グラフそれ自体が持つ性質についての研究が主になっており, 一段抽象的な分野として離散数学があります.
グラフ機械学習 (Graph Machine Learning)
グラフ機械学習はグラフや、グラフ内部の頂点、または、枝を入力として統計的な処理に基づいて何らかの出力を得ることを目的としています. 例えば, 分子の性質などを予測する場合などは, 入力が個々の分子構造 (グラフ) で, 出力がその性質となります. また, グラフ機械学習では, リンク予測や頂点分類などが主に扱う問題設定となります. グラフを入力とする場合にはグラフが複数あることが前提である一方で, 頂点や枝が入力となる場合にはグラフは一つであることが多いという点でこれらは少し別の扱いをする必要があるようです.
グラフ機械学習はその性質から, 本質的には各グラフや頂点などをどのように特徴量に落とし込むかに興味があるとも言えそうです.
グラフマイニング (Graph Mining)
グラフマイニングはより数理的な側面が強い分野のようです. 例えば, 二つのグラフが同じグラフであるかどうかを判定するグラフ同型問題や, 特定の部分グラフを検索する問題, そして, 多頻出の部分グラフを見つけるなどの問題を扱ったりします.
複雑ネットワーク理論 (Complex Network Theory)
複雑ネットワーク理論は実際の世の中にある大規模な個々のネットワークの性質を研究する学問で, ドメインはその時々で様々です. 例えば, 初期の方に研究されていたものだと web ページ間のリンク構造などが挙げられ, それらがどのような生成過程で発生しているのかや, ドメインごとにどんなネットワークの違いがあるのかなどを定量的に評価・比較することに主眼が置かれているようです.
社会ネットワーク理論 (Social Network Theory)
社会ネットワーク理論はつながりそれ自体にどのような性質があるのかや, どうやってできているかに特に関心があり, 研究がされている分野のようです. こちらは, 弊社研究員前嶋の連載ブログが詳しいです.
まとめ
今回はグラフを扱う問題設定の概観について, グラフを扱うこと自体の難しさから, それを実際に扱えるパッケージ, そして, どんな分野で研究がなされているかなどを見ていきました. 今自らが直面している課題が何なのか, 何を解決したいのかがわかればより適切な分野の上の研究をサーベイすることができるようになりますし, 適切なツールが使えると思います. 今回は機械学習要素が少なかったので, 次回は満を持して機械学習におけるグラフの扱いについてみていきます. 次回もお楽しみに！
▼【ML Tech RPT. 】シリーズ
buildersbox.corp-sansan.com
