When Should Graph Attention Be Sparse? Learning a Per-Edge Tsallis Index

Abstract

Graph attention normalizes neighborhood scores with softmax, the maximum-entropy choice under Shannon statistics. But homophilic and heterophilic graphs want different attention shapes, and one fixed normalization cannot serve both. We propose \textbf{LTGA} (\textbf{L}earnable \textbf{T}sallis \textbf{G}raph \textbf{A}ttention), a graph attention layer whose Tsallis entropic index $q$ is learned jointly with the weights, interpolating continuously between heavy-tailed ($q<1$), softmax ($q=1$) and compact-support ($q>1$) attention at four granularities from a global scalar to a per-edge index, under a bounded reparameterization that starts every model at the GAT baseline. Across eight benchmarks at ten seeds, LTGA-Edge takes the best average rank ($2.75$), but the omnibus test does not reject ($p=0.199$) and learning $q$ does not beat searching it: a validation-tuned frozen grid reaches $61.4\%$, tuned $\alpha$-entmax $62.2\%$ and a capacity-matched $q\equiv 1$ control $62.0\%$, against $61.7\%$ for LTGA-Edge. What the learned index buys is one run instead of a grid, and an interpretable mechanism: where $q$ leaves $1$, it prunes $42\%$ of attention coefficients to exactly zero, and those edges are selectively the wrong ones, restoring them costs $7.1$ points, while random pruning at the same rate costs $13.0$ more. Project page: https://kleyt0n.github.io/ltga