arXiv:1505.06607v2
[] 26
May 2015
arXiv:
some other
text
goes here

Stochastic Block Coordinate Frank-Wolfe Algorithm for
Large-Scale Biological Network Alignment
1

Yijie Wang1 and Xiaoning Qian1
Department of Electrical & Computer Engineering, Texas A&M University,
College Station, Texas, USA, 77843
(Dated: May 23, 2015)
Abstract

With increasingly “big” data available in biomedical research, deriving accurate and reproducible
biology knowledge from such big data imposes enormous computational challenges. In this paper, motivated by recently developed stochastic block coordinate algorithms, we propose a highly scalable randomized block coordinate Frank-Wolfe algorithm for convex optimization with general compact convex
constraints, which has diverse applications in analyzing biomedical data for better understanding cellular
and disease mechanisms. We focus on implementing the derived stochastic block coordinate algorithm
to align protein-protein interaction networks for identifying conserved functional pathways based on the
IsoRank framework. Our derived stochastic block coordinate Frank-Wolfe (SBCFW) algorithm has the
convergence guarantee and naturally leads to the decreased computational cost (time and space) for
each iteration. Our experiments for querying conserved functional protein complexes in yeast networks
confirm the effectiveness of this technique for analyzing large-scale biological networks.

1

Introduction

First-order methods in convex optimization have attracted significant attention in statistical learning in recent years. They are appealing to many learning problems, such as LASSO regression and matrix completion,
which have diverse applications in analyzing large-scale biological systems and high-dimensional biomedical
measurement profiles [13, 7]. These first-order optimization methods scale well with the current “big” data in
many biomedical applications due to their advantages that they have low computation burden per iteration
and they are easy to be implemented on parallel computational resources.
In this paper, we focus on the Frank-Wolfe algorithm, which is also known as the conditional gradient
method. One of its advantages is that at each iteration step it decomposes the complex constrained optimization problem into sub-problems which are easier to solve. Additionally, it is a projection free algorithm,
which avoids solving the projection problem for constrained optimization as done in many other algorithms.
The original Frank-Wolfe algorithm, developed for smooth convex optimization on a polytope, dates back
to Frank and Wolfe [4]. Dunn and Harshbarger [2, 3] have generalized the algorithm to solve the optimization for more general smooth convex objective functions over bounded convex feasible regions. Recently,
researchers [9] have proposed stochastic optimization ideas to scale up the original Frank-Wolfe algorithm.
Based on these previous seminal efforts, our main contribution in this paper is that we generalize the
stochastic block coordinate Frank-Wolfe algorithm proposed in [9], previously with block separable constraints, to solve more general optimization problems with any convex compact constraints, including the
problems with block inseparable constraints. Such a generalized algorithm has a broader range of biomedical
applications, including biological network alignment. We prove the convergence of our generalized stochastic block coordinate Frank-Wolfe algorithm and evaluate the algorithm performance for querying conserved
functional protein complexes in real-world protein-protein interaction (PPI) networks.
In the following sections, we first describe the model formulation of the optimization problems that
we are generally interested. Specifically, to address potential difficulty from more general convex compact
constraints, we derive a new stochastic block coordinate Frank-Wolfe algorithm and provide the convergence
proof. Then, we formulate the IsoRank problem for network alignment [11] as a convex programming
problem and develop a SBCFW-IsoRank algorithm based on our new stochastic block coordinate FrankWolfe algorithm. At last, in our experiments, we show the efficiency and effectiveness of our algorithm for
solving the PPI network query problem.

1

arXiv: some other text goes here

2

Stochastic Block Coordinate Descent Frank-Wolfe Algorithm

Consider the minimization problem:
min: f (x)

(1)

s.t. x ∈ D,

where the objective function f (x) is convex and differentiable on RN , and the domain D is a compact convex
subset of any vector space. We assume that the optimal solution x∗ to the above problem is non-empty and
bounded without loss of generality.
Assume that we can decompose the solution space RN into n equal-size subspaces:
n

RN = ⊕ RNi , N =
i=1

n
X

Ni ,

(2)

i=1

where N1 = . . . = Ni = . . . , Nn and RNi denotes the ith equal-size subspace along the corresponding coordinates. This decomposition enables scalable stochastic optimization algorithms.
Based on this decomposition,
Pn
we introduce matrices Ui , who sum up to an identity matrix IN = i=1 Ui , and Ui is a N × N matrix with
Ui (t, t) = 1, t ∈ RNi on its diagonal and the other entries being equal to zero. In typical stochastic optimization algorithms [12], instead of computing the gradient ∇f (x) at each iteration, the partial gradient of f (x)
on a randomly selected subspace RNi is used:
∇i f (x) = Ui ∇f (x).

(3)

Now we generalize the previous stochastic block coordinate Frank-Wolfe algorithm derived in [9] to solve
more general optimization problems with any compact convex constraints D. The new generalized stochastic
block coordinate Frank-Wolfe (SBCFW) algorithm is illustrated in Algorithm 1. In the pseudo code, the
operation i = Ck randomly selects one of the n equal-size subspaces to update the partial gradient at each
iteration with the same probability. In addition, Uj × s = Uj × xk denotes the condition that the elements
of the jth block of s equal to the elements of the jth block of xk .
Algorithm1: Generalized SBCFW Algorithm
1 Let x0 ∈ D, k = 0.
2 While Stopping criteria not satisfied do
3

n

Randomly divide RN into n blocks RN = ⊕ RNi ;
i=1

4
5
6

Choose i = Ck ;
Find ski such that
ski := arg
min

7
8

Determine the step size γ
γ := arg min f ((1 − γ)xk + γski );

∇i f (xk )T (s − xk );

Uj ×s=Uj ×xk ,∀j6=i;
s∈D

γ ∈[0,1]

9 Update xk+1 := (1 − γ)xk + γski ;
10 k = k + 1;
11 Endwhile

Note that our generalized SBCFW algorithm is similar to the algorithm in [9], which aims to solve optimization problems with block separable constraints and has the sub-linear convergence property. However,
our algorithm provides a more generalized framework, which can manipulate any convex and compact constraints no matter whether they are block separable or not. Because the setup of our algorithm is more
general without any specific structure, it is difficult to obtain theorectical convergence rate guarantees. In
this paper, we only provide the proof that our SBCFW converges to the global optimum. The convergence
guarantee of the generalized SBCFW algorithm is provided by Theorem 1 below, which is based on Lemma
1:

2

arXiv: some other text goes here

Lemma 1:

At each iteration of the SBCFW algorithm, the following inequality holds

∇f (xk )T Ei [ski ] − xk ≤ 0,

(4)

where Ei [ski ] is the expectation of ski with respect to the random selection of the ith cordinate block to the
corresponding subspace.
Proof. Assuming at the kth iteration, we solve the following optimization problem:
min: Zki (s) := ∇i f (xk )T (s − xk )
s.t. Uj × s = Uj × xk , ∀j 6= i,

(5)

s ∈ D.
The solution to (5) is ski . With ski achieving the minimum of (5), we have
Zki (ski ) ≤ Zki (xk ) = ∇i f (xk )T (xk − xk ) = 0.

(6)

Zki (ski ) = ∇i f (xk )T (ski − xk ) ≤ 0.

(7)

Therefore,
Taking expectation on both sides of the above inequality with respect to random blocks, we obtain


Ei ∇i f (xk )T (ski − xk )
≤0
1X
∇i f (xk )T (ski − xk ) ≤ 0
⇒
n i
!T
!
X
1 X k
k
k
⇒
∇i f (x )
(si − x )
≤0
n
i
i
!T
!
X
1X k
k
k
⇒
∇i f (x )
s −x
≤0
n i i
i

⇒
∇f (xk )T Ei [ski ] − xk
≤ 0.

(8)

The inequality in the third line can be derived based on the fact that ski − xk is a vector with only its ith
coordinate block having non-zero values and the other parts being all
Pzeros. With that,
P the summation in
the second line can be written as the inner product between vectors i ∇i f (xk ) and i (ski − xk ).
We now analyze the convergence of the new SBCFW algorithm based on Lemma 1 from two cases. The
first case is when

∇f (xk )T Ei [ski ] − xk = 0.
(9)
This simply means that xk is a stationary point. Because the original objective function f (x) is convex, we
can conclude that xk is the global minimum. Another case is when

∇f (xk )T Ei [ski ] − xk < 0,
(10)
indicating that Ei [ski ] − xk is a decent direction based on the definition [10]. Hence, Ei [ski ] − xk can move
along the direction to get closer to the global minimum in expectation. Furthermore, we compute the optimal
step size at each iteration, therefore the objective function values are guaranteed to be non-increasing. With
that, we present Theorem 1 as follows:
Theorem 1:
The sequence f (x1 ), f (x2 ), ..., f (xk ), ... generated by the SBCFW algorithm is nonincreasing
f (x1 ) ≥ f (x2 ) ≥ ... ≥ f (xk ) ≥ f (xk+1 ), k → ∞.
(11)

3

arXiv: some other text goes here

3
3.1

Biological Network Alignment
Optimization Model Formulation

In this section, we re-formulate the involved optimization problem for the network alignment algorithm—
IsoRank [11] to address the potential computational challenges of aligning multiple large-scale networks. The
new formulation has the same mathematical programming structure as the problem (1).
Let Ga and Gb be two biological networks to align. Two networks has Na and Nb vertices respectively.
We define B ∈ R(Na ×Nb )×(Na ×Nb ) as the Cartesian product network from Ga and Gb : B = Ga ⊗ Gb . Denote
the all one vector 1 ∈ RNa ×Nb and
B̄ = B × Diag(B1)−1 ,
(12)
where Diag(B1) can be considered as a degree matrix with B1 on its diagonal and all the other entries equal
to zero. B̄ contains the transition probabilities for the underlying Markov random walk in IsoRank [11]. It
is well known that if Ga and Gb are connected networks and neither of them is bipartite graph, then the
corresponding Markov chain represented by B̄ is irreducible and ergodic, and there exists a unique stationary
distribution for the underlying state transition probability matrix B̄. The goal of the IsoRank algorithm
is to find a right maximal eigenvector of the matrix B̄: B̄x = x and 1T x = 1, x ≥ 0, which corresponds
to the best correspondence relationships between vertices across two networks. When two networks are
of reasonable size, spectral methods as well as power methods can be implemented to solve the IsoRank
problem [11]. However, with large-scale networks, the transition probability matrix B̄ can be extremely
large (quadratic with Na × Nb ) and spectral methods can be computationally prohibitive. In this paper, we
re-formulate this problem of searching for maximal right eigenvector as a constrained optimization problem:
1
B̄x − x
2
s.t. 1T x = 1, x ≥ 0.

min: f (x) :=

2

(13)
(H)

1
After expanding the objective function, we obtain f (x) = xT M x, where M = B̄ T B̄ − B̄ − B̄ T +I. Therefore
2
the equivalent optimization problem is
1 T
x Mx
2
s.t. 1T x = 1, x ≥ 0.

min: f (x) :=

(14)
(H)

The gradient of f (x) can be easily computed ∇f (x) = M x. Furthermore, we find that the Hessian matrix
of f (x) is M , which is a positive semi-definite matrix proven by Lemma 2 :
Lemma 2 : M = B̄ T B̄ − B̄ − B̄ T + I is positive semi-definite.
Proof. M can be written as M = (B̄ − I)T (B̄ − I), which proves the lemma.
With Lemma 2, it is obvious that the objective function f (x) is convex. Also, the constraint set
H = {x|xT 1 = 1, x ≥ 0} is a unit simplex, which is convex and compact. Hence, the IsoRank problem (13) has
the same problem structure as (1) and our generalized SBCFW algorithm can be used to solve (14) with much
better scalability and efficiency due to the efficiency of the randomized partial gradient computation at each
iteration. Similarly as in [11], in addition to network topology, we can incorporate other information in the
formulation for more biologically significant alignment results by replacing B̄ with B̂ = αB̄ +(1−α)S̄1T , α ∈
[0, 1]. Here S̄ = S/|S| is a normalized similarity vector with size Na × Nb , cancatenated from the doubly
indexed similarity estimates S([u, v]) based on the sequence or function similarity between vertices u in Ga
and v in Gb .

3.2

SBCWF-IsoRank Algorithm

As shown in Section 3.1, f (x) in (13) is convex and the constraint set H in (14) is a convex compact set.
Therefore, we can apply the generalized SBCWF algorithm proposed in Section 2 to solve the corresponding
optimization problem (14). The detailed algorithm is illustrated in Algorithm 2. Here we want to emphasize
4

arXiv: some other text goes here

that, in
 each
iteration of our SBCFW-IsoRank algorithm, both the time complexity and the space complexity
N2
, which is achieved through tracking the vectors of pk = Exk and qk = Eski at step 2 and 10
are O
n
of each iteration in Algorithm 2, respectively. The stopping criterion is B̄x − x ≤ ξ kxk, which can be
efficiently estimated by
B̄x − x = xT M x = (Ex)T Ex = pTk pk ,
(15)
which is taken in line 11 in the SBCFW-IsoRank algorithm.
Algorithm 2: SBCFW-IsoRank Algorithm
Input: ξ, n and E
1 for k = 0, ..., ∞ do
2 randomly divide RN into n equal-size parts
3 choose i = Ck
4 if (k == 0)
n
5
initialize the ith block of x0 with
N
6 endif
7 compute pk = Exk and ∇i f (xk ) = [E T ]i pk
8 solve the sub-problem:
9
ski := arg
min
∇i f (xk )T (s − xk )
10
11
12
13
14

Uj ×s=Uj ×xk , ∀j6=i;
s∈H,
qk = Eski

compute
if pTk pk < ξ kxk
break;
endif
∗
compute the
 step size γk :
pTk pk − pTk qk

min
{γ̂,
1}
γ̂
>
0,
γ̂
=
15
γk∗ =
pTk pk − 2pTk qk + qTk qk

0
o.w.
16 xk+1 = xk + γ k (ski − xk )
17 endfor
Output: xk

3.3

Initialization
2

In order to guarantee both the time and space complexity to be O( Nn ) at each iteration, we can not initialize
the algorithm with randomly generated x0 to avoid a multiplication of a matrix of size N × N and a vector
of size N , whose time and space complexity would be O(N 2 ). We propose to initialize x0 in the following
way: First, randomly divide RN into n parts with equal sizes and randomly pick the ith part. Then,
n
we initialize every elements in the ith part with N
, which makes x0 in the feasible space defined by the
constraint set H. Using the above initialization strategy, the time and space complexity for computating
2
∇i f (x0 ), p0 = Ex0 and q0 = Es0 are all under O( Nn ), which is easy to verify.

3.4

Algorithm to Solve the Sub-problem

As shown in the SBCFW-IsoRank algorithm, at each iteration we need to solve a sub-problem. Fortunately,
the sub-problem can be solved in a straightforward manner for the optimization problem (14). For the
following sub-problem at iteration k:
min: ∇i f (xk )T (s − xk )
s.t. s ∈ H,

(16)
k

Uj × s = Uj × x , ∀j 6= i,
5

arXiv: some other text goes here

the optimalP
solution is s∗ = xk − Ui xk + Lej , where ej is an all-zero vector except that the jth element is
1 and L = l∈RNi xk (l). Here, j is the index of the coordinate with the smallest value in the ith block of
∇i f (xk ):
j = arg min: [∇i f (xk )](l).
(17)
l∈RNi

3.5

Optimal Step Size

To obtain the optimal step size at each iteration, we need to solve the following optimization problem:
T

min: xk + γ(sk − xk ) M xk + γ(sk − xk )
s.t. 0 ≤ γ ≤ 1,

(18)

pTk pk − pTk qk
> 0, which is the
pTk pk − 2pTk qk + qTk qk
solution to (18) without any constraints, the optimal solution γ ∗ is the minimum value between 1 and γ̂,
otherwise γ ∗ = 0. The definition of pk and qk are given in lines 7 and 10 in Algorithm 2.

which is the classic quadratic form with respect to γ. If γ̂ =

3.6

Time and Space Complexity

At each iteration, the most computationally expensive operations are the updates of pk and qk (lines 7 and
10 of SBCFW-IsoRank) and the calculation of the partial gradient ∇i f (xk ) (line 7 of SBCFW-IsoRank).
The calculation of pk and qk are similar. From line 10 of Algorithm 2, we know
pk = Exk

= E xk−1 + γ k−1 (sk−1 − xk−1 )
= pk−1 + γ

k−1

k−1

E(s

−x

k−1

(19)

).

The second equation is derived by replacing xk with the equation in line 16 of our SBCFW-IsoRank algorithm.
Because we keep tracking pk at each iteration,
 we
do not need to recompute pk−1 . Therefore, we only need
N2
k−1
k−1
to compute E(s
−x
), which takes O
operations because (sk−1 − xk−1 ) is a vector, with only
n
itsith block
 being non-zeros and all the other parts are zeros. Additionally, the memory consumption is also
N2
O
by the similar argument. Similarly, we can compute qk
n
qk = Esk

= E xk + (Lej − Ui xk )

(20)

= pk + E(Lej − Ui xk ),
where (Lej −Ui xk )is alsoa vector with only the ith block
 having
 non-zero values. Therefore, the computation
N2
N2
operations and consumes O
memory.
of qk also takes O
n
n
The equation of calculating ∇i f (xk ) is as follows:
∇i f (xk ) = [E T ]i pk ,

(21)

where the operator [·]i is to get the rows of the matrix corresponding to the ith coordinate block.
it
 2 Hence,

N
k
is easy to verify that the time complexity and space complexity of computing ∇i f (x ) are O
.
n
In summary, based on the above
both the time complexity and space complexity of our SBCFW analyses,

N2
IsoRank at each iteration are O
.
n

6

arXiv: some other text goes here

YGR047C

YGR047C

YOR110W

YOR110W

YDR362C

YDR362C

YPL007C

YPL007C

YBR123C

YBR123C

YAL001C

YAL001C

(b) Sub-Network in Collins

(a) Sub-Network in Krogan

Figure 1: Query subnetwork and its aligned result in the target network: (a) the query subnetwork in the
Krogan’s yeast PPI network; (b) the aligned result in Collins yeast PPI network.

4

Experiments

In this section, we apply our SBCFW-IsoRank algorithm to two network query problems. For the first set of
experiments, we take a known protein complex in an archived yeast protein-protein interaciton (PPI) network
in one database [8] as the query to search for the subnetwork in another yeast PPI network [5] with different
archived interactions. We call this yeast-yeast network query problem. The goal of this set of experiments
is to check the correctness of our algorithm as we have the ground truth for the target subnetwork. With
that, we aim to test the convergence property of our algorithm under different partitions and the relationship
between the number of iterations and number of partitions. The second experiment is to query a large-scale
yeast PPI network in IntAct [6] to find similar subnetworks of proteins with similar cellular functionalities
for a known protein complex in human PPI network. The aim of this experiment is to show that our new
algorithm can help transfer biology knowledge from model organisms to study potential functionalities of
molecules in different organisms.

4.1

Yeast-Yeast Network Query Problem

We test our SBCFW-IsoRank algorithm on the yeast-yeast PPI network query problem by solving the
optimization problem introduced in the previous section. We take a subnetwork with 6 proteins (Fig. 1(a))
from the Krogan’s yeast PPI network [8] as the query example to search for the conserved functional complex
in a target network, which is the Collins network [5] with 1,622 proteins and 9,074 interactions. The query
subnetwork is the transcription factor TFIIIC complex in the Krogan’s network and we are interested in
testing whether we can find the same subnetwork in the Collins network. The dimension of our optimization
problem is 6 × 1, 622 = 9, 732. We run this preliminary example so that we can compare our stochastic
optimization results with the results from the power method, which is typically done in the original IsoRank
algorithm [11]. Theoretically, the time and space complexity of our SBCFW-IsoRank at each iteration are
both O(N 2 /n) based on the analysis in Section 3.6. Compared to O(N 2 ) time and space complexity for the
power method by IsoRank [11], our SBCFW-IsoRank algorithm can scale better with properly selected n.
As both the query example and the target network contain interactions among proteins from the same
organism—yeast, we can easily check the correctness of the query result. We define the accuracy as the
number of corrected aligned proteins divided by the total number of proteins in the query subnetwork. We
implement the SBCFW-IsoRank algorithm for different numbers of partitions n but use the same stopping
criterion: B̂x − x ≤ ξ kxk , ξ = 0.1. In Table I, we find that our stochastic optimization algorithm obtains

7

0.14
Objective Function Value

arXiv: some other text goes here

0.16
n=2
n=5
n=10
n=30
n=50
n=100
n=200

0.12
0.1
0.08
0.06
0.04
0.02
0
0

1000

2000
3000
#. Iterations

4000

Figure 2: The change of the objective function values with the increasing number of iterations with different
numbers of partitions.
the same biologically meaningful results as the power method.
Fig. 2 shows the changes of the objective function values with respect to the increasing number of
iterations. As illustrated in Fig. 2, our algorithm converges for all different n. Additionally, we find the
larger the number of partitions n is, the larger the number of iterations we need to have the algorithm
converge to the global optimum with the same stopping criterion. This clearly demonstrates the tradeoff
between the efficiency and scalability of the stochastic optimization algorithms. Interestingly, we notice
that for n = 10, 30, and 50, the number of iterations does not increase much, which indicates that we may
achieve fast computation with reasonably large n because our algorithm is more efficient for larger n at each
iteration.
Table 1: Comparison on different decompositions with ξ = 0.1.
#. of partitions (n) Computational time (s) #. Iterations Accuracy
2
11.60
648
100%
5
8.53
1,045
100%
10
7.44
1,742
100%
30
5.05
1,880
100%
50
4.93
2,070
100%
100
7.06
2,942
100%
200
13.05
4,478
100%

To further investigate the performance with different n, we run our algorithm 10 times for each n and show
the average computational time, the average number of iterations, and the average accuracy score in Table I.
From Table I, we observe that for all different n, our algorithm can obtain 100% accuracy, which again
demonstrates the effectiveness and convergence of our generalized SBCFW algorithm. Also, we notice that
with the increasing n, the number of iterations increase; however, the computational time is first reducing
then increasing. For example, when n = 2, our algorithm converges with the smallest number
 2 of iterations,
N
but the computational time is not the best because at each iteration the algorithm takes O
operations.
2
In contrast, when n = 50, though the number of iterations is larger, but it reaches the global optimum with
8

arXiv: some other text goes here

PUP3

PSMB2
PSMB1
PSMB5
PSMA6

PRE9

PSMB4

PRE2
PRE7

PSMB7
PSMA2
PSMB3
PSMA1

PRE8

PSMB6

PRE5

PRE4

PUP1

SCL1

PSMA7
PSMA3

PRE3

PRE6 PRE1

PUP2 PRE10

PSMA4PSMA5
(a) The proteasome core complex
(Human)

(b) The proteasome core complex
(Yeast)

Figure 3: Querying human protein complex in a yeast PPI network. The proteins are annotated by their
gene names. The solid lines are protein interactions and the dash lines denote orthologous relationships
based on protein sequence similarity by BLAST between the proteins in different organisms. (a) Human
proteasome core complex; (b) The aligned proteasome core complex in yeast found by SBCFW-IsoRank.
the least computation time, which is indeed twice faster than n = 2. The trend of the computational time
implies that there may exist the best number of partitions n∗ . Empirically, when n < n∗ the computational
time decreases while the computational time can increase when n > n∗ . However, it is difficult to provide a
theoretical proof for this observed phenomenon. Finally, for the scalibility of the algorithm, we always prefer
larger n to make the memory requirement as low as possible.

4.2

Human-Yeast Network Query Problem

We further study the biological signficance of network query results by our SBCFW-IsoRank algorithm. We
extract a subnetwork as a query example from a human PPI network archived in IntAct [6]. The query
subnetwork is the proteasome core complex, with induced interactions among the corresponding proteins
from IntAct [6]. The proteasome core complex in human consists of 14 proteins in total, as shown in Fig. 3(a).
The target network is the yeast PPI network, also obtained from IntAct [6], which has 6,392 proteins and
77,065 interactions. Our goal is to find the most similar subnetwork to the human proteasome core complex
in the target yeast PPI network, based on both the interaction topology and the protein sequence similarity,
which is computed by BLAST [14].
We first construct the alignment network, which has N = 14 × 6, 392 = 89, 488 vertices. By our SBCFWIsoRank algorithm with n = 300, instead of operating a matrix of size 89, 488 × 89, 488 by the power method,
we only need to handle a matrix of size 298 × 89, 488. At each iteration, the computational time as well
as the memory requirement are reduced 300 times. Our Matlab implementation of SBCFW-IsoRank on
a MacPro notebook with 8GB RAM takes only around 750 seconds to converge by reaching the stopping
criteria (ξ = 0.1).
The identified subnetwork in the target yeast PPI network by our algorithm is illustrated in Fig. 3(b).
To evaluate the biological significance of the obtained subnetwork, we check the p-value based on GO (Gene
Ontology) enrichment analysis using GOTerm Finder [1]. The identified subnetwork is significantly enriched
in GO term GO:0005839, which is in fact the same proteasome core complex, with p-value 9.552e − 36. This
experiment demonstrates that our algorithm can find the biologically consistent groups of proteins with the
same cellular functionalities as the proteins in the query subnetwork, hence with the capability of transferring
existing biology knowledge in model organisms (yeast for example) to less studied organisms when the group
of proteins in the query subnetwork require better understanding of their cellular functionalities.

9

arXiv: some other text goes here

5

Conclusions

In this paper, we generalize the block coordinate Frank-Wolfe algorithm to solve general convex optimization
problems with any convex and compact constraint set. Our generalized SBCFW algorithm has the convergence guarantee. We re-formulate the IsoRank problem to such a convex programming problem and solve the
biological network alignment problem by our SBCFW-IsoRank algorithm, which scales better with the size
of networks under study. The scalability, efficiency, and effectiveness of our algorithm on solving IsoRank are
demonstrated for real-world PPI network query problems. In our future work, we will consider the derivation
of the optimal partition number for better tradeoff between computational efficiency and scalability.

6

Acknowledgements

The authors would like to thank Simon Lacoste-Julien for pointing out the error in the original conference
paper. This work was partially supported by Awards #1447235 and #1244068 from the National Science
Foundation; as well as Award R21DK092845 from the National Institute Of Diabetes And Digestive And
Kidney Diseases, National Institutes of Health.

References
[1] Boyle, E., Elizabeth, I., Weng, S., Gollub, J., Jin, H., Botstein, D., Cherry, J., and
Sherlock, G. GO::TermFinder—open source software for accessing Gene Ontology information and
finding significantly enriched Gene Ontology terms associated with a list of genes. Bioinformatics 20
(2004), 3710–3715.
[2] Dunn, J. Convergence rates for conditional gradient sequences generated by implicit step length rules.
SIAM Journal on Control and Optimization 5, 473-487 (1980).
[3] Dunn, J., and Harshbarger, S. Conditional gradient algorithms with open loop step size rules.
Journal of Mathematical Analysis and Applications 62, 432-444 (1978).
[4] Frank, M., and Wolfe, P. An algorithm for quadratic programming. Naval Research Logistics
Quarterly 3, 95-110 (1956).
[5] Hasty, J., McMillen, D., Issacs, F., and Collins, J. Computational studies of gene regulatory
networks: in numero molecular biology. Nat Rev Genet 2 (2001), 268–279.
[6] Kerrien, S., Aranda, B., Breuza, L., and et al. The intact molecular interaction database in
2012. Nucleic Acids Research 40, D1 (2012), D841–D846.
[7] Klau, G. A new graph-based method for pairwise global network alignment. BMC Bioinformatics 10,
Suppl 1 (2009), S59.
[8] Krogan, N., et al. Global landscape of protein complexes in the yeast Saccharomyces cerevisiae.
Nature 440 (2006), 4412–4415.
[9] Lacoste-Julien, S., Jaggi, M., Schmidt, M., and Pletscher, P. Block-coordinate frank-wolfe
optimization for structural svms. In International Conference on Machine Learning (2013).
[10] Ortega, J., and Rheinbold, W. C. Iterative Solution of Nonlinear Equations in Several Variables.
Society for Industrial and Applied Mathematics, 1970.
[11] Singh, R., Xu, J., and Berger, B. Global alignment of multiple protein interaction networks with
application to functional orthology detection. Proc. Natl Acad. Sci. 105 (2008), 12763–12768.
[12] Uryasev, S., and Pardalos, P. M., Eds. Stochastic Optimization: Algorithm and Application.
Springer, 2001.

10

arXiv: some other text goes here

[13] Zaslavskiy, M., Bach, F., and Vert, J. Global alignment of protein-protein interaction networks
by graph matching methods. Bioinformatics 25 (2009), 259–267.
[14] Zhang, Z., Schwartz, S., Wagner, L., and Miller, W. A greedy algorithm for aligning dna
sequences. J Comput Biol 7(1-2) (2000), 203–214.

11

