ラプラシアン行列

グラフ理論の数学分野において、ラプラシアン行列はグラフラプラシアン、アドミタンス行列、キルヒホッフ行列、離散ラプラシアンとも呼ばれ、グラフの行列表現です。ピエール＝シモン・ラプラスにちなんで名付けられたグラフラプラシアン行列は、 差分法によって得られる負の連続ラプラシアンを近似するグラフ上の負の離散ラプラス演算子の行列形式と見なすことができます

ラプラシアン行列は、多くの機能グラフ特性に関連しています。キルヒホッフの定理は、与えられたグラフの全域木の個数を計算するために使用できます。グラフの最もスパースなカットは、チーガーの不等式によって確立されているように、グラフ ラプラシアンの 2 番目に小さい固有値に対応する固有ベクトルであるフィードラーベクトルを通じて近似できます。ラプラシアン行列のスペクトル分解により、多くの機械学習アプリケーションで見られるような低次元埋め込みの構築が可能になり、グラフ描画のスペクトル レイアウトが決定されます。グラフベースの信号処理は、信号に対応するグラフのラプラシアン行列の固有ベクトルを複素正弦波の標準基底で置き換えることにより従来の離散フーリエ変換を拡張したグラフ フーリエ変換に基づいています。

ラプラシアン行列は単純なグラフに対して定義するのが最も簡単ですが、エッジ重み付きグラフ、つまりグラフの隣接行列の要素であるエッジに重みが付けられたグラフへの応用ではより一般的です。スペクトルグラフ理論は、グラフの特性をスペクトル、つまりグラフに関連付けられた行列（隣接行列やラプラシアン行列など）の固有値と固有ベクトルに関連付けます。重みの不均衡は行列のスペクトルに望ましくない影響を与える可能性があり、正規化（行列要素の列/行スケーリング）が必要になります。その結果、正規化された隣接行列とラプラシアン行列が生成されます。

単純なグラフの定義

ラプラシアン行列

頂点を持つ単純なグラフ が与えられたとき、そのラプラシアン行列は要素ごとに次のように定義される^{[ 1 ]。} ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle v_{1},\ldots ,v_{n}}$ ${\textstyle L_{n\times n}}$

${\displaystyle L_{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{if}}\ i=j\\-1&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}},\end{cases}}}$

あるいは、行列

${\displaystyle L=D-A,}$

ここで、Dは次数行列、Aはグラフの隣接行列です。は単純なグラフなので、1 または 0 のみを含み、対角要素はすべて 0 です。 ${\textstyle G}$ ${\textstyle A}$

以下は、ラベル付きの無向グラフとそのラプラシアン行列の簡単な例です。

ラベル付きグラフ	次数行列	隣接行列	ラプラシアン行列
	${\textstyle \left({\begin{array}{rrrrrr}2&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrrrr}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrrrr}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0&-1&3&0\\0&0&0&-1&0&1\\\end{array}}\right)}$

無向グラフでは、隣接行列とラプラシアン行列の両方が対称であり、ラプラシアン行列の行と列の合計がすべてゼロであることがわかります (これは、ラプラシアン行列が特異であることを直接的に示しています)。

有向グラフの場合、次の例のように、アプリケーションに応じて 入次数または出次数のいずれかが使用されることがあります。

ラベル付きグラフ	隣接行列	出次数行列	出次数ラプラシアン	入次行列	入次数ラプラシアン
	${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&0&0\\0&1&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&-1&-1\\0&1&-1\\-1&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&-1\\0&1&-1\\-1&0&2\\\end{array}}\right)}$

有向グラフでは、隣接行列とラプラシアン行列は非対称です。ラプラシアン行列では、入次数または出次数が使用されている かどうかに応じて、列の合計または行の合計が0になります

有向接続行列を介した無向グラフのラプラシアン行列

頂点v と辺e（頂点と頂点を結び、i ≠ j ）に対する要素B _veを持つ有向接続行列B は 次のように定義される 。 ${\textstyle |v|\times |e|}$ ${\textstyle v_{i}}$ ${\textstyle v_{j}}$

${\displaystyle B_{ve}=\left\{{\begin{array}{rl}1,&{\text{if }}v=v_{i}\\-1,&{\text{if }}v=v_{j}\\0,&{\text{otherwise}}.\end{array}}\right.}$

この定義における辺は技術的には有向であるが、その方向は任意であり、結果として次のように定義される 同じ対称ラプラシアン行列Lが得られる。 ${\textstyle |v|\times |v|}$

${\displaystyle L=BB^{\textsf {T}}}$

ここで、 Bの転置行列です。 ${\textstyle B^{\textsf {T}}}$

無向グラフ	接続行列	ラプラシアン行列
	${\textstyle \left({\begin{array}{rrrr}1&1&1&0\\-1&0&0&0\\0&-1&0&1\\0&0&-1&-1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}3&-1&-1&-1\\-1&1&0&0\\-1&0&2&-1\\-1&0&-1&2\\\end{array}}\right)}$

代替積は、 一般的に使用されている頂点ベースのラプラシアン行列Lとは対照的に、いわゆるエッジベースのラプラシアンを定義します ${\displaystyle B^{\textsf {T}}B}$ ${\textstyle |e|\times |e|}$

有向グラフの対称ラプラシアン

有向グラフのラプラシアン行列は定義上、一般に非対称である。一方、例えば従来のスペクトルクラスタリングは、主に対称な隣接関係とラプラシアン行列を持つ無向グラフを対象に開発されている。対称性を必要とする手法を適用する簡単な方法は、元の有向グラフを無向グラフに変換し、後者のラプラシアン行列を構築することである。

行列表記では、無向グラフの隣接行列は、例えば、元の有向グラフの隣接行列とその転置行列のブール和として定義できます。ここで、 の 0 番目と 1 番目のエントリは、次の例のように、数値ではなく論理値として扱われます。 ${\displaystyle A}$ ${\displaystyle A^{T}}$ ${\displaystyle A}$

隣接行列	対称化隣接	対称ラプラシアン行列
${\textstyle \left({\begin{array}{ccc}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{ccc}0&1&1\\1&0&1\\1&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{ccc}2&-1&-1\\-1&2&-1\\-1&-1&2\\\end{array}}\right)}$

ラプラシアン行列の正規化

大きな次数を持つ頂点（重ノードとも呼ばれる）は、ラプラシアン行列の対角成分が大きく、行列の特性を支配します。正規化は、ラプラシアン行列の成分を頂点の次数で割ることで、そのような頂点の影響を他の頂点の影響とより均等にすることを目的としています。ゼロ除算を避けるため、次数0の孤立した頂点は正規化のプロセスから除外されます

対称正規化ラプラシアン

対称正規化ラプラシアン行列は次のように定義されます。^{[ 1 ]}

${\displaystyle L^{\text{sym}}:=(D^{+})^{1/2}L(D^{+})^{1/2}=I-(D^{+})^{1/2}A(D^{+})^{1/2},}$

ここで、は次数行列の ムーア・ペンローズ逆行列です。 ${\displaystyle D^{+}}$

の要素は次のように与えられる。 ${\textstyle L^{\text{sym}}}$

${\displaystyle L_{i,j}^{\text{sym}}:={\begin{cases}1&{\mbox{if }}i=j{\mbox{ and }}\deg(v_{i})\neq 0\\-{\frac {1}{\sqrt {\deg(v_{i})\deg(v_{j})}}}&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}}$

対称的に正規化されたラプラシアン行列は、隣接行列が対称である場合にのみ対称になります。

隣接行列	次数行列	正規化ラプラシアン
${\textstyle \left({\begin{array}{rrr}0&1&0\\1&0&1\\0&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&2&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-{\sqrt {1/2}}&0\\-{\sqrt {1/2}}&1&-{\sqrt {1/2}}\\0&-{\sqrt {1/2}}&1\\\end{array}}\right)}$

有向グラフの非対称隣接行列の場合、正規化には入次数と出次数のいずれかを使用できます

隣接行列	出次数行列	出次数正規化ラプラシアン	入次行列	次数内正規化ラプラシアン
${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&0&0\\0&1&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-{\sqrt {1/2}}&-{\sqrt {1/2}}\\0&1&-1\\-{\sqrt {1/2}}&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&-{\sqrt {1/2}}\\0&1&-{\sqrt {1/2}}\\-{\sqrt {1/2}}&0&1\\\end{array}}\right)}$

左（ランダムウォーク）および右正規化ラプラシアン

左（ランダムウォーク）正規化ラプラシアン行列は次のように定義されます。

${\displaystyle L^{\text{rw}}:=D^{+}L=I-D^{+}A,}$

ここではムーア・ペンローズ逆行列である。 の元は次のように与えられる。 ${\displaystyle D^{+}}$ ${\textstyle L^{\text{rw}}}$

${\displaystyle L_{i,j}^{\text{rw}}:={\begin{cases}1&{\mbox{if }}i=j{\mbox{ and }}\deg(v_{i})\neq 0\\-{\frac {1}{\deg(v_{i})}}&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}}$

同様に、右正規化ラプラシアン行列は次のように定義される。

${\displaystyle LD^{+}=I-AD^{+}}$。

隣接行列が対称でグラフが正則である場合、左または右の正規化ラプラシアン行列は対称です。そうでない場合、左または右の正規化ラプラシアン行列は非対称です。例えば、

隣接行列	次数行列	左正規化ラプラシアン	右正規化ラプラシアン
${\textstyle \left({\begin{array}{rrr}0&1&0\\1&0&1\\0&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&2&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&0\\-1/2&1&-1/2\\0&-1&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1/2&0\\-1&1&-1\\0&-1/2&1\\\end{array}}\right)}$

この例では、孤立した頂点を持たない場合、右確率的であり、したがってランダムウォークの行列であることも示しています。そのため、左正規化ラプラシアンの各行の和はゼロになります。したがって、ランダムウォーク正規化ラプラシアンをランダムウォーク正規化ラプラシアンと呼ぶこともあります。 あまり一般的ではない右正規化ラプラシアンでは、左確率的であるため、各列の和はゼロになります ${\displaystyle G}$ ${\displaystyle D^{+}A}$ ${\displaystyle L^{\text{rw}}:=D^{+}L=I-D^{+}A}$ ${\displaystyle L^{\text{rw}}}$ ${\displaystyle LD^{+}=I-AD^{+}}$ ${\displaystyle AD^{+}}$

有向グラフの非対称隣接行列の場合、正規化のために入次数または出次数も選択する必要があります。

隣接行列	出次数行列	出次数左正規化ラプラシアン	入次行列	入次右正規化ラプラシアン
${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&0&0\\0&1&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1/2&-1/2\\0&1&-1\\-1&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&-1/2\\0&1&-1/2\\-1&0&1\\\end{array}}\right)}$

行和がすべて0である左出次正規化ラプラシアンは右確率 に関連し、列和がすべて0である右入次正規化ラプラシアンは左確率を含みます ${\displaystyle D_{\text{out}}^{+}A}$ ${\displaystyle AD_{\text{in}}^{+}}$

重み付きエッジを持つグラフの定義

アプリケーションでよく使用される重み付きエッジを持つグラフは、隣接行列によって定義するのが便利です。隣接行列では、エントリの値は数値であり、0と1に限定されなくなります。グラフの頂点がデータ ポイントを表すスペクトル クラスタリングとグラフベースの信号処理では、エッジの重みを、たとえば、データ ポイントのペア間の距離に反比例するものとして計算できます。その結果、すべての重みが非負になり、値が大きいほど非公式に、より類似したデータ ポイントのペアに対応します。データ ポイント間の相関と反相関を使用すると、当然、正と負の両方の重みが生じます。単純なグラフの定義のほとんどは、標準的な非負の重みの場合に簡単に拡張されますが、負の重みの場合は、特に正規化において、より注意が必要です。

ラプラシアン行列

ラプラシアン行列は次のように定義されます

${\displaystyle L=D-A,}$

ここで、Dは次数行列、Aはグラフの 隣接行列です

有向グラフの場合、次の例のように、アプリケーションに応じて 入次数または出次数のいずれかが使用されることがあります。

隣接行列	入次行列	入次数ラプラシアン	出次数行列	出次数ラプラシアン
${\textstyle \left({\begin{array}{rrr}0&1&2\\3&0&5\\6&7&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}9&0&0\\0&8&0\\0&0&7\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}9&-1&-2\\-3&8&-5\\-6&-7&7\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}3&0&0\\0&8&0\\0&0&13\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}3&-1&-2\\-3&8&-5\\-6&-7&13\\\end{array}}\right)}$

隣接行列の主対角線上の非ゼロの要素として現れるグラフの自己ループは許容されますが、グラフのラプラシアン値には影響しません

対称ラプラシアン（接続行列経由）

2次元スプリングシステム。

重み付き辺を持つグラフの場合、重み付き接続行列Bを定義し、それを用いて対応する対称ラプラシアンを として構築することができます。ここで説明するより簡潔な別のアプローチは、重みを接続性から分離することです。つまり、通常のグラフの場合と同様に接続行列を使用し続け、重みの値のみを保持する行列を導入します。バネシステムは、与えられた剛性と単位長さを持つバネのシステムを記述するために力学で使用されるこのモデルの一例であり、剛性の値はグラフの辺の重みの役割を果たします。 ${\displaystyle L=BB^{\textsf {T}}}$

そこで、頂点vと辺e（頂点とを繋ぐ、i >  j  ）について 、要素B _veを持つ重みなしの接続行列Bの定義を再利用し、次のように定義する。 ${\textstyle |v|\times |e|}$ ${\textstyle v_{i}}$ ${\textstyle v_{j}}$

${\displaystyle B_{ve}=\left\{{\begin{array}{rl}1,&{\text{if }}v=v_{i}\\-1,&{\text{if }}v=v_{j}\\0,&{\text{otherwise}}.\end{array}}\right.}$

ここで、辺の重みを含む対角行列Wも定義する。Bの定義における辺は技術的には有向であるが、その方向は任意であり、結果として、以下のように定義される 対称ラプラシアン行列Lが得られる。 ${\textstyle |e|\times |e|}$ ${\textstyle |v|\times |v|}$

${\displaystyle L=BWB^{\textsf {T}}}$

ここで、 Bの転置行列です。 ${\textstyle B^{\textsf {T}}}$

この構成は次の例で示されており、すべてのエッジに重み値iが割り当てられ、 ${\textstyle e_{i}}$ ${\textstyle i=1,2,3,4.}$

無向グラフ	接続行列	辺の重み	ラプラシアン行列
	${\textstyle \left({\begin{array}{rrrr}1&1&1&0\\-1&0&0&0\\0&-1&0&1\\0&0&-1&-1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}1&0&0&0\\0&2&0&0\\0&0&3&0\\0&0&0&4\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}6&-1&-2&-3\\-1&1&0&0\\-2&0&6&-4\\-3&0&-4&7\\\end{array}}\right)}$

有向グラフの対称ラプラシアン

単純なグラフと同様に、重み付き有向グラフのラプラシアン行列は定義により一般に非対称です。ラプラシアンを構築する前に、元の有向グラフを無向グラフに変換することで、対称性を維持できます。無向グラフの隣接行列は、例えば、次の例のように、 元の有向グラフの隣接行列とその転置行列の和として定義できます。 ${\displaystyle A}$ ${\displaystyle A^{T}}$

隣接行列	対称化隣接行列	対称ラプラシアン行列
${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}0&1&2\\1&0&1\\2&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}3&-1&-2\\-1&2&-1\\-2&-1&3\\\end{array}}\right)}$

ここで、 の 0 および 1 のエントリは、単純なグラフの場合の論理値ではなく数値として扱われ、結果の違いを説明しています。単純なグラフの場合、対称化されたグラフは、対称化された隣接行列が数値ではなく論理値のみを持つように単純である必要があります。たとえば、論理和は 1 v 1 = 1 ですが、数値の合計は 1 + 1 = 2 です。 ${\displaystyle A}$

あるいは、次の例のように、 入次数と出次数を使用して 2 つのラプラシアンから対称ラプラシアン行列を計算することもできます。

隣接行列	出次数行列	出次数ラプラシアン	入次行列	入次数ラプラシアン
${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&0&0\\0&1&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&-1&-1\\0&1&-1\\-1&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&-1\\0&1&-1\\-1&0&2\\\end{array}}\right)}$

転置された出力次数ラプラシアンと入力次数ラプラシアンの合計は対称ラプラシアン行列に等しくなります。

ラプラシアン行列の正規化

正規化の目的は、単純なグラフの場合と同様に、ラプラシアン行列の対角成分をすべて単位行列にし、非対角成分もそれに応じてスケーリングすることです。重み付きグラフでは、接続された辺の数が少ないが重みが大きいために頂点の次数が大きい場合もあれば、接続された辺の数が多く重みが単位の場合もあるため、頂点の次数が大きい場合もあります

グラフの自己ループ、つまり隣接行列の主対角線上の非ゼロのエントリは、グラフのラプラシアン値には影響しませんが、正規化係数の計算ではカウントする必要がある場合があります。

対称正規化ラプラシアン

対称正規化ラプラシアンは次のように定義されます

${\displaystyle L^{\text{sym}}:=(D^{+})^{1/2}L(D^{+})^{1/2}=I-(D^{+})^{1/2}A(D^{+})^{1/2},}$

ここで、Lは正規化されていないラプラシアン、Aは隣接行列、Dは次数行列、 はムーア・ペンローズ逆行列です。次数行列Dは対角行列なので、その逆平方根は、対角要素がDの対角要素の平方根の逆数である対角行列です。すべての辺の重みが非負の場合、すべての次数値も自動的に非負になり、すべての次数値は一意の正の平方根を持ちます。ゼロ除算を避けるため、次の例のように、次数ゼロの頂点は正規化のプロセスから除外されます。 ${\displaystyle D^{+}}$ ${\textstyle (D^{+})^{1/2}}$

隣接行列	入次行列	次数内正規化ラプラシアン	出次数行列	出次数正規化ラプラシアン
${\textstyle \left({\begin{array}{rrr}0&1&0\\4&0&0\\0&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&4&0\\0&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1/2&0\\-2&1&0\\0&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}4&0&0\\0&1&0\\0&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1/2&0\\-2&1&0\\0&0&0\\\end{array}}\right)}$

対称正規化ラプラシアンは、隣接行列Aが対称で、Dの対角要素が非負である場合にのみ対称行列となります。 この場合、対称正規化ラプラシアンという用語を使用できます

対称正規化ラプラシアン行列は次のようにも書ける。

${\displaystyle L^{\text{sym}}:=(D^{+})^{1/2}L(D^{+})^{1/2}=(D^{+})^{1/2}BWB^{\textsf {T}}(D^{+})^{1/2}=SS^{T}}$

重みなしの接続行列Bと、エッジの重みを含む対角行列Wを使用して、行が頂点でインデックスされ、列が G のエッジでインデックスされる新しい重み付き接続行列を定義します。エッジ e = {u、v}に対応する各列には、 uに対応する行にエントリが 1 つ、vに対応する行にエントリが 1 つあり、それ以外の場所にはエントリが 0 個あります。 ${\textstyle |v|\times |e|}$ ${\textstyle |e|\times |e|}$ ${\textstyle |v|\times |e|}$ ${\textstyle S=(D^{+})^{1/2}BW^{{1}/{2}}}$ ${\textstyle {\frac {1}{\sqrt {d_{u}}}}}$ ${\textstyle -{\frac {1}{\sqrt {d_{v}}}}}$

ランダムウォーク正規化ラプラシアン

ランダムウォーク正規化ラプラシアンは次のように定義される。

${\displaystyle L^{\text{rw}}:=D^{+}L=I-D^{+}A}$

ここで、Dは次数行列である。次数行列Dは対角行列であるため、その逆行列は単純に対角行列として定義され、その対角要素はDの対応する対角要素の逆数となる。孤立した頂点（次数0の頂点）については、対応する要素を0に設定するのが一般的である。の行列要素は次のように与えられる 。 ${\textstyle D^{+}}$ ${\textstyle L_{i,i}^{\text{rw}}}$ ${\textstyle L^{\text{rw}}}$

${\displaystyle L_{i,j}^{\text{rw}}:={\begin{cases}1&{\mbox{if}}\ i=j\ {\mbox{and}}\ \deg(v_{i})\neq 0\\-{\frac {1}{\deg(v_{i})}}&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}}$

ランダムウォーク正規化ラプラシアンという名前は、この行列が であるという事実に由来しています。ここでは、非負の重みを仮定した、グラフ上のランダムウォーカーの遷移行列です。例えば、i番目の標準基底ベクトルを とします。すると、 は、頂点 から1歩進んだ後のランダムウォーカーの位置の分布を表す確率ベクトル、つまり となります。より一般的には、ベクトル がグラフの頂点におけるランダムウォーカーの位置の確率分布である場合、 は、ステップ後のランダムウォーカーの確率分布です。 ${\textstyle L^{\text{rw}}=I-P}$ ${\textstyle P=D^{+}A}$ ${\textstyle e_{i}}$ ${\textstyle x=e_{i}P}$ ${\textstyle i}$ ${\textstyle x_{j}=\mathbb {P} \left(v_{i}\to v_{j}\right)}$ ${\textstyle x}$ ${\textstyle x'=xP^{t}}$ ${\textstyle t}$

ランダムウォーク正規化ラプラシアンは、正規化がラプラシアンに左辺の正規化行列を乗算することで行われるため、左正規化ラプラシアンとも呼ばれます。すべての重みが非負であると仮定すると、 は右確率的であるため、各行の和はゼロになります。 ${\displaystyle L^{\text{rw}}:=D^{+}L}$ ${\displaystyle D^{+}}$ ${\displaystyle P=D^{+}A}$

あまり一般的ではない右正規化ラプラシアンでは、 は左確率的であるため、各列の合計はゼロになります。 ${\displaystyle LD^{+}=I-AD^{+}}$ ${\displaystyle AD^{+}}$

有向グラフの非対称隣接行列の場合、正規化のために入次数または出次数も選択する必要があります。

隣接行列	出次数行列	出次数左正規化ラプラシアン	入次行列	入次右正規化ラプラシアン
${\textstyle \left({\begin{array}{rrr}0&1&0\\0&0&2\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&2&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&0\\0&1&-1\\-1&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&0\\0&1&-1\\-1&0&1\\\end{array}}\right)}$

行和がすべて0である左出次正規化ラプラシアンは右確率 に関連し、列和がすべて0である右入次正規化ラプラシアンは左確率を含みます ${\displaystyle D_{\text{out}}^{+}A}$ ${\displaystyle AD_{\text{in}}^{+}}$

負の重み

負の重みは正規化においていくつかの課題を提示します。

• 負の重みが存在すると、孤立していない頂点の行合計および／または列合計が自然にゼロになる可能性があります。正の重みの行合計が大きく、負の重みの行合計も同様に大きく、合計がゼロになる頂点は重いノードと見なすことができ、両方の大きな値がスケーリングされますが、対角要素は孤立した頂点と同様にゼロのままです
• 負の重みは負の行合計および/または列合計を与える可能性があり、その結果、正規化されていないラプラシアン行列の対応する対角要素は負になり、対称正規化に必要な正の平方根は存在しなくなります。
• 正規化の目的で行合計および/または列合計の絶対値を取るという議論が行われ、可能な値 -1 が正規化されたラプラシアン行列の主対角線の正当な単位エントリとして扱われることになります。

性質

（無向）グラフGとその固有値を持つラプラシアン行列Lについて： ${\textstyle \lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{n-1}}$

• Lは対称です。
• Lは半正定値行列である（つまり、すべての に対して である）。これは、ラプラシアンが対称かつ対角優勢であるという事実からわかる。 ${\textstyle \lambda _{i}\geq 0}$ ${\textstyle i}$
• LはM 行列です(非対角要素は非正ですが、固有値の実部は非負です)。
• Lの行と列の和はすべてゼロです。実際、和において、各隣接頂点の次数は「-1」で合計されます。
• その結果、ベクトルがを満たすため、これはラプラシアン行列が特異であることも意味します。 ${\textstyle \lambda _{0}=0}$ ${\textstyle \mathbf {v} _{0}=(1,1,\dots ,1)}$ ${\textstyle L\mathbf {v} _{0}=\mathbf {0} .}$
• グラフ内の接続されたコンポーネントの数は、ラプラシアンのヌル空間の次元と0 固有値の代数的重複度です。
• Lの最小の非ゼロ固有値はスペクトルギャップと呼ばれます。
• Lの 2 番目に小さい固有値(ゼロの場合もある) は、Gの代数的接続性(またはフィードラー値)であり、グラフの最もスパースなカットを近似します。
• ラプラシアンは、関数 の n 次元ベクトル空間上の演算子です。ここで、 は G の頂点集合、 です。 ${\textstyle f:V\to \mathbb {R} }$ ${\textstyle V}$ ${\textstyle n=|V|}$
• G がk 正則の場合、正規化されたラプラシアンは です。ここで、A は隣接行列、I は単位行列です。 ${\textstyle {\mathcal {L}}={\tfrac {1}{k}}L=I-{\tfrac {1}{k}}A}$
• 複数の接続されたコンポーネントを持つグラフの場合、Lはブロック対角行列です。ここで、各ブロックは各コンポーネントのそれぞれのラプラシアン行列であり、頂点を並べ替えた後の可能性があります (つまり、Lはブロック対角行列と順列類似です)。
• ラプラシアン行列Lのトレースは、考慮するグラフのエッジの数に等しくなります。 ${\textstyle 2m}$ ${\textstyle m}$
• ここで、単位ノルムの固有ベクトルとそれに対応する固有値を持つ の固有分解を考えます。 ${\textstyle L}$ ${\textstyle \mathbf {v} _{i}}$ ${\textstyle \lambda _{i}}$

${\displaystyle {\begin{aligned}\lambda _{i}&=\mathbf {v} _{i}^{\textsf {T}}L\mathbf {v} _{i}\\&=\mathbf {v} _{i}^{\textsf {T}}M^{\textsf {T}}M\mathbf {v} _{i}\\&=\left(M\mathbf {v} _{i}\right)^{\textsf {T}}\left(M\mathbf {v} _{i}\right).\\\end{aligned}}}$

はベクトルとそれ自身の内積として表すことができるため、となり、 の固有値はすべて非負になります。 ${\textstyle \lambda _{i}}$ ${\textstyle M\mathbf {v} _{i}}$ ${\textstyle \lambda _{i}\geq 0}$ ${\textstyle L}$

• 正規化対称ラプラシアンのすべての固有値は 0 = μ ₀ ≤ … ≤ μ _n−1 ≤ 2 を満たす。これらの固有値（正規化ラプラシアンのスペクトルとして知られる）は、一般的なグラフの他のグラフ不変量とよく関連している。^{[ 1 ]}

• 次のことを確認できます:

${\displaystyle L^{\text{rw}}=I-D^{-{\frac {1}{2}}}\left(I-L^{\text{sym}}\right)D^{\frac {1}{2}}}$、

つまり、正規化ラプラシアン に類似しています。このため、が一般に対称でなくても、 は実固有値を持ちます。これは、正規化対称ラプラシアン の固有値と全く同じです。 ${\textstyle L^{\text{rw}}}$ ${\textstyle L^{\text{sym}}}$ ${\textstyle L^{\text{rw}}}$ ${\textstyle L^{\text{sym}}}$

連続ラプラス演算子を近似する離散ラプラス演算子としての解釈

グラフのラプラシアン行列は、さらに、有限差分法によって得られる負の連続ラプラシアン演算子を近似するグラフ上の負の離散ラプラシアン演算子の行列形式として見ることができます。（離散ポアソン方程式を参照）^{[ 2 ]}この解釈では、すべてのグラフ頂点がグリッドポイントとして扱われます。頂点のローカル接続性により、このグリッドポイントでの有限差分近似ステンシルが決定され、グリッドサイズは常にすべてのエッジに対して1であり、どのグリッドポイントにも制約はなく、これは同次ノイマン境界条件、つまり自由境界の場合に対応します。このような解釈により、例えば、ラプラシアン行列を無限数の頂点とエッジを持つグラフの場合に一般化することができ、無限サイズのラプラシアン行列が得られます。

ラプラシアン行列の一般化と拡張

一般化ラプラシアン

一般化ラプラシアンは次のように定義されます: ^{[ 3 ]} ${\displaystyle Q}$

${\displaystyle {\begin{cases}Q_{i,j}<0&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\Q_{i,j}=0&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is not adjacent to }}v_{j}\\{\mbox{any number}}&{\mbox{otherwise}}.\end{cases}}}$

通常のラプラシアンは一般化ラプラシアンであることに注意してください。

交流回路のアドミタンス行列

グラフのラプラシアンは、電気回路網をモデル化するために初めて導入されました。交流（AC）電気回路網では、実数値の抵抗が複素数値のインピーダンスに置き換えられます。辺（i、j）の重みは、慣例により、iとjの間に位置するインピーダンスの逆数を減算した値となります。このような回路網のモデルでは、隣接行列の要素は複素数ですが、キルヒホッフ行列はエルミート行列ではなく対称行列のままです。このような行列は通常、「ラプラシアン」ではなく「アドミタンス行列」と呼ばれ、 と表記されます。これは、複素対称行列を生み出す数少ない応用例の1つです。 ${\displaystyle Y}$

隣接行列	重み付き次数行列	アドミタンス行列
${\textstyle \left({\begin{array}{rrrr}0&i&0&0\\i&0&1-2i&0\\0&1-2i&0&1\\0&0&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}i&0&0&0\\0&1-i&0&0\\0&0&2-2i&0\\0&0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}-i&i&0&0\\i&-1+i&1-2i&0\\0&1-2i&-2+2i&1\\0&0&1&-1\\\end{array}}\right)}$

磁気ラプラシアン

隣接行列の要素が複素数値であり、ラプラシアンがエルミート行列になる状況も存在します。実重みを持つ有向グラフの磁気ラプラシアンは、対称化ラプラシアンの実対称行列と、複素要素 を持つエルミート位相行列とのアダマール積 として構成されます。 ${\displaystyle w_{ij}}$

${\displaystyle \gamma _{q}(i,j)=e^{i2\pi q(w_{ij}-w_{ji})}}$

これはエッジの方向を複素平面上の位相に符号化する。量子物理学の文脈では、磁気ラプラシアンは、磁場の作用を受けるグラフ上の自由荷電粒子の現象を記述する演算子として解釈することができ、そのパラメータは 電荷と呼ばれる。^{[ 4 ]} 次の例では： ${\displaystyle q}$ ${\displaystyle q=1/4}$

隣接行列	対称化ラプラシアン	位相行列	磁気ラプラシアン
${\textstyle \left({\begin{array}{rrrr}0&1&0&0\\1&0&1&0\\0&0&0&0\\0&0&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}2&-2&0&0\\-2&3&-1&0\\0&-1&2&-1\\0&0&-1&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}1&1&1&1\\1&1&i&1\\1&-i&1&-i\\1&1&i&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}2&-2&0&0\\-2&3&-i&0\\0&i&2&i\\0&0&-i&1\\\end{array}}\right)}$

変形ラプラシアン

変形ラプラシアンは一般的に次のように定義されます

${\displaystyle \Delta (s)=I-sA+s^{2}(D-I)}$

ここで、Iは単位行列、Aは隣接行列、Dは次数行列、sは（複素数値）数である。^{[ 5 ]}標準ラプラシアンはちょうどであり、は符号なしラプラシアンである。 ${\textstyle \Delta (1)}$ ${\textstyle \Delta (-1)=D+A}$

符号なしラプラシアン

符号なしラプラシアンは次のように定義されます

${\displaystyle Q=D+A}$

ここで は次数行列、 は隣接行列である。^{[ 6 ]}符号付きラプラシアンと同様に、符号なしラプラシアンも次のように因数分解できるため、半正定値である。 ${\displaystyle D}$ ${\displaystyle A}$ ${\displaystyle L}$ ${\displaystyle Q}$

${\displaystyle Q=RR^{\textsf {T}}}$

ここで、は接続行列である。が0-固有ベクトルを持つのは、二部連結成分（孤立頂点は二部連結成分）を持つ場合のみである。これは次のように表される。 ${\textstyle R}$ ${\displaystyle Q}$

${\displaystyle \mathbf {x} ^{\textsf {T}}Q\mathbf {x} =\mathbf {x} ^{\textsf {T}}RR^{\textsf {T}}\mathbf {x} \implies R^{\textsf {T}}\mathbf {x} =\mathbf {0} .}$

これには、グラフに二部接続コンポーネントがある場合に限り、次のような 解があります。 ${\displaystyle \mathbf {x} \neq \mathbf {0} }$

有向多重グラフ

ラプラシアン行列の類似物は、有向多重グラフに対して定義できます。^{[ 7 ]}この場合、ラプラシアン行列Lは次のように定義されます

${\displaystyle L=D-A}$

ここで、Dは対角行列であり、 D _{i , i は}頂点iの出次数に等しく、Aは行列であり、 A _{i , j}はiからjへの辺の数(ループを含む) に等しくなります。

オープンソースソフトウェアの実装

• SciPy ^{[ 8 ]}
• ネットワークX ^{[ 9 ]}
• ジュリア^{[ 10 ]}

アプリケーションソフトウェア

• scikit-learnスペクトルクラスタリング^{[ 11 ]}
• PyGSP: Pythonによるグラフ信号処理^{[ 12 ]}
• ロックマン：数百万点の多様体学習^{[ 13 ]}
• スムースG ^{[ 14 ]}
• 動的グラフのラプラシアン変化点検出（KDD 2020）^{[ 15 ]}
• LaplacianOpt（重み付きグラフのラプラシアンの2次固有値を最大化するJuliaパッケージ）^{[ 16 ]}
• LigMG（大規模不規則グラフマルチグリッド）^{[ 17 ]}
• ラプラシアン.jl ^{[ 18 ]}

参照

• 剛性マトリックス
• 抵抗距離
• 遷移速度マトリックス
• 有限重み付きグラフ上の微積分
• グラフフーリエ変換

参考文献

1. Chung, Fan (1997) [1992].スペクトルグラフ理論. アメリカ数学会. ISBN 978-0821803158。
2. Smola, Alexander J.; Kondor, Risi (2003)、「カーネルとグラフ上の正則化」、学習理論とカーネルマシン：第16回学習理論年次会議および第7回カーネルワークショップ、COLT/Kernel 2003、ワシントンD.C.、米国、2003年8月24～27日、議事録、Lecture Notes in Computer Science、第2777巻、Springer、pp.  144～ 158、CiteSeerX 10.1.1.3.7020、doi : 10.1007/978-3-540-45167-9_12、ISBN  978-3-540-40720-1。
3. Godsil, C.; Royle, G. (2001).代数的グラフ理論, Graduate Texts in Mathematics . Springer-Verlag
4. 古谷 聡; 柴原 俊樹; 秋山 光明; 波戸 邦夫; 相田 正樹 (2020).エルミートラプラシアンに基づく有向グラフのグラフ信号処理(PDF) . ECML PKDD 2019: データベースにおける機械学習と知識発見. pp.  447– 463. doi : 10.1007/978-3-030-46150-8_27 .
5. モルビディ、F. (2013)。「変形コンセンサスプロトコル」(PDF)。オートマチック。49 (10): 3049–3055。土井: 10.1016/j.automatica.2013.07.006。S2CID 205767404。 
6. Cvetković, Dragoš; Simić, Slobodan K. (2010). 「符号なしラプラシアンに基づくグラフのスペクトル理論に向けて III」 . Applicable Analysis and Discrete Mathematics . 4 (1): 156– 166. doi : 10.2298/AADM1000001C . ISSN 1452-8630 . JSTOR 43671298 .  
7. Chaiken, S.; Kleitman, D. (1978). 「行列木定理」 . Journal of Combinatorial Theory, Series A. 24 ( 3): 377– 381. doi : 10.1016/0097-3165(78)90067-5 . ISSN 0097-3165 . 
8. “SciPy” . GitHub . 2023年10月4日.
9. "NetworkX" . GitHub . 2023年10月4日.
10. “Julia” . GitHub . 2023年10月4日.
11. 「2.3. クラスタリング」。
12. 「PyGSP: Pythonでのグラフ信号処理」GitHub。2022年3月23日。
13. 「Megaman: 数百万点のポイントのための多様体学習」 GitHub 。 2022年3月14日。
14. "SmoothG" . GitHub . 2020年9月17日.
15. 「KDD 2020で論文を発表」。2020年7月2日。
16. “Harshangrjn/LaplacianOpt.jl” . GitHub . 2022年2月2日.
17. 「LigMG（Large Irregular Graph MultiGrid） - 大規模不規則グラフ用の分散メモリグラフラプラシアンソルバー」。GitHub 。 2022年1月5日。
18. “Laplacians.jl” . GitHub . 2022年3月11日.

「 https://en.wikipedia.org/w/index.php?title=ラプラシアン行列&oldid =1322577856」より取得