April 24–26, 2014
SIAM SDM14

MLCB

Multi-Task Feature Selection
on Multiple Networks
via Maximum Flows
Mahito Sugiyama1 (,2) , Chloé-Agathe Azencott3 , Dominik
Grimm2,4 , Yoshinobu Kawahara1 , Karsten Borgwardt2,41 Osaka University, 2 Max Planck Institutes Tübingen, 3 Mines ParisTech,Institut Curie, INSERM, 4 Eberhard Karls Universität Tübingen

1/23

Goal
• Given multiple networks• Find features (vertices), which are associated withthe target response and tend to be connected each other

2/23

Main Result• New formulation of multi-task feature selectionargmaxtasks)

associationpenalty),|,sparsityconnectivity)|• It is eﬃciently solved by max-flow algorithms• Its performance is superior to Lasso-based methods
3/23Motivation: Data Mining on Networks• Networks (graphs) are everywhere– Biological pathways (KEGG), chemical compounds(PubChem), social networks, …

• Which part of the network is responsible for performing aparticular function?
→ Feature selection on networks– Features vertices (nodes)– Network topology a priori knowledge about relationships
between features• Multi-task feature selection should be considered
for more eﬀectiveness
4/23

Existing Approach: Lasso• Lasso-based regression with:– ℓ -regularizer– Structured (network) regularizers• Drawbacks– Prediction loss is optimized, diﬀerent from finding featuresthat are relevant for (associated with) a property of interest• Drawbacks in multi-task setting– Exactly the same features are always selectedamong diﬀerent tasks– Only one network structure can be employed∘ No method can use multiple networks simultaneously
5/23

SConES (Selecting Connected Explanatory SNPs)• Single task feature selection on a network[Azencott et al. ISMB2013]• Given a weighted graph 𝐺 = (𝑉, 𝐸)– Each ∈ has a relevance score ( )– If you have a design matrix 𝐗 ∈ ℝ ×| | and a response vector𝐲 ∈ ℝ , ( ) is the association of 𝐲 and each feature of 𝐗

• Objective: Find a subset 𝑆 ⊂ 𝑉 which maximizes𝑓(𝑆) ∶=𝑞(𝑣) (additive score), while∈– 𝑆 is small– Vertices in 𝑆 are connected each other
6/23

Formulation of SConES• argmax ⊂ 𝑓(𝑆) − 𝑔(𝑆)𝑓(𝑆) ∶=𝑞(𝑣),𝑔(𝑆) ∶= 𝜆∑ ∈ 𝑤(𝑒) + 𝜂|𝑆|∈––connectivity

sparsity{ { , } ∈ ∣ ∈ ⧵ , ∈ } (boundary)∶ → ℝ is a weighting functionSB

7/23

Solution of SConES via Maximum Flow
• The 𝑠/𝑡-network 𝑀(𝐺) = (𝑉 ∪ {𝑠, 𝑡}, 𝐸 ∪ 𝑆 ∪ 𝑇) with{ , }∣ ∈ , ( ),{ , }∣ ∈ , ( )and set the capacity 𝑐 ∶ 𝐸 → ℝ to| 𝑞(𝑢) − 𝜂 | if 𝑢 ∈ {𝑠, 𝑡} and 𝑣 ∈ 𝑉,𝑐({𝑣, 𝑢}) = 𝜆𝑤({𝑣, 𝑢}) otherwise• The minimum 𝑠/𝑡 cut of 𝑀(𝐺) = the solution of SConES
6152110

λ = 0.5, η = 34273s

3 0.5
245Minimum
1 s/t cut
22t1

1.5

8/23

Key Contribution: Multi-SConES• Given 𝐾 networks 𝒢 = {𝐺 , 𝐺 , … , 𝐺 }– They share vertices and have diﬀerent edges• Multi-task version of SConES:
argmaxtasks)

associationpenalty),|,

sparsityconnectivity)|

9/23

Solution of Multi-SConES• Multi-SConES is solved by the max-flow algorithm
on the unified single network

10/23

Solution of Multi-SConES• Multi-SConES is solved by the max-flow algorithm
on the unified single networkMultiplenetworks

s/t-networks
Minimum
cut

Unified single networks

st

11/23

From Multi-Task to Single-Task
̃ from 𝐾 networks:• The unified network 𝑈(𝒢) = (𝑉,̃ 𝐸)
𝑉̃ ∶= ⋃ 𝑉 , 𝐸̃ ∶= ⋃ 𝐸 ∪ ⋃𝐴 , where𝐴∶= {𝑣 , 𝑣 } 𝑖, 𝑗 ∈ {1, … , 𝐾}, 𝑖 ≠ 𝑗 .

– The weight 𝑤̃ of edges is given as 𝑤(𝑒)̃
= 𝑤 (𝑒) if 𝑒 ∈ 𝐸and 𝑤(𝑒)̃= 𝜇/𝜆 otherwise– 𝑈(𝒢) has |𝑉|̃ = 𝐾𝑛 vertices,|𝐸|̃ = ∑ |𝐸 | + 𝑛𝐾(𝐾 − 1)/2 edges• Our multi-task problem is exactly equivalent tothe single-task over 𝑈(𝒢)12/23

Empirical Comparison• Correlation ranking (baseline)• Single-task:– Lasso, Elastic net– Group Lasso (with groups formed by edges)– Grace, aGrace (Lasso-based state-of-the-art)
argmin ‖𝐲 − 𝐗𝛽‖ + 𝜆 ‖𝛽 ‖ + 𝜆 𝛽 𝐋𝛽sparsity

connectivity∘ Accelerated by replacing SVD to the incidence matrix• Multi-task:– Multi-task Lasso, Multi-task Grace• Performance is measured by
MCC (Matthews correlation coeﬃcient) and MSE
13/23

Synthetic Data
• Gene regulatory networks are simulated– 2,200 features (vertices)∘ 200 transcription factors (TFs) and 2,000 genes∘ Each TF is connected to 10 regulatory target genes– First 44 features (4 TFs and 40 genes) are causal to the response∘ They are correlated with the response– 4 models∘ Models 1, 3 (2, 4) are positively (negatively) correlated∘ Correlation in models 3, 4 is weaker than 1, 2
– The same data was used in [Li and Li; 2008]

14/23

Running Time

Running time (s)100.0010.00
1.00
LassoGraceSConES

0.10
0.01
1251020Number of tasks

50100

15/23

Parameter Sensitivity (1/2)
Sparsity

Connectivity

400

400

400300

300

300

MSE

200

1000200

1000.15 0.20 0.25 0.30

η00.01

0.9
0.8
0.7
0.6
0.5
0.4
0.3MSE

MCC
MSE

200

GoodMCC

Bad

MCC

Bad

0.9
0.8
0.7
0.6
0.5
0.4
0.3

Good

0.9
0.8
0.7
0.6
0.5
0.4
0.3

Difference between tasks

100
1.00

λ

100

00.01 0.10 1.00 10.00

μsharing all features

16/23

Parameter Sensitivity (2/2)

400

400

400

300

300

300

200

100

0.9
0.8
0.7
0.6
0.50.40.3MSEMSE

MCC
MSE

200

Good

0.90.80.7
0.6
0.5
0.40.3

MCCBadMCC

Bad

0.90.80.70.6
0.50.40.3

Good20010010000.01 0.10 1.00 10.00

00.01 0.10 1.00 10.00

00.01 0.10 1.00 10.00

sharing 3/4 features

sharing 1/2 features

sharing no feature

μμμ

17/23

Performance for Synthetic Data (model 1)
Good

1.0

MCC

0.8
0.6
0.4
0.20BadCR LA EN GL GR AG SC

CR LA GR SC

CR LA GR SC

CR LA GR SC

Single task

Two tasks

Three tasks

Four tasks

CR LA EN GL GR AG SC

CR LA GR SC

CR LA GR SC

CR LA GR SC

Single task

Two tasks

Three tasks

Four tasks

400BadMSE

300200100
Good0

CR: ranking of correlations (baseline), LA: Lasso, EN: the elastic net, GL: group Lasso,
GR: Grace, AG: aGrace, and SC: SConES

18/23

Performance for Two Tasks (model 1)
1.0Good

MCC

0.8
0.6
0.4
0.20BadCR LA GR SC

CR LA GR SC

CR LA GR SC

sharing 3/4 features sharing 1/2 features sharing no feature
500BadMSE

400300200100
Good0

CR LA GR SC

CR LA GR SC

CR LA GR SC

sharing 3/4 features sharing 1/2 features sharing no feature
CR: ranking of correlations (baseline), LA: Lasso, GR: Grace, SC: SConES

19/23

Multi-Locus Association Mapping• Goal: Find SNPs (features) that are associated withphenotype, using a network over SNPs
• Arabidopsis thaliana GWAS data
– 216,130 SNPs (features)– 6 flowering time phenotypes (1 phetnotype 1 task)– Protein-protein interaction network from TAIR∘ SNPs are connected if they belong to the connected genes• 282 candidate genes are gold standard of causal features
Region of candidate causal geneSNPs A T T A G G C C...
Hit region (20kb)
20/23

Results of Association Mapping (MCC)
Phenotype
Lasso

MCC
Grace

SConES

2W
2W + 4W
2W + FT GH
2W + 4W + FT GH

0.001−0.001
0.001
0.005−0.001−0.003
0.000
0.002

𝟎.𝟎𝟏𝟒
𝟎.𝟎𝟏𝟔
𝟎.𝟎𝟐𝟒
𝟎.𝟎𝟐𝟕

LDV
LDV + 0W
LDV + FT10
LDV + 0W + FT10

0.001
0.005
0.001
0.003

0.000
0.007
0.001
0.002

𝟎.𝟎𝟏𝟔
𝟎.𝟎𝟐𝟎
𝟎.𝟎𝟐𝟏
𝟎.𝟎𝟐𝟑
21/23

Results of Association Mapping (SNPs)
Phenotype

Hit ratio of SNPs (prec.)
Lasso
Grace
SConES

2W
2W + 4W
2W + FT GH
2W + 4W + FT GH

7/126
7/175
9/173
15/183

4/98
6/198
7/146
16/265𝟒𝟐/𝟑𝟑𝟖𝟖𝟏/𝟖𝟎𝟐
𝟏𝟎𝟔/𝟖𝟏𝟖
𝟏𝟎𝟏/𝟔𝟕𝟗LDV
LDV + 0W
LDV + FT10
LDV + 0W + FT10

6/116
16/196
12/214
18/283

7/144
19/206
10/191
19/323𝟕𝟑/𝟔𝟔𝟕𝟖𝟔/𝟕𝟎𝟐
𝟗𝟐/𝟕𝟔𝟐
𝟖𝟏/𝟒𝟖𝟐
22/23

Conclusion• A new formulation, Multi-SConES, for multi-task
feature selection with multiple network regularizers– Direct optimization of feature relevance scores– Exact solution via max-flow algorithms• It can select diﬀerent features for diﬀerent tasks• It can use diﬀerent networks for diﬀerent tasks• Future work
– Incorporating more complex task relationships∘ Currently, a single parameter 𝜇23/23

Appendix

A-1/A-11

Diﬃculty of Optimization• Given a positive integer 𝑘• The maximum-weight connected graph (MCG) problem:
argmax 𝑓(𝑆) s.t. 𝐺| is connected and |𝑆| = 𝑘⊂

is known to be strongly NP-complete

A-2/A-11

Regularization Path• 𝜂 has anti-monotonicity with respect to the number of selected features– 𝑆(𝜂) ⊂ 𝑆(𝜂 ) if and only if 𝜂 > 𝜂• The entire regularization path along with the changes in𝜂 can be obtained– Time complexity does not increase by using parametricmaximum flow algorithm [Gallo et al. 1989]

A-3/A-11

Spectral Analysis• 𝐟 ∈ {0, 1}| | : the indicator vector of a subset 𝑆 ⊂ 𝑉• 𝐜 ∈ ℝ| | : the vector composed of values 𝑞(𝑣)• Single-task SConES:
argmax 𝐜 𝐟 − 𝜆𝐟 𝐋𝐟 − 𝜂‖𝐟‖𝐟∈{ , }| |• Multi-task SConES:
argmax ∑𝐜 𝐟 −𝜆𝐟 𝐋 𝐟 −𝜂‖𝐟 ‖−∑𝜇‖𝐟 −𝐟 ‖ ,𝐟 ,…,𝐟

• On the unified network, multi-task SConES is written as:̃ .
argmax 𝐜̃ 𝐟̃ − 𝜆𝐟̃ 𝐋̃ 𝐟̃ − 𝜂‖𝐟‖
̃𝐟∈{, } | |

A-4/A-11

Performance for Synthetic Data (model 2)
Good1.0MCC

0.80.60.40.20Bad

CR LA EN GL GR AG SC

CR LA GR SC

CR LA GR SC

CR LA GR SC

Single task

Two tasks

Three tasks

Four tasks

CR LA EN GL GR AG SC

CR LA GR SC

CR LA GR SC

CR LA GR SC

Single task

Two tasks

Three tasks

Four tasks

200BadMSE

150
10050
Good0

CR: ranking of correlations (baseline), LA: Lasso, EN: the elastic net, GL: group Lasso,
GR: Grace, AG: aGrace, and SC: SConES

A-5/A-11

Performance for Synthetic Data (model 3)
Good1.0MCC

0.80.60.40.20BadMSEBadGood140120100806040200CR LA EN GL GR AG SC

CR LA GR SC

CR LA GR SC

CR LA GR SC

Single task

Two tasks

Three tasks

Four tasks

CR LA EN GL GR AG SC

CR LA GR SC

CR LA GR SC

CR LA GR SC

Single task

Two tasks

Three tasks

Four tasks

CR: ranking of correlations (baseline), LA: Lasso, EN: the elastic net, GL: group Lasso,
GR: Grace, AG: aGrace, and SC: SConES

A-6/A-11

Performance for Synthetic Data (model 4)
Good1.0

MCC

0.8
0.6
0.4
0.20BadCR LA EN GL GR AG SC

CR LA GR SC

CR LA GR SC

CR LA GR SC

Single task

Two tasks

Three tasks

Four tasks

CR LA EN GL GR AG SC

CR LA GR SC

CR LA GR SC

CR LA GR SC

Single task

Two tasks

Three tasks

Four tasks

100Bad

MSE

80
60
4020
Good

0

CR: ranking of correlations (baseline), LA: Lasso, EN: the elastic net, GL: group Lasso,
GR: Grace, AG: aGrace, and SC: SConES

A-7/A-11

Performance for Two Tasks (model 2)
1.0GoodMCC

0.80.6
0.40.20Bad

CR LA GR SC

CR LA GR SC

CR LA GR SC

sharing 3/4 features sharing 1/2 features sharing no feature
200BadMSE

15010050Good0CR LA GR SC

CR LA GR SC

CR LA GR SC

sharing 3/4 features sharing 1/2 features sharing no feature
CR: ranking of correlations (baseline), LA: Lasso, GR: Grace, SC: SConES

A-8/A-11

Performance for Two Tasks (model 3)
1.0

Good

MCC

0.8
0.6
0.4
0.20BadCR LA GR SC

CR LA GR SC

CR LA GR SC

sharing 3/4 features sharing 1/2 features sharing no featureMSEBadGood140120
100806040200

CR LA GR SC

CR LA GR SC

CR LA GR SC

sharing 3/4 features sharing 1/2 features sharing no feature
CR: ranking of correlations (baseline), LA: Lasso, GR: Grace, SC: SConES

A-9/A-11

Performance for Two Tasks (model 4)
1.0

GoodMCC

0.8
0.6
0.4
0.20BadCR LA GR SC

CR LA GR SC

CR LA GR SC

sharing 3/4 features sharing 1/2 features sharing no feature
100BadMSE

80604020Good0CR LA GR SC

CR LA GR SC

CR LA GR SC

sharing 3/4 features sharing 1/2 features sharing no feature
CR: ranking of correlations (baseline), LA: Lasso, GR: Grace, SC: SConES

A-10/A-11

Results of Association Mapping (genes)
Phenotype

Hit ratio of genes (prec.)Lasso Grace SConES

2W
2W + 4W
2W + FT GH
2W + 4W + FT GH

2/112
2/163
9/162
6/174

1/91
2/191
7/135
3/256

𝟕/𝟏𝟐𝟒
𝟏𝟏/𝟐𝟒𝟎𝟏𝟑/𝟐𝟓𝟎𝟏𝟑/𝟐𝟎𝟖LDV
LDV + 0W
LDV + FT10
LDV + 0W + FT10

2/107
2/183
1/199
2/265

2/131
2/187
1/181
1/307

𝟗/𝟐𝟎𝟐
𝟏𝟎/𝟐𝟎𝟗𝟏𝟎/𝟐𝟐𝟏
𝟏𝟎/𝟏𝟓𝟑
A-11/A-11