Inductive: learn a general rule, then apply it to new data points.
Transductive: reason directly about the specific unlabeled points already in hand.
Operational definition: A new data point is introduced. Do you have to redo the training? If yes, it’s transductive.
Example: 30 students in a room, 10 heights known.
height = a·(shoe size) + b on the 10 → predict any student, anywhere, forever.To understand transductive learning, we have to forget about finding a “general rule” or a “formula.” Instead, transductive learning is about solving a specific problem for a specific, known, and finite set of test data points.
Imagine a small office with exactly 5 employees: Alice, Bob, Charlie, Dave, and Eve.
We want to predict whether each person prefers Coffee or Tea. We only have labels for two people, but we know exactly who the other three people are from the very beginning.
Because we know exactly who we need to make predictions for, we don’t need to learn a general formula based on their age, height, or job title (inductive learning).
Instead, our algorithm simply relies on a hardcoded Friendship Lookup Table that maps every person in the office to their closest work friend.
The Friendship Lookup Table:
| Employee | Closest Friend |
|---|---|
| Alice | Bob |
| Bob | Alice |
| Charlie | Alice |
| Dave | Eve |
| Eve | Dave |
Our transductive algorithm is incredibly simple: Look at the unlabeled person, find their closest friend in the table, and if that friend has a known label, copy it.
Let’s execute it on our specific, pre-defined test set:
This model successfully predicted the labels for Bob, Charlie, and Dave. But here is the catch that defines transductive learning: It learned absolutely no general rules.
Inductive models build a map (a formula) so you can navigate anywhere.
Transductive models just draw a straight line between the specific places you asked to go right now. If you ask to go somewhere new later, you have to start over.
The test: a new data point is introduced. What breaks?
Hard transductive: there is nothing to transfer.
Soft transductive: the function transfers; But the training was done in the context of a specific training set. .
The parameters are a genuine reusable map on the feature axis: nothing about them is node-specific.
What binds the model to one dataset is the training procedure: full-batch propagation over a fixed graph, so test nodes were already in the room.
Operational check: could you compute an output for the new point without redoing training? Yes: recompute the local neighborhood context.
| Inductive | Transductive | |
|---|---|---|
| Shallow | Linear/logistic regression, SVM, trees, RF, XGBoost, naive Bayes, LDA, \(k\)-NN, \(k\)-means | label propagation/spreading, spectral & agglomerative clustering, DBSCAN, tSNE |
| Deep | MLP, CNN, RNN/LSTM, Transformers, autoencoders/VAEs, diffusion | N/A |
| Graph | GraphSAGE, GAT, GIN, MPNN, PinSAGE, graph transformers, any graph-level task | GCN (Kipf-Welling setting), ChebNet/spectral filters, DeepWalk, node2vec, LINE, SDNE |
alternatively PCA is inductive learning
GCN weights are trained in the context of the multiplicative normalization matrix \(\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\)
That normalization matrix is specific to the training graph
So when generalizing to a truly new graph, the weights become less reliable
Reason: they were fit under one particular normalization regime and are now evaluated under a different one
The strict sense of “transductive” here is not “weights don’t transfer” but “the training procedure presupposed you already had those nodes.”
So the “normalization regime” is a fixed, deterministic, scale-stabilizing function of whatever graph you hand it: not arbitrary per-graph calibration baked into \(W\).
The fundamental definition of variance measures the spread around the mean (\(\mu = \mathbb{E}[X]\)):
\[Var(X) = \mathbb{E}[(X - \mathbb{E}[X])^2]\]
By expanding the quadratic, we get the classic computational formula:
\[Var(X) = \mathbb{E}[X^2 - 2X\mathbb{E}[X] + (\mathbb{E}[X])^2]\]
\[Var(X) = \mathbb{E}[X^2] - 2\mathbb{E}[X]\mathbb{E}[X] + (\mathbb{E}[X])^2\]
\[Var(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2\]
Covariance extends this concept to measure the joint variability of two variables, \(X\) and \(Y\):
\[Cov(X, Y) = \mathbb{E}[(X - \mathbb{E}[X])(Y - \mathbb{E}[Y])]\]
Expanding this yields the parallel computational formula:
\[Cov(X, Y) = \mathbb{E}[XY - X\mathbb{E}[Y] - Y\mathbb{E}[X] + \mathbb{E}[X]\mathbb{E}[Y]]\]
\[Cov(X, Y) = \mathbb{E}[XY] - \mathbb{E}[X]\mathbb{E}[Y] - \mathbb{E}[Y]\mathbb{E}[X] + \mathbb{E}[X]\mathbb{E}[Y]\]
\[Cov(X, Y) = \mathbb{E}[XY] - \mathbb{E}[X]\mathbb{E}[Y]\]
Variance is simply the covariance of a variable with itself.
Substitute \(Y = X\) into the Covariance formula:
\[Cov(X, X) = \mathbb{E}[XX] - \mathbb{E}[X]\mathbb{E}[X]\]
Which directly returns our original Variance identity:
\[Cov(X, X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2 = Var(X)\]
When working with empirical data, let \(\mathbf{x}\) be an \(N \times 1\) column vector containing \(N\) observations, and \(\mathbf{1}\) be an \(N \times 1\) vector of ones.
The expected values translate perfectly into vector operations:
Substituting these into our identity \(Var = \mathbb{E}[X^2] - (\mathbb{E}[X])^2\) gives the empirical variance scalar:
\[Var(\mathbf{x}) = \frac{1}{N}\mathbf{x}^T\mathbf{x} - \left(\frac{1}{N}\mathbf{1}^T\mathbf{x}\right)^2\]
Now, let \(X\) be an \(N \times 2\) data matrix (rows are observations, columns are features \(X_1\) and \(X_2\)).
The univariate identity elegantly generalizes to the Covariance Matrix (\(\Sigma\)) by replacing the square with an outer product:
Applying the generalized identity \(\Sigma = \mathbb{E}[XX^T] - \mathbb{E}[X]\mathbb{E}[X]^T\):
If you don’t center, the two differ by a rank-one term:
\[\Sigma = \frac{1}{N}X^TX - \boldsymbol{\mu}\boldsymbol{\mu}^T\]

Four points, two features. Already centered \((\boldsymbol{\mu}=\mathbf{0})\).
\[ X=\left(\begin{array}{cc} 2 & 1 \\ 1 & 2 \\ -1 & -2 \\ -2 & -1 \end{array}\right) \quad(n=4, d=2) \]
From one data matrix, two very different products:
| Definition | Shape | Indexed by | |
|---|---|---|---|
| Covariance | \(C=X^{\top} X\) | \(d \times d=2 \times 2\) | features |
| Gram | \(G=X X^{\top}\) | \(n \times n=4 \times 4\) | data points |
Same data. One matrix grows with the number of features, the other with the number of observations.
The Covariance Matrix \((d \times d)\)
\[ C=X^{\top} X=\left(\begin{array}{cc} 10 & 8 \\ 8 & 10 \end{array}\right) \]
Eigendecomposition:The eigenvectors are directions in feature space. \(\mathbf{v}_1\) says “feature 1 and feature 2 move together.” That statement is about the variables, not about Ann or Ben.
PCA come from projecting: \(\mathbf{z}=W^{\top} \mathbf{x}\), giving (2.12, 2.12, -2.12, -2.12) on PC1.
\(W\) is the matrix whose columns are the eigenvectors of \(C\), kept in descending eigenvalue order. It’s \(d \times k\) - features by components.
\[ G=X X^{\top}=\left(\begin{array}{cccc} 5 & 4 & -4 & -5 \\ 4 & 5 & -5 & -4 \\ -4 & -5 & 5 & 4 \\ -5 & -4 & 4 & 5 \end{array}\right) \]
Same nonzero spectrum \(-\lambda=18,2\) - but the top eigenvector is
\[ \mathbf{u}_1=\frac{1}{2}(1,1,-1,-1) \]
One entry per data point. This eigenvector is the embedding: it already contains the four coordinates. There is no direction, no \(W\), nothing to apply to anything.
The Gram matrix is named after Jorgen Pedersen Gram, a Danish actuary and mathematician.
\[ z_1=\mathbf{v}_1^{\top} \mathbf{x}_5=\frac{3+2}{\sqrt{2}}=3.54 \]
Done. \(W\) is \(2 \times 2\) and does not know or care how many points it was estimated from.
\(G\) is now \(5 \times 5\). Its eigenvectors live in \(\mathbb{R}^5\), not \(\mathbb{R}^4\) - a different vector space. Every existing coordinate is recomputed. There was never a function to evaluate; the coordinates were the parameters.
Fitting more data refines \(W\). Fitting more data replaces \(\mathbf{u}\).
This is why our spectral methods are transductive.
The eigendecomposition was never the problem. What the index runs over is the problem.