On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Features

2021/11/23 by Emanuele Rossi, Rossi, Emanuele, Henry Kenlay +9 · 8 citations
Computer Science · #Advanced Graph Neural Networks #Topic Modeling #Recommender Systems and Techniques

paper · pdf · doi:10.48550/arxiv.2111.12128

Abstract

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 ∼2.5M nodes and ∼123M edges on a single GPU.

Citations

• Auto-Encoding Variational Bayes
• Neural Message Passing for Quantum Chemistry
• Graph Convolutional Matrix Completion
• Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs

Cited by

• Mitigating Structural Overfitting: A Distribution-Aware Rectification Framework for Missing Feature Imputation
• FGC-Comp: Adaptive Neighbor-Grouped Attribute Completion for Graph-based Anomaly Detection
• Learning Cell-Aware Hierarchical Multi-Modal Representations for Robust Molecular Modeling
• Beyond the Laplacian: Interpolated Spectral Augmentation for Graph Neural Networks
• Multi-View Graph Feature Propagation for Privacy Preservation and Feature Sparsity
• Are LLMs Better GNN Helpers? Rethinking Robust Graph Learning under Deficiencies with Iterative Refinement
• Graph Your Own Prompt
• On the Impact of Downstream Tasks on Sampling and Reconstructing Noisy Graph Signals

Related

• Mitigating Structural Overfitting: A Distribution-Aware Rectification Framework for Missing Feature Imputation
• Confidence-Based Feature Imputation for Graphs with Partially Known Features
• Should Graph Neural Networks Use Features, Edges, Or Both?
• MDS-GNN: A Mutual Dual-Stream Graph Neural Network on Graphs with Incomplete Features and Structure
• Oldie but Goodie: Re-illuminating Label Propagation on Graphs with Partially Observed Features