有限重み付きグラフの微積分

数学において、有限重み付きグラフ上の微積分とは、有限個の頂点と辺に関連付けられた重みを持つグラフの頂点集合を定義域とする関数の離散微積分である。これには、ラプラシアンの離散バージョンとしてのグラフラプラシアン（または離散ラプラス演算子）などの微積分における微分演算子に類似したグラフ上の離散演算子の定式化、およびこれらの演算子を使用してグラフ上の微分方程式、差分方程式、または変分モデルを定式化することが含まれます。これらは、偏微分方程式または連続変分モデルの離散バージョンとして解釈できます。このような方程式やモデルは、画像処理、機械学習、ネットワーク分析など、さまざまな研究分野で離散情報を数学的にモデル化、分析、および処理するための重要なツールです。

アプリケーションでは、有限重み付きグラフは、グラフの頂点によって有限個のエンティティを、これらのエンティティ間のペアワイズ関係をグラフのエッジによって、関係の重要性をエッジ重み関数によって表します。このようなグラフ上の微分方程式または差分方程式は、グラフの構造を利用して、画像セグメンテーション(頂点はピクセルを表し、重み付きエッジはムーア近傍またはより大きなウィンドウの比較に基づいてピクセルの類似性をエンコードします)、データ クラスタリング、データ分類、ソーシャル ネットワークでのコミュニティ検出(頂点はネットワークのユーザーを表し、エッジはユーザー間のリンクを表し、重み関数はユーザー間の相互作用の強度を示します) などのタスクに使用できます。

有限重み付きグラフの主な利点は、離散正規グリッド、格子グラフ、メッシュなどの高度に規則的な構造に制限されないため、不規則な相互関係を持つ抽象データを表すために適用できることです。

有限の重み付きグラフがユークリッド空間に幾何学的に埋め込まれている場合、つまりグラフの頂点がこの空間の点を表している場合、連続体設定における関連する非局所演算子の離散近似として解釈できます。

有限重み付き グラフは、 ${\displaystyle G}$${\displaystyle G=(V,E,w)}$

• ${\displaystyle V=\{x_{1},\dots ,x_{n}\},n\in \mathbb {N} }$はグラフの頂点またはノードとして表されるインデックスの有限集合である。
• ${\displaystyle E\subset V\times V}$頂点のサブセットを接続する（有向）グラフの辺の有限集合である。
• ${\displaystyle w\colon E\rightarrow \mathbb {R} }$グラフのエッジ上で定義されるエッジ重み関数です。

有向グラフでは、各辺に開始ノードと終了ノードがあります。無向グラフでは、すべての辺に対して辺が存在し、重み関数は対称である必要があります。つまり、 です。 ^[1]このページの残りの部分では、特に断りがない限り、グラフは無向であると仮定します。このページで紹介されているアイデアの多くは、有向グラフに一般化できます。^[1]${\displaystyle (x_{i},x_{j})\in E}$ ${\displaystyle x_{i}\in V}$ ${\displaystyle x_{j}\in V}$${\displaystyle (x_{i},x_{j})}$${\displaystyle (x_{j},x_{i})}$${\displaystyle w(x_{i},x_{j})=w(x_{j},x_{i})}$

エッジ重み関数は、 すべてのエッジに実数値を関連付けます。数学的理由とアプリケーション固有の理由の両方から、エッジの重み関数は厳密に正である必要があることが多く、このページでは特に明記しない限り、そのように想定されます。このページで紹介されている多くのアイデアを一般化して、負の重みを持つエッジを含めることは可能です。と設定することにより、エッジ重み関数の定義域を に拡張することが検討されることがあります (結果の関数は依然としてエッジ重み関数と呼ばれます) 。 ${\displaystyle w}$${\displaystyle (x_{i},x_{j})\in E}$${\displaystyle w(x_{i},x_{j})>0}$${\displaystyle V\times V}$${\displaystyle w(x_{i},x_{j})=0}$${\displaystyle (x_{i},x_{j})\not \in E}$

アプリケーションでは、各グラフ頂点は 通常、特定のデータ内の単一のエンティティを表します。たとえば、有限データセットの要素、画像内のピクセル、ソーシャルネットワーク内のユーザーなどです。グラフのエッジは 、2 つのエンティティ間の関係を表します。たとえば、ペアワイズ相互作用や、幾何学的近傍 (たとえば、画像内のピクセル) または別の機能の比較に基づく類似性などです。エッジの重みは、この関係の強さをエンコードします。最も一般的に使用される重み関数は、0 から 1 の間の値にマップされるように正規化されます。つまり、 です。 ${\displaystyle x\in V}$${\displaystyle w:E\rightarrow (0,1]}$

以下では、検討対象のグラフは自己ループや頂点間の複数のエッジなしで接続されているものと仮定します。これらの仮定は、多くのアプリケーションでは、切断されたグラフの各接続コンポーネントをそれ自体のグラフとして扱うことができ、(自己ループが存在する場合は非ゼロになる) の各出現は、(以下の微分グラフ演算子のセクションを参照) が消える別の要素が存在する場合に出現し、エッジの重みは複数のエッジの場合と同様の情報をエンコードできるため、ほとんど無害です。 ${\displaystyle w(x_{i},x_{i})}$${\displaystyle i=j}$

エッジが存在する場合、ノードはノードの隣接ノードです。表記上、この関係は と省略でき、「は の隣接ノードである」と読みます。それ以外の場合、 がの隣接ノードでない場合はと書きます。頂点の近傍は、単に近傍ノードの集合です。頂点の次数は、その近傍ノードの重み付けされたサイズです。 ${\displaystyle x_{j}\in V}$${\displaystyle x_{i}\in V}$${\displaystyle (x_{i},x_{j})\in E}$${\displaystyle x_{j}\sim x_{i}}$${\displaystyle x_{j}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle x_{i}}$${\displaystyle x_{j}\not \sim x_{i}}$ ${\displaystyle {\mathcal {N}}(x_{i})}$${\displaystyle x_{i}\in V}$${\displaystyle {\mathcal {N}}(x_{i}):=\{x_{j}\in V\colon x_{j}\sim x_{i}\}}$${\displaystyle x_{i}\in V}$

${\displaystyle \deg(x_{i}):=\sum _{j\,:\,x_{j}\sim x_{i}}w(x_{i},x_{j}).}$

が である特殊なケース（つまり、グラフが重み付けされていない）では、 となることに注意してください。 ${\displaystyle w\equiv 1}$${\displaystyle E}$${\displaystyle \deg(x_{i}):=|{\mathcal {N}}(x_{i})|}$

を（実）頂点関数の空間とします。は有限集合なので、任意の頂点関数は-次元ベクトル（ここで）として表すことができ、したがって頂点関数の空間は-次元ヒルベルト空間と同一視できます。 の内積は次のように定義されます。 ${\displaystyle {\mathcal {H}}(V):=\{f:V\rightarrow \mathbb {R} \}}$${\displaystyle V}$${\displaystyle f\in {\mathcal {H}}(V)}$${\displaystyle n}$${\displaystyle f\in \mathbb {R} ^{n}}$${\displaystyle n:=|V|}$${\displaystyle {\mathcal {H}}(V)}$${\displaystyle n}$${\displaystyle {\mathcal {H}}(V)\cong \mathbb {R} ^{n}}$${\displaystyle {\mathcal {H}}(V)}$

${\displaystyle \langle f,g\rangle _{{\mathcal {H}}(V)}:=\sum _{x_{i}\in V}f(x_{i})g(x_{i}),\quad \forall f,g\in {\mathcal {H}}(V).}$

さらに、任意の頂点関数の-ノルムと-ノルムは次のように定義されます。 ${\displaystyle f\in {\mathcal {H}}(V)}$${\displaystyle \ell_{p}}$${\displaystyle \ell _{\infty }}$${\displaystyle f}$

${\displaystyle \|f\|_{p}={\begin{cases}\left(\sum _{x_{i}\in V}|f(x_{i})|^{p}\right)^{\frac {1}{p}},&{\text{ }}1\leqslant p<\infty \ ,\\\max _{x_{i}\in V}|f(x_{i})|,&{\text{ }}p=\infty \ .\end{cases}}}$

-ノルムは内積によって誘導されます。 ${\displaystyle \ell_{2}}$

アプリケーションでは、頂点関数はノードの頂点にラベルを付けるのに役立ちます。たとえば、グラフベースのデータ クラスタリングでは、各ノードはデータ ポイントを表し、頂点関数はノードのクラスター メンバーシップを識別するために使用されます。

実頂点関数と同様に、実エッジ関数の空間 を導入することができます。任意のエッジ関数は有限のエッジ集合上で定義されるため、次元ベクトルとして表すことができます。ここで、です。したがって、エッジ関数の空間は次元ヒルベルト空間、つまりとして識別できます。 ${\displaystyle {\mathcal {H}}(E):=\{F:E\rightarrow \mathbb {R} \}}$${\displaystyle F}$${\displaystyle E}$${\displaystyle m}$${\displaystyle F\in \mathbb {R} ^{m}}$${\displaystyle m:=|E|}$${\displaystyle {\mathcal {H}}(E)}$${\displaystyle m}$${\displaystyle {\mathcal {H}}(E)\cong \mathbb {R} ^{m}}$

エッジ関数の特殊なケースの 1 つは、上記の基本定義のセクションで紹介した正規化されたエッジ重み関数 です。この関数と同様に、任意のエッジ関数は、 であればと設定することで簡単に に拡張できます。拡張されたエッジ関数の空間は依然として で表され、 と同一視できます( ) 。 ${\displaystyle w\colon E\rightarrow (0,1]}$${\displaystyle F}$${\displaystyle V\times V}$${\displaystyle F(x_{i},x_{j}):=0}$${\displaystyle (x_{i},x_{j})\not \in E}$${\displaystyle {\mathcal {H}}(E)}$${\displaystyle \mathbb {R} ^{m}}$${\displaystyle m:=|V|^{2}}$

の内積は次のように定義されます。 ${\displaystyle {\mathcal {H}}(E)}$

${\displaystyle \langle F,G\rangle _{{\mathcal {H}}(E)}:=\sum _{(x_{i},x_{j})\in E}F(x_{i},x_{j})G(x_{i},x_{j}),\quad \forall F,G\in {\mathcal {H}}(E).}$

さらに、任意のエッジ関数の-ノルムと-ノルムは次のように定義されます。 ${\displaystyle F\in {\mathcal {H}}(V)}$${\displaystyle \ell _{p}}$${\displaystyle \ell _{\infty }}$${\displaystyle F}$

${\displaystyle \|F\|_{p}={\begin{cases}\left(\sum _{(x_{i},x_{j})\in E}|F(x_{i},x_{j})|^{p}\right)^{\frac {1}{p}}&{\text{ for }}1\leqslant p<\infty \ ,\\\max _{(x_{i},x_{j})\in E}|F(x_{i},x_{j})|,&{\text{ for }}p=\infty \ .\end{cases}}}$

-ノルムは内積によって誘導されます。 ${\displaystyle \ell _{2}}$

となるようにエッジ セットを拡張すると、 となることが明らかになります。これは、各エッジ関数が線形行列演算子で識別できることを意味します。 ${\displaystyle E}$${\displaystyle E=V\times V}$${\displaystyle {\mathcal {H}}(E)\cong \mathbb {R} ^{n\times n}}$${\displaystyle {\mathcal {H}}(V)\cong \mathbb {R} ^{n}}$

有限重み付きグラフの計算における重要な要素は、連続体設定の標準微分演算子を有限重み付きグラフの離散設定で模倣することです。これにより、偏微分方程式や変分法などの数学でよく研究されているツールを変換し、グラフによって最もよくモデル化できるアプリケーションで使用できるようになります。この変換を可能にする基本概念は、グラフ勾配、つまりグラフ上の 1 階差分演算子です。これに基づいて、グラフ ラプラシアンなどの高階差分演算子を導出できます。

を有限重み付きグラフとし、を頂点関数とする。すると、有向辺に沿ったの重み付き差（または重み付きグラフ微分）は ${\displaystyle G=(V,E,w)}$${\displaystyle f\in {\mathcal {H}}(V)}$${\displaystyle f}$${\displaystyle (x_{i},x_{j})\in E}$

${\displaystyle \partial _{x_{j}}f(x_{i})\ :=\ {\sqrt {w(x_{i},x_{j})}}\left(f(x_{j})-f(x_{i})\right).}$

任意の加重差については、次の特性が当てはまります。

• ${\displaystyle \partial _{x_{i}}f(x_{j})=-\partial _{x_{j}}f(x_{i}),}$
• ${\displaystyle \partial _{x_{i}}f(x_{i})=0,}$
• ${\displaystyle f(x_{i})=f(x_{j})\Rightarrow \partial _{x_{j}}f(x_{i})=0.}$

重み付き差の概念に基づいて、グラフ上の重み付き勾配演算子を次のように 定義する。${\displaystyle \nabla _{w}:{\mathcal {H}}(V)\rightarrow {\mathcal {H}}(E)}$

${\displaystyle (\nabla _{w}f)(x_{i},x_{j})\ =\ \partial _{x_{j}}f(x_{i}).}$

これは線形演算子です。

頂点関数の局所的変化を頂点で測定するには、この辺関数の -ノルムを使用して、から始まるすべての有向辺へのの勾配を制限することができます。つまり、 ${\displaystyle f}$${\displaystyle x_{i}\in V}$${\displaystyle \nabla _{w}f}$${\displaystyle f}$${\displaystyle x_{i}}$${\displaystyle \ell _{p}}$

${\displaystyle \|(\nabla _{w}f)(x_{i},\cdot )\|_{\ell _{p}}={\begin{cases}\left(\sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})^{\frac {p}{2}}|f(x_{j})-f(x_{i})|^{p}\right)^{\frac {1}{p}}&{\text{ for }}1\leq p<\infty ,\\\max _{x_{j}\sim x_{i}}{\sqrt {w(x_{i},x_{j})}}|f(x_{j})-f(x_{i})|&{\text{ for }}p=\infty .\end{cases}}}$

重み付き勾配演算子の 随伴演算子は 、次のように定義される線形演算子である。${\displaystyle \nabla _{w}^{*}\colon {\mathcal {H}}(E)\rightarrow {\mathcal {H}}(V)}$

${\displaystyle \langle \nabla _{w}f,G\rangle _{{\mathcal {H}}(E)}=\langle f,\nabla _{w}^{*}G\rangle _{{\mathcal {H}}(V)}\quad {\text{ for all }}f\in {\mathcal {H}}(V),G\in {\mathcal {H}}(E).}$

対称的な重み関数を持つ無向グラフの場合、頂点における関数の随伴演算子は次の形式になります。 ${\displaystyle w\in {\mathcal {H}}(E)}$${\displaystyle \nabla _{w}^{*}}$${\displaystyle F\in {\mathcal {H}}(E)}$${\displaystyle x_{i}\in V}$

${\displaystyle \left(\nabla _{w}^{*}F\right)(x_{i})\ =\ {\frac {1}{2}}\sum _{x_{j}\sim x_{i}}{{\sqrt {w(x_{i},x_{j})}}(F(x_{j},x_{i})-F(x_{i},x_{j}))}.}$

次に、グラフ上の重み付き発散演算子を随伴演算子を介して として定義できます。グラフ上の発散は、グラフの各頂点におけるエッジ関数の純流出を測定します。 ${\displaystyle \operatorname {div} _{w}:=-\nabla _{w}^{*}}$

重み付きグラフ ラプラシアンは、 グラフ設定においてよく研究されている演算子です。連続体設定におけるラプラス演算子の関係を模倣して、重み付きグラフ ラプラシアンは任意の頂点に対して次のように導出できます。 ${\displaystyle \Delta _{w}:{\mathcal {H}}(V)\rightarrow {\mathcal {H}}(V)}$${\displaystyle \operatorname {div} (\nabla f)=\Delta f}$${\displaystyle x_{i}\in V}$

${\displaystyle {\begin{aligned}(\operatorname {div} _{w}(\nabla _{w}f))(x_{i})&={\frac {1}{2}}\sum _{x_{j}\sim x_{i}}{\sqrt {w(x_{i},x_{j})}}(\nabla _{w}f(x_{j},x_{i})-\nabla _{w}f(x_{i},x_{j}))\\&={\frac {1}{2}}\sum _{x_{j}\sim x_{i}}{\sqrt {w(x_{i},x_{j})}}\left({\sqrt {w(x_{i},x_{j})}}(f(x_{j})-f(x_{i}))-{\sqrt {w(x_{j},x_{i})}}(f(x_{i})-f(x_{j}))\right)\\&={\frac {1}{2}}\sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})(2f(x_{j})-2f(x_{i}))\\&=\sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})(f(x_{j})-f(x_{i}))\ =:\ (\Delta _{w}f)(x_{i}).\end{aligned}}}$

この表現では、 グラフが無向であり、対称的な重み関数を持っていると仮定する必要があることに注意してください。${\displaystyle G}$${\displaystyle w(x_{i},x_{j})=w(x_{j},x_{i})}$

連続-ラプラス演算子は、有限重み付きグラフにうまく変換できる 2 次微分演算子です。これにより、熱方程式などのさまざまな偏微分方程式をグラフ設定に変換できます。 ${\displaystyle p}$

グラフ上の1階偏差分演算子に基づいて、離散ディリクレエネルギー関数 の最小化によって重み付きグラフラプラス演算子の族を正式に導くことができる。${\displaystyle p}$ ${\displaystyle \Delta _{w,p}\colon {\mathcal {H}}(V)\rightarrow {\mathcal {H}}(V)}$${\displaystyle 1\leq p<\infty }$${\displaystyle p}$

${\displaystyle E(f)\ :=\ {\frac {1}{p}}\sum _{x_{i}\in V}\|\nabla _{w}f(x_{i},\cdot )\|_{\ell _{p}}^{p}.}$

エネルギー関数の最小化に必要な最適条件は、グラフ-ラプラシアンの次の定義につながります。 ${\displaystyle E}$${\displaystyle p}$

${\displaystyle (\Delta _{w,p}f)(x_{i})\ :=\ \sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})^{\frac {p}{2}}|f(x_{j})-f(x_{i})|^{p-2}(f(x_{j})-f(x_{i})).}$

グラフラプラス演算子はグラフ-ラプラス演算子の特殊なケースであることに注意する。つまり、 ${\displaystyle p}$${\displaystyle p=2}$

${\displaystyle (\Delta _{w,2}f)(x_{i})\ =\ (\Delta _{w}f)(x_{i})\ =\ \sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})(f(x_{j})-f(x_{i})).}$

有限重み付きグラフの計算は、画像処理、機械学習、ネットワーク分析など、さまざまな分野の幅広いアプリケーションで使用されています。有限重み付きグラフが使用されているタスクの一覧は次のとおりです (これらに限定されません)。

• 画像ノイズ除去^{[2] [3]}
• 画像セグメンテーション^[4]
• 画像修復^{[2] [5]}
• 断層再構成^[6]
• 逆問題^[7]
• データクラスタリング^[8]
• 点群圧縮^[9]
• 手書き数字認識^[3]

• グラフ上の位相場モデル

1. ^無向グラフのわずかに異なる定義も使用されていることに注意してください。この定義では、無向エッジは、 と の順序付きペアのペアではなく、2 セット(2 つの異なる要素を持つセット)と見なされます。ここでは、 のエッジ関数 (エッジ関数の空間に関するセクションを参照)が と で異なる値をとることができるようにする必要があるため、後者の記述が必要です。${\displaystyle \{x_{i},x_{j}\}}$ ${\displaystyle (x_{i},x_{j})}$${\displaystyle (x_{j},x_{i})}$${\displaystyle {\mathcal {H}}(E)}$${\displaystyle (x_{i},x_{j})}$${\displaystyle (x_{j},x_{i})}$