Gauge-Invariant, Parameter-Insensitive Regularization for Potential Recovery from Flow on Directed Graphs

Mohammad Forouhesh

cs.LGJul 15, 2026

Gauge-Invariant, Parameter-Insensitive Regularization for Potential Recovery from Flow on Directed Graphs

Authors: Mohammad Forouhesh

Organizations: Amirkabir University of Technology, Iran

Abstract

Recovering a latent potential from observed flow on a directed graph (a discrete Poisson problem with Dirichlet boundaries) is ill-posed, and the standard fix backfires: ridge regularization shrinks toward a gauge-meaningless origin, collapsing and reversing the recovered ordering ( $+0.81\to-0.42$ rank correlation against a planted ground truth). The gauge-invariant graph Dirichlet energy removes the hazard and delivers parameter-insensitivity: the estimate is stable across four orders of magnitude in $λ$ , whereas ridge inverts the ordering for every $λ>0$ . We prove the reduced solve is SPD and preserves dynamic range exactly where ridge collapses it, and localize absorbing boundaries from flow alone via a Poisson residual. The $H^1$ seminorm is classical; what is new is the gauge diagnosis, the parameter-insensitivity it buys, and an ablation showing the result is robust to the extraction method. On three public clickstream corpora the gauge-invariant estimate retains $28$ -- $41\%$ of the interior dynamic range while ridge collapses to as little as $0.2\%$ . The same gauge invariance carries into graph neural networks -- neutralizing the constant mode per layer prevents the oversmoothing that collapses a deep directed GCN -- linking this classical inverse problem to a central question in graph learning.

Explore similar work

Sep 20, 2026eess.SP

Fast Graph Laplacian Estimation using Effective Resistance

Inferring network topology from noisy node observations is a central problem in graph signal processing. In this paper, we consider Laplacian-constrained graph estimation for Gaussian Markov random fields, focusing on the underdetermined regime in which the number of samples is smaller than the number of graph nodes. Existing approaches often formulate the problem as a sparsity-regularized maximum-likelihood estimation problem. While effective, such methods typically require iterative optimization and are often computationally demanding, particularly under Laplacian constraints. Instead, we propose a non-iterative estimator of graph Laplacians that uses effective resistance for regularization, and evaluate the method using a simple sparsification procedure. Experiments show that with some trade-off in edge and weight recovery on the considered dataset, computational cost for moderately sized graphs can be substantially reduced.

Christoffer Kjellson, Claudio Altafini, Emma Tegling

Graph Laplacians Graph Representation Learning

Ask PDF

Jul 8, 2026cs.LG

Eigenbasis-Independent Learnable Spectral Positional Encodings for Directed Graphs via Hermitian Block Krylov Subspaces

Spectral positional encodings (PEs) for \emph{directed} graphs face two obstacles: magnetic Laplacians require an

O(n^3)

Hermitian eigendecomposition per potential, and their complex eigenvectors are defined only up to unitary gauge, which prior work handles with basis-invariant architectures. We propose learnable spectral PEs of the form

h_θ(A_q)\,R

, where

A_q

is a normalized magnetic operator,

h_θ

a learnable scalar spectral response, and

R

a block of random probes. Because the PE is a \emph{matrix function} of the operator, it is gauge-invariant by construction. We compute it in a Hermitian block Krylov subspace from sparse matrix--vector products only, prove that

k = O(\log(1/\varepsilon))

block steps suffice uniformly over heat--resolvent response families, and give a covering-number argument for why low-dimensional structured families generalize where free per-eigenvalue weights overfit. On a directed SBM whose symmetrization is uninformative by construction, direction-blind PEs stay at chance while magnetic Krylov PEs converge to the exact-eigendecomposition oracle as the depth grows. The same probes yield gauge-invariant pairwise features with

1/\sqrt{s}

Monte-Carlo error, and the undirected

q{=}0

case improves heterophilous benchmarks over no-PE and polynomial baselines.

Jiaqing Xie, Yuxin Wang

Graph Laplacians Graph Representation Learning Largest Eigenvalue Positional Encoding Gauge

Ask PDF

Aug 13, 2026math.OC

Difference-of-Convex Regularization for Graph Learning by Differentiable Programming

Laplacian-regularized minimization is fundamental in signal processing and machine learning, but is limited by the dense and ill-conditioned nature of the graph Laplacian pseudoinverse. While the Laplacian itself is sparse, its pseudoinverse is dense and often ill-conditioned, rendering direct computation impractical at scale. Moreover, pseudoinverse learning is more challenging than Laplacian learning. To address this challenge, this paper considers the setting where the graph Laplacian is given and proposes a Difference-of-Convex Regularizer (DCR) graph learning framework that approximates the spectral action of the Laplacian pseudoinverse without direct inversion via regularized Maximum Likelihood Estimation (MLE). By reformulating Laplacian-Regularized Nonnegative Least Squares (LR-NNLS) through a dual representation, DCR decouples pseudoinverse learning from instance-specific inference and enables efficient primal solution reconstruction via a differentiable dual-guided learning scheme. We establish theoretical guarantees on stability and the existence of a unique fixed point for DCR algorithm. Numerical experiments demonstrate improved performance over convex solvers and graph filtering baselines and robust performance across diverse graph topologies.

Liping Tao, Chee Wei Tan

Graph Laplacians Graph Representation Learning Regularization Techniques Differentiable Programming

Ask PDF