PaperlayerView exact revision on arXiv

Source-linked AI summary

A network approach to topic models

Martin Gerlach, Tiago P. Peixoto, Eduardo G. Altmann

arXiv:1708.01677v2stat.MLcs.CLphysics.data-anphysics.soc-ph

TL;DR

Topic models, particularly LDA, have conceptual and practical limitations involving priors, real-text statistics, and topic-number selection. The paper represents corpora as bipartite networks and adapts nonparametric hierarchical SBMs to topic modeling. The resulting hSBM produces better topic models than LDA under statistical model-selection criteria and formally connects the two fields.

  • Problem

    LDA lacks principled topic-number selection, can overfit, and uses Dirichlet priors that may conflict with real-text statistics and heterogeneous mixtures.

  • Method

    The paper represents word-document matrices as bipartite networks and derives a nonparametric Bayesian topic model from hierarchical stochastic block models.

  • Results

    The hSBM yields better topic models than LDA across diverse real and artificial corpora, including non-Dirichlet synthetic data where LDA fails.

  • Takeaways & Limitations

    The formal correspondence enables community-detection methods and extensions to be applied to topic modeling and richer text data.

Abstract

from arXiv · show

One of the main computational and scientific challenges in the modern age is to extract useful information from unstructured texts. Topic models are one popular machine-learning approach which infers the latent topical structure of a collection of documents. Despite their success --- in particular of its most widely used variant called Latent Dirichlet Allocation (LDA) --- and numerous applications in sociology, history, and linguistics, topic models are known to suffer from severe conceptual and practical problems, e.g. a lack of justification for the Bayesian priors, discrepancies with statistical properties of real texts, and the inability to properly choose the number of topics. Here we obtain a fresh view on the problem of identifying topical structures by relating it to the problem of finding communities in complex networks. This is achieved by representing text corpora as bipartite networks of documents and words. By adapting existing community-detection methods -- using a stochastic block model (SBM) with non-parametric priors -- we obtain a more versatile and principled framework for topic modeling (e.g., it automatically detects the number of topics and hierarchically clusters both the words and documents). The analysis of artificial and real corpora demonstrates that our SBM approach leads to better topic models than LDA in terms of statistical model selection. More importantly, our work shows how to formally relate methods from community detection and topic modeling, opening the possibility of cross-fertilization between these two fields.

I. INTRODUCTION

Topic modeling and community detection address related structure-inference problems but have developed largely separately. The paper unifies them by representing texts as bipartite word-document networks and adapting hierarchical, nonparametric SBM methods to overcome limitations of LDA.

  • Motivation: LDA lacks an intrinsic method for choosing the number of topics and can overfit because it contains many free parameters.
  • Motivation: Topic modeling and community detection share conceptual similarities, but the fields have largely developed independently.
  • Approach: The paper represents document-word matrices as bipartite networks, making topic inference equivalent to community inference.
  • Approach: It derives a nonparametric Bayesian topic model from hierarchical SBM methods, reducing assumptions and allowing model complexity to be inferred from the posterior.
  • Motivation: Dirichlet priors impose simplistic mixture assumptions that conflict with heterogeneous topic structure and real-text word frequencies such as Zipf’s law.

2. Topic models and community detection: Equivalence between pLSI and SBM

The paper establishes a mathematical correspondence between pLSI and mixed-membership SBMs by recasting word-document counts as a bipartite multigraph. This correspondence shows that SBM methods generalize pLSI by clustering both words and documents.

  • Equivalence: pLSI is equivalent to a specific mixed-membership stochastic block model.
  • Network representation: Word-document count matrices can be treated as adjacency matrices of bipartite multigraphs, yielding an equivalent SBM likelihood under a document-specific grouping.
  • Generalization: The SBM generalizes pLSI by allowing both words and documents to be clustered, while recovering pLSI when documents are not clustered.
  • Network representation: The symmetric SBM treats words and documents as nodes in different partitions of a bipartite network.

3. Community detection and the hierarchical SBM

The paper extends the pLSI–SBM correspondence into a hierarchical, nonparametric topic model that infers topic structure without fixing the number of groups in advance. Hierarchical priors accommodate heterogeneous structures and preserve the known document–word bipartite organization.

  • 3. Community detection and the hierarchical SBM: Hierarchical SBMs extend the pLSI–SBM correspondence into a framework for inferring topical structure in texts.The approach builds on the mathematical equivalence between pLSI and SBMs and extends hierarchical SBMs for text inference.
  • 3. Community detection and the hierarchical SBM: The earlier noninformative SBM formulation retains a resolution limit, allowing at most O(N) groups to be inferred on a sparse network with N nodes.The hierarchical prior is introduced to address this shared disadvantage while maintaining nonparametric inference.
  • 3. Community detection and the hierarchical SBM: Hierarchical priors replace homogeneous assumptions with latent mixture and degree-frequency structure, allowing substantially more heterogeneous group mixtures than LDA’s Dirichlet prior.The resulting expected degrees follow a broader Bose–Einstein distribution rather than the exponential distribution associated with the earlier prior.
  • 3. Community detection and the hierarchical SBM: Nested SBMs recursively cluster groups across levels, modeling higher-order organization and heterogeneity at multiple scales.Each hierarchy level clusters groups from the levels below, while the prior contains the flat model as the special case L = 1.
  • 3. Community detection and the hierarchical SBM: Nonparametric inference estimates both hierarchy depth and the number of document and word groups from the posterior.The flat model is included when the data do not support hierarchical structure, avoiding extrinsic methods for choosing model dimension.
  • 3. Community detection and the hierarchical SBM: The text-specific prior enforces disjoint word and document partitions, so words and documents cannot occupy the same group.This incorporates the known bipartite structure instead of requiring inference to discover it.

B. Comparing LDA and hSBM in real and artificial data

The evaluation compares hSBM with LDA across non-Dirichlet mixtures, LDA-generated corpora, and five real corpora using minimum-description-length model selection.

  • B. Comparing LDA and hSBM in real and artificial data: The study evaluates hSBM against LDA on three problem classes: non-Dirichlet mixtures, LDA-generated artificial corpora, and five real corpora.The comparison is organized to test both mixture recovery and model selection on real and synthetic data.
  • B. Comparing LDA and hSBM in real and artificial data: The non-Dirichlet experiments test whether hSBM can infer mixtures that LDA fails to represent appropriately.The artificial examples are designed to expose limitations caused by LDA’s Dirichlet assumption.

1. Failure of LDA in the case of non-Dirichlet mixtures

The experiments test LDA and SBM on Dirichlet, non-Dirichlet, and real-document topic mixtures. SBM matches Dirichlet mixtures while also recovering richer non-Dirichlet patterns that LDA distorts toward its prior.

  • 1. Failure of LDA in the case of non-Dirichlet mixtures: The experiments compare true and inferred topic-mixture distributions for synthetic Dirichlet, synthetic non-Dirichlet, and real datasets with K = 3 topics.The figure shows true synthetic distributions alongside LDA and SBM inferences, with real-data mixtures unknown.
  • 1. Failure of LDA in the case of non-Dirichlet mixtures: SBM correctly identifies both Dirichlet and non-Dirichlet mixtures, whereas LDA completely fails on the non-Dirichlet synthetic data.For Dirichlet-generated data, both methods recover the mixture distribution; for non-Dirichlet data, SBM closely matches the truth.
  • 1. Failure of LDA in the case of non-Dirichlet mixtures: On real data, LDA produces distributions resembling Dirichlet expectations, while SBM suggests a richer pattern despite unknown underlying mixtures.The Dirichlet-like LDA result is characterized as likely an artifact of the prior.
  • 1. Failure of LDA in the case of non-Dirichlet mixtures: The results show that LDA is biased toward Dirichlet-type mixtures, while SBM captures a broader spectrum through its more agnostic nonparametric formulation.The contrast is attributed directly to the models’ prior choices.

2. Artificial corpora sampled from LDA

On artificial corpora generated by LDA, hSBM generally achieves shorter description lengths than LDA, even though the data-generating process favors LDA. It also automatically selects hierarchical topic and document structure without requiring the number of groups or levels beforehand.

  • Artificial corpora sampled from LDA: hSBM frequently provides a better description than LDA for artificial corpora generated from LDA, despite the data-generating process favoring LDA.The comparison uses minimum description length, where smaller values indicate better statistical models.
  • Artificial corpora sampled from LDA: hSBM is consistently better than LDA across synthetic text lengths spanning 4 orders of magnitude.This result is shown for corpora with asymptotically large document counts and remains qualitatively stable across parameter settings.
  • Artificial corpora sampled from LDA: LDA’s description length becomes largely insensitive to whether true or noninformative priors are used as corpus size increases.For smaller corpora, the noninformative prior has significantly worse description length than the true prior.
  • Artificial corpora sampled from LDA: Allowing documents to be clustered gives hSBM much shorter description lengths than LDA, except for very small texts with m < 10 tokens.For D →∞, the authors expect hSBM to be similarly good or better than LDA for all text lengths.
  • Artificial corpora sampled from LDA: For real corpora, hSBM systematically achieves smaller description lengths than LDA and can additionally cluster documents.The comparison considers noninformative and fitted LDA priors across a range of topic counts.
  • Artificial corpora sampled from LDA: Unlike LDA, hSBM extracts the number of topics from its posterior while avoiding the underfitting and overfitting patterns associated with LDA’s prior choices.The noninformative LDA choice underfits as topic count increases, whereas the parametric approach overfits.
  • Case study: Application of hSBM to Wikipedia articles: The hierarchical hSBM automatically detects group numbers and levels while clustering both documents and words.In the case study, document groups separate biology from physics, while word groups distinguish subject-specific and function words.

III. DISCUSSION

The paper frames topic modeling and community detection as mathematically connected problems and uses that connection to develop hierarchical SBM topic models. Across real and artificial corpora, hSBM is reported to outperform LDA under description-length model selection while enabling richer structural interpretations.

  • Unified framework: hSBM formulates topic modeling as community inference in bipartite networks linking documents and words.This framework is based on the mathematical equivalence between pLSI and overlapping SBMs.
  • Unified framework: The hierarchical model identifies structural patterns unavailable to LDA across multiple resolution scales.The approach supports hierarchical clustering of words and documents.
  • Model comparison: hSBM outperforms LDA on diverse real corpora and artificial corpora generated from LDA itself.The comparison is based on statistical model selection using description length.
  • Implications: The analysis argues that Dirichlet priors can bias inference because they are poorly matched to language usage and constrain topic mixtures.The authors report that hSBM incorporates priors agnostic to inferred mixture types within a fully Bayesian framework.
  • Model comparison: Description length provides an information-theoretic comparison by encoding both the data given model parameters and the parameters themselves.Smaller description length indicates a better model.

B. Artificial corpora

The artificial-corpus experiments construct texts from fixed LDA generative parameters and vary the corpus design across controlled topic, word, and document settings. The broader evaluation also compares models across multiple real-text datasets spanning genres, periods, lengths, document counts, and languages.

  • Corpus construction: Artificial corpora are generated by fixing LDA’s topic count, hyperparameters, and individual article lengths.The α and β hyperparameters govern topic distributions in documents and word distributions in topics.
  • Corpus construction: LDA generation samples topic-word distributions and document-topic mixtures from Dirichlet distributions before sampling word positions.The process uses β for topic-word distributions and α for document-topic mixtures.
  • Corpus construction: The artificial-corpus parametrization imposes shared document-topic and topic-word hyperparameters across documents and topics.Equiprobable topics and a specified word-frequency distribution are among the stated choices.
  • Corpus construction: The chosen word probabilities can yield a Zipfian distribution described by a double power law.This distribution is specified over 95,129 words.
  • Real corpora: The real-corpus comparison spans datasets differing in genre, time of origin, average text length, document count, and language.The listed datasets include Twitter, Reuters, Web of Science, New York Times, and PLoS One.
  • Real corpora: Preprocessing includes decapitalization and replacement of punctuation and special characters for datasets other than the already filtered NYT corpus.The experiments use random subsets of documents.

D. Numerical Implementations

The numerical implementation uses established software for LDA and a C++ implementation of hSBM within graph-tool. The supplementary derivation specifies the labeled-network likelihood and its integrated marginal likelihood under noninformative priors.

  • Implementation: LDA inference uses the MALLET package, while hSBM inference is implemented in C++ as part of graph-tool’s Python library.The authors also provide usage code in a GitHub repository.
  • Likelihood calculation: For labeled networks, the supplementary derivation introduces the hSBM likelihood and then evaluates it under noninformative priors.The integrated marginal likelihood is computed after specifying the labeled-network formulation.
  • Likelihood calculation: The likelihood decomposition separates constrained graph probability, degree-sequence priors, and edge-count priors.The edge-count prior is described as a mixture of independent geometric distributions.

C. Labelled degrees and overlapping partitions

The supplementary construction models labeled degrees and overlapping partitions through hierarchical mixture assignments and conditioned degree sampling. Integer-partition distributions provide the combinatorial components used to sample degree frequencies.

  • Overlapping partitions: The model represents overlapping group memberships as mixtures, with each mixture corresponding to a specific set of groups.Mixture size is q = |b|, and overlap size can be bounded by Q.
  • Overlapping partitions: Mixture-size frequencies are sampled first, followed by mixture assignments for nodes with a given overlap size.Assignments are sampled uniformly conditional on the relevant frequencies.
  • Labeled degrees: Labeled degree sequences are sampled conditional on the overlapping partition and degree frequencies within each mixture.The construction then samples degree sums associated with labels inside mixtures.
  • Labeled degrees: The frequency of degrees is generated using integer-partition distributions and their recurrence relations.The supplementary text defines p(m,n) as partitions of m into exactly n parts and q(m,n) as partitions into at most n parts.
  • Labeled degrees: The partition-count calculations can use accurate asymptotic approximations for q(m,n).The supplementary text refers to prior work for further distributional details.

II. ARTIFICIAL CORPORA DRAWN FROM LDA

Artificial corpora are generated by sampling topic-specific word frequencies and document-specific topic frequencies, then generating each document token by token.

  • Each topic r receives word frequencies φr drawn from a V-dimensional Dirichlet distribution.
  • Each document d receives topic frequencies θd drawn from a K-dimensional Dirichlet distribution.
  • For every token in document d, the generative process proceeds sequentially across the document’s nd tokens.

B. Inference of corpora drawn from LDA

For corpora generated from LDA, the comparison uses the true topic labels to evaluate each model’s description length while separately considering inference-prior choices.

  • The generated corpora provide labeled word-document counts nᵣwd representing the true labels from LDA’s generative process.
  • The LDA description length is obtained from word-topic and document-topic count tables derived from the labeled corpus.
  • Inference specifies hyperparameters α̂dr and β̂rw, which may equal the generating hyperparameters or use a noninformative prior.
  • The noninformative inference choice sets α̂dr = 1 and β̂rw = 1.

2. Inference with SBM

The SBM represents texts as bipartite word-document networks and compares hierarchical community inference with LDA across modeling and network-scaling conditions.

  • Inference with SBM: Texts become bipartite multigraphs whose nodes are documents and words, with edge strength equal to word occurrences in documents.
  • Inference with SBM: With no document clustering, each document forms its own group while word groups correspond to LDA topics, yielding B = D + K groups.
  • Inference with SBM: With document clustering, documents and words are each clustered into K groups, yielding B = 2K groups.
  • Robustness checks: Across varied hyperparameters, topic counts, and symmetric or asymmetric base measures, hSBM qualitatively outperforms LDA with noninformative priors.
  • Network structure: Word-document networks exhibit superlinear edge scaling E ∝ N^δ with δ > 1 rather than the linear scaling typically assumed for sparse networks.
  • Empirical word frequencies: The empirical word-frequency distribution is measured from Wikipedia using V = 95129 word types and M = 5,118,442 word tokens.
Loading 1708.01677v2…