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

Problem Statement

Graph Attention Networks (GAT) normalize neighborhood relevance scores using softmax, which corresponds to the maximum-entropy solution under Shannon statistics. This design implicitly assumes that attention weights should be distributed according to extensive (Boltzmann–Gibbs) statistics. However, real-world graphs often violate these assumptions:

• Homophilic graphs (e.g., citation networks) often benefit from focusing on a few highly relevant neighbors, ignoring the long tail of weakly related ones.
• Heterophilic graphs (e.g., web graphs) often benefit from aggregating small amounts of evidence from many dissimilar neighbors.

Standard softmax is sub-optimal for both regimes because it cannot represent exact zeros (forcing dense attention) and enforces a fixed tail behavior. While sparse alternatives like Sparsemax and $\alpha$-entmax exist, they typically rely on fixed hyperparameters or are restricted to specific regimes (e.g., $\alpha$-entmax is defined only for $\alpha \ge 1$, missing the heavy-tailed regime). Furthermore, existing methods often treat the sparsity index as a frozen hyperparameter requiring per-task grid search.

Methodology: LTGA

The authors propose LTGA (Learnable Tsallis Graph Attention), a graph attention layer that replaces the standard softmax normalization with a $q$-softmax based on Tsallis statistics. The entropic index $q$ is learned end-to-end, allowing the model to interpolate continuously between three regimes:

1. Heavy-tailed ($q < 1$): Unbounded support, retaining weight on low-scoring neighbors.
2. Shannon/Softmax ($q = 1$): The standard GAT baseline.
3. Compact-support ($q > 1$): Produces exact zeros for scores below a threshold, effectively pruning uninformative neighbors.

Key Technical Components:

• Reparameterization: To ensure numerical stability and prevent the index from drifting to degenerate regimes, $q$ is parameterized as $q(\alpha) = 1 + \delta \tanh(\alpha)$, where $\alpha$ is an unconstrained scalar. This pins the initialization to the Shannon baseline ($q=1$) when $\alpha=0$.
• Granularities: The index $q$ can be tied at four levels of granularity, trading expressiveness for parameter count:
  • Global-q: A single scalar shared across all layers and heads.
  • Layer-q: One scalar per layer.
  • Head-q: One scalar per attention head.
  • Edge-q (LTGA-Edge): A per-edge index generated by a small MLP that maps endpoint embeddings to a scalar gate. This allows different edges within the same neighborhood to adopt different attention regimes.
• Numerical Stability: A Taylor expansion branch is used near $q=1$ to handle the removable singularity in the $q$-exponential function, ensuring continuous values and gradients.
• Training Stabilizers:
  • Decoupled Optimizer: A separate Adam optimizer for the $\alpha$ parameters with a warm-up schedule (freezing $\alpha=0$ for the first $T_w$ epochs) allows feature weights to converge before the attention geometry changes.
  • Shannon-Prior Regularizer: A quadratic penalty on $(q-1)^2$ acts as Occam's razor, penalizing departures from the softmax baseline unless they improve the task loss.

Key Contributions

1. Learnable Entropic Index: LTGA introduces a learnable $q$ to graph attention, covering the full two-sided Tsallis family ($q<1$ and $q>1$), unlike previous work restricted to $\alpha \ge 1$.
2. Stable Formulation: The paper provides a numerically stable $q$-softmax formulation with a Taylor branch around the Shannon limit, alongside reparameterization and regularization strategies to enable stable end-to-end training.
3. Comprehensive Evaluation: The method is evaluated across eight benchmarks spanning a wide homophily spectrum ($h \in [0.05, 0.81]$), comparing against softmax, frozen-$q$ grids, tuned $\alpha$-entmax, sparsemax, and heterophily-specific architectures.
4. Interpretability Analysis: The authors analyze the behavior of the learned index, linking $q>1$ to data-dependent neighborhood pruning and verifying that pruned edges are indeed "noise" (low label agreement and feature similarity).

Results

• Performance: Across 10 seeds and 8 datasets, LTGA-Edge achieves the best average Friedman rank (2.75), outperforming GAT (3.19) and GATv2 (4.06). However, the omnibus test does not reject the null hypothesis ($p=0.199$), indicating that the aggregate performance difference is not statistically significant across all methods.
• Specific Gains: The primary gains are observed on heterophilic benchmarks:
  • Roman-Empire ($h=0.05$): LTGA-Edge improves accuracy by +16.3% over GAT and +1.4% over GATv2.
  • Amazon-Ratings ($h=0.38$): LTGA-Edge improves accuracy by +0.8% over GAT and +1.1% over GATv2.
  • On homophilic graphs (Cora, CiteSeer, PubMed), $q$ converges to 1, and LTGA performs comparably to GATv2.
• Learning vs. Tuning: Learning $q$ does not strictly beat searching for the optimal frozen $q$. A validation-tuned frozen grid achieves 61.4%, tuned $\alpha$-entmax achieves 62.2%, and a capacity-matched control achieves 62.0%, compared to 61.7% for LTGA-Edge. The paper concludes that the value of learning $q$ is convenience (one run instead of a grid) and adaptability, rather than a raw accuracy ceiling.
• Mechanism Validation:
  • On Roman-Empire, the learned index prunes ~42% of attention coefficients to exactly zero.
  • Selectivity: Pruned edges have significantly lower label agreement (9.3% vs 43.5% for kept edges) and feature similarity.
  • Counterfactuals: Restoring pruned edges at inference drops accuracy by 7.1 points. Randomly pruning the same number of edges drops accuracy by 13.0 points more than the learned pruning, confirming that the sparsity is selective and beneficial.
• Granularity: While LTGA-Edge takes the best average rank, the scalar granularities (Global, Layer, Head) perform similarly on datasets where $q$ moves, suggesting the per-edge capacity is the primary driver of performance on heterophilic graphs.

Significance and Claims

The paper modestly claims that LTGA provides a unified, learnable framework for graph attention normalization that adapts to the specific statistical needs of a graph without manual hyperparameter tuning.

• Interpretability: Where $q$ departs from the Shannon baseline, it does so interpretably: $q>1$ corresponds to the selective pruning of uninformative neighbors (compact support), while $q<1$ corresponds to heavy-tailed diffusion.
• Limitations: The authors explicitly state that the heavy-tailed regime ($q<1$) did not show empirical benefits on the tested benchmarks. They also note that on small, high-variance datasets (WebKB), the method offers no advantage over GATv2.
• Positioning: LTGA is not claimed to be complementary to heterophily-specific architectures (like H2GCN or GPR-GNN) because those models do not normalize attention in the same way. Instead, LTGA competes directly with attention-based models and offers a mechanism to replace the fixed softmax normalization with an adaptive, data-driven alternative.

In summary, LTGA demonstrates that learning the entropic index allows a graph attention network to automatically discover whether to be dense, sparse, or heavy-tailed based on the graph's homophily, offering a robust, single-run alternative to grid-searched sparse attention mechanisms.