Time complexity of matrix multiplication in Big-Align

Question

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?

Answer 1

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)$.

Answer 2

The paper is correct, but you need to keep reading to understand why. Often when something in a paper doesn't make sense, it makes sense to keep reading the next few paragraphs, as sometimes the authors will follow a non-obvious claim with information to help you understand why the claim is true.

The subtle point here has to do with the difference between computing a matrix explicitly (i.e., outputting all of its elements) vs implicitly (i.e., computing some compressed form of the matrix where you don't store all elements explicitly, but where the compressed form is good enough for everything you plan to do with the matrix).

$\bf P$ is a $n \times n$ matrix. Therefore you can't compute it explicitly in $O(nd^2)$ time. Merely outputting all of the entries of the matrix $\bf P$ requires $\Omega(n^2)$ time. In other words, there is no algorithm to output the matrix $\bf P$ explicitly in $O(n d^2)$ time.

This doesn't rule out the possibility of an algorithm that outputs some implicit representation of $\bf P$. Indeed, the very next paragraph in the paper discusses representing $\bf P$ implicitly in compressed form as the product of two low-rank matrices. You can view equation (5) as already computing $\bf P$ in such a form. In particular, if we view $\bf 1 \cdot Y$ as the "simpler terms" to be omitted, $\bf B \cdot \bf X$ is already a representation of that matrix as a product of two low-rank matrices: $\bf B$ is a $n \times d$ matrix and $X$ is a $d \times n$ matrix, so both have rank at most $d$.

In that sense, computing $\bf P$ in such a form (omitting "simpler terms") amounts to computing $\bf B$ and computing $\bf X$. That can be done in $O(nd^2)$ time, as follows. $\bf B$ is given, so there's nothing to do to compute it. So, all that remains it to compute $\bf X = A^T U S^{-2} U^T$ in $O(n d^2)$ time, given $\bf A,U,S$. This can be done in three steps:

1. Compute $\bf U S^{-2}$. This can be done in $O(nd^2)$ time, by using the special structure of $\bf S$. In particular, you can view $\bf U S^{-2}$ as a $n \times d$ matrix (strictly speaking, it is a $n \times n$ matrix, but the last $n-d$ columns are all zero, so we're only going to compute its first $d$ columns).

2. Compute $\bf A^T U S^{-2}$. This can be done in $O(nd^2)$ time, as you are basically multiplying a $d \times n$ matrix ($\bf A^T$) by a $n \times d$ matrix ($\bf U S^{-2}$). The result is basically a $d \times d$ matrix (strictly speaking, it is a $d \times n$ matrix, but the last $n-d$ columns are all zero, so we only need to compute its first $d$ columns).

3. Compute $\bf A^T U S^{-2} U^T$. This can also be done in $O(nd^2)$ time, as you are basically multiplying a $d \times d$ matrix by a $d \times n$ matrix. The result is a $d \times n$ matrix. (Strictly speaking, $\bf A^T U S^{-2}$ is a $d \times n$ matrix and $\bf U^T$ is a $n \times n$ matrix, but the last $n-d$ columns of $\bf A^T U S^{-2}$ are all zero, so the last $n-d$ rows of $\bf U^T$ don't matter, and we can view this as multiplying a $d \times d$ matrix by a $d \times n$ matrix.)

Each step can be completed in $O(nd^2)$ time, so the whole computation can be done in $O(nd^2)$ time.