Learning on Hypergraphs with Sparsity
  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.
