Sublinear Update Time Randomized Algorithms for Dynamic Graph Regression

Abstract

A well-known problem in data science and machine learning is 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 subsampled randomized Hadamard transform and CountSketch to propose the first sublinear update time randomized algorithms for regression of general dynamic graphs. Suppose that we are given a n d matrix embedding M of the graph, where d n and M has certain properties. Let r be the number of samples required by subsampled randomized Hadamard transform for a 1 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 CountSketch and supports edge insertion, edge deletion, node insertion and node deletion. It updates the approximate solution in O(qd) time, where q=O(d^2^2 ^6(d/) ).

Tasks

Reproductions