Bipartite Graph for Topic Extraction

Thiago de Paulo Faleiros, Alneu de Andrade LopesIJCAI 2015

Abstract

Traditional topic modeling techniques like Latent Dirichlet Allocation (LDA) often struggle with complexity and resource intensity, particularly in streaming data environments. This paper proposes a Bipartite Graph Propagation Algorithm as a flexible, intuitive alternative. By representing documents and words as a network, the system allows for easier integration of custom heuristics and is better suited for high-speed, "one-pass" data processing.

Introduction

Extracting meaningful topics from massive text collections is a fundamental task in unsupervised machine learning. While methods like Latent Semantic Analysis (LSA) and Latent Dirichlet Allocation (LDA) are widely used, they present significant challenges in real-world applications. These include high mathematical complexity, which hinders the addition of domain-specific heuristics, and high resource requirements for matrix-based storage and computation. Furthermore, these static models are often ill-equipped for streaming data where models must update continuously without re-processing historical data.

Methodology

The core innovation of this work is the Bipartite Graph Propagation Algorithm. This approach shifts from standard document-term matrices to a graph-based representation.

Graph Representation

The system uses a bipartite graph $G = (D, W, E)$, where:

  • $D$ is the set of document nodes ($d_1, d_2, \dots, d_m$).
  • $W$ is the set of word nodes ($w_1, w_2, \dots, w_n$).
  • $E$ represents edges connecting documents to the words they contain, weighted by frequency.
Bipartite graph representation of documents and words.

Soft-Clustering and Propagation

Unlike standard label propagation, which typically assigns a single label per node, this method employs a "soft-cluster" schema. Each vertex is associated with a distribution across multiple topics simultaneously. The algorithm iterates through two primary phases:

  1. Local Propagation: Spreading word influence within specific documents.
  2. Global Propagation: Distributing corpus-wide cluster proportions back to individual words.

The authors demonstrate that this graph-based approach is formally equivalent to aspects of Nonnegative Matrix Factorization (NMF) and Variational Bayesian (VB) inference used in LDA, providing a solid theoretical foundation.

Experimental Setup

The algorithm's performance was evaluated using two primary metrics:

  • Pointwise Mutual Information (PMI): Used to assess the coherence of the extracted topics.
  • Classification Accuracy: Used to determine how effectively the topics represent the underlying documents.

Key Insights

  • Heuristic Flexibility: The graph structure allows practitioners to easily incorporate "rules of thumb" or domain-specific knowledge, which is often difficult in the rigid mathematical framework of LDA.
  • Efficiency through Sparsity: By only storing existing edges, the network representation naturally handles sparsity, leading to lower memory consumption compared to dense matrices.
  • Structural Adaptability: The model is inherently "pluggable," allowing for the seamless addition or removal of word and document vertices.

Results and Discussion

Initial offline experiments indicate that the Bipartite Graph Propagation algorithm achieves performance parity with LDA. The graph structure proved to be a promising method for topic extraction, notably due to its inherent parallelizability. The model successfully balanced local document context with global corpus trends to identify meaningful, representative topics.

Conclusion and Future Work

While this paper establishes the effectiveness of the bipartite graph approach in a static context, its true potential lies in dynamic environments. Future research will focus on:

  • Online Transition: Adapting the algorithm for single-pass processing of data streams.
  • Concept Drift: Enabling the model to adjust as topics evolve over time (e.g., shifting news cycles).
  • Scalability: Testing the algorithm against "big data" volumes to further evaluate its memory and processing efficiency.

Summary updated

BibTeX
@inproceedings{faleiros2015bipartite,
  author = {Thiago de Paulo Faleiros and Alneu de Andrade Lopes},
  title = {{Bipartite Graph for Topic Extraction}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure