PaperlayerView exact revision on arXiv

Source-linked AI summary

Label Efficient Semi-Supervised Learning via Graph Filtering

Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, Zhichao Guan

arXiv:1901.09993v3cs.LGcs.AIstat.ML

TL;DR

Existing graph-based semi-supervised methods either inadequately combine graph structure with data features or require substantial labeled data because of model complexity. The paper introduces a graph-filtering framework that smooths feature signals and unifies label propagation with graph convolutional networks, with experiments validating the proposed GLP and IGCN methods across classification and regression tasks.

  • Problem

    Existing methods are limited in jointly modeling graph structures and data features, or require considerable labeled data for training and validation because of high model complexity.

  • Method

    The paper treats data features as graph signals, applies adjustable low-pass graph filters, and derives generalized label propagation and improved graph convolutional networks.

  • Results

    Experiments validate the proposed methods across semi-supervised classification on citation networks and a knowledge graph, and regression for zero-shot image recognition.

  • Takeaways & Limitations

    The graph-filtering perspective provides unified insights into label propagation and graph convolutional networks while supporting improved modeling capabilities and label efficiency.

  • Takeaways & Limitations

    Neural-network-based graph models may require considerable labeled data for training and validation because of high model complexity, motivating the paper's label-efficiency focus.

Abstract

from arXiv · show

Graph-based methods have been demonstrated as one of the most effective approaches for semi-supervised learning, as they can exploit the connectivity patterns between labeled and unlabeled data samples to improve learning performance. However, existing graph-based methods either are limited in their ability to jointly model graph structures and data features, such as the classical label propagation methods, or require a considerable amount of labeled data for training and validation due to high model complexity, such as the recent neural-network-based methods. In this paper, we address label efficient semi-supervised learning from a graph filtering perspective. Specifically, we propose a graph filtering framework that injects graph similarity into data features by taking them as signals on the graph and applying a low-pass graph filter to extract useful data representations for classification, where label efficiency can be achieved by conveniently adjusting the strength of the graph filter. Interestingly, this framework unifies two seemingly very different methods -- label propagation and graph convolutional networks. Revisiting them under the graph filtering framework leads to new insights that improve their modeling capabilities and reduce model complexity. Experiments on various semi-supervised classification tasks on four citation networks and one knowledge graph and one semi-supervised regression task for zero-shot image recognition validate our findings and proposals.

1. Introduction

The paper targets label-efficient semi-supervised learning by combining graph structures with data features through graph filtering. It develops GLP and IGCN, which improve modeling capability and training efficiency across classification and regression tasks.

  • Graph-based semi-supervised learning must exploit both graph relations and data features, because each can encode different aspects of the data.
  • Classical label propagation uses graph structure alone, while neural graph models typically require considerable labeled data because of their high complexity.
  • The proposed framework treats data features as graph signals and applies low-pass graph filters to inject graph similarity into representations while flexibly controlling filter strength.
  • The framework unifies label propagation and graph convolutional networks, motivating generalized label propagation and improved graph convolutional networks.
  • Experiments cover semi-supervised classification on four citation networks and one knowledge graph, plus semi-supervised regression for zero-shot image recognition.
  • GLP and IGCN perform superiorly in prediction accuracy and training efficiency.

2. Graph Filtering

Graph filtering uses a graph to transform signals into smoother representations by preserving low-frequency components and suppressing high-frequency ones. Applied to vertex features, it provides a principled way to combine graph structure with feature information for learning.

  • A graph signal is a real-valued function on graph vertices, represented as a vector indexed by the vertices.
  • Graph filtering takes a graph signal as input and outputs a new signal, with a linear filter represented by a matrix G producing Gf.
  • Graph convolutional filters are characterized by a frequency response p(·), with G = Φp(Λ)Φ^-1.
  • A low-pass filter preserves low-frequency basis signals and attenuates high-frequency ones, so its response is larger for smaller eigenvalues.
  • Taking vertex features as graph signals lets graph filtering integrate graph structure and vertex features for learning.

3. Revisit and Extend Label Propagation

Recasting label propagation as graph filtering exposes its signal, filter, and classifier components, while generalized label propagation replaces label signals with feature signals and supports flexible filters and classifiers.

  • Revisit Label Propagation: Label propagation uses the label matrix as graph signals, an autoregressive graph filter, and a nonparametric classifier over filtered embeddings.The filter produces smooth signals, and unlabeled vertices receive the class with the largest embedding value.
  • Revisit Label Propagation: The autoregressive filter becomes more low-pass as α increases, producing smoother signals across the graph.Its response is near 1 at low frequencies and decreases toward 0 as frequency increases.
  • Revisit Label Propagation: A major limitation of label propagation is that it uses graph and label information without using the feature matrix X.This limits its ability to exploit datasets that provide both graph structure and data features.
  • Generalized Label Propagation Methods: Generalized label propagation replaces label signals with feature matrix X, permits any low-pass graph convolutional filter, and supports any classifier trained on labeled embeddings.The filtered features are used to train a supervised classifier for predicting unlabeled vertices.
  • Generalized Label Propagation Methods: GLP injects graph relations into features, allows computationally efficient and strength-adjustable filters, and accommodates domain-specific classifiers for high-dimensional data.Examples include multilayer perceptrons for text and convolutional neural networks for images.

4. Revisit and Improve Graph Convolutional Networks

The graph filtering perspective interprets GCN as repeated graph filtering and reveals how normalization and renormalization shape its frequency response. This analysis motivates IGCN, which controls filter strength with an exponent while retaining a shallow model for label efficiency.

  • Revisit Graph Convolutional Networks: GCN applies the renormalized adjacency filter to layer activations, then projects the filtered features with trainable weights and nonlinearities.The model starts from H(0) = X and trains with cross-entropy on labeled samples.
  • Revisit Graph Convolutional Networks: GCN’s filter has a linear low-pass response on [0, 1] but is not low-pass on.The normalized Laplacian keeps eigenvalues in [0, 2], while the renormalization trick shrinks the range to approximately [0, 1.5], reducing noise from large eigenvalues.
  • Revisit Graph Convolutional Networks: Under graph filtering, GCN is a special case of GLP using input signal X, filter ˜W_s^2, and a two-layer MLP classifier.Exchanging the second-layer filter with the internal ReLU exposes this equivalence.
  • Improved Graph Convolutional Networks: GCN cannot easily control filter strength, so stacking layers adds parameters and can cause overfitting or require extra labels for validation.This limitation is especially relevant when the label rate is small.
  • Improved Graph Convolutional Networks: IGCN replaces ˜W_s with ˜W_s^k, using exponent k to adjust filter strength while maintaining a shallow structure with fewer trainable parameters.The RNM filter provides the tunable frequency response used by the improved model.

5. Filter Strength and Computation

Filter strength can be tuned to the label rate: stronger filtering smooths representations and can support classification with few labels, but excessive smoothing is a concern. The proposed computations exploit polynomial or sparse repeated-multiplication forms to avoid expensive matrix inversion.

  • Filter Strength: When each class has very few labels, increasing filter strength can make distant nodes more similar to labeled nodes, although over-smoothing can result.The filter-strength parameters are α for AR and k for RNM.
  • Filter Strength: As k increases, RNM-filtered Cora features become smoother and form more compact clusters, supporting classification with few labels.The visualization uses t-SNE projections of raw and filtered features.
  • Computation: Matrix inversion has complexity O(n^3), motivating polynomial approximation for the relevant filter computation.The approximation avoids directly computing the inverse.
  • Computation: The polynomial approximation can reduce complexity to O(nmα + Nmα), with N ≪ n^2 when the graph is sparse.The stated approximation uses k = ⌈4α⌉ empirically.
  • Computation: For sparse graphs, repeated multiplication by the sparse filter computes the approximation in O(Nmk) time.Here N is the number of nonzero entries in the graph Laplacian and m is the feature dimension.

6. Experiments

The experiments evaluate GLP and IGCN across semi-supervised classification and zero-shot image-recognition regression tasks, with comparisons covering accuracy, running time, and multiple baselines.

  • 6.1. Semi-Supervised Classification: The classification experiments cover document classification on citation networks and entity classification on a knowledge graph using few labeled examples.The settings include citation-network and NELL label regimes, with baselines including LP, GCN, GAT, Planetoid, and others.
  • 6.1. Semi-Supervised Classification: GLP and IGCN perform best overall on the reported classification benchmarks and demonstrate label efficiency.On NELL, selected GLP and IGCN variants slightly outperform LP and Planetoid and outperform other baselines by a large margin.
  • 6.1. Semi-Supervised Classification: GLP with the RNM filter runs much faster than GCN in most cases, while IGCN with the RNM filter has similar time efficiency to GCN.The running-time comparison is reported alongside classification accuracy in Table 2.
  • 6.1. Semi-Supervised Classification: The analysis attributes the methods’ gains to combining graph and feature information and adjusting filter strength for low label rates.GLP and IGCN increase filter parameters k and α to extract higher-level representations, whereas increasing GCN smoothness requires stacking layers.
  • 6.2. Semi-Supervised Regression: The regression experiment replaces GCN with GLP and IGCN for zero-shot image recognition using category text descriptions and relationships.The task predicts classifier weights for unseen categories from known-category weights, word embeddings, and the WordNet knowledge graph.
  • 6.2. Semi-Supervised Regression: On AWA2, IGCN with k = 1, 2 and GPM perform best, while GLP with k = 2 is second best among the compared baselines.The compared methods include Devise, SYNC, GCNZ, and DGPM, with results averaged over 20 runs.

7. Related Works

Related work spans broad semi-supervised learning approaches, graph-based methods, graph convolutional networks, and feature smoothing. These lines of research motivate combining graph structure with data features through graph filtering.

  • Semi-Supervised Learning: Semi-supervised learning includes generative models, semi-supervised support vector machines, self-training, co-training, and graph-based methods.The cited literature covers multiple families of approaches for exploiting labeled and unlabeled data.
  • Graph-Based Methods: Early graph-based methods assume nearby vertices are likely to share labels and use embeddings, random walks, spectral methods, graph partitions, or contextual information.Other approaches regularize supervised classifiers with graph- or embedding-based regularizers.
  • Graph Convolutional Networks: Graph convolutional networks extend convolutional ideas from grid-structured data to general graphs, with ChebyNet using polynomial graph-Laplacian filters and GCN simplifying that approach.This line of work addresses graph-structured representation learning while avoiding expensive eigen-decomposition.
  • Feature Smoothing: Feature smoothing has also been used as preprocessing for semi-supervised learning, including manifold denoising with data-feature graphs and an AR filter.The cited method smooths features before constructing a graph for label propagation.

8. Conclusion

The paper develops a unifying graph-filtering view of semi-supervised learning and uses it to extend label propagation and graph convolutional networks for stronger modeling and label efficiency.

  • 8. Conclusion: The graph-filtering perspective provides new insights into label propagation and graph convolutional networks.The conclusion presents this perspective as the basis for the paper’s proposed methods.
  • 8. Conclusion: The proposed generalized label propagation methods and improved graph convolutional networks extend modeling capabilities and achieve label efficiency.The conclusion identifies both method families as outcomes of the graph-filtering analysis.
Loading 1901.09993v3…