2015/2/24

疑似独立集合制約と正規化カットを用いたグラフの構造比較
北海道大学 情報科学研究科
間澤直寛， Zhai HongJie ，原口誠
電気通信大学 先進アルゴリズム研究ステーション
富田悦次

z グラフ（全体）の差異や距離ではなく，グラフの部分での差異を示す頂点集合．
z それらは複数あり，それゆえに，マイニングの問題と考える

Contrast vertex set:
２つのグラフの差異を示す頂点集合

Base graphanti‐community

時間，場所，

target graph

塊． 孤立性を要求
community1

2015/2/24

暗黙の仮定，ならびに目標• 接続
接続・非接続関係が全て同時に変わることは稀．
非接続関係が全て同時に変わることは稀
多くの（特に非接続）関係は変わらない．
• 特に，ベースにおいて疎結合（非接続）な頂点集合で，ターゲットにおいて密結合のものを探す．
• タ
ターゲットにおけるゲットにおける community 性（外部との接続が少数）

関連研究 1： 制約下での極大疑似クリーク探索
E.サラ et al., MPS 87‐2 (2012)
Y.Okubo et al., Discovery Science 2012. （和文版は JSAI2012 大会）

G (base )G ( t arg et )「無い → 有」統合グラフの極大疑似ク

G リーク（k‐Plex）で，base,② 疑似クリーク固有の問題点：

target における外部接続制約を満たすもの

接続例外を許したクリーク
例外数の増加⇒ 例外の組合せ爆発① 孤立性がより高い部分を見落とす危険性22015/2/24

関連研究２： c‐孤立(疑似)クリーク
Ito 2009, Komusiewicz 2009

最小c‐孤立性：
外部次数c未満の頂点が存在

最大c‐孤立性：
各頂点の外部次数がc未満のクリーク

c‐孤立性：
外部次数が平均c未満

極大な最大c‐孤立 k‐plex 列挙

k=1 を除いて不十分= 極大(k,c)‐plex の列挙

逆単調性が言えない ⇒ 組合せ論的探索の困難性
少なくとも自明ではない．

今回の作戦
z 逆単調性に基づくクリーク探索の高速性を活かす：
目標それ自体は，接続例外を許した疑似クリーク
距離空間への埋め込み (正規化カット最小化）
unit disk graph 風のグラフにおけるクリーク制約．
z ベースでの疎結合性： 疑似独立集合制約（補グラフにおける疑似クリーク）
２つの制約（共に逆単調）を同時に満たす
極大な頂点集合を列挙
 埋め込み後の disk graph のクリークを，候補頂点を追加する形で形成する．
 その際，ベースでの制約を満たさない候補頂点をカット可能

3

2015/2/24

正規化カットと射影（埋め込み）∑w
cut(X, X )Ncut(X, X ) ==.
vol(X)∑di∈X , j∈Xi∈Xiji∑ Ncut( X X ) の最小化問題の近似解j,1≤ j ≤ kj

Lsim = D −1/ 2 L D −1/ 2 = D −1/ 2 ( D − W ) D −1/ 2⎛ λ1 L 0 ⎞⎟⎜V ' LsimV = ⎜ M O M ⎟⎟⎜⎝ 0 L λn ⎠D−1 / 2頂点の近接性と unit
disk graphrr
V = (v1 ... vn )⎛ v11 / d1⎜rr(v1 ... vk ) = ⎜ M⎜⎜⎝ vn1 / d n

L v1k / d1 ⎞⎟⎟OM⎟
L vnk / d n ⎟⎠一般化固有値問題の固有ベクトル

射影距離の性質
狭い範囲内の配置

2Ncut(x, x) = x′D −1 2 LD −1 2 x =自明な解⎛ xx j ⎞⎟1.
wij ⎜ i −∑⎟2 i, j ⎜ didj⎝⎠( d ，) との直交条件 ∑ d x = 0i i

一般化固有値問題の解iiiy=D「端末」の次数は概ね小で，近場に配置した方が最小化に有利． 「センター」は，バランス条件から少し離れて配置−1/ 2x
1y ' Ly = ∑ wij ( yi − y j ) 22 i, j∑d y = 0iii

4

2015/2/24

固有ベクトルの距離の性質 (Mazawa’s original slide)
一定の距離基準で辺を張ると、うまくクラスタリングできない場合がある。その例が、スターグラフである。

固有ベクト
ル密度が高い部分と少し離れた値が出る。
ソーシャルネットワークは特定の人物に多くの人が集まることが多いのでスター構造になりやすい。

DBSCAN とその補正

左の形状だと，フィルダーベクトルでは，スターも端末もごく近くに配置
すると，センターの接続先と端末が近くになりまずい？
第２固有値だと，センターと端末の違いを認識している？
いずれにせよ，センターの外部との接続関係にも注意して 数値実験がも注意して，数値実験が必要．
バランス条件があるので，mazawa の主張はにわかには信じがたい．

DBSCAN:① 近傍内に多数の点を持つ内点(core pt)② 近場の core pt を結線で結んだときの連結成分③ “境界点”を追加し，クラスタ各クラスタ毎に，各点から最も近いクラスタ外の点と結ぶ．
この補正後のグラフに対するクリーク探索を行う

5

2015/2/24

minPts, ε の決め方（経験則）• minPts = k から ε を決める
Noise: どのクラスタにも属さな 孤立点も属さない孤立点

k − dist ( pt )K 個の点を含む最小半径狭い範囲に k 個の点～ core ptptp• minPts 大： 希少な core pt.
minPts 小： 殆どが core pt
core pt の数で適宜決める

疑似独立集合制約

Gbase

補グラフにおいて k‐plex
高々 (k‐1) の結線．

逆単調性

Gbase

補グラフで 高々 (k‐1)(k ) の欠落

6

2015/2/24

実験データ
2006年9月の新聞記事において単語を頂点、単語同士の共起を辺として、頻度で重みを付ける。

全国版の某政党に関する記事から抽出した単語の関係グラフをBase。
北海道版からのそれをTargetとする。

頂点数：749
辺数(Base)：65463
辺数(Target)：87226
k=5

実験結果
得られた解の数は3041、解の最大サイズは25
K=5, minPts = 5, ε = 2*10^{‐4}
この例では，k =4 でもOK最も顕著な差異があった例
も 著な差 があ例
Target （地方版）

Base （全国版）
地方票
党友
落選議員名
健闘
etc.

2006年9月の某政党総裁選において、当選議員が全国的には圧勝であったが、北海道では他の議員も健闘していたという記事が見られた。

7

2015/2/24

計算時間(固有値計算以外)
計算時間と頂点数

Target3000

平均次数：232.9132

計算時間（ms）

2500
2000
1500
1000

距離空間射影500

平均次数：5.9839

00500

1000

1500

2000

2500

頂点数

クリーク探索の高速性と，ダブル制約の効果

空間内に バランスをとって配置され，その結果，もとのグラフと比較すると疎になる

今後の課題
埋め込みの補正は一つの経験則的なパッチ
9 DBSCAN 以外の Density‐based
Density based clustering の検討
9 元のターゲットグラフの接続構造を保存する埋め込みの可能性

計算時間の問題点 ラプラシアンのスペクトル分解
計算時間の問題点：
9 近似高速化手法の導入

8