Higher order learning with graphs

ABSTRACT

Recently there has been considerable interest in learning with higher order relations (i.e., three-way or higher) in the unsupervised and semi-supervised settings. Hypergraphs and tensors have been proposed as the natural way of representing these relations and their corresponding algebra as the natural tools for operating on them. In this paper we argue that hypergraphs are not a natural representation for higher order relations, indeed pairwise as well as higher order relations can be handled using graphs. We show that various formulations of the semi-supervised and the unsupervised learning problem on hypergraphs result in the same graph theoretic problem and can be analyzed using existing tools.

REFERENCES

• 1: Sameer Agarwal , Jongwoo Lim , Lihi Zelnik-Manor , Pietro Perona , David Kriegman , Serge Belongie, Beyond Pairwise Clustering, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.838-845, June 20-26, 2005 [doi>10.1109/CVPR.2005.89]
• 2: Charles J. Alpert , Andrew B. Kahng , So-Zen Yao, Spectral partitioning with multiple eigenvectors, Discrete Applied Mathematics, v.90 n.1-3, p.3-26, Jan. 15, 1999 [doi>10.1016/S0166-218X(98)00083-3]
• 3: Mikhail Belkin , Partha Niyogi, Semi-Supervised Learning on Riemannian Manifolds, Machine Learning, v.56 n.1-3, p.209-239 [doi>10.1023/B:MACH.0000033120.25363.1e]
• 4: Marianna Bolla, Spectra, Euclidean representations and clusterings of hypergraphs, Discrete Mathematics, v.117 n.1-3, p.19-39, July 1, 1993 [doi>10.1016/0012-365X(93)90322-K]
• 5: Chung, F. R. (1993). The Laplacian of a hypergraph. In J. Friedman (Ed.), Expanding graphs (DIMACS series), 21--36. AMS.
• 6: Chung, F. R. K. (1997). Spectral graph theory. AMS.
• 7: Forman, R. (2003). Bochner's method for cell complexes and combinatorial Ricci curvature. Discrete & Computational Geometry, 29, 323--374.
• 8: David Gibson , Jon M. Kleinberg , Prabhakar Raghavan, Clustering Categorical Data: An Approach Based on Dynamical Systems, Proceedings of the 24rd International Conference on Very Large Data Bases, p.311-322, August 24-27, 1998
• 9: Venu Madhav Govindu, A Tensor Decomposition for Geometric Grouping and Segmentation, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1, p.1150-1157, June 20-26, 2005 [doi>10.1109/CVPR.2005.50]
• 10: Wen-Ch'ing Winnie Li , Patrick Solé, Spectra of regular graphs and hypergraphs and orthogonal polynomials, European Journal of Combinatorics, v.17 n.5, p.461-477, July 1996 [doi>10.1006/eujc.1996.0040]
• 11: Munkres, J. R. (1984). Elements of algebraic topology. The Benjamin/Cummings Publishing Company.
• 12: Ng, A., Jordan, M., & Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm. NIPS.
• 13: Rodríguez, J. A. (2002). On the Laplacian eigenvalues and metric parameters of hypergraphs. Linear and Multilinear Algebra, 50, 1--14.
• 14: Rodríguez, J. A. (2003). On the Laplacian spectrum and walk-regular hypergraphs. Linear and Multilinear Algebra, 51, 285--297.
• 15: Rosenberg, S. (1997). The Laplacian on a Riemannian manifold. London Mathematical Society.
• 16: Amnon Shashua , Tamir Hazan, Non-negative tensor factorization with applications to statistics and computer vision, Proceedings of the 22nd international conference on Machine learning, p.792-799, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102451]
• 17: Shashua, A., Zass, R., & Hazan, T. (2006). Multi-way clustering using super-symmetric non-negative tensor factorization. ECCV.
• 18: 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]
• 19: Smola, A., & Kondor, I. (2003). Kernels and regularization on graphs. COLT. Springer.
• 20: Zhou, D., Huang, J., & Schöölkopf, B. (2005). Beyond pairwise classification and clustering using hypergraphs (Technical Report 143). Max Plank Institute for Biological Cybernetics, Tübingen, Germany.
• 21: Zhou, D., & Schöölkopf, B. (2005). Regularization on discrete spaces. Pattern Recognition, 361--368.
• 22: Zhu, X. (2005). Semi-supervised learning literature survey (Technical Report 1530). Computer Sciences, University of Wisconsin.
• 23: Zien, J. Y., Schlag, M. D. F., & Chan, P. K. (1999). Multi-level spectral hypergraph partitioning with arbitrary vertex sizes. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 18, 1389--1399.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

General Terms:
Theory