More Like this

1. Compact Representation of Uncertainty in Clustering

   Greenberg, Craig; Monath, Nicholas; Kobren, Ari; Flaherty, Patrick; McGregor, Andrew; McCallum, Andrew (January 2018, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018)

   For many classic structured prediction problems, probability distributions over the dependent variables can be efficiently computed using widely-known algorithms and data structures (such as forward-backward, and its corresponding trellis for exact probability distributions in Markov models). However, we know of no previ- ous work studying efficient representations of exact distributions over clusterings. This paper presents definitions and proofs for a dynamic-programming inference procedure that computes the partition function, the marginal probability of a cluster, and the MAP clustering—all exactly. Rather than the N th Bell number, these exact solutions take time and space proportional to the substantially smaller powerset of N . Indeed, we improve upon the time complexity of the algorithm introduced by Kohonen and Corander [11] for this problem by a factor of N. While still large, this previously unknown result is intellectually interesting in its own right, makes feasible exact inference for important real-world small data applications (such as medicine), and provides a natural stepping stone towards sparse-trellis approximations that enable further scalability (which we also explore). In experi- ments, we demonstrate the superiority of our approach over approximate methods in analyzing real-world gene expression data used in cancer treatment. 

   more » « less
2. Interactive Correlation Clustering with Existential Cluster Constraints

   Angell, Rico; Monath, Nicholas; Yadav, Nishant; McCallum, Andrew (July 2022, Proceedings of the 39th International Conference on Machine Learning)

   We consider the problem of clustering with user feedback. Existing methods express constraints about the input data points, most commonly through must-link and cannot-link constraints on data point pairs. In this paper, we introduce existential cluster constraints: a new form of feedback where users indicate the features of desired clusters. Specifically, users make statements about the existence of a cluster having (and not having) particular features. Our approach has multiple advantages: (1) constraints on clusters can express user intent more efficiently than point pairs; (2) in cases where the users’ mental model is of the desired clusters, it is more natural for users to express cluster-wise preferences; (3) it functions even when privacy restrictions prohibit users from seeing raw data. In addition to introducing existential cluster constraints, we provide an inference algorithm for incorporating our constraints into the output clustering. Finally, we demonstrate empirically that our proposed framework facilitates more accurate clustering with dramatically fewer user feedback inputs. 

   more » « less
3. Toeplitz quotient C*-algebras and ratio limits for random walks

   Dor-On, Adam (January 2021, Documenta mathematica)

   We study quotients of the Toeplitz C*-algebra of a random walk, similar to those studied by the author and Markiewicz for finite stochastic matrices. We introduce a new Cuntz-type quotient C*-algebra for random walks that have convergent ratios of transition probabilities. These C*-algebras give rise to new notions of ratio limit space and boundary for such random walks, which are computed by appealing to a companion paper by Woess. Our combined results are leveraged to identify a unique symmetry-equivariant quotient C*-algebra for any symmetric random walk on a hyperbolic group, shedding light on a question of Viselter on C*-algebras of subproduct systems. 

   more » « less
4. Online Factorization and Partition of Complex Networks by Random Walk

   Yang, Lin; Yu, Zheng; Braverman, Vladimir; Zhao, Tuo; Wang, Mengdi (July 2019, Conference on Uncertainty and Artificial Intelligence)

   Finding the reduced-dimensional structure is critical to understanding complex networks. Existing approaches such as spectral clustering are applicable only when the full network is explicitly observed. In this paper, we focus on the online factorization and partition of implicit large lumpable networks based on observations from an associated random walk. We formulate this into a nonconvex stochastic factorization problem and propose an efficient and scalable stochastic generalized Hebbian algorithm (GHA). The algorithm is able to process random walk data in a streaming fashion and learn a low-dimensional representation for each vertex. By applying a diffusion approximation analysis, we show that the continuous-time limiting process of the stochastic algorithm converges globally to the “principal components” of the Markov chain. We also establish a finite-sample error bound that matches the nonimprovable state-of-art result for online factorization. Once learned the low-dimensional state representations, we further apply clustering techniques to recover the network partition. We show that when the associated Markov process is lumpable, one can recover the partition exactly with high probability given sufficient data. We apply the proposed approach to model the traffic flow of Manhattan as city-wide random walks. By using our algorithm to analyze the taxi trip data, we discover a latent partition of the Manhattan city that closely matches the traffic dynamics. 

   more » « less
5. Scalable Hierarchical Agglomerative Clustering

   https://doi.org/10.1145/3447548.3467404  

   Monath, Nicholas; Dubey, Kumar Avinava; Guruganesh, Guru; Zaheer, Manzil; Ahmed, Amr; McCallum, Andrew; Mergen, Gokhan; Najork, Marc; Terzihan, Mert; Tjanaka, Bryon; et al (August 2021, KDD '21: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining)

   null (Ed.)

   The applicability of agglomerative clustering, for inferring both hierarchical and flat clustering, is limited by its scalability. Existing scalable hierarchical clustering methods sacrifice quality for speed and often lead to over-merging of clusters. In this paper, we present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points. We perform a detailed theoretical analysis, showing that under mild separability conditions our algorithm can not only recover the optimal flat partition but also provide a two-approximation to non-parametric DP-Means objective. This introduces a novel application of hierarchical clustering as an approximation algorithm for the non-parametric clustering objective. We additionally relate our algorithm to the classic hierarchical agglomerative clustering method. We perform extensive empirical experiments in both hierarchical and flat clustering settings and show that our proposed approach achieves state-of-the-art results on publicly available clustering benchmarks. Finally, we demonstrate our method's scalability by applying it to a dataset of 30 billion queries. Human evaluation of the discovered clusters show that our method finds better quality of clusters than the current state-of-the-art. 

   more » « less