長らく（２年くらい）NetworkX のユーザだったが、今回 Graphlab Create に乗り換えた。それと同時に、pythonz + virtualenv から、anaconda に乗り換えた。

ここに書いていることは、自分が何か大事なことを勘違いしていなければ恐らく当たり前のことなので、わざわざ言わなくても、と思われかねない。だけど、グラフのプラットフォームを調べている初学者には多少有用かもしれないので書き残しておく。

乗り換えた主な理由は、メモリの使用量。NetworkX は、API は豊富だし、速い。だけど、メモリの使用量が多い。そのため、大きなグラフを処理しようとすると swap してしまうことが度々あった。一人で占有しているマシンであればそれでもまま許されるのだが、共有マシンでそれをやると随分嫌われてしまうのでこまる。

そこで、目を付けたのが Graphlab Create。元々の Graphlab は C++ のライブラリだったし、エッジの weight 以外の属性値がつけられなくて使いづらそうだった。それが Python のライブラリになり、ノードとエッジそれぞれに属性がつけられるようになっていて、これなら選択肢になりそうだ、と思った。

Graphlab Create ドキュメントの中の SArray の項には以下のようにある。SArray は グラフデータ（SGraph）を実現するための基本となるデータ構造。

SArray is scaled to hold data that are much larger than the machine’s main memory. It fully supports missing values and random access. The data backing an SArray is located on the same machine as the GraphLab Server process. Each column in an SFrame is an SArray.

なるほど、主記憶よりも大きなデータを扱えるように作られていると。求めていたのはこれだ、ということで、使ってみることにする。すると、確かに、メモリに使用量は減らせる。体感は、５分の１くらいになるイメージ。おお、これは素晴らしい。

ところが、グラフ解析のアルゴリズムを実装しようとして少し困ったことに気づく。使えそうなグラフ解析の API が SGraph.triple_apply しかない。これは、（Pythonではめっちゃめんどくさい）並列処理ができるので、解析内容がハマればとても有用だろう。だけど、実用的なアルゴリズムが全然実装されていない。NetworkX にはトポロジカルソートが実装されているが、Graphlab Create にそんなものはない。こんなものですら自分で実装しなければならない。

そして、トポロジカルソートを実装し始めて気づくことが、「あるノードから出ているエッジ（out-edges）を調べる」というような処理がめちゃくちゃ遅い。データのフットプリントが小さいうえに全データがメモリ上に載らなくてもいいように作っているのだから当然っちゃ当然。だけど、とても使えるようなスピードではない。トポロジカルソートできるのが、秒あたり100ノードくらいだったりする。

しばらく試行錯誤した後、結局、あらかじめすべてのエッジの一覧を取得して、「あるノードから出ているエッジ（out-edges）を調べる」ことが高速にできるようにリストを使ったデータ構造を作ることにした。これをすると、一気に秒あたり２万ノードくらい処理できる。この処理の間は、Graphlab Create のデータ構造は触っていないので、これは Python のポテンシャルなんだけど。Graphlab Create でのトポロジカルソートは誰かの役に立つかもしれないので、どこかで公開しようと思う。

というわけで、Graphlab Create は NetworkX に比べるととても省メモリなので、NetworkX を使っていてグラフのサイズがメモリに乗りきらず困っている人は是非プラットフォームを変えてみることを勧める。ただし、Graphlab はハマる解析以外はグラフ向きのデータ構造くらいにしかならないことを分かっておくのが良い。