Nuclear-norm regularization

Overview

The nuclear norm of a matrix is the sum of its singular values 2011.07057 §4.3 eq. 11. Used as a penalty, it rewards matrices whose energy sits in few directions, so a learned matrix is pushed toward low rank. The only source here applies it to the adjacency matrix of a graph after a learned mask has been applied, one term per GNN layer 2011.07057 §4.3. The authors report that the term reduces the share of edges that cross communities in their ablation, from 0.211 to 0.189 2011.07057 tab. 5 §5.5. This page covers that use. It is based on one card, so it cannot compare several ways of computing the penalty.

Variants

Exact nuclear norm

The penalty is the full sum over all singular values of the masked adjacency 2011.07057 eq. 11. The paper defines it this way but does not use it directly in its experiments: it estimates the norm with the top-K method below 2011.07057 §4.3. The paper does not report the run time of the exact sum on its benchmarks. Card: PTDNet.

Top-K estimate (PTDNet)

The penalty is the sum of only the K largest singular values, found one at a time by power iteration with deflation 2011.07057 §4.3 alg. 2. The paper gives a bound on the gap to the full norm 2011.07057 eq. 13, and says that ceil(|V|/K) times the estimate is an upper bound on the full norm 2011.07057 §4.3. Larger K gives a tighter bound and more run time, and accuracy rises with K in the paper's sweep from 1 to 32 on synthetic data 2011.07057 §5.6 fig. 7. The benchmark K is not stated.

When to use which

Use this penalty when your goal is a sparser, community-like graph, and check the effect on your own data. The paper's benchmark gains from the low-rank term are small on Cora, Citeseer and Pubmed (at most 0.007 with GCN 2011.07057 tab. 3). The largest gap is on PPI with GCN, from 0.752 to 0.803 2011.07057 tab. 3. The paper reports that gains from the whole method grow with noise 2011.07057 §5.3.

Implementation sketch

Penalty per GNN layer, using the top-K estimate. The gates come from the learned edge-gating step 2011.07057 §4.2.

# Masked adjacency for one layer  [arxiv:2011.07057 §4.2.1]
a_masked = adjacency * gates          # gates: relaxed keep per edge

# Top-K nuclear-norm estimate  [arxiv:2011.07057 alg. 2]
def topk_nuclear(matrix, k):
    gram = matrix.T @ matrix          # (n, n)
    total = 0.0
    for _ in range(k):
        # Dominant eigenvector by power iteration  [§4.3]
        v = power_iteration(gram)     # (n,)
        # Singular value from the Rayleigh quotient  [alg. 2]
        sigma = sqrt(abs(v @ gram @ v / (v @ v)))
        total = total + sigma
        # Deflate so the next pass finds the next vector  [alg. 2]
        gram = gram - gram @ outer(v, v)
    return total

# Add the penalty to the loss; beta2 is chosen by search  [§5.5]
low_rank = sum(topk_nuclear(a, k) for a in masked_adjacencies)
loss = task_loss + beta1 * edge_penalty + beta2 * low_rank

The paper does not write the combined loss, and it does not state the benchmark value of beta2 2011.07057 §5.5. The line that adds the terms is therefore a design choice, not the paper's formula.

Contradictions

None known between papers, since only one card covers this concept. The paper and its released code differ in how the penalty is computed, for example in which masks it uses and in its weight scales. Those differences are listed on the card 2011.07057 §4.3: PTDNet.

Pitfalls

• Weight scale. The paper's synthetic weights are for a different setting and are not transferable to benchmarks 2011.07057 tab. 4.
• K is unstated for benchmarks. The only K values given are a synthetic sweep 2011.07057 §5.6.
• Variance can hide the gain. On Citeseer with GCN the variant without the term has a standard deviation of 0.170, far above the rest of the table 2011.07057 tab. 3. Check that figure in the original table before using it.
• Gradient path. The paper's algorithm marks the exact SVD output as receiving no gradient, and its backward pass runs through the power-iteration step 2011.07057 alg. 2 §4.3.

Papers

• Learning to Drop: Robust Graph Neural Network via Topological Denoising: uses a top-K nuclear-norm penalty on each layer's masked adjacency, trained together with learned edge gates.