Improving Graph Machine Learning Performance Through Feature Augmentation Based on Network Control Theory

Anwar Said, Obaid Ullah Ahmad, Waseem Abbas, Mudassir Shabbir, Xenofon KoutsoukosarXiv 2024 · arXiv

TL;DR

This paper introduces NCT-EFA, a framework that uses Network Control Theory (NCT) to generate rich node features for Graph Neural Networks (GNNs) when real-world data is missing or sparse. By augmenting graphs with "average controllability" and traditional centrality metrics, the authors achieved performance boosts of up to 11% in graph classification tasks.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) are incredibly powerful, but they have a "cold start" problem: their performance depends heavily on the quality of initial node features. In many real-world scenarios—such as privacy-protected social networks or incomplete datasets—node-level information is missing entirely.

The standard fallback is to use "one-hot degree encoding" (representing a node by its number of connections). However, this is a rudimentary structural proxy that fails to capture the complex, dynamic roles nodes play within a system. The authors aim to bridge this gap by borrowing tools from control engineering to better describe a node's functional importance.

Methods

The authors propose NCT-based Enhanced Feature Augmentation (NCT-EFA). The core idea is to treat the graph as a dynamic system and calculate how much "control" each node exerts over that system.

  1. Average Controllability: This is the star of the show. Derived from the controllability Gramian ($W$), it quantifies a node's intrinsic ability to steer the entire network's state toward a desired goal through external inputs. It captures how control energy proliferates through the architecture.
  2. Centrality Metrics: To provide a holistic view, they also include:
  3. Closeness Centrality: How quickly a node can interact with others.
  4. Betweenness Centrality: How often a node acts as a "bridge" between others.
  5. Eigenvector Centrality: A node's influence based on the influence of its neighbors.
  6. Rank One-Hot Encoding: Instead of using raw scalar values for average controllability, the authors propose a novel encoding scheme. They create a histogram of controllability values across the graph and use one-hot vectors to represent which "bin" a node falls into. This helps the GNN better distinguish between different tiers of influential nodes.
Illustration of the NCT-EFA framework, showing the pipeline from a raw graph to feature construction and GNN classification.

Datasets

The framework was evaluated on two binary graph classification tasks:

  • Reddit Threads: Classifying whether a thread facilitates active discussion or not (203,088 graphs).
  • GitHub Stargazers: Classifying developer networks as either "web development" or "machine learning" based on their starring patterns (12,725 graphs).

Key Insights and Ideas

  • Dynamics vs. Statics: Traditional network science (centrality) often looks at static paths. NCT looks at dynamic influence—how information or energy propagates over time. This provides a "window" into the network's innate information flow that simple degree counts miss.
  • Controllability is a "Super-Feature": The authors found that average controllability alone is a massive upgrade over degree encoding. In their ablation studies, using just this one NCT metric provided gains nearly as high as the full feature set.
  • Topology Sensitivity: The performance gains were much higher on the GitHub dataset than on Reddit. This suggests that in some networks, the raw topology is already highly informative, while in others (like GitHub), the functional role of nodes (captured by NCT) is the missing key to high accuracy.

Key Results

The authors tested NCT-EFA across six GNN architectures (including GCN, GraphSAGE, and GAT).

  • Significant Accuracy Boosts: On the GitHub Stargazers dataset, NCT-EFA improved the ROC AUC of the Graph Attention Network (GAT) by 11.69% and GraphSAGE by 9.55% compared to standard degree encoding.
  • Controllability Dominance: Even when using only average controllability as a feature (without the other centralities), the models consistently outperformed the baseline. For example, GAT saw a 9.98% improvement using only controllability.
Comparison of ROC AUC scores showing that average controllability consistently outperforms standard degree encoding across various GNN models.

Limitations and Future Work

  • Integration into Message Passing: Currently, NCT metrics are used as static input features. The authors suggest that integrating controllability directly into the GNN's internal message-passing mechanism could be even more powerful.
  • Computational Complexity: Calculating the controllability Gramian for extremely large graphs can be computationally expensive, though this wasn't the focus of this specific study.
  • Broader Metric Exploration: The study focused on average controllability; future work could explore other NCT metrics like "modal controllability" (the ability to push a system into difficult-to-reach states) to see if they offer different advantages.

Summary updated

Abstract

Network control theory (NCT) offers a robust analytical framework for understanding the influence of network topology on dynamic behaviors, enabling researchers to decipher how certain patterns of external control measures can steer system dynamics towards desired states. Distinguished from other structure-function methodologies, NCT's predictive capabilities can be coupled with deploying Graph Neural Networks (GNNs), which have demonstrated exceptional utility in various network-based learning tasks. However, the performance of GNNs heavily relies on the expressiveness of node features, and the lack of node features can greatly degrade their performance. Furthermore, many real-world systems may lack node-level information, posing a challenge for GNNs.To tackle this challenge, we introduce a novel approach, NCT-based Enhanced Feature Augmentation (NCT-EFA), that assimilates average controllability, along with other centrality indices, into the feature augmentation pipeline to enhance GNNs performance. Our evaluation of NCT-EFA, on six benchmark GNN models across two experimental setting. solely employing average controllability and in combination with additional centrality metrics. showcases an improved performance reaching as high as 11%. Our results demonstrate that incorporating NCT into feature enrichment can substantively extend the applicability and heighten the performance of GNNs in scenarios where node-level information is unavailable.
BibTeX
@misc{said2024improving,
  author = {Anwar Said and Obaid Ullah Ahmad and Waseem Abbas and Mudassir Shabbir and Xenofon Koutsoukos},
  title = {{Improving Graph Machine Learning Performance Through Feature Augmentation Based on Network Control Theory}},
  year = {2024},
  eprint = {2405.03706},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2405.03706},
}
Figure