Sublinear Update Time Randomized Algorithms for Dynamic Graph Regression
This addresses efficiency bottlenecks for practitioners working with large-scale dynamic graph data, though it is an incremental improvement over existing methods.
The paper tackles the problem of dynamic graph regression, where existing exact algorithms require linear update time, by proposing the first sublinear update time randomized algorithms. The first algorithm supports edge insertions/deletions with O(rd) time, and the second supports edge/node operations with O(qd) time, where r and q are sublinear in graph size n.
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 ε$ 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}{ε^2} \log^6(d/ε) \right)$.