Latest version of CHOLMOD SuiteSparse package (beta SuiteSparse 4.4.5) has a matlab (and C) API for modifying a symmetric row/column (rank2 update) for $LDL^T$ decomposition (I used it successfully in one of my projects).
You can use it to make $nnz(G)$ updates to the factorization. It is based on this paper.
Therefore, the complexity will be $O(nnz(G)*nnz(L))$. Where $nnz(L)$ can be significantly reduced when using a fill reducing permutation for a sparse $A$
The package can be downloaded from here
Below are some notes the package owner gave (Prof. Tim Davis):
LD = ldlrowmod (LD,k) deletes row/column k, by setting A(:,k) and
A(k,:) to the kth row/col of identity.
LD = ldlrowmod (LD,k,C)
replaces the kth row/col of A (which must be the kth row/col of
identity) with the sparse column C.
The row add/delete takes at most $O(nnz(L))$ time, so if $nnz(L)$ is $O(n)$,
then the time is at most $O(n)$.
Fill reducing permutation:
Rarely is it a good idea to factorize a user's matrix, as in $LDL^T$ =
A. Rather, we permute to $LDL^T$ = $PAP^T$ so that $L$ has vastly fewer