クロスエントロピーに基づくネットワークデータの埋め込み
山田武士○、斉藤和巳、上田修功
ＮＴＴ コミュニケーション科学基礎研究所
京都© NTT Communication Science Laboratories

研究の目的• 複雑なリレーショナルデータの表現手段として、ネットワーク表現は有効
ネットワーク＝N 個のノードとノード間のリンクからなる集合• ＷＥＢページのハイパーリンクネットワーク• 生物学の遺伝子制御ネットワーク• 社会学のソーシャルネットワーク• 低次元ユークリッド空間への効果的なネットワークの埋め込みが必要• ネットワークを直接「ブラウジング」することによる新たな知見の獲得⇒ ネットワークに内在する知識の獲得と、科学的発見に結びつく構造の抽出の効率向上⇒ 発見科学、機械学習• 次世代の３Ｄウェブブラウジングに向けたコア技術の提供⇒ Ｗｅｂサイエンス、Ｗｅｂテクノロジー⇒ Ｗｅｂに限らず各種情報の閲覧（写真、商品パンフレット、旅行案内、）
ブラウジングに最適な，ネットワークの低次元ユークリッド空間への埋め込みアルゴリズムを探求© NTT Communication Science Laboratories

埋め込みに関する二つの基本原則
原則A (connectivity preserving principle)
各ノードは，それと隣接するノード を，隣接しないノードより相対的により近くに配置する．
原則B (distance preserving principle)
各ノードのペアにとって，相互のグラフ距離（最短経路）がユークリッド空間の距離としてもっとも忠実に復元されるように配置する．（主流）⇒ 古典ＭＤＳ（Torgerson）、ばねモデル（Ｋａｍａｄａ＆Ｋａｗａｉ）、スペクトラルクラスタリング（Ｎｇ）
原則Ａ

原則Ｂ

• 原則B ⇒原則Ａ（逆は成立せず）• 原則Bを満たすのは困難 ⇒ 偏った配置になりがち• グラフ距離がノード間の近接関係の忠実な反映とは限らない

できるだけ原則Ａを満足する埋め込みを求めたい© NTT Communication Science Laboratories

クロスエントロピーに基づく埋め込み法
ρ (di,j) 2[0,1], ρ (0)=1, ρ (1)=0, ：（連続値）類似度関数とし，［原則Ａ］の条件を類似度間のクロスエントロピーで近似に表現する• N ：ネットワークのノード数、 K：埋め込み次元数• A = (ai,j)， ：隣接行列， ai,j 2 {0,1}, ai,j = 1, ai,j = aj, iK（無向を仮定）• x1,L,xN ： N個のノードの座標

i =1

di , j =|| xi − x j ||2 = ∑ ( xi , k − x j ,k ) 2• ［原則A］各ノードは，隣接ノード を，非隣接ノードより近くに配置「近く」 ＝ 「類似度ρ (di,j)大」• ［類似度による言い換え］各ノードは隣接ノードとの類似度ρ (di,j) が，非隣接ノードとの類似度よりも大きくなるように配置>ρ「類似度ρ (di,j) 」≒「 ai,j （離散類似度とみなす） 」• ［類似度の近似］ ρ (di,j) をi,jの関数と見たとき、各ノードの連続類似度
ρ (di,j) が離散類似度 ai,j のもっとも良い近似となるように配置
クロスエントロピー

ρ (di,j) と ai,jとの負のクロスエントロピーを最小化

Ei , j = −ai , j ln( ρ (di , j )) − (1 − ai , j ) ln(1 − ρ (di , j ))© NTT Communication Science Laboratories

クロスエントロピーに基づく埋め込み法（続き）
Ei , j = −ai , j ln( ρ (di , j )) − (1 − ai , j ) ln(1 − ρ (di , j ))1

ρ = exp(−di , j2ρ)∞0ai , j1
2
Ei , j =|| xi − xj || −(1 − ai , j ) ln(1 − exp( || xi − xj ||2 ))
2
2N −1

目的関数

NJ = ∑ ∑ Ei , j +μ n|| x ||
∑22

ラベル１

ラベル０ii =1 j =i +1i =1正規化のためのWeight-Decay項• i を固定したとき，ai,j はノード j の{0,1}のクラスラベルを定義• x1,L,xN をパラメータとする N個の２値分類問題を同時に解くことと解釈可能⇒ ニューラルネットワークのオンライン学習© NTT Communication Science Laboratories

学習アルゴリズム
各ノードにおいて勾配ベクトルがゼロとなるエネルギー極小配置を探索• ニューラルネットワークのオンライン学習の手法を適用（ばねモデルの学習法をほぼ踏襲）• 一度に１ノード移動し、その間他ノードは固定する逐次的アルゴリズム• 差分のみの更新で計算を効率化
入力: N £ N 隣接行列 A = (ai,j)、埋め込み次元 K、収束精度定数 ε勾配ベクトルの変位を一次近似(1) t = 1 とし， x1,L,xN をランダムに初期化(2) 勾配ベクトル Jx1(1), L, JxN(1)Jを計算( t +1)xi=0≈J
H=(3) i = arg maxj{|Jx (t)|2} となる xi を選択
j(t )xi2 (t )∂ 2 J (t )+Δxi = 0t
∂xi ∂xi∂ J（ヘッシアン）∂xi ∂xit(4) |Jx (t)|2 < ε ならば x1,L,xN を出力し終了 -1 (t)–H Jx
if J (t+1) < J (t)(5) 変分ベクトル Δxi を計算 Δxi =λJx (t) otherwiseiii（⇒収束を保証）(6) Jx (t), L, Jx (t) を用いてJx (t+1), L, Jx (t+1) を更新
1N1N(7) xi = xi + Δxiによって xi を更新(8) t = t + 1 とし，ステップ(3)へ© NTT Communication Science Laboratories

Ｆ－値に基づく評価［原則Ａ］を完全に実現する理想的な埋め込みにどれくらい近いかを、Ｆー値に基づいて評価する

Bi (ri )xi

Bi(ri)： 各 xi を中心とし，半径 ri の K 次元球体
理想的な埋め込み ⇒ 各ノード i において完全分離球面が存在• 各ノード i において適切な半径 ri を選べば， i に隣接ノードをすべて含み，非隣接ノードは全く含まない Bi(ri) を構成できる（違反ゼロ）

現実の埋め込み ⇒ 違反ゼロにはできない。
• 各ノード i において、 F-値の意味で違反度最小となる Bi(ri) を構成• 全ノードのF-値の平均で埋め込みの良さを評価［理想］違反ゼロ

∃rixi

［現実］

Bi (ri )

分離球面

xi

違反あり

© NTT Communication Science Laboratories

Ｆ－値に基づく評価（続き）
全ノードのF-値の平均で埋め込みの良さを評価
F-値： Precision と Recall の調和平均

11}
Fi (ri ) = 1/{α+ (1 − α )Pi (ri )Ri (ri )NFi (rˆi )F =∑N 通常はα=1/2i =1Precision

Recall7Pi (ri ) =137
Ri (ri ) =9

半径が小さいほうが有利

半径が大きいほうが有利

正解

Accuracy は高いが、Ｆ－値は低い例 ⇒（スパースなＮＷでは非隣接ノードがはるかに多い）［原則Ｂ］を完全に実現する埋め込みでは F = 1 (ri = 1 for all i )© NTT Communication Science Laboratories

実データを用いた評価実験
E.Coli： 大腸菌（Escherichia coli）の遺伝子制御ネットワーク
NIPS： NIPS掲載論文の共著者ネットワーク
NTT：
ＮＴＴドメインに属するWWWページ
CE: 提案法、CMDS: Torgersonによる古典的ＭＤＳ、KK: ばねモデル、SC: スペクトラルクラスタリング
F (F-measure)
10.8F (F-measure)
11CECEKK

0.8
KK

0.60.6F (F-measure)0.8SCCE0.6CMDSCMDS

0.40.40.4

0.2

0.2

0.2

0025K (dim.)09K (dim.)

KK

SC

51015E.Coli

SC

20

ノード数 328， リンク数 456

23456NIPS78

ノード数1061， リンク数 2080

CMDS
234567NTT

89K (dim.)

ノード数 2870，リンク数 9337

• 期待どおり，提案法が他の手法に比べて，特に配置が難しい低次元において，優れている．
• 中でももっともサイズの大きいNTT を用いた実験において，提案法と従来法の性能差が際立っている．
© NTT Communication Science Laboratories

（参考）比較に用いた従来法
CMDS: Torgersonによる古典的ＭＤＳ1J CMDS = trace{(− YOY − XX' ) 2 }2 G=(gi,j )：グラフ距離行列

O=(oi,j )： oi,j= gi,j £ gi,j
Y: N-次元 Young-Householder 変換行列

SC: スペクトラルクラスタリング
1--

1
2J SC = trace{(D 2 BD − XX' ) 2 }B =(bi,j )： exp (– gi,j /2)
D =(di,j )：対角行列， di,i= Bの第i行の全要素の和
xˆi , j =xi , j∑N

によって結果を球面上に表示
xj =1 i , j

KK: Kamada & Kawaiによるばねモデル

1 N −1 N ( gi , j − || xi − x j ||)J KK = ∑ ∑2 i =1 j =i +1g i2, j2© NTT Communication Science Laboratories

２次元・3次元への埋め込み結果
配置例
各手法の特徴• 古典MDS： 多くのノードが一点に縮退し，可視化，特にブラウジングの観点では問題あり⇒線型手法の限界• バネモデル： 多くのノードが半円状にかたまって配置（「たんぽぽ効果」）• 提案法： より一様に放射状に広がり、空間を効率的に活用• 埋め込み結果はF-値の性能差を良く反映している• バネモデルが復元するグラフ距離が，離散値のため配置が偏在• 従来法は特にノードが密集した領域において，ブラウジングが困難© NTT Communication Science Laboratories

結論• クロスエントロピーに基づくネットワークの埋め込み法を提案• Ｆ－値に基づく定量的評価によって、提案法は［原則Ａ］をより忠実に反映していることを確認• 視覚的にも従来法に比べ、より空間を効率的に活用した埋め込みであることを確認

今後• 一般の（スパースな）重みつきネットワーク・類似度行列へ拡張• ３Ｄウェブブラウザの配置エンジンとして組み込み• 知識発見システムへ発展・組み込み• もっと直接Ｆー値を最適化する手法を探求© NTT Communication Science Laboratories