Graph Space Embedding

João P. B. Pereira, Albert K. Groen, Erik S. G. Stroes, Evgeni LevinIJCAI 2019 · DOI

TL;DR

This paper introduces Graph Space Embedding (GSE), a novel kernel method that maps input data into a space where interactions between features are implicitly encoded. GSE offers improved performance and efficiency compared to existing graph kernels, particularly for tasks involving complex, feature-specific interactions, and provides a mechanism for interpreting model predictions.

What Problem Does This Paper Address?

Learning from interconnected systems, where components interact in complex ways, is a significant challenge in machine learning. While some approaches leverage known interactions or discover them through graph structures, this paper focuses on a setting where interactions are feature-specific and universal across data instances. Traditional methods often struggle with this scenario, leading to a gap in effectively modeling such systems. The authors aim to address this by developing a method that can efficiently capture and utilize these feature-specific interactions for prediction and interpretation.

Methods

The core contribution is the Graph Space Embedding (GSE), a new kernel function. GSE builds upon existing graph kernel concepts, particularly random walks, but introduces a novel way to compare graphs. Instead of summing all possible walks, GSE compares "similar edges" across different graphs, leading to increased expressiveness. This is achieved by combining graph kernels with a radial basis function (RBF) and a specific distance metric between graph representations.

Key methodological aspects include:

  • Graph Space Embedding (GSE) Function: Maps input data into an "interaction-based" space.
  • Theoretical Feasibility Region: The paper derives a theoretical result for an optimal regime for GSE's parameters, specifically the hyperparameter v, which controls the contribution of higher-order edge combinations. This region helps in efficiently optimizing hyperparameters.
  • Even Descent Sampling Algorithm: A novel strategy for interpretability. It aims to approximate the function values in unexplored regions by taking steps with equidistant output values, allowing for insights into which interactions are responsible for specific predictions. This method is designed to escape local extrema and handle the complexity of high-dimensional spaces.

Datasets

The primary dataset used for evaluation is a collection of plasma protein levels from patients with suspected coronary artery disease (CAD). This dataset includes measurements of 332 proteins and information on protein-protein interactions. The study also mentions using a constant interaction matrix (all ones) to test the hypothesis that prior interaction knowledge is beneficial.

Key Insights and Ideas

  • Beyond Random Walks: GSE's innovation lies in moving beyond simply comparing random walks to comparing "similar edges," which enhances its ability to capture nuanced interactions.
  • Interaction-Specific Advantage: The empirical results strongly suggest that leveraging feature-specific interaction information (via protein-protein interactions) significantly improves predictive performance over methods that ignore or use generic interaction information.
  • Efficient Hyperparameter Optimization: The derived feasibility region for the v parameter is crucial. It transforms hyperparameter tuning from a potentially exhaustive search into a more guided and efficient process, leveraging the kernel's variance as a proxy for expressiveness.
  • Interpretable Predictions: The Even Descent Sampling algorithm offers a valuable tool for understanding "black-box" models. By perturbing inputs in directions of maximum output change, it helps identify specific features and their interactions that drive predictions, moving towards more transparent AI.

Key Results

  • Performance Improvement: GSE significantly outperformed baseline algorithms (random-walk graph kernel, RBF, random forests) in predicting ischaemia in CAD patients, achieving a higher ROC AUC.
  • Efficiency: GSE is considerably faster than the Random-Walk kernel, with a computational complexity of O(m²n²) compared to O(m²k'n⁴) or O(m²k'n²) for random-walk kernels, where 'm' is the number of features and 'n' is the number of data points.
  • Interaction Knowledge Matters: GSE with actual protein-protein interaction data performed better than GSE with a constant interaction matrix, confirming the value of prior interaction knowledge.
  • Feasible Region Validation: The study found that the proxy for kernel expressiveness (variance of the kernel matrix) is a convex function that peaks at the analytically determined optimal v* value, validating the theoretical findings.

Limitations and Future Work

  • Interpretability Model Choice: While the paper uses decision trees for interpretability, the authors note that other interpretable models could be explored.
  • Generalizability of Even Descent: The Even Descent Sampling algorithm is presented as a promising technique for interpretability. Further exploration of its application across different model types and datasets would be beneficial.
  • Complexity of Interactions: While GSE handles feature-specific interactions well, the paper could explore its scalability and effectiveness with even more complex or dynamic interaction structures.
  • Future Work: The authors suggest further research into the optimal regime for GSE parameters and the application of their interpretability technique to a wider range of problems.

Summary updated

BibTeX
@inproceedings{pereira2019graph,
  author = {João P. B. Pereira and Albert K. Groen and Erik S. G. Stroes and Evgeni Levin},
  title = {{Graph Space Embedding}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/451},
}
Figure