PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectral Reversal: Counteracting Singular Value Bias for Graph Prompting

Hanxu Yang, Yuhuan Zhao, Xiaodong He, Zhao Kang

arXiv:2609.32143v1cs.LGcs.AIcs.SI

TL;DR

Existing graph prompting adapts frozen pre-trained GNNs without explicitly using their internal spectral structure, while pre-training can emphasize dominant singular directions and underuse lower-energy ones. SRP rebalances those directions with spectral and null-space components; the paper reports state-of-the-art benchmark performance using less than 7% of backbone parameters.

  • Problem

    Graph prompting offers parameter-efficient adaptation of frozen GNNs, but existing methods often treat encoders as black-box feature extractors and overlook their spectral structure.

    Source: §1 · p. 1

  • Method

    SRP rebalances frozen encoders using a learnable soft-thresholding spectral mask and a null-space augmentation channel.

    Source: §1 · p. 2

  • Results

    SRP achieves state-of-the-art performance across diverse benchmarks while using less than 7% of backbone parameters.

    Source: §7 · pp. 9–10

  • Takeaways & Limitations

    The paper concludes that which directions are adapted can matter more than how many parameters are introduced.

    Source: §7 · p. 10

    SRP relies on a shared singular basis and global threshold, which may miss region-specific frequency heterogeneity; its null-space channel can be limited when the frozen transformation has little or no null space.

    Source: §7 · p. 10

Abstract

from arXiv · show

Pre-training Graph Neural Networks (GNNs) via self-supervised learning has become a dominant paradigm, yet efficiently adapting frozen encoders remains a challenge. Graph prompting offers a parameter-efficient alternative to fine-tuning, but existing methods largely treat pre-trained models as opaque feature extractors, ignoring their internal spectral structure. In this work, we identify a systematic phenomenon in pre-trained GNNs, which we term spectral bias: optimization during pre-training disproportionately aligns representations with directions associated with large singular values, leaving low-energy directions under-explored. We show that these underutilized directions can encode complementary information that is beneficial for downstream adaptation, especially under distribution shift. To leverage this insight, we propose Spectral Reverse Prompt (SRP), a prompting framework that rebalances the spectral contributions of frozen GNN encoders. SRP applies a learnable soft-thresholding mask in the spectral domain to down-weight dominant directions while amplifying weaker ones. In addition, SRP incorporates a null-space augmentation module that captures variation in directions with minimal activation under the frozen encoder. Extensive experiments across multiple benchmarks demonstrate that SRP achieves state-of-the-art performance with minimal additional parameters, highlighting that reweighting spectral components is a principled and effective strategy for parameter-efficient graph adaptation.

1 Introduction

Graph prompting adapts frozen pre-trained GNNs efficiently, but often treats them as black-box feature extractors and overlooks their spectral structure. SRP rebalances spectral contributions to address underused directions, with reported gains in parameter efficiency, robustness to distribution shift, and benchmark performance.

1 Introduction

  • Pre-training emphasizes large-singular-value directions, while lower-energy directions can be misaligned with downstream needs, especially under inter-class inequality.The paper calls this pattern spectral bias.Source: §1 · p. 1
  • SRP combines a learnable soft-thresholding spectral mask with a null-space channel to rebalance frozen encoders toward underused directions.The spectral channel suppresses dominant components and amplifies weaker ones; the null-space channel extracts variation minimally expressed by the encoder.Source: §1 · p. 2
  • SRP is reported to improve parameter efficiency and robustness to distribution shift, with consistent gains over existing prompting methods on node- and graph-level benchmarks.The paper also identifies more effective and robust adaptation, particularly in low-resource settings.Source: §1 · p. 2

2 Related Work

Prior work covers self-supervised graph pre-training and parameter-efficient graph adaptation. The paper situates its approach as addressing the lack of explicit spectral analysis in existing prompting methods.

2 Related Work

  • Self-supervised graph pre-training includes contrastive methods such as DGI, InfoGraph [16], GraphCL [17], GRACE [18], and SimGRACE [19], as well as generative reconstruction methods.Other approaches use bootstrapping, domain-specific motifs [21], masked node features [22] [23], or edge prediction [24].Source: §2 · p. 2
  • Graph adaptation methods include LoRA-based approaches and prompts that modify node features, edges, topology, representations, or virtual nodes.Examples include GraphLoRA [32], GPF [8], EdgePrompt [9], GraphTOP [34], UniPrompt [35], CurvPrompt [36], GraphPrompt [37], and GPPT.Source: §2 · p. 2
  • Existing prompting approaches primarily adapt inputs or structures without explicitly analyzing agreement between prompting mechanisms and weight metrics.The paper identifies this gap as motivation for rebalancing spectral contributions and using the null space.Source: §2 · p. 2

3 Notations and Preliminaries

The preliminaries define graph data and contrast prompt tuning with joint pre-training and fine-tuning. They also introduce the SVD components and the right null space used in the paper’s spectral analysis.

3 Notations and Preliminaries

  • A graph is represented by nodes, edges, node features, labels, and an adjacency matrix encoding connectivity.The feature matrix has one row per node, and each node has a label from the label space.Source: §3 · pp. 2–3
  • Graph prompt learning freezes the pre-trained encoder and optimizes prompt parameters, unlike joint downstream updating of the encoder and task-specific head.Prompts may be injected at input, intermediate-layer, or representation levels.Source: §3 · p. 3
  • The compact SVD expresses a weight matrix using orthonormal left and right singular vectors and a diagonal matrix of sorted positive singular values.The right null space is the orthogonal complement of the subspace spanned by the right singular vectors.Source: §3 · p. 3

4 The Spectral Bias of Pre-trained GNNs

The section characterizes spectral bias as a mismatch between pre-trained capacity and downstream demand: dominant directions receive disproportionate capacity, while weak directions and null-space signals pose distinct constraints. It motivates targeted adaptation by showing that weak directions can carry downstream utility and that restricting trainable capacity to them can tighten a generalization bound.

4 The Spectral Bias of Pre-trained GNNs

  • The paper attributes spectral bias to gradient updates concentrating along principal input directions and graph message passing further contracting representation covariance.Under the stated assumptions, low-dimensional training inputs constrain update energy to their principal subspace.Source: §4 · pp. 3–4
  • PCA of the null space reportedly yields higher information density than the encoder, with 8 dimensions matching the classification performance of a 128-dimensional encoder.The comparison is reported for a representation obtained through costly training.Source: §4 · p. 4, Figure 1 · p. 4
  • Theorem 4.2 states that downstream signals in the encoder’s column space are recoverable, while components in its null space incur irreducible approximation error.For a frozen encoder, the optimal downstream classifier may therefore have a residual determined by its projection onto the null space.Source: §4 · p. 4
  • DPMS grows inversely with pre-trained capacity, so severe spectral concentration makes the weak-direction-to-strong-direction DPMS ratio diverge.The net gap ∆q quantifies this pattern regionally across singular-value quintiles.Source: §4 · p. 4
  • Theorem 4.3’s setup restricts a learnable adaptor to rank r_s across |V_w| weak directions, with parameter count O(|V_w|r_s).The bound is stated under McAllester’s bound with a Gaussian prior bounded by the backbone condition number and an analytically optimized posterior.Source: §4 · p. 5
  • The resulting generalization gap depends on the number of activated weak directions rather than the original feature dimensions, motivating adaptation restricted to the misaligned subspace.The passage describes this as a tighter guarantee than full fine-tuning.Source: §4 · p. 5

5 Method: Spectral Reverse Prompt

SRP prompts frozen GNNs through two orthogonal channels that counteract pretrained spectral weighting and recover signal from directions invisible to the encoder. A shared bottleneck fuses these channels, with linear training overhead and a trainable parameter count that scales independently of input dimension.

5 Method: Spectral Reverse Prompt

  • SRP adds a layer-wise prompt to node features, using spectral and null-space channels on orthogonal subspaces.The channels reverse the encoder’s spectral weighting and extract signal from directions invisible to its weight matrix.Source: §5 · pp. 5–6

5.1 Spectral Channel: Soft-Threshold Reversal

  • The spectral channel projects features onto the right-singular basis and applies a learnable soft-threshold mask before a bottleneck adaptor.The mask suppresses strong singular directions and weights weak ones toward 1.Source: §5.1 · p. 6

5.2 Null-Space Channel

  • The null-space channel projects features onto ker(W) and extracts the top-m principal components from that projection.The PCA basis and singular-vector basis are frozen and orthogonal; only the null-space adaptor is learned.Source: §5.2 · p. 6

5.3 Channel Fusion and Output

  • The two channel outputs are summed in a shared bottleneck and projected to the GNN activation space.When din ≤ k + m, SRP instead uses a projective fallback that preserves weak spectral and null-space signals.Source: §5.3 · p. 6

5.4 Complexity Analysis

  • After offline SVD and null-space computation, SRP’s training forward-pass overhead is O(|V|rs(k + m + h)), compared with backbone message passing at O(|E|din).The passage characterizes SRP’s cost as linear in graph size and asymptotically negligible relative to the backbone’s message passing.Source: §5.4 · p. 6
  • SRP’s trainable parameter count scales as O(nrsh), avoiding dependence on input dimension din and remaining far smaller than full fine-tuning or LoRA-style baselines.Frozen buffers require O(din(k + m) + nhk) memory; activation memory is O(|V|din), as in the unmodified backbone.Source: §5.4 · p. 6

6 Experiments

Across node- and graph-level benchmarks, SRP is consistently among the top-performing methods under GraphCL and SimGRACE pre-training. Ablations and additional evaluations examine its components, sensitivity, and convergence behavior.

6.1 Experimental Setup

  • The experiments cover ten datasets: five-shot node classification and 50-shot graph classification, using GraphCL and SimGRACE against ten prompting and adaptation baselines.All methods use the same backbone architecture, pretrained checkpoints, and evaluation protocol.Source: §6.1 · p. 7

6.2 Main Results

  • SRP achieves the best or second-best performance on almost all datasets across node- and graph-level classification benchmarks.The reported comparisons cover GraphCL and SimGRACE pre-training.Source: §6.2 · p. 7, Table 1 · p. 7, Table 2 · p. 8

6.3 Ablation Study

  • Removing either SRP channel, removing spectral reversal, or replacing it with bidirectional amplification reduces performance relative to full SRP.The comparisons span both pre-training frameworks; the ablations test the null-space and spectral channels as well as the reversal strategy.Source: §6.3 · p. 8, Table 3 · p. 8

6.4 Additional Evaluation

  • When the shot count is extremely low, node-classification performance fluctuates significantly with label count, while graph-classification performance is less affected.The label-sensitivity analysis is reported in Figure 3.Source: §6.4 · pp. 8–9, Figure 3 · p. 9
  • Under GraphCL, 5-shot node-classification accuracy remains stable across the tested bottleneck ranks and PCA dimensions, plateauing at rs=32 and m=16.Figure 3 varies rs over {16, 32, 64, 128} and m over {4, 8, 16, 32}.Source: §6.4 · p. 9, Figure 3 · p. 9
  • SRP generally converges faster than other methods under the two pre-training strategies shown in Figure 4.The authors associate faster convergence with needing fewer tuning epochs.Source: §6.4 · p. 9, Figure 4 · p. 9

7 Conclusion

SRP addresses spectral bias by reallocating adaptation capacity toward underutilized components of frozen encoders. It reports state-of-the-art performance across diverse benchmarks using less than 7% of backbone parameters, while identifying limits tied to its shared singular basis, global threshold, and available null space.

7 Conclusion

  • SRP achieves state-of-the-art performance across diverse benchmarks using less than 7% of backbone parameters.The conclusion argues that which directions are adapted can matter more than how many parameters are introduced.Source: §7 · pp. 9–10
  • SRP targets spectral bias by reallocating capacity toward underutilized components of frozen encoders.Its spectral reweighting uses soft-thresholding and null-space augmentation.Source: §7 · p. 9
  • A shared singular basis and global threshold may miss region-specific frequency heterogeneity, while the null-space channel can be limited when the frozen transformation has little or no null space.Future work includes instance- or structure-adaptive reweighting driven by downstream feedback.Source: §7 · p. 10

A Dataset Statistics

The appendix lists the benchmark-statistics tables and develops proofs concerning spectral concentration, downstream reachability, and null-space PCA. Together, these results formalize how frozen encoders constrain downstream approximation and how null-space directions can be selected.

A Dataset Statistics

B.1 Proof of Proposition 4.1 (Spectral Concentration)

  • The proof section derives a concentration result for updates under a spectral-alignment condition.The supplied passage identifies the conclusion as a spectral concentration result.Source: §B.1 · pp. 14–15

B.2 Proof of Theorem 4.2 (Reachability and Approximation Limits)

  • For a frozen encoder, the minimum linear-head approximation error is the squared Frobenius norm of the downstream target projected onto the encoder’s null space.The optimal head is A* = UΣ^-1V^⊤W_down.Source: §B.2 · p. 15

B.3 Null-Space PCA Optimality (Proof of Theorem B.1)

  • Among orthonormal bases constrained to the encoder’s null space, null-space PCA uniquely selects the top-m directions of projected input covariance; unconstrained PCA is generically infeasible and suboptimal.The construction maximizes variance while satisfying WN_o = 0.Source: §B.3 · p. 16

B.4 PAC-Bayes Generalization Bound (Proof of Theorem B.2)

The appendix bounds SRP’s generalization complexity, establishes an algebraic fallback for small input dimensions, and reports extensions and comparisons across architectures and graph settings. It also clarifies the temperature mask, runtime, and how SRP’s adaptation subspaces differ from low-rank alternatives.

B.4 PAC-Bayes Generalization Bound (Proof of Theorem B.2)

  • The PAC-Bayes complexity bound depends on the number of targeted weak directions, |Vw|, rather than the full feature dimensions.The dominant parameter count scales as |Vw|r_s, linking the bound to SRP’s restriction of capacity to the weak subspace.Source: §B.4 · p. 16

B.5 Algebraic Equivalence of the Projective Fallback

  • When d_in − k ≤ m, a single projective-fallback adaptor spans the same hypothesis space as the dual-channel prompt.The fallback is presented as an exact algebraic simplification that avoids redundant PCA calculations while maintaining SRP’s theoretical capacity.Source: §B.5 · p. 17

C.1 Generalization to GraphGPS and Graphormer

  • 12.48 percentage points: SRP’s average absolute gain over Classifier-only across eight GraphGPS and Graphormer settings; it wins six settings and is within 0.82 points of GraphLoRA in the other two.Results use the same frozen encoder and evaluation protocol as the main experiments.Source: §C.1 · p. 17, Table 6 · p. 18

C.2 Role and Sensitivity of the Temperature Coefficient

  • 3.55 points on Cora and 1.35 points on CiteSeer: accuracy gains when γ increases from 0.001 to 10; Weak-k also outperforms Strong-k and Random-k, particularly on those datasets.Performance is stable for γ ≥ 1, and the authors use γ = 10 without dataset-specific tuning.Source: Table 7 · p. 18, §C.2 · p. 18, Table 8 · p. 18

C.3 Extension to Heterophilic Graphs

  • SRP outperforms GraphLoRA on all three heterophilic datasets, with especially clear improvements on Squirrel and Chameleon, where GraphLoRA falls below Classifier-only.The experiments use GraphCL pre-training and the main-experiment hyperparameter configuration.Source: Table 9 · p. 19, §C.3 · p. 19

C.4 Scalability and Runtime

  • SRP is faster than GPF on five of six evaluated datasets, while its trainable parameter count is independent of graph node and edge counts.The frozen GNN backbone remains the dominant computation; the experiments include ogbn-arxiv with nearly 170,000 nodes.Source: §C.4 · p. 19, Table 10 · p. 20

C.5 Difference from GraphLoRA / C.6 Difference from Standard LoRA

  • GraphLoRA adapts within the message-passing pathway, whereas SRP selects weak singular and null-space directions; unlike standard LoRA, SRP preserves the frozen operator and prompts after aggregation.The methods therefore differ in adaptation objective, subspace geometry, and interaction with graph propagation.Source: §C.5 · p. 20, §C.6 · p. 21

C.7 Clarification of the Singular-Value Groups in Figure 1

  • The five singular-value groups are spectrum-defined: Q1 contains the largest and Q5 the weakest nonzero directions, while exact zero directions are handled separately.Group sizes differ by at most one, and the downstream classifier does not determine group construction.Source: §C.7 · p. 21

C.8 Why SRP Shows Larger Gains on Node-Level Tasks

SRP’s larger node-level gains are associated with greater null-space capacity in high-dimensional inputs. Graph-level readout can also reduce the contribution of local information recovered by SRP.

C.8 Why SRP Shows Larger Gains on Node-Level Tasks

  • The node-versus-graph performance difference is attributed mainly to input dimensionality, null-space capacity, and graph-level readout.For graph classification, the same singular direction can correspond to different graph frequencies across graphs, weakening its correspondence to complementary graph-frequency information.Source: §C.8 · pp. 21–22
  • When input dimension greatly exceeds hidden dimension, the first frozen layer necessarily has a large right null space; Cora and CiteSeer have at least 1,305 and 3,575 null-space dimensions, respectively, with 1,305 observed on Cora.Graph-level datasets have only 3–89 input dimensions, providing substantially less null-space capacity and making SRP rely more on spectral reversal or the projective fallback.Source: §C.8 · p. 22
  • Mean readout preserves the constant component while cancelling many nonstationary node-local variations, potentially reducing the local information SRP recovers.Sum pooling has the same directional effect up to scaling.Source: §C.8 · p. 22

C.9 Why the Gains Are Larger on Some Smaller Datasets

The gains on some smaller datasets are associated with spectral complement capacity rather than dataset size alone. Input dimensionality, null-space capacity, and local frequency heterogeneity are identified as relevant factors.

C.9 Why the Gains Are Larger on Some Smaller Datasets

  • The observed trend is better explained by spectral complement capacity than dataset size alone, since input dimension and graph size are confounded in these benchmarks.Cora and CiteSeer have substantially greater null-space-channel capacity; the exact right-null-space dimension depends on input dimension and weight rank, not directly on node count.Source: §C.9 · p. 22
  • SRP uses a shared right-singular basis and global spectral threshold, which can become less precise as local frequency heterogeneity increases.A singular direction may represent different graph-frequency characteristics across regions; the observed performance trend is associated with input dimensionality, null-space capacity, and local frequency heterogeneity rather than graph size itself.Source: §C.9 · p. 23

D.1 Compute Resources Usage.

Experiments use a specified workstation and software environment. The complexity analysis describes SRP’s initialization and per-forward-pass costs, along with its parameter and space overhead.

D.1 Compute Resources Usage.

  • Experiments ran on Ubuntu 22.04 LTS with an Intel Core i9-13900K CPU, an NVIDIA GeForce RTX 3090 GPU with 24GB memory, CUDA 12.1, Python 3.10.19, PyTorch 2.5.1, and PyTorch Geometric 2.7.0.Source: §D.1 · p. 23

D.2 Complexity Analysis

  • The null-space PCA initialization is performed once before training, cached as a frozen buffer, and does not affect training throughput.The analysis says this one-time PCA is typically the dominant initialization cost.Source: §D.2 · p. 23
  • SRP adds no asymptotic overhead beyond the backbone GNN’s message-passing and projection costs.The trainable-path cost is O(|V|(k + m)rs + |V|rsdout), described as negligible versus the backbone’s O(|E|din).Source: §D.2 · pp. 23–24
  • SRP’s trainable parameter count scales as O(rh), with space overhead O(d(k + m) + hk) in parameters and buffers.The stated total trainable count is r(k + m + 3h) + 2h + 2.Source: §D.2 · p. 24

Related papers

Loading 2609.32143v1…