RankClus：クラスタリングとランキングの統合異種情報ネットワーク分析

最近読んでたソンさんの論文「RankClus: Integrating Clustering with Ranking for Heterogeneous Information Network Analysis」理論的に難しくないですが，よく理解までちょっと時間かかると思って，要点をまとめていきます．

ネットワーク分析は最近，情報ネットワークから知識を抽出する重要な手法としてます．そして，ランキングやクラスタリングは情報ネットワークの全体的なビューを提供しています．ただし，対象が属するクラスタを考慮せずに全体的にランク付けると，あまり意味がない結果になってしまいます．同様に，膨大な数の対象をランクを考えなくてクラスタ結果もおかしくなります．

そして，ソンさんの論文では，マルチライプの情報ネットワークに基づいてランク付けと統合されたクラスタリング手法RankClusを提案しました．

まず，RankClusに関するいくつかの定義を述べます．

１．バイタイプ情報ネットワーク

まず，グラフの中のノードのタイプをXとY2つの集合に分けます． $X=\left\{x_{1}, x_{2}, \ldots, x_{m}\right\}$ と $Y=\left\{y_{1}, y_{2}, \ldots, y_{n}\right\}$ ．xとyはそれぞれの対象です．

そして，グラフ $G=\langle V, E\rangle$ では，ノードの集合は $V(G)=X \cup Y$ ノード間のリンクの集合は $E(G)=\left\{\left\langle o_{i}, o_{j}\right\rangle\right\}, \text { where } o_{i}, o_{j} \in X \cup Y$ とします．

各リンクが存在する数はリンクの重み付け係数として，グラフの隣接行列 $W_{(m+n) \times(m+n)}=\left\{w_{o_{i} o_{j}}\right\}$ を算出できます．グラフ $G=\langle\{X \cup Y\}, W\rangle$ すると，このグラフGはバイタイプ情報ネットワークといいます．

簡単に表すため，隣接行列Wを $W_{X X}, W_{X Y}, W_{Y X}, W_{Y Y}$ 4つのブロックに分け，各対象のサブグラフとすることができます．

$W=\left(\begin{array}{ll} W_{X X} & W_{X Y} \\ W_{Y X} & W_{Y Y} \end{array}\right)$

2．ランキング関数

バイタイプグラフGでは，ランキング関数は全てのノードのランクスコアを与えます． $f: G \rightarrow\left(\vec{r}_{X}, \vec{r}_{Y}\right)$
このランクスコアは以下の条件を満たす．
$\forall x \in X, \vec{r}_{X}(x) \geq 0, \sum_{x \in X} \vec{r}_{X}(x)=1$
$\forall y \in Y, \vec{r}_{Y}(y) \geq 0, \sum_{y \in Y} \vec{r}_{Y}(y)=1$
つまり，ランクスコアは非負，タイプXに属する全ての対象のランクスコアの和は1になる，Yは同様に．
ここのランキングはPageRankみたいに，それぞれの対象に対する重要度を与えるためです．ソンさんの論文では，2つのラインキング関数を提案しました．あとで述べます．

与えたクラスタ数Kにたいし，クラスタリングは目標タイプXに属する全ての対象にクラスタラベルを付けます． $X_{k}$ はクラスタkの対象集合です． $X^{'}$ は任意のクラスタ集合です．

多くのバイタイプネットワークでは，2つタイプの対象数が非対称になっています．例えば，DBLPのデータベースでは，著者の数はおよそ50万，学会の数は4千ぐらいしかない．

それに対し，ソンさんの論文では，より少ない数を持つ対象タイプはこの情報ネットワークの目標タイプとし，他のは属性タイプとします．もっと少ない数かつ意味があるクラスタを生成するため，クラスタリングは目標タイプしか行いません．一方，属性タイプはクラスタリングを補助します．

DBLPの例では，学会を目標タイプとしてクラスタリングする理由は，生成された学会クラスタは数が少なくなるし，固有的な研究分野の意味があります．著者が各学会におけるランクスコアは十分な情報を提供できます．

最初に言ったように，属するクラスタを考えずに，対象をランキングすれば，結果はあまり意味がありません．ゆえに，条件付きランクとクラスタ内ランクの概念を定義します．

3．条件付きランクとクラスタ内ランク
目標タイプX，クラスタ $X^{\prime} \subseteq X$ を与えると，サブネットワーク $G^{\prime}=\left\langle\left\{X^{\prime} \cup Y\right\}, W^{\prime}\right\rangle$ は，Gが頂点 $X^{\prime} \cup Y$ で誘導されたグラフです．Yの条件付きランク $\vec{r}_{Y | X^{\prime}}$ とX'のクラスタ内のランク $\vec{r}_{X^{\prime} | X^{\prime}}$ は直接にランキング関数で算出します． $G^{\prime}:\left(\vec{r}_{X^{\prime} | X^{\prime}}, \vec{r}_{Y | X^{\prime}}\right)=f\left(G^{\prime}\right)$ .
全てのXの対象はサブグラフに存在するわけではないので，Xの条件付きランク $\vec{r}_{X | X^{\prime}}$ はちょっと複雑になっています．ここは，ネットワークGにおける $\vec{r}_{Y | X^{\prime}}$ の伝播スコアとして算出します．

$\vec{r}_{X | X^{\prime}}(x)=\frac{\sum_{j=1}^{n} W_{X Y}(x, j) \vec{r}_{Y | X^{\prime}}(j)}{\sum_{i=1}^{m} \sum_{j=1}^{n} W_{X Y}(i, j) \vec{r}_{Y | X^{\prime}}(j)}$

つまり，クラスタX'が与えられる時，Yの条件付きランクが算出できます．一方，X’に関するXの条件付きランクは今のYのランクにしたがっています．

例えば，DBDM分野クラスタが与えられたら，DBDM分野クラスタにおける著者の条件付きランクが得られます．ある会議がDBDM分野クラスタでの条件付きランクはこの会議に参加する著者の条件付きランクにしたがっています．

この概念に基づいて，この論文の目的は簡略化します．バイタイプグラフは $G=\langle\{X \cup Y\}, W\rangle$ ，目標タイプはX，特定的なクラスタ数はKにすると，今回の目的はXのK個のクラスタ，Xクラスタ内のランク付けと，Xクラスタに対するYのランク付けを生成することです．

4．ランキング関数
4.1　シンプルランキング
会議と著者のシンプルランキングは学会に受け入れた論文数と著者が公開する論文数にしたがっています．
情報ネットワーク $G=\langle\{X \cup Y\}, W\rangle$ が与えられたら，XとYのシンプルランキングが以下に生成されます．
$\left\{\begin{array}{l} \vec{r}_{X}(x)=\frac{\sum_{j=1}^{n} W_{X Y}(x, j)}{\sum_{i=1}^{m} \sum_{j=1}^{n} W_{X Y}(i, j)} \\ \vec{r}_{Y}(y)=\frac{\sum_{i=1}^{n} W_{X Y}(i, y)}{\sum_{i=1}^{m} \sum_{j=1}^{n} W_{X Y}(i, j)} \end{array}\right.$

シンプルランキングでは，参加の会議の質と関係なく，著者が論文の発表数が多ければ多いほど，ランクスコアが高くなる．しかし，現実では，会議と論文の質は数より重要だと思われます．そのため，権威ランキングが提案されました．

4.2 権威ランキング

ここ提案された権威ランキングは権威が高い対象に高いランクスコアを与えます．だから，権威ランキンは最初に情報が少ない時期は，計算が不可能になってしまうと思われます．
そして，以下の経験則は手がかりを与えました．

ルール1：ランクが高い著者はランクが高い会議に論文を発表する．

ルール2：ランクが高い会議はランク高い著者からの論文を引きつける．

ヒューリスティック的に考えると，著者と会議のランクを以下に定義します．

ルール1に基づいて，
各著者のスコアは論文の発表数と発表する会議にしたがっています．
$\vec{r}_{Y}(j)=\sum_{i=1}^{m} W_{Y X}(j, i) \vec{r}_{X}(i)$

正規化すると，
$\vec{r}_{Y}(j) \leftarrow \frac{\vec{r}_{Y}(j)}{\sum_{j^{\prime}=1}^{n} \vec{r}_{Y}\left(j^{\prime}\right)}$ になります．

ルール2に基づいて，
各会議のスコアは論文の数と質にしたがっています．論文の質は著者のランクスコアに従っています．
$\vec{r}_{X}(i)=\sum_{j=1}^{n} W_{X Y}(i, j) \vec{r}_{Y}(j)$

正規化すると， $\vec{r}_{X}(i) \leftarrow \frac{\vec{r}_{X}(i)}{\sum_{i^{\prime}=1}^{m} \vec{r}_{X}\left(i^{\prime}\right)}$ になります．

以上の2つの式を行列で表すと，
$\left\{\begin{array}{l} \vec{r}_{X}=\frac{W_{X Y} \vec{r}_{Y}}{\left\|W_{X Y} \vec{r}_{Y}\right\|} \\ \vec{r}_{Y}=\frac{W_{Y X} \vec{r}_{X}}{\left\|W_{Y X} \vec{r}_{X}\right\|} \end{array}\right.$

定理として，反復式を通じて得られる $\vec{r}_{X}$ と $\vec{r}_{Y}$ それぞれは $W_{X Y} W_{Y X}$ と $W_{Y X} W_{X Y}$ の固有ベクトルである．

証明
$\vec{r}_{X}=\frac{W_{X Y} \vec{r}_{Y}}{\left\|W_{X Y} \vec{r}_{Y}\right\|}=\frac{W_{X Y} \frac{W_{Y X} \vec{r}_{X}}{\left\|W_{Y X} \vec{r}_{X}\right\|}}{\left\|W_{X Y} \frac{W_{Y X} \vec{r}_{X}}{\left\|W_{Y X} \vec{r}_{X}\right\|}\right\|}=\frac{W_{X Y} W_{Y X} \vec{r}_{X}}{\left\|W_{X Y} W_{Y X} \vec{r}_{X}\right\|}.$

ルール3: ある著者の共著者のランクが高ければ，この著者のランクも高くなる．

このルールに基づいて，以下の式が得られる
$\vec{r}_{Y}(i)=\alpha \sum_{j=1}^{m} W_{Y X}(i, j) \vec{r}_{X}(j)+(1-\alpha) \sum_{j=1}^{n} W_{Y Y}(i, j) \vec{r}_{Y}(j)$