patternMinor
Time complexity of matrix multiplication in Big-Align
Viewed 0 times
alignmultiplicationtimebigmatrixcomplexity
Problem
I am reading the following paper:
Big-Align: Fast Bipartite Graph Alignment. Danai Koutra, Hanghang Tong, David Lubensky. International Conference on Data Mining (ICDM 2013).
I'd like to understand one of the paper's claims about the running time of their algorithm. Their algorithm uses matrix multiplication as follows:
where $n \gg d$, $\bf A,B$ are a $n \times d$ matrices, $\bf U$ is a $n\times n$ matrix, and $\bf S$ is a $n\times n$ diagonal matrix with only the first $d$ diagonal elements being non-zero, with $\bf U,S$ derived from $\bf A$ via a SVD decomposition as indicated above. $\bf A$ has rank at most $d$, so there are at most $d$ non-zero singular values in $\bf S$. All matrices contain only non-negative values.
The multiplication of a $l\times m$ matrix and a $m\times n$ matrix take $O(lmn)$ time.
How can we compute $\bf P$ in $O(nd^2)$ time? I think it suffices to compute $\bf B \cdot \bf X$ in $O(nd^2)$ time. I tried different multiplication orders but cannot arrive at a $O(nd^2)$ time complexity. For example,
1) first compute $US^{-1}$, then result is a $n\times n$ matrix with only the first $d$ columns being "non-zero". Since $S$ is diagonal with $d$ non-zero diagonal elements, the time complexity is $O(nd)$.
2) then compute $A^T(US^{-1})$, the result is a $d\times n$ matrix with only the first $d$ columns being "non-zero". The time complexity is $O(nd^2)$.
3) then compute $B(A^TUS^{-1})$, the result is a $n\times n$ matrix with the first $d$ columns being "non-zero". The time complexity is $O(nd^2)$.
4) then compute $S^{-1}U^T$ similar to 1), the result is a $n\times n$ matrix with the first $d$ rows being "non-zero". The time complexity is $O(nd)$.
5) finally the do multiplication $(BA^TUS^{-1})(S^{-1}U^T)$, but this takes $O(n^2d)$ time.
I tried some other order without success to derive $O(nd^2)$ complexity. Am I missing something, or the paper is wrong about this?
Big-Align: Fast Bipartite Graph Alignment. Danai Koutra, Hanghang Tong, David Lubensky. International Conference on Data Mining (ICDM 2013).
I'd like to understand one of the paper's claims about the running time of their algorithm. Their algorithm uses matrix multiplication as follows:
where $n \gg d$, $\bf A,B$ are a $n \times d$ matrices, $\bf U$ is a $n\times n$ matrix, and $\bf S$ is a $n\times n$ diagonal matrix with only the first $d$ diagonal elements being non-zero, with $\bf U,S$ derived from $\bf A$ via a SVD decomposition as indicated above. $\bf A$ has rank at most $d$, so there are at most $d$ non-zero singular values in $\bf S$. All matrices contain only non-negative values.
The multiplication of a $l\times m$ matrix and a $m\times n$ matrix take $O(lmn)$ time.
How can we compute $\bf P$ in $O(nd^2)$ time? I think it suffices to compute $\bf B \cdot \bf X$ in $O(nd^2)$ time. I tried different multiplication orders but cannot arrive at a $O(nd^2)$ time complexity. For example,
1) first compute $US^{-1}$, then result is a $n\times n$ matrix with only the first $d$ columns being "non-zero". Since $S$ is diagonal with $d$ non-zero diagonal elements, the time complexity is $O(nd)$.
2) then compute $A^T(US^{-1})$, the result is a $d\times n$ matrix with only the first $d$ columns being "non-zero". The time complexity is $O(nd^2)$.
3) then compute $B(A^TUS^{-1})$, the result is a $n\times n$ matrix with the first $d$ columns being "non-zero". The time complexity is $O(nd^2)$.
4) then compute $S^{-1}U^T$ similar to 1), the result is a $n\times n$ matrix with the first $d$ rows being "non-zero". The time complexity is $O(nd)$.
5) finally the do multiplication $(BA^TUS^{-1})(S^{-1}U^T)$, but this takes $O(n^2d)$ time.
I tried some other order without success to derive $O(nd^2)$ complexity. Am I missing something, or the paper is wrong about this?
Solution
D.W. is absolutely right about the time complexity for $\bf X$. Meanwhile, I think the paper is vague on what they are saying and not exact on the complexity.
The paper is about network alignment, where $\bf A$ and $\bf B$ are adjacency matrices for bipartite networks, and $\bf P$ can be viewed as a matrix indicating alignment. $\bf P$ is dependent on $\bf B$ based on the equation. So it is better to view $\bf P$ as a function $\bf P(B)$ of $\bf B$, and $\bf X$ and $\bf Y$ are representation of function $\bf P$.
I believe the paper means first "pre"-compute $\bf X$ and $\bf Y$, store the results somewhere, and then for any given $\bf B$, they can compute the value of $\bf P$ given $\bf B$ using the pre-computed $\bf X,Y$.
The problem is, eventually one has to compute $\bf P (B)$ in order to determine the alignment result between $\bf A$ and $\bf B$. The complexity of that computation is $O(n^2d)$, since $\bf B$ is $n\times d$ and $\bf X$ is $d\times n$, and there is no guaranteed zero rows or columns in $\bf B$ or $\bf X$ to reduce computation.
Thus, the computation of $\bf P(B)$ requires indeed quadratic time. It is just that computation of the function $\bf P$ is $O(d^2n)$.
The paper is about network alignment, where $\bf A$ and $\bf B$ are adjacency matrices for bipartite networks, and $\bf P$ can be viewed as a matrix indicating alignment. $\bf P$ is dependent on $\bf B$ based on the equation. So it is better to view $\bf P$ as a function $\bf P(B)$ of $\bf B$, and $\bf X$ and $\bf Y$ are representation of function $\bf P$.
I believe the paper means first "pre"-compute $\bf X$ and $\bf Y$, store the results somewhere, and then for any given $\bf B$, they can compute the value of $\bf P$ given $\bf B$ using the pre-computed $\bf X,Y$.
The problem is, eventually one has to compute $\bf P (B)$ in order to determine the alignment result between $\bf A$ and $\bf B$. The complexity of that computation is $O(n^2d)$, since $\bf B$ is $n\times d$ and $\bf X$ is $d\times n$, and there is no guaranteed zero rows or columns in $\bf B$ or $\bf X$ to reduce computation.
Thus, the computation of $\bf P(B)$ requires indeed quadratic time. It is just that computation of the function $\bf P$ is $O(d^2n)$.
Context
StackExchange Computer Science Q#72441, answer score: 3
Revisions (0)
No revisions yet.