Technical Summary: PostDeg: Placement Beats Parameterization in LayerNorm GNNs

Problem Statement

Many graph-learning policies for combinatorial optimization tasks—such as influence maximization, network dismantling, and maximum independent set (MIS)—rely on ranking nodes based on topological signals like degree, centrality, or k-core. The dominant deep learning architecture for these tasks involves stacking Graph Attention Network (GAT) blocks with LayerNorm. However, LayerNorm, while stabilizing training, inadvertently erases the very topology signals these policies require. Empirical observations in prior work (e.g., GraphNorm, PairNorm) indicate that feature-statistic normalizers fail to preserve degree-based magnitude contrasts necessary for node selection, yet the literature has not identified the specific mechanism or location within the residual block where this erasure occurs.

Methodology

The paper investigates the "placement" of positive per-node scalar multipliers (representing topology signals like degree) relative to the LayerNorm operation within a GNN residual block.

The Placement Diagnostic

The authors leverage the LayerNorm absorption identity. For a positive scalar $a_i$ and node representation $z_i$:
$$\text{LN}(a_i z_i) \approx \text{LN}(z_i)$$
This approximation holds up to a stabilizer term $\epsilon_{\text{LN}}$. Specifically, the relative residual is bounded by $\epsilon_{\text{LN}} / (a_i^2 \sigma^2)$, where $\sigma^2$ is the feature variance. The paper demonstrates that if a topology scalar is inserted before LayerNorm, it is effectively divided out (absorbed), leaving the representation magnitude unchanged. Conversely, if the same scalar is inserted after LayerNorm, it survives as the representation magnitude reaching the score head.

The PostDeg Operator

Based on this diagnostic, the authors propose PostDeg, a parameter-free operator that occupies the post-LayerNorm slot. It applies an inverse-degree scale to the normalized representation:
$$\hat{h}_i = (b c_i + \epsilon)^{-1/2} \cdot \text{LN}(h_i)$$
where $b c_i$ is the normalized degree (clamped to avoid division by zero), and $\epsilon$ is a small stabilizer. This operation restores a monotone-in-$1/d_i$ magnitude contrast, allowing the downstream scorer to rank nodes by topology.

Experimental Design and Falsifiability

To isolate "placement" from "parameterization," the study employs a controlled experimental grid:

1. Backbone: A fixed 3-layer GAT with LayerNorm.
2. Variable: Only the post-block normalization slot is modified.
3. Falsifiers: Four pre-registered controls were designed to reject the placement rule if they succeeded:
   • GraphScalar: A graph-level spectral scalar (tests if the gain comes from global spectral properties rather than per-node degree).
   • Extra LayerNorm: An additional normalization layer (tests if the gain comes from extra feature normalization).
   • Learned Variants (PostDeg-L-FG/Adaptive): Learned operators in the same slot (tests if expressive capacity is required).
   • PNA Backbone: Adding PostDeg to a PNA backbone (which injects degree inside aggregation) (tests if the gain is backbone-agnostic).

Key Results

The experiments were conducted on four node-selection tasks (InfluMax, Dismantle, Epidemic, MIS) and one graph classification task (DD).

• Performance Gains: PostDeg outperformed the standard LayerNorm backbone by +3.5% on InfluMax, +2.5% on Network Dismantling, and +5.6% on MIS. These gains were consistent across all 10 paired seeds (10/10 wins).
• Placement vs. Parameterization: The learned variants (PostDeg-L-FG and PostDeg-L-Adaptive) were statistically equivalent to the parameter-free PostDeg (TOST equivalence at $\pm 1\%$). This confirms that the gain is driven by the placement of the scalar, not the learnable capacity of the operator.
• Falsifier Outcomes: None of the four falsifiers rejected the placement rule:
  • GraphScalar and Extra LayerNorm showed negligible or negative gains.
  • Learned variants offered no advantage over the fixed PostDeg.
  • Adding PostDeg to a PNA backbone (which already handles degree in aggregation) resulted in paired-equivalence, indicating the gain vanishes when the degree channel is already present in the aggregation step.
• Boundary Conditions: The gain attenuated on tasks with low degree heterogeneity (DD dataset) or where the reward was not aligned with degree magnitude (Epidemic containment), consistent with the theoretical prediction that the effect relies on degree variance.
• DD Collapse: Variance-zeroing normalizers (PairNorm, InstanceNorm, BatchNorm) collapsed to majority-class prediction on the DD dataset, whereas PostDeg maintained ~80% accuracy, demonstrating that PostDeg does not suffer from the same collapse as feature-statistic normalizers.

Significance and Claims

The paper claims to have located the precise mechanism by which LayerNorm erases topology signals in GNNs and provides a simple, parameter-free solution.

• Placement over Parameterization: The primary takeaway is that placement, not parameterization, carries the gain. A small invariance check (placing the scalar after LayerNorm) is sufficient to recover topology signals without learning weights.
• Generalizability: The diagnostic is claimed to generalize to any positive topology scalar (e.g., PageRank, k-core) in any normalized residual stack.
• Theoretical Contribution: The work formalizes the LayerNorm absorption identity for positive scalars and establishes a "placement rule" that dictates where topology magnitude must be injected to be visible to the scorer.
• Modesty: The authors explicitly limit their claims to positive scalars and single-layer residual blocks. They do not claim the method solves multi-layer compounding effects, RMSNorm variants, or sign-changing multipliers, noting these are out of scope. The gain is presented as a specific fix for degree-sensitive node selection tasks where standard LayerNorm GNNs fail to utilize topological magnitude.