Feature Construction Using Network Control Theory and Rank Encoding for Graph Machine Learning

Anwar Said, Yifan Wei, Obaid Ullah Ahmad, Mudassir Shabbir, Waseem Abbas, Xenofon KoutsoukosarXiv 2025 · arXiv

TL;DR

Graph Neural Networks (GNNs) struggle when node features are missing, a common issue in privacy-sensitive social networks. This paper introduces a framework that uses Network Control Theory—specifically average controllability—combined with a novel "rank encoding" method to automatically build expressive, fixed-dimensional node features from graph topology alone, significantly boosting classification performance.

What Problem Does This Paper Address?

GNNs rely heavily on high-quality node features to perform downstream tasks like graph classification. However, in many real-world scenarios, such as social networks, node features are completely absent due to privacy constraints or a lack of inherent attributes.

The standard workaround is using one-hot encoded node degrees as surrogate features. However, this approach leads to sparse, high-dimensional vectors that scale poorly (especially in power-law networks) and fail to capture continuous structural properties. The authors address the challenge of creating dense, expressive, and computationally efficient node features purely from a graph's topology.

Methods

The authors propose two main strategies to enrich unattributed graphs:

  1. NCT-EFA (Network Control Theory and Essential Feature Augmentation): They leverage average controllability, a concept from Network Control Theory that quantifies a node's ability to steer the overall network's dynamics when external control energy is applied. They combine this control-theoretic metric with traditional network science centralities (closeness, betweenness, and eigenvector centrality) to form a comprehensive structural feature vector for each node.
  2. Rank Encoding: To avoid the high dimensionality and sparsity of traditional one-hot degree encoding, they introduce a histogram-based rank encoding scheme. Continuous or discrete scalar metrics are divided into $k$ bins across the graph. Each node's metric value is mapped to its corresponding bin index, which is then one-hot encoded. This preserves the relative distribution of structural properties while keeping the feature space compact and fixed-dimensional.
Figure 1: Illustration of the proposed NCT-EFA framework: Starting with a simple graph, NCT-EFA leverages network control theory and network science metrics to enrich node features. These enhanced graphs are then used to train a GNN for the downstream classification task. Here, xi ∈X refers to the node feature initialized in the feature construction module.
Figure 2: Illustration of the proposed rank encoding scheme. Initially, desired centrality metrics are computed. Each metric is then transformed into a one-hot encoded vector. These encoding are concatenated to form a unified feature vector for each node. The augmented graph is subsequently used to train a GNN for the social network classification task.

Datasets

The method was evaluated on four standard social network benchmarks for graph classification:

  • Reddit Threads: 203,088 graphs; distinguishing between discussion and non-discussion based threads.
  • GitHub Stargazers: 12,725 graphs; classifying developer networks into web development or machine learning repositories.
  • Twitch Ego Nets: 127,094 graphs; predicting whether an ego user plays a single game or multiple games.
  • Deezer Ego Nets: 9,629 graphs; predicting the gender of the ego user based on network structure.

Key Insights and Ideas

  • Control as a Proxy for Influence: Network Control Theory provides a unique lens for GNN initialization. Instead of just looking at static connectivity (like degree), average controllability captures how easily a node can propagate information or energy through linear dynamics, encoding implicit causal influence.
  • Distribution Matters More Than Absolute Values: The success of Rank Encoding shows that a GNN benefits more from knowing a node's relative rank or position within the graph's overall metric distribution than its raw, absolute centrality value.
  • Task-Dependent Feature Importance: The topological features heavily boosted performance on GitHub and Twitch but slightly lagged behind raw degree encoding on Deezer. This reveals that certain tasks (like gender prediction in specific ego networks) might rely purely on local connectivity (degree) rather than global control dynamics.

Key Results

  • Substantial Performance Gains: On the GitHub Stargazers dataset, incorporating NCT-EFA features led to a 7.66% improvement in ROC AUC using GraphSAGE compared to standard degree encoding.
  • Rank Encoding Superiority: Replacing traditional one-hot degree encoding with the proposed rank encoding method boosted GraphSAGE's ROC AUC from 68.7% to 73.9% on GitHub Stargazers, underscoring its efficiency.
  • Robustness to Bin Size: Evaluating different bin sizes ($k = 10, 20, 30$) showed that while performance varies across datasets, larger bin sizes ($k=30$) generally yielded the best results for the Reddit and GitHub datasets.

Limitations and Future Work

  • Computational Complexity: Calculating average controllability requires computing the controllability Gramian, which incurs a worst-case time complexity of $O(n^3)$, where $n$ is the number of nodes. While highly tractable for smaller ego-networks (e.g., the maximum of 97 nodes per graph in the Reddit dataset), it remains a bottleneck for massive, monolithic graphs.
  • Future Directions: The authors suggest exploring low-rank approximations, incremental updates, or spectral methods to scale the controllability calculations for large-scale or dynamic graphs. They also propose embedding control-theoretic principles directly into the GNN's message-passing mechanism itself, rather than just using them as static initial features.

Summary updated

Abstract

In this article, we utilize the concept of average controllability in graphs, along with a novel rank encoding method, to enhance the performance of Graph Neural Networks (GNNs) in social network classification tasks. GNNs have proven highly effective in various network-based learning applications and require some form of node features to function. However, their performance is heavily influenced by the expressiveness of these features. In social networks, node features are often unavailable due to privacy constraints or the absence of inherent attributes, making it challenging for GNNs to achieve optimal performance. To address this limitation, we propose two strategies for constructing expressive node features. First, we introduce average controllability along with other centrality metrics (denoted as NCT-EFA) as node-level metrics that capture critical aspects of network topology. Building on this, we develop a rank encoding method that transforms average controllability or any other graph-theoretic metric into a fixed-dimensional feature space, thereby improving feature representation. We conduct extensive numerical evaluations using six benchmark GNN models across four social network datasets to compare different node feature construction methods. Our results demonstrate that incorporating average controllability into the feature space significantly improves GNN performance. Moreover, the proposed rank encoding method outperforms traditional one-hot degree encoding, improving the ROC AUC from 68.7% to 73.9% using GraphSAGE on the GitHub Stargazers dataset, underscoring its effectiveness in generating expressive and efficient node representations.
BibTeX
@misc{said2025feature,
  author = {Anwar Said and Yifan Wei and Obaid Ullah Ahmad and Mudassir Shabbir and Waseem Abbas and Xenofon Koutsoukos},
  title = {{Feature Construction Using Network Control Theory and Rank Encoding for Graph Machine Learning}},
  year = {2025},
  eprint = {2507.15195},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.15195},
}
Figure