講演者：塩川 浩昭（筑波大学）
題 目：大規模グラフのためのクラスタリングアルゴリズム
日 時：2017年3月10日(金) 18:00-
場 所：筑波大学春日キャンパス 高細精医療イノベーション棟 308号室
オープニング
二村 本日はわざわざ遠い中お越しくださいましてありがとうございます。
今回の数理人の発表者は筑波大学の塩川先生でして、塩川先生は筑波大学を修士でやられて、NTTの研究所に行って研究活動をされていまして、その中で社会人博士で筑波大で博士号を取られて、その後、筑波大の助教になられたといった方です。個人的な話ですが、私と塩川先生は筑波大学の同期で、そんな同期的なお付きあいをしたりしています。
Ｑ、修士のころからですか。
二村 そうですね、学部と修士が同じだったという感じです。よろしくお願いいたします。
講演
イントロダクション
塩川 ご紹介ありがとうございます。筑波大学の塩川と申します。二村君とは…いや、二村先生と言ったほうがいいかもしれませんが（笑）、彼が三年次編入で大学に入ってきたときに同じ学年で、そこから修士卒業するまで一緒で、海に行ったりとかいろいろ遊びに行ったりしました。
早速ですが研究の話に移りたいと思います。今日は、大規模グラフのためのクラスタリングアルゴリズムということで、私がここ４、５年ぐらいやっている研究の一部をご紹介させていただければと思います。
まず最初に、ほとんど二村先生がご紹介してくださったんですけれども、簡単に略歴紹介をして、私の所属は筑波大学の計算科学研究センターというところになります。多分、多くの方はご存じかとは思うんですけれども、物理や生物などのサイエンス分野をご専門にされている研究者の方々と、ハイパーコンピューティングやデータベースなどのコンピュータサイエンスを専門とする研究者が一緒に研究して、学際的な研究成果を出そうというような研究組織に所属しています。その中でもいろいろ研究室があるんですけれども、私がもともと出身だった北川データ工学研究室でデータベース専門の研究室に所属していて助教をやっております。
研究の興味としては、最近はデータマイニングとかアルゴリズム、特にグラフ分析の高速化ということをやっているんですけれども、最近はそれ以外にも、もともとデータベース系を勉強していたということもあって、データベースで広く利用されるアルゴリズム研究などにも興味があります。例えばデータベースの授業などで結合演算とかって聞いたことありますかね。２つのレコード集合があったときに条件を満たすレコード集合のペアを見つけるといった、非常に渋いアルゴリズムなんですけれども、その高速化の研究などにも最近興味を持って調べていたりしています。
早速、本題に入っていくんですけれども、釈迦に説法になってしまいますが、グラフというのはデータのエンティティとそれらの関連性をネットワークのように表現した最も基本的なデータ構造のひとつです。グラフの形を持っているデータというのは身の回りにたくさんあります。よく挙げられるものですと道路網だったり電車の路線ネットワークなどがありますね。例えば駅がノードになって線路がエッジとして表現されるといいた感じです。このようなネットワーク状になったデータを分析して、その中から渋滞を事前に予測して回避しましょうですとか、渋滞による待ち時間を減らしましょうといった応用に活用していくということが行われています。
道路網以外に非常に有名なのがソーシャルネットワークだと思います。例えば、これはフランスか電話会社が持っているグラフデータなんですけれども、赤色で囲まれているのがフランス語しか話さない人たち、緑色で書かれているのが、ちょっと言語は忘れちゃったんですけれども、フランス語じゃない言語の人たちなんですね。そういった人たちの通話履歴をグラフで表現して可視化してみると、明らかにフランス語圏のコミュニティーとそうじゃないコミュニティというのが出てくるんです。ここでおもしろいのが、２つのコミュニティの間に実は非常に小さいコミュニティーが存在することが分かるんです。実は、この小さなコミュニティはバイリンガルの人たちのコミュニティなんですね。このようにデータを眺めてみただけではわからないような構造がデータをグラフとして表現して分析してみると見えてきたりします。
もっと身近な例を紹介すると、例えばこれは私がウィキペティアから芸能人の記事のリンク関係を抽出して、擬似的に芸能人のソーシャルネットワークを作ってみたんですけれども、これをクラスタリングしてコミュニティを見つけてみると、大体こういう日本の芸能人のコミュニティ構造がどんな感じになっているというのが見えてきます。これが実におもしろくて、例えばAKBとハロプロ系って我々から見るとどっちも同じようなアイドルグループというふうに見えるんですけれども、実は全く別のコミュニティーとしてそれぞれ抽出されるんです。それぞれのコミュニティが強くつながっているコミュニティを観察してみると、AKB系はバラエティの司会者やタレント、男性モデルのコミュニティに強くリンクしているんです。一方でハロプロ系というのはお笑い芸人とタレントに強くリンクしていて、それぞれ出演戦略や共演戦略が違うのかわからないんですけれども、どうやら何かしら活動方針に違いがありそうだということが見えてきたりしました。その他にも、女性アナウンサーのコミュニティはジャニーズのコミュニティと強くリンクしていて共演しやすい傾向にありそうだとか、そういったコミュニティの繋がり方がグラフデータを分析すると結構見えてくるというのが非常におもしろいところです。
こういうふうに、実際に分析すると、例えばコミュニティがわかったり、混雑予測や科学データ分析をしたりと、いろいろな応用があるんですけれども、近年直面している問題としてこのグラフデータが非常に大きくなってきているという点があります。交通ネットワーク規模ですと、大体データ件数がだいたい10の7乗規模なので、まだ処理できるぐらいかなという感じなんですけれども、ソーシャルネットワーク、あとは生物情報系のネットワークになってくると10の8乗から10の9乗というような規模になってくる。これはグラフのノード数が大体１億から10億程度の規模に相当しまして、今まで提案されてきた単純なアルゴリズムで計算しようとすると、なかなか１日とか１週間とかそういった規模では計算できないようなサイズになってきてしまいます。
こういったデータに対して、例えばデータを間引いて近似的な分析結果を高速に求めるというアプローチもあるんですけれども、グラフというのはつながりを分析するようなデータですので、かなり精度が落ちてしまうということが多いんです。なので、いかに高速かつ精度を落とさないで分析するかというのが非常に重要な課題になっていて、私はここ数年ぐらいずっとこの課題に取り組んでいます。
この課題はコンピュータサイエンスの幅広い分野でも広く認識されていて、私がよく参加するデータベースのトップ会議SIGMODでは、ここ３年ぐらい全体の3分の１ぐらいがグラフの論文で占められています。あとは、これはHPC系、スパコン系の会議でGraph500といって、グラフデータ処理のスピードを競う、スピードをもってスパコンの性能を競うといった種目のベンチマークができていて、やはり注目が集まっています。2016年の結果だと京コンピュータが１位だったそうです。かなり幅広いコミュニティで大規模グラフをいかに速く処理するかというのが重要になっていて、注目して研究しているという背景があります。
今回の講演では、このグラフをいかに高速に解くかということに主眼を置いてちょっとお話しさせていただくんですけれども、その中でも特にグラフのクラスタリングについてお話させていただきます。先ほど日本の芸能人のネットワークでお見せした例でもあるんですけれども、グラフから密に互いにつながったようなコミュニティの構造というのを抽出する処理をクラスタリングと言います。このクラスタリングの処理の高速化に着目して、幾つか研究をご紹介させていただこうかなと思います。こういったクラスタが取れると、先ほど紹介した例以外にも例えば脳神経ネットワークから発火部位を特定するなど幅広い応用があるので、最近非常によく研究されているところです。
このクラスタリングに対して、私ここ５年ぐらい研究をやっておりまして、今回ご紹介するのは大きく分けて２つのトピックになっています。一つ目のトピックは、モジュラリティと呼ばれるかなり最近デファクトとされているクラスタリングの指標があるんですが、その指標に基づくアルゴリズムの高速化です。この研究は、昨今非常に注目が集まっている人工知能系のトップの国際会議AAAIで発表させていただいたものなんですけれども、そこで発表させていただいた研究テーマというのをちょっと紹介したいと思います。
モジュラリティというのは現在デファクトだと先程申し上げたんですが、これにも結構弱点がありまして精度面であまりなかなかいいクラスタリングが取れないということが最近わかってきました。そこで、それに代わる手法というのが近年提案されてきていて、その一つがこの構造的類似度に基づく手法というものなんですが、これがなかなか遅いんです。なので、二つ目のトピックとして、構造的類似度に基づく手法の高速化アルゴリズムをご紹介いたします。この話は今、筑波大学CS専攻のM1の学生と一緒にスパコンを使って高速に解いてみようということも新たにやってまして、それもおまけ程度にご紹介できればと思います。
モジュラリティクラスタリングの高速化
早速１番目のトピックなんですけれども、まずグラフからコミュニティを取ろうとかクラスタ構造を取ろうという話をすると、直感的に思い浮かべるアルゴリズムってこれなんじゃないかなと思って持ってきました。Min-cut法とかNormalized-Cut法とか、あとスペクトラルクラスタリングとかと呼ばれるアプローチです。直感的には、グラフがあったときにどこかでカットすることを考えます。そのときに、カットされるエッジの数がなるべく少なくなるようにグループを分けましょうとやるアプローチです。この処理を再帰的に適用していくことで、何もコミュニティが見つかっていない状況からコミュニティ構造を見つけましょうというアルゴリズムなんです。
これは理論的にいろいろな保証されたものであって、かなり使い勝手はいいんですけれども、一方で、現実のグラフに含まれるようなクラスタのサイズの偏りなどを考慮したクラスタというのが取りにくいということが長い間言われてきました。または、計算量自体も結構大きくて、大きなグラフに適用するのは難しいよねということで、2005年ぐらいからModularityと呼ばれる手法が代わりに注目を集めるようになってきました。
このModularityというのは、もともと物理学の分野で発表されたアプローチで、あるクラスタリング結果がどれぐらい良いものなのかを評価するための指標として提案されました。Modularityでは、実際のグラフとランダムグラフの二つのグラフを想定します。そして、あるクラスタリング結果が与えられた際に、実際のグラフとランダムグラフでは同じクラスタの中に存在するエッジの数、にどれぐらい差があるかというのを評価して、その差がなるべく大きくなるようなクラスタリング結果を良い結果とみなしましょうというのがModularityの考え方になります。何でこのランダムなグラフに対して考えるのかというのがポイントになってくるんですけれども、基本的にランダムなグラフというのは、ノード間のエッジがランダムに接続されていますのでコミュニティの構造を持ちにくいということが考えられます。そうしたときに、ランダムグラフにおいてクラスタ内に含まれるエッジ数というのは、たまたま同じクラスタの中にエッジが存在してしまう期待値を計算していることになります。なので、たまたまクラスタに入ってしまうエッジの数に対して、実際のグラフに対するクラスタリング結果はクラスタの中にどれだけ多くのエッジが存在しているかどうかという、その度合を評価しようとしている指標になっているんです。これは、式だけ見ると本当かなという感じがするんですけれども、例を見ると結構直感的に納得いただけると思います。
今、同じグラフなんですけれども、２つのクラスタリング案、A案、B案を用意していて、それぞれのModularityがどのように評価されているかというのをこの例で示しています。まずA案の場合ですと、赤色で示されている３本と１本と１本という形でクラスタのところにエッジを持ってきます。一方で、これは適当につくったグラフですが、ランダムグラフの場合２本、１本、１本という形で、差を取ると１本だけクラスタ内にエッジが多く存在しているという指標になっています。B案でも同じランダムグラフを前提に持っているんですけれども、エッジの本数を数えていくと、B案の場合は（６本－２本）＋（３本－１本）で５本、ランダムグラフに対してクラスタの中に存在エッジが多いですねということで、なかなか人間が直感的に見て妥当性が高そうなクラスタのほうが高い値を持ちやすいという性質があります。
これをあとは最大化するようなコミュニティを見つけるんですけれども、当然、例えばさっきのグラフ構造に対して２つのコミュニティーを探すだけでもこれぐらいの組み合わせ数になりますし、３つのコミュニティを探すだけでもとても計算できない規模になる。
この問題は事前にコミュニティ数もわかってすらいないので、どれぐらいの組み合わせを計算したらいいかというのがわからないんです。なので、このModularityに対するグラフクラスタリングというのも2005年ぐらいに提案されているんですけれども、そこから10年ぐらいかけてたくさんの高速化手法が提案されてきました。最も一番基礎になっている手法というのがGirvan-Newman法と呼ばれる手法で、大体私が調べた範囲ですと１時間あたり１万ノードぐらいの規模を処理するのが限界かなという手法です。計算量が大きくて、大体ノード数をＮにするとＮの3乗ぐらいになっちゃって、とても最近のグラフですと使えないなという計算量になっていますね。
これに対して、これはほぼデファクトとされる手法なんですけれども、2004年さらに提案されたのがNewman法とあとその亜種であるCNM法という手法です。これはもう非常に直感的でわかりやすいんですが、ある２つのノードペアを同じクラスタにしたときにどれぐらいModularityが向上するかというものを、このModularityという式を変形してModularity gainという式を導出してあげて、このModularity gainが最も大きくなるようなノードのペアというのを貪欲法で探索する手法になっています。この手法の発展系であるCNM法ではインデックス構造を使うことでNewman法を少し高速化しているんですが、やっぱりこれも大体１時間当たり数百万ノード規模を処理するのが限界なので、例えばWebグラフのような非常に大きなグラフを対象にするのは難しい手法です。
そのあと2008年に提案されたのがLouvain法という呼ばれる手法です。最近の論文ですと、大体比較手法としてよく出てくるのはこのLouvain法ですね。これは最速かつ最も精度が高い手法ということが知られているんです。グラフのコミュニティ構造は、結局のところ隣接するところとしかくっつかないという暗黙の仮定を置いていて、基本的には隣接ノードの中でModularity最大となるノードをひたすらクラスタにしていくということを繰り返す手法です。例えばイギリス国内の2015年時点におけるWebグラフに対してこのアルゴリズムを適用したとしても、大体３～４時間ぐらいとかで計算できる非常に高速な手法です。
ですが、私の研究としてはもっと大きく１時間で１億ノードとか10億ノード、全世界のウエブページを１時間で計算したいなと、それぐらいの野望がありまして、2013年にIncremental Aggregation法と呼ばれる新しいアルゴリズムを提案しました。詳細はこの後説明するんですが、結果としてLouvain法とほぼ同じぐらいの精度なんですけれども、その計算速度を60倍ぐらい速く処理できるというものを実現することが出来ました。アメリカの2001年時点での全Webページを含んだ「webbase2001」という有名なデータセットがありまして、大体規模が１億ノード10億エッジぐらいなんですが、ノートパソコンとか使って計算しても３分ぐらいで計算が終わってしまうというアルゴリズムになっていて、これは私が知る限りこの領域だと世界最速なんじゃないかと思っています。
どういうことをやっているアルゴリズムなのかといいますと、実はどんなグラフに対しても速くなるというアルゴリズムではなくて、現実のグラフデータとか現実でよくあるようなグラフデータが持っているある性質に着目したアルゴリズムになっています。逆に言うと、その性質がないデータに対しては速くないんです。何に着目しているかというと、グラフのクラスタ性とPower-Law特性という２つの性質を使っています。
クラスタ性について簡単に説明すると、クラスタ性というのはグラフの中で３つのノードが互いに接続し合った３部クリークがたくさん含まれるよという性質です。一般的に世の中にあるソーシャルネットワークとかWebグラフというのはクラスタ性が高いというのが示されていまして、ダンカン・ワッツという人が1999年頃に有名なスモールワールドという本まで出版しています。例えばこれはWebグラフなんですけれども、かなりクラスタ性が高くて三角形を形成している部分が真ん中に密集していることがわかります。この三角形の構造というのをうまく使ってあげることで計算コストを下げようということをやっています。
もう一つの性質Power-Law特性です。これはかなり有名だと思うんですけれども、次数のPower-Law性ということで、世の中のグラフの大半は各ノードが持つエッジの数にかなり偏りがあるという性質があります。例えばこれはアメリカのWebページの次数分布をあらわしたものですが、かなり偏りがあるというのがわかるかと思います。この性質をうまく使ってどういう順番で計算したらクラスタリングを行う際の計算コストを小さくクラスタを求められるかというのを最適化していくということをやっています。
Incremental Aggregation法というのは名前のとおりでして、クラスタリングしていくにつれてどんどん計算が不要そうなエッジとかノードというのをどんどんクラスタに集約していってしまう。最終的に小さいグラフの上でしかクラスタリングをやっていなくて、その集約されたものを展開すると元のクラスタリング結果というのがちゃんとできていますというようなアルゴリズムになっています。
その中で肝となるテクニックというのがいくつかあります。一つが先ほどのクラスタ性に着目した逐次集約というテクニックです。例えば、この２つのノードが同じクラスタと判明したとします。そのときに従来のアルゴリズムですと、この２つのノードをそのまま同じクラスタだよというふうにラベルはつけて次の計算を行う。そうすると何が起こるかというと、以降の計算ではこのクラスタに対して計算しようとした際に、クラスタ内にで三角形を形成している部分に対しては何度も同じModularity gainを計算する必要が出てきます。しかし、この計算結果は常にModularity gainの値をとるため、計算すること自体が無駄なんです。そこで、2つのノードが同じクラスタだと判明した時点でひとつのノードに逐次してあげると、面白いことに集約をするたびにクラスタ性があるところ、つまり三角形を形成しているところってどんどんなくなっていくんですね。結果として、クラスタ性が非常に高いグラフでは、早い段階で三角形が削除されてしまって、全体として無駄な計算を省くことが出来るようになります。これは非常に単純なんですけれども、とても効果があるアプローチでして、このModlarityクラスタリング以外でもグラフ処理系だったら結構このテクニックが使えるのではないかと思っています。
もう一つが先ほど申し上げたPower-Law特性を捉えるという話なんですけれども、これも説明してみると非常に単純な話なんですけれども、実は結構効果がある手法になっています。例えばノードAとノードBというのが同じクラスタになるとしましょう。そのときにノードAとノードBが同じクラスタにするためには、その間にあるModularity gainが大きいということがわからないといけないんですが、この間にあるModularity gainが大きいということをどこから計算して見つけるのが速いかというのを考えたアプローチになります。そうすると自明にですけれども、エッジ数は少ないノードから計算した方が効率がいいですよね。ノードAから計算するとこの青いエッジ数分３回計算した結果ノードBというのがクラスタとして併合するのにいい相手だというのがわかるんですけれども、逆にノードBを選択して２回しか計算しないでAを見つけるほうが効率がいいでしょう。グラフというのは非常に強いエッジの偏りというのを持っていますので、その性質をうまく使ってあげることで、これだけでも非常に単純なんですが計算速度が２倍から３倍ぐらい速くなるという手法になっています。
今回使ったのは、こちらの５つのリアルワールドのデータセットで、一番大きいグラフですと、大体このあたりで１億エッジ、こっちは１億ノード37億エッジと、それぐらいの規模です。最近だとこれよりもっと大きいグラフが出てきちゃっていて、ちょっと私のほうでもどうやって使おうかまだ考え中のところなんですけれども、当時はこれが一番大きなデータセットでした。使ったのは、一般的なLinux serverで当時最速だったLouvain法および一般的に使われているCNM法と比較しています。
こちらが実行時間の比較なんですけれども、一番標準的なwebbaseというデータセットですと、大体１億ノードぐらいなんですけれども、これが大体私の手法だと156秒でクラスタリングできます。これはLouvain法を使うと、10の4乗秒以上なのでそれなりに長い時間かかってしまう。また、dblpって非常に小さいデータセットなんですけれども、3.2万ノードぐらいのグラフなんですが、これだったらこのマックブックでも１秒未満でクラスタリングできます。
あとは、問題は精度のほうで、過去のModularityクラスタリングと比較してどれぐらいのモジュラリティの値があるのかというのをはかったものになっていまして、ちょっとこのCNMはこの４つのデータセットに対しては遅過ぎて適用できなかったのでないんですけれども、BGLLと比較すると基本的にほぼ遜色ないような結果になっているかと思います。
ということで、今回提案したアルゴリズムというのは、基本的にBGLLとほぼ同程度のモジュラリティ値を示すんですが、その速度がこっちに示したような大体最大で60倍ぐらい速いということが出ていにて、最近幸いなことにいろいろな論文で使っていただけるようになってきているというアルゴリズムです。ちょっとまだ普及活動が足りないのですが、これからもっと使われていくんじゃないかと私は信じています。
構造的類似度に基づくクラスタリングの高速化
ここまでがModularityクラスタリングの話なんですけれども、今、ここで実はちょっと私嘘ついたんですよね。精度いいですとはあえて言わなかったんです。モジュラリティ値が同じぐらいになるという話をしたんですけれども、それは何でかということはこれからの話のきっかけになります。
実は、近年モジュラリティに基づく手法にも限界が指摘されてきています。Resolution Limitと呼ばれていて、グラフの規模が大きくなればなるほど、適当にクラスタリングしてもモジュラリティ値がいい値になってしまうという問題が指摘されています。その結果、取れるクラスタの質も下がってしまって、正解がわかっているデータに対して実はその正解の再現性がかなり低いということが最近指摘されてきています。例えば、先ほどの私が持ってきた芸能人のネットワークなんですけれども、ここに男性俳優コミュニティというがあったと思います。実はこれもよくよく深堀りしていくと、この上のほうは映画俳優なんです。逆に下のほうは割とタレントみたいな感じの男性俳優とかが多くて、結構この中も本当はばらばらコミュニティに分かれている。あとは、男性モデルのコミュニティなんですけれども、どう見てもハブとなっていてコミュニティとは区別されるべき存在というのもコミュニティ内に取り込まれてしまっていて、この結果を見てもこのクラスタリングの解像度の限界が存在しそうだということが直感的にはご理解いただけるかと思います。
そこで、こういった問題を解決するためにさまざまな新しい指標ですとかクラスタリングのアルゴリズムというのを提案されているんですが、近年その中でも成功をおさめている手法として、構造的類似度に基づくクラスタリング手法というものが提案されております。特にこれはデータベース分野でかなり使われている手法なんですけれども、それに対して行われている研究というのをちょっと紹介していこうかと思います。
この構造的類似度に基づく手法というのは、通称SACNと言われているアルゴリズムなんですけれども、これはどういったものかといいますと、グラフの中で高い接続密度で接続したノードだけをクラスタとして抽出して、接続密度が低いノードというのは外れ値、ノイズみたいなデータと、あとはハブ、クラスタとクラスタを紐づけるような橋渡しするような特殊なノードとしてクラスタとは別に抽出しましょうというアルゴリズムになります。ここで肝なのは、この接続密度を評価するというのがこのアルゴリズムの肝になっています。接続密度は２つのノードがどれぐらいの強さでどれぐらいの接続をしているかというのを、この論文で提案されている構造的類似度Structural similarityという指標を使って評価したものです。直感的には２つのノードが持つ隣接ノード集合がどれくらいの割合共有しているのかというのをStructural similarityとして計算しています。
このStructural similarityを使って、グラフから二つ役割を持ったノードを抽出します。一つがほかのノードと密に接続するクラスタの核になるノード、coreというもの。もう一つがクラスタのメンバーになれるぐらい周囲と密に接続しているんですけれどもcoreにはなれないborderというノードです。例えば、このノード４というのは、明らかに周りのノードと三角形の構造というのはいっぱいありますので、非常に密に接続しているということでcoreになれそうです。一方で、coreの隣接ノードというのは、もしかしたらよく調べたらcoreかもしれないんですが、まずノード４と密に接続しているという観点からborderとみなせるノードです。SCANでは、このcoreを中心として、coreとborderからなるコード集合をクラスタにしていきます。この処理を、全てのノードに対して繰り返していくことによって密に接続したノード集合だけをクラスタに抽出します。
どれぐらい密に接続したらcoreになれるのかというのを決めるために、この手法はパラメーターを必要とします。それがεとμという二つのパラメーターなんですけれども、それぞれ具体的には何をあらわしているのかといいますと、εというのが「どれぐらいStructural similarityの値の大きさを持ったら密に接続しているとみなしていいか」というのを指定するしきい値です。もう一つのパラメータμは「εを超えるStructural similarityで接続する隣接ノードが何個あったらそのノードがcoreとみなしてよいか」を指定しています。例えば、εを0.7、μを２にしたときに、ノード４についてその隣接ノード全てとStructural similarityを計算すると、エッジに書いてある数字になります。今εが0.7ですので、この赤色で示したエッジの部分がどうやら密だと言えます。この密になっている本数を数えると３本あり、μの数を超えていますのでノード４がcoreであると判定できます。あとはcoreを中心として密に接続した隣接ノードborderを一つのクラスタにまとめるということをします。
こういった形で、互いに密に接続した部分だけをクラスタに取る手法なので、強みとしてモジュラリティと比較してεを適切に設定すれば精度がいいということが知られています。例えば、こういう人工的なグラフデータに対して、ModularityクラスタリングとSCANでそれぞれクラスタリングした結果がこちらに示します。SCANですとこの青色のクラスタとちょっとベージュ色のクラスタとオレンジとこの濃い青色という四つのクラスタと外れ値、ハブみたいなものとあります。これは多分我々が見ても直感にあった結果になっているかなと思います。一方で、モジュラリティを使うとこの間の橋渡ししている部分というのもどちらかのクラスタに含まれてしまうんです。なので、こういった部分で全体的にこのクラスタの解像度の差というのが出てきてしまいます。ただし、先ほどアルゴリズムの流れをご覧になってもわかるかと思うんですけれども、非常に計算時間が大きいんです。全てのエッジに対して構造的類似度を計算しなきゃならない。さらに構造的類似度とは結局、集合と集合の積を計算しなければならなくて、あまり計算量としては軽い処理じゃないんです。なので、結構これを実際のグラフに適用すると、エッジ数の２乗に近いような計算時間とかがかかってしまって、なかなか大きいグラフには適用しづらいという話があります。
2007年に提案された手法なんですけれども、実は高速化のほうというのがなかなか実はやられていませんでした。唯一、私が研究をやったときにやられていたのが、ICDEというデータベースのトップ会議に出ていたものなんですが、Link SCANといわれてるグラフを適当に間引いて近似的にクラスタリングしようというようなアルゴリズムだったんですが、間引いてしまうせいで実際にとてもじゃないけど使えないぐらい精度が悪いという手法になっていました。
そこで私が提案した手法というのが、SCAN++といわれるアルゴリズムです。このアルゴリズムはS高速かつSCANと完全に同じ結果を返せるようにしようというものです。そのためにこの手法では何をやったかといいますと、また出てくるんですけれども、実際の世の中のグラフのクラスタ性、三角形の構造がたくさんあるという構造に着目して、この特徴を使って不要な計算を省くということをしています。この研究を始めた時にクラスタ性が高い場合２ホップ離れたノードは互いに多くのノードを既にシェアしていると言う性質に気づきました。この特性を利用して、グラフの中でも２ホップ離れたノードだけを適当に探索・計算していき、オーバーラップが大きくなるところをクラスタにまとめるという操作をすることで計算コストを下げていくというアプローチをとります。
これがアルゴリズムの概要です。SCAN++ではTwo-phaseクラスタリング手法というものを内部で導入しています。最初のphaseではLocal clusterと呼ばれるあるcoreとその隣接ノードからなるクラスタをとり、次のphaseでLocal clusterの中でもオーバーラップが多いようなところだけを統合して一つのクラスタにするというう非常にシンプルなアルゴリズムです。
結果として、計算量はO(E)になります。クラスタ係数が高くなるほど高速に計算できます。今回証明を省きましたが、必ずこのアルゴリズムはSCANと同じ結果を返すということが保証できます。この証明が非常に大変で、論文を書くまでにすごい時間がかかった思い出があります。
実際にここから実験になりますが、webbaseとかuk-2002などはさきほど使ったデータセットと同じものです。webbaseとかの１億ノードのデータセットに対して１日以内で計算結果を返したのは我々の提案したアルゴリズムだけでした。それ以外でも大体どのデータセットを使っても一番速い既存手法であるSCANに対して大体20倍ぐらい速いというようなアルゴリズムになりました。
あとはこれはちょっとおもしろい結果なんですけれども、人工グラフデータでクラスタ係数を実際に人工的に変化させて大きくさせたときにどのように性能が変わるかという比較をしています。既存手法は当然、全部計算するのは変わらないんですが、提案手法はクラスタ係数が大きくなればなるほどだんだん計算時間というのは小さくなってくるという特性があります。ここまでが大体二つ目のトピックの話です。
クラスタリングの並列化
あと最後は今進行中の話で、アルゴリズムの並列化、このSCANのアルゴリズムの並列化というのを研究室のM1の学生さんと一緒にやっているんですが、ちょっとおまけ程度なのでさらっと簡単に紹介させていただきます。今これは論文投稿中で、まだ昨日結果が来るはずだったんですけど、さきほど来週まで結果通知を待って欲しいみたいなメールが来てしまって、ちょっとそわそわしています。
これまでも結構並列化を使った高速化手法というのが提案されています。例えばGPUを使う手法は最近の流行りもあって、いろいろ提案されているんですけれども、どうしてもGPUの場合はPCI expressを介してグラフのトポロジ構造を転送するコストというのが大きくなってしまうので、まだ私のシングルスレッドのアルゴリズムに勝てていないというような現状になっています。あとは、分散メモリ環境、いろいろなマシン上でデータをばらまいて速く解きましょうという話も盛んに研究されていますが、分散処理をするためにはまずデータを分割する必要がありますので、そのオーバーヘッドがかかって少なからず必要になってしまいます。また、グラフ分割するとどうしてもエッジを切らなきゃいけないんですね。そうすると、その切ってしまったエッジに対する計算結果を何らかの方法で保証したり、同期をとったりするオーバーヘッドも必要になってしまい、分散環境でのグラフ処理はなかなか容易ではないという現状がありました。
そこで私はここ２年ぐらい、共有メモリ環境でその下にたくさんのCPUのコアとかがぶら下がっているような環境だったらある程度並列化しても精度が高く速く計算できるんじゃないかということで、そういった環境を対象としたグラフ分析アルゴリズムの高速化をはじめました。冒頭で申し上げたように私は計算科学研究センターの所属でして、スパコンを比較的利用しやすい環境に居ますので、せっかくなのでこの環境を活かした並列化できないかなということで、2016年昨年度から一緒にM1の学生さんと一緒に研究をしています。今現在利用している環境というのがIntel Xeon Phiというものです。Intel Xeon Phiはここ数年Intelから出ているメニーコアプロセッサなんですけれども、72個程度の物理コアが搭載されていて、各コアは512ビットのSIMD命令が利用できるという非常に面白いプロセッサなんです。これらを全部使い切ると、かなり高い並列計算性能を引き出せるハードウェアなんです。
ただし難しいのが、今まで我々が使っていたXeonのCPUと比べるとかなり一個一個のコア自体の性能は低いんです。これがXeonの我々が使っていたCPUの大体平均的なクロック数なんですけど、これは3.5GHzなんですけれども、Xeon PhiのKnights landingだと1.4GHzと３分の１程度に下がってしまいます。実際に実行すると３分の１では収まらないぐらいの性能差が出てきてしまいます。あとは、グラフ分析ならではの難しさになりますが、グラフというのは構造が極端に偏っていますので、ロードバランシングが難しいんです。いろいろなスレッドに対して均等な量のタスクを割当てられれば並列処理の効率があがりますが、それがなかなか難しい。
そこで、この問題を解決したアルゴリズムとしてSCAN-XPというのを最近、学生さんと一緒につくりまた。詳細は実装の話しが中心になってしまって細かいので割愛しますが、データ構造の工夫と、SCANの計算を徹底的にCPUに最適化するということをやっています。結果としてwebbase2001ですと、私のアルゴリズムですと大体１時間ちょっとぐらいかかっていた計算なんですけれども、M1の学生さんが作ってくれたSCAN-XPだと36秒ぐらいで計算できてしまうんです！大体どのデータセットを持ってきても100倍以上高速でした。これはまだ世界で誰もこの性能を出せてないくらいすごい結果なのですが、学生さんは納得がいかないようで引き続き高速化を突き詰める方向で研究を進めてもらっています（笑）
まとめ
今日お話する内容は以上になります。まとめますと、グラフクラスタリングを題材に高速化のアルゴリズムを研究していまして、今回はその一部をご紹介させていただきました。私のアルゴリズムは、実際のグラフデータが持っている特性をうまくアルゴリズムに組み込むということをやっているんですけれども、多分皆さんだったらもうちょっと数学を使ってすぱっと美しく解けるという方法をご存じなんじゃないかなと思ったので、もし興味がありましたら今後はそういったところでお知恵を拝借して、一緒に議論できるとうれしいなと思います。
あとは、私が今後興味があるのは、Real-world propertyというのをどうやってモデル化して、それをアルゴリズムに組み込むかということですね。今は単純なクラスタ性とPower-Lawの次数特性やクラスタ性に限られているんですが、もうちょっと何かあるんじゃないかな。Real-world propertyとしてどんなものを捉えたらいいのかというのはちょっと興味があるところです。
あとは、いろいろ速いアルゴリズムを使って、いろいろな人に使われつつあるので、もうちょっと広く普及するように、例えばライブラリとして実装を公開するとか、そういったことがちょっと興味があるというのと、あとは実際にグラフを使って世の中の役に立つことをやりたいなというので、いろいろなアプリケーション分野での応用というのを少し興味を持っていますということで以上になります。ありがとうございました。
質疑
二村 どうもありがとうございました。では、早速、質問タイムでお願いします。
Ｑ、私の研究室の隣にクラスタリングの専門の先生がいて、その先生にいろいろ言われることが多いんですけれども、彼がよく言うことなんですが、よくクラスタリングするときに単にクラスタリングするだけではだめなんだというふうに彼はおっしゃっていて、何が言いたいかというと、ある意味クラスタリングというのは何かの最適化関数があって、その最適化になっているということをちゃんと保証できるクラスタリングが美しいとまでは言わないですが、おっしゃっていないので言わないですけど、何かそういった信念みたいなものがあるそうなんです。今回、ご紹介していただいたIncremental Aggregationのアルゴリズムで逐次的にひとまとめにしてまた次といくじゃないですか。そうすると、このような何かの最適化というような観点は、ここは入ってくるべきなんですか。
塩川 結論から言うと、最適化はされていないと思います。それなりに妥当な局所解にしているということです。モジュラリティの最適化自体がそもそもNP困難なので、だったらある程度妥当な解が出ている範囲でのほうが速いのではないか。
Ｑ、最初から問題のアプローチとして困難な悩みではなく、できるところをやるという、そして速くやろうということになるわけですね。
塩川 はい。一方で二つ目に紹介したSCANのほうは、パラメーターとグラフが与えられたら正解のクラスタというのは一意に決まるアルゴリズムなので、そこについてはちゃんとパラメーターとグラフに対しては最適性を保証しますということになっています。
Ｑ、やはり最適性を保証しようとすると、ちょっと時間がかかるということですよね。
塩川 そうですね。
Ｑ、わかりました。あともう一つ、クラスタリング結果に意味づけをするじゃないですか、このクラスタリングの一つに。ちょっとよくわかっていないんですけれども、素人過ぎて、クラスタリング結果にどのように意味づけをすれば妥当だと言えるんですか。
塩川 私の研究の範囲だと、クラスタリング結果がいいか悪いかというのを評価するためにはGround truth、正解がわかっているデータとかを使ってやっています。そうじゃなくて実際の現場でいいかどうかというのを判定するには結構やはりまだ泥臭いことをやっていて、目で見ていいかどうかとやったりとか、ユーザーテストを通していいかどうかとやったりとかというのもあります。あとはある程度もうちょっとテクニックがわかっている人がやるとラベルプロパゲーションといって一部人間が意味をつけて、そこから確率的にどの人がどれぐらいの意味を持っているか、というのを計算する方法があるんですけれども、それとの比較をして妥当かどうかというのをやったりします。
Ｑ、そういう指標があるんだ。
塩川 多分ちゃんとはかろうと思うと、多分最終的には人間がという話になってくるんですね。
Ｑ、僕の隣の先生のところのゼミも出たりするんですけどちょっと、そうすると意味づけが一番難しくて、実データをやったときに一体どんなふうに計算するのがいいのかというのがすごく難しいですよね。
Ｑ、２個目のほうの構造的類似度のアルゴリズムで、グラフのクラスタ性を使って類似度を必要ないところは計算しないようにしましょうというセンスですよね。
塩川 はい、そうです。
Ｑ、全部計算が終わっていれば、あとしきい値以上だけをクラスタリングをやりましょう、それに必要ないところはやらないでいいというお話だと思うんですけれども、そのときにもう一個のほうの性質というのは使っていないんですか。
塩川 Power-Lawですか。あっちは使っていないんです。
Ｑ、Power-Lawを使うと、最初の項と同じで、エラーの少ないやつから順番にやっていったほうがいいような気がするんですけれども。
塩川 そうですね。実はそれはあって、やったんですけれども、ちょっとこの問題に対しては高速化のインパクトが小さくて、大体速くなっても1.2倍とかだったんです。
Ｑ、それは不満ですか（笑）
塩川 ちょっと、私は足りないかなと思って（笑）
Ｑ、今のクラスタ性を使ってさらにそっちも使ってということですか。一応速くはなっているんですか。
塩川 インパクトは小さいですが、一応速くはなりますね。
Ｑ、PageRankの高速化を比較している人たちは1.2倍で十分じゃないですか？
塩川 ページランク系のアルゴリズムもいろいろやってるんですが、あっちの高速化は大体よくて５倍から８倍とかです、10いかないぐらいです。
Ｑ、感覚が違い過ぎて（笑）
あと、解析の話に近いかもしれないんですけれども、最後のクラスタリングの精度の評価というのは、モジュラリティはよくないということじゃないですか。それの代わりに何を使って評価するんですか。
塩川 結局、今クラスタリング界隈は何を使っているかというと、ある程度正解がわかっているデータに対してその正解のクラスタをどれぐらい復元したかというものをやっています。どういう手法を使っているかというと、大体ARIやMNIを使っていることが多いですね。どっちも感覚的には正解に対してどれぐらい同じクラスタリング結果を復元できたかというのは評価している指標になります。それを使うのが今は標準になっています。
Ｑ、ほかのやつに関してはSCANと必要のないやつを省いただけであって、性格的に全く同じ答えを返す。
塩川 そこは結構頑張って証明してあります。
Ｑ、ただ、使わないやつ、いらない枝の数字を計算しないだけだから。
塩川 いや、ちょっと難しいのが、ここの統合の部分が結局肝なんですよね。ここはラフにこの条件を満たしていれば統合していいよということを言っているんですけれども、実はこの破線になっているエッジは計算していなくて、ここを計算したらこの条件を満たすというような、この橋渡ししているノードが当然存在するわけで、そういったものというのは、そのやり方というの見落としてしまうんですよね。直感的には見落としてしまうように感じると思う。それが何で見落としがないのかというのをぐちぐちと証明したというのがこの論文の結構ハイライトになっています。
Ｑ、SCAN++を考えるとき、思いついたときって、その思いついた瞬間にSCANと同じ結果が出るというのはわかっていましたか。
塩川 何となくはそうじゃないかなという感覚はありました。あまり若い人には参考にしないでもらいたいんですけど、私の研究の仕方っていつも変で、普段起きている間はなかなか解けないんですよ。頭がパンクするくらい考え続けて夜寝ると夢の中で何となくこのやり方でいけるんじゃないかというのを思いついて翌朝試すとうまくいくみたいなパターンが多くて。夢の中で多分これはいけるはずだみたいな思いがあって（笑）
Ｑ、早稲田大学の石川といいます。化学をやっていまして、化学反応ってそのグラフ的に見るとすごくわかりやすくなるというふうに考えている人もはやりではないんですけれども、個人的には思っています。なのでちょっと簡単なところ、基本的な質問をしたいんですけれども、クラスタリングをする人ってその後に何をすると思ってクラスタリングするんですか。
塩川 結構私の論文は生物学系のほうで引用されるんですけれども、そっちのほうで何をやっているかといいますと、酵素同士の反応の関係をやっぱりグラフで表現してクラスタリングするということをやっています。酵素同士の反応関係から作ったグラフにクラスタリングを行うと、特定の機能を持つようなクラスタが取れるらしく、関係性を見ることでと生物や化学の研究に応用しているようです。
Ｑ、例えばこのアルゴリズムでパラメーターを連続的か離散化で変えたやつもクラスタリング結果全部同時に欲しいみたいなことがあったとして、うまくいけたりしますか。
塩川 実はいけます。今回紹介しなかったんですけれども、ちょっとやっていて。
Ｑ、それはおもしろいですね。
塩川 はい、これはちょっとおもしろいなと思って私も今構想等を考えているところです。
Ｑ、アルゴリズムの性能の評価として、今は少数のデータセットをとってきてそれを個別の性能を、計算時間の精度を見ていますけれども、ある程度まとまったデータセットみたいなので、そういうのを統合した評価指標、いわゆるパフォーマンプロファイリングみたいなものは使ったりしないんですか。
塩川 我々の分野だとあまりないですね。大体、別にこれを使いなさいというのは決まっているわけではないんですが、暗黙のうちにみんなが使っているデータセット、標準になっているというかベンチマークがあって、大体ここに上がっているものがそうなんです。
Ｑ、線形計画問題とかだと結構何百という問題があって、それをみんな使って新しい手法をつくったり、手法を使って評価して、それを統合的にまとめて早く反証とかをして、それをまるっと評価する。
塩川 多分、歴史が長いので結構ベンチマークがしっかりしていますよね。結構データベースの学会に行くと、フェイスブックの人とかがこういうグラフデータ処理のベンチマークをつくろうという話を結構よくしているんですけれども、まだなかなか普及してデファクトになっているものはないですね。なので、どうしてもみんなこの辺はすぐに手に入ってしまうので、みんなこればっかり使っているということです。
Ｑ、重みつきのクラスタリングってどういう感じなんですか。ここのエッジのウエイトが小さいから。なければその周囲を見たりすればそれは取れちゃうということですか。
塩川 そうですね。そういう感じですね。その接続の強さをあらわすような重みがついているということです。例えばモジュラリティの場合だったら、重みがついているところを優先的にクラスタリングするような動きをしますし、SCANの場合は、多分重みがついているところの類似度だけちょっと大きく計算したりとか、それが結果としていい方に寄与するかどうかというのはちょっとわからないんですけれども、そういうふうな重みつきの対応の仕方はやられています。
司会 いろいろまだ何かあるみたいですけれども、質問タイムはこのぐらいということで、どうもありがとうございました。
プロフィール
2015 年3 月筑波大学 大学院システム情報工学研究科 博士後期課程 コンピュータサイエンス専攻 修了。博士（工学）。日本電信電話株式会社にて研究員として勤務の後、現在、筑波大学計算科学研究センター助教。大規模データ処理、データマイニングならびにデータ工学を中心とした研究に従事。ゲームが好き。日本データベース学会、情報処理学会、ACM、AAAI各会員。ホームページ：http://www.kde.cs.tsukuba.ac.jp/~shion/