I have a graph clustering problem I'm working on and it basically involves finding a factorization of the adjacency matrix $A$ such that the following equations are (approximately) satisfied: $$ A \approx L \tilde{A} R,\quad RL\approx \mathbb{I}_k \\ A \in \mathbb{R}^{n \times n},\; L \in \mathbb{R}^{n \times k},\; R \in \mathbb{R}^{k \times n},\; \tilde{A} \in \mathbb{R}^{k \times k},\; \text{and}\; k < n $$ where $A$ and $k$ are inputs, and I would like to calculate $L$, $\tilde{A}$, and $R$. On the face of things, this seems like it's just begging for a spectral or singular value decomposition, but the problem is that $A$ and $\tilde{A}$ have different sizes. I could just do a spectral decomposition and throw away the eigenvectors with the smallest eigenvalues, but (1) if the eigenvalues are all roughly the same magnitude it could introduce large error, and (2) I would actually prefer if $\tilde{A}$ was NOT diagonal, because it has an interpretation as a coarsened/clustered version of the original adjacency matrix, and diagonal adjacency matrices are not interesting to me.
I'm hoping this is a problem that has already been solved, so I don't have to reinvent the wheel here. I tried looking for an algorithm (ideally in the form of a python package) to compute this factorization but haven't been able to find anything. I assume that since there is some dimensional reduction involved this is not exactly soluble and an approximate solution that minimizes some norm $||A - L \tilde{A} R||$ would be satisfactory. Does anyone know if a solution for this type of problem already exists? And if not, what might be the most efficient way to solve it? Gradient descent? Some generalization of ALS?