シムランク

SimRank は、シンプルで直感的なグラフ理論モデルに基づく一般的な類似度尺度です。SimRank は、オブジェクト間の関係を持つあらゆるドメインに適用でき、他のオブジェクトとの関係に基づいて、オブジェクトが発生する構造コンテキストの類似度を測定します。実質的に、SimRank は、「2 つのオブジェクトは、類似のオブジェクトによって参照されている場合に類似していると見なされる」という尺度です。SimRank は広く採用されていますが、さまざまな要因の影響を受ける不合理な類似度スコアを出力する可能性があり、証拠重み係数の導入、^[1]、 SimRank によって無視される追加の用語の挿入^[2]、または PageRank ベースの代替手段の使用など、いくつかの方法で解決できます。^[3]

多くのアプリケーションでは、オブジェクト間の「類似性」の尺度が必要です。 1 つの明らかな例は、従来のテキスト コーパスまたはWorld-Wide Webでの「類似ドキュメントの検索」クエリです。 より一般的には、類似性の尺度は、ユーザーの好みに基づいて「類似」ユーザーとアイテムがグループ化されるレコメンデーション システムでの協調フィルタリングなど、オブジェクトをクラスタ化するために使用できます。

オブジェクトのさまざまな側面を使用して類似性を判断できますが、通常はドメインとそのドメインの類似性の適切な定義によって異なります。ドキュメント コーパスでは、一致するテキストが使用される場合があり、協調フィルタリングでは、共通の好みによって類似のユーザーが識別される場合があります。SimRank は、多くの関心領域で見られるオブジェクト間の関係を活用する一般的なアプローチです。たとえば、Webでは、2 つのページ間にハイパーリンクがある場合、それらのページは関連しています。同様のアプローチは、科学論文とその引用、または相互参照情報を含むその他のドキュメント コーパスに適用できます。レコメンデーション システムの場合、アイテムに対するユーザーの好みは、ユーザーとアイテムの関係を構成します。このようなドメインは、ノードがオブジェクトを表し、エッジが関係を表すグラフとして自然にモデル化されます。

SimRankアルゴリズムの背後にある直感は、多くのドメインで類似のオブジェクトが類似のオブジェクトによって参照されるというものです。より正確には、オブジェクトと は、それぞれオブジェクトとから参照されている場合に類似しているとみなされ、と自体も類似しています。基本ケースは、オブジェクトがそれ自体 に最大限に類似していることです。^[4]${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle d}$${\displaystyle c}$${\displaystyle d}$

SimRank は、構造的コンテキストの類似性のみを決定する一般的なアルゴリズムであることに留意することが重要です。SimRank は、オブジェクト間に十分な関連関係があり、少なくとも何らかの類似性の概念を関係に基づいているすべてのドメインに適用されます。明らかに、他のドメイン固有の側面の類似性も重要です。これらは、全体的な類似性の尺度として、関係構造的コンテキストの類似性と組み合わせることができます (また、組み合わせる必要があります)。たとえば、Web ページの場合、SimRank は従来のテキスト類似性と組み合わせることができます。同じ考え方が科学論文やその他のドキュメント コーパスにも適用されます。推奨システムの場合、アイテム間の既知の類似性 (両方のコンピューター、両方の衣類など) や、ユーザー間の類似性 (同じ性別、同じ支出レベルなど) が組み込まれている場合があります。この場合も、これらの類似性を、好みのパターンに基づいて計算された類似性スコアと組み合わせて、全体的な類似性の尺度を作成できます。

有向グラフのノードについて、 の入近傍と出近傍の集合をそれぞれと表します。の場合には、個々の入近傍は と表され、の場合には、個々の出近傍は と表されます。 ${\displaystyle v}$${\displaystyle I(v)}$${\displaystyle O(v)}$${\displaystyle v}$${\displaystyle I_{i}(v)}$${\displaystyle 1\leq i\leq \left|I(v)\right|}$${\displaystyle O_{i}(v)}$${\displaystyle 1\leq i\leq \left|O(v)\right|}$

オブジェクトとの類似性を で表します。前述の動機に従って、 について再帰方程式が書かれます。の場合、は と定義されます。それ以外の場合、 ${\displaystyle a}$${\displaystyle b}$${\displaystyle s(a,b)\in [0,1]}$${\displaystyle s(a,b)}$${\displaystyle a=b}$${\displaystyle s(a,b)}$${\displaystyle 1}$

${\displaystyle s(a,b)={\frac {C}{\left|I(a)\right|\left|I(b)\right|}}\sum _{i=1}^{\left|I(a)\right|}\sum _{j=1}^{\left|I(b)\right|}s(I_{i}(a),I_{j}(b))}$

ここで、 はと の間の定数です。ここで少し技術的なことは、またはのどちらかに内隣がない可能性があるということです。この場合、と の間に類似性を推測する方法がないため、類似性は に設定され、したがって、 または の場合には、上記の式の合計は と定義されます。 ${\displaystyle C}$${\displaystyle 0}$${\displaystyle 1}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle s(a,b)=0}$${\displaystyle 0}$${\displaystyle I(a)=\emptyset }$${\displaystyle I(b)=\emptyset }$

との間の任意の定数が与えられたとき、 を類似度行列とし、そのエントリが類似度スコア を表すものとし、を列正規化された隣接行列とし、そのエントリがから への辺がある場合に、それ以外の場合は 0 であるとする。行列表記では、SimRank は次のように定式化できる。 ${\displaystyle C}$${\displaystyle 0}$${\displaystyle 1}$${\displaystyle \mathbf {S} }$${\displaystyle [\mathbf {S} ]_{a,b}}$${\displaystyle s(a,b)}$${\displaystyle \mathbf {A} }$${\displaystyle [\mathbf {A} ]_{a,b}={\tfrac {1}{|{\mathcal {I}}(b)|}}}$${\displaystyle a}$${\displaystyle b}$

${\displaystyle {\mathbf {S} }=\max\{C\cdot (\mathbf {A} ^{T}\cdot {\mathbf {S} }\cdot {\mathbf {A} }),{\ mathbf {I} }\},}$

ここで、は単位行列です。 ${\displaystyle \mathbf {I} }$

グラフの SimRank 方程式の解は、固定点への反復によって得られます。を のノード数とします。各反復 で、エントリ を保持できます。ここで、 は反復との間のスコアを示します。に基づいて、 を連続的に計算します。 から開始します。ここで、それぞれは実際の SimRank スコアの下限です。 ${\displaystyle G}$${\displaystyle n}$${\displaystyle G}$${\displaystyle k}$${\displaystyle n^{2}}$${\displaystyle s_{k}(*,*)}$${\displaystyle s_{k}(a,b)}$${\displaystyle a}$${\displaystyle b}$${\displaystyle k}$${\displaystyle s_{k+1}(*,*)}$${\displaystyle s_{k}(*,*)}$${\displaystyle s_{0}(*,*)}$${\displaystyle s_{0}(a,b)}$${\displaystyle s(a,b)}$

${\displaystyle s_{0}(a,b)={\begin{cases}1{\mbox{ }},{\mbox{ }}{\mbox{if }}a=b{\mbox{ }},\\0{\mbox{ }},{\mbox{ }}{\mbox{if }}a\neq b{\mbox{ }}.\end{cases}}}$

から計算するには、基本的な SimRank 方程式を使用して次の式を取得します。 ${\displaystyle s_{k+1}(a,b)}$${\displaystyle s_{k}(*,*)}$

${\displaystyle s_{k+1}(a,b)={\frac {C}{\left|I(a)\right|\left|I(b)\right|}}\sum _{i=1}^{\left|I(a)\right|}\sum _{j=1}^{\left|I(b)\right|}s_{k}(I_{i}(a),I_{j}(b))}$

については、については です。つまり、各反復 で、基本的な SimRank 方程式に従って、前回の反復からの近傍の類似度スコアを使用しての類似度を更新します。値は が増加しても減少しません。^[4]では、値が基本的な SimRank 方程式を満たす限界、つまり SimRank スコアに収束することが示されています。 つまり、すべての、についてです。${\displaystyle a\neq b}$${\displaystyle s_{k+1}(a,b)=1}$${\displaystyle a=b}$${\displaystyle k+1}$${\displaystyle (a,b)}$${\displaystyle (a,b)}$${\displaystyle k}$${\displaystyle s_{k}(*,*)}$${\displaystyle k}$${\displaystyle s(*,*)}$${\displaystyle a,b\in V}$${\displaystyle \lim _{k\to \infty }s_{k}(a,b)=s(a,b)}$

元のSimRank提案では、減衰係数と実行する反復回数の固定値を選択することが提案されていました。しかし、最近の研究^[5]では、およびに与えられた値は、反復計算されたSimRankスコアの精度が一般的に比較的低いことを意味していることが示されました。より正確な計算結果を保証するために、後者の論文では、より小さな減衰係数（特に）を使用するか、反復回数を増やすことを提案しています。 ${\displaystyle C=0.8}$${\displaystyle K=5}$${\displaystyle C}$${\displaystyle K}$${\displaystyle C=0.6}$

CoSimRankはSimRankの変形であり、ローカル定式化もできるという利点があります。つまり、CoSimRankは単一のノードペアに対して計算できます。^[6]を類似度行列とし、そのエントリが類似度スコアを表すものとし、を列正規化された隣接行列とします。すると、行列表記では、CoSimRankは次のように定式化できます。 ${\displaystyle \mathbf {S} }$${\displaystyle [\mathbf {S} ]_{a,b}}$${\displaystyle s(a,b)}$${\displaystyle \mathbf {A} }$

${\displaystyle {\mathbf {S} }=C\cdot (\mathbf {A} ^{T}\cdot {\mathbf {S} }\cdot {\mathbf {A} })+{\mathbf {I} },}$

ここで、は単位行列です。 1 つのノード ペアのみの類似度スコアを計算するには、を標準基底のベクトル、つまり、番目のエントリが 1 で、他のすべてのエントリが 0 であるとします。次に、CoSimRank は 2 つの手順で計算できます。 ${\displaystyle \mathbf {I} }$${\displaystyle p^{(0)}(i)=e_{i}}$${\displaystyle e_{i}}$${\displaystyle i}$

1. ${\displaystyle p^{(k)}=Ap^{(k-1)}}$
2. ${\displaystyle s(i,j)=\sum _{k=0}^{\infty }C^{k}\langle p^{(k)}(i),p^{(k)}(j)\rangle }$

ステップ 1 は、Personalized PageRankの簡略版と見ることができます。ステップ 2 では、各反復のベクトル類似度を合計します。行列表現とローカル表現はどちらも、同じ類似度スコアを計算します。CoSimRank は、 を変更することで、ノード セットの類似度を計算するためにも使用できます。 ${\displaystyle p^{(0)}(i)}$

• FogarasとRacz ^[7]は、モンテカルロ法を用いた確率計算を通じてSimRankの計算を高速化することを提案した。
• Antonellisら^{[8]は、SimRank方程式を拡張し、(i)}インシデントノードの証拠係数と(ii)リンクの重みを考慮に入れました。
• Yuら^[9]は、異なる部分和の間で小さな共通部分を共有する細粒度メモ化法を介してSimRank計算をさらに改善しました。
• チェン氏とジャイルズ氏はSimRankの限界と適切な使用例について議論した。^[3]

Lizorkinら^[5]はSimRankの計算を高速化するための3つの最適化手法を提案した。

1. 必須ノードの選択により、事前スコアがゼロのノード ペアの一部の計算が不要になる場合があります。
2. 部分和のメモ化は、類似度の合計の一部をキャッシュして後で再利用することで、異なるノード ペア間の類似度の繰り返し計算を効果的に削減できます。
3. 類似度のしきい値設定により、計算されるノード ペアの数をさらに削減できます。

特に、部分和メモ化の 2 番目の観察は、 から への SimRank の計算を大幅に高速化する上で重要な役割を果たします。ここで、は反復回数、はグラフの平均次数、 はグラフ内のノード数です。部分和メモ化の中心的な考え方は、次の 2 つのステップで構成されます。 ${\displaystyle {\mathcal {O}}(Kd^{2}n^{2})}$${\displaystyle {\mathcal {O}}(Kdn^{2})}$${\displaystyle K}$${\displaystyle d}$${\displaystyle n}$

まず、上の部分和は次のように記される。 ${\displaystyle I(a)}$

${\displaystyle {\text{Partial}}_{I(a)}^{s_{k}}(j)=\sum _{i\in I(a)}s_{k}(i,j),\qquad (\forall j\in I(b))}$

そして、次のよう に繰り返し計算される。${\displaystyle s_{k+1}(a,b)}$${\displaystyle {\text{Partial}}_{I(a)}^{s_{k}}(j)}$

${\displaystyle s_{k+1}(a,b)={\frac {C}{|I(a)||I(b)|}}\sum _{j\in I(b)}{\text{Partial}}_{I(a)}^{s_{k}}(j).}$

したがって、、、の結果は、後で最初の引数として 与えられた頂点の類似度を計算するときに再利用できます。${\displaystyle {\text{Partial}}_{I(a)}^{s_{k}}(j)}$${\displaystyle \forall j\in I(b)}$${\displaystyle s_{k+1}(a,*)}$${\displaystyle a}$

• ページランク

• Cai, Y.; Cong, G.; Jia, X.; Liu, H.; He, J.; Lu, J.; Du, X. (2009-12-01)。「実世界ネットワークにおけるリンクベースの類似性を計算するための効率的なアルゴリズム」。2009第9 回 IEEE 国際データマイニング会議。pp.  734– 739。doi :10.1109/ ICDM.2009.136。ISBN 978-1-4244-5242-2. S2CID  9799597。