Quantifying the alignment of graph and features in deep learning

Yifan Qian, Paul Expert, Tom Rieu, Pietro Panzarasa, Mauricio Barahona

Introduction

Graph Convolutional Networks (GCNs) have become a cornerstone of modern machine learning by fusing node features with relational graph structures. However, their performance is not guaranteed to exceed that of simpler models. In certain scenarios, such as specific subsets of Wikipedia, a standard Multi-Layer Perceptron (MLP) that ignores graph topology can actually outperform a GCN. This paper addresses this discrepancy by introducing the Subspace Alignment Measure (SAM), a geometric metric designed to quantify the synergy between a dataset’s features, its graph topology, and the ground-truth labels.

The Subspace Alignment Measure (SAM)

The authors propose SAM to fill a critical gap: the lack of a formal method to measure how well the three pillars of graph learning—Features ($X$), the Graph ($A$), and the Labels ($Y$)—align. If these components are poorly aligned (e.g., connected nodes have dissimilar features or different labels), the smoothing mechanism of a GCN may introduce more noise than signal.

Geometric Foundation and the "Alignment Triangle"

SAM treats features, graphs, and labels as subspaces within a high-dimensional space. It utilizes principal angles to calculate the chordal distance between these subspaces. The relationship is conceptualized as an "Alignment Triangle" where the vertices represent the Feature, Graph, and Label subspaces.

The Alignment Triangle: Visualizing the geometric relationship between feature, graph, and label subspaces.

SAM is calculated as the Frobenius norm of the distance matrix formed by these pairwise chordal distances, effectively measuring the total misalignment of the triangle. To ensure consistency across different matrix shapes, the authors employ an optimization criterion to identify the optimal lower-dimensional representations ($k^*$) for features and graphs that maximize the measure's discriminatory power.

Experimental Setup and Datasets

The study validates SAM across a diverse range of benchmarks, from synthetic models to real-world citation and knowledge networks. These datasets vary significantly in scale and complexity, providing a robust testbed for the metric.

Summary of benchmarks used to evaluate SAM, including synthetic and real-world citation and Wikipedia networks.

Key datasets include:

  • Constructive Example: A synthetic Stochastic Block Model where alignment is manually controlled.
  • CORA & AMiner: Classic and new citation networks where graph structure is typically highly informative.
  • Wikipedia (I and II): Two distinct subsets. Wikipedia I focuses on self-referential topics (e.g., Mathematics) where GCNs thrive, while Wikipedia II contains broader topics where MLPs often prove superior.

Key Insights and Results

The research yields several critical insights into the behavior of GNNs:

  1. Alignment as a Performance Predictor: SAM—a linear algebraic measure—correlates remarkably strongly (mean correlation of -0.92) with the accuracy of highly non-linear GCNs. As alignment decreases (higher SAM), GCN accuracy drops monotonically.
  2. Predicting Model Failure: SAM serves as a diagnostic tool. In the Wikipedia II dataset, SAM correctly identified poor alignment, explaining why the "No Graph" (MLP) approach achieved ~66% accuracy while the full GCN lagged at ~57%.
  3. Component Saliency: By using randomization as a stress test (rewiring edges or swapping features), the authors can quantify whether the graph or the features are more critical for a specific task.

Limitations and Future Directions

While powerful, SAM currently faces computational challenges regarding the eigendecomposition of very large graphs, though approximations like the Lanczos algorithm are suggested as a remedy. Additionally, because subspace dimensions are adjusted per dataset, SAM values are not yet directly comparable across different benchmarks. Future work aims to develop a "normalized" SAM and extend the metric beyond node classification to tasks like link prediction and graph regression.

Summary updated

Abstract

We show that the classification performance of graph convolutional networks (GCNs) is related to the alignment between features, graph, and ground truth, which we quantify using a subspace alignment measure (SAM) corresponding to the Frobenius norm of the matrix of pairwise chordal distances between three subspaces associated with features, graph, and ground truth. The proposed measure is based on the principal angles between subspaces and has both spectral and geometrical interpretations. We showcase the relationship between the SAM and the classification performance through the study of limiting cases of GCNs and systematic randomizations of both features and graph structure applied to a constructive example and several examples of citation networks of different origins. The analysis also reveals the relative importance of the graph and features for classification purposes.
BibTeX
@article{qian2019quantifying,
  author = {Yifan Qian and Paul Expert and Tom Rieu and Pietro Panzarasa and Mauricio Barahona},
  title = {{Quantifying the alignment of graph and features in deep learning}},
  journal = {IEEE Trans. Neural Networks Learn. Syst.},
  year = {2019},
  doi = {10.1109/tnnls.2020.3043196},
}
Figure