Hypergraph spectral learning for multi-label classification

By Liang Sun, Shuiwang Ji, Jieping Ye. 2008

297 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Urban Studies

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Urban Studies

Citations in the corpus

Transductive Multi-View Zero-Shot Learning (2015, methodology): “Interestingly, our way of deﬁning hyperedges naturally corresponds to the star expansion [46] where the query node (i.e. ψ ik ) is introduced to connect each node in the hyperedge e ij where In the embedding space Γ , similarity sets ∆ ij can be compared.”
Adversarial Multi-label Prediction for Spoken and Visual Signal Tagging (2019, background): “1y[j] denotes the jth dimension of the label vector their correlations in CCA space [4].”
Multi-Label Learning with Global and Local Label Correlation (2017, unknown): “These datasets have been widely used in multi-label learning literatures [7], [8], [11], [14], [15], [22], [26], [36], [37], [38], [39], [40], [41], [42] etc.”
Learning shared subspace for multi-label dimensionality reduction via dependence maximization (2015, background): “HSL: Hypergraph spectral learning (HSL) for multi-label classification [31].”
Transductive Multilabel Learning via Label Set Propagation (2013, background): “Sun et al. [29] employed hypergraph spectral learning to solve multilabel classification problems.”
Multilabel Classification with Principal Label Space Transformation (2012, methodology): “To further validate the advantages of PLST, future work includes extensive performance comparison of PLST with related multi-label classification algorithms, including hypergraph spectral learning (Sun et al., 2008).”
A Review on Multi-Label Learning Algorithms (2014, methodology): “Exploiting label correlations by manipulating the input space can be realized in other ways such as Canonical Correlation Analysis (CCA) [139], [140], [194] or kernel feature mapping [166].”
Music recommendation by unified hypergraph: combining social media information and music content (2010, methodology): “Our work is also related to graph-based ranking and hypergraph learning [45, 2, 3, 44, 12, 35, 7].”
Classifier chains for multi-label classification (2009, methodology): “The consensus view in the literature is that it is crucial to take into account label correlations during the classification process [3, 2, 15, 8, 11, 18, 4].”
Adaptive Hypergraph Learning and its Application in Image Classification (2012, unknown): “Hypergraph has been applied to problems of multilabel learning [22] and video segmentation [23].”
Click Prediction for Web Image Reranking Using Multimodal Sparse Coding (2014, methodology): “Hypergraphs have been applied to solve problems with multilabel learning [25] and video segmentation [26].”
Mining Multi-label Data (2010, methodology): “Finally, a hypergraph is employed in [52] for modeling higher-order relations among instances sharing the same label.”
Ieee Transactions on Knowledge and Data Engineering Context-aware Hypergraph Construction for Robust Spectral Clustering (unknown): “This has been applied to many domains such as image matching [19], multi-label classification [20], video object segmentation [21], and image retrieval [22].”