SLaQ：大規模データの形状を理解する(2/2)

１．SLaQ：大規模データの形状を理解する(2/2)まとめ

・グラフのスペクトラムは、グラフの接続パターンなどの属性を符号化する強力な表現手法
・DDGKは巨大なグラフを扱う事ができないがスペクトラムで規模拡大がしやすい属性を取得可能
・SLaQを使用するとWikipediaのような巨大データのグラフ構造の変化から重大な異常を検知可能

２．SLaQとは？

以下、ai.googleblog.comより「Understanding the Shape of Large-Scale Data」の意訳です。元記事の投稿は2020年5月5日、Anton TsitsulinさんとBryan Perozziさんによる投稿です。

アイキャッチ画像のクレジットはPhoto by Vivaan Trivedii on Unsplash

スペクトラム記述子による高速で正確な近似
グラフのスペクトラム(spectrum)は、グラフノード間の接続パターンやクラスタリング情報など、そのグラフの属性を符号化する強力な表現手法です。

訳注：spectrumは英語の綴りは同じであっても日本語で「スペクトラム」と表記される場合と「スペクトル」と表記される場合があります。結論を言いますと、専門分野に深く立ち入るのでなければ両者とも「複雑な情報や信号を成分ごとに分解し、並べたもの」の理解で大丈夫です。

・スペクトル
フランス語(Spectre)が由来で、主に光の成分分解を示す際にスペクトルで表記されているケースが多いです。学生時代にプリズムで太陽光を７つの光に分解する実験をした際に聞いた事のある言葉と思います。

・スペクトラム
英語由来で、主に電気、通信、周波数や連続体の成分分解を示す際にスペクトラムで表記されているケースが多いです。ただし、「周波数スペクトル」や「スペクトル解析」という言葉もありますが、「周波数スペクトラム」や「スペクトラム解析」の読み方はあまり聞かないのでどちらかと言うとマイナーな読み方なのかなと思います。

更にややこしいのですが、スペクトラムの時間変化を表わすスペクトログラム(Spectrogram)と言う単語もあって、これは本ブログでもクジラの唄声を分類する機械学習の事例で紹介した事がありますが、とにかく光や音を扱うためだけのテクニックではなくて「複雑な情報や信号を成分ごとに分解し、並べたもの」であり、今回の主題のグラフなどもスペクトラムで扱う事ができますよって事です。

スペクトラムは、ドラムの音響、3D物体の形状、グラフ、一般的な高次元データなど、様々な物体の属性に関する豊富な情報を伝えることが示されています。

スペクトラムグラフ記述子を使ったアプリケーションには、AutoMLシステム、動的グラフによる異常検出システム、化学分子の特性評価などがあります。

現在、DDGKなどの学習ベースのシステムは、大きなグラフや大きなグラフの集まりを扱うように拡張できません。その代わりに、スペクトラム情報を使用すると学習用ベースのシステムではなくとも、より望ましい規模拡大がしやすい属性を取得できます。

例えば、SLaQを使用して、Wikipediaのグラフ構造の変化から異常を検知できます。SLaQを使用すると、ページグラフに発生した重大な変更を、大量のページ名の変更などの些細な変更と区別できます。私達の実験では、概算で近似精度が2桁向上しています。

左：空手クラブの人間関係を示す有名なグラフ。2つの武術クラブのメンバー同士の社会的関係を表しています。右：元のグラフに対して計算されたスペクトラム記述子(NetLSD、VNGE、およびEstrada Index)は青、エッジが削除されたバージョンは赤で表現されています。

結論
教師なしでグラフの特徴表現を学習する事は重要な問題であり、今回取り上げる方法は、この領域での刺激的な一歩であると信じています。具体的には、SLaQを使用すると、大規模なデータセットの主要な特徴表現を計算できます。DDGKには、データセット間の並びを自動的に学習するメカニズムが導入されています。

私たちの貢献が大規模なデータセットの分析を前進させ、推薦システムで使用されるような時間と共に変化するグラフデータセットの変更部を理解するために役立つことを願っています。

謝辞
これらの作品に貢献してくれたMarina Munkhoeva, Rami Al-Rfou, 及び Dustin Zelle に感謝します。グラフマイニングチーム(アルゴリズムと最適化グループの一部)の詳細については、research.googleのWebページをご覧ください。