Label Propagation for Semi-Supervised Graph Learning

Label propagation is one of the oldest and most intuitive ideas in graph-based machine learning: if two nodes are connected, they probably share the same label. By iteratively spreading known labels through edges, you can assign soft labels to unlabeled nodes using only graph structure and a small labeled seed set. This article explains the algorithm, its iterative mechanics, its implementation in TGraphX, and how it compares to training a full GNN when labeled data is scarce.

What This Builds On

This tutorial assumes familiarity with basic graph concepts — nodes, edges, adjacency matrices — and a working Python environment with TGraphX installed. You do not need a GPU; label propagation is a CPU-bound iterative algorithm, not a neural method. Readers who want context on how graph structure relates to learning may find the graph mining overview and the knowledge graph embedding article useful background.

Label propagation belongs to a family of semi-supervised methods that assume the manifold hypothesis: the decision boundary should pass through low-density regions, and nearby points (nodes connected by edges) should share the same label. On graphs, connectivity is explicit rather than inferred from feature distance, which makes the manifold assumption particularly natural.

The Label Propagation Algorithm

The algorithm maintains a label matrix F of shape [N, C] where N is the number of nodes and C is the number of classes. The entry F[i, c] represents node i's current belief that it belongs to class c.

The update rule at each iteration is:

F^(t+1) = α · A_norm · F^(t) + (1 - α) · Y
        

Where A_norm is the row-normalized (or symmetric-normalized) adjacency matrix, Y is the initial label matrix with known labels fixed and zeros for unlabeled nodes, and α is a propagation factor typically between 0.8 and 0.99. The (1 - α) term clamps the known labels so they do not drift — labeled nodes are always pulled back toward their ground truth assignment after every propagation step.

This has a closed-form solution:

F* = (1 - α) · (I - α · A_norm)^{-1} · Y
        

In practice, iterating the recurrence is cheaper than computing the matrix inverse when graphs are large. Most implementations run for a fixed number of steps (50–200) or until convergence is detected via the change in F between iterations.

Using TGraphX's Label Propagation

TGraphX exposes label propagation through the tgraphx.mining.label_prop module. The interface follows the sklearn-style estimator pattern: you call fit with the graph and label information, then retrieve propagated labels.

import torch
        from tgraphx import Graph
        from tgraphx.mining.label_prop import LabelPropagation
        
        # Build a small example graph
        edge_index = torch.tensor([
            [0, 1, 1, 2, 3, 4, 4, 5],
            [1, 0, 2, 1, 4, 3, 5, 4],
        ], dtype=torch.long)
        
        # Node features (optional for label prop; only structure is used)
        x = torch.randn(6, 16)
        
        g = Graph(node_features=x, edge_index=edge_index)
        
        # Known labels: nodes 0 and 5 are labeled (classes 0 and 1)
        # -1 marks unlabeled nodes
        labels = torch.tensor([0, -1, -1, -1, -1, 1], dtype=torch.long)
        
        model = LabelPropagation(num_layers=50, alpha=0.9)
        out = model(g.edge_index, labels, num_nodes=6)
        
        print(out.argmax(dim=-1))  # predicted class for each node
        

The output out is a soft label matrix [N, C]. The argmax gives hard predictions. Labeled nodes should recover their original labels exactly (or very nearly, depending on alpha).

Iterative Mechanics: What Actually Happens

It helps to trace one propagation step manually. After initialization, labeled nodes have a one-hot row in F and unlabeled nodes have a zero row. After the first propagation step:

• Each node receives a weighted average of its neighbors' current beliefs.
• Labeled nodes are then partially reset toward their ground truth: their row becomes α * (weighted_neighbor_average) + (1 - α) * one_hot.
• Unlabeled nodes receive only the first term: α * (weighted_neighbor_average).

After many iterations, the beliefs stabilize. Nodes that are densely connected to labeled nodes of one class end up with high probability for that class. Nodes sitting on structural bridges between two labeled clusters end up with mixed beliefs — this uncertainty is genuine and useful, not a bug.

The convergence speed depends on the spectral gap of the graph. Dense, well-connected graphs converge in fewer iterations. Sparse graphs or graphs with many weak bridges may need more iterations or a smaller alpha.

Iterative Propagation in Pure PyTorch

For readers who want to understand the mechanics before using the module:

import torch
        import torch.nn.functional as F
        
        def label_propagation(edge_index, labels, num_nodes, num_classes, alpha=0.9, num_iters=50):
            # Build Y: initial soft labels
            Y = torch.zeros(num_nodes, num_classes)
            labeled_mask = labels >= 0
            Y[labeled_mask] = F.one_hot(labels[labeled_mask], num_classes).float()
        
            # Build row-normalized adjacency (add self-loops)
            row, col = edge_index
            # Degree vector
            deg = torch.zeros(num_nodes).scatter_add(0, row, torch.ones(row.size(0)))
            deg_inv = deg.pow(-1).clamp(max=1e9)
        
            F_mat = Y.clone()
            for _ in range(num_iters):
                # Aggregate: sum neighbor values, normalize by degree
                agg = torch.zeros_like(F_mat)
                agg.scatter_add_(0, col.unsqueeze(1).expand(-1, num_classes), F_mat[row])
                agg = agg * deg_inv.unsqueeze(1)
                # Update
                F_mat = alpha * agg + (1 - alpha) * Y
        
            return F_mat
        
        # Example usage
        edge_index = torch.tensor([[0,1,1,2,3,4],[1,0,2,1,4,3]], dtype=torch.long)
        labels = torch.tensor([0, -1, -1, 1, -1, -1])
        result = label_propagation(edge_index, labels, num_nodes=5, num_classes=2)
        print(result)
        

This bare implementation omits symmetric normalization and self-loops that production code would include, but shows the core loop clearly.

Label Propagation vs GNN Approaches

Label propagation ignores node features entirely — only graph structure matters. This is a significant difference from GNN-based semi-supervised classifiers like GraphSAGE or GAT, which propagate learned feature representations. The practical consequences:

When node features are highly informative (for example, in citation networks where paper abstracts distinguish classes well), a trained GNN will substantially outperform label propagation. When features are noisy, absent, or uninformative, label propagation can match or even exceed shallow GNNs.

Label propagation is also transductive: it produces predictions only for nodes present at fit time. A trained GNN can generalize to unseen nodes by running a forward pass. If your graph is dynamic or you need to classify new nodes that arrive after training, a GNN is the better choice.

Label propagation requires no training in the gradient-descent sense. There are no parameters to optimize, no learning rate to tune, no GPU required. For small graphs (up to a few hundred thousand nodes), a few iterations of label propagation can run in under a second on a laptop CPU.

When to Use Label Propagation

Label propagation is the right starting point when:

• You have very few labeled nodes (under 5 labels per class) and do not trust that a GNN will generalize from so few examples.
• Your node features are weak or absent and the graph structure is your primary signal.
• You need a fast, interpretable baseline before committing to a full GNN training pipeline.
• You want to pre-propagate labels to create weak supervision for a downstream model.

It is less appropriate when:

• Your graph is heterogeneous and the homophily assumption (connected nodes share labels) does not hold.
• You need to scale to graphs with hundreds of millions of edges (though approximate variants exist).
• You need to generalize to new nodes not seen at fit time.

Limitations and Honest Notes

Label propagation's core assumption is homophily — nodes connected by edges share labels more often than not. This holds for citation networks and social networks with community structure, but breaks on heterophilic graphs (e.g., bipartite interaction networks, fraud rings where fraudulent nodes connect to legitimate ones).

The alpha hyperparameter has a large effect on results. High alpha (close to 1.0) allows labels to propagate far from the seed set but makes labeled nodes less anchored. Low alpha keeps predictions close to the labeled nodes and may fail to reach distant unlabeled nodes in sparse graphs. Cross-validating alpha over the labeled set is important, though the small number of labeled nodes makes reliable cross-validation difficult.

Label propagation does not produce calibrated probabilities. The soft output F[i] should be treated as a ranking score, not a true posterior probability. Applying softmax to the output is nonstandard and not theoretically motivated.

The iterative form converges only when alpha < 1. Near alpha = 1, convergence can be very slow. Always check whether the output has stabilized before treating results as final.

Connecting to the TGraphX Ecosystem

Label propagation can serve as more than a standalone classifier. Several integration patterns are worth knowing:

Warm-starting a GNN: Run label propagation first to generate soft pseudo-labels for all unlabeled nodes. Use these pseudo-labels as additional supervision when training a GNN. This technique is especially effective when labeled nodes are very sparse (fewer than 5 per class) because label propagation can provide weak supervision for nodes that a GNN would otherwise receive no gradient signal from.

Feature initialization: In some formulations, label propagation is run not on class labels but on node feature vectors. The propagated features serve as an additional input to a downstream classifier. This is sometimes called "feature smoothing" and is related to the spectral low-pass filtering interpretation of message passing.

Post-processing GNN outputs: Run label propagation on the logits or softmax outputs of a trained GNN. This is sometimes called "label smoothing post-processing" and can sharpen predictions in high-confidence regions of the graph. The Correct and Smooth (C&S) method (Huang et al., 2020) formalizes this two-step approach and achieves competitive results on citation benchmarks.

Community seeding: Use label propagation as a fast pre-processor to identify high-confidence nodes in each class, then train a GNN only on those high-confidence nodes as an expanded labeled set. This semi-automated labeling pipeline can meaningfully expand the effective training set without requiring human annotation.

For experiment tracking when combining label propagation with GNN training, TGraphX's tgraphx.tracking module can log both the propagation step and the downstream model training as part of the same experiment record.

Debugging Label Propagation

A few common failure modes and their diagnostics:

All predictions collapse to one class: This usually means one class dominates the labeled set by count, and the propagation is sweeping through the graph before the minority classes can establish a footprint. Check label balance in your seed set. If possible, ensure at least 1 seed per class.

Propagation does not reach distant nodes: With a sparse graph and many components, label propagation cannot cross disconnected components. Isolated nodes or small components will have the same uniform prediction regardless of the labeled nodes. Check your graph connectivity — tgraphx.doctor provides connectivity diagnostics.

Results are identical across different alpha values: This can happen when the labeled nodes are so densely connected that the labels propagate fully regardless of alpha. Or when the graph is a single clique and averaging produces the same result for any alpha.

Convergence is extremely slow: If alpha is very close to 1.0 and the graph has a small spectral gap, the iteration converges slowly. Reduce alpha to 0.85–0.90 or increase the maximum number of iterations.

Frequently Asked Questions

Can label propagation use edge weights?
Yes. The adjacency normalization can incorporate edge weights directly. Replace the binary edge presence with the weight value during the aggregation step. TGraphX's implementation accepts an optional edge_weight argument.

Does label propagation work on directed graphs?
Technically yes, but you lose the convergence guarantee that comes from the symmetric adjacency assumption. On directed graphs, the behavior depends heavily on graph topology and is less predictable.

How does this relate to PageRank?
PageRank is structurally similar: both iterate a weighted propagation over the graph. PageRank propagates a single scalar (page authority). Label propagation propagates a vector of class beliefs. The math is nearly identical.

What if I have no labels at all?
Then label propagation cannot be applied. You need at least one labeled node per class. For the fully unsupervised case, community detection (see tgraphx.mining.communities) or spectral clustering is more appropriate.