A Mobile Touchable Application for Online Topic Graph Extraction and Exploration of Web Content

Günter Neumann, Sven SchmeierACL 2011

TL;DR

This paper introduces a mobile application for the iPad that extracts and visualizes topic graphs from web search snippets. It addresses the limitations of traditional document-centric search by enabling interactive exploration of related topics, particularly useful for users with vague information needs.

What Problem Does This Paper Address?

Current web search engines primarily operate on a document-centric paradigm. Users input keywords and receive a ranked list of documents, which are treated independently. This approach is effective when users know exactly what they're looking for. However, it falls short for exploratory searches where users have only a vague idea of their information needs or wish to discover new, related information. This is especially cumbersome on mobile devices, where reformulating queries and sifting through documents can be tedious. The authors aim to bridge this gap by facilitating "content-oriented interaction" and enabling users to "find out about something" rather than just finding specific documents.

Methods

The core of the system is the topic graph extraction process. This is framed as an empirical collocation extraction task between chunks (word sequences) rather than individual words. The association strength between chunks is measured using a modified Pointwise Mutual Information (PMI) approach that explicitly considers the distance between chunks.

Here's a breakdown of the key steps:

  1. Document Construction: The N (typically 1000) web snippets returned by a standard search engine for a user's query are concatenated into a single document.
  2. Chunking: Each snippet line is first tagged with Part-of-Speech (PoS) tags. Then, the text is "chunked" to identify noun chains and verb chains. A "phrasal head test" is applied to ensure these chunks represent proper noun groups or verb groups.
  3. Chunk-Pair-Distance Model: The system computes frequencies of individual chunks, chunk pairs, and chunk pair distances. This forms a chunk-pair-distance model (CPDM).
  4. Topic Graph Construction: The topic graph is built from the CPDM. Nodes represent chunks, and edges represent relationships between them. The weighting scheme for edges considers chunk frequencies and their collocations, using a PMI-based calculation that incorporates Taylor series polynomials to approximate probabilities based on chunk frequencies and distances. The complexity of the graph is managed by restricting the number of edges connected to a node.

Beyond the extracted topic graph, the system also incorporates background knowledge by extracting explicit relationships from Wikipedia's infoboxes. This provides users with validated background information related to the topics.

The application features a touchable user interface on an iPad. Users can interact with the topic graph by touching nodes to inspect content or expand the graph with newly computed related topics.

Datasets

The system primarily uses web snippets obtained from a standard search engine (specifically, Bing is mentioned for web search). For background knowledge, it utilizes Wikipedia's infoboxes. The authors mention testing DBpedia but found it contained too much redundant information compared to Wikipedia's infoboxes for their purposes.

Key Insights and Ideas

  • Shifting from Document to Topic Perspective: The fundamental idea is to move beyond presenting raw documents and instead offer a structured, graphical representation of a topic and its related entities. This is particularly valuable for exploration.
  • Chunk-Pair-Distance for Collocations: Treating word sequences (chunks) and their spatial relationships as the basis for identifying meaningful associations is a novel approach to collocation extraction, moving beyond simple word co-occurrence.
  • Interactive Exploration on Mobile: The design specifically targets mobile devices (iPad) with a touch-based interface, making complex information exploration intuitive and engaging.
  • Integrating External Knowledge: Seamlessly blending dynamically extracted topic graphs with structured background knowledge from sources like Wikipedia enriches the user's understanding and discovery process.
  • User Evaluation Highlights Exploratory Value: The initial user evaluation suggests the system is most helpful for users who have a vague idea of a topic, indicating success in addressing the identified problem.

Key Results

The paper presents qualitative results through screenshots of the iPad application demonstrating the topic graph extraction and exploration for the query "Justin Bieber."

An initial user evaluation with 20 testers (a mix of computer science and non-computer science backgrounds, many new to iPads) provided the following insights:

  • Users generally preferred the result representation and accuracy of Google for general themes, finding web snippets more convenient to understand.
  • However, for discovering interesting and surprising facts, users enjoyed exploring the results using the topic graph.
  • The overall feeling was in favor of their system, possibly due to its novelty and "playful" nature.
  • Users appreciated the explorative search paradigm on the iPad and preferred touching the graph over reformulating queries.
  • The presentation of background facts from Wikipedia (i-MILREX mode) was highly appreciated.
  • A limitation noted was that topic graphs could become confusing when expanded beyond three nodes.

Limitations and Future Work

  • Graph Complexity: Users found topic graphs confusing when expanded beyond three nodes. The authors plan to automatically collapse nodes with higher distances from the focus node in future versions.
  • Ambiguity in Infobox Matching: Currently, the system only supports exact matches between user queries and Wikipedia infobox titles.
  • Handling Redundant Information: Techniques are needed to cope with undesired or redundant information from knowledge sources.
  • Broader Knowledge Source Integration: The authors plan to extend the system to other knowledge sources like DBpedia, newsticker, and stock information.
  • Partial Matches and Ambiguities: Future work will address handling partial matches and more complex ambiguities when querying knowledge sources.

Summary updated

BibTeX
@inproceedings{neumann2011mobile,
  author = {Günter Neumann and Sven Schmeier},
  title = {{A Mobile Touchable Application for Online Topic Graph Extraction and Exploration of Web Content}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2011},
}
Figure