I have been reading this paper https://arxiv.org/abs/1307.6864 which is concerned with matrix completion problems of the following form: Suppose we know that $A=xx^*$ is the outer product of a vector $x\in\mathbb{C}^N$ with itself (i.e. a positive definite rank one matrix), can we construct $A$ given only a few of its entries?
Let $D=\{(1,1),\ldots,(N,N)\}$ denote the diagonal in $\{0,\ldots,N\}^2$ and let $E\subseteq \{1,\ldots,N\}^2\setminus D$ be a symmetric set (meaning that $(i,j)\in E\Rightarrow (j,i)\in E$). Assume that the given data is precisely $\{A_{i,j}, (i,j)\in D\cup E\}$. Theorem 4 in the article then establishes a connection between the matrix completion problem and the spectral gap of the matrix (called data weighted graph laplacian) $$ L_{i,j}= \begin{cases} \sum_{(i,k)\in E} |x_k|^2,\quad j=i\\ -|x_i| |x_j|, \quad (i,j)\in E\\ 0, \qquad \text{otw} \end{cases} $$ My question is now which graph does the Laplacian correspond to? I know how to set up the Laplacian when I am given a weighted graph, but here it is the other way round. It seems to me that there is a compatibility problem as the diagonal entries do not correspond to the degree when the edge weights are defined by $|x_i||x_j|$. Is there maybe a less standard notion of graph laplacian where this one fits into? Or is it a matter of some similarity transformation? A connection between spectral gap and geometric/isoperimetric/connectivity quantity of an associated graph would be nice.