ラプラシアン行列

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

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

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

単純なグラフの定義

ラプラシアン行列

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

L_{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{if}}\ i=j\\-1&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{はv_{j}に隣接している\\0&{\mbox{otherwise}},\end{cases}}

あるいは、行列

L=DA,

ここで、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&1&0&1&0&1\\0&0&1&0&1&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}}$

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|}$

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とは対照的に、いわゆるエッジベースのラプラシアンを定義します $B^{\textsf {T}}B$ ${\textstyle |e|\times |e|}$

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

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

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

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

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

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

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)}$

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

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

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

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

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}}

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

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)}$

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

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

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

ラプラシアン行列

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

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)}$

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

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

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

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

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|}$

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)}$

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

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

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

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

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

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

対称正規化ラプラシアン

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

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

ここで、Lは正規化されていないラプラシアン、Aは隣接行列、Dは次数行列、はムーア・ペンローズ逆行列です。次数行列Dは対角行列なので、その逆平方根は、対角要素がDの対角要素の平方根の逆数である対角行列です。すべての辺の重みが非負の場合、すべての次数値も自動的に非負になり、すべての次数値は一意の正の平方根を持ちます。ゼロ除算を避けるため、次の例のように、次数ゼロの頂点は正規化のプロセスから除外されます。 $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の対角要素が非負である場合にのみ対称行列となります。この場合、対称正規化ラプラシアンという用語を使用できます

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

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}}}}}$

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

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

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}}}$

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}$

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

あまり一般的ではない右正規化ラプラシアンでは、は左確率的であるため、各列の合計はゼロになります。 $LD^{+}=I-AD^{+}$ $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である右入次正規化ラプラシアンは左確率を含みます $D_{\text{out}}^{+}A$ $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}}$

{\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 ]}

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

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}}}$

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

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

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

一般化ラプラシアン

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

{\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つです。 $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)}$

磁気ラプラシアン

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

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

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