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:
- 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).
- 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.
- Concatenation: The final PIC3 embedding is the concatenation of these two vectors, typically resulting in a representation as small as 10 dimensions.
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.
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