Abstract
Graph-based machine learning methods often suffer from $O(N^2)$ complexity, creating a significant bottleneck for large-scale applications. While the Variational Dual-Tree (VDT) framework provides a sub-quadratic alternative, it is limited to Euclidean distances. This paper introduces the Bregman Variational Dual-Tree (BVDT) framework, which generalizes efficient dual-tree approximations to the flexible class of Bregman divergences. By leveraging mathematical decoupling and anchor tree adaptations, BVDT maintains $O(N^{1.5} \log N)$ complexity while enabling the use of domain-appropriate metrics, such as Generalized I-Divergence for text data. Experimental results on large-scale text datasets demonstrate that BVDT significantly outperforms Euclidean-based methods in accuracy without sacrificing scalability.
Introduction
Graph-based methods are fundamental to machine learning, supporting tasks from clustering to semi-supervised learning by representing data points as nodes in a similarity graph. However, calculating similarity between every pair in a dataset of size $N$ requires $O(N^2)$ time and memory, which is unfeasible for modern large-scale datasets. For a million data points, this translates to a trillion calculations.
The existing Variational Dual-Tree (VDT) framework addresses this by using hierarchical trees to approximate the graph in blocks. However, VDT's reliance on Euclidean distance limits its effectiveness in domains like text analysis, where Euclidean measures often fail to capture meaningful similarities. BVDT overcomes this limitation by bringing computational efficiency to the broader world of Bregman divergences.
Methods and Technical Approach
The BVDT framework generalizes the dual-tree approach through several key technical innovations designed to handle the mathematical challenges of non-Euclidean spaces.
Variational Approximation and Block Partitioning
Instead of computing individual point-to-point transition probabilities, BVDT partitions the transition matrix into blocks. Each block represents the average interaction between two clusters (subtrees), significantly reducing the number of required calculations while maintaining a high-fidelity approximation of the global graph structure.
The De-coupling Trick
To maintain $O(1)$ calculation time for cluster-to-cluster distances ($D_{AB}$), the authors demonstrate that any Bregman divergence can be "de-coupled" into four sufficient statistics. These statistics are pre-calculated during tree construction, preventing the algorithm from reverting to $O(N^2)$ complexity during the similarity estimation phase.
Bregman Anchor Trees
Standard dual-trees rely on the triangle inequality and symmetry—properties Bregman divergences lack. BVDT adapts the "anchor tree" construction with a new "stealing threshold" and merging cost to maintain pruning efficiency despite mathematical asymmetry.
Probabilistic Grounding
A core strength of the framework is the bijection between Bregman divergences and exponential families. This allows the approximation to be framed as a maximum likelihood problem, providing a rigorous statistical foundation for the choice of divergence based on the underlying data distribution.
Experimental Evaluation
The framework was evaluated on five large-scale text datasets, including BBC News, 20 Newsgroup, and Large Movie Reviews (up to 50,000 documents). For these datasets, the authors derived that Generalized I-Divergence (GID) was the natural Bregman divergence by modeling text generation as a mixture of Multinomial and Poisson distributions.
Key Results
- Accuracy: BVDT with GID consistently and significantly outperformed the Euclidean VDT across all text datasets in semi-supervised learning tasks.
- Scalability: BVDT maintains the $O(N^{1.5} \log N)$ scaling of the original VDT, proving that geometric flexibility does not require a sacrifice in speed. Both VDT and BVDT are orders of magnitude faster than "Exact" $O(N^2)$ methods as dataset size grows.
- Metric Importance: A critical finding was that using an approximated method with the correct metric (GID) often outperformed exact $O(N^2)$ methods using the wrong metric (Euclidean).
Conclusion
The Bregman Variational Dual-Tree framework demonstrates that large-scale graph-based learning can be both efficient and geometrically flexible. By extending dual-tree approximations to Bregman divergences, BVDT allows researchers to apply domain-specific similarity measures to massive datasets without the prohibitive cost of quadratic complexity. Future work may extend this approach to other non-Euclidean domains such as image processing (via Mahalanobis distance) and signal processing (via Itakura-Saito distance).
Summary updated