Spectral clustering and transductive learning with multiple views

ABSTRACT

We consider spectral clustering and transductive inference for data with multiple views. A typical example is the web, which can be described by either the hyperlinks between web pages or the words occurring in web pages. When each view is represented as a graph, one may convexly combine the weight matrices or the discrete Laplacians for each graph, and then proceed with existing clustering or classification techniques. Such a solution might sound natural, but its underlying principle is not clear. Unlike this kind of methodology, we develop multiview spectral clustering via generalizing the normalized cut from a single view to multiple views. We further build multiview transductive inference on the basis of multiview spectral clustering. Our framework leads to a mixture of Markov chains defined on every graph. The experimental evaluation on real-world web classification demonstrates promising results that validate our method.

REFERENCES

• 1: Ando, A., & Zhang, T. (2007). Learning on graph with Laplacian regularization. Advances in Neural Information Processing Systems 19. MIT Press, Cambridge, MA.
• 2: Argyriou, A., Herbster, M., & Pontil, M. (2006). Combining graph Laplacians for semi-supervised learning. Advances in Neural Information Processing Systems 18. MIT Press, Cambridge, MA.
• 3: Belkin, M., Matveeva, I., & Niyogi, P. (2004). Regression and regularization on large graphs. Proc. 17th Annual Conference on Learning Theory.
• 4: Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279962]
• 5: Carlos Castillo , Debora Donato , Luca Becchetti , Paolo Boldi , Stefano Leonardi , Massimo Santini , Sebastiano Vigna, A reference collection for web spam, ACM SIGIR Forum, v.40 n.2, p.11-24, December 2006 [doi>10.1145/1189702.1189703]
• 6: Chapelle, O., Weston, J., & Schöölkopf, B. (2003). Cluster kernels for semi-supervised learning. Advances in Neural Information Processing Systems 15. MIT Press, Cambridge, MA.
• 7: Chung, F. (1997). Spectral graph theory. No. 92 in CBMS Regional Conference Series in Mathematics. American Mathematical Society, Providence, RI.
• 8: El-Yaniv, R., & Pechyony, D. (2006). Stable transductive learning. Proc. 19th Annual Conference on Computational Learning Theory.
• 9: El-Yaniv, R., & Pechyony, D. (2007). Transductive rademacher complexity and its applications. Proc. 20th Annual Conference on Computational Learning Theory.
• 10: Henzinger, M. (2003). Algorithmic challenges in web search engines. Internet Mathematics, 1, 115--123.
• 11: Joachims, T. (2003). Transductive learning via spectral graph partitioning. Proc. 20th IInternational Conference on Machine Learning.
• 12: Thorsten Joachims , Nello Cristianini , John Shawe-Taylor, Composite Kernels for Hypertext Categorisation, Proceedings of the Eighteenth International Conference on Machine Learning, p.250-257, June 28-July 01, 2001
• 13: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 14: Meila, M., & Shi, J. (2001). A random walks view of spectral segmentation. Proc. 8th International Workshop on Artificial Intelligence and Statistics.
• 15: Ng, A., Jordan, M., & Weiss, Y. (2002). On spectral clustering: analysis and an algorithm. Advances in Neural Information Processing Systems 14. MIT Press, Cambridge, MA.
• 16: Rüping, S., & Scheffer, T. (2005). Learning with multiple views. Proc. ICML Workshop on Learning with Multiple Views.
• 17: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 18: Sindhwani, V., Niyogi, P., & Belkin, M. (2005). A coregularization approach to semi-supervised learning with multiple views. Proc. ICML Workshop on Learning with Multiple Views.
• 19: Smola, A., & Kondor, R. (2003). Kernels and regularization on graphs. Proc. 16th Annual Conference on Learning Theory.
• 20: Daniel A. Spielman , Shang-Hua Teng, Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time 0(m1.31), Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.416, October 11-14, 2003
• 21: Koji Tsuda , Hyunjung Shin , Bernhard Schölkopf, Fast protein classification with multiple networks, Bioinformatics, v.21 n.2, p.59-65, January 2005 [doi>10.1093/bioinformatics/bti1110]
• 22: Tong Zhang , Alexandrin Popescul , Byron Dom, Linear prediction models with graph regularization for web-page categorization, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150510]
• 23: Zhou, D., Bousquet, O., Lal, T., Weston, J., & Schöölkopf, B. (2004). Learning with local and global consistency. Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA.
• 24: Dengyong Zhou , Jiayuan Huang , Bernhard Schölkopf, Learning from labeled and unlabeled data on a directed graph, Proceedings of the 22nd international conference on Machine learning, p.1036-1043, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102482]
• 25: Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. Proc. 20th International Conference on Machine Learning.