Published on Tue Apr 03 2018

Learning on Hypergraphs with Sparsity

Canh Hao Nguyen, Hiroshi Mamitsuka

Hypergraph is a generalization of graph, in which only pairwise relations can be represented. On a hypergraph, one wishes to learn a smooth function with respect to its topology. We propose sparsely smooth formulations that learn smooth functions and induce sparsity.

0
0
0
Abstract

Hypergraph is a general way of representing high-order relations on a set of objects. It is a generalization of graph, in which only pairwise relations can be represented. It finds applications in various domains where relationships of more than two objects are observed. On a hypergraph, as a generalization of graph, one wishes to learn a smooth function with respect to its topology. A fundamental issue is to find suitable smoothness measures of functions on the nodes of a graph/hypergraph. We show a general framework that generalizes previously proposed smoothness measures and also gives rise to new ones. To address the problem of irrelevant or noisy data, we wish to incorporate sparse learning framework into learning on hypergraphs. We propose sparsely smooth formulations that learn smooth functions and induce sparsity on hypergraphs at both hyperedge and node levels. We show their properties and sparse support recovery results. We conduct experiments to show that our sparsely smooth models have benefits to irrelevant and noisy data, and usually give similar or improved performances compared to dense models.

Wed Dec 18 2013
Machine Learning
The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited
Hypergraphs allow one to encode higher-order relationships in data. Current learning methods are either based on approximations of the hypergraphs via graphs or on tensor methods which are only applicable under special conditions.
0
0
0
Mon Sep 12 2016
Machine Learning
Learning Sparse Graphs Under Smoothness Prior
In this paper, we are interested in learning the underlying graph structure behind training data. We assume that the data is smooth with respect to the graph topology. We show that the joint sparse graph learning problem can be simplified to designing only the sparse edge selection vector.
0
0
0
Mon Jan 11 2016
Machine Learning
How to learn a graph from smooth signals
We propose a framework that learns the graph structure underlying a set of Smooth signals. We show that the problem is a weighted minimization that leads to naturally sparse solutions. We present efficient, scalable primal-dual based algorithms for both our model and the previous state of the art.
0
0
0
Fri Oct 24 2014
Computer Vision
On The Effect of Hyperedge Weights On Hypergraph Learning
Hypergraph is a powerful representation in several computer vision, machine learning and pattern recognition problems. In the last decade, many researchers have been keen to develop different hypergraph models. No much attention has been paid to the design of hyperedge weights.
0
0
0
Mon May 11 2020
Machine Learning
Hypergraph Learning with Line Expansion
Previous hypergraph expansions are solely carried out on either vertex level or hyperedge level. The new expansion induces a homogeneous structure from the hypergraph by treating vertex-hyperedge pairs as "line nodes"
0
0
0
Mon Mar 14 2016
Computer Vision
Regression-based Hypergraph Learning for Image Clustering and Classification
Regression-based Hypergraph (RH) is a new type of hypergraph model. RH can be used to address image clustering and classification issues. The experimental results on six popular image databases demonstrate that the proposed RH learning algorithms achieve promising performance.
0
0
0