Source-linked AI summary
On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Features
Emanuele Rossi, Henry Kenlay, Maria I. Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, Michael Bronstein
TL;DR
GNNs commonly assume complete node features, although real graph data often contain substantial missingness. The paper introduces Feature Propagation, which reconstructs missing features by minimizing Dirichlet energy and discretizing the resulting diffusion process before downstream GNN prediction. Across common node-classification benchmarks, FP remains robust under extreme missingness and is scalable to very large graphs.
Problem
Real-world graph feature matrices are often only partially observed, while most existing GNN models assume complete features and cannot be directly applied.
Method
Feature Propagation minimizes Dirichlet energy to derive graph diffusion, then uses its discretization as an iterative feature-reconstruction step before a downstream GNN.
Results
FP outperforms or matches competing methods across common node-classification benchmarks, with around a 4% average relative accuracy drop when 99% of features are missing.
Takeaways & Limitations
FP provides a useful and scalable reconstruction approach for downstream graph learning even when feature availability is extremely limited.
Takeaways & Limitations
FP is most suitable for homophilic graphs and can perform poorly as homophily decreases, with an extremely large gap at zero homophily.
Abstract
from arXiv · showhide
While Graph Neural Networks (GNNs) have recently become the de facto standard for modeling relational data, they impose a strong assumption on the availability of the node or edge features of the graph. In many real-world applications, however, features are only partially available; for example, in social networks, age and gender are available only for a small subset of users. We present a general approach for handling missing features in graph machine learning applications that is based on minimization of the Dirichlet energy and leads to a diffusion-type differential equation on the graph. The discretization of this equation produces a simple, fast and scalable algorithm which we call Feature Propagation. We experimentally show that the proposed approach outperforms previous methods on seven common node-classification benchmarks and can withstand surprisingly high rates of missing features: on average we observe only around 4% relative accuracy drop when 99% of the features are missing. Moreover, it takes only 10 seconds to run on a graph with $\sim$2.5M nodes and $\sim$123M edges on a single GPU.
1 Introduction
GNNs typically require complete node features, but real graphs often contain extensive missingness that limits direct application of existing models. The paper introduces Feature Propagation, a diffusion-based reconstruction step followed by a downstream GNN, and reports strong robustness, scalability, and benchmark performance.
- Motivation: Real-world feature matrices often contain missing values, so most existing GNN models cannot be directly applied.Examples include partial demographic, content, and product-description data, as well as features withheld pending user consent.
- Prior limitations: Existing graph-signal methods do not scale beyond a few thousand nodes, while recent missing-feature GNN methods lack evaluation at rates above 90% and scale poorly.The paper identifies SAT, GCNMF, and PaGNN as recent approaches with these limitations.
- Approach: Feature Propagation reconstructs missing features through diffusion-based propagation before passing the graph and reconstructed features to a downstream GNN.The reconstruction is based on Dirichlet energy minimization and discretization of a diffusion-type differential equation.
- Results: FP outperforms state-of-the-art methods on six standard node-classification benchmarks.The paper presents FP as a general approach for graph machine-learning tasks with missing node features.
- Results: 99% missing features causes around a 4% average relative accuracy drop for FP, compared with 53.33% for GCNMF and 21.25% for PaGNN.FP is also reported as generic, fast, and scalable, including approximately 10 seconds for reconstruction on a graph with 2.5M nodes and 123M edges on one GPU.
2 Preliminaries
The paper formulates missing-feature learning as transductive learning with partially observed graph features and labels. It separates feature interpolation from downstream prediction and motivates reconstruction through graph smoothness and Dirichlet energy.
- Notation: The setup assumes scalar node features for convenience, while the derivations extend straightforwardly to d-dimensional feature matrices.The graph uses a normalized-adjacency-based Laplacian and separates known and unknown node sets.
- Feature interpolation: Graph feature interpolation reconstructs unknown features from the graph structure and known features.The formulation may use an energy function expressing prior assumptions about feature behavior.
- Feature interpolation: The common smoothness prior assumes neighboring nodes have similar features, quantified using the Dirichlet energy.When feature behavior is unknown, the energy may instead be learned from data.
- Problem formulation: Learning with missing features is transductive: the graph is known, while labels and node features are only partially observed and may occur on different node subsets.The label-observed and feature-observed subsets can be different or even disjoint.
- Problem formulation: A preprocessing interpolation step can estimate a full feature vector independently of the learning task before a GNN performs prediction.The resulting model applies the downstream function to the inferred fully featured graph.
3 Feature Propagation
Feature Propagation reconstructs missing node features by minimizing Dirichlet energy through graph diffusion, then discretizes the resulting flow into a scalable iterative algorithm. The method converges, preserves known features, and produces increasingly smooth reconstructions that can be combined with downstream GNNs.
- Gradient flow: Dirichlet-energy minimization yields a graph heat-diffusion equation whose boundary conditions keep known features fixed while reconstructing missing ones.The resulting interpolation is the global minimizer of the convex Dirichlet energy.
- Closed-form solution: The closed-form solution is theoretically available, but matrix inversion costs O(|Vu|^3), making it impractical for large graphs.For connected graphs, the relevant Laplacian sub-matrix is invertible; disconnected graphs can be handled component-wise.
- Iterative scheme: Feature Propagation discretizes diffusion with an explicit Euler scheme that repeatedly propagates features through the diffusion matrix and resets known features to their true values.Unknown features may start from any values, and 40 iterations were sufficient for convergence on the authors’ datasets.
- Spectral interpretation: The Euler iteration is gradient descent on Dirichlet energy, so it progressively smooths features and acts as successive low-pass filtering.On Cora, the low-pass effect becomes stronger as the missing-feature rate increases.
- Convergence: The iterative scheme with h = 1 converges to the closed-form solution independently of the initial values assigned to unknown features.The convergence result is stated for undirected connected graphs.
- Use with GNNs: Feature Propagation extends to feature matrices by diffusing each channel independently and can supply reconstructed features to downstream GNNs for multiple graph-learning tasks.The paper focuses experimentally on node classification, while describing broader applicability to link prediction and graph classification.
- Oversmoothing: Boundary conditions prevent reconstructed features from becoming overly smooth, even when diffusion uses an extremely high number of steps.The paper distinguishes this behavior from oversmoothing caused by repeated diffusion in deep GNNs.
4 Related Work
Prior work addresses missing node features through graph-aware completion, specialized GNNs, or partial propagation, but these approaches differ in scalability and performance at high missing-feature rates. Feature Propagation instead reconstructs continuous features before a downstream GNN, unlike Label Propagation, which directly predicts labels from graph structure.
- Label Propagation: Label Propagation directly classifies nodes from graph structure, whereas Feature Propagation reconstructs continuous features before feeding them to a downstream GNN.The experiments report that FP+GNN outperforms Label Propagation even at extremely high missing-feature rates.
- Matrix completion: Classic matrix-completion methods are unaware of graph structure, while graph-signal methods incorporate it but do not scale beyond graphs with a few thousand nodes.Graph matrix completion extends matrix completion to use an underlying graph.
- Missing-feature GNNs: SAT, GCNMF, and PaGNN adapt neural models to missing features, but they struggle with high missing-feature rates and large graphs.The cited methods show reasonable performance at low missingness, whereas their limitations emerge in more demanding regimes.
- Other GNN work: Other related work studies feature-free or random-feature GNNs, Dirichlet-energy regularization, continuous graph diffusion, and feature propagation for different graph-learning settings.These directions address adjacent problems or mechanisms rather than the same missing-feature reconstruction pipeline.
5 Experiments and Discussion
Experiments evaluate Feature Propagation across benchmark datasets, missing-feature rates, runtime, and homophily levels. FP matches or outperforms alternatives, remains robust under extreme missingness, and scales to a 2.45-million-node graph, but its advantage weakens as homophily decreases.
- Node Classification Results: FP matches or outperforms other methods across missing-feature rates in benchmark node-classification experiments.Experiments use Cora, Citeseer, PubMed, Amazon-Computers, Amazon-Photo, and OGBN-Arxiv, with a 2-layer GCN downstream model in Figure 3.
- Node Classification Results: At 99% missing features, FP loses 4.12% relative accuracy on average, compared with 58.33% for GCNMF and 21.25% for PaGNN.These drops are measured against each method’s performance when all features are present.
- Node Classification Results: Most methods perform well up to 50% missing features, while performance gaps widen from around 60% and become especially large at 90% and 99%.FP is the only feature-aware method reported as robust to these high missing-feature rates across all datasets.
- Runtime: FP’s propagation takes approximately 0.6 seconds on Computers, 0.8 seconds on OGBN-Arxiv, and 10.5 seconds on OGBN-Products using one GPU.PaGNN and GCNMF run out of memory on OGBN-Products; Figure 4 reports FP as 3x faster than both other methods where runtime is reported.
- Homophily: With 99% missing features, FP performs similarly to full-feature performance at high homophily, but its accuracy gap becomes extremely large at zero homophily.In low-homophily settings, FP is only slightly better than the Zero baseline; a feature-dependent non-homogeneous diffusion is left for future work.
6 Conclusion
The paper presents Feature Propagation as an efficient approach for missing node features, with experiments indicating useful reconstruction even when 99% of features are missing. Its stated limitations concern graph homophily, graph heterogeneity, and independent treatment of feature channels.
- Feature Propagation reconstructs missing node features through diffusion before downstream graph learning and remains useful when 99% of features are missing.The method repeatedly applies a diffusion matrix and resets known features to their original values.
- The method is designed for homophilic graphs, with more general learnable diffusion suggested for low-homophily scenarios.
- Feature Propagation currently supports one node and edge type, although separate diffusions could extend it to heterogeneous graphs.
- Feature channels are treated independently, so channel mixing would be needed to model dependencies between channels.
- The authors note that broad adoption of GNNs could enable misuse with potentially detrimental societal impact.
A.1 Closed-Form Solution for Harmonic Interpolation
The appendix derives the harmonic interpolation solution by minimizing Dirichlet energy over unknown features. For connected undirected graphs, the relevant Laplacian submatrix is invertible, yielding a unique solution.
- Minimizing Dirichlet energy over unknown features gives the optimality condition Δ_uk x_k + Δ_uu x_u = 0.
- The unique harmonic-interpolation solution is x_u = −Δ_uu^-1Δ_ukx_k.
- For connected undirected graphs, the unknown-feature block of the normalized adjacency has spectral radius below 1.
- The principal submatrix of the Laplacian associated with unknown nodes is invertible.
- Invertibility follows because Δ_uu = I − Ã_uu and Ã_uu has no eigenvalue equal to 1.
A.2 Closed-Form Solution for the Euler scheme
The appendix analyzes the recursive Euler-style propagation scheme on a connected graph and states that its recursion converges to a steady state. The section’s figure context concerns accuracy under varying missing-feature rates across six benchmarks.
- The recursion is defined using the normalized adjacency and an initial feature vector on an undirected connected graph.
- The appendix states that the recursion converges and gives its steady-state expression.
- The first l rows remain fixed, so convergence analysis focuses on the remaining u rows.
- Unrolling the recursion and taking the limit yields the stationary state.
- Figure 6 reports test accuracy versus missing-feature rate on six node-classification benchmarks, using 2-layer GraphSAGE for methods requiring a downstream GNN.
A.3 Baselines’ Implementation and Tuning
The baseline implementations use dataset-specific tuning and specified preprocessing choices. Label Propagation receives a per-dataset grid search, positional encodings use twenty eigenvectors, and MGCNN uses a defined matrix-completion split.
- Label Propagation: Label Propagation is tuned separately on each dataset over α values from 0.1 through 0.99.The searched values are 0.1–0.9 in increments of 0.1, plus 0.95 and 0.99.
- Positional Encodings: Positional Encodings use the top twenty graph Laplacian eigenvectors computed with SciPy sparse eigensolver routines.
- MGCNN: MGCNN is reimplemented without its LSTM, and observed features are split into 50% input, 40% training targets, and 10% validation data.The trained model then predicts the whole feature matrix from all observed features.
A.4 Discussion Over Baselines’ Performance
Neighborhood Averaging works competitively when homophilous features are observed among neighbors, but Feature Propagation can use information from farther nodes as missingness increases. For fully missing features, Random can outperform Zero because random values distinguish nodes whereas all-zero vectors do not.
- Neighborhood Averaging: Neighborhood Averaging estimates a node’s feature by averaging neighboring features, but its variance rises when few or no neighbors have observed values.This assumes a single homophilous feature channel.
- Feature Propagation: Feature Propagation repeatedly diffuses information across the graph, allowing estimation from more distant nodes when nearby features are unavailable.The gap over Neighborhood Averaging becomes increasingly significant at higher missing-feature rates.
- Zero versus Random: Zero is easier for a GNN to ignore than Random values, which corrupt weighted neighbor averages and cannot be distinguished from genuine non-zero features.The comparison concerns how missing-value baselines affect message aggregation.
- Zero versus Random: Random performs better than Zero when all features are missing because random features act as node signatures, whereas identical zero vectors leave nodes nearly indistinguishable.With all-zero inputs, post-GNN embeddings remain very similar and task performance approaches random guessing.