research-article

Hypergraph spectral learning for multi-label classification

Authors:

Jieping YeAuthors Info & Claims

KDD '08: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 668 - 676

https://doi.org/10.1145/1401890.1401971

Published: 24 August 2008 Publication History

Abstract

A hypergraph is a generalization of the traditional graph in which the edges are arbitrary non-empty subsets of the vertex set. It has been applied successfully to capture high-order relations in various domains. In this paper, we propose a hypergraph spectral learning formulation for multi-label classification, where a hypergraph is constructed to exploit the correlation information among different labels. We show that the proposed formulation leads to an eigenvalue problem, which may be computationally expensive especially for large-scale problems. To reduce the computational cost, we propose an approximate formulation, which is shown to be equivalent to a least squares problem under a mild condition. Based on the approximate formulation, efficient algorithms for solving least squares problems can be applied to scale the formulation to very large data sets. In addition, existing regularization techniques for least squares can be incorporated into the model for improved generalization performance. We have conducted experiments using large-scale benchmark data sets, and experimental results show that the proposed hypergraph spectral learning formulation is effective in capturing the high-order relations in multi-label problems. Results also indicate that the approximate formulation is much more efficient than the original one, while keeping competitive classification performance.

References

[1]

S. Agarwal, K. Branson, and S. Belongie. Higher order learning with graphs. In ICML, pages 17--24, 2006.

Digital Library

[2]

M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in Neural Information Processing Systems 14, pages 585--591, 2001.

[3]

C. M. Bishop. Pattern Recognition and Machine Learning. Springer, New York, 2006.

Digital Library

[4]

M. R. Boutell, J. Luo, X. Shen, and C. M. Brown. Learning multi-label scene classification. Pattern Recognition, 37(9):1757--1771, 2004.

[5]

D. Cai, X. He, and J. Han. SRDA: An efficient algorithm for large-scale discriminant analysis. IEEE Transactions on Knowledge and Data Engineering, 20(1):1--12, 2008.

Digital Library

[6]

O. Chapelle, B. Scholkopf, and A. Zien. Semi-Supervised Learning. MIT Press, Cambridge, MA, 2006.

Digital Library

[7]

F. R. K. Chung. Spectral Graph Theory. American Mathematical Society, 1997.

[8]

A. Edelman, T. A. Arias, and S. T. Smith. The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl., 20(2):303--353, 1999.

Digital Library

[9]

A. Elisseeff and J. Weston. A kernel method for multi-labelled classification. In Advances in Neural Information Processing Systems 14, pages 681--687, 2001.

[10]

G. H. Golub and C. F. V. Loan. Matrix Computations. Johns Hopkins Press, Baltimore, MD, 1996.

[11]

D. R. Hardoon, S. R. Szedmak, and J. R. Shawe-taylor. Canonical correlation analysis: An overview with application to learning methods. Neural Comput., 16(12):2639--2664, 2004.

Digital Library

[12]

T. Hastie, R. Tibshirani, and J. H. Friedman. The Elements of Statistical Learning. Springer, New York, NY, 2001.

[13]

A. E. Hoerl and R. W. Kennard. Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1):55--67, 1970.

[14]

H. Hotelling. Relations between two sets of variables. Biometrika, 28:312--377, 1936.

[15]

F. Kang, R. Jin, and R. Sukthankar. Correlated label propagation with application to multi-label learning. In Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 1719--1726, 2006.

Digital Library

[16]

H. Kazawa, T. Izumitani, H. Taira, and E. Maeda. Maximal margin labeling for multi-topic text categorization. In Advances in Neural Information Processing Systems 17, pages 649--656. 2005.

[17]

W. Noble. Support vector machine applications in computational biology. Kernel Methods in Computational Biology. B. Schoelkopf, K. Tsuda and J.-P. Vert, ed. MIT Press, pages 71--92, 2004.

[18]

C. C. Paige and M. A. Saunders. LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software, 8(1):43--71, 1982.

Digital Library

[19]

J. A. Rodriguez. On the laplacian spectrum and walk-regular hypergraphs. Linear and Multilinear Algebra,:285--297, 2003.

[20]

A. Torralba, K. P. Murphy, and W. T. Freeman. Sharing visual features for multiclass and multiview object detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(5):854--869, 2007.

Digital Library

[21]

N. Ueda and K. Saito. Parametric mixture models for multi-labeled text. In Advances in Neural Information Processing Systems 16, pages 721--728. 2003.

[22]

R. Yan, J. Tesic, and J. R. Smith. Model-shared subspace boosting for multi-label classification. In Proceedings of the thirteenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 834--843, 2007.

Digital Library

[23]

Y. Yang and J. O. Pedersen. A comparative study on feature selection in text categorization. In ICML, pages 412--420, 1997.

Digital Library

[24]

J. Ye. Least squares linear discriminant analysis. In ICML, pages 1087--1094, 2007.

Digital Library

[25]

S. Yu, K. Yu, V. Tresp, and H.-P. Kriegel. Multi-output regularized feature projection. IEEE Transactions on Knowledge and Data Engineering, 18(12):1600--1613, 2006.

Digital Library

[26]

M.-L. Zhang and Z.-H. Zhou. Multilabel neural networks with applications to functional genomics and text categorization. IEEE Transactions on Knowledge and Data Engineering, 18(10):1338--1351, 2006.

Digital Library

[27]

M.-L. Zhang and Z.-H. Zhou. Ml-knn: A lazy learning approach to multi-label learning. Pattern Recognition, 40(7):2038--2048, 2007.

Digital Library

[28]

D. Zhou, J. Huang, and B. Scholkopf. Learning with hypergraphs: Clustering, classification, and embedding. In Advances in Neural Information Processing Systems 19, pages 1601--1608, 2007.

[29]

J. Zien, M. Schlag, and P. Chan. Multilevel spectral hypergraph partitioning with arbitrary vertex sizes. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 18(9):1389--1399, 1999.

Digital Library

Cited By

Shakya KAlavi APorteous JK PLaddi AJaiswal M(2024)A Critical Analysis of Deep Semi-Supervised Learning Approaches for Enhanced Medical Image ClassificationInformation10.3390/info1505024615:5(246)Online publication date: 24-Apr-2024
https://doi.org/10.3390/info15050246
Li YYu HLi HPan FLiu S(2024)AHD-SLE: Anomalous Hyperedge Detection on Hypergraph Symmetric Line ExpansionAxioms10.3390/axioms1306038713:6(387)Online publication date: 7-Jun-2024
https://doi.org/10.3390/axioms13060387
Lee JChae DHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)Multi-view Mixed Attention for Contrastive Learning on HypergraphsProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657897(2543-2547)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657897
Show More Cited By

Index Terms

Hypergraph spectral learning for multi-label classification
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Learning label-specific features with global and local label correlation for multi-label classification
Abstract
Multi-label algorithms often use an identical feature space to build classification models for all labels. However, labels generally express different semantic information and should have their own characteristics. A few algorithms have been ...
Multi-label classification by exploiting label correlations

Nowadays, multi-label classification methods are of increasing interest in the areas such as text categorization, image annotation and protein function classification. Due to the correlation among the labels, traditional single-label classification ...
Improving multi-label classification using semi-supervised learning and dimensionality reduction
PRICAI'12: Proceedings of the 12th Pacific Rim international conference on Trends in Artificial Intelligence

Multi-label classification has been increasingly recognized since it can assign multiple class labels to an object. This paper proposes a new method to solve simultaneously two major problems in multi-label classification; (1) requirement of sufficient ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '08: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining

August 2008

1116 pages

ISBN:9781605581934

DOI:10.1145/1401890

General Chair:
Ying Li
Microsoft adCenter Labs
,
Program Chairs:
Bing Liu
University of Illinois at Chicago
,
Sunita Sarawagi
Indian Institute of Technology, Bombay

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 August 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

KDD08

Sponsor:

KDD08: The 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 24 - 27, 2008

Nevada, Las Vegas, USA

Acceptance Rates

KDD '08 Paper Acceptance Rate 118 of 593 submissions, 20%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

184
Total Citations
View Citations
1,926
Total Downloads

Downloads (Last 12 months)85
Downloads (Last 6 weeks)5

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shakya KAlavi APorteous JK PLaddi AJaiswal M(2024)A Critical Analysis of Deep Semi-Supervised Learning Approaches for Enhanced Medical Image ClassificationInformation10.3390/info1505024615:5(246)Online publication date: 24-Apr-2024
https://doi.org/10.3390/info15050246
Li YYu HLi HPan FLiu S(2024)AHD-SLE: Anomalous Hyperedge Detection on Hypergraph Symmetric Line ExpansionAxioms10.3390/axioms1306038713:6(387)Online publication date: 7-Jun-2024
https://doi.org/10.3390/axioms13060387
Lee JChae DHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)Multi-view Mixed Attention for Contrastive Learning on HypergraphsProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657897(2543-2547)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657897
Neuhäuser LScholkemper MTudisco FSchaub M(2024)Learning the effective order of a hypergraph dynamical systemScience Advances10.1126/sciadv.adh405310:19Online publication date: 10-May-2024
https://doi.org/10.1126/sciadv.adh4053
Pei XDeng XXiong NMumtaz SWu J(2024)Complex Graph Analysis and Representation Learning: Problems, Techniques, and ApplicationsIEEE Transactions on Network Science and Engineering10.1109/TNSE.2024.341785011:5(4990-5007)Online publication date: Sep-2024
https://doi.org/10.1109/TNSE.2024.3417850
Chen JWang YZhang D(2024)HGT: Transformer Architecture for Arbitrary Hypergraphs Based on P-Laplacian2024 International Joint Conference on Neural Networks (IJCNN)10.1109/IJCNN60899.2024.10650472(1-9)Online publication date: 30-Jun-2024
https://doi.org/10.1109/IJCNN60899.2024.10650472
Alsarhan TAli SAlsarhan AGanapathi IWerghi N(2024)Human Action Recognition with Multi-Level Granularity and Pair-Wise Hyper GCN2024 IEEE 18th International Conference on Automatic Face and Gesture Recognition (FG)10.1109/FG59268.2024.10582032(1-10)Online publication date: 27-May-2024
https://doi.org/10.1109/FG59268.2024.10582032
Alsarhan TAli SGanapathi IAli AWerghi N(2024)PH-GCN: Boosting Human Action Recognition Through Multi-Level Granularity With Pair-Wise Hyper GCNIEEE Access10.1109/ACCESS.2024.347732112(162608-162621)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3477321
Zou MGan ZWang YZhang JSui DGuan CLeng S(2024)UniG-Encoder: A universal feature encoder for graph and hypergraph node classificationPattern Recognition10.1016/j.patcog.2023.110115147(110115)Online publication date: Mar-2024
https://doi.org/10.1016/j.patcog.2023.110115
Zhao CSong AZeng ZJi YDu Y(2024)Multi-modal trajectory forecasting with Multi-scale Interactions and Multi-pseudo-target SupervisionKnowledge-Based Systems10.1016/j.knosys.2024.111903296(111903)Online publication date: Jul-2024
https://doi.org/10.1016/j.knosys.2024.111903
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents