The Monge--Ampère equation on graphs

Technical Summary: The Monge–Ampère Equation on Graphs

Problem Statement
The paper addresses the challenge of extending the Monge–Ampère operator, a fully nonlinear elliptic operator central to convex geometry and optimal transport, to the discrete setting of finite graphs. This work is motivated by the limitations of current graph-based semi-supervised learning methods, which predominantly rely on the graph Laplacian. While Laplacian-based approaches (harmonic extension) are computationally efficient, they are intrinsically diffusive, averaging information isotropically across all graph directions. This often leads to oversmoothing of sharp transitions and degeneracies in low-label regimes. The authors propose a nonlinear alternative that respects the anisotropic structure of data by formulating a Monge–Ampère equation on finite graphs, aiming to provide a geometry-sensitive mechanism for interpolation that differs fundamentally from isotropic smoothing.

Methodology and Definitions
The core difficulty in defining a graph Monge–Ampère operator is the absence of a canonical Hessian on a graph. The authors resolve this by defining discrete analogs of Hessian eigenvalues, denoted $\lambda_i[u](x)$, using local order statistics of function values at neighboring vertices.

1. Discrete Eigenvalues: For a vertex $x$ with an even number of neighbors $n = |N_x|$, the neighbors' values are ordered $u(y_1) \leq \dots \leq u(y_n)$. The discrete eigenvalues are defined as:
   $$\lambda_i[u](x) = \frac{u(y_{2i-1}) + u(y_{2i})}{2} - u(x), \quad i = 1, \dots, n/2.$$
   These quantities represent ordered directional second-order increments. The graph Laplacian is shown to be the trace of these eigenvalues ($L[u] = \frac{2}{n} \sum \lambda_i$), while the graph Monge–Ampère operator is defined as their product (determinant analog):
   $$M[u](x) = \prod_{i=1}^{n/2} \lambda_i[u](x).$$

2. Graph Convexity: A function $u$ is defined as graph convex if $\lambda_i[u](x) \geq 0$ for all $i$. Strict graph convexity ensures the operator is in its elliptic regime.

3. Bellman Formulation: To facilitate analysis, the product form of the equation $M[u](x) = f(x)$ is reformulated using the arithmetic-geometric mean inequality into a Bellman-type equation:
   $$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),$$
   where $H_i[u](x)$ are the order-statistic operators and $A_{n/2}$ is the set of positive weights with product 1. This formulation makes the operator's monotonicity transparent.

Key Contributions and Theoretical Results

• Comparison Principle and Uniqueness: The authors establish a comparison principle for subsolutions and supersolutions of the inhomogeneous Dirichlet problem. A key technical step involves proving that if two functions agree at a point and their order-statistic operators agree, they must agree on the entire neighborhood. This leads to the uniqueness of strictly graph-convex solutions.
• Existence via Perron's Method: Existence is investigated using Perron's method. The authors identify that, unlike the linear Laplacian case, the existence of solutions for the inhomogeneous problem is sensitive to the combinatorial geometry of the graph. Specifically, barriers for the extremal operators exist if and only if the subgraph induced by the unlabeled vertices is a "1-degenerate" graph (specifically, a forest). If the unlabeled subgraph contains a closed structure (like a cycle where every node has $\geq 2$ neighbors within the set), a solution may not exist.
• Homogeneous Case: For the homogeneous equation $M[u]=0$, the problem reduces to the condition $\lambda_1[u] = 0$ (or $u = H_1[u]$). This represents a nonlinear interpolation rule based on the smallest discrete eigenvalue. The authors prove comparison and uniqueness for this case under a "reachability condition" (no nonempty subset of unlabeled vertices is closed under retaining at least two neighbors), which is satisfied if the unlabeled subgraph is a forest.
• Woven Forests: To guarantee existence for the inhomogeneous problem, the paper introduces "woven forests." These are graphs constructed by augmenting a forest $F$ with boundary vertices $O$ to ensure every interior vertex has a fixed degree $n$. This construction ensures the necessary 1-degeneracy condition is met.

Numerical Schemes and Experiments
The paper proposes fixed-point iterative schemes motivated by the Bellman formulation:

• Inhomogeneous Scheme: An iterative update based on solving a scalar nonlinear equation derived from the Bellman map.
• Homogeneous Scheme: A simpler update driven by the residual $u - H_1[u]$.
• Convergence: The authors prove that these schemes converge to the unique solution on woven forests, utilizing a weighted norm based on a barrier function constructed via a "peeling" sequence of the graph layers.

Numerical experiments compare the graph Monge–Ampère method against graph Laplacian regularization on a 2D domain (approximating the unit ball). The results indicate that while Laplacian solutions tend to be flatter, the Monge–Ampère method produces solutions that better approximate the parabolic shape of the continuous solution, particularly on radial and uniform tree-like graph structures. The method demonstrates lower discrete $\ell_2$ errors in several test cases.

Significance and Claims
The paper claims to add a "determinant-type graph operator" to the toolkit of nonlinear PDEs for machine learning. Its primary significance lies in:

1. Theoretical Framework: Providing the first rigorous analysis of a Monge–Ampère equation on finite graphs, including comparison principles, uniqueness, and existence conditions tied to graph topology.
2. Nonlinearity: Offering a mechanism for semi-supervised learning that is sensitive to anisotropic data structures, contrasting with the diffusive nature of Laplacian methods.
3. Computational Viability: Demonstrating that despite the fully nonlinear nature of the operator, efficient fixed-point schemes can be constructed and proven to converge on specific graph classes (woven forests).

The authors modestly note that current numerical experiments assess qualitative shape rather than rigorous continuum convergence, as the normalization is currently graph-dependent. They suggest future work should incorporate positive edge weights to achieve geometrically consistent scaling and a meaningful continuum limit.