# Updating factorization of Laplacian (add/remove edges)

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.

• – Kirill Aug 9 '16 at 3:04
• Thanks for the link --- indeed I was just trying to code that paper up yesterday :-) . The issue I see (beyond my lack of coding skills getting it to work...) is that the update formula would update a dense pseudoinverse matrix, which will be expensive for large $G$. I was hoping to make use of sparse matrix factorizations. But maybe there's a way to combine the two? – Justin Solomon Aug 9 '16 at 13:13
• Update: We managed to find a reasonable solution, documented in this paper --- people.csail.mit.edu/jsolomon/assets/sisc_transport.pdf – Justin Solomon Dec 26 '18 at 18:18