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.
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.
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:
- 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.
- 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%.
- 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