Bipartite graph partitioning and data clustering

By Hongyuan Zha, Xiaofeng He, Chris H. Q. Ding, Ming Gu, Horst D. Simon. International Conference on Information and Knowledge Management, 2001

389 citations recorded by the source corpus.

Many data types arising from data mining applications can be modeled as bipartite graphs, examples include terms and documents in a text corpus, customers and purchasing items in market basket analysis and reviewers and movies in a movie recommender system. In this paper, we propose a new data clustering method based on partitioning the underlying bipartite graph. The partition is constructed by minimizing a normalized sum of edge weights between unmatched pairs of vertices of the bipartite graph. We show that an approximate solution to the minimization problem can be obtained by computing a partial singular value decomposition (SVD) of the associated edge weight matrix of the bipartite graph. We point out the connection of our clustering algorithm to correspondence analysis used in multivariate analysis. We also briefly discuss the issue of assigning data objects to multiple clusters. In the experimental results, we apply our clustering algorithm to the problem of document clustering to illustrate its effectiveness and efficiency.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/09036439c33d38aa46cb8b6bbfbf5ad82f1cc852

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Geometry and Topology

Citations in the corpus

Two supervised learning approaches for name disambiguation in author citations (2004, methodology): “Existing word clustering methods we can apply include methods based on the Word Net [5], distributional word clustering [3, 31, 13, 14], bipartite word clustering [42], and committee-based word clustering [27].”
Real-time automatic tag recommendation (2008, methodology): “Thetaggedtraining documents aretreated astripletsof(words,docs,tags), and represented in two bipartite graphs, which are partitioned into clustersby SpectralRecursiveEmbedding(SRE).”
Minimum Sum-Squared Residue Co-Clustering of Gene Expression Data (2004, methodology): “Different normalizations of genes and conditions are compared in [13]; however, the algorithms in [13] and [6, 20] model the gene expression matrix as a bipartite graph with non-negative edge weights where the quality of a co-cluster by the normalized cut criterion of [15].”
The Relationships Among Various Nonnegative Matrix Factorization Methods for Clustering (2006, background): “(3) This form gives a good framework for simultaneously clustering the rows and columns of X [35].”
Spectral Clustering with Two Views (2007, methodology): “This trick is used in the co-clustering literature (Dhillon, 2001; Zha et al., 2001), but there the affinity submatrix W is derived simply from the term document matrix (or equivalent) not derived as a product of affinity matrices from different views 1.”
Hierarchical Clustering Algorithms for Document Datasets (2005, neutral): “Viewing the documents in this fashion, a number of edge-cut-based criterion functions can be used to cluster document datasets [7, 17, 34, 13, 43, 10].”
Name disambiguation in author citations using a K-way spectral clustering method (2005, methodology): “Existing word clustering methods we can apply include meth-ods based on the Word Net [7], distributional word clustering [6, 38, 14, 16], bipartite word clustering [53], committee-based word clustering [33], and other word similarity measures [46, 29] .”
Empirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering (2004, methodology): “Viewing the documents in this fashion, a number of edge-cut-based criterion functions can be used to cluster document datasets (Cheng & Wei, 1991; Hagen & Kahng, 1991; Shi & Malik, 2000; Ding et al., 2001; Zha et al., 2001a; Dhillon, 2001).”
Document clustering by concept factorization (2004, neutral): “Spectral clustering based bipartite normalized cut (BP) [3] [15] 10.”
Segmentation using superpixels: A bipartite graph partitioning approach (2012, background): “The costs of SVD and the Lanczos are quite close to each other.”
Large Scale Spectral Clustering Via Landmark-Based Sparse Representation (2015, background): “Given a bipartite B, bipartite graph normalized cut [8], [39] seeks to simultaneously partition the data points and the landmarks based on the spectral graph theory.”
Cross-view action recognition via view knowledge transfer (2011, methodology): “Unlike [13] and [17], where a bipartite graph is used to model the document-to-word relationship, we employ a bipartite graph to model the visual-word to visual-word relationship.”