We study the spectral gap λ2 of the ABT operator AεG = I − D−1Aε, a generalization of the normalized Laplacian with per-edge ε weights ε(e) > 0. We prove: (i) the Laplacian (ε ≡ 1) is subopti- mal for any connected graph with a leaf and simple λ2 < 1; (ii) any graph with a leaf vertex admits a strictly improving weight via an ex- plicit gradient formula derived from the eigenvalue equation; and (iii) a projected-gradient algorithm achieves +34% improvement on average (up to +46.5% with full optimization). To the author’s knowledge, no prior work addresses suboptimality of the row-stochastic normalized Laplacian among all budget-constrained edge weightings. The closest result, Boyd–Diaconis–Xiao 1, solves the symmetric (doubly stochastic) case, which is a fundamentally different problem.
Eugene Sporyshev (Thu,) studied this question.