TL;DR
PropEnc (Property Encoder) is a versatile, low-dimensional encoding scheme designed to initialize node features in graphs that lack inherent attributes. By mapping arbitrary graph metrics—whether discrete like node degree or continuous like PageRank—into user-defined histogram bins, PropEnc eliminates the dimensionality explosion and data sparsity issues common to traditional one-hot encodings while maintaining or improving GNN performance.
What Problem Does This Paper Address?
Graph Neural Networks (GNNs) rely heavily on initial node features to execute their iterative message-passing algorithms. However, many real-world graphs (such as social, financial, or biological networks) are "unattributed" or featureless due to privacy restrictions or incomplete data collection.
To bypass this, researchers typically generate structural features, most commonly by one-hot encoding the node degree. While straightforward, this approach suffers from a major flaw: in scale-free networks, a few hub nodes have massive degrees, forcing the one-hot vector size to match the maximum degree in the entire dataset. As shown in Figure 1, this causes a massive explosion in feature dimensionality (exceeding 3,000 dimensions for Reddit datasets), leading to extreme data sparsity and heavy computational overhead. Furthermore, standard one-hot encoding cannot handle continuous decimal metrics like PageRank or betweenness centrality, limiting the structural variety available to the GNN.
Methods
The authors propose PropEnc, a simple two-step framework that treats feature dimensionality as a controllable hyperparameter rather than a dataset-dependent constraint:
- Global Histogram Construction: First, a chosen graph metric (e.g., degree, PageRank, or closeness centrality) is calculated for all nodes. A global histogram is then constructed across the entire search space using a user-specified number of bins ($d$) and range.
- Reversed One-Hot Frequency Indexing: Instead of encoding the raw metric value, each node is assigned a $d$-dimensional binary vector. A value of
1is placed at the index corresponding to the specific histogram bin where the node's metric value falls, and0elsewhere.
This approach ensures that nodes with similar structural properties are naturally grouped into proximate bins, and it strictly caps the feature dimension to $d$ (typically between 10 and 50).
Datasets
The method was evaluated on six well-known featureless graph classification benchmarks from the TU Dataset repository:
- Small-scale networks: IMDB-BINARY, IMDB-MULTI, and COLLAB.
- Large-scale scale-free networks: REDDIT-BINARY, REDDIT-MULTI-5K, and REDDIT-MULTI-12K.
Key Insights and Ideas
- Decoupling Dimension from Data: PropEnc transforms feature size into a tunable hyperparameter. This prevents a single high-degree node from inflating the feature space of the entire dataset.
- Unifying Continuous and Discrete Metrics: By leveraging histogram binning, continuous decimal-based centralities (like PageRank and Eigenvector centrality) can be seamlessly converted into compact binary vectors, opening up a broader toolkit for feature initialization.
- Sparsity Reduction Boosts Learning: Compressing the feature space from thousands of dimensions down to 10–50 dimensions significantly reduces the number of parameters in the GNN's first layer. This reduction in model complexity mitigates overfitting and improves generalization on large graphs.
Key Results
PropEnc demonstrates a clear advantage on large-scale datasets where dimensionality reduction matters most. For instance, on REDDIT-BINARY, PropEnc using node degree with just 50 dimensions achieved an accuracy of 91.60%, outperforming standard one-hot degree encoding (82.40%).
Crucially, as illustrated in Figure 2, PropEnc achieves these competitive or superior accuracy marks while drastically reducing the model's parameter footprint compared to standard one-hot encoding.
Additionally, PropEnc successfully unlocked continuous metrics: using it to encode closeness centrality yielded the highest overall accuracy on REDDIT-BINARY (92.10%), proving that alternative centrality measures can be highly effective when encoded properly.
Limitations and Future Work
While PropEnc is highly effective for unattributed networks, the paper primarily evaluates it in scenarios where zero node features are initially present. The authors note that promising avenues for future work include:
- Systematically investigating which specific structural or positional metrics work best for different graph topologies.
- Exploring how to optimally combine these encoded topological features with original node attributes when partial data is available.
Summary updated