Experiments in Graph-Based Semi-Supervised Learning Methods for Class-Instance Acquisition

Partha Pratim Talukdar, Fernando C. N. PereiraACL 2010 · OpenReview

Abstract

Graph-based semi-supervised learning (SSL) algorithms have been successfully used to extract class-instance pairs from large unstructured and structured text collections. However, a careful comparison of different graph-based SSL algorithms on that task has been lacking. We compare three graph-based SSL algorithms for class-instance acquisition on a variety of graphs constructed from different domains. We find that the recently proposed MAD algorithm is the most effective. We also show that class-instance extraction can be significantly improved by adding semantic information in the form of instance-attribute edges derived from an independently developed knowledge base. All of our code and data will be made publicly available to encourage reproducible research in this area.

Introduction

Traditional Named-Entity Recognition (NER) usually focuses on broad categories such as Person, Location, or Organization. However, modern applications like web search and semantic matching require much finer granularity—identifying whether an entity is a Boxer, a Scientist, or a Musician.

Training supervised classifiers for thousands of these specific classes is impractical due to the lack of massive labeled datasets. To address this, researchers utilize Semi-Supervised Learning (SSL), starting with a small set of "seed" examples and propagating those labels across a graph of related entities. While several graph-based SSL algorithms exist, a rigorous comparison of their performance on massive, noisy datasets for class-instance acquisition has been missing.

Methodology

This study compares three primary graph-based SSL algorithms across various datasets, including Freebase relational tables and TextRunner hypernym tuples.

Evaluated Algorithms

  1. LP-ZGL (Label Propagation): An early SSL method assuming connected nodes share similar labels. It strictly fixes seed node labels, which can be problematic with noisy data.
  2. Adsorption: An iterative random-walk-based algorithm that allows seed labels to change and uses controlled propagation to mitigate the influence of high-degree "hub" nodes.
  3. MAD (Modified Adsorption): An unconstrained optimization version of Adsorption. It features better regularization than LP-ZGL, reducing overfitting in highly connected graphs.

Semantic Constraints: The "Secret Sauce"

Beyond algorithmic comparison, the authors introduce a novel graph construction technique by adding instance-attribute edges derived from external knowledge bases like YAGO. For instance, if two entities share an attribute (e.g., "has_albums"), they are connected via a shared attribute node, facilitating more effective label flow between similar entities.

Key Results

Algorithm Performance

Across nearly all experiments, MAD proved to be the most robust algorithm. On the Freebase-1 graph (23 Pantel classes), MAD achieved a Mean Reciprocal Rank (MRR) of approximately 0.78 with 10 seeds per class, significantly outperforming LP-ZGL and Adsorption.

Comparison of SSL algorithms on the Freebase-1 graph, showing MAD's superior performance as supervision increases.

Impact of Semantic Attributes

Integrating attributes as "bridges" in the graph significantly improves accuracy. Instances sharing attributes are more likely to belong to the same class, and the propagation process naturally identifies which attributes are strong indicators for specific classes (e.g., "works_at" for Scientist). Adding YAGO attributes to the TextRunner graph resulted in a massive performance jump; for 10 seeds per class, the MRR for MAD jumped from roughly 0.34 to over 0.43.

Performance jump when combining TextRunner graphs with YAGO attribute data, demonstrating the benefit of semantic constraints.

Sparsity and Regularization

LP-ZGL often suffers from under-regularization in dense graphs, leading to performance drops. MAD's superior regularization prevents this overfitting. Additionally, enforcing per-node sparsity—limiting the number of classes allowed per node—is crucial for maintaining accuracy. Performance was found to peak when nodes were restricted to their top 25 most likely classes.

Conclusion

The Modified Adsorption (MAD) algorithm is the most effective tool for fine-grained class-instance acquisition in large-scale graphs. Furthermore, the inclusion of semantic constraints through instance-attribute edges provides a substantial boost to extraction performance. Future work will explore more complex graph architectures and additional types of semantic constraints to further refine these methods.

Summary updated

Abstract

Graph-based semi-supervised learning (SSL) algorithms have been successfully used to extract class-instance pairs from large unstructured and structured text collections. However, a careful comparison of different graph-based SSL algorithms on that task has been lacking. We compare three graph-based SSL algorithms for class-instance acquisition on a variety of graphs constructed from different domains. We find that the recently proposed MAD algorithm is the most effective. We also show that class-instance extraction can be significantly improved by adding semantic information in the form of instance-attribute edges derived from an independently developed knowledge base. All of our code and data will be made publicly available to encourage reproducible research in this area.
BibTeX
@inproceedings{talukdar2010experiments,
  author = {Partha Pratim Talukdar and Fernando C. N. Pereira},
  title = {{Experiments in Graph-Based Semi-Supervised Learning Methods for Class-Instance Acquisition}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2010},
  url = {https://openreview.net/forum?id=ByZTLsguZH},
}
Figure