Why Regularize NMF Scores With a Sample Graph?
In nonnegative matrix factorization (NMF), a data matrix is approximated by the product of nonnegative factors. Its sample-score columns describe how the samples are represented by the components. If some samples are known to be similar, or are close under a chosen similarity measure, it can be useful to encourage their score columns to be similar as well. Graph-regularized NMF adds that preference to the fitting objective without requiring connected samples to have identical scores.
This is a modeling choice, not a claim that similar samples must share the same biology. Its meaning depends on what the graph represents, how its edges were constructed, and how strongly the graph penalty is weighted. The graph should connect samples, because the penalty acts on sample scores, not on the feature profiles represented by the other factor.
Objective, Graph, and Laplacian
Let \(X\in\mathbb{R}_{\geq 0}^{m\times n}\) be a nonnegative matrix with \(m\) features and \(n\) samples. For a chosen rank \(r\), let \(W\in\mathbb{R}_{\geq 0}^{m\times r}\) contain feature loadings and let \(H\in\mathbb{R}_{\geq 0}^{r\times n}\) contain sample scores. Write \(h_i\) for column \(i\) of \(H\). The basic squared-error NMF objective is \(\frac12\|X-WH\|_F^2\), where the factor of \(\frac12\) is a convenient scaling.
Represent sample relationships by a weighted, undirected graph with adjacency matrix \(A\in\mathbb{R}_{\geq 0}^{n\times n}\). The weights satisfy \(A_{ij}=A_{ji}\geq 0\), and typically \(A_{ii}=0\). A zero weight means that samples \(i\) and \(j\) are not directly connected; a larger weight represents a stronger specified connection. Define the degree matrix \(D\) to be diagonal, with \(D_{ii}=\sum_j A_{ij}\), and define the graph Laplacian \(L=D-A\).
The sum in this definition runs over ordered pairs \((i,j)\). Because the graph is undirected, each distinct edge appears twice in that sum. This convention explains the factor of one-half: each edge contributes \(\lambda A_{ij}\|h_i-h_j\|_2^2\) when counted once.
Why the Laplacian Trace Is a Smoothness Penalty
The trace identity follows by expanding squared distances. First, \(\mathrm{tr}(H D H^\mathsf{T})=\sum_i D_{ii}\|h_i\|_2^2\), while \(\mathrm{tr}(H A H^\mathsf{T})=\sum_{i,j}A_{ij}h_i^\mathsf{T}h_j\). Since \(L=D-A\), their difference is:
The second equality uses the symmetry \(A_{ij}=A_{ji}\): the two squared-norm terms contribute equally after the indices are exchanged. Each pairwise squared distance is nonnegative, so the graph penalty cannot be negative. Edges with greater weights contribute more to the objective when their endpoint scores differ.
Worked Example: Calculating the Penalty on a Three-Sample Path
Suppose three samples form a path: samples 1 and 2 have edge weight 1, samples 2 and 3 have edge weight 1, and there is no edge between samples 1 and 3. Let their two-component scores be \(h_1=(1,0)^\mathsf{T}\), \(h_2=(0.8,0.2)^\mathsf{T}\), and \(h_3=(0,1)^\mathsf{T}\). Set \(\lambda=0.5\). The graph has two distinct edges, so the penalty can be calculated by summing once over those edges:
The second edge contributes more because its endpoint score vectors are farther apart. The penalty is zero only when the scores agree across every positive-weight edge. It does not require equality between samples that are not connected.
Gradient With Respect to the Sample Scores
For fixed \(W\), the reconstruction part has gradient \(W^\mathsf{T}(WH-X)\) with respect to \(H\). To differentiate the graph term, use the symmetry of \(L\). For a perturbation matrix \(\Delta\), the first-order change in \(\mathrm{tr}(H L H^\mathsf{T})\) is \(\mathrm{tr}(\Delta L H^\mathsf{T})+\mathrm{tr}(H L\Delta^\mathsf{T})\). Symmetry makes these two terms equal, so their sum is the inner product of \(2HL\) with \(\Delta\). Thus the graph term's gradient is \(2\lambda HL\).
The column form shows the local effect of the graph. A connected sample's graph gradient points away from its weighted neighboring-score average; a gradient-based decrease therefore tends to move its score toward those neighbors. The factor \(2\lambda\) is consistent with the objective's trace convention. Nonnegativity still constrains the fitted scores, so an optimization step must respect \(H\geq0\).
Worked Example: Computing a Graph Gradient
Use the three-sample path from the previous example, but take one score per sample: \(H=(1,2,4)\), with the two edge weights equal to 1 and \(\lambda=0.25\). For this path, the degree values are \((1,2,1)\), and the Laplacian is $$ L=\begin{pmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{pmatrix}. $$ Multiplication gives \(HL=(-1,-1,2)\), so the graph gradient is $$ 2\lambda HL=0.5(-1,-1,2)=(-0.5,-0.5,1). $$
The first two scores receive negative graph-gradient contributions and the third receives a positive one. A small unconstrained gradient-descent step subtracts the gradient: it raises the first two scores and lowers the third. This moves the scores toward one another. This calculation isolates the graph contribution; the reconstruction gradient and the nonnegativity constraint also affect an actual NMF update.
Choosing and Checking the Graph
The graph is part of the model and should have a stated interpretation. For example, edge weights might be based on a prespecified sample-similarity measure, perhaps after a suitable transformation or standardization. One common construction uses a Gaussian kernel on distances: \(A_{ij}=\exp[-d_{ij}^2/(2\tau^2)]\) for selected pairs, where \(d_{ij}\) is a distance and \(\tau>0\) controls its scale. A graph may instead keep only selected nearest-neighbor connections. These choices are not interchangeable: they determine which score differences the penalty discourages and by how much.
Worked Example: Interpreting Unequal Edge Weights
Suppose a graph has two edges, with \(A_{12}=0.8\) and \(A_{23}=0.2\), and a one-component score \(H=(1,3,4)\). Let \(\lambda=0.5\). The penalty counts each distinct edge once: $$ \begin{aligned} \lambda\left[A_{12}(h_1-h_2)^2+A_{23}(h_2-h_3)^2\right] &=0.5\left[0.8(1-3)^2+0.2(3-4)^2\right]\\ &=0.5(3.2+0.2)=1.7. \end{aligned} $$
Although the score difference on edge 2–3 is smaller, its contribution is only \(0.1\), compared with \(1.6\) for edge 1–2, because the first edge has greater weight and a larger squared difference. The weights describe the graph's chosen relationships; they do not, by themselves, establish that either pair is biologically equivalent.
Before fitting, check that graph rows and columns use the same sample ordering as \(X\) and \(H\), that the matrix is symmetric and has nonnegative weights, and that degrees and connected components are sensible for the intended application. If the graph is generated from features with very different scales, distances may reflect measurement scale rather than meaningful similarity. It is also important to consider whether the variables used to build the graph are appropriate for imposing a relationship on the scores.
During fitting, compare the reconstruction and graph contributions rather than reporting only their sum. A large graph contribution may indicate that neighboring samples remain quite different; an almost negligible contribution may mean that the graph has little influence at the chosen \(\lambda\). Neither pattern alone proves an error, but both are reasons to check the graph, the value of \(\lambda\), and the resulting scores. As with other constrained NMF objectives, numerical optimization can depend on initialization and stopping choices; use an optimizer that respects nonnegativity and assess whether the objective has stabilized.
What the Graph Penalty Does—and Does Not—Guarantee
If \(\lambda=0\), the objective reduces to ordinary squared-error NMF. As \(\lambda\) increases, the optimizer faces a greater cost for score differences across edges. This can stabilize local sample patterns, but it can also suppress meaningful variation if the graph connects samples whose scores should differ. A graph with disconnected components imposes no direct penalty between components; an isolated sample has degree zero and receives no graph-gradient contribution. A constant score vector within each connected component has zero graph penalty, but the graph term alone does not determine which constant to use.
The graph term does not guarantee that every pair of similar samples will have identical fitted scores, nor does it prove that an observed grouping is real. The reconstruction term, nonnegativity, other modeling choices, and graph topology all matter. Interpret graph-regularized scores as the result of fitting the data while favoring the relationships encoded by the chosen graph.
| Approach | What it penalizes or uses | Distinction from sample-graph regularization |
|---|---|---|
| Unregularized NMF | Reconstruction error only | Does not explicitly encourage scores of connected samples to agree. |
| Graph-regularized NMF | Weighted score differences across sample-graph edges | Uses relationships between samples, encoded in \(A\). |
| Smooth NMF for ordered features | Changes across ordered features | Acts on feature structure, rather than on sample relationships. |
The most common mistake is to interpret a graph edge as a hard equality constraint: “These two samples are connected, so their scores must be the same.” That is incorrect. An edge contributes a weighted squared difference to the objective, and the optimizer balances that cost against reconstruction error. A larger weight or \(\lambda\) makes disagreement more costly; it does not impose exact equality.
A second practical risk is choosing \(\lambda\) so large that the score patterns mainly reflect graph smoothing rather than the data. A small value can also make the intended regularization negligible. The units of reconstruction error and the scale of the graph penalty both depend on the data and graph construction, so a numerical value of \(\lambda\) is not meaningful in isolation. Report how the graph was formed and assess the effect of plausible penalty strengths.
Check Your Understanding
Answer each question, then check the solutions below.
- For an undirected graph with two samples connected by an edge of weight 3, and scores \(h_1=(1,2)^\mathsf{T}\) and \(h_2=(2,0)^\mathsf{T}\), calculate the graph penalty when \(\lambda=0.5\).
- What is the graph-gradient contribution for a sample with score \(h_i\) and neighbors \(h_j\), using the adjacency weights \(A_{ij}\)?
- What graph-gradient contribution does an isolated sample receive?
- Why does a positive graph edge not require its two samples to have identical scores?
Solutions. (1) Count the edge once: \(0.5\times3\times[(1-2)^2+(2-0)^2]=0.5\times3\times5=7.5\). The penalty is 7.5 in squared-score units, scaled by the specified weight and \(\lambda\). (2) It is \(2\lambda\sum_j A_{ij}(h_i-h_j)\), the \(i\)th column of \(2\lambda HL\). (3) Zero: all its adjacency weights and its degree are zero. (4) The edge adds a finite weighted squared-difference cost to an objective that also includes reconstruction error; the optimizer balances the terms rather than enforcing equality.