Feature Propagation: Spreading Known Features to Unlabeled Nodes

Feature propagation spreads known labels or features to unlabeled nodes using graph structure. In real-world graphs, many nodes have incomplete or missing features. A new customer has no purchase history. A recently added product has no reviews. A newly discovered entity in a knowledge graph has no attributes. Feature propagation fills in these gaps by diffusing information from feature-rich neighbors to feature-poor nodes.

This is the graph-structured equivalent of data imputation, but instead of using column-level statistics (mean, median), it uses the local graph neighborhood. A new customer connected to high-spending customers gets high-spending-like features, not the global average.

How it works

Feature propagation is iterative:

1. Initialize: nodes with known features keep their values. Nodes with missing features start at zero (or random).
2. Propagate: each missing-feature node takes the weighted average of its neighbors' current features.
3. Anchor: known-feature nodes reset to their original values (they are not overwritten).
4. Repeat: iterate steps 2-3 until convergence (typically 10-50 iterations).

import torch
from torch_geometric.nn import MessagePassing
from torch_geometric.utils import add_self_loops, degree

def feature_propagation(x, edge_index, known_mask, num_iterations=40):
    """
    Propagate known features to nodes with missing features.

    x: [num_nodes, num_features] - feature matrix (zeros for missing)
    known_mask: [num_nodes] bool - True for nodes with known features
    """
    original_features = x.clone()

    edge_index, _ = add_self_loops(edge_index)
    row, col = edge_index
    deg = degree(col, x.size(0))
    deg_inv = 1.0 / deg.clamp(min=1)

    for _ in range(num_iterations):
        # Aggregate neighbor features (mean)
        out = torch.zeros_like(x)
        out.index_add_(0, col, x[row])
        out = out * deg_inv.unsqueeze(-1)

        # Anchor: keep known features, update only missing
        x = torch.where(known_mask.unsqueeze(-1), original_features, out)

    return x

# 1000 nodes, 80% have features, 20% missing
known_mask = torch.rand(1000) > 0.2
x_imputed = feature_propagation(x, edge_index, known_mask)

Enterprise example: cold-start customers

An e-commerce platform has 1 million customers. 800,000 have complete profiles (age, spending patterns, product preferences). 200,000 are new with minimal data. The customer-product interaction graph connects customers to their purchased items.

Feature propagation for new customers:

• New customer Alice bought 2 products
• Those products were also bought by 50 other customers with full profiles
• Feature propagation averages those 50 customers' profiles
• Alice gets imputed features reflecting her purchase-based cohort

This is more informative than zero-filling or mean imputation because it places Alice in the right neighborhood of customer space based on her behavior, not demographics.

When to use feature propagation

• Cold start: new entities with no history (new users, new products)
• Incomplete records: some data sources have gaps (missing demographics, missing attributes)
• Data integration: merging datasets with different column coverage
• Dynamic graphs: newly added nodes need features before the GNN runs