Beyond the Laplacian: Doubly Stochastic Matrices for Graph Neural Networks

2026-04-16 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning · Depth: Expert, quick

Summary

Graph Neural Networks (GNNs) typically use Laplacian or adjacency matrices for message passing, but a new approach replaces these with a Doubly Stochastic graph Matrix (DSM). This DSM, derived from the inverse of a modified Laplacian, naturally encodes continuous multi-hop proximity and strict local centrality. To address the $O(n^3)$ complexity of exact matrix inversion, the DsmNet model approximates the DSM using a truncated Neumann series, achieving $O(KE|)$ time efficiency. A variant, DsmNet-compensate, introduces a Residual Mass Compensation mechanism to analytically re-inject truncated probability mass into self-loops, strictly restoring row-stochasticity and structural dominance. This method effectively mitigates over-smoothing by bounding Dirichlet energy decay and shows robust performance on homophilic benchmarks, also demonstrating versatility for Graph Transformers.

Key takeaway

For research scientists developing or optimizing Graph Neural Networks, consider integrating Doubly Stochastic Matrices (DSMs) to enhance structural encoding and mitigate over-smoothing. Your GNN architectures could benefit from the DsmNet or DsmNet-compensate variants, which offer efficient $O(KE|)$ operation and improved performance on homophilic benchmarks. Evaluate DSMs as a continuous structural encoding for Graph Transformers to explore new architectural possibilities.

Key insights

Doubly Stochastic Matrices (DSMs) can replace Laplacians in GNNs to encode multi-hop proximity and local centrality.

Principles

• DSM encodes continuous multi-hop proximity.
• Residual Mass Compensation restores row-stochasticity.

Method

Approximate DSM using a truncated Neumann series, then apply Residual Mass Compensation to re-inject probability mass into self-loops, ensuring strict row-stochasticity.

In practice

• Use DsmNet for efficient GNN message passing.
• Apply DsmNet-compensate to mitigate over-smoothing.

Topics

• Graph Neural Networks
• Doubly Stochastic Matrices
• Neumann Series Approximation
• Residual Mass Compensation
• Over-smoothing Mitigation

Best for: Research Scientist, AI Scientist, Machine Learning Engineer

Related on AIssential

• Understanding Convolutions on Graphs — GNNs process graph-structured data by aggregating and combining node features, enabling powerful predictions on complex systems.
• Geometrical fairness in graph neural networks — A new graph diffusion method modifies the Laplacian operator to mitigate bias and improve fairness.
• GJDNet: Robust Graph Neural Networks via Joint Disentangled Learning Against Adversarial Attacks — GJDNet enhances GNN robustness by jointly disentangling node representations and decision spaces against adversarial attacks.
• Learning Long Range Spatio-Temporal Representations over Continuous Time Dynamic Graphs with State Space Models — CTDG-SSM unifies state-space modeling with graph topology to capture long-range spatio-temporal dependencies in continuous-time dynamic graphs.
• Graph Reduction in Multirelational Networks: A Spreading-Oriented Reduction Benchmark — Graph reduction's impact on influence maximization performance varies significantly by network type and reduction strategy.
• Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey — Graph rewiring modifies GNN topology to combat over-squashing and over-smoothing, improving information flow.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.