nips nips2006 nips2006-123 nips2006-123-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Dengyong Zhou, Jiayuan Huang, Bernhard Schölkopf
Abstract: We usually endow the investigated objects with pairwise relationships, which can be illustrated as graphs. In many real-world problems, however, relationships among the objects of our interest are more complex than pairwise. Naively squeezing the complex relationships into pairwise ones will inevitably lead to loss of information which can be expected valuable for our learning tasks however. Therefore we consider using hypergraphs instead to completely represent complex relationships among the objects of our interest, and thus the problem of learning with hypergraphs arises. Our main contribution in this paper is to generalize the powerful methodology of spectral clustering which originally operates on undirected graphs to hypergraphs, and further develop algorithms for hypergraph embedding and transductive classification on the basis of the spectral hypergraph clustering approach. Our experiments on a number of benchmarks showed the advantages of hypergraphs over usual graphs. 1
[1] S. Agarwal, L. Zelnik-Manor J. Lim, P. Perona, D. Kriegman, and S. Belongie. Beyond pairwise clustering. In IEEE Conf. on Computer Vision and Pattern Recognition, 2005.
[2] C. Berge. Hypergraphs. North-Holland, Amsterdam, 1989.
[3] P. Bonacich, A.C. Holdren, and M. Johnston. Hyper-edges and multi-dimensional centrality. Social Networks, 26(3):189–203, 2004.
[4] P.K. Chan, M.D.F. Schlag, and J. Zien. Spectral k-way ratio cut partitioning and clustering. IEEE Trans. on Computer Aided Design of Integrated Circuits and Systems, 13(9):1088–1096, 1994.
[5] F. Chung. Spectral Graph Theory. Number 92 in CBMS Regional Conference Series in Mathematics. American Mathematical Society, Providence, RI, 1997.
[6] A. Corduneanu and T. Jaakkola. Distributed information regularization on graphs. In Advances in Neural Information Processing Systems 17, Cambridge, MA, 2005. MIT Press.
[7] M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(98):298– 305, 1973.
[8] G. Gallo, G. Longo, and S. Pallottino. Directed hypergraphs and applications. Discrete Applied Mathematics, 42(2):177–201, 1993.
[9] D. Gibson, J. Kleinberg, and P. Raghavan. Clustering categorical data: An approach based on dynamical systems. VLDB Journal, 8(3-4):222–236, 2000.
[10] M. Gu, H. Zha, C. Ding, X. He, and H. Simon. Spectral relaxation models and structure analysis for k-way graph clustering and bi-clustering. Technical Report CSE-01-007, Department of Computer Science and Engineering, Pennsylvania State University, 2001.
[11] L. Hagen and A.B. Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE Trans. on Computed-Aided Desgin of Integrated Circuits and Systems, 11(9):1074–1085, 1992.
[12] D. Klein and C. Manning. Parsing and hypergraphs. In Proc. 7th Intl. Workshop on Parsing Technologies, 2001.
[13] M. Meila and J. Shi. A random walks view of spectral segmentation. In Proc. 8th Intl. Workshop on Artificial Intelligence and Statistics, 2001.
[14] A.Y. Ng, M.I. Jordan, and Y. Weiss. On spectral clustering: analysis and an algorithm. In Advances in Neural Information Processing Systems 14, Cambridge, MA, 2002. MIT Press.
[15] J.S. Oliveira, J.B. Jones-Oliveira, D.A. Dixon, C.G. Bailey, and D.W. Gull. Hyperdigraph– Theoretic analysis of the EGFR signaling network: Initial steps leading to GTP: Ras complex formation. Journal of Computational Biology, 11(5):812–842, 2004.
[16] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Tran. on Pattern Analysis and Machine Intelligence, 22(8):888–905, 2000.
[17] K. Tsuda. Propagating distributions on a hypergraph by dual information regularization. In Proc. 22th Intl. Conf. on Machine Learning, 2005.
[18] E.P. Xing and M.I. Jordan. On semidefinite relaxation for normalized k-cut and connections to spectral clustering. Technical Report CSD-03-1265, Division of Computer Science, University of California, Berkeley, 2003.
[19] D. Zhou, O. Bousquet, T.N. Lal, J. Weston, and B. Sch¨lkopf. Learning with local and global o consistency. In Advances in Neural Information Processing Systems 16, Cambridge, MA, 2004. MIT Press.
[20] D. Zhou, J. Huang, and B. Sch¨lkopf. Learning from labeled and unlabeled data on a directed o graph. In Proc. 22th Intl. Conf. on Machine Learning, 2005.
[21] X. Zhu. Semi-supervised learning literature survey. Technical Report Computer Sciences 1530, University of Wisconsin - Madison, 2005.