Source-linked AI summary
Revisiting Semi-Supervised Learning with Graph Embeddings
Zhilin Yang, William W. Cohen, Ruslan Salakhutdinov
TL;DR
The paper addresses the challenge of using graph structure and labels together in semi-supervised learning while supporting prediction on unseen instances. It introduces Planetoid, which jointly trains label- and context-predicting embeddings in transductive and inductive forms, and reports improved performance across benchmark tasks, especially inductively.
Problem
Existing graph embeddings are often learned separately from supervised tasks, while graph Laplacian regularization may not produce useful features or fully leverage graph distributional information.
Method
Planetoid jointly trains embeddings to predict class labels and graph context, using graph-dependent embeddings transductively and feature-parameterized embeddings inductively.
Results
Planetoid improves over existing methods across five datasets and three tasks, with gains up to 8.5% overall and up to 18.7% in the inductive setting.
Takeaways & Limitations
Joint training improves over unsupervised learning, graph-context prediction is more effective than graph Laplacian regularization, and inductive performance depends on feature informativeness.
Takeaways & Limitations
The transductive formulation cannot predict instances absent from the training graph, and incrementally learning embeddings is time consuming and does not scale.
Abstract
from arXiv · showhide
We present a semi-supervised learning framework based on graph embeddings. Given a graph between instances, we train an embedding for each instance to jointly predict the class label and the neighborhood context in the graph. We develop both transductive and inductive variants of our method. In the transductive variant of our method, the class labels are determined by both the learned embeddings and input feature vectors, while in the inductive variant, the embeddings are defined as a parametric function of the feature vectors, so predictions can be made on instances not seen during training. On a large and diverse set of benchmark tasks, including text classification, distantly supervised entity extraction, and entity classification, we show improved performance over many of the existing models.
1. Introduction
The paper introduces Planetoid, a graph-based semi-supervised framework that jointly trains embeddings to predict labels and graph context. It provides transductive and inductive variants, with experiments showing improvements across three task types.
- 1. Introduction: Planetoid jointly trains each instance embedding to predict its class label and neighborhood context in the graph.The framework concatenates embeddings with the classifier’s hidden layers before softmax prediction.
- 1. Introduction: The transductive variant predicts labels for instances already observed in the training graph.Its embeddings are learned from graph structure and are unavailable for unseen graph instances.
- 1. Introduction: The inductive variant defines embeddings as a parameterized function of input features, enabling prediction on previously unobserved instances.The embeddings can be viewed as hidden layers of a neural network.
- 1. Introduction: Experiments cover five datasets and three tasks: text classification, distantly supervised entity extraction, and entity classification.The evaluation compares both inductive and transductive approaches with existing methods.
- 1. Introduction: The inductive method exceeds the second-best inductive method by up to 18.7 percentage points and 7.8 points on average in accuracy.The combined best Planetoid variant exceeds the best other method by up to 8.5% and 4.1% on average.
2. Related Work
Related work spans semi-supervised learning with labeled and unlabeled data, graph-based regularization, and embedding methods that predict graph context. The paper distinguishes its approach by jointly using label prediction and graph-context prediction rather than only regularizing labels or learning embeddings separately.
- 2.1. Semi-Supervised Learning: Semi-supervised learning uses labeled and unlabeled instances to learn classifiers, with transductive and inductive paradigms differing in generalization to unseen instances.Transductive classifiers apply to observed unlabeled instances, whereas inductive classifiers are parameterized to generalize.
- 2.1. Semi-Supervised Learning: Graph-based semi-supervised learning receives an instance-similarity graph whose edges can derive from distances or external sources such as knowledge graphs and citation networks.The graph is represented as an (L + U) × (L + U) matrix A.
- 2.2. Graph-Based Semi-Supervised Learning: Graph Laplacian methods combine supervised loss with a regularization penalty that discourages different predictions for similar nodes.The penalty increases when nodes with large similarity weights receive different labels.
- 2.2. Graph-Based Semi-Supervised Learning: Existing methods include label propagation, local and global consistency, semi-supervised embedding, and iterative classification.These methods vary in whether they use label lookup, squared loss, embedding regularization, or iterative neighbor-label prediction.
- 2.3. Learning Embeddings: Skipgram-based embedding methods minimize log loss for predicting context from an instance embedding, extending from words to graph nodes.DeepWalk uses random-walk contexts, while LINE models first- and second-order proximity.
- 2.3. Learning Embeddings: Compared with prior methods, the paper uses embeddings to predict graph context jointly with classification instead of imposing graph regularization or learning embeddings separately.Conventional Laplacian methods do not learn embeddings, while standalone graph embeddings do not use task-specific label information.
3. Semi-Supervised Learning with Graph Embeddings
The framework jointly learns instance embeddings for class-label prediction and graph-context prediction, using sampled positive and negative contexts. It supports transductive predictions for observed graph instances and an inductive variant whose embeddings are functions of input features.
- Framework: The model represents each instance with an embedding and combines it with neural-network hidden layers to predict class labels.The network uses feed-forward layers with ReLU activations, concatenates hidden representations, and feeds them to a softmax classifier.
- Framework: Training jointly minimizes supervised label-prediction loss and unsupervised graph-context prediction loss.The weighting factor λ controls the contribution of context prediction relative to label prediction.
- Context sampling: Context prediction uses negative sampling to classify sampled instance-context pairs as positive or negative.Positive pairs represent related contexts, while negative examples approximate normalization over the full context space.
- Context sampling: The context distribution mixes graph-based random-walk samples with label-based samples, while separately controlling positive and negative sampling.Graph contexts are sampled within a random-walk window; label contexts use same-label positive pairs and different-label negative pairs among labeled instances.
- Transductive formulation: The transductive variant predicts labels for instances observed in the training graph because their embeddings are learned directly for those graph instances.It does not generalize to unobserved instances, and transductive training can use unlabeled test instances during training.
- Inductive formulation: The inductive variant defines the embedding as a parameterized function of the input features, enabling prediction on instances unobserved during graph training.The embedding is implemented as an intermediate hidden layer, with later layers producing the classifier representation.
4. Experiments
Experiments evaluate Planetoid across text classification, distantly supervised entity extraction, and entity classification, comparing inductive and transductive variants with established baselines. Results show strong gains from jointly using graph context and label information, while the relative value of features and graph structure varies by dataset.
- Text Classification: Planetoid-I achieves the best inductive performance on all three text-classification datasets, improving by up to 6.1% on Pubmed.Planetoid-T is best among transductive methods on Cora and Pubmed, while TSVM is best on Citeseer.
- Text Classification: Planetoid-G consistently outperforms GraphEmb on all three text-classification datasets.The authors relate this result to jointly training label and graph-context objectives rather than training supervised and unsupervised objectives separately.
- Entity Classification: Adding feature vectors does not improve Planetoid-T on NELL, making it equivalent to Planetoid-G in that experiment.The results therefore use empty feature vectors for Planetoid-T.
- Entity Classification: Planetoid-I outperforms SemiEmb by 4.8%, 16.0%, and 18.7% at labeling rates 0.1, 0.01, and 0.001, respectively.The improvement becomes more significant as the labeling rate decreases.
- Entity Classification: Graph structure is more informative than features on this entity-classification dataset, so inductive methods perform worse than transductive methods.Planetoid-G outperforms GraphEmb by 5.0%, 3.2%, and 3.8%.
5. Conclusion
The paper proposes joint classification and graph-context prediction, including an inductive variant that conditions embeddings on input features, and reports substantial gains over existing methods. Experiments also indicate that joint training and graph-context prediction improve performance, while inductive performance depends on feature informativeness.
- The framework jointly trains classification with graph-context prediction instead of relying primarily on graph Laplacian regularization.
- The inductive variant conditions embeddings on input features to generalize to novel instances.
- The methods improve over existing approaches by up to 8.5% and on average 4.1%, with larger inductive gains of up to 18.7% and 7.8% on average.
- Joint training improves over unsupervised learning, and graph-context prediction is more effective than graph Laplacian regularization.
- Inductive performance depends on the informativeness of the feature vectors.
- Future work includes applying the framework to more complex networks and graphs computed from distances between feature vectors.