1
$\begingroup$

For a graph $G=(V,E)$, recall that the unweighted Laplacian is $L:=D^\top D$, where $D\in\{-1,0,1\}^{|E|\times|V|}$ is the graph "gradient" operator that subtracts adjacent vertex values onto edges.

I'm writing an algorithm that adds/removes edges one-at-a-time to a graph. In each iteration, I need to apply $L^+$ to a few vectors, where $L^+$ is the Moore-Penrose pseudoinverse of $L$ for the current graph. I could recompute $L$ and its pseudoinverse in each iteration, but this is computationally expensive!

Adding/removing an edge from $E$ makes a rank-1 change to $L$. So, it seems like we could update a sparse factorization (Cholesky? LDLT?) of $L$ and use this to accelerate application of $L^+$. Are there easy-to-use algorithms for this?


NOTES:

I've struggled to apply standard Matlab calls. Challenges include the fact that $L$ always has a null space (constant functions), $G$ may not be a connected graph, and removing an edge is a rank-1 but subtractive update.

Extra credit if you have a pointer to existing library of code!

This paper shows how to update the pseudoinverse of the Laplacian when adding an edge. But it does not show what to do when removing an edge (maybe it's an easy extension, but I didn't see it!), and the pseudoinverse is a dense matrix that I would like to avoid storing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.