Kemeny-Regularized Message Passing

Integrate the regularizer into a message-passing GNN immediately after the layer that produces pairwise edge logits and before normalization into propagation weights. For node embeddings z_u, compute candidate-edge logits s_uv with an MLP, symmetrize them as a_uv=softplus((s_uv+s_vu)/2), add self-loop weights, and form A from these affinities. Set D_uu=sum_v A_uv+epsilon and P=D^{-1}A. For small graphs, construct the symmetric similar matrix S=D^{-1/2}AD^{-1/2}, compute its eigenvalues with a differentiable symmetric eigensolver, and evaluate K_hat=sum_{r=2}^n 1/(1-lambda_r). Add alpha times max(0,K_hat-tau)^2 to the task loss. For larger graphs, estimate the dominant reciprocal-gap terms with Lanczos iterations, or estimate the trace of the pseudoinverse using Rademacher vectors and iterative linear solves. The theorem constant is used only as a calibration reference; the learned weighted graph need not have diameter exactly two. First test a three-layer GCN or GraphSAGE on Cora and on a synthetic two-community graph with long-range labels. Compare the baseline with threshold values tau equal to the baseline Kemeny estimate, 1.5 times it, and 2 times it. Track validation accuracy, long-range accuracy, Kemeny estimate, smallest nontrivial spectral gap, gradient variance across layers, and final-state cosine similarity. Success requires a lower Kemeny estimate and larger spectral gap without increased oversmoothing, together with improved long-range accuracy or smoother loss curves at equal FLOPs.