Time complexity of matrix multiplication in Big-Align
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)$.