ラプラシアン行列

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

ラプラシアン行列は、グラフの多くの有用な特性と関係しています。キルヒホッフの定理とともに、特定のグラフの全域木の数を計算するために使用できます。グラフの最も疎なカットは、チーガーの不等式によって確立されているように、フィードラーベクトル（グラフラプラシアンの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 nearby to }}v_{j}\\0&{\mbox{otherwise}},\end{cases}}}$

または、行列

${\displaystyle L=DA,}$

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

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

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

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

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

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

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

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

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

大きな次数を持つ頂点 (重いノードとも呼ばれる) は、ラプラシアン行列の大きな対角エントリとなり、行列の特性を左右します。正規化は、ラプラシアン行列のエントリを頂点の次数で割ることで、このような頂点の影響を他の頂点の影響とより均等にすることを目的とします。ゼロ除算を回避するために、ゼロ次数の孤立した頂点は正規化のプロセスから除外されます。

対称正規化ラプラシアン行列は次のように定義される: ^[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}}}$

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

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

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

${\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^{+}}$。

隣接行列が対称である場合、左または右の正規化されたラプラシアン行列は対称ではありません。ただし、すべての頂点が孤立しているという単純なケースは除きます。たとえば、

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

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

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

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

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

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

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

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

隣接行列の主対角線上の非ゼロのエントリによって現れるグラフ自己ループは許可されますが、グラフのラプラシアン値には影響しません。

重み付きエッジを持つグラフの場合、重み付き接続行列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.}$

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

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

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

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

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

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

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

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

対称正規化ラプラシアンは、隣接行列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^{+}}$

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

行の合計がすべて 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の代数的接続性(またはFiedler 値)であり、グラフの最もスパースなカットを近似します。
• ラプラシアンは、関数 の 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}$

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

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

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

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

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

ここで、は接続行列です。は、2部連結成分（孤立した頂点は2部連結成分）を持つ場合にのみ、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への辺の数(ループを含む) に等しい。

• サイパイ^[8]
• ネットワークX ^[9]
• ジュリア^[10]

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

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