PropEnc: A Property Encoder for Graph Neural Networks

Anwar Said, Waseem Abbas, Xenofon KoutsoukosarXiv 2024 · arXiv

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.

Fig. 1: Illustration of features dimensionality for five well- known featureless graph classification datasets. For large datasets such as Reddit (RDT), where the graph sizes reach thousands of nodes, the feature dimensionality cor- respondingly escalates significantly. Specifically, the maxi- mum number of nodes (largest graph) in these datasets are 136, 89, 492, 3782, 3648, 3782, respectively.

Methods

The authors propose PropEnc, a simple two-step framework that treats feature dimensionality as a controllable hyperparameter rather than a dataset-dependent constraint:

  1. 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.
  2. Reversed One-Hot Frequency Indexing: Instead of encoding the raw metric value, each node is assigned a $d$-dimensional binary vector. A value of 1 is placed at the index corresponding to the specific histogram bin where the node's metric value falls, and 0 elsewhere.

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.

Fig. 2: Comparison of the number of parameters between the proposed PropEnc and one-hot degree encoding. The increase in the dimension of features results in an increase in the number of parameters.

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:

  1. Systematically investigating which specific structural or positional metrics work best for different graph topologies.
  2. Exploring how to optimally combine these encoded topological features with original node attributes when partial data is available.

Summary updated

Abstract

Graph machine learning, particularly using graph neural networks, heavily relies on node features. However, many real-world systems, such as social and biological networks, lack node features due to privacy concerns, incomplete data, or collection limitations. Structural and positional encoding are commonly used to address this but are constrained by the maximum values of the encoded properties, such as the highest node degree. This limitation makes them impractical for scale-free networks and applications involving large or non-categorical properties. This paper introduces PropEnc, a novel and versatile encoder to generate expressive node embedding from any graph metric. By combining histogram construction with reversed index encoding, PropEnc offers a flexible solution that supports low-dimensional representations and diverse input types, effectively mitigating sparsity issues while improving computational efficiency. Additionally, it replicates one-hot encoding or approximates indices with high accuracy, making it adaptable to a wide range of graph applications. We validate PropEnc through extensive experiments on graph classification task across several social networks lacking node features. The empirical results demonstrate that PropEnc offers an efficient mechanism for constructing node features from various graph metrics.
BibTeX
@misc{said2024propenc,
  author = {Anwar Said and Waseem Abbas and Xenofon Koutsoukos},
  title = {{PropEnc: A Property Encoder for Graph Neural Networks}},
  year = {2024},
  eprint = {2409.11554},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.11554},
}
Figure