.png){kind=icon}
返回
Sublinear update time randomized algorithms for dynamic graph regression
.png){kind=icon}
OA
AI
DOI：10.1016/j.amc.2021.126434.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 x d matrix embedding M of the graph, where d << n and M has certain properties. Let rbethenumber of samples required by subsampled randomized Hadamard transform for a 1 +/- 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 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)/epsilon(2) log(6) (d/epsilon)). (c) 2021 Elsevier Inc. All rights reserved.
Keyword:
Dynamic networks
Dynamic graph regression
Least squares regression
Sublinear update time
Subsampled randomized Hadamard transform
CountSketch
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.4
论文数:
2.3W
被引数:
3.3W
机构
引用论文
A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications图嵌入的综合调查: 问题，技术和应用OAAI
OAAI分享收藏gBoost: a mathematical programming approach to graph classification and regression.png)
MACHINE LEARNING
OAAI
MACHINE LEARNINGIF2.9
OAAI分享收藏
查看更多内容