# Negative Bethe-Hessian positional features

- ID: 2410
- Canonical URL: https://synthcore.org/idea/2410/negative-bethe-hessian-positional-features
- API JSON: https://synthcore.org/api/idea/2410.json
- API Markdown: https://synthcore.org/api/idea/2410.md
- Verification status: unverified
- Source: [arXiv:2608.16672](https://arxiv.org/abs/2608.16672)
- Category: architecture
- Solves: accuracy, sample-efficiency, stability
- ML areas: graph-nn, embedding, initialization
- Math tags: spectral-theory, graph-theory, random-matrix, probability
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Augment node features with eigenvectors corresponding to negative eigenvalues of the Bethe-Hessian H(t,G), rather than using only Laplacian or adjacency positional encodings. The diagonal D-I correction is designed for sparse, locally tree-like graphs and should suppress degree-fluctuation artifacts near the connectivity threshold. Feed the resulting coordinates to a GNN through a learned gate so the model can ignore them when they are uninformative.

## Mathematical statement

Definition 1.1 defines the Bethe-Hessian of an n-vertex graph G as H(t,G)=t^2 I_n-t A_G+(D_G-I_n). Here A_G is the adjacency matrix, D_G is the diagonal degree matrix with (D_G)_{ii}=deg(i), I_n is the identity, and t is a real scalar spectral parameter. Since H(t,G) is symmetric, it has real eigenvalues lambda_i and orthonormal eigenvectors u_i satisfying H(t,G)u_i=lambda_i u_i. The paper proves, for sparse stochastic block models with expected degree d>1, that the number of negative eigenvalues matches the number of informative planted eigenvalues outside the bulk. Use the negative eigenspace Z=[u_i : lambda_i<0] as a structural estimate of community directions. The sparse matrix-vector product is H(t,G)x=t^2x-tA_Gx+(D_G-I_n)x, so the operator can be used without materializing a dense matrix.

## Key formulas

- $$H(t,G)\mathrel{:=}t^{2}I_{n}-tA_{G}+(D_{G}-I_{n}).$$
- $$H(t,G)u_i=\lambda_i u_i,\qquad \lambda_i<0,\qquad Z=[u_i]_{i:\lambda_i<0}.$$
- $$H(t,G)x=t^{2}x-tA_Gx+(D_G-I_n)x.$$
- $$h_i^{(\ell+1)}=\operatorname{GNN}_\ell\left(h_i^{(\ell)},\{h_j^{(\ell)}:j\in\mathcal N(i)\},g_i\odot Z_i\right),\qquad g_i=\sigma(W_g[X_i\,\|\,Z_i]+b_g).$$

## Implementation notes

(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.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.