Supplementary Notes forMulti-Task Feature Selection on Multiple Networks via Maximum Flows
Mahito Sugiyama∗

Chloé-Agathe Azencott∗Yoshinobu Kawahara‡
A

Network Transformation for Maximum FlowAlgorithms

We explain how our single-task formulation(A.1)

argmax f (S) − g(S),S⊂V

can be solved by the maximum flow algorithm. Givena network G = (V, E), let us introduce a source nodes and a sink node t and construct a transformed s/tnetwork M (G) = (V ′ , E ′ ) such that V ′ = V ∪ {s, t} andE ′ = E ∪ S ∪ T , where{}S = {s, v} | v ∈ V, q(v) > η ,{}T = {t, v} | v ∈ V, q(v) < η .

Dominik Grimm∗†

Karsten M. Borgwardt∗†
6152110s

4273 0.521254

32t
1

1.5

Figure S1: Example of a network (left) and its corresponding s/t-network (right) for the maximum flow
problem. Numbers in circles denote values q and thoseon edges denote weights (left) and capacities (right). In
this example, λ = 0.5 and η = 3.

is derived from noticing that η only aﬀects the capacities
In addition, we set the capacity c : E ′ → R+ of the on edges connected the source or the sink on the s/tedges in M (G) tonetwork M (G).
{Moreover, the following three properties hold:| q(v) − η | if u ∈ {s, t} and v ∈ V,c({v, u}) =1. The capacity c({s, v}) is a non-decreasing function
λw({v, u}) otherwise.
of −η for all v ∈ V .
Figure S1 shows a simple example of a network G and
2. The capacity c({t, v}) is a non-increasing functionits s/t-network.
of −η for all v ∈ V .
Theorem A.1. ([S1]) Let G be a network. The minimum s/t cut of the network M (G), which gives the so3. The capacity c({v, u}) is constant for all v, u ∈ V .
lution of the maximum flow problem from the source s
These properties exactly coincide with the assumptions
to the sink t, coincides with the solution of the probnecessary to the application of the parametric maximumlem (A.1) on G.
flow algorithm.
The proof is available in [S1] and can be derived
similarly as in [S2]. Thus a maximum flow algorithm C Multi-Task Lasso and Multi-Task Grace
can be directly applied to solve the problem (A.1).
Given a design matrix X ∈ RN ×|V | and K response
BConditions for the Parametric Maximum
Flow Algorithm

The anti-monotonicity of η, that is,S(η) ⊂ S(η ′ ) if and only if η > η ′ ,∗ Machine Learning and Computational Biology ResearchGroup, Max Planck Institutes Tübingen, Germany† Zentrum für Bioinformatik, Eberhard Karls UniversitätTübingen, Germany‡ The Institute of Scientific and Industrial Research (ISIR),
Osaka University, Japanvectors yk , the multi-task Lasso solves
1 ∑2(C.2) argmin||yk − Xβk ||2 + λ ||B||ℓ1 /ℓ2 ,2N|V|×K
B∈RK

k=1

where the k-th column of B is the parameter vector βkof the corresponding task and the ℓ1 /ℓ2 -norm of B isgiven byv|V | u K|V |u∑∑∑t2βk,v =||B||ℓ1 /ℓ2 =∥βv ∥2 .
v=1

k=1

v=1

Grace can be extended to multi-task learning witha single network over the features as follows. Given adesign matrix X ∈ RN ×|V | , K response vectors yk , anetwork over the |V | features described by its LaplacianL, and two parameters λ1 , λ2 ∈ R. We formulate MultiGrace for K tasks as(C.3)
argminK (2∑||yk − Xβk || + λ1 ||B||

B∈R|V |×K k=1+λ2 βk⊤ Lβk2)ℓ1 /ℓ2.

which includes 200 connected subnetworks. Moreover,for each TF, an expression level x is generated from thenormal distribution N (0, 1), and the expression levels
for its regulatory genes are generated from N (0.7x, 0.51).
Thus the correlation between a TF and its regulatory
genes is 0.7. Finally, we simulate a response vector
from the linear model ∑y = Xβ + ϵ with i.i.d. noiseϵ ∼ N (0, σ 2 ) and σ 2 = i βi2 /4.
We prepare four models with diﬀerent feature
weights β and use their combination in the multi-task
setting. In model 1,Following the reasoning from Lemma 1 of [S3], thisis equivalent to the following multi-task Lasso problem:
K (∑argmin
B ∗ ∈R|V |×K)||yk∗ − X ∗ βk∗ ||2 + γ ||B ∗ ||ℓ1 /ℓ2 ,2k=1(
β=55−5−55, √ , . . . , √ , −5, √ , . . . , √ ,10101010)
3
3−3−33, √ , . . . , √ , −3, √ , . . . , √ , 0, . . . , 0 .
10101010√
where γ = λ1 / 1 + λ2 and for each task, (yk∗ , X ∗ ) is an
artificial dataset defined byThus the first four TFs and their regulatory genes, that(())
is to say 44 features in total, are causal to the response.
yk∗−1/2 √ X∗X = (1 + λ2 ),, yk =Note that there is no edge between causal and non0|V|
λ2 S ⊤causal features. Model 2 diﬀers from model 1 in that thewhere S is such that SS ⊤ = L. If (β̂k∗ )k=1,...,K is signs of the first three target genes in each subnetwork
opposites, that is, For√example,
the solution to this multi-task Lasso problem, √then the are flipped to their√∗β,β,β=−5/10andβ5 , β6 , . . . , β11 = 5/ 10. Thissolution to Equation C.3 is given by β̂k = β̂k / 1 + λ2 . 2 3 4modelsanegatively
correlated
network. Model 3 (resp.
Li and Li [S3] proposed to use a singular value
model4)
isidenticaltomodel1(resp. model 2), except
decomposition to obtain S, but the Lemma also holds
√
that
all
10in
β
arereplacedwith
10. Therefore theif S is replaced by the incidence matrix of the network.
connection
between
TF
andgenesinmodels 3 and 4 is
As it can be constructed in linear time in the numberweaker
thaninmodels1and2.
of vertices and edges, this makes for a much faster
implementation of Grace, aGrace and Multi-Grace. We
used this implementation in our experiments.
If the diﬀerent tasks have diﬀerent networks, thisderivation does not apply and solving a multi-task References
version of Grace is not straightforward any more.
D

Generation of Synthetic Data

There are 2, 200 features in total composed of 200
transcription factors (TFs) and 2, 000 genes. Each TF [S1] Azencott, C.A., Grimm, D., Sugiyama, M., Kawahara,
is connected to 10 regulatory target genes. That is, weY., Borgwardt, K.M.: Eﬃcient network-guided multihave a network G = (V, E) such that
locus association mapping with graph cuts. BioinforV =200∪{ti } ∪ Gi with |Gi | = 10, and

i=1

E=200
∪
i=1

Ei with Ei = {{ti , v} | v ∈ Gi },matics 29(13), i171–i179 (2013)[S2] Greig, D.M., Porteous, B.T., Seheult, A.H.: Exactmaximum a posteriori estimation for binary images.
Journal of the Royal Statistical Society: Series B 51(2),271–279 (1989)[S3] Li, C., Li, H.: Network-constrained regularizationand variable selection for analysis of genomic data.