arXiv:2608.04150 2026 Architecture 1 ideas extracted · analyzed Aug 31, 2026
The paper identifies a counterintuitive failure mode of graph augmentation: adding edges or cliques can increase Kemeny’s constant, the stationary-distribution-weighted average hitting time of a random walk. This is directly relevant to graph neural networks, where rewiring and shortcut insertion are commonly used to improve information propagation but can instead worsen global diffusion by changing both paths and stationary mass. The most transferable construction is a Braess-aware rewiring criterion that estimates the change in Kemeny’s constant before accepting candidate edges or cliques. It can be used either as a preprocessing algorithm for static graphs or as a regularizer for a learnable graph-construction module.
Use Kemeny’s constant as a diffusion-quality gate when adding shortcut edges or cliques to a graph used by a GNN. Candidate augmentations are accepted only when they reduce estimated average hitting time, preventing rewiring operations that superficially shorten paths but make the random walk mix more slowly.