Cross-Space Active Learning on Graph Convolutional Networks

Yufei Tao, Hao Wu, Shiyuan DengICML 2022

Introduction

Graph Convolutional Networks (GCNs) operate by iteratively applying convolutions—aggregating information from neighboring nodes—to create a sequence of distinct feature spaces at each layer. Typically, researchers find that one specific layer (often the second or third) yields the best performance for a given task. However, identifying this optimal "sweet spot" usually requires a fully labeled validation set.

This paper introduces Cross-Space Active Learning (CSAL), a novel framework designed to answer a fundamental question: Can we simultaneously find the best layer and the best classifier while requesting very few labels? The authors tackle the challenge of "cross-space" learning, where a single vertex in a graph has multiple representations across different layers but only one true label. The ultimate goal is to minimize the "label cost" required to reach a target accuracy.

Methodology: Formalizing Cross-Space Active Learning

The authors formalize the CSAL problem using Simple Graph Convolution (SGC), a streamlined GCN variant where features propagate linearly. The study relies heavily on the disagreement coefficient, a standard learning theory metric that captures how much hypotheses within a class differ from one another.

To understand label efficiency, the authors analyze two distinct classes of active learning algorithms:

  1. The Verifiable Class: These algorithms are given a target error ($\epsilon$) and must continue querying labels until they can mathematically guarantee they have met it. The authors approach this by treating the union of all layers as one massive hypothesis space and applying disagreement-based active learning.
  2. The Budget Class: These algorithms are given a strict, fixed number of label requests ($L$) and must achieve the lowest possible error within that constraint. The proposed budget algorithm splits its queries across all layers to find the best candidate in each, then conducts a final "tournament" to select the overall winner.

Theoretical Framework

As a purely theoretical study, this paper bypasses standard empirical benchmarks like Cora or Citeseer. Instead, the authors develop a synthetic stochastic model and a specific family of GCN inputs to rigorously prove their theorems.

  • Hardness Construction: To prove the fundamental limitations of verifiable algorithms, the authors design a complete graph with self-loops and a carefully constructed label distribution.
  • Stochastic Model: They introduce a model where an oracle "conceals" genuine, easily separable features using a graph structure. In this view, the GCN's convolution acts as a "reverse" operation, searching through different feature spaces to recover the original underlying labels.

Key Insights and Results

The paper's most striking contribution is the theoretical proof of a "separation" between budget and verifiable algorithms. In standard active learning, these two types of algorithms usually exhibit similar label complexities. In the cross-space GCN setting, however, they diverge significantly.

  • Verifiable Complexity (Theorem 5.2): The label complexity for verifiable algorithms is bounded by the sum of the disagreement coefficients across all layers. Because a verifiable algorithm must spend extra labels to definitively prove that no other layer could be better, it is highly sensitive to the "hardest" layer to learn.
  • Budget Complexity (Theorem 5.5): Budget algorithms achieve a complexity proportional to the disagreement coefficient of the best layer, multiplied by the number of layers ($T$). If $T$ is relatively small (logarithmic relative to the number of nodes), a budget algorithm can perform almost as well as if it knew the optimal layer in advance—essentially "lucking into" the best layer without needing to prove it.
  • The Separation (Theorem 6.1): The authors definitively prove that no verifiable algorithm can match the efficiency of a budget algorithm in this setting, even when there are only two layers ($T=2$). This separation is uniquely driven by the cross-space nature of GCNs.

Limitations and Future Directions

Because the proofs focus on linear Simple Graph Convolutions, the rigorous bounds are tightest for the linear case. While the authors provide a roadmap for extending these concepts to general GCNs with non-linearities (such as ReLU), the paper remains purely mathematical and does not offer a "plug-and-play" empirical library for practitioners working with real-world, noisy graphs.

Looking forward, the authors suggest that their "reverse convolution" stochastic model offers a highly fruitful direction for future research, providing a strong theoretical foundation for understanding why GCNs are so remarkably effective at feature discovery.

Summary updated

BibTeX
@inproceedings{tao2022cross,
  author = {Yufei Tao and Hao Wu and Shiyuan Deng},
  title = {{Cross-Space Active Learning on Graph Convolutional Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
}
Figure