I was talking with colleagues about link prediction in directed networks and we came up with the following problem: Given a square, asymmetric matrix **A**, find a decomposition

**A** = **U** **X U**¯¹

such that **U** is orthogonal, and **X** is not necessarily diagonal. The idea is to introduce asymmetry into the decomposition by making **X** asymmetric, and therefore non-diagonal. If the decomposition is of low-rank, i.e. **U** is a *n*-by-*r* matrix and **X** a *r*-by-*r* matrix with *r *≪ *n*, then we can then compute powers of **A** very efficiently by computing powers of **X**, and thus compute any power of **A**. The result is that we can implement link prediction in directed graph efficiently.

Do you have an idea how to solve this? There doesn’t seem to be a common name for this kind of decomposition– If you know anything, please comment!

**Background**

Given a network with *n* nodes, we can represent it as an *n*-by-*n* matrix **A** called the adjacency matrix. The power **A*** ^{k}* can then be used to count the number of paths from any node to any other node. Since in practice

**A**is very large, we can’t just compute powers of it by matrix multiplication. Instead, one must use matrix decompositions. For instance, if

**A**is symmetric, then it has an eigenvalue decomposition

**A** = **U Λ U**^{T}

This can be exploited to compute powers of **A** by using the fact that in the eigenvalue decomposition, **U** is an orthogonal matrix (meaning that **U**^{T} = **U**¯¹) and that **Λ** is diagonal (meaning that its powers can be computed by computing the powers of its diagonal elements):

**A**^{k} = **U Λ U**^{T} **U Λ U**^{T} … **U Λ U**^{T} = **U Λ**^{k} **U**^{T}

The trick works because **U**^{T} **U** equals the identity matrix. If the graph is directed however, then **A** is asymmetric and this trick does not work! A related idea is to use the singular value decomposition, which is defined for all matrices:

**A** = **U Σ V**^{T}

This is defined for asymmetric matrices, but the trick from above does not work, because **V**^{T} **U** will not simplify away. Any ideas?

**ADDENDUM**

Thanks for Tamara G. Kolda for giving the solution: The decomposition is called DEDICOM, which stands for *Decomposition into Directional Components*. See these two papers:

Models for Analysis of Asymmetrical Relationships Among N Objects or Stimuli

, Richard Harshman, First Joint

Meeting of the Psychometric Society and the Society for

Mathematical Psychology, 1978.

Here’s a 3-way version of it, i.e. for 3-tensors:

Temporal analysis of semantic graphs using ASALSAN,

Brett Bader, Richard Harshman & Tamara G. Kolda, ICDM 2007.

**ADDENDUM (DECEMBER 2012)**

I wrote a paper about this decomposition and its application to link prediction in directed networks at the International Conference on Data Mining 2012:

Predicting Directed Links using Nondiagonal Matrix Decomposition

, Jérôme Kunegis & Jörg Fliege, ICDM 2012.

It’s called 2-way DEDICOM. See http://www.sandia.gov/~tgkolda/pubs/bibtgkfiles/ICDM07.pdf and references therein.

@Tamara Great; this is exactly what I was looking for!