Technical Summary: Rank Is Not Capacity: Spectral Occupancy for Latent Graph Models

Problem Statement

In graph representation learning, the dimension of the latent space is a critical design choice that governs model behavior. However, this dimension is traditionally treated as a brittle hyperparameter: it is fixed before training and tuned via held-out performance. This approach suffers from two fundamental issues:

1. Identifiability: Learned latent factors are identifiable only up to rotation and global rescaling. Consequently, the nominal rank (the declared dimension) rarely coincides with the quantity that actually governs model behavior.
2. Lack of Control: Existing selection procedures (e.g., profile-likelihood elbows, Bayesian selection, cross-validation) typically select a single dimension either before or after fitting. They fail to expose "representational capacity"—the number of latent modes effectively used by the fitted model—as a measurable, controllable, or auditable quantity within the model itself.

In overparameterized regimes, the operative quantity is not the declared rank, but how representational mass is distributed across latent modes.

Methodology: SPECTRA

The authors propose Spectral Prefix Extraction and Capacity-Targeted Representation Analysis (SPECTRA), a framework that replaces nominal rank with the spectrum of a learned positive semidefinite (PSD) kernel as the unit of analysis.

Core Components

1. Trace-Normalized Kernel:
   Instead of fixing the rank $r$ as the dimension, SPECTRA parameterizes a latent affinity kernel $K \in \mathbb{R}^{N \times N}$ via a rank-capped factor $L \in \mathbb{R}^{N \times r}$. Crucially, the kernel is trace-normalized:
   $$K(L) = \frac{N \cdot LL^\top}{\text{tr}(LL^\top)}$$
   This normalization fixes the total spectral mass to $N$, ensuring that differences in the eigenvalue distribution reflect how the representation allocates its fixed spectral budget across latent modes, rather than differences in overall magnitude. This makes spectra comparable across different fits and rank caps.

2. Spectral Occupancy and Effective Dimension:
   The normalized eigenvalues $\lambda_i(K)$ define a probability distribution $p_i(K) = \lambda_i(K)/N$ over spectral modes, termed the spectral occupancy distribution. The authors define the effective spectral dimension ($d_{\text{spec}}$) as the exponential of the Shannon entropy of this distribution:
   $$d_{\text{spec}}(K) := \exp\left( -\sum_{i: p_i > 0} p_i \log p_i \right)$$
   Unlike hard rank, $d_{\text{spec}}$ is a smooth, continuous measure of realized capacity. It equals 1 if all mass is in one mode and equals $s$ if mass is uniformly spread over $s$ modes.

3. Capacity-Control Objective:
   To control the realized dimension during training, SPECTRA introduces an entropy-regularized objective:
   $$F_\eta(L, a, \beta) = \ell(L, a, \beta) - \eta \log d_{\text{spec}}(K(L)) + R(L, a, \beta)$$
   Here, $\ell$ is the link-prediction loss, $R$ is quadratic regularization, and $\eta$ is a scalar entropy weight.

   • $\eta > 0$ encourages a diffuse spectrum (higher $d_{\text{spec}}$).
   • $\eta < 0$ encourages a concentrated spectrum (lower $d_{\text{spec}}$).
   • $\eta = 0$ corresponds to the standard maximum-likelihood fit without spectral entropy bias.

4. Targeting and Calibration:
   The authors establish that, under local regularity conditions (simple active spectrum and non-degenerate Hessian), the realized dimension $d_{\text{spec}}(\eta)$ is locally $C^1$ and monotonically non-decreasing with respect to $\eta$. This allows the use of bisection to find an $\eta^*$ that targets a desired effective dimension $d^*_{\text{spec}}$ within a specified tolerance.

5. Spectral Prefixes:
   A single fitted kernel yields a nested family of aligned lower-dimensional representations. By truncating the kernel to its top $k$ eigenmodes ($K_k$), one obtains the optimal rank-$k$ PSD approximation (by the Eckart–Young–Mirsky theorem). These spectral prefixes provide aligned, lower-capacity views of the same fitted model without retraining.

Key Contributions

1. Spectral Occupancy as Realized Capacity: The paper replaces nominal rank with the trace-normalized spectrum of the learned PSD kernel, using Shannon effective rank ($d_{\text{spec}}$) as a smooth measure of realized latent dimension.
2. Training-Time Capacity Control: It introduces an entropy-regularized objective where a scalar $\eta$ shapes the realized spectral dimension, enabling the targeting of specific $d_{\text{spec}}$ values via bisection.
3. Theoretical Guarantees: The authors verify the identifiability of active spectral modes under simple-spectrum conditions and establish local $C^1$ behavior and monotonicity of the realized-dimension profile. They also prove that spectral prefixes are optimal low-rank PSD summaries.
4. Empirical Capacity Frontiers: Experiments across eight benchmark networks (collaboration, social, biological, infrastructure) reveal that predictive performance (AUC) aligns by achieved $d_{\text{spec}}$ rather than nominal rank. This distinguishes between "saturated" datasets (where performance peaks below the rank cap) and "rank-cap-binding" datasets (where performance improves as the cap increases).
5. Single-Fit Prefix Families: A fitted kernel provides a nested family of aligned spectral prefixes, offering lower-capacity views of the same representation without retraining.
6. Spectrally Controlled Overparameterization: In paired experiments, $\eta$-targeted overparameterized fits (where $r > d_{\text{spec}}$) improve test log-likelihood and reduce the train–test gap compared to rank-cap-only baselines, even when matched for effective capacity.

Experimental Results

• Datasets: The method was evaluated on eight undirected graphs, including citation networks (ca-GrQc, ca-HepTh), social networks (socfb-American75, socfb-Amherst41), biological networks (bio-grid-human, bio-grid-worm), and infrastructure networks (inf-power, inf-openflights).
• Baselines: SPECTRA was compared against Euclidean embeddings (Node2Vec, Role2Vec), matrix factorization (NetMF, GRAREP), mixed-membership models (MNMF), and latent-distance simplex models (HM-LDM).
• Performance:
  • At matched parameter counts, SPECTRA ($\eta=0$) achieved top or second-best AUC on 7/8 datasets across various dimensions.
  • Capacity-Targeted SPECTRA remained competitive at substantially smaller realized dimensions. For instance, targeting the median effective rank of baselines often yielded comparable performance with significantly lower $d_{\text{spec}}$.
  • Frontier Analysis: When plotting AUC against achieved $d_{\text{spec}}$, curves from different rank caps ($r=64, 128, 256$) collapsed onto a common frontier. This confirms that performance is organized by realized spectral capacity, not the nominal rank.
  • Overparameterization: Targeting a specific $d^*_{\text{spec}}$ using a larger rank cap $r$ resulted in better-calibrated models (lower generalization gap and higher test log-likelihood) compared to training with a rank cap equal to $d^*_{\text{spec}}$.

Significance and Claims

The paper argues that capacity should be treated as a property of the fitted model rather than a hyperparameter of the training process. By shifting the focus from nominal rank to spectral occupancy, SPECTRA makes the trade-off between predictive accuracy and realized dimension visible and controllable.

The authors claim that this approach:

• Provides a principled handle on capacity in the overparameterized regime.
• Allows for the extraction of aligned, lower-capacity views of a model (spectral prefixes) without retraining.
• Distinguishes between datasets where the latent structure is fully captured by a small number of modes (saturated) and those where the model is constrained by the rank cap.
• Offers a continuous coordinate ($d_{\text{spec}}$) for comparing the structural complexity of different networks, potentially applicable to studying how network complexity varies across different contexts (e.g., social, biological, infrastructure).

The work is modest about its limitations, noting that it currently operates within Euclidean latent spaces. Extending these concepts to non-Euclidean geometries (e.g., simplex-valued or hyperbolic embeddings) and developing common preprocessing protocols for cross-network comparisons are left for future work.