TL;DR
SGHFP (Self-supervised Guided Hypergraph Feature Propagation) is a novel framework designed to classify graph nodes even when the vast majority of their features are missing. By using hypergraphs to model complex, multi-node relationships and iteratively refining features through self-supervision, the method maintains high accuracy even when 99% of node data is absent.
What Problem Does This Paper Address?
Graph Neural Networks (GNNs) have revolutionized how we analyze networked data, from social media to molecular structures. However, most GNNs share a common "Achilles' heel": they assume that every node in the graph has a complete set of features (attributes).
In the real world, data is messy. Users might hide their age or gender for privacy, or sensors might fail to record specific metrics. When features are missing, GNN performance plummets. Existing solutions often rely on simple "Feature Propagation" (FP), which only looks at pairwise connections between nodes and treats all neighbors as equally influential. This paper argues that these methods are too simplistic to capture the complex, higher-order correlations inherent in real-world data.
Methods
The authors introduce SGHFP, which shifts the paradigm from simple graphs to hypergraphs. While a standard graph edge connects exactly two nodes, a hyperedge can connect any number of nodes, allowing the model to capture group-level dynamics.
The core of SGHFP is an iterative, two-pronged approach:
- Hypergraph Fusion: The model constructs two distinct hypergraphs:
- Feature Hypergraph ($G_f$): Built using the available (and partially reconstructed) node features.
- Pseudo-label Hypergraph ($G_{pl}$): Generated by passing the current features through a two-layer GNN to predict "pseudo-labels." Nodes predicted to be in the same class are linked via hyperedges.
- These two are fused into a single propagation matrix ($\Theta$) that better describes the local geometric distribution of the data.
- Iterative Propagation: Using the fused hypergraph, the model propagates known feature information to "fill in" the missing values. This is mathematically framed as minimizing Dirichlet energy, a technique used to ensure that the reconstructed features vary smoothly across the graph.
- Clamping: After each propagation step, the "known" features are reset to their original true values to prevent the model from drifting away from ground-truth data.
Datasets
The researchers evaluated SGHFP on four widely-used benchmarks:
- Cora, CiteSeer, and PubMed: Standard citation networks where nodes are papers and edges are citations.
- Photo: An Amazon dataset where nodes represent goods and edges indicate that items were frequently bought together.
The team tested these datasets under extreme conditions, simulating missing feature rates of 50%, 90%, and even 99%.
Key Insights and Ideas
- Beyond Pairwise: The transition to hypergraphs is the "aha moment." By grouping nodes into hyperedges based on both feature similarity and predicted class labels, the model can "triangulate" missing data much more effectively than looking at one neighbor at a time.
- Self-Supervision as a Guide: Using a GNN to create a pseudo-label hypergraph creates a virtuous cycle. As the feature reconstruction improves, the pseudo-labels become more accurate, which in turn creates a better hypergraph for the next round of reconstruction.
- Robustness to Data Loss: The most surprising insight is how little data the model actually needs. The "geometric distribution" of the graph structure itself contains enough latent information to reconstruct features with remarkable fidelity.
Key Results
- Superior Accuracy: SGHFP consistently outperformed standard Feature Propagation (FP) and other state-of-the-art methods like GCNMF and PaGNN across all datasets.
- Resilience to Extreme Scarcity: On the Cora dataset with 99% missing features, SGHFP achieved 79.41% accuracy. For comparison, the same model with 0% missing features achieved 81.23%—meaning the model lost only ~2.67% accuracy despite losing 99% of its input features.
- Better Clustering: t-SNE visualizations (a way to map high-dimensional data into 2D) showed that SGHFP produced much tighter, more distinct clusters of node classes compared to traditional methods, proving that the reconstructed features were high-quality.
Limitations and Future Work
The authors note one significant limitation: SGHFP is designed for homogeneous graphs (where all nodes and edges are of the same type). It does not currently perform well on heterogeneous graphs (e.g., a graph containing both "users" and "products" as different node types).
Future Work: The researchers suggest exploring more general, learnable diffusion matrices that could adapt to the complexities of heterogeneous networks, potentially making SGHFP applicable to even more diverse real-world scenarios.
Summary updated