Abstract

The field of information and knowledge management increasingly adapt methods and algorithms from advanced matrix computations, graph theory and optimization. Prominent examples are spectral clustering, non-negative matrix factorization, Principal Component Analysis (PCA) and Singular Value Decomposition (SVD), graph-Laplacian based semi-supervised learning, diffusion process, etc. Graph and matrix-based methods are rapidly becoming popular and significant in information and knowledge management for the following reasons: (1) Graph and matrix based methods are amenable to vigorous analysis and benefits from the well-established knowledge in matrix computations, graph theory and optimization; (2) Compared to probabilistic and information theoretic approaches, graph and matrix based methods are fast, easy to understand and implement; and (3) Graph and matrix based methods are especially suitable for parallel and distributed-memory computers to solve large scale challenging problems such as searching and extracting patterns from the entire Web.

This tutorial will present recent advances in algorithms and methods using graphs and matrices for modeling and analyzing massive, high-dimensional, and nonlinear-structured data. One main goal of the tutorial is to consolidate the recent ideas on information and knowledge management using graphs and matrices. We will summarize some open problems contained in this field and propose some future trends. We also wish to attract practitioners who seek novel ideas for applications.

Keywords: Graph, Matrices, Unsupervised Learning, Semi-supervised Learning

Slides[updated]

Aims and Learning Objectives

The aim of this tutorial is to consolidate the recent research works in data mining, information retrieval and machine learning communities using graphs and matrices, which starts from the classic linear algebra like PCA and SVD to the state-of-the-arts developments like nonnegative matrix factorization, label propagation and green's functions. Some applications of these methods to information and knowledge management, e.g., document clustering and classification, automatic recommendation and community discovery, will be represented. Finally the tutorial concludes with some possible future research directions.

Outline

• Part I: Introductions: Graphs and Matrices are Everywhere
• Part II: Unsupervised Learning with Graphs and Matrices
  • Dimensionality Reduction (PCA, SVD, LSA, LLE, Laplacian Embedding, LPP, Graph Embedding)
  • Clustering (K-means, Spectral Clustering, NMF and its variants)
  • Co-Clustering (Spectral, Tri-NMF)
• Part III: Semi-supervised Learning with Graphs and Matrices
  • Semi-supervised Learning with Partially Labeled Data (Label Propagation, Local & Global Consistency, Linear Neighborhood Propagation, Green's Function)
  • Semi-supervised Learning Using Side-Information (Constraint Margin Maximization, Penalized Matrix Factorization)
• Part IV: Future research Directions
  • Tensor & Hypergraph
  • Efficient & Large Scale
  • Probabilistic Models
  • Knowledge Transfer Across Different Domains     

Target Audience

All the researchers from data mining, information retrival, knowledge management and machine learning communities are welcome. The audience are assumed to have the basic knowledge on matrix theory, linear algebra and graph theory.

About the Instructors

• Fei Wang. Dr. Fei Wang has got his Ph.d. and M. E. degrees from Tsinghua University, Beijing, China in 2008 and 2006 respectively, and B. E. degree from Xidian University, Xi'an, Shaanxi, China in 2003. He is currently a postdoctoral researcher in School of Computing & Information Sciences, Florida International University working with Prof. Tao Li. His main research interests include machine learning (especially graph based learning, semi-supervised learning, clustering), data mining (especially text classification and clustering, collaborative filtering, community discovery and information retrieval) and multimedia analysis (especially image retrieval, music retrieval and video content analysis and retrieval).
• Tao Li. Dr. Tao Li got his Ph.d. degree from the University of Rochester. He is currently an assistant professor in the School of Computing and Information Sciences at Florida International University. His research interests are in data mining, machine learning and information retrieval. He has been actively working on data mining using graph and matrix based methods and has about 25 publications in this area. He is a recipient of NSF CAREER Award and IBM Faculty Research Awards.
• Chris Ding. Dr. Chris Ding got his Ph.d. degree from Columbia University. He is currently a professor in Department of Computer Science and Engineering University of Texas at Arlington. His research focuses on machine mining, bioinformatics, information retrieval. After he earned a Ph.D. from Columbia, he worked at Caltech, Jet Propulsion Lab and Lawrence Berkeley National Lab before joining UTA in 2007. He started work on spectral graph partitioning used since mid 1990s and has been working extensively on spectral clustering, matrix factorization models, K-means clustering, PCA, extension to bipartite graphs, Latent Semantic Indexing in IR and web ranking algorithms using spectral methods, with more than 30 publications in this area. He has given invited seminars on topics related to the tutorial at Stanford, Berkeley, Carnegie Mellon, U. Alberta, U. Hong Kong, IBM Research, Google Research.

Related References

• M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. NIPS 2001.
• A. Banerjee, S. Basu and S. Merugu. Multi-way Clustering on Relation Graphs. SDM 2007.
• I. S. Dhillon, Y. Guan and B. Kulis. Weighted Graph Cuts without Eigenvectors: A Multilevel Approach.
  PAMI 2007.
• I. S. Dhillon. Co-Clustering Documents and Words Using Bipartite Spectral Graph Partitioning.
  KDD 2001.
• C. Ding, X. He, and H. D. Simon. On the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering. SDM 2005.
• C. Ding, T. Li, W.Peng and H. Park. Orthogonal Nonnegative Matrix Tri-factorizations for Clustering.
  KDD 2006.
• C. Ding, T. Li, M. I. Jordan. Convex and Semi-Nonnegative Matrix Factorizations. Technical Report. 2006.
• C. Ding, R. Jin, T. Li and H. D. Simon. A Learning Framework Using Green's Function and Kernel Regularization with Application for Recommender System. KDD 2007.
• X. He and P. Niyogi. Locality Preserving Projections. NIPS 2003.
• X. He, D. Cai, H. Liu, and W.-Y. Ma. Locality Preserving Indexing for Document Representation. SIGIR 2004.
• D. D. Lee and H. S. Seung. Learning the parts of objects with nonnegative matrix factorization.
  Nature 1999.
• D. D. Lee and H. S. Seung. Algorithms for Non-negative Matrix Factorization. NIPS 2000.
• T. Li, C. Ding, Y. Zhang, and B. Shao. Knowledge Transformation from Word Space to Document Space. SIGIR 2008.
• T. Li, C. Ding and M. l. Jordan. Solving Consensus and Semi-supervised Clustering Problems Using Nonnegative Matrix Factorization. ICDM 2007.
• T. Li and C. Ding. The Relationships Among Various Nonnegative Matrix Factorization Methods for Clustering. ICDM 2006.
• S. Roweis and L. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science 2000.
• J. Shi and J. Malik. Normalized Cuts and Image Segmentation. PAMI 2000.
• F. Wang, S. Chen and T. Li, Changshui Zhang. Semi-Supervised Metric Learning by Maximizing Constraint Margin. CIKM 2008.
• F. Wang, T. Li and C. Zhang. Semi-Supervised Clustering via Matrix Factorization. SDM 2008.
• F. Wang, S. Ma, L. Yang and T. Li. Recommendation on Item Graphs. ICDM 2006.
• F. Wang and C. Zhang. Label Propagation Through Linear Neighborhoods. ICML 2006.
• W. Xu, X. Liu, Y. Gong. Document Clustering Based on Non-negative Matrix Factorization. SIGIR 2003.
• S. Yan, D. Xu, B. Zhang and H. Zhang. Graph Embedding: A General Framework for Dimensionality Reduction. CVPR 2005.
• D. Zhou , O. Bousquet, T.N. Lal, J. Weston and B. Schölkopf. Learning with Local and Global Consistency. NIPS 2003.
• X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. ICML 2003.
• X. Zhu and Z. Ghahramani. Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University, 2002.