Sublinear Update Time Randomized Algorithms for Dynamic Graph Regression

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 $\mathsf{\text{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 ϵ$ 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 $\mathsf{\text{CountSketch}}$ and supports edge insertion, edge deletion, node insertion and node deletion. It updates the approximate solution in $O(qd)$ time, where $q=O(\frac{d^2}{{ϵ}^2}{\log }^6(d\mathrm{/}ϵ))$.