PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph-based Semi-supervised Learning: A Comprehensive Review

Zixing Song, Xiangli Yang, Zenglin Xu, Irwin King

arXiv:2102.13303v1cs.LG

TL;DR

GSSL methods require systematic organization across graph regularization and graph embedding approaches. This paper reviews these methods, provides resources and applications, and identifies future research directions. Its outcome is a generalized taxonomy connecting popular label inference methods within regularization and encoder-decoder frameworks.

  • Problem

    Existing GSSL approaches require a systematic understanding of their methods, connections, applications, and resources.

  • Method

    The paper comprehensively reviews GSSL, proposes a two-category taxonomy of graph regularization and graph embedding, and collects codes, datasets, applications, and research directions.

  • Results

    The review groups popular label inference methods into graph regularization and graph embedding, generalizing them through regularization and encoder-decoder frameworks.

  • Takeaways & Limitations

    The survey serves as a hands-on guide for understanding GSSL approaches, running experiments with resources, and developing new ideas.

  • Takeaways & Limitations

    Shallow embedding approaches do not use node features and are inherently transductive, preventing embeddings for nodes observed after training.

Abstract

from arXiv · show

Semi-supervised learning (SSL) has tremendous value in practice due to its ability to utilize both labeled data and unlabelled data. An important class of SSL methods is to naturally represent data as graphs such that the label information of unlabelled samples can be inferred from the graphs, which corresponds to graph-based semi-supervised learning (GSSL) methods. GSSL methods have demonstrated their advantages in various domains due to their uniqueness of structure, the universality of applications, and their scalability to large scale data. Focusing on this class of methods, this work aims to provide both researchers and practitioners with a solid and systematic understanding of relevant advances as well as the underlying connections among them. This makes our paper distinct from recent surveys that cover an overall picture of SSL methods while neglecting fundamental understanding of GSSL methods. In particular, a major contribution of this paper lies in a new generalized taxonomy for GSSL, including graph regularization and graph embedding methods, with the most up-to-date references and useful resources such as codes, datasets, and applications. Furthermore, we present several potential research directions as future work with insights into this rapidly growing field.

I. INTRODUCTION

GSSL represents labeled and unlabeled samples as similarity graphs, then propagates labels through graph structure. This survey reviews GSSL systematically, introduces a taxonomy centered on graph construction and label inference, and provides resources and future directions.

  • GSSL framework: GSSL constructs a similarity graph whose nodes are samples and whose weighted edges represent pairwise similarity.The graph reflects the manifold assumption and includes both labeled and unlabeled data.
  • GSSL framework: Label inference propagates information from labeled samples to unlabeled ones using the structure of the constructed graph.The survey identifies label inference as the more challenging step and its main focus.
  • Motivation: GSSL is motivated by applications involving graph-structured data, including the World Wide Web, citation networks, and social networks.The review also highlights convexity and scalability as advantages of graph-based methods.
  • Taxonomy: The survey’s taxonomy divides GSSL into graph construction and label inference, with graph regularization and graph embedding as the main label-inference groups.Graph regularization is organized through loss-function regularizers, while graph embedding is unified through an encoder-decoder framework.
  • Contributions: The paper provides detailed method descriptions, comparisons, strengths and limitations, open-source code, benchmark datasets, and application pointers.It also discusses future directions involving dynamicity, scalability, noise-resilience, and attack-robustness.
  • Motivation: SSL combines a few costly labeled samples with abundant cheap unlabeled samples, matching the setting of many real-world applications.The paper situates GSSL within SSL’s broader development across classic, mature, and deep-learning phases.

3) Transductive and inductive settings:

GSSL methods are categorized by whether they predict labels only for the observed unlabeled samples or for arbitrary future inputs. The section also introduces graph notation and construction assumptions.

  • 3) Transductive and inductive settings:: Transductive GSSL predicts labels only for the unlabeled data in the training set, whereas inductive GSSL predicts outputs for any input x ∈ X.
  • 3) Transductive and inductive settings:: Most GSSL approaches are transductive; transductive methods often achieve higher prediction accuracy but incur higher training costs, especially for large-scale incremental learning.
  • Graph notation and construction: A graph is represented as G = (V, E), with nodes and edges, and GSSL treats each node as an input sample.
  • Graph notation and construction: Weighted graphs assign nonnegative edge weights Wij, while node degree Dii is the sum of incident edge weights.
  • Graph notation and construction: Graph construction estimates edges E and weights W for a fixed node set, commonly assuming undirected graphs, nonnegative weights, no self-loops, and Wij = 0 for absent edges.
  • Graph notation and construction: KNN and b-Matching, together with their extensions, are identified as the most popular unsupervised graph-construction methods.

1) KNN-based approaches:

KNN-based graph construction connects each node to nearby samples using a configured similarity or distance measure, but can produce irregular graphs. Related methods address connectivity, hubs, and degree balance.

  • 1) KNN-based approaches:: KNN graphs connect each node to its k nearest neighbors according to a pre-configured distance metric, often producing irregular graphs with degrees larger than k.
  • 1) KNN-based approaches:: ε-neighborhood graphs connect pairs whose distance is below ε, but a misleading ε can produce disconnected graphs; KNN graphs offer better scalability.
  • 1) KNN-based approaches:: Mutual KNN combined with a maximum spanning tree addresses hubs, while sequential KNN avoids hubs without requiring regularity.
  • 1) KNN-based approaches:: b-Matching constructs the graph through graph sparsification followed by edge re-weighting, with binary, Gaussian, and locally linear reconstruction weighting options.
  • 1) KNN-based approaches:: b-Matching constrains every node to have exactly b neighbors, enabling more balanced label propagation in the subsequent inference step.
  • 1) KNN-based approaches:: Supervised graph construction incorporates labeled samples as prior information, including GBILI and its robust extension RGCLI.

A. Label propagation

Label propagation infers unlabeled labels from graph similarities while fixing seed labels, and related regularization methods express prediction as a balance between supervised fit and graph smoothness.

  • A. Label propagation: Label Propagation spreads seed labels to unlabeled nodes through graph similarities while keeping the labeled-node assignments fixed.
  • A. Label propagation: The basic algorithm iteratively propagates labels, row-normalizes class scores, clamps labeled data, and repeats until convergence.
  • A. Label propagation: Gaussian Random Fields produce a harmonic prediction function whose unlabeled-node values equal the mean of neighboring values under graph constraints.
  • A. Label propagation: LGC extends propagation to multiclass problems and relaxes exact seed matching, improving tolerance to noisy seed labels while degree-normalizing node influence.
  • A. Label propagation: LGC has variants including p-Laplacian regularization, and it has been used to generate pseudo-labels for unlabeled data in DNN training.

B. Directed regularization

Directed regularization extends graph-based label inference to edge directionality, while manifold and newer regularization frameworks address geometry, scalability, ambiguity, and sparse-label settings.

  • B. Directed regularization: A directed-graph regularization framework incorporates naive random walks to account for edge directionality in settings such as citation networks.
  • B. Directed regularization: The directed-graph loss sums weighted variation across directed edges, and the undirected LGC regularizer is a special case obtained from the stationary random-walk distribution.
  • B. Directed regularization: Manifold regularization combines spectral graph theory and manifold learning to enforce smoothness in the intrinsic geometry of high-dimensional data.
  • B. Directed regularization: Its objective balances ambient-space prediction complexity with an intrinsic-space smoothness term weighted by γA and γI.
  • B. Directed regularization: Manifold regularization has high computational cost and becomes unscalable for large graphs, motivating acceleration of graph-Laplacian or kernel operations.
  • B. Directed regularization: LPDGL adds a local-information smoothness term for ambiguous examples and is reported to achieve a globally optimal prediction function with robust hyperparameter performance.

A. Generalization: Perspective of encoder-decoder

The encoder-decoder framework unifies graph embedding methods as low-dimensional node encoding followed by neighborhood-information reconstruction. It also clarifies how embedding approaches differ from graph regularization and how representative methods are compared.

  • A. Generalization: Perspective of encoder-decoder: Graph embedding uses an encoder to map nodes into low-dimensional vectors and a decoder to reconstruct information about their original neighborhoods.The decoder may reconstruct neighbor sets, adjacency rows, or pairwise node similarities.
  • A. Generalization: Perspective of encoder-decoder: The reconstruction objective minimizes the discrepancy between graph-defined similarities and similarities produced from pairs of node embeddings.For neighborhood prediction, the objective can minimize the gap between S[u, v] and A[u, v].
  • A. Generalization: Perspective of encoder-decoder: Encoders are either shallow lookup functions based on node IDs or deep models using node features and local graph structure, including GNNs.The shallow-versus-deep distinction concerns the information supplied to the encoder.
  • A. Generalization: Perspective of encoder-decoder: Factorization methods learn low-dimensional approximations of similarity matrices encoding adjacency or other graph measurements.Adjacency and normalized Laplacian matrices are examples of structural matrices used for factorization.
  • A. Generalization: Perspective of encoder-decoder: The encoder-decoder framework provides a general overview of method components, making different graph embedding approaches easier to compare.This comparison perspective is applied to representative factorization-based shallow embedding methods.
  • A. Generalization: Perspective of encoder-decoder: LLE represents each node embedding as a linear combination of neighborhood nodes, whereas Laplacian Eigenmaps make strongly connected nodes close in embedding space.LLE uses eigenvectors of a sparse matrix, while Laplacian Eigenmaps select eigenvectors associated with the smallest normalized-Laplacian eigenvalues.

3) Graph factorization:

Graph factorization methods obtain embeddings by factorizing matrices that encode graph structure, while random-walk methods preserve proximity through node co-occurrence. The reviewed approaches differ in the structural information they preserve, scalability, and downstream-task specialization.

  • 3) Graph factorization:: Graph Factorization reduces the time complexity of earlier graph embedding algorithms to O(E) by directly using the adjacency matrix.Its objective sums over observed edges because the adjacency matrix is not necessarily positive semidefinite.
  • 3) Graph factorization:: GraRep preserves k-order proximity through powers of the node transition matrix, but its scalability is limited because T^k can contain O(|V|^2) non-zero entries.The method concatenates embeddings learned for different orders k.
  • 3) Graph factorization:: HOPE preserves higher-order proximity using a sparse proximity-matrix formulation that permits efficient node embedding through singular value decomposition.Its proximity matrix is defined using two sparse matrices, M_g and M_l.
  • 3) Graph factorization:: M-NMF extends embedding beyond microscopic proximity by incorporating mesoscopic community structure through consensus between node and community representations.The method combines local structural information with community-level structure.
  • 3) Graph factorization:: Random-walk embeddings are useful when only part of a graph is accessible or its scale makes direct processing difficult.Random walks provide approximate information about graph properties such as centrality and similarity.
  • 3) Graph factorization:: DeepWalk, Planetoid, and node2vec preserve proximity through random-walk context, with Planetoid jointly predicting labels and graph context in transductive and inductive settings.node2vec uses biased walks balancing breadth-first and depth-first exploration.
  • 3) Graph factorization:: LINE targets scalability by preserving first- and second-order proximity, while PTE embeds text networks combining labels and word co-occurrence information for downstream tasks.LINE optimizes its proximity objectives with KL divergence; PTE is designed for text representation learning.

6) HARP:

This section reviews HARP and deep graph embedding methods, emphasizing their architectures, capabilities, and limitations. HARP improves shallow embedding optimization, while deep approaches incorporate structural and, in some cases, feature information.

  • 6) HARP:: HARP uses graph coarsening and level-by-level embedding propagation to improve weight initialization and avoid local optima.It can be combined with random-walk-based approaches for better performance.
  • Shallow embedding: Shallow embedding methods can be unified because random-walk approaches generally perform implicit matrix factorization with closed-form solutions.NetMF provides a framework for factorizing the underlying matrices.
  • Limitations of shallow embedding: Shallow embedding has three key drawbacks: parameters grow as O(|V|), node features are unused, and embeddings cannot be generated for new nodes.These limitations affect massive graphs and inductive applications.
  • Deep embedding methods: Deep embedding methods use more complex encoders, often based on deep neural networks, to address limitations of shallow approaches.Autoencoder, recurrent, and graph-convolutional encoders are reviewed.
  • AutoEncoder-based methods: Autoencoder-based methods encode similarity-matrix rows into low-dimensional representations and reconstruct them, but can remain computationally costly and transductive.Their predefined structures may not adapt to evolving graphs.
  • GAE & VGAE: GAE incorporates both graph structure and node attributes through graph convolution, whereas direct adjacency reconstruction may cause overfitting.VGAE instead learns a data distribution using a variational lower bound.

6) ARGA & ARVGA:

This section places graph neural network methods within deep graph embedding and describes their message-passing framework. GNNs use neighborhood information and node features to produce embeddings for semi-supervised classification.

  • Deep graph embedding: Deep embedding approaches use complex neural-network encoders to incorporate structural and attribute information into graph representations.This distinguishes them from shallow embedding approaches.
  • GNN framework: Basic GNN message passing consists of differentiable aggregation and update operations repeated across iterations.The resulting final hidden state is treated as the node embedding.
  • GNN framework: GNN-based models generate node embeddings by aggregating information from each node’s neighborhood and updating its hidden representation.The final hidden state can support a classifier for unlabeled nodes.
  • Basic GNN: The basic GNN first summarizes neighbor messages, combines them with the node’s previous hidden state, and applies a nonlinear activation.This is expressed through the model’s aggregation and update components.

D. Generalized aggregation operation

This section surveys generalized GNN aggregation operations and their variants. The methods address degree sensitivity, over-smoothing, neighborhood mixing, and permutation handling in neighborhood representations.

  • Neighborhood normalization: Basic summation aggregation can be unstable because nodes with larger degree receive larger total values.Degree-based normalization replaces or rescales the sum, including averaging and symmetric normalization.
  • Neighborhood normalization: GCN combines normalized neighborhood aggregation with self-loop updates and is described as a popular and effective GNN baseline.Its aggregation is implicitly included in the update function.
  • GCN variants: GCN extensions explore graph construction, graph regularization, random walks, and other modifications to improve SSL performance.The review identifies multiple directions for extending GCNs.
  • Higher-order aggregation: MixHop learns neighborhood relationships at multiple distances by mixing feature representations from one-hop and higher-order neighbors.Setting P = {1} recovers the original graph-convolution layer.
  • Generalized aggregation: Aggregation functions map neighborhood embeddings to one vector while encoding local structure and neighbor features.The review considers more sophisticated alternatives to summation and linear aggregation.
  • Permutation-aware aggregation: Set pooling preserves permutation invariance, whereas Janossy pooling averages a permutation-sensitive function over multiple neighbor orderings.Janossy pooling commonly uses an LSTM for the sequence function.

3) Neighborhood attention:

The review covers neighborhood aggregation and update mechanisms in GNNs for graph-based semi-supervised learning, including attention, skip connections, recurrent gates, and layer combinations. These techniques address information weighting, stability, over-smoothing, and representation effectiveness.

  • Neighborhood attention: Attention mechanisms assign importance weights to neighbors during aggregation, while GAT implements this principle through a weighted neighbor sum.GAT defines attention weights for each neighbor; AGNN pursues a related goal with fewer parameters.
  • Concatenation and skip-connections: Over-smoothing washes away node-specific information after many message iterations, motivating vector concatenations and skip connections that retain previous-layer representations.The problem arises when node representations become overly dependent on aggregated incoming messages.
  • Concatenation and skip-connections: GraphSAGE uses concatenation to combine a node’s previous-layer representation with the output of the current update function.This encourages the model to dissociate information during message passing.
  • Concatenation and skip-connections: Column Network uses gated linear interpolation between previous and current outputs, with neighborhood information controlling the update.The gating vectors satisfy α1 + α2 = 1 and combine representations through the Hadamard product.
  • Over-smoothing: Scattering GCN uses geometric scattering for bandpass graph-signal filtering, while DropEdge removes edges during training to mitigate over-smoothing.These strategies are beneficial for relatively deep GNNs in semi-supervised node classification, where predictions correlate with local neighborhoods.
  • Jumping knowledge connections: Jumping knowledge connections combine embeddings from multiple message-passing layers instead of using only the final layer’s output.The combination can use concatenation or max pooling and has produced progress across tasks including SSL classification.

VIII. APPLICATIONS

The survey presents GSSL applications across computer vision, natural language processing, social networks, and biomedical science, alongside datasets, implementations, historical development, and open problems. It highlights scalability, noise resilience, and robustness as continuing research concerns.

  • Resources: The survey organizes selected GSSL datasets across seven domains and provides benchmark statistics in Table VII.It also lists open-source implementations for GSSL methods in Table VIII.
  • Computer vision: GSSL applications include hyperspectral image classification, image retrieval, temporal image analysis, and visual-audio domain adaptation in computer vision.These applications address settings such as costly labeled data and sparse labels.
  • Natural language processing: In NLP, similarity graphs support POS tagging, graph-based smoothing of language models, information retrieval, and GAT-based short-text understanding.The reviewed methods range from random fields to GCN- and GAT-based approaches.
  • Social networks: Social-network applications use GSSL for crisis tweet classification, user–POI smoothing, friend recommendation, follower suggestion, and heterogeneous POI recommendation.These tasks exploit explicit or bipartite graph structures among users, documents, and points of interest.
  • Biomedical science: Biomedical applications include phenotype classification, miRNA–disease prediction, disease diagnosis, and molecular or protein–drug graph analysis.The survey describes semantic biomedical knowledge graphs, molecular graphs, and protein–drug interaction graphs as application settings.
  • Open problems: The survey identifies scalability, noisy or missing attributes, and adversarial attacks as open problems for GSSL.Proposed directions include anchor graph regularization, noise-resilient co-training, and defenses against data-poisoning attacks.

APPENDIX A DATASETS COLLECTION FOR GSSL

The survey’s chronology shows a shift from graph regularization and matrix factorization toward AutoEncoder, random-walk, and ultimately GNN-based methods. After GCN’s introduction in 2017, GNN-based methods became dominant in the field.

  • Chronological overview: From 2000 to 2012, GSSL research centered on graph regularization and matrix factorization.This period represents the early mainstream of the field’s development.
  • Chronological overview: After deep learning’s resurgence in 2015, AutoEncoder-based methods emerged while random-walk-based methods continued to coexist.The chronology captures parallel development rather than a single immediate replacement.
  • Chronological overview: After GCN was introduced in 2017, GNN-based methods became the dominant solution and remained an active research topic.The survey presents this transition as the latest major phase in GSSL development.
Loading 2102.13303v1…