Collectively Representing Semi-Structured Data from the Web

Bhavana Dalvi, William W. Cohen, Jamie CallanAKBC-WEKEX @ NAACL 2012 · OpenReview

Abstract: In this paper, we propose a single low-dimensional representation of a large collection of table and hyponym data, and show that with a small number of primitive operations, this representation can be used effectively for many purposes. Specifically we consider queries like set expansion, class prediction etc. We evaluate our methods on publicly available semi-structured datasets from the Web.

Introduction

The web is a vast repository of semi-structured information, primarily encoded in HTML tables and linguistic "hyponym" patterns (e.g., "cities such as Paris"). Extracting and utilizing this data for tasks like set expansion (finding new members of a category) or class prediction has traditionally required separate, computationally intensive graph-based algorithms and bespoke data structures.

The primary challenges are twofold: first, the sheer scale of web graphs makes real-time querying difficult; second, information is often fragmented across different "views," such as a sports table on one site and a list of athletes on another. We address these issues by introducing a unified, low-dimensional representation of entities that captures diverse relationships while remaining efficient for real-time applications.

Methodology: The PIC3 Representation

We introduce PIC3, a method that leverages Power Iteration Clustering (PIC) to compress complex web graphs into high-performance vectors. PIC is an iterative algorithm that assigns values to nodes, moving connected nodes closer together in a low-dimensional space.

The PIC3 construction process involves three key steps:

  1. Graph Construction: We build a graph where entities serve as central nodes, connected to two types of context: Table-Columns (where the entity appears) and Hyponym Concepts (concepts associated via "such as" patterns).
  2. Bipartite Embedding: Rather than embedding the entire graph at once, we treat the Entity-Table and Entity-Hyponym relationships as separate bipartite graphs. We run PIC on each to generate $m$-dimensional vectors.
  3. Concatenation: The final PIC3 embedding is the concatenation of these two vectors, typically resulting in a representation as small as 10 dimensions.
The PIC3 embedding process: separate bipartite graphs are embedded via PIC and then concatenated to form a unified representation.

By reducing the feature space from thousands of dimensions to just 10, complex tasks are transformed into simple geometric operations. For instance, set expansion becomes a K-Nearest Neighbor (K-NN) search around the centroid of seed entities.

Experimental Setup

We evaluated our approach using several datasets derived from web crawls:

  • Toy_Apple: ~15,000 entities and 156 table columns.
  • Delicious_Sports: A dense dataset with 438 entities and 925 table columns.
  • Hyponym Concept Dataset: A collection of Hearst patterns providing semantic context.
  • NELL (Never-Ending Language Learner): Used for ground-truth category labels.

Key Results and Discussion

Our experiments demonstrate that PIC3 achieves extreme compression without sacrificing accuracy. Reducing the feature space from over 2,500 dimensions to 10 dimensions maintained high performance while significantly increasing query speed.

Classification Accuracy

In semi-supervised learning tests, the SVM+PIC3 approach consistently outperformed high-dimensional SVM baselines. This advantage was most pronounced when training data was sparse (e.g., 10-20% training size), as the low-dimensional embedding effectively "smooths" the data, aiding generalization.

Comparison of 10-fold CV accuracy between the SVM+PIC3 approach and the high-dimensional baseline across different training sizes for two datasets.

Efficiency and Speed

PIC3 provides substantial speedups at query time. For set expansion on the Delicious_Sports dataset, PIC3 handled 881 queries in 12.7 seconds, compared to 80.1 seconds for the standard K-NN baseline and 38.2 seconds for the state-of-the-art MAD (Modified Adsorption) algorithm. In Automatic Set Instance Acquisition (ASIA) tasks, PIC3 was orders of magnitude faster than MAD (0.5s vs 150s per query) while remaining competitive in accuracy.

Conclusion

PIC3 demonstrates that a unified, low-dimensional representation can effectively bridge fragmented web data sources. By shifting the computational burden to an offline embedding phase, we enable lightning-fast entity classification and set expansion. Future work will explore scaling this approach to the full web and applying it to tasks like named-entity disambiguation.

Summary updated

Abstract

In this paper, we propose a single low-dimensional representation of a large collection of table and hyponym data, and show that with a small number of primitive operations, this representation can be used effectively for many purposes. Specifically we consider queries like set expansion, class prediction etc. We evaluate our methods on publicly available semi-structured datasets from the Web.
BibTeX
@inproceedings{dalvi2012collectively,
  author = {Bhavana Dalvi and William W. Cohen and Jamie Callan},
  title = {{Collectively Representing Semi-Structured Data from the Web}},
  booktitle = {AKBC-WEKEX @ NAACL},
  year = {2012},
  url = {https://openreview.net/forum?id=HkWzR7-dbH},
}
Figure