Frovedisによるグラフ解析(その1)

no.0162021.11.26

グラフ解析(グラフ理論)について

 ソーシャルネットで表現される人と人とのつながりや物流ネットワーク、情報ネットワークなど、様々な種類のネットワークに対して関係性を解析することで何らかの予測や分類を行う、グラフ解析という機械学習の一分野があります。ここではグラフ理論と呼ばれるノードとエッジの集合で形作られるグラフについての数学的理論をベースにしてネットワークについて様々な解析が行われます。なお、グラフ理論、グラフの種類、グラフアルゴリズムについてはインターネット上に数多くある講義資料やnew windowwikipediaの解説を参照ください。

 Networks: An Introduction Mark Newman(new window目次の他にnew window本文へのアクセスも可能なようです)から4つに分類されるネットワークについて引用します。

4つに分類されるネットワーク

 Technological networksには広域電力送配電ネットワーク、鉄道・バスや高速道路をはじめとする交通インフラネットワーク、物量配送ネットワークなどが含まれます。Googleマップやカーナビゲーションでは道路ネットワークをベースにグラフ機械学習を使用して経路探索や渋滞予測を行っているようです。

 Social networksはSNSに代表される人と人のつながりの他、企業間あるいは組織間の取引、さらには送金関係といった種類のネットワークが含まれています。

 インターネットやE-mailの連鎖、そして学術論文の引用関係などが3番目のNetworks of informationに分類されます。

 Biological networksとは生物学的ネットワークという意味ですが、創薬分野でのグラフ解析応用が始まっているようです。例えば、正則化されたスパース生成ネットワークモデルを介したタンパク質 - タンパク質相互作用データに基づく発見(※1)のように、たんぱく質間の相互作用ネットワークをモデル化してタンパク質複合体を探索しています。

 以上、幅広い領域での活用が見込まれるグラフ解析あるいはグラフ機械学習ですが、画像解析やチャットボットなどで利用される技術と比較して存在感が薄い印象を受けることは否めません。その一因として、グラフ機械学習を使用して何ができるのか漠然としており、自動運転やコールセンターサポートなど具体的なサービスに結びつけることが容易でないことがあるのかもしれません。しかし、先に上げた経路検索の例だけでなく、物流配送最適化やソーシャルネットワークを利用したマーケティングから、アンチ・マネーロンダリングや不正取引検知など、数多くの実社会での利用が始まっています。

NetworkXとFrovedisによるグラフ解析

 Pythonを使用してグラフデータ作成、グラフ表示や構造解析など行うためのライブラリとしてNetworkXが知られています。グラフオブジェクトをNetworkXのAPIに渡すことで、様々なグラフアルゴリズムを簡単に利用することができます。NetworkXには最短路問題、リンク分析、グラフ探索、グラフの中心性をはじめとして様々な種類のグラフアルゴリズムが用意されており、グラフデータのタイプや構造に応じた解析方法が提供されています。

 Frovedisではこれらグラフアルゴリズムの中から以下の4種類について、NetworkXとのインターフェース互換性を保ちながら処理高速化を行っています。

Frovedisがサポートするグラフアルゴリズム
Frovedisがサポートするグラフアルゴリズム

 グラフデータはノードとエッジの関係性を隣接行列と呼ばれる行列形式で保存しますが、多くのノード間はエッジで結合されていないため、隣接行列の要素は多数の0が占めることになります。このような場合、隣接行列は疎行列で表現できます。この特性を生かし、Frovedisでは処理を高速化しています。

 NetworkX互換のFrovedisグラフアルゴリズムについて今回と次回の2回に分けて説明していきます。グラフ解析第1回はグラフ解析アルゴリズムの使用例を見ていきます。そして次回はNetworkXとFrovedisアルゴリズムの処理速度を比較する予定です。

サンプルコードの処理内容

 グラフアルゴリズムを使用した解析を行うために、次に示す手順でサンプルデータを用意しました。

サンプルデータ

 例えばlockdownという単語と双方向で近距離である単語の集まりは次の通りです。

['pandemic', 'virus', 'restriction', 'social-distancing', 'government-imposed', 'strictest', 'localise', 'lock-down', 'socialise', 'stay-home', 'reintroduction', 'confinement', 're-imposing', 'containment', 're-introduce', 'curfew', 'anti-virus', 'self-isolation', 'draconian', 'festivity', 'three-stage', 'quarantine', 'anti-coronavirus', 'shelter-in-place', 'resurgence', 'state-wide', 're-imposed', 'outbreak', 'country-wide', 'worst-affected', 're-impose', 'shut-downs', 'non-essential', 'nightclub', 'virus-led', 'strict', 'caseloads', 'curb', 'manila', 'pandemic-linked', 'contain', 'virulent', 'tourism-dependent', 'shutdown', 'reimpose', 'stay-at-home', 're-opened', 'relaxation', 'nonessential', 're-opens', 'reopen', 'hibernation', 'reintroduce', 'milder', 'locked-down', 'easter', 're-imposition', 'gradually', 'traveller', 'resurge', 'paralyze', 'reimposition', 'localize', 'normality', 'epicentre', 'relax', 'hotspot', 'unevenly', 'closure', 'travel', 'month-long', 'jacinda ardern', 'indoors', 'isolation', 'holidaymaker', 'wale']

 エッジ集合を作成するにあたり、('pandemic': 1, 'virus': 2, 'restriction': 3…)のように各単語に独立した番号を割り当てることで、例えばE={('pandemic', ' virus '),(' pandemic ', ' restriction ')}はE={(1,2),(1,3)}へと変換しました。

 全単語でエッジ集合を作成した後に、まずadd_edges_fromでNetworkX のGraphに取り込みます。さらにこれを使ってFrovedisのGraphに変換します。

 以降、NetworkXとFrovedis双方のGraphアルゴリズムを使用してサンプルデータである無方向グラフデータの特徴を調べていきます。


graph_test

 はじめに、あるノードに対して隣接して接続されるノードの数を返すNetworkXのneighborsアルゴリズムを使い、’gdp'とエッジを経て隣接するノード(単語)を見ています。bea: U.S. Bureau of Economic Analysis, cbo: Congressional Budget Officeを筆頭に多くは経済(国内総生産)に関連する単語が表示されています。

 続いてFrovedisのアルゴリズムを使った処理に移ります。まず、connected_componentsで1つ以上のエッジを経てつながっているノード数を表示しています。サンプルデータが22の独立したグループで構成され、一つの大きなグループ(17977ノード)と、その他2ないし3つのノードで構成される小グループであることが分かります。このことから、大多数のノードがなんらかのパスを経てお互いに接続されていることが分かります。

 次のdescendants_at_distanceは指定する距離内でエッジにより結ばれるノードのリストを返します。サンプルコードではdistanceを2としていますが、各ノードの隣接ノードからさらに隣接するノードをリストアップすることになります。2つまでのエッジで結ばれる範囲内に存在するノード数は500以下が多く、その先は次第に減少傾向を示しています。3000を超えるノード同士が接続されているものも少数ながら存在し、そこでは密なクラスターが形成されていることがうかがえます。

 single_source_shortest_pathは指定したノードからスタートして最短距離で辿り着ける全てのノードとルートを返すものです。この例(ノード’gdp'を起点)では自身を含めて17977のノードにつながっていることを示しています。このことからノード’gdp’がconnected_componentsで示された一つの大きなグループ内に含まれていることを示しています。

 pagerankではより多数のノードから接続されているノードを見つけ出しています。pagerankが返す係数が一定以上であるノードを表示しました。個人名や株銘柄を示すティッカーコード、15-dayやshort-durationのような期間を示すものなど、それら大半はあまり大きな意味を持たない単語がリストアップされています。他の多数ノードからリンクされているこうした単語の扱い(例えば、単語リストから削除)によって、グラフ特性に変化がみられることが考えられます。また、LDAなど他の処理の結果にも影響を与える可能性があります。

 最後にNetworkXのdegree_centralityを使って多くのノードと隣接しているノードの確認(次数中心性)と、ネットワークを視覚化します。サンプルデータでは多数のノードを結ぶハブ的なノードが存在する一歩で、疎な結合状態のノードが多数存在していることを示しています。これは先に示したdescendants_at_distanceで得られた結果を裏付けるものと言えます。

 NetworkXとより高速なFrovedisのGraphアルゴリズムを使い分けながら、ネットワークの特徴を調べる一例を紹介しました。今回は無向グラフであるサンプルデータを使用しましたが、単語間距離の重みへの追加や、有向グラフ化するなど、より複雑さを加えることでさらにネットワークが有する特性を深く調べることができる可能性があります。

 巨大なネットワークを有するグラフデータを扱う場合、Graphアルゴリズムの計算が長時間化することが考えられます。Frovedisの高速化アルゴリズムを使うことで、より短時間なグラフネットワーク解析が可能となります。

 次回は、先に述べた通り、FrovedisとNetworkXのアルゴリズム実行時間比較をご説明します。

関連リンク