Beyond the Laplacian: Doubly Stochastic Matrices for Graph Neural Networks

arXiv cs.LG / 4/17/2026

📰 NewsDeveloper Stack & InfrastructureIdeas & Deep AnalysisModels & Research

共有:

Key Points

The paper proposes replacing the usual Laplacian/adjacency-based structure in Graph Neural Networks with a Doubly Stochastic graph Matrix (DSM) derived from the inverse of a modified Laplacian to better capture continuous multi-hop proximity and strict local centrality.
Because exact DSM computation via matrix inversion is intractable at O(n^3), it introduces a scalable approximation using a truncated Neumann series to build DsmNet.
To fix probability mass leakage caused by truncation, the work adds a Residual Mass Compensation mechanism (DsmNet-compensate) that analytically re-injects the truncated tail mass into self-loops to strictly restore row-stochasticity.
The authors provide theoretical and empirical results showing efficient O(K|E|) runtime, reduced over-smoothing via bounds on Dirichlet energy decay, and solid performance on homophilic benchmarks, while also analyzing limitations on heterophilic graphs.
The DSM framework is further positioned as a continuous structural encoding applicable beyond GNNs, including Graph Transformers, with established theoretical boundaries for different graph types.

Abstract

Graph Neural Networks (GNNs) conventionally rely on standard Laplacian or adjacency matrices for structural message passing. In this work, we substitute the traditional Laplacian with a Doubly Stochastic graph Matrix (DSM), derived from the inverse of the modified Laplacian, to naturally encode continuous multi-hop proximity and strict local centrality. To overcome the intractable

O(n^3)

complexity of exact matrix inversion, we first utilize a truncated Neumann series to scalably approximate the DSM, which serves as the foundation for our proposed DsmNet. Furthermore, because algebraic truncation inherently causes probability mass leakage, we introduce DsmNet-compensate. This variant features a mathematically rigorous Residual Mass Compensation mechanism that analytically re-injects the truncated tail mass into self-loops, strictly restoring row-stochasticity and structural dominance. Extensive theoretical and empirical analyses demonstrate that our decoupled architectures operate efficiently in

O(K|E|)

time and effectively mitigate over-smoothing by bounding Dirichlet energy decay, providing robust empirical validation on homophilic benchmarks. Finally, we establish the theoretical boundaries of the DSM on heterophilic topologies and demonstrate its versatility as a continuous structural encoding for Graph Transformers.