1

Learning on Hypergraphs with Sparsity
Canh Hao Nguyen and Hiroshi Mamitsuka Member,IEEE
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 areobserved. 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 generalframework that generalizes previously proposed smoothness measures and also generates 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 theirproperties and sparse support recovery results. We conduct experiments to show that our sparsely smooth models are beneficial tolearning irrelevant and noisy data, and usually give similar or improved performances compared to dense models.
Index Terms—Sparse Learning, Learning on Hypergraphs, Learning on Graphs, Sparsistency.

F

1

I NTRODUCTION

Graphs and hypergraphs are very useful in data analysis,by which they currently are of much interest in machinelearning, particularly when dealing with high-dimensional
data and complicated distributions [1], [2]. It is the main toolfor network analysis [3], [4]. Hypergraphs can be found inbroad applications: multi-label learning [5], computer vision[6], biology [7], information retrieval [8], social networks[3] and scientific literature [4]. For encoding high-orderrelationships among objects, hypergraphs have been studied
in different settings. One is high-order logical relationships
among many objects, being the subject of statistical relational
learning area [9], [10]. Another is the collective classification
or regression [11], [12], in which the relationships are notspecified and need to be learnt [13]. However, in this paper,
we consider the setting of hypergraphs with similarity
relationship.
While graphs encode various types of relationship [3], [4],similarity relationship has received the most of the interest. In
similarity graphs, the main target is to learn smooth functions
in many problems such as the graph Laplacian regularization[14], harmonic functions on graphs [15], Lp Laplacians [16],trend filtering on graphs [17]. These are the main tools
for semi-supervised learning [18], manifold learning, graphembedding [19] and clustering on graphs [20]. The main
assumption behind these methods is that the graphs are
random geometric [21], meaning that the nodes of a graph are
randomly sampled from a fixed but unknown distribution
and the edges encode their neighborhood relationship (by aknn or an  neighborhood graph).
In this paper, we focus on learning with similarity hypergraphs, in which the nodes in a hyperedge of a hypergraph aremeant to be similar to each others. This is a direct generalization of similarity graphs with the assumption that the nodes••

Canh Hao Nguyen is with Institute for Chemical Research, Kyoto
University, Japan.
E-mail: canhhao@kuicr.kyoto-u.ac.jp
Hiroshi Mamitsuka is with Institute for Chemical Research, Kyoto
University, Japan and Department of Computer Science, Aalto University,
Finland, 02150 Espoo, Finland.
E-mail: mami@kuicr.kyoto-u.ac.jp

on a hyperedge are random samples from a neighborhood in
an unknown underlying space. Therefore, smooth functions
also play a key role in this setting. On graphs, smoothness
measures are mainly based on the graph Laplacian [14] andits variants [16], [22]. However, generalizing to smoothness
measures on hypergraphs poses new challenges. So far, inmost of the methods, smoothness measures on hypergraphs
have been studied simply by reducing hypergraphs to graphs
using clique or star expansions [23], [24]. Since these expansions are not one-to-one mappings, the original hypergraphtopology is lost, potentially resulting in information loss
and other undesirable effects such as graphs with different
hyperedge degrees. Another direction is total variation [25],which is later shown to be inflexible for several reasons.
One of the main problems in machine learning is thatdata can be noisy or irrelevant to the problem. This could
happen with hypergraphs and it is desirable to handle itexplicitly. For example, in predicting house price, data cancome in form of a hypergraph, of which each hyperedge isa group of houses. A hyperedge containing houses in thesame street is relevant to the problem in the sense that theirprices are expected to be similar (i.e. prices are smooth on
the hyperedge). However, a hypergraph for houses whose
owners are of the same ethnic group might be irrelevant. In
recommending music for users on social networks, while
communities (as hyperedges) with the same listening patternmight be relevant, communities with the same workplace
might not. This is inherently similar to irrelevant and noisy
features problem in multivariate data. In such data, withadditive models, sparse learning [26], [27] is a solution
due to its ability to make the models sparse, potentiallyremoving irrelevant and noisy data automatically. Lasso [26]would be able to eliminate irrelevant features to the problem
and its variants [28], [29], [30] can detect noisy features
within a given group using appropriate sparse-inducing
regularization terms. It is noteworthy that previous work on
hypergraph did not explicitly consider noisy and irrelevant
information, potentially hindering their performances inpractice.
In this work, we aim to derive new hypergraph learning

2

methods that are theoretically sound and flexible enough tohandle noisy and irrelevant information in the data set. Ina similar manner to additive models, to eliminate irrelevant
hyperedges and noisy nodes, we wish to incorporate sparsity
into hypergraph learning that automatically detect irrelevant
hyperedges and noisy nodes. In hypergraph setting, sparsity ismeant to be that (i) the label is very smooth on only a small
number of hyperedges (highly non-smooth on others), or (ii)the label is very similar on some nodes, different on others
within a single hyperedge. These concepts are to be definedformally later on.
We first present a unified framework that generalizes allother smoothness measures for graphs/hypergraphs, such asgraph Laplacian-based learning, star and clique expansions[24] or total variation [25]. The framework allows to analyze
if a measure can be achieved with expansions, or whether it isuseful for keeping hypergraph information in its formulation.
The framework is general enough to be used to design
new smoothness measures. We then derive sparsely smooth
formulations, which learn functions on the nodes of a hypergraph that are smooth on only a subset of nodes or hyperedges
in a hypergraph. We further present theoretical propertiesof learning on hypergraphs that statistical consistency ofsparse support recovery (sparsistency) of these models can beachieved. Finally, we conducted experiments to show that
our formulations allow us with great flexibility in supervised
learning on hypergraphs. Overall, the contributions of thiswork are:
1)

2)

3)

We present a unified framework for the problem oflearning smooth functions on hypergraphs that covers all previously proposed smoothness measures.
We propose new models for learning smooth functions with sparsity on hypergraphs at both hyperedge and node levels.
We show the theoretical properties of our formulations, including computational efficiency and consistency of sparse support recovery. We also empiricallyexamine the performance of several models in thisframework and show the benefit of sparse models.

This paper is organized as follows. Section 2 describes
the unified smoothness measure framework, which is a
generalization of previous work. We show a key property
that learning on hypergraph cannot be achieved by simply
using graphs. Section 3 and 4 devotes to formulation andtheoretical analyses of learning on hypergraph with sparsity.
We then show simulations to show properties of theseformulations. Sections 6 shows experiments on real data
sets to show how sparsity can help improve supervised
learning performances. We then conclude the paper.

2

S MOOTHNESS M EASURES ON H YPERGRAPHS

A hypergraph G is defined as G = (V, E) comprising of
a node set V and hyperedge set E . As an example of asimilarity hypergraph in Figure 1, the nodes are sampledfrom an unknown space with hyperedges are nodes lying
in fixed neighborhoods. Each hyperedge is a subset of theVnodes, E = {ek }m
k=1 and E ⊆ 2 . Cardinality |V | = n and|E| = m. Each hyperedge e ∈ E is a subset of the nodes withsize |e| and weight w(e) (could be given or set appropriately

street 1

street 2
2

1
3
4
5

7
6

street 3

Fig. 1: Hypergraph example with nodes, which are houses ina neighborhood, numbered from 1 to 7. Hyperedges (street 1,street 2 and street 3) contain houses on the same streets. For
the problem of predicting house prices, this is a similarity
hypergraph as houses on the same street are expected tohave similar prices.
for each method). Note that a graph is a special hypergraphwith the special requirement that each hyperedge is of size 2.
It is commonly assumed that the set of hyperedges encode
similarity relationship among the nodes in V .
Similar to learning on graphs, for the similarity relationship in hypergraphs, it is expected that the nodes in thesame hyperedge tend to have similar labels, such as thesame class, the same cluster assignment or similar regression
values. Therefore, the label function to be learnt will vary
less within a hyperedge. These label functions will be calledsmooth on the graph or hypergraph. This is why smoothness
measures are at the core of learning problems on graphs
and hypergraphs: to score how much a label function varies
within the hyperedges.
We show that all previously proposed smoothness measures of a function f : V → R on graph or hypergraph G,
with fi being the value on node i, has the following unified
form (as in Table 1):

sh(f ) = Te∈E (ti,j∈e (wij · s(fi , fj ))),
•
•
•
•
•

(1)

sh(f ): smoothness measure of function f (on G),
T (.): the function combining smoothness measureson all hyperedges,t(.): the function combining smoothness measures on
all pairs of nodes belonging to a hyperedge,s(fi , fj ): smoothness measure on the pair of nodes(i, j), andwij : weight of pair of nodes (i, j).

In other words, smoothness measure of a function on a
hypergraph is a combination (T ) of smoothness measureson each hyperedge, which, in turn, is a combination (t) ofsmoothness measures on all pairs of the nodes in the hyperedge. The combinations, at both hypergraphor hyperedgePlevels, can have many variants such as , max, lp and otherpossibilities.
There are many variants of smoothness measures bysimply choosing different T and t. We list them in Table 1 andshow their corresponding
names and interpretations. WhenP
T and t are bothor max, the smoothness measures of a

3

TABLE 1: Different variants of (1) as smoothness measures for graphs/hypergraphs. Unreferenced formulations are newly
derived from this framework.
type
graph
graph
graph
graph
hypergraphhypergraphhypergraphhypergraphhypergraphhypergraphhypergraph

T
P
P
P
max
P
P
P
max
max

any
P 1
( ·) p

t
.
.
.
.
P
max
max
P

s(fi , fj )(fi − fj )2|fi − fj |p|fi − fj |p→∞|fi − fj |(fi − fj )2|fi − fj ||fi − fj ||fi − fj ||fi − fj |sh(f )
f T Lf : graph Laplacian [31]< f, ∆p f >: p-Laplacian [16]Lipschitz extension (lex-minimizer) [22]Lipschitz extension (inf-minimizer) [22]f T Lf of clique/star expansion [24]clique expansion + 1-Laplacian
total variation [25]inf-minimizer + star/clique expansion
max hyperedge smoothness

P 1( ·) p|fi − fj |pwithin-hyperedge lp normany|fi − fj |p

between-hyperedge lp normPhypergraph can be expressed in the smoothness measuresof its star or clique expansion graph. In the other cases
listed in the Table, sh cannot be computedon expansion
Pgraphs. For example, when T = , t = max, then sh(f )becomes the sum of maximum differences in all hyperedges,
which is total variation [25]. The reason sh(f ) cannot becomputed in its star or clique expansion graphs is that
hyperedge information is no longer available in graphs.
This kind of measures is unique to hypergraph setting anduseful for keeping hypergraph information (which star andclique expansions would fail to keep). It can be seen thatthese variants captures all previously proposed smoothness
measures to the best of our knowledge. There are also manyother variants that have not been proposed before. Therefore,
within this general framework, we could propose many newsmoothness measures, shown as the ones without referencesin the table.

3

S PARSELY S MOOTH M ODELS

While there are many existing and newly proposed smoothness measures for hypergraphs as in the previous Section,
it is the main objective of this work to study the casesof smoothness measures with sparsity property, to show
different sparsity patterns and their usefulness. Sparsity is
an exciting topic in machine learning and statistics, used
to improve interpretability, robustness, effectiveness andefficiency of learning models [32]. It have been used to
select features in additive models such as lasso [26] andmany extensions in many situations. Similar to learning
additive models, we consider the problem that there aremany hyperedges that are irrelevant to the problem or withina hyperedge, many nodes are noisy. This is a practical setting
as one may have data of a hypergraph without knowing
which hyperedges are useful for the prediction problem inhand. In this case, one wishes to learn a function f on (thenode set of) a hypergraph that:1)

2)

f is only smooth on an unknown subset of thehyperedge set Er ⊆ E , not smooth on the rest Ei(= E\Er ). In this case, we say that f has the property
of hyperedge-wise sparsity or hyperedge selection.
f is only smooth on an unknown subset of the nodes
in a hyperedge. We say that f has the property ofnode-wise sparsity or node selection.

Definition. Any function f with either of the two
properties is called sparsely smooth. Ideally, smoothness
measure can be 0 on some hyperedges/nodes, so that these
hyperedges/nodes are considered relevant to the problem
while the other hyperedges/nodes are not. However, thisis not usually possible in practice. The solution is to have a(nonzero) cut-off threshold that separates smooth and nonsmooth hyperedges or nodes, which we call hyperedge or node
selection ability, respectively.
3.1

Supervised Learning

In the scope of this paper, we specifically deal with supervised learning problem. We work on regression setting,with smoothness measures are used as regularization. Classification, semi-supervised learning can be done by simply
replacing the label fitting term in the objective function. For
regression, we are given a hypergraph G on which we know
the label of some node encoded in label vector L ∈ Rn . We
also assume that in the hypergraphs, some hyperedges are
not supposed to be relevant to the learning problem. To learn
sparsely smooth functions on a hypergraph, we formulate
the following optimization problem

1f ∗ = arg minn |f − Y |2L + λsh(f ).
f ∈R 2(2)

with λ is the tradeoff parameter between faithfulness to
the known label Y and smoothness measures. |.|L is thedifference between the known and predicted labels only on
the nodes with known labels. T and t are chosen so that sh has
hyperedge and/or node selection abilities. Since constraining
a fixed number of nodes/hyperedges usually results incomputationally inefficient and non-optimal formulations,
we use l1 norm in a similar manner to lasso [26] as a convex
relaxation of the problem. We use a lasso-like formulation,
which can be regarded as star expansion, equipped with l1
norm for sparsity while preserving convexity.
3.2

Sparsely Smooth Models

We propose new formulations using a slack variable µk
for each hyperedge ek ∈ E , which can be interpreted
as star expansion-styled formulations and µk becomesthe label of star node of ek , which plays the role ofmean/central/representative label of a hyperedge. Note thatwhile the formulations we propose are still mathematically4equivalent to, but not of exactly the same form as the generalform of smoothness measure in (1). We propose to use thefollowing formulation:sh(f ) = Tek (ss(f, ek ))(3)

where ss(f, ek ) is the smoothness measure on hyperedge ek .
ss(f, ek ) plays the same role as ti,j∈e (wij · s(fi , fj )) in (1).
We show some examples of ss(f, ek ) that we
Pwill use later.
Case 1. ss1 (f, ek ) = minµk ∈R w(ek ) i∈ek |fi − µk |.
ss1 (f, ek ) is the sum of absolute differences between thelabels of the nodes in hyperedge ek and a value µk thatis chosen to minimize the sum. This smoothness measureshows the total difference of the labels from µk , which play
the role of a representative label of the hyperedge.
Case 2. ss2 (f, ek ) = minµk ∈R w(ek ) maxi∈ek |fi − µk |.
ss2 (f, ek ) is the maximum absolute difference of all thelabels of the nodes in ek from a value µk that is chosen
to minimize the maximum difference. A property of thismeasure is that µk becomes the midpoint of the maximum
and minimum labels of the nodes. In other words,

1w(ek )(max(fi ) − min(fi ))
i∈ek
i∈ek
2
1
= w(ek ) max |fi − fj |.
i,j∈ek2

min ss2 (f, ek ) =µk ∈Rand µk becomes the median of {fi }i∈ek . Using l1 norm
constraint, many of the |µk −fi | would be close to zero, giving
this formulation node selection ability. Having δk2 would not
make many δk = 0, therefore no hyperedge selection ability.
Definition 3. Joint hyperedge and node selection: the formulation ismX
12
f ∗ = arg
min
|f
−
Y
|
+
λ
w(ek )δk(6)
Lf ∈Rn ,δk ,µk ∈R 2
k=1
X
s.t
|µk − fi | ≤ δk , k = 1..m.
i∈ek

Similar to (5), at the optimal solution, slack variable

δk =

m
X
1
|f − Y |2L + λw(ek )δkf ∈R ,δk ,µk ∈R 2
k=1

TABLE 2: Comparison of smoothness measures and theirsparse-inducing property.
Selectionnone
hyperedges
node
joint

3.3

At the optimal solution of (4), slack variable δk =maxi∈ek |µk − fi | and µk is set to minimize δk . This makesw(ek )δk = ss2 (f, ek ) as in the aforementioned case 2. Hence,µk becomes the mid-range of fi , ∀i ∈ ek . δk becomes half of
their range and δk is half of total variation. This formulation
is mathematically equivalent to total variation regularization(with appropriate λ) using star expansion style with µk plays
the role of label of star node [25]. This is more efficient thanoriginal total variation formulation as analyzed later on. This
formulation
Pm has hyperedge selection ability in the sense thathaving k=1 w(ek )δk , which is similar to l1 norm of thevector (δk )mi=1 , many δk would become 0, and the remaining
become large. One can select hyperedges that have verysmooth labels on them.
Definition 2. Node selection: the formulation is

s.t

X

m
X
1
|f − Y |2L + λw(ek )δk2
f ∈R ,δk ,µk ∈R 2
k=1

min
n

|µk − fi | ≤ δk , k = 1..m.

i∈ek

At the optimal solution, slack variable

δk =

X
i∈ek

|µk − fi | =ss1 (f, ek ),w(ek )

T
P
Pk
k

maxk
P
k

P ss(f, ek ) 2i∈ek |µk − fi |max
P i∈ek |µk − fi ||µ − fi |Pi∈ek ki∈ek |µk − fi |(4)s.t |µk − fi | ≤ δk , ∀i ∈ ek , k = 1..m.

f ∗ = arg

ss1 (f, ek ).
w(ek )

Having |µk − fi | would have node selection ability in thesense that many
Pm |µk − fi | would become 0. Different from(5), having
k=1 w(ek )δk in the objective function, thisformulation has hyperedge selection ability in a similarmanner to (4). Table 2 summarizes sparse-inducing property
of formulations.

Definition 1. Hyperedge selection: our efficient version of total
variation [25], the formulation isminn|µk − fi | =i∈ekNote that this is half of total variation [25].
Using the notion of ss(f, ek ), we can define our sparsely
smooth formulations as follows.

f ∗ = arg

X

(5)

Properties

We show properties of our sparsely smooth formulations one
by one.
Computation. All these formulations are quadratic programs, can be solved efficiently with off-the-shelf softwares.
Note that these formulations, similar to star-expansion,
incur m more variables to optimize. However, instead ofcomputing all fi − fj in a hyperedge, we use |µk − fi ||e |(|e |−1)constraints, reducing from k 2k
to |ek | terms, with |ek |being the number of nodes in the hyperedge. For the problem
having hyperedges of large cardinalities, star expansionstyled formulations are recommended.
Regularization parameter λ. It is noteworthy that toolarge λ will lead to many smooth hyperedges/nodes. The
reason is that large λ forces smoothness measures of all
hyperedges to be small, making the gap between those of
relevant hyperedges and of irrelevant hyperedges small. The
small gap is then dominated by random error of labels,
making relevant and irrelevant hyperedges indistinguishable.
Hence, different from additive models [26], sparsely smoothmodels need small enough λ. This is purely for sparse
support recovery purpose. It is noteworthy that too small λis not for generalization purpose that requires λ not to bearbitrarily small (or large). Finding the balance is a key issue,
but is out of the scope of this paper.
Related formulations. Our proposed formulations arecorresponding to two well-known formalisms in sparse5learning: generalized adaptive fused lasso [27], [33] for
its requirement of parameters with similar values, andoverlapping group lasso with intra-group or inter-group
sparsity [29], [30]. In fact, joint hyperedge and node selection
formulation is a generalization of fused lasso to a the wholegroup (rather than only two variables for usual fused lasso).
Out-of-Sample Extension. Previous models for learningon graphs and hypergraphs are only in transductive setting,requiring test samples to be included at training time. In our
proposed formulations with star expansion in (4) (5) and (6),
we can have out of sample extension, meaning that labels of
new samples can be predicted with (µ̂k , δk ), k = 1, . . . , m,without re-learning the model. This is advantageous compared to transductive learning models. For new samples(nodes) with known hyperedge membership, their labels f
can be inferred based on its hyperedge representative/meanlabels {µ̂k }k and their smoothness measures δk by optimizing the same objective function as learning the model (3)with fixed µk as follows.

fˆ = arg min Tek (ss(f, ek )) s.t µk = µ̂k .
f

3.4

(7)

Sparsistency

We wish to see if these formulations would recover the
support of a set of hyperedges that are relevant to the
problem in the same manner as lasso and others [34], [35].
This is known as model support consistency, and for sparsemodeling, it is called sparsistency. Since each hyperedge isassociated with a smoothness measure, a relevant hyperedge
should have a small enough smoothness measure and an
irrelevant hyperedge should not. We first define relevant andirrelevant hyperedges based on their smoothness measures.
We then introduce assumptions about noise level and how
the hypergraph is constructed as n → ∞ before main results
showing the probability of recovering the correct sparsemodels.
Definition 4. γ -smooth: Label function f is considered γ smooth on a given hyperedge e if and only if its smoothness
measure satisfies ss(f, e) ≤ γ .
Definition 5. Relevant hyperedges: Given a γr ∈ R, a
hyperedge e is relevant to the problem with true label y if and only
if y is γr -smooth on e.
Definition 6. Irrelevant hyperedges: Given a γi ∈ R, a
hyperedge e is irrelevant to the problem with true label y if andonly if y is not γi -smooth on e.
3.4.1

General assumptions

We present the set of general assumptions behind oursparsistency analysis.
(1) Noise assumption. Each observed label Yi is the truelabel yi plus white Gaussian noise: (Yi − yi ) ∼ N (0, δ 2 ).
(2) Relevance assumption. We assume that all hyperedges in E are either relevant (γr -smooth) or irrelevant (notγi -smooth) to the problem with given γr , γi ∈ R.
(3) Separation assumption. We assume that the relevant
and irrelevant hyperedge sets, as defined above, are disjoint,
meaning that γi > γr . γi − γr should be large enough tomake sure that the two set of hyperedges can be separated

according to their smoothness measures with high probability. We note that this plays a similar role as Irrepresentable
Conditions for Lasso consistency [34].
iLet γ = γr +γ
be the midpoint of {γr , γi }. Call the2
set of relevant hyperedges Er = {e1 , · · · er } and irrelevant
hyperedges Ei = {er+1 , · · · em }. We call Er the support of the
problem. We now show the probability that star expansionstyled joint hyperedge and node selection formulation (6)and star expansion-styled hyperedge selection formulation(4) will recover the correct (sparse) model support in thesense that the relevant hyperedges are γ -smooth but theirrelevant hyperedges are not.
3.4.2 Sparsistency for hyperedge selection (4)This is the case for

ss = ss2 = min w(ek ) max |fi − µk |.
µk ∈R

i∈ek

This is equivalent to total variation in [25]. As also usedin [25], we let w(ek ) = 1 for the reason that smoothness
measure does not increase linearly with the number of nodes
in a hyperedge.
To simplify discussion, we use the following growthmodel. As having more training data n → ∞, we assume
that the hyperedge set is fixed and the number of points
belonging to each hyperedge grows linearly with n, meaning|e |that rk = nk = const with respect to n. This follows
the assumption that, similarity hypergraphs are generated
from connecting the nodes in fixed neighborhoods in a
latent space of the nodes, in a similar manner to random geometric graphs. Sampling more data points boils
down to the process of sampling on each neighborhood
separately. This makes w(ek ) = |e1k | = O(n−1 ), andnw(ek )) = r1k . Let d ∈ Rn be the scaled weight vector:
PP1
di = n k|i∈ek w(ek ) =. Let R = maxk rk
k|i∈ek rPkP
and D = maxi k|i∈ek dk = maxi k|i∈ek r1k , which areconstants with respect to n. The sparsistency result is shownas follows.
Theorem 1. Suppose that the general assumptions hold. Without
loss of generality, assume
that all labels have unit range yi , Yi ∈√[0, 1] and γi −γr > 2√π2δ . As ss(f, ek ) = minµ∈R maxi |µ−fi |,letX1fˆ = arg minn |Y − f |2 + λss(f, ek )f ∈R 2kbe the optimal solution√of the learning√ problem (equivalent to (4)).
π(γi −γr ))−2 2δ√Then for 0 < λ <, with a probability of at
D πleast (1 − 1+c1 2 n )n for some constant c, it will recover the correct
support of the problem in the sense that:1)2)fˆ is γ -smooth on all hyperedges in Er , andfˆ is not γ -smooth on all hyperedges in Ei .

Please find the detailed proof√ in the next Section.
The condition γi − γr > 2 δ√π2 is a necessary condition
for sparsistency. This states that the smoothness gap γi − γrshould be higher than the later term, which is the label
error incurred by white noise in observed labels (N (0, δ 2 )).
The condition for λ means that it has to be small enoughnot to force the label to be smooth on all hyperedges.
This looks counter-intuitive as one usually requires higher

6

regularization hyperparameters to force irrelevant variables
to have zero weights in lasso [26]. However, this actually
makes sense by the nature of smooth functions in hypergraphsituation where smaller λ would not force all smoothness
measures to be small, making smoothness measures ofirrelevant hyperedges to be much larger than those of
relevant hyperedges, resulting in a large gap and hence,sparsistency can be obtained. Similarly, λ needs to be smallenough to guarantee sparsistency.
One thing to note about the probability is as follows.

lim (1 −n→∞−1
1)n = 1 − e c2 < 1
2
1+c n

There is one key implication is that, the lower bound forprobability of sparsistency (1 − 1+c1 2 n )n does not converge to
1 as n → ∞. Sparsistency is only guaranteed with a limited
probability regardless of sample size n. This is a drawback ofsparsistency result of total variation [9]. While this result does
not automatically mean that sparsistency cannot be achieved,
another argument can be used to show the limitation of
hyperedge selection (total variation) as follows.
Proposition 1. Suppose that Xn is any set of n white noises
xi = Yi − yi ∼ N (0, δ 2 ), then for any constant a ∈ R,

lim P (max |xi | < a) = 0.

n→∞

i∈Xn

Proof. This is the case we assume that the differences between
node labels and the representative label µ̂k follow a zeromean and fixed standard deviation. In this case, total
variation, which is twice as large as the maximum absolutedeviation, would go to infinity as n → ∞ aslim P ( max |xi | < a) = lim P (|xi | < a)∀i

n→∞

n→∞

i=1···n= lim P (|x| < a)n = 0.
n→∞This is obvious as the larger the sample size is, the larger the
maximum deviation (half of total variation) becomes. Hence,as n → ∞, maxi=1···n |Yi − yi | would go to infinity withhigh probability, exceeding the magnitude of the constants
γr , γi and δ . Hence, at some large n on, there is a highprobability that ss(f, e) is fully dominated by errors of theobserved labels. This is different from the previous caseof joint hyperedge and node selection where the mean ofabsolute deviation converges to a constant. This explains thelack of sparsistency guarantee in Theorem 1.
3.4.3 Sparsistency for joint hyperedge and node selection(6)
This is the case for

ss = ss1 = min w(ek )
µk ∈R

X

|fi − µk |.

We use the same growth model with n → ∞ and fixed
hyperedge set, γr , γi and δ to simplify discussion. The
following theorem shows the conditions and probability
that the model recovers the correct support.
Theorem 2. Suppose that the general assumptions hold. Assume
that the gap is wide enough with respect to√label noise standard
deviation δ in the sense that γi − γr > 2√π2δ . As ss(f, ek ) =Pminµ∈R |e1k | i∈ek |fi − µ|, the optimal solution of the learning
problem (equivalent to (6))
X
1fˆ = arg minn |Y − f |2 + λss(f, ek )f ∈R 2k√√π(γ −γ )−2 2δi√ r
for 0 < λ <will, with a probability of at least
2 πDR−1
1 − O(n ), recover the correct support of the problem in the sense
that

1)
2)

fˆ is γ -smooth on all hyperedges in Er , andfˆ is not γ -smooth on all hyperedges in Ei .

Proof can be found in the next Section. The theorem
states that under general assumptions, if the regularization
parameter (γ ) is small enough, the optimization problem willfind the correct sparsity pattern with a probability of at least
1 − O(n−1 ). In other words, as n → ∞, the probability of
having sparsistency approaches 1 with a O(n−1 ) rate. Thismeans that the model is statistically consistent by converging
to the true model with large enoughn.
√
The condition γi − γr > 2 δ√π2 has the same interpretation
as in Theorem 1. That is the level of noise should not exceed
the level of signal. The condition of mall enough λ is also
required.
All in all, we presented the conditions to recover thecorrect model support of the two formulations (4) and (6) .
While sparsistency of (6) is guaranteed with large n, it is not
the case for (4).
We note that this is different from hyperedge lasso [36] inseveral aspects. First, our framework is strictly about learningsmooth functions on a hypergraph. However, in [36], there isan additional constraint that labels from different hyperedges
must be different. This is the case of non-overlapping hyperedges. As non-overlapping hyperedges divides the node
set into disjoint subsets without any interrelationship, theirlabels can be learnt separately and this becomes unrelated
problems. Our setting of overlapping hyperedges is more
realistic.

4

P ROOF FOR S PARSISTENCY

Due to their lengths, we present sparsistency proofs in thissection.

i∈ek

We assign w(ek ) = |e1k | , making ss(f, ek ) =Pminµ∈R |e1k | i∈ek |fi − µ| the mean absolute deviation oflabels on the hyperedge. This is suitable as we consider ngrows (n → ∞) while keeping γi , γr and δ constant. In
this setting, all these parameters and ss would be of thesame magnitude. Note that there might be other weights,
but in these cases, λ cannot remain a constant, which notconvenient for practical uses.

4.1

Sparsistency for hyperedge selection

ss(f, ek ) = min w(ek ) max |mk − fi |
mk ∈R

i

We first prove two lemmas to support the main proof.
For w(ek ) = 1.
Lemma 1. Given a true label function y on a hypergraph. Supposethat label Y is a noisy observation with white noise in the sense that(yi −Yi ) are independent following a normal distribution N (0, δ 2 ).

7Then, with a probability of at least√√δ√ 2+ tδ √π−2
and ∀t ≥ 0.
π
nπ

t2n
(1+t2 )n , max|yi − Yi | <Proof. As (yi − Yi ) follows normal distribution with standard
deviation δ , according to one-sided Chebyshev’s inequality(also known as Cantelli’s lemma), for any i,
√
√
δ 2
π−2
t2
P (|yi − Yi | − √ ≤ tδ √
.
)≥
π
nπ
1 + t2
Then, ∀i = 1..n,

√
√
π−2
δ 2
P (max |yi − Yi | − √ ≤ tδ √
)
i
π
nπ
√
√
π−2
δ 2
=P (∀i : |yi − Yi | − √ ≤ tδ √
)
π
nπ
t2n
≥
.
(1 + t2 )nLemma 2. Given any label Y on a hyperedge e. Let max |f −Y | = maxi∈1..n |fi − Yi | and likewise max |f − Y |e =maxi∈e |fi − Yi |. Any close approximate f of Y would havesmoothness measure close enough to that of Y by:ss(Y, e) − w(e) max |f − Y |e≤ss(f, e)≤ss(Y, e) + w(e) max |f − Y |e .
(8)P
Proof. Let µy = P
arg minµ∈R w(e) i∈e |yi − µ| and µf =arg minµ∈R w(e) i∈e |fi − µ|. We prove the second inequality.
ss(f, e) = w(ek ) max |fi − µf |i∈e

≤ w(e) max |fi − µy |i∈e

≤ w(e) max(|Yi − µy | + |fi − Yi |)i∈e≤ ss(Y, e) + w(e) max |f − Y |e .

Proof. Step 1: Bounding max |f − Y |.
For 0 ≤ Yi ≤ 1, let mk = arg minm maxi∈ek (fi − m).
Hence mk becomes the mid-range value of fi , and therefore
0 ≤ mk ≤ 1.
Let f (abuse the notation of fˆ for simplicity)Pbe the optimal solution of f = arg minf ∈Rn 21 |Y − f |2 + λ k ss(f, ek ).
Then, at the optimal point,P∂( 12 |Y − f |2 + λ k ss(f, ek ))= 0.
∂f
Set the partial derivative on fi to be zero. Derivative of thefirst term (quadratic) is f − Y . Note that ss(f, ek ) is notdifferentiable.
However, we can have the subderivatives ofP
k ss(f, ek ) and −(f − Y ) should be in this range.
P
We show that any directional derivative of k ss(f, ek )didifor fi is contained within [−λ 2 , λ 2 ].
Step 1.1: For each ek . Let take an infinitesimal change ∂fi
of fi . If fi is not at the border (|fi − µk | < maxj |fj − µk | =ss(f, ek )), then fi + ∂fi would not change ss(f, ek ), making
the directional derivative 0. If fi is at the border (|fi − µk | =k)maxj |fj −µk | = ss(f,ew(ek ) ) then taking an infinitesimal change∂fi of fi still keeps fi at the border, and µk , being the midrange, would change ∂f2 i . In this case, ss(f, ek ) would changew(ek )∂fiw(e )making the directional derivative either 2 k or2−w(ek ). Then the directional derivative of ss(f, ek ) on fi is2∂ss(f,ek )k ) λw(ek )∈ [− λw(ebounded by, 2 ].
∂fi
2
Step 1.2: For the whole hypergraph: summing from all
ek , we have upper boundPPk|i∈ek w(ek )k|i∈ek w(ek )(fi − Yi ) ∈[−λ
,λ
]
2
2
di di
=[−λ , λ ]22(−(fi − Yi ) is in the range of the subderivative of the latterterm).
Therefore, we have:λd
λd≤ fˆ − Y ≤
2
2
λdi
λD
max|f − Y | < maxi
=
(9)
2
2
(as D = maxi di being the max degree of any node, being
constant with respect to n).
Step 2: bounding ss(f, ek ).
Step 2.1: For relevant hyperedges Er : k = 1..r:−Due to symmetry, we can also have the first inequality.

ss(Y, e) ≤ ss(f, e) + w(e) max |f − Y |ess(Y, e) − w(e) max |f − Y |e ≤ ss(f, e).

We now restate and prove the main theorem
Theorem 1. Suppose that the general assumptions hold.
Without loss of generality, assume that√all labels have unit
range yi , Yi ∈ [0, 1] and γi − γr > 2√π2δ . As ss(f, ek ) =minµ∈R maxi |µ − fi |, letX1fˆ = arg minn |Y − f |2 + λss(f, ek )f ∈R 2kbe the optimal solution√of the learning√ problem (equivalent to (7)).
π(γi −γr ))−2 2δ√Then for 0 < λ <, with a probability of at
D πleast (1 − 1+c1 2 n )n for some constant c, it will recover the correct
support of the problem in the sense that:1)2)fˆ is γ -smooth on all hyperedges in Er , andfˆ is not γ -smooth on all hyperedges in Ei .

••ss(y, ek ) < γr as in the general assumptions.
ss(Y, ek ) < γr + w(ek ) max |y − Y |ek (Lemma 2).

Then, according to Lemma 1, for any t > 0, with a probability
t2n
of at least (1+t
2 )n , we can have:
√
√
δ 2
π−2
√
ss(Y, ek ) < γr ++ tδ √.
(10)πnπThen, according to Lemma 2 and (9),√√δ 2
π − 2 λDss(f, ek ) < γr + √ + tδ √
+
π
nπ
2
2n

(11)

t
with a probability of at least (1+t
2 )n .
Step 2.2: For irrelevant hyperedges Ei : k = (r + 1)..m8••

ss(y, ek ) > γi as in the general assumptions.
ss(Y, ek ) > γi − w(ek ) max |y − Y |ek (Lemma 2).

Then, according to Lemma 1, for any t > 0, with at2n
probability of at least (1+t
2 )n , we can have:
√
√
δ 2
π−2
ss(Y, ek ) > γi − √ − tδ √
.
(12)
π
nπ
Then, according to Lemma 2 and (9),√√δ 2
π − 2 λDss(f, ek ) > γi − √ − tδ √
−
π
nπ
2

(13)

t2n
with a probability of at least (1+t
2 )n .

Hence, from (12) and (13) we can bound the estimated f .
Step 2.3: For all hyperedges. We investigate the condition
that there exists λ > 0 and t > 0 such that smoothness
measures of relevant hyperedgesare√√ smaller than those ofδ√ 2irrelevant hyperedges: γr + π +tδ √π−2
+ λD
2 < γ ∀k = 1..rnπ√√(equivalently, γi − δ√π2 − tδ √π−2
− λD
2 > γ ∀k = (r + 1)..m).
nπ√This is equivalent to γr + δ√π2 < γ , or√2 2δ√γi − γr >
.
π

(14)

√

With the condition that γr + δ√π2 < γ , then we can choose√

λ > 0 such that γ−γr − δ√π2 − λD
2 > 0 ∀k = 1..r , equivalently√

γi − γ − δ√π2 − λD
2 > 0 ∀i = (r + 1)..m), or equivalently:
λ<

√
√
√
π(γi − γr )) − 2 2δ2(γ − γr ) 2 2δ
√
− √ =
.
D
D π
D π

(15)

With
condition (15), then we choose t so√that√√ λ satisfying
δ√ 2
+ λD
−
γr + δ√π2 + tδ √π−22 < γ (equivalently, γi −nππ√tδ √π−2− λD
2 > γ ). Choosing the largest possible t0 :nπ√√
δ 2 λDnπt0 = √(γ − γr − √ −
).
(16)
π
2
δ π−2
√
√
Note that t0 = O( n). To simplify (16), let t = c n for someconstant c. For λ satisfying (15), t0 satisfying (16) we canconclude that••

we assume that the number of nodes in a hyperedge growlinearly with hypergraph size, meaning that rk are constant,0
so are R and R . Hence w(ek ) = nr1k = O(n−1 ).
We first prove some lemmas to support the main proof.
Lemma 3. Given a true label function y on a hypergraph. Supposethat label Y is a noisy observation with white noise in the sensethat (yi − Yi ) are independent following a normal distribution1
N (0, δ 2 ). Then, with a probability of at least 1 − 1+t
2 , for ∀t ≥ 0,q√ |y−Y |1− δ√π2 ≤ tδ π−2nπn .
Proof. As (yi − Yi ) is follows normal distribution with standard deviation δ ,√|yi − Yi | follows a half-normal distributionqwith a mean of δ√π2 and a standard deviation of δ 1 − π2 .
PnHence, |y − Y |1 =i=1 |yi − Yi |, as the sum of√n
independent random variables, will have a mean of nδ√π2qand a standard variation of δ n(1 − π2 )According to one-sided Chebyshev’s inequality (alsoknown as Cantelli’s inequality),r√nδ 2 
2
t2
P |y − Y |1 − √≤ tδ n(1 − ) ≥π
π
1 + t2
Dividing the inequality by n, then
r
√


δ 2
π−2
t2
|y − Y |1
− √
≤ tδ
≥
P
n
π
πn
1 + t2|y−Y |

meaning that the probability
that n 1 is far enough from√2
its expected value δ √π approaches zero as n → ∞.
Lemma 4. Given
any two labels f and Y on a hyperedge e. LetP|f − Y |e = i∈e |fi − Yi |. Then their smoothness measure on e
is bounded by each other in the sense that.

ss(Y, e) − w(e)|f − Y |e ≤ ss(f, e) ≤ ss(Y, e) + w(e)|f − Y |e .
(17)
P
Proof. Let µy = P
arg minµ∈R w(e) i∈e |yi − µ| and µf =arg minµ∈R w(e) i∈e |fi − µ|.
ss(f, e) = min w(e)µ∈R

ss(f, ek ) < γ ∀k = 1..r andss(f, ek ) > γ ∀k = (r + 1)..m= w(e)t2n1n0with a probability of at least (1+t
2 )n = (1 − 1+c2 n ) .
0−1

Note that, limn→∞(1− 12 )n =(1− 21 )n = e c2 (with e
1+c n
c n
being Euler’s number, the base of natural logarithm) notconverging to 1.

Sparsistency for joint selectionX
ss(f, ek ) = min w(ek )|fi − µk |
µ∈R

1
|e|

i∈ek

We set w(e) =to avoid hyperedge weight size
effect. This setting makes the smoothness measure on each|e |hyperedge become the average variance. Let rk = nk ,0
R = maxk=1..m rk and R = mink=1..m rk . For simplicity,|fi − µ|i∈eX|fi − µf |i∈e

≤ w(e)

X|fi − µy |i∈e

≤ w(e)X(|Yi − µy | + |fi − Yi |)i∈e= w(e)
4.2

X

X|Yi − µk | + w(e)|f − Y |e .

i∈ekThis proves the second inequality. Due to symmetry, the firstinequality can be equivalently induced.
We now restate and prove the main theorem.
Theorem 2. Suppose that the general assumptions hold.
Assume that the gap is wide enough with respect to label√ noise2√ 2δ
standard deviation δ in the sense that γi − γr >
. As
π

9

P
ss(f, ek ) = minµ∈R |e1k | i∈ek |fi − µ|, the optimal solution of
the learning problem (equivalent to (9))

X
1fˆ = arg minn |Y − f |2 + λss(f, ek )f ∈R 2k√√π(γ −γ )−2 2δi√ r
for 0 < λ <will, with a probability of at least
2 πDR−1
1 − O(n ), recover the correct support of the problem in the sense
that

1)
2)

fˆ is γ -smooth on all hyperedges in Er , andfˆ is not γ -smooth on all hyperedges in Ei .

The theorem states that under general conditions, if theregularization parameter is small enough, the optimization
problem will find the right (γ ) sparsity pattern with aprobability that approaches 1 as n → ∞. We abuse thenotation to use fi for fˆi for simplicity from here on.

Then, according to Lemma 3, for any t > 0, with a probability
1of at least 1 − 1+t
2,
s
√
δ 2
π−2
ss(Y, ek ) < γr + √ + tδπ
π|ek |√√π−2
δ 2= γr + √ + tδ √
.
(19)
π
nrk π
P
P
As D = maxi k|i∈ek dk = maxi k|i∈ek r1k , lemma 4
together with (18) give:√√δ 2
π − 2 X λdiss(f, ek ) < γr + √ + tδ √+π
nrk π i∈e n
k
√
√
δ 2
π−2
≤ γr + √ + tδ √+ λDrk .
(20)
π
nrk π
Step 2.2: For irrelevant hyperedges in Ei , k = (r + 1)..m••

Proof. Step 1: bounding f − Y .
PAs fˆ = arg minf ∈Rn 12 |Y − f |2 + λ k ss(f, ek ), at the
optimal point, derivative of the objective function becomeszero.
P∂( 12 |Y − f |2 + λ k ss(f, ek ))= 0.
∂f
Set the partial derivative on each fi to be zero. Derivativeof the first term (quadratic) is (fi − Yi ). The second term is
not everywhere differentiable.
However, we can have thePsubderivative of k ss(f, ek ) and −(fi − Yi ) in its range at
optimal point of f .
Step 1.1: For each ek , we show that any directional derivative of ss(f, ek ) is contained within
P [−λw(ek ), λw(ek )]. Notethat as µk = arg minµ∈R w(ek ) i∈ek |fi − µ|, µk is either
the median of all {fi }i∈ek if |ek | is an odd number or within
the two medians of {fi }i∈ek if |ek | is an even number.
Let take an infinitesimal change ∂fi of fi , then µk onlychanges if i is exactly the median point (fi = µk ). In thiscase, the total change to ss(f, ek ) is 0 as µk changes withfi , fi − µk = 0. For all the other cases, ss(f, ek ) onlychanges at |fi − µk | being w(ek )∂fi as µk remains the same.
Hence, the maximum change of ss(f, ek ) is w(ek )∂fi . Then,the directional derivative of ss(f, ek ) on fi is bounded by∂ss(f,ek )∈ [−λw(ek ), λw(ek )].
∂fi
Step 1.2: For the whole hypergraph, summing up fromall ek :(fi − Yi ) ∈ [−λX
k|i∈ekw(ek ), λXw(ek )].

Then d is constant with respect to n. Then we have(18)

Step 2: bounding ss(f, ek ).
Step 2.1: For relevant hyperedges in Er : k = 1..r••Then, according to Lemma 3, for any t > 0, with a1probability of at least 1 − 1+t
2,
s
√
δ 2
π−2
ss(Y, ek ) > γi − √ − tδππ|ek |
√
√
δ 2
π−2
.
(21)
= γi − √ − tδ √πnrk πLemma 4 together with (18) give:√√δ 2
π − 2 X λdiss(f, ek ) > γi − √ − tδ √−π
nrk π i∈e n
k
√
√
δ 2
π−2
> γi − √ − tδ √− λDrk .
πnrk πss(y, ek ) ≤ γr as in the general assumptions.
ss(Y, ek ) ≤ ss(y, ek ) + w(ek )|y − Y |ek (Lemma 4).

(22)

Hence, from (20) and (22), we can bound the estimated f .
Step 2.3: For all hyperedges. We investigate the condition
that there exist λ > 0 and t > 0 so that smoothness measuresof relevant hyperedges
are smaller than those of irrelevant√δ√ 2hyperedges: γr + π < γ , then for λ > 0 such that γ − γr −√√δ√ 2
− λDrk > 0 ∀k = 1..r, (equivalently γi − δ√π2 − λDR −π

γ > 0 ∀k = (r + 1)..m ), or equivalently:√√√
γ − γr − δ√π2π(γi − γr ) − 2δ
√
λ<
=
DR
πDR

(23)

as R = maxk rk in the growth model.
For√λ satisfying
this condition (23), then for any t so√that
√
π−2
δ√ 2
√
γr + π + tδ nrk π + λDR ≤ γ ∀k (equivalently γi − δ√π2 −√k|i∈ek−λd
λd≤f −Y ≤.
nnss(y, ek ) > γi as in the general assumptions.
ss(Y, ek ) > ss(y, ek ) − w(ek )|y − Y |ek (Lemma 4)

π−2tδ √nr− λDrk ≥ γ ∀k ), such as:
kπ
√ 0
√
δ 2
nR π
√
t0 = (γ − γr −− λDR) √
(24)
π
δ π−2
√
Note that t0 = O( n). For λ satisfying condition in (23),t0 satisfying the condition in (24), we can finally conclude
that
•
•

ss(f, ek ) < γ ∀k = 1..r, andss(f, ek ) > γ ∀k = (r + 1)..m

1−1with a probability of at least 1 − 1+t).
2 = 1 − O(n010S IMULATION

•

•
•
•

(i) dense: the non-sparse model in the sense that it
does not use l1 regularization (equivalent to star andclique expansions [24], [37] and then using graphLaplacian regularization),(ii) hyperedge selection: (4) equivalent to total variation model [25],(iv) node selection: (5) (our proposed formulation),(iii) joint selection: (6) (our proposed formulation).

dense
hyperedge selection
joint selection
node selection

0.2

RMSE

We designed experiments with simulated data to demonstrate how sparsely smooth models work and the benefitof sparsity. Similarity hypergraphs were generated keeping
in mind that nodes on a hyperedge are from a fixed neighborhood in some unknown space as follows. Labels vector
Y for 200 nodes were i.i.d. samples following a uniform
distribution on [0, 1]. Ten relevant hyperedges were generated
as ten groups of nodes i that a ≤ y(i) < a + 0.15 for evenly
spaced a from 0 to 0.9. A number of irrelevant hyperedges(depending on the simulations) were generated by randomly
grouping 20 points regardless of Y . A number of noisy nodes
were randomly chosen to add into each relevant hyperedge.
Ten-fold cross-validation to split train/test data and averaged
RMSEs over ten runs. We used transductive setting to include
test data at learning stage for all models. The lower the RMSE,
the better the model. Tradeoff parameter λ was chosen to be
the one with the lowest RMSE among {10i−5 }, i = 1..7. To
show the properties of different sparsely smooth models, we
compare the following models:

0.15

0.1

0.05

0

0

2

4

6

8

10

Number of irrelevant hyperedges

Fig. 2: Simulation with irrelevant hyperedges without noisy
nodes. X axis was the number of irrelevant hyperedges
and y axis was the RMSEs of different models on test
data. Hyperedge selection method gave the lowest RMSEs
consistently at different numbers of irrelevant hyperedges.

dense
hyperedge selection
joint selection
node selection

0.25
0.2

RMSE

5

0.15
0.1
0.05
0

0

2

4

6

8

10

Number of noisy nodes

5.1

Irrelevant Hyperedges

This is to simulate the situation that there are irrelevant
hyperedges in data. We generated hypergraphs with different
numbers of irrelevant hyperedges ranging from 1 to 10,
without noisy nodes. We split the data to train and test
as described above. We summarized RMSEs of the models
for different numbers of irrelevant hyperedges in Figure 2.
We could observe that hyperedge selection model had very
stable performances even when the number of irrelevant
hyperedges increased. In contrast, the other models weresensitive to the number of irrelevant hyperedges. This
showed that hyperedge selection model could select relevant
hyperedges in presence of irrelevant hyperedges without
noisy nodes while the other methods were not as effectively.
5.2

Noisy Nodes

We simulated the case of having only noisy nodes inside
relevant hyperedges (no irrelevant hyperedges). We generated hypergraphs with different noisy nodes and without
irrelevant hyperedges. We slitted train/test data and conducted experiments in the same way as above. We showed
RMSEs of the models for different numbers of noisy nodesin Figure 3. We found that hyperedge selection model has
the worst performance in terms of RMSEs consistently. The
other models, while sensitive to the number of noisy nodes,
have lower better performances with lower RMSEs. Joint
hyperedge and node selection model were the one withthe lowest RMSEs, then followed by node selection anddense models. The experiments showed that joint selection
model had similar performances to node selection models

Fig. 3: Simulation with noisy nodes and without irrelevant
hyperedges. X axis was the number of noisy nodes added toeach hyperedge and y axis was the RMSEs of the models. Hyperedge selection model had the worst performances while
the node selection and joint selection models performed bestin terms of RMSEs.
only, showing its flexibility in case of noisy nodes without
irrelevant hyperedges.
5.3

Both Irrelevant Hyperedges and Noisy Nodes

We simulated this case by having five irrelevant hyperedges
and different numbers of noisy nodes on each relevant
hyperedge and carried out experiments in a similar manner.
RMSE results were shown in Figure 4. We found that joint
hyperedge and node selection model (6) had the lowest
RMSEs consistently. It showed the ability of this model toselect both hyperedges and nodes at the same time. Allother models, dense, hyperedge selection and node selection
models, were not as effective to handle this case. We would
consider this was the most practical case as there would be
irrelevant and noisy data in the dataset. In this case, ourproposed joint selection model was the most advantageous
due to its flexibility to handle both irrelevant hyperedges
and noisy nodes.
5.4

Sparsity with λWe also showed the sparsistency arguments (3.3) on simulated data with five relevant/irrelevant edges with our

11

dense
hyperedge selection
joint selection
node selection

0.25

RMSE

0.2

0.15

0.1

0.05

0

2

4

6

8

10

Number of noisy nodes

Fig. 4: Simulation data with both irrelevant hyperedges
and noisy nodes, generated with five irrelevant hyperedges.
X axis was different numbers of noisy nodes added toeach relevant hyperedge and y axis was the RMSEs of themodels. Joint selection gave the lowest RMSEs, showing its
effectiveness for both irrelevant hyperedges and noisy nodes.

Fig. 5: Simulation results on hypergraphs with five relevant
hyperedges and five irrelevant hyperedges. X axis was theindexes of hyperedges. From 1 to 5 were relevant hyperedges
and from 6 to 10 were irrelevant ones. Y axis was thesmoothness measures on each hyperedge with different λ.
We could observe that when λ were small enough, large
gaps occured between smoothness measures of relevant andirrelevant hyperedge groups.
proposed joint selection model. Data were split to train andtest as above. We showed the smoothness measures (δk )with different values of regularization parameter λ. It wasproved in theory that the gap between smoothness measuresof a relevant hyperedge and an irrelevant hyperedge isguaranteed if λ was small enough. We could confirm thetheory in Figure 5 that, as λ decreased, smoothness measureson relevant hyperedges (indexed from 1 to 5) became significantly smaller than that of irrelevant hyperedges (indexed 6
to 10).

6

E XPERIMENTS

We conducted experiments on real benchmark data to show
the effectiveness of the four models in real situations, together
with a general method not for hypergraphs. We compared
regression performances of these models to show the benefitsof learning sparsely smooth models on hypergraphs. We also
compared the performances of regression trees [38], being ageneral method for multivariate data not for hypergraphs, toshow how hypergraph assumption works in general setting.
We generated a hypergraph from multivariate categorical
data as follows. For each categorical variable, each groupof points having the same category formed a hyperedge.
The set of all hyperedges (for all categories of all variables)
formed the hypergraph. We chose multivariate categorical
data that were publicly available in UCI machine learning
repository [39]. Parameter setting of this experiment was thesame as in simulations. We used ten-fold cross-validation
to split train/test data and averaged RMSEs over ten runs.
We collected the least RMSEs for different hyperparametervalues from its predefined set (as in previous section).
Performances of the models were shown in Table 3. We
observed that, among the models for hypergraphs, sparsely
smooth models always have lower or equal RMSEs comparedto the dense model. In fact, four out of eight datasets showed
the significantly lowest RMSEs, which are all from sparsemodels.This might be attributed to the fact that sparse models
are usually robust to irrelevant hyperedges and noisy nodes.
We could conclude that sparsely smooth models are generallearning tools for hypergraphs and can be used to test for
irrelevant hyperedges or noisy nodes. However, comparedto more general models such as regression trees, hypergraphbased methods can only have higher performances in a few
cases. This is expected as the data are more suitable forgeneral models, not for smooth models. However, the rarehigher performance of hypergraph based methods is highly
encouraging because this result shows that smoothness
models can sometimes be better candidates for multivariate
data analysis. Using or incorporating smooth models in thesesituations would be beneficial, potentially improving usualmodels as well as smooth models.

7

C ONCLUSION

The paper dealt with the problem of learning smoothfunctions on hypergraphs in the presence of irrelevant
hyperedges and noisy nodes. We first proposed a generalframework of smooth functions that includes all previous
models. The framework could be used to derive many newmodels. To address the case of noisy and irrelevant data, we
propose to incorporate sparse learning into hypergraph setting. To deal with irrelevant hyperedges and noisy nodes, we
proposed sparsely smooth formulations to learn the functions
that are smooth on a small number of hyperedges/nodes. We
showed their sparse-inducing properties and analyzed theirsparse support recovery (sparsistency) results. We found thatour proposed joint selection model was able to recover thecorrect sparse support while hyperedge selection model wasnot. We then conducted experiments on simulated and real
data to validate their properties and performances. Sparsely
smooth models were shown to be more robust in the presenceof irrelevant hyperedges and noisy nodes. In summary, ourproposed models guaranteed both theoretical soundness andpractical effectiveness.
In this work, we could see that hypergraphs resemble
multivariate data with each hyperedge plays the role of afeature. This is different from graph setting where edges,
involving only two nodes, are too sparse to be considered
as features. Various problems of multivariate data may

12

TABLE 3: RMSEs of the four models on real data. n and m are the numbers of nodes and hyperedges, respectively. Bold fontis the lowest RMSEs among the hypergraph-based methods with 95% statistical significance using t-test. The models withthe lowest RMSEs are sparse models. For regression trees, the cases that with the lowest RMSEs among all the methods areemphasized with italic numbers.
DatasetHayesRoth
LensesCongress
Spect
TicTacToe
Car
Monks
Balance

n
132
24
435
267
958
1728
124
625

m
15
9
48
44
27
21
17
20

Dense
0.587±0.044
0.730±0.215
0.373±0.011
0.384±0.035
0.468±0.009
0.692±0.043
0.469±0.008
0.831±0.013

Hyperedge Selection
0.600±0.071
0.574±0.248
0.473±0.012
0.400±0.021
0.476±0.009
0.462±0.026
0.437±0.023
0.955±0.010

happen to hypergraphs as well. Not only noisy or irrelevant
variables can be handled with sparse learning, there aremany other possibilities such as variable dependency andinteraction. These are future directions of great promise.
Another lesson is that it is possible to consider multivariate
data as hypergraphs. However, it is noteworthy that learningsmooth models are meant for similarity hypergraphs only,
may not work well with multivariate data in general, as evidenced by the comparison with regression trees experiment.
Nevertheless, it is also possible that the usual models (suchas additive models) and smooth models may co-exist in asingle dataset that some features should be in usual models
while others should be in smooth models. Combining these
two types of models would improve both of them. This isalso a promising future direction. H. M. has been supported
in part by JST ACCEL (grant number JPMJAC1503), MEXT
Kakenhi (grant numbers 16H02868 and 19H04169), FiDiPro
by Tekes (currently Business Finland) and AIPSE programby Academy of Finland.

R EFERENCES
O. Chapelle, B. Scholkopf, and A. Zien, Semi-Supervised Learning,
1st ed. The MIT Press, 2010.
[2] Y. Ma and Y. Fu, Manifold Learning Theory and Applications, 1st ed.
CRC Press, Inc., 2011.
[3] D. J. Cook and L. B. Holder, Mining Graph Data. John Wiley &Sons, 2006.
[4] M. Newman, Networks: An Introduction. Oxford University Press,
Inc., 2010.
[5] L. Sun, S. Ji, and J. Ye, “Hypergraph spectral learning for multi-label
classification,” in Proceedings of the 14th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining, ser. KDD ’08.
ACM, 2008, pp. 668–676.
[6] P. Ochs and T. Brox, “Higher order motion models and spectralclustering,” in 2012 IEEE Conference on Computer Vision and Pattern
Recognition, 2012, pp. 614–621.
[7] D. A. Weighill and D. A. Jacobson, “3-way networks: Applicationof hypergraphs for modelling increased complexity in comparative
genomics,” PLoS Computational Biology, vol. 11, no. 3, 2015.
[8] J. Bu, S. Tan, C. Chen, C. Wang, H. Wu, L. Zhang, and X. He, “Music
recommendation by unified hypergraph: Combining social media
information and music content,” in Proceedings of the 18th ACM
International Conference on Multimedia, ser. MM ’10. ACM, 2010,
pp. 391–400.
[9] L. Getoor and B. Taskar, Introduction to Statistical Relational Learning(Adaptive Computation and Machine Learning). The MIT Press, 2007.
[10] L. De Raedt, K. Kersting, and S. Natarajan, Statistical Relational
Artificial Intelligence: Logic, Probability, and Computation. Morgan &Claypool Publishers, 2016.
[11] P. Sen, G. M. Namata, M. Bilgic, L. Getoor, B. Gallagher, andT. Eliassi-Rad, “Collective classification in network data,” AI
Magazine, vol. 29, no. 3, pp. 93–106, 2008.
[1]

Node Selection
0.758±0.076
0.767±0.227
0.444±0.010
0.405±0.057
0.481±0.019
0.748±0.043
0.528±0.029
0.916±0.014

Joint Selectection
0.746±0.067
0.770±0.227
0.306±0.034
0.404±0.031
0.476±0.009
0.740±0.044
0.504±0.004
0.629±0.044

Regression Trees
0.293 ± 0.014
0.661 ± 0.040
0.209 ± 0.009
0.408 ± 0.018
0.234 ± 0.017
0.219 ± 0.010
0.330 ± 0.037
0.650 ± 0.019[12] C. Loglisci, A. Appice, and D. Malerba, “Collective regression forhandling autocorrelation of network data in a transductive setting,”
Journal of Intelligent Information Systems, vol. 46, no. 3, pp. 447–472,
2016.
[13] T. Pham, T. Tran, D. Q. Phung, and S. Venkatesh, “Column networks
for collective classification,” in AAAI. AAAI Press, 2017, pp. 2485–
2491.
[14] F. R. K. Chung, Spectral Graph Theory. American MathematicalSociety, 1997.
[15] X. Zhu, Z. Ghahramani, and J. D. Lafferty, “Semi-supervised
learning using gaussian fields and harmonic functions,” in Machine
Learning, Proceedings of the Twentieth International Conference (ICML
2003), 2003, pp. 912–919.
[16] T. Bühler and M. Hein, “Spectral clustering based on the graph plaplacian,” in Proceedings of the 26th Annual International Conference
on Machine Learning, ser. ICML ’09. ACM, 2009, pp. 81–88.
[17] Y.-X. Wang, J. Sharpnack, A. Smola, and R. Tibshirani, “Trend
Filtering on Graphs,” in Proceedings of the Eighteenth International
Conference on Artificial Intelligence and Statistics, ser. Proceedings of
Machine Learning Research, G. Lebanon and S. V. N. Vishwanathan,Eds., vol. 38. San Diego, California, USA: PMLR, 09–12 May 2015,
pp. 1042–1050.
[18] M. Belkin, P. Niyogi, and V. Sindhwani, “Manifold regularization:
A geometric framework for learning from labeled and unlabeled
examples,” Journal of Machine Learning Research, vol. 7, pp. 2399–
2434, Dec. 2006.
[19] M. Belkin and P. Niyogi, “Laplacian eigenmaps for dimensionality
reduction and data representation,” Neural Computation, vol. 15,
no. 6, pp. 1373–1396, Jun. 2003.
[20] U. Luxburg, “A tutorial on spectral clustering,” Statistics andComputing, vol. 17, no. 4, pp. 395–416, Dec. 2007.
[21] U. Von Luxburg, A. Radl, and M. Hein, “Hitting and commutetimes in large random neighborhood graphs,” Journal of Machine
Learning Research, vol. 15, no. 1, pp. 1751–1798, Jan. 2014.
[22] R. Kyng, A. Rao, S. Sachdeva, and D. A. Spielman, “Algorithms forlipschitz learning on graphs,” in Proceedings of The 28th Conference
on Learning Theory, COLT 2015, 2015, pp. 1190–1223.
[23] J. Y. Zien, M. D. F. Schlag, and P. K. Chan, “Multilevel spectral
hypergraph partitioning with arbitrary vertex sizes,” IEEE Trans. on
CAD of Integrated Circuits and Systems, vol. 18, no. 9, pp. 1389–1399,
1999.
[24] S. Agarwal, K. Branson, and S. Belongie, “Higher order learningwith graphs,” in Proceedings of the 23rd International Conference on
Machine Learning, ser. ICML ’06. ACM, 2006, pp. 17–24.
[25] M. Hein, S. Setzer, L. Jost, and S. S. Rangapuram, “The total
variation on hypergraphs - learning on hypergraphs revisited,”in Advances in Neural Information Processing Systems 26: 27th Annual
Conference on Neural Information Processing Systems 2013., 2013, pp.
2427–2435.
[26] R. Tibshirani, “Regression shrinkage and selection via the lasso,”
Journal of the Royal Statistical Society (Series B), vol. 58, pp. 267–288,
1996.
[27] J. Friedman, T. Hastie, H. Höfling, and R. Tibshirani, “Pathwise
coordinate optimization,” Annals of Applied Statistics, vol. 1, no. 2,
pp. 302–332, 2007.
[28] M. Yuan and Y. Lin, “Model selection and estimation in regression
with grouped variables,” Journal of the Royal Statistical Society (SeriesB), vol. 68, pp. 49–67, 2006.

13[29] L. Jacob, G. Obozinski, and J.-P. Vert, “Group lasso with overlap
and graph lasso,” in Proceedings of the 26th Annual International
Conference on Machine Learning, ser. ICML ’09. ACM, 2009, pp.
433–440.
[30] Y. Zhou, R. Jin, and S. C. H. Hoi, “Exclusive lasso for multi-task
feature selection.” in AISTATS, ser. JMLR Proceedings, Y. W. Teh
and D. M. Titterington, Eds., vol. 9. JMLR.org, 2010, pp. 988–995.
[31] F. R. Chung, “The laplacian of a hypergraph,” AMS DIMACS Series
in Discrete Mathematics and Theoretical Computer Science, vol. 10, pp.
21–36, 1993.
[32] T. Hastie, R. Tibshirani, and M. Wainwright, Statistical Learning withSparsity: The Lasso and Generalizations. Chapman & Hall/CRC,
2015.
[33] A. Rinaldo, “Properties and refinements of the fused lasso,” Annalsof Statistics, vol. 37, no. 5B, pp. 2922–2952, 2009.
[34] P. Zhao and B. Yu, “On model selection consistency of lasso,” Journalof Machine Learning Research, vol. 7, pp. 2541–2563, Dec. 2006.
[35] M. J. Wainwright, “Sharp thresholds for high-dimensionaland noisy sparsity recovery using l1-constrained quadratic
programming (lasso),” IEEE Transactions on Information Theory,
vol. 55, no. 5, pp. 2183–2202, May 2009. [Online]. Available:
http://dx.doi.org/10.1109/TIT.2009.2016018[36] J. Sharpnack, A. Singh, and A. Rinaldo, “Sparsistency of theedge lasso over graphs,” in Proceedings of the Fifteenth International
Conference on Artificial Intelligence and Statistics, AISTATS 2012, La
Palma, Canary Islands, April 21-23, 2012, 2012, pp. 1028–1036.
[37] D. Zhou, J. Huang, and B. Scholkopf, “Learning with hypergraphs:
Clustering, classification, and embedding,” in NIPS, B. Scholkopf,
J. Platt, and T. Hoffman, Eds. MIT Press, 2006, pp. 1601–1608.
[38] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone,
Classification and Regression Trees. Wadsworth, 1984.
[39] M. Lichman, “UCI machine learning repository,” 2013. [Online].
Available: http://archive.ics.uci.edu/ml

Canh Hao Nguyen Canh Hao Nguyen received
his B.S. degree in Computer Science from the
University of New South Wales, Australia, M.S.
and Ph.D. degrees from JAIST, Japan. He has
been working in machine learning and bioinformatics. His current interests are machine learning
for graph data, sparse modeling with applications
in biological network analysis.

Hiroshi Mamitsuka Hiroshi Mamitsuka received
the B.S. degree in biophysics and biochemistry,
the M.E. degree in information engineering, and
the Ph.D. degree in information sciences from the
University of Tokyo, Tokyo, Japan, in 1988, 1991,
and 1999, respectively. He has been working
on research in machine learning, data mining,and bioinformatics. His current research interests
include mining from graphs and networks inbiology and chemistry.