The Monge--Ampère equation on graphs

技術要約：グラフ上のモンジュ・アンペール方程式

問題提起
本論文は、凸幾何学や最適輸送において中心的な役割を果たす完全非線形楕円作用素であるモンジュ・アンペール作用素を、有限グラフの離散設定へと拡張するという課題に取り組んでいる。この研究は、現在のグラフベースの半教師あり学習手法が主にグラフ・ラプラシアンに依存しているという限界によって動機付けられている。ラプラシアンに基づく手法（調和拡張）は計算効率が高いものの、本質的に拡散的であり、すべてのグラフ方向に対して等方的に情報を平均化してしまう。これは、鋭い遷移のオーバースムーシング（過度な平滑化）や、ラベルが少ない領域での退化を引き起こしやすい。著者らは、データの異方的な構造を尊重する非線形な代替案を提案しており、等方的な平滑化とは根本的に異なる、幾何学に敏感な補間メカニズムを提供することを目指して、有限グラフ上のモンジュ・アンペール方程式を定式化している。

手法と定義
グラフ上のモンジュ・アンペール作用素を定義する上での核心的な困難は、グラフ上に標準的なヘッセ行列が存在しないことである。著者らは、関数の値の局所的な順序統計量を用いて、離散的なヘッセ固有値 $\lambda_i[u](x)$ と呼ばれる離散的な類似物を定義することで、この問題を解決している。

1. 離散固有値: 頂点 $x$ の隣接頂点の数が偶数 $n = |N_x|$ であるとき、隣接する頂点の値を $u(y_1) \leq \dots \leq u(y_n)$ と順序付ける。離散固有値は以下のように定義される：
   $$\lambda_i[u](x) = \frac{u(y_{2i-1}) + u(y_{2i})}{2} - u(x), \quad i = 1, \dots, n/2.$$
   これらの量は、順序付けられた方向的な二次の増分を表す。グラフ・ラプラシアンはこれら固有値のトレース（跡）であることが示されている（$L[u] = \frac{2}{n} \sum \lambda_i$）。一方、グラフ・モンジュ・アンペール作用素は、それらの積（行列式の類似物）として定義される：
   $$M[u](x) = \prod_{i=1}^{n/2} \lambda_i[u](x).$$

2. グラフ凸性: 関数 $u$ は、すべての $i$ に対して $\lambda_i[u](x) \geq 0$ であるとき、「グラフ凸」であると定義される。厳密なグラフ凸性は、作用素が楕円領域にあることを保証する。

3. ベルマン定式化: 解析を容易にするため、積の形式である方程式 $M[u](x) = f(x)$ を、算術・幾何平均不等式を用いてベルマン型の形式へと再定式化する：
   $$u(x) = \inf_{\alpha \in A_{n/2}} \left( \frac{\sum \alpha_i H_i[u](x) - \frac{n}{2} f(x)^{2/n}}{\sum \alpha_i} \right),$$
   ここで、$H_i[u](x)$ は順序統計量作用素であり、$A_{n/2}$ は積が1となる正の重みの集合である。この定式化により、作用素の単調性が透明になる。

主な貢献と理論的結果

• 比較原理と一意性: 著者らは、非同次ディリクレ問題における劣解（subsolutions）と優解（supersolutions）に対する比較原理を確立している。重要な技術的ステップは、2つの関数がある点で一致し、かつそれらの順序統計量作用素が一致する場合、それらは近傍全体でも一致しなければならないことを証明することである。これにより、厳密なグラフ凸解の一意性が導かれる。

• ペロンの方法による存在性: 存在性はペロンの方法を用いて調査されている。著者らは、線形ラプラシアンの場合とは異なり、非同次問題に対する解の存在はグラフの組合せ幾何学に敏感であることを特定した。具体的には、極限作用素のための障壁（バリア）が存在するための必要十分条件は、ラベルのない頂点によって誘導される部分グラフが「1次退化（1-degenerate）」なグラフ（具体的には森林：forest）であることである。もしラベルのない部分グラフが閉じた構造（例えば、各ノードが集合内の少なくとも2つの隣接点を持つようなサイクル）を含む場合、解が存在しない可能性がある。

• 同次の場合: 同次方程式 $M[u]=0$ については、問題は $\lambda_1[u] = 0$ （または $u = H_1[u]$）という条件に帰着する。これは最小の離散固有値に基づく非線形補間規則を表している。著者らは、「到達可能性条件」（ラベルのない頂点の空でない部分集合が、少なくとも2つの隣接点を保持する形で閉じられていないこと）の下で、この場合の比較原理と一意性を証明している。この条件は、ラベルのない部分グラフが森林である場合に満たされる。

• Woven Forests（織られた森林）: 非同次問題の存在を保証するために、論文では「woven forests」を導入している。これらは、森林 $F$ に境界頂点 $O$ を追加して、すべての内部頂点の次数が固定値 $n$ になるように構成されたグラフである。この構成により、必要な1次退化条件が満たされることが保証される。

数値スキームと実験
論文では、ベルマン定式化に着想を得た不動点反復スキームを提案している：

• 非同次スキーム: ベルマン写像から導出されたスカラー非線形方程式を解くことに基づく更新。
• 同次スキーム: 残差 $u - H_1[u]$ によって駆動されるより単純な更新。
• 収束: 著者らは、グラフのレイヤーを「剥離（peeling）」していく手順によって構築された障壁関数を用いた加重ノルムを用いることで、これらのスキームがwoven forests上で一意な解に収束することを証明している。

数値実験では、2次元領域（単位球を近似）におけるモンジュ・アンペール法とグラフ・ラプラシアン正則化を比較している。結果は、ラプラシアン解が平坦になる傾向があるのに対し、モンジュ・アンペール法は、特に放射状および一様な樹状構造において、連続解の放物線状の形状をより良く近似することを示している。この手法は、いくつかのテストケースにおいて、離散的な $\ell_2$ 誤差が低いことを示している。

意義と主張
本論文は、機械学習のための非線形偏微分方程式のツールキットに「行列式型のグラフ作用素」を加えるものであると主張している。その主な意義は以下の通りである：

1. 理論的枠組み: 比較原理、一意性、およびグラフのトポロジーに結びついた存在条件を含む、有限グラフ上のモンジュ・アンペール方程式に関する初の厳密な解析を提供したこと。
2. 非線形性: ラプラシアン手法の拡散的な性質とは対照的に、異方的なデータ構造に敏感な半教師あり学習のメカニズムを提供したこと。
3. 計算の実行可能性: 完全に非線形な作用素であるにもかかわらず、特定のグラフクラス（woven forests）において、収束が証明された効率的な不動点スキームを構築できることを示したこと。

著者らは、現在の正規化はグラフに依存しているため、数値実験は厳密な連続体への収束ではなく、定性的な形状の評価を行っているに過ぎないと謙虚に述べている。今後の課題として、幾何学的に一貫したスケーリングと意味のある連続体極限を実現するために、正の辺の重みを組み込むことを挙げている。