On two conjectures concerning Kemeny's constant of graphs

What the math gives to ML

The paper provides explicit global bounds on Kemeny's constant in terms of graph diameter, resistance distances, and spectral gaps. This suggests a practical regularizer for learned graph structures in GNNs: discourage propagation graphs with slow-mixing bottlenecks that make long-range information flow inefficient. The most promising adaptation is to apply a soft penalty to a symmetrized learned adjacency, while avoiding unconditional minimization because excessively fast mixing can cause oversmoothing.