  A well-known problem in data science and machine learning is {\em linear
regression}, which is recently extended to dynamic graphs. Existing exact
algorithms for updating the solution of dynamic graph regression require at
least a linear time (in terms of $n$: the size of the graph). However, this
time complexity might be intractable in practice. In the current paper, we
utilize {\em subsampled randomized Hadamard transform} and \textsf{CountSketch}
to propose the first sublinear update time randomized algorithms for regression
of general dynamic graphs. Suppose that we are given a $n\times d$ matrix
embedding $\mathbf M$ of the graph, where $d \ll n$ and $\mathbf M$ has certain
properties. Let $r$ be the number of samples required by subsampled randomized
Hadamard transform for a $1\pm \epsilon$ approximation, which is a sublinear of
$n$. Our first algorithm supports edge insertion and edge deletion and updates
the approximate solution in $O(rd)$ time. Our second algorithm is based on
\textsf{CountSketch} and supports edge insertion, edge deletion, node insertion
and node deletion. It updates the approximate solution in $O(qd)$ time, where
$q=O\left(\frac{d^2}{\epsilon^2} \log^6(d/\epsilon) \right)$.
