Abstract
We introduce a nonparametric approach to multiscale analysis of document corpora using a hierarchical matrix analysis framework called diffusion wavelets. In contrast to eigenvector methods, diffusion wavelets construct multiscale basis functions. In this framework, a hierarchy is automatically constructed by an iterative series of dilation and orthogonalization steps beginning with an initial set of orthogonal basis functions, such as the unitvector bases. Each set of basis functions at a given level is constructed from the bases at the lower level by dilation using the dyadic powers of a diffusion operator. A novel aspect of our work is that the diffusion analysis is conducted on the space of variables (words), instead of instances (documents). This approach can automatically and efficiently determine the number of levels of the topical hierarchy, as well as the topics at each level. Multiscale analysis of document corpora is achieved by using the projections of the documents onto the spaces spanned by basis functions at different levels. Further, when the input term-term matrix is a "local" diffusion operator, the algorithm runs in time approximately linear in the number of non-zero elements of the matrix. The approach is illustrated on various data sets including NIPS conference papers, 20 Newsgroups and TDT2 data.
Introduction
In text mining, the goal is often to summarize vast document collections into coherent "topics." Traditional tools like Latent Semantic Indexing (LSI) or Latent Dirichlet Allocation (LDA) typically provide a "flat" view, presenting a single list of topics. However, human knowledge is inherently hierarchical; a broad category like "Science" naturally branches into "Biology" and "Physics," which further refine into specialized fields like "Genetics" or "Quantum Mechanics."
While hierarchical models like hierarchical LDA (hLDA) exist, they are often computationally prohibitive, requiring complex Markov Chain Monte Carlo sampling and significant manual tuning of priors. This paper introduces a nonparametric, multiscale framework based on Diffusion Wavelets that is data-driven, parameter-free, and highly scalable.
Methodology: Diffusion on Word Spaces
The core innovation lies in applying Diffusion Wavelets (DWT) to the space of variables (words) rather than document instances. The process follows four key steps:
- Term-Term Matrix Construction: A normalized matrix captures the co-occurrence relationships between words.
- Diffusion and Dilation: The algorithm utilizes dyadic powers of this matrix ($T^2, T^4, T^8...$). This simulates a diffusion process where the "influence" of a word spreads across the semantic network, capturing increasingly abstract concepts at each step.
- Multiscale Basis Functions: Through a modified QR decomposition, the algorithm filters out local "noise" to identify broad "scaling functions" or topics that persist at higher levels of abstraction.
- Local Support: Unlike the dense vectors produced by LSI, these topic vectors are sparse and "local," making them significantly more interpretable for human readers.
Hierarchical Topic Discovery
One of the most powerful features of this model is its ability to automatically discover the depth of a hierarchy. The mathematics naturally signal when the hierarchy is complete—specifically when the diffusion matrix converges. For example, in the NIPS dataset, the model automatically identified five distinct levels of abstraction.
At the highest level of the NIPS corpus, the model correctly identified the two primary pillars of the conference: Machine Learning and Neuroscience. As the levels descend, it uncovers niche sub-fields such as Reinforcement Learning and Speech Recognition.
Experimental Results
The model was evaluated on three major benchmarks: NIPS papers, 20 Newsgroups, and the TDT2 dataset.
Efficiency and Speed
The multiscale analysis of 2 million tokens was completed in approximately 15 minutes on a standard PC. In comparison, the authors noted that hLDA required roughly 20 hours for the same task. This near-linear scaling is a result of the "local" nature of the diffusion operator, which avoids the $O(N^2)$ or $O(N^3)$ complexity of standard eigenvector methods.
Classification Accuracy
When using the discovered topics as features for a $k$-Nearest Neighbor classifier, the Diffusion Model consistently outperformed LDA and matched or exceeded LSI performance across the 20 Newsgroups and TDT2 datasets.
Conclusion
By shifting the focus of diffusion analysis from documents to words, this framework provides a computationally efficient way to uncover the "conceptual skeleton" of a corpus. While the model relies on a precision parameter ($\epsilon$) to determine granularity, it largely removes the need for manual topic counting. Future work may extend this multiscale approach to social network analysis and more complex author-topic modeling.
Summary updated