Sketch-based Randomized Algorithms for Dynamic Graph Regression
share
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 problem 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 randomized algorithms. Suppose that we are given an n× m matrix embedding M of the graph, where m ≪ n. Let r be the number of samples required for a guaranteed approximation error, which is a sublinear function of n. Our first algorithm reduces time complexity of pre-processing to O(n(m + 1) + 2n(m + 1) _2(r + 1) + rm^2). Then after an edge insertion or an edge deletion, it updates the approximate solution in O(rm) time. Our second algorithm reduces time complexity of pre-processing to O ( nnz(M) (n/ϵ) + m^3 ^2 m + m^2 (1/ϵ) ), where nnz(M) is the number of nonzero elements of M. Then after an edge insertion or an edge deletion or a node insertion or a node deletion, it updates the approximate solution in O(qm) time, with q=O(m^2/ϵ^2).
READ FULL TEXT