HCGA: Highly Comparative Graph Analysis for Network Phenotyping

Robert L. Peach, Alexis Arnaudon, J.a.r. Schmidt, Henry Antonio Palasciano, Nathan Bernier, Kim E. Jelfs, Sophia N. Yaliraki, Mauricio BarahonaSSRN 2020 · DOI

TL;DR

This paper introduces HCGA, a powerful Python package for extracting thousands of graph features from complex network data. HCGA not only automates this massive feature extraction but also integrates statistical learning tools to identify the most important features for tasks like classification and regression, enabling deeper scientific discovery from network data.

What Problem Does This Paper Address?

Analyzing complex systems represented as networks is crucial across many scientific disciplines. While a vast array of graph properties (features) exist, it's often unclear which ones are most relevant for a specific research question. This leads to a manual, time-consuming, and potentially biased selection of features, limiting the ability to fully characterize and classify networks or discover new insights. Existing tools often compute only a small, domain-specific subset of features, failing to leverage the full potential of graph theory.

Methods

The core of HCGA is its highly comparative graph analysis approach. It automates the extraction of a large number of graph-theoretical features (thousands) from any given network. This creates a high-dimensional feature matrix for the entire dataset. HCGA then employs statistical learning techniques (like XGBoost for classification and regression) to analyze this feature matrix. A key innovation is the integration of Shapley Additive Explanations (SHAP) to quantify the importance of individual features for prediction tasks, providing interpretable insights into why a particular network structure is important. The framework is modular and open-source, allowing for easy expansion of features and analysis tools.

Datasets

HCGA was evaluated on several benchmark datasets:

  • Biochemical datasets: ENZYMES, PROTEINS, D&D, NCI1, MUTAG.
  • Social network datasets: COLLAB, REDDIT-BINARY, REDDIT-MULTI-5K, REDDIT-MULTI-12K, IMDB-BINARY, IMDB-MULTI.
  • Custom datasets:
    • Neuronal morphologies from the Blue Brain Project.
  • Organic semiconductors (helicene dimers) from a previous computational screening study.

Key Insights and Ideas

  • Massive Feature Extraction is Key: The sheer number of features extracted by HCGA is crucial for capturing the complexity of real-world networks and achieving high performance, often outperforming methods that rely on a smaller, pre-selected set of features.
  • Interpretability is Preserved: Despite the massive feature set, HCGA's use of SHAP values allows researchers to understand which specific graph properties are driving predictions, bridging the gap between complex models and scientific understanding.
  • Feature Redundancy and Correlation: The analysis revealed that many seemingly distinct graph features are highly correlated, providing complementary descriptions of the data and highlighting the need for careful feature selection or understanding of these relationships.
  • Domain-General Utility: HCGA demonstrates its applicability across diverse scientific domains, from biology and neuroscience to chemistry and social sciences, by successfully analyzing different types of network data.

Key Results

  • State-of-the-Art Classification: HCGA achieved competitive or superior classification accuracies on benchmark biochemical and social network datasets compared to popular deep learning and kernel methods, even without hyperparameter optimization of the classifier. For example, on the PROTEINS dataset, HCGA achieved 75.7% accuracy, and with feature selection (HCGA*), it reached 79.3%.
  • Successful Clustering: HCGA successfully recovered biologically meaningful clusters of neuronal morphologies, aligning with known cell types (Pyramidal, Martinotti, interneurons).
  • Predictive Regression: In predicting the electronic transfer integral (J-coupling) of helicene dimers, HCGA achieved a mean absolute error (MAE) of 0.355 ± 0.022, significantly outperforming a model using only molecular distance (MAE of 1.58). The top features identified, like variation in edge betweenness centrality, provided interpretable insights into electronic transport.

Limitations and Future Work

  • Computational Cost: While HCGA offers options to mitigate computational burden (e.g., time-out limits, speed rankings), feature extraction for large datasets can still be time-consuming, taking hours on a local computer.
  • Feature Selection Parameters: The paper notes that the parameters for feature reduction (number of top features 'n' and maximum correlation 'c') can be optimized further with a validation set for improved performance.
  • Future Work: The authors suggest expanding HCGA to include more complex network representations like multilayer networks and exploring more advanced statistical learning tools. Further research could also focus on designing classification tasks to identify graph features that specifically lead to very high or very low J-couplings for guiding the design of more efficient organic semiconductor compounds.

Summary updated

BibTeX
@misc{peach2020hcga,
  author = {Robert L. Peach and Alexis Arnaudon and J.A.R. Schmidt and Henry Antonio Palasciano and Nathan Bernier and Kim E. Jelfs and Sophia N. Yaliraki and Mauricio Barahona},
  title = {{HCGA: Highly Comparative Graph Analysis for Network Phenotyping}},
  year = {2020},
  doi = {10.2139/ssrn.3720300},
  howpublished = {SSRN},
}
Figure