IBM Research

ネットワーク構造解析- 機械学習によるアプローチ -鹿島 久嗣
IBM東京基礎研究所
Tokyo Research Laboratory© Copyright IBM Corporation 2006

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

ネットワーク構造データの解析において、機械学習の立場からどのような考え方に基づいたアプローチが行われているかを紹介します
ここで扱うネットワーク構造データの定義
なぜ従来の機械学習がネットワーク構造に適用しにくいか
ネットワーク構造の上でのさまざまな学習タスク
ノードに関するタスク： とくにノード分類
構造に関するタスク： とくにリンク予測問題へのアプローチに共通の考え方
具体的な手法統一的なモデルIBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

ネットワーク構造データとは、データ間の関係がグラフ構造によって表されたものです
通常の機械学習において、データが「特徴空間」のベクトル（＝点）として表現されるのに対し、ネットワーク構造では「データ間の関係」がグラフ構造で表現されます
ノードは、個々のデータを表す
リンクは、データ間の関係を表す

個々のデータ

個々のデータ年齢・

従来： ベクトル型のデータ
顧客番号

顧客氏名

年齢

性別住所

…

0001

○○

４０代

男性

東京都

…

0002

××

３０代

女性

大阪府

…

４０

ベクトル（＝点）として表現

３０
男

・女

性別

No
Yes

住所=東京

もともとテーブル形式なので、特徴空間が比較的簡単に構成できる

ネットワーク構造データ
特徴空間

特徴空間が不明

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

通常の機械学習手法では、ネットワーク構造を自明に扱うことはできなかったため、研究が盛んに行われています
ネットワーク構造の場合、個々のデータに対してどのような特徴空間を定義するかが自明ではない
従って、通常の機械学習手法では、ネットワーク構造を自明に扱うことはできない
通常の機械学習手法は、データ＝ベクトルを想定しているため?
?
自明でない?
?

ネットワーク構造データ?

特徴空間が不明

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

世の中の色々なデータがネットワーク構造をもっています
ノードがネットワークの構成要素を、リンクがそれらの間の関係を表します
ネットワーク構造ノード

リンク

WWW

ページ

ハイパーリンクSNS

人コミュニティ友人関係
所属生体ネットワーク遺伝子
タンパク質制御関係
相互作用関係

リンクは静的な関係だけでなく、メールのやりとり協力などの動的な関係も表すことがありますIBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

機械学習／データマイニングの分野では、ネットワーク構造の解析は「リンク マイニング」という名前で研究が行われています
Getoor らによる、リンク マイニングの基本的なタスク
ノードに関するタスク• ノードのランキング• ノードの分類• ノードのクラスタリング
ネットワーク構造に関するタスク• リンク予測• 構造パターン発見

Getoor & Riehl.: Link Mining: A Survey, KDD Exploration, vol. 7, 2005

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

今回は、とくに「ノードの分類予測」と「リンク予測」についてのお話ですGetoor らによる、リンクマイニングの基本的なタスク
ノードに関するタスク• ノードのランキング• ノードの分類• ノードのクラスタリング
ネットワーク構造に関するタスク• リンク予測• 構造パターン発見

どちらも「半教師付き分類学習」のような問題として捉えられますIBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

ノードに関する予測タスク： ノードの分類問題

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

教師付きノード分類タスクの定義：
グラフ上のいくつかのノードのクラスラベルをもとに、残りのノードのクラスラベルを当てる
やりたいこと： グラフ構造が与えられ、その上で+1ラベルつきのノードラベルなしのノードが与えられたときラベルなしのノード-1+1のラベル（「＋１」か「−１」）を当てたい+1-1

現実の問題例としては、タンパク質の相互作用ネットワークにおける、各タンパク質の機能予測
WWWの各HTMLページのトピック予測

半教師つきの分類問題、あるいは、トランスダクションの問題として捉えることができる

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

教師付きノード分類タスクでは、特徴空間を構成するのではなく、直接的に構造情報を利用して問題を解く方法を用います
1つ1つのノードを特徴空間の点として表現できれば従来の機械学習アルゴリズムが適用できるが、特徴空間の構成は自明ではないネットワーク構造を「世界の構造の表現」と受け入れ、直接的に構造情報を利用する方法を考える?

X?

自明でないネットワーク構造データ?

特徴空間を使わず直接解く?
?

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

教師付きノード分類の各手法に共通する考え方は「隣同士は似ている」 です
グラフ構造が、データ空間の構造を表しているとすると「隣同士のノードのクラスラベルは似ている」と考えるのは自然
周りを「＋１」で囲まれてるノードは、やっぱり「＋１」だろう・・・

さらに、「伝播」を考えることで、隣よりも遠くに「似てる」が伝わる
AさんとBさんが似ている
BさんとCさんが似ている→ AさんとCさんがそこそこ似ているIBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

具体的な解法はだいたい、「直接解く」か「グラフの上での類似度を定義して解く」のどちらかです1. 直接解く「隣同士のクラスラベルは似ている」を式で書いて、最適化問題を解くことで未知ラベルを当てる

2. グラフの上での類似度を定義して学習アルゴリズムに渡す「類似度の伝播」に従って、2つのノードの類似度が定義できれば、それをカーネル法などの「類似度ベース学習器」に放り込めばOKIBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

解法 １） 「直接解く」方法： ティコノフ正則化によって「隣同士のクラスラベルは似てる」を最適化問題として定式化し、解きますi

予測が満たすべき２つの条件を式で書いてみる• ノード i のラベル予測を sign fi とする （f : fi を並べたベクトル）• ノード i のラベルを yi とする （y： yi を並べたベクトル）
条件 １）隣同士のクラスラベルは似ている• F1 =i,j （ノード i のラベル予測 − ノード j のラベル予測）

真のラベル
予測
2 を最小化

jyj
fj

yifi

キモはここ

Lはグラフラプラシアン
条件 ２）ラベルつきのノードに対する予測が当たる• F2 =2
i:ラベル付きノード （ノード i のラベル予測 − ノード i のラベル） を最小化

F1とF2の線形結合を目的関数として最小化することで予測が求まる
F1 + C F2 を最小化する （Cは定数）
凸で制約ナシ
この場合、closed form の解が求まる
Belkin et al.: Regularization and Semi-supervised Learning on Large Graphs, COLT 2004

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

参考： グラフラプラシアンLは、グラフの構造を行列で表現したものです
ノードの次数をもつ対角行列から、隣接行列を引いたもの
対角成分は、ノードの次数を表す
対角以外の成分は、グラフのリンク情報を表す（リンクがあるときに-1）対称行列i 番目の対角成分はノードi の次数

d1...

L=di

これをつかって-1...

00dNと書ける

ノードiとノードjの間にリンクがあると(i,j) 番目の要素が-1

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

解法 ２） 「グラフの上での類似度を定義して解く」方法： 拡散カーネルによって隣よりも離れたノード間の類似度を求め → 類似度ベースの学習機に渡します
類似度ベースの機械学習法（＝SVMなどのカーネル法など）に渡すために、グラフの上での2ノード間の類似度を定義する方向で考える「隣同士の類似度を１、そうでないものの類似度を０」では、心許ない→ 「隣の隣」、「隣の隣の隣」、「隣の隣の隣の隣」、… も考えよう
そこで、拡散カーネル

Lはグラフ ラプラシアン(i,j) 要素 kij は、ノードi と ノードj とのカーネル（＝類似度）
t は拡散の時間を表すパラメータ• 大きいほど、長い時間「類似度」が拡散することになるであるから、 「隣」、 「隣の隣」、「隣の隣の隣」、「隣の隣の隣の隣」、…を重みを小さくしながら足しこんでいっているイメージ
Kondor and Lafferty: Diffusion Kernels on Graphs and Other Discrete Structures, ICML 2002

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

拡散カーネルの解釈： 類似度がリンクを介して流れると考えます
拡散カーネルの定義(i,j) 要素 kij は、ノードi と ノードj とのカーネル（＝類似度）

拡散カーネルは以下の微分方程式の解になっている→ 類似度の差分がリンクを通じて流れ込んでくる感じと j は似ている

差分が流れ込む

ij

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

現実的な問題設定では、構造の情報だけでなく、個々のノードの情報も利用できます
ここまでは、ネットワーク構造情報のみを用いていたが、本当はノードの持つ情報も使える
タンパク質ネットワークの場合、個々のタンパク質はそれぞれ配列情報などの情報を持っているSNSの場合、個々の人はそれぞれの個人情報を持っているノード情報は、ベクトル表現可能であるから、通常の機械学習手法で扱える構造情報を用いた「隣は似てる」という考え方に基づく学習と、ノード情報に基づく従来の学習を組み合わせたい＋「隣は似ている」
ティコノフ正則化＋「類似度を定義する」
拡散カーネル

個々のノード情報

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

組み合わせ １） 個々のノード自身の情報 ＋ 「隣は似ている」ティコノフ正則化：
多様体正則化（manifold regularization）によって「隣同士の〜」制約を入れます
ノード情報に基づく予測器のパラメータを「隣同士の予測が近くなるような制約」を入れて学習する
ノード情報に基づく予測器をとする
w はノード情報に対するパラメータx はノード情報

通常は、正しいラベル y(i) をと予測してしまう誤りの損失の和を最小化するようにパラメータを決定する

ここに「隣同士〜」の制約をいれると…
グラフラプラシアンをつかった正則化項を入れる

Belkin et al.: On Manifold Regularization, AISTATS 2005

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

組み合わせ ２） 個々のノード自身の情報 ＋ 「類似度を定義する」拡散カーネル：
カーネルを組み合わせることによって簡単に実現できます
拡散カーネルによって、ネットワーク構造から、2つのノード i と j の間のカーネル関数
KD (i, j ) を導くことができた
一方、ノード自身の情報から、ノード i と j の間のカーネル関数 KN (i,j) を定義する
従って、2つを組み合わせて、両方の情報をもったカーネル関数を作ることができる「カーネル関数の線形和はカーネル関数」なのでKNEW (i,j) =KD (i,j) +KN (i,j)
によってカーネル関数を合成できる（ とは定数）

ちなみに「最良の」係数を求める問題は半正定値計画（SDP）として記述できる

Bach et al.: Multiple Kernel Learning, Conic Duality, and the SMO Algorithm, ICML 2004
Lanckriet et al.: Kernel-Based Data Fusion and Its Application to Protein Function Prediction in Yeast, PSB 2004

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

まとめ： ノードの分類問題では「隣同士は似ている」というネットワーク構造上の制約をうまく使います
ネットワーク構造上のノード分類問題に対する２つの異なったアプローチを紹介しました「直接解く」 ティコノフ正則化「ノードの類似度を定義する」 拡散カーネル

これらを従来のノード情報のみを扱う手法と組み合わせる方法を紹介しました
多様体正則化
カーネル合成実際には、色々な手法が山ほど提案されています。
紹介した手法が代表的とは限りませんが、ベースとなる考え方は大体同じです。

IBM Tokyo Research Laboratory

構造に関する予測タスク： リンク予測© Copyright IBM Corporation 2006

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

リンク予測問題は、部分的に観測されているネットワーク構造から、残りの構造を推定する問題です
例えば、生体ネットワークの構造予測
SNSにおける友人の推薦

特にバイオインフォマティクス分野で著しく発展している
理由は、たぶん一番役に立ちそうだから補完部分的に観測される構造予測される構造

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

リンク予測の問題は、ノードペアの分類問題として捉えることができます
リンク予測の問題は、2つのノードに注目して、その間にリンクがあるかないか （分類問題）
リンクのありそう具合 （ランキング問題）を予測する問題と考えることができる
リンクの存在はお互いに独立に決まる（i.i.d.）と仮定する
この2つのノードの間にリンクはありますか？ （はい／いいえ）

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

リンク予測は、ノードペアの特徴ベクトルに基づき分類を行います
普通の分類は、データ i の特徴ベクトル x(i) に基づき、データ i の分類を行う

リンク予測では、ノードペア（i, j ）の特徴ベクトル (x(i) , x(j) ) から、ノードペアの特徴ベクトル z(i,j) を構成し、これに基づきノードペア （i, j ） の分類を行う
もっとも単純な z(i,j) の定義の仕方は、要素ごとの和や積によって定義する方法

z(i,j) = ( x1(i)・x1(j) , x2(i)・x2(j) , x3(i)・x3(j) , ...

)でもこれではちょっと不十分。
「片方にある特徴があって、もう片方にそれに対応する別の特徴がある」が表現できないから

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

ノードペアの特徴ベクトルは、ノードの特徴ベクトルのテンソル積で定義できます
また、ノードペアの特徴ベクトル同士のカーネル関数も容易に計算できます
2つのノードの特徴ベクトルのテンソル積によってノードペアの特徴ベクトルを定義する

z(i,j) = x(i)ノードペアの特徴ベクトル=(x(j)

x1(i)・x1(j) , x1(i)・x2(j) , x1(i)・x3(j) , ...

i
特徴ベクトル x(i)x2(i)・x1(j) , x2(i)・x2(j) , x2(i)・x3(j) , ... ,kx3(i)・x1(j) , x3(i)・x2(j) , x3(i)・x3(j) , ...

) 特徴ベクトル x(k)

jx(ｊ)
lx(l)

によってノードペアの特徴ベクトルを定義する
カーネル関数も簡単： 2組のノードペア (i, j ) と (k ,l ) の特徴ベクトルz(i,j), z(k,l) 間の内積は、＜ z(i,j), z(k,l) ＞ = ＜ x(i), x(k) ＞・＜ x(j), x(l) ＞のように計算できるノードの特徴ベクトルの次元の計算量で計算できる （ただしノード数の2乗になる）

ペアの組み合わせに向きがない場合には対称化して使う ＜ z(i,j), z(k,l) ＞ + ＜ z(i,k), z(j,l) ＞
あとは SVM などに投げ込めば解決
Oyama & Manning: Using Feature Conjunctions across Examples for Learning Pairwise Classifiers, ECML 2004
Ben-Hur & Noble: Kernel methods for predicting protein–protein interactions, Bioinformatics, Vol. 21 Suppl. 1, 2005

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

性能はイイみたいです
同一著者の同定

タンパク質の機能予測（[Oyama & Manning] より拝借）（[Ben-Hur & Noble] より拝借）

テンソル積
（イイ）

提案法（イイ）

要素ごとの積
（悪い）
従来法
（悪い）

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

ノード分類同様、リンク予測においても、ノードのもつ情報 と構造の持つ情報（＝リンク指標） の2種類を組み合わせて用いることができます
ノードの持つ情報： ノード単体の情報をノードペア情報にまとめ上げて使う （前述）
タンパク質ネットワークの場合、個々のタンパク質はそれぞれ配列情報などの情報を持っているSNSの場合、個々の人はそれぞれの個人情報を持っている構造の持つ情報 （＝リンク指標）： 大体もともとノードペアに対して定義される
計量社会学における社会ネットワーク分析の文脈で古くから用いられている各種のリンク指標を用いることができる
情報検索でも色々提案されている
ノード分類のときに使った指標（例えば、拡散カーネル）を使うのもアリ

2種類をまとめて分類器に渡せば解決

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

構造的なリンク指標の多くはネットワーク構造の遷移モデルに基づいています
社会ネットワーク研究やスケールフリーネットワーク研究においていくつかの指標が提案されている
これらは、ネットワークの構造遷移モデルに基づいている
共通の隣接ノードが多いほど、リンクが張られやすいとするモデル 「友達の友達は友達」(i) はノード i の隣接ノード集合
common neighbors の重み付きバージョン 「友達が少ない人ほど付き合いは深い」（こちらは情報検索で使われる指標）
遠距離の影響もとりいれたcommon neighbors

pathi,j(l)はノード i から j への長さ l のパスの集合- これは、ほぼ拡散カーネル
バラバシのpreferential attachment モデル （友人が多いほど、より多くの友人を得る）

単純に、指標の大きい順にリンクがあると予測する方法もアリ
Liben-Nowelly & Kleinberg: The Link Prediction Problem for Social Networks, CIKM 2004

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

参考： 各指標の相対的な関係
代謝ネットワークデータに対する各手法の予測の Spearman 相関 （順序の相関）大きいほど予測が似ている

preferential

相関のMDSによる視覚化• preferential attachmentとcommon neighborsが一番遠い

proposed

Katz_0.05

Jaccard's
Adamic/AdarcommonIBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

【手前味噌】 「構造情報だけで、できるとこまで頑張ろう」
リンク指標をパラメタライズすることで予測精度を高めようという試みを行っています
個々のリンク指標に注目すると、これらのパラメタライズされた版を考えることができる
例えば、ノードからノードへの枝の「コピー＆ペースト」が確率的におこるノードコピーモデル
もともと Kleinberg らによって、Webの構造進化のモデルとして提案されたタンパク質のネットワークの成長過程のモデルとしても有力ノード間のコピー確率をモデルパラメータとして、パラメータを学習、残りの部分を予測する
観測されるネットワークは、この時間変化モデルの定常状態であると仮定して、分かっている部分を使ってパラメータを最尤推定、そして残りの部分を予測する

i
確率wijでコピー
時間変化jij

Kashima & Abe: A Parameterized Probabilistic Model of Network Evolution for Supervised Link Prediction, ICDM 2006
( To Appear )IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

リンク指標をパラメタライズすることによって予測精度は向上します
提案されているいくつかのリンク指標と比べて性能が改善された同様に、他の指標のパラメタライズも考えられるはず…
precision (%)

precision (%)
100

提案手法が優位

100
9090802080
proposed70
Katz_0.05
60
preferential
50
Adamic/Adar
40
Jaccard's
30
common20

1010706050
40300050

代謝ネットワーク

1000
recall0(%)

提案手法が優位

proposed
Katz_0.05
preferential
Adamic/AdarJaccard's
common50100

タンパク質相互作用ネットワーク

recall (%)

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

まとめ： リンク予測の問題は、ノードペアについての分類問題と考えます
ノードの特徴から、ノードペアの特徴を構成する方法を紹介しました
ネットワーク構造に基づくいくつかのリンク指標を紹介しました
手前味噌として、リンク指標のパラメタライズの試みを紹介しましたIBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

統一的フレームワーク？： ネットワーク構造全体のモデル

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

ネットワーク構造全体の一般的モデルを考えることで、問題をより一般的に捉えなおします
ここまでで疑問
ノード分類で 「隣同士は似ている」 というけれど…
• 「隣同士は似ていない」• 「隣が似ているもの同士は似ている」などは扱えないの？
リンク指標は恣意的、どれを使うの？ 全部使うの？ そもそもこれで全部なの？

また、これまではノードあるいはリンクの独立性を仮定し、分類問題に帰着してきたが、ネットワーク構造の大局的な整合性は無視しているネットワーク構造全体のより一般的なモデルが考えられないか？

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

マルコフネットワークは、ネットワーク全体の確率モデルを定義します
たぶんモデルとしてはファイナルアンサーに近いですが、計算は大変です
ネットワーク構造 G の特徴ベクトルを定義

G = {X, Y} は与えられている部分 X と、予測したい部分からなる• ノード分類の場合： Xはノード特徴とリンク構造、Yがノードラベル• リンク予測の場合： Xはノード特徴と部分的なリンク、Yが残りのリンク
各特徴（の各要素）はネットワーク構成部品（テンプレート）のマッチ回数+1-1「+1の隣は-1」な特徴（ノード分類）X
Relational Markov Network
各部品の重要度

Z(X) の計算は大変。 サンプリングなどによる近似が必要。
予測が大変「友達の友達は友達なんかじゃない」な特徴（リンク予測）ネットワーク構成部品（テンプレート）の例

Taskar et al.: Label and Link Prediction in Relational Data, IJCAI Workshop on Learning
Statistical Models from Relational Data, 2003

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

…なので、大規模なデータには適当な中間的なモデルを考えていくのがよいでしょう
例えば、ネットワークのスケールフリー性を積極的に予測に用いていくという試みもあります
現実世界のネットワーク構造は、しばしばスケールフリーネットワークになっている
つまり次数 k がベキ分布に従う

Pr(k)k（ は定数）

ネットワーク構造に「スケールフリーネットワークになるような制約」を入れて予測を行うこと
で、より現実のネットワーク構造に近いものが構成できるはず
ネットワーク構造の事後分布に、スケールフリー性をもつ事前分布を入れる（ネットワーク構造の事後分布） = （ノードペアからのリンク確率） ｘ （スケールフリーな事前分布）

Pr(k )

kGomez et al.: Probabilistic Prediction of Unknown Metabolic and Signal-Transduction Networks, Genetics 159, 2001

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

ネットワーク構造データの解析において、機械学習の立場からどのような考え方に基づいたアプローチが行われているかを紹介しました
リンクマイニングのタスクのうち「ノード分類」と「リンク予測」を紹介しました「隣は似ている」という考えに基づくアプローチを紹介しました
ネットワーク構造の遷移モデルから出てくるいくつかのリンク指標を紹介しました
これらの制約を除いたより一般的なモデルを紹介しました