We study the problem of efficiently approximating the effective resistance (ER) on undirected graphs, where ER is a widely used node proximity measure with applications in graph spectral sparsification, multi-class graph clustering, network robustness analysis, graph machine learning, and more. Specifically, given any nodes s and t in an undirected graph G, we aim to efficiently estimate the ER value R(s,t) between nodes s and t, ensuring a small absolute error ε. The previous best algorithm for this problem has a worst-case computational complexity of Õ(Lmax3/ε2d2), where the value of Lmax depends on the mixing time of random walks on G, d = mind(s), d(t), and d(s), d(t) denote the degrees of nodes s and t, respectively. We improve this complexity to Õ ( min Lmax7/3/ε2/3, Lmax3/ε2d2,mLmax ), achieving a theoretical improvement of Õ (maxLmax2/3/ε4/3d2,1, Lmax2/ε2d2m2) over previous results. Here, m denotes the number of edges. Given that Lmax is often very large in real-world networks (e.g., Lmax > 104), our improvement on Lmax is significant, especially for real-world networks. We also conduct extensive experiments on real-world and synthetic graph datasets to empirically demonstrate the superiority of our method. The experimental results show that our method achieves a 10× to 1000× speedup in running time while maintaining the same absolute error compared to baseline methods.

We propose a simple and optimal algorithm, BackMC, for local PageRank estimation in undirected graphs: given an arbitrary target node t in an undirected graph G comprising n nodes and m edges, BackMC accurately estimates the PageRank score of node t while assuring a small relative error and a high success probability. The worst-case computational complexity of BackMC is upper bounded by O(1/dmin ⋅ min(dt, m1/2)), where dmin denotes the minimum degree of G, and dt denotes the degree of t, respectively. Compared to the previously best upper bound of O(log n ⋅ min(dt, m1/2)) (VLDB '23), which is derived from a significantly more complex algorithm and analysis, our BackMC improves the computational complexity for this problem by a factor of Θ(log n/dmin) with a much simpler algorithm. Furthermore, we establish a matching lower bound of Ω(1/dmin ⋅ min(dt, m1/2)) for any algorithm that attempts to solve the problem of local PageRank estimation, demonstrating the theoretical optimality of our BackMC. We conduct extensive experiments on various large-scale real-world and synthetic graphs, where BackMC consistently shows superior performance.

In this paper, we study the Dynamic Parameterized Subset Sampling (DPSS) problem in the Word RAM model. In DPSS, the input is a set, S , of n items, where each item, x , has a non-negative integer weight, w(x). Given a pair of query parameters, (α, β), each of which is a non-negative rational number, a parameterized subset sampling query on S seeks to return a subset T ⊆ S such that each item x∈ S is selected in T , independently, with probability p_x(α, β) which is the minimum between 1 and w(x) / (α \cdot W + β), where W is the total weight of the items in S . More specifically, the DPSS problem is defined in a dynamic setting, where the item set, S , can be updated with insertions of new items or deletions of existing items. Our first main result is an optimal algorithm for solving the DPSS problem, which achieves O(n) pre-processing time, O(1+μ_S(α,β)) expected time for each query parameterized by (α, β), given on-the-fly, and O(1) time for each update; here, μ_S(α,β) is the expected size of the query result. At all times, the worst-case space consumption of our algorithm is linear in the current number of items in S . Our second main contribution is a hardness result for the DPSS problem when the item weights are O(1)-word float numbers, rather than integers. Specifically, we reduce Integer Sorting to the deletion-only DPSS problem with float item weights. Our reduction shows that an optimal algorithm for deletion-only DPSS with float item weights (achieving all the same bounds as aforementioned) implies an algorithm for sorting N integers in O(N) expected time. The latter remains an important open problem. Moreover, a deletion-only DPSS algorithm which supports float item weights, with complexities worse, by at most a factor of o(√łog łog N), than the optimal counterparts, would already improve the current-best integer sorting algorithm [FOCS 2002]. Last but not least, a key technical ingredient for our first main result is a set of exact and efficient algorithms for generating Bernoulli (of certain forms) and Truncated Geometric random variates in O(1) expected time with O(n) worst-case space in the Word RAM model. Generating Bernoulli and geometric random variates efficiently is of great importance not only to sampling problems but also to encryption in cybersecurity. We believe that our new algorithms may be of independent interests for related research.

Personalized PageRank (PPR) is a traditional measure for node proximity on large graphs. For a pair of nodes$\boldsymbol{s}$and$\boldsymbol{t}$, the PPR value$\boldsymbol{\pi_{s}(t)}$equals the probability that an$\boldsymbol{\alpha }$-discounted random walk from$\boldsymbol{s}$terminates at$\boldsymbol{t}$and reflects the importance between$\boldsymbol{s}$and$\boldsymbol{t}$in a bidirectional way. As a generalization of Google's celebrated PageRank centrality, PPR has been extensively studied and has found multifaceted applications in many fields, such as network analysis, graph mining, and graph machine learning. Despite numerous studies devoted to PPR over the decades, efficient computation of PPR remains a challenging problem, and there is a dearth of systematic summaries and comparisons of existing algorithms. In this paper, we recap several frequently used techniques for PPR computation and conduct a comprehensive survey of various recent PPR algorithms from an algorithmic perspective. We classify these approaches based on the types of queries they address and review their methodologies and contributions. We also discuss some representative algorithms for computing PPR on dynamic graphs and in parallel or distributed environments.

We study the fundamental problem of sampling independent events, called subset sampling. Specifically, consider a set of n distinct events S=x1, …, xn, in which each event xi has an associated probability p(xi). The subset sampling problem aims to sample a subset T ⊆ S, such that every xi is independently included in T with probability p(xi). A naive solution is to flip a coin for each event, which takes O(n) time. However, an ideal solution is a data structure that allows drawing a subset sample in time proportional to the expected output size μ=∑i=1n p(xi), which can be significantly smaller than n in many applications. The subset sampling problem serves as an important building block in many tasks and has been the subject of various research for more than a decade.

Graph Neural Networks (GNNs) have been widely used for modeling graph-structured data. Recent breakthroughs have been made in improving the scalability of GNNs to work on graphs with millions of nodes. However, how to instantly represent continuous changes of large-scale dynamic graphs with GNNs is still an open problem. Existing dynamic GNNs focus on modeling the periodic evolution of graphs, often on a snapshot basis. Such methods suffer from two drawbacks: first, there is a substantial delay for the changes in the graph to be reflected in the graph representations, resulting in losses on the model's accuracy; second, repeatedly calculating the representation matrix on the entire graph in each snapshot is predominantly time-consuming and severely limits the scalability. In this paper, we propose Instant Graph Neural Network (InstantGNN), an incremental computation approach for the graph representation matrix of dynamic graphs. Set to work with dynamic graphs with the edge-arrival model, our method avoids time-consuming, repetitive computations and allows instant updates on the representation and instant predictions. Graphs with dynamic structures and dynamic attributes are both supported. The upper bounds of time complexity of those updates are also provided. Furthermore, our method provides an adaptive training strategy, which guides the model to retrain at moments when it can make the greatest performance gains. We conduct extensive experiments on several real-world and synthetic datasets. Empirical results demonstrate that our model achieves state-of-the-art accuracy while having orders-of-magnitude higher efficiency than existing methods.

Personalized PageRank (PPR) is a popular node proximity metric in graph mining and network research. A single-source PPR (SSPPR) query asks for the PPR value of each node on the graph. Due to its importance and wide applications, decades of efforts have been devoted to the efficient processing of SSPPR queries. Among existing algorithms, LocalPush is a fundamental method for SSPPR queries and serves as a cornerstone for subsequent algorithms. In LocalPush , a push operation is a crucial primitive operation, which distributes the probability at a node u to ALL u 's neighbors via the corresponding edges. Although this push operation works well on unweighted graphs, unfortunately, it can be rather inefficient on weighted graphs. In particular, on unbalanced weighted graphs where only a few of these edges take the majority of the total weight among them, the push operation would have to distribute "insignificant" probabilities along those edges which just take the minor weights, resulting in expensive overhead. To resolve this issue, in this paper, we propose the EdgePush algorithm, a novel method for computing SSPPR queries on weighted graphs. EdgePush decomposes the aforementioned push operations in edge-based push , allowing the algorithm to operate at the edge level granularity. As a result, it can flexibly distribute the probabilities according to edge weights. Furthermore, our EdgePush allows a fine-grained termination threshold for each individual edge, leading to a superior complexity over LocalPush. Notably, we prove that EdgePush improves the theoretical query cost of LocalPush by an order of up to O ( n ) when the graph's weights are unbalanced. Our experimental results demonstrate that EdgePush significantly outperforms state-of-the-art baselines in terms of query efficiency on large motif-based and real-world weighted graphs.

Efficient computation of node proximity queries such as transition probabilities, Personalized PageRank, and Katz are of fundamental importance in various graph mining and learning tasks. In particular, several recent works leverage fast node proximity computation to improve the scalability of Graph Neural Networks (GNN). However, prior studies on proximity computation and GNN feature propagation are on a case-by-case basis, with each paper focusing on a particular proximity measure.

Personalized PageRank (PPR) is a widely used node proximity measure in graph mining and network analysis. Given a source node s and a target node t, the PPR value π(s,t) represents the probability that a random walk from s terminates at t, and thus indicates the bidirectional importance between s and t. The majority of the existing work focuses on the single-source queries, which asks for the PPR value of a given source node s and every node t ∈ V. However, the single-source query only reflects the importance of each node t with respect to s. In this paper, we consider the single-target PPR query, which measures the opposite direction of importance for PPR. Given a target node t, the single-target PPR query asks for the PPR value of every node $s\in V$ to a given target node t. We propose RBS, a novel algorithm that answers approximate single-target queries with optimal computational complexity. We show that RBS improves three concrete applications: heavy hitters PPR query, single-source SimRank computation, and scalable graph neural networks. We conduct experiments to demonstrate that RBS outperforms the state-of-the-art algorithms in terms of both efficiency and precision on real-world benchmark datasets.

SimRank is a popular measurement for evaluating the node-to-node similarities based on the graph topology. In recent years, single-source and top-k SimRank queries have received increasing attention due to their applications in web mining, social network analysis, and spam detection. However, a fundamental obstacle in studying SimRank has been the lack of ground truths. The only exact algorithm, Power Method, is computationally infeasible on graphs with more than 106 nodes. Consequently, no existing work has evaluated the actual trade-offs between query time and accuracy on large real-world graphs. In this paper, we present ExSim, the first algorithm that computes the exact single-source and top-k SimRank results on large graphs. With high probability, this algorithm produces ground truths with a rigorous theoretical guarantee. We conduct extensive experiments on real-world datasets to demonstrate the efficiency of ExactSim. The results show that ExactSim provides the ground truth for any single-source SimRank query with a precision up to 7 decimal places within a reasonable query time.