Intuition behind matrix factorization formulations?

Question

I'm reading this paper about matrix factorization. In the paper they propose to use this factorization for the adjacency (or similarity) matrix $G$ using the following formulation: $G = U \Lambda U^T$ where $U \in R^{n \times k}$, $\Lambda \in R^{k \times k}$.

They say that when the graph is undirected then we can omit $\Lambda$ and have it like this $G = U U^T$. I can understand the intuition behind that formulation. However the authors said that if the graph is directed then they used this formulation $G = U \Lambda U^T$. They didn't explain at all why we should use $\Lambda$ for directed graphs! They just said we follow a paper for that formulation. I went to read the linked paper for the formulation, but it also has a very poooor explanation! Or probably an unconvincing explanation.

• Does anyone understand why we should use the other factorization when we have a directed graph?

• When people provide a formulation for a matrix factorization, do they need to provide an explanation for that? Because one could make a fancy factorization formula and just say "hey look it works!". As I saw so far from matrix factorization papers, there is no good solid ground for the formulations. Am I mistaken?

Answer 1

Regarding the points you raised:

1. The authors of the first paper you cite (Menon & Elkan) use the other factorization, $G \approx U\Lambda U^T$, for the case of a directed graph because as they explicitly say: "For directed graphs, we can let $\Lambda$ be an arbitrary asymmetric matrix" (p. 442) . This is important as while an undirected adjacency graph is by definition symmetric, the same is far from guaranteed for directed adjacency graph. To that extent, you can easily convince yourself that $A=UU^T$ has to be symmetric so to get $A$ to be asymmetric you need a non-symmetric matrix $\Lambda$ to come into play.

   This point about asymmetry actually what the authors of the second paper you link against (Zhu et al.) also raise: "..., we suggest a different factorization: \begin{align} min_{Z,U} || A - ZUZ^T||_F^2 + \gamma|| U ||^2_F \end{align} where U an $l \times l$ full matrix. Note that $U$ is not symmetric, thus $ZUZ^T$ produces an asymmetric matrix, which is the case of $A$" (p. 3). Just to elaborate why this asymmetry is important and how it relates to an actual adjacency matrix: Given an adjacency matrix $A$ where $A_{i,j}$ is link between nodes $i$ and $j$ if the matrix is undirected one can assume $A_{i,j} = A_{j,i}$. If though $A_{i,j}$ is the directed link from node $i$ to node $j$, there is no guarantee that a directed link from node $j$ to $i$ also exist (so it is not $0$) and even if it exists that $A_{i,j} = A_{j,i}$.

   Clearly there is some notation overloading going on ($\Lambda = U$ between the two papers) but I hope you are now convinced why $\Lambda$ is used to begin with; without a (potenially) asymmetric $\Lambda$ you cannot have an (quite possibly) asymmetric adjacency matrix for a directed network.

2. I think you are over-stating things a bit. The majority of peer-reviewed papers from respectable journals/conferences (as ECML and SIGIR in these cases) are working and they do provide adequate explanations for that they are doing. Mathematical rigor might not be their prime target and they might have some undesirable properties (eg. non-uniqueness in the original NNMF) but they are not back-of-the-envelope calculations done in good faith.