Newton Sketches: Estimating Node Intimacy in Dynamic Graphs Using Newton's Law of Cooling

Dynamic graphs are gaining importance in many real-world applications based on different graph queries. Due to the large volume and high dynamicity, people resort to compute approximations to answer graph queries. However, previous work primarily evaluates the relationship between nodes based on frequency, which is not sufficient in many cases. We observe that this relationship varying process is highly similar to the water cooling process in nature. Based on the observation, we formulate a new concept Intimacy with Newton's law of cooling, to illustrate the relationship between nodes. Currently, there is no prior algorithm tailored for Intimacy estimation. Because Intimacy varies in every time unit, the main challenge lies in how to record and update the Intimacy efficiently. In this paper, we propose a novel technique named Newton-Observe to address this challenge. The key idea of Newton-Observe is that we only decay the Intimacy when we observe/query it. Based on Newton-Observe, we develop a series of Newton sketches to answer three fundamental tasks of Intimacy in dynamic graphs. We theoretically prove that the Newton sketch can estimate the Intimacy within an additive constant error to the real Intimacy. Our experiments on real-world datasets and synthetic datasets show that Newton-Observe outperform the strawman solution by up to$570\times$smaller ARE and improve the throughput by up to$1.62\times$. All source codes are open sourced at Github anonymously.