Negative Bethe-Hessian positional features

(1) Integration point: before the first message-passing layer, construct node positional features Z from the negative Bethe-Hessian eigenspace and concatenate them with the original node attributes X, or process Z through a separate linear branch. Do not materialize H. Implement its matrix-vector product using one sparse adjacency multiplication and one elementwise degree multiplication. For estimated mean degree d_hat=2|E|/|V|, initialize t=sqrt(max(d_hat-1,epsilon)); also test a small grid around this value, such as 0.5t, t, and 2t. (2) Pseudocode: degree=degree(A); matvec(x)=t*t*x-t*(A@x)+(degree-1)*x; eigenvalues,eigenvectors=lanczos(matvec,which='SA',k=K); keep={j:eigenvalues[j]<-tau}; Z=eigenvectors[:,keep]; normalize each column of Z; zero-pad to K columns; H0=MLP(concat(X,Z)); output=GNN(H0,A). Use K=16 initially and tau=1e-5. Add the learned gate g_i=sigmoid(W_g[X_i concatenated with Z_i]+b_g) so the model can suppress noisy coordinates. (3) Computed from the mathematics: the operator, its eigenpairs, and negative-eigenvalue selection. Estimated empirically: t, tau, K, and whether gating helps. Verify every retained eigenpair using the residual norm ||H u_i-lambda_i u_i||_2/||u_i||_2<1e-4. (4) First experiment: generate two- and four-community stochastic block model graphs with n in {1000,5000}, mean degrees d in {1.2,1.5,2,3,5}, and several signal strengths around the detectability transition. Compare a three-layer GCN with raw features, Laplacian eigenvectors, adjacency eigenvectors, and Bethe-Hessian features at equal hidden width and training FLOPs. Measure node-classification accuracy, accuracy with only 10 percent labels, eigensolver cost, and performance as degree changes. Success means higher accuracy or better label efficiency near d=1 without degradation on denser graphs.