Search

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\left(\frac{1}{d_{\mathrm{min}}}\cdot \min\left(d_t, m^{1/2}\right)\right)$, where $d_{\mathrm{min}}$ denotes the minimum degree of $G$, and $d_t$ denotes the degree of $t$, respectively. Compared to the previously best upper bound of $ O\left(\log{n}\cdot \min\left(d_t, m^{1/2}\right)\right)$ (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 $\Theta\left(\frac{\log{n}}{d_{\mathrm{min}}}\right)$ with a much simpler algorithm. Furthermore, we establish a matching lower bound of $\Omega\left(\frac{1}{d_{\mathrm{min}}}\cdot \min\left(d_t, m^{1/2}\right)\right)$ 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., Comment: KDD 2024

We revisit the classic local graph exploration algorithm ApproxContributions proposed by Andersen, Borgs, Chayes, Hopcroft, Mirrokni, and Teng (WAW '07, Internet Math. '08) for computing an $\epsilon$-approximation of the PageRank contribution vector for a target node $t$ on a graph with $n$ nodes and $m$ edges. We give a worst-case complexity bound of ApproxContributions as $O(n\pi(t)/\epsilon\cdot\min(\Delta_{in},\Delta_{out},\sqrt{m}))$, where $\pi(t)$ is the PageRank score of $t$, and $\Delta_{in}$ and $\Delta_{out}$ are the maximum in-degree and out-degree of the graph, resp. We also give a lower bound of $\Omega(\min(\Delta_{in}/\delta,\Delta_{out}/\delta,\sqrt{m}/\delta,m))$ for detecting the $\delta$-contributing set of $t$, showing that the simple ApproxContributions algorithm is already optimal. We also investigate the computational complexity of locally estimating a node's PageRank centrality. We improve the best-known upper bound of $\widetilde{O}(n^{2/3}\cdot\min(\Delta_{out}^{1/3},m^{1/6}))$ given by Bressan, Peserico, and Pretto (SICOMP '23) to $O(n^{1/2}\cdot\min(\Delta_{in}^{1/2},\Delta_{out}^{1/2},m^{1/4}))$ by simply combining ApproxContributions with the Monte Carlo simulation method. We also improve their lower bound of $\Omega(\min(n^{1/2}\Delta_{out}^{1/2},n^{1/3}m^{1/3}))$ to $\Omega(n^{1/2}\cdot\min(\Delta_{in}^{1/2},\Delta_{out}^{1/2},m^{1/4}))$ if $\min(\Delta_{in},\Delta_{out})=\Omega(n^{1/3})$, and to $\Omega(n^{1/2-\gamma}(\min(\Delta_{in},\Delta_{out}))^{1/2+\gamma})$ if $\min(\Delta_{in},\Delta_{out})=o(n^{1/3})$, where $\gamma>0$ is an arbitrarily small constant. Our matching upper and lower bounds resolve the open problem of whether one can tighten the bounds given by Bressan, Peserico, and Pretto (FOCS '18, SICOMP '23). Remarkably, the techniques and analyses for proving all our results are surprisingly simple., Comment: 30 pages, 3 figures, full version of a STOC 2024 paper

Personalized PageRank (PPR) is a traditional measure for node proximity on large graphs. For a pair of nodes $s$ and $t$, the PPR value $\pi_s(t)$ equals the probability that an $\alpha$-discounted random walk from $s$ terminates at $t$ and reflects the importance between $s$ and $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., Comment: 20 pages, "accepted version" of an article accepted by IEEE Transactions on Knowledge and Data Engineering (TKDE) for publication

Learning from the limited amount of labeled data to the pre-train model has always been viewed as a challenging task. In this report, an effective and robust solution, the two-stage training paradigm YOLOv8 detector (TP-YOLOv8), is designed for the object detection track in VIPriors Challenge 2023. First, the backbone of YOLOv8 is pre-trained as the encoder using the masked image modeling technique. Then the detector is fine-tuned with elaborate augmentations. During the test stage, test-time augmentation (TTA) is used to enhance each model, and weighted box fusion (WBF) is implemented to further boost the performance. With the well-designed structure, our approach has achieved 30.4% average precision from 0.50 to 0.95 on the DelftBikes test set, ranking 4th on the leaderboard., Comment: 4 pages, 2 figures

PageRank is a famous measure of graph centrality that has numerous applications in practice. The problem of computing a single node's PageRank has been the subject of extensive research over a decade. However, existing methods still incur large time complexities despite years of efforts. Even on undirected graphs where several valuable properties held by PageRank scores, the problem of locally approximating the PageRank score of a target node remains a challenging task. Two commonly adopted techniques, Monte-Carlo based random walks and backward push, both cost $O(n)$ time in the worst-case scenario, which hinders existing methods from achieving a sublinear time complexity like $O(\sqrt{m})$ on an undirected graph with $n$ nodes and $m$ edges. In this paper, we focus on the problem of single-node PageRank computation on undirected graphs. We propose a novel algorithm, SetPush, for estimating single-node PageRank specifically on undirected graphs. With non-trival analysis, we prove that our SetPush achieves the $\tilde{O}\left(\min\left\{d_t, \sqrt{m}\right\}\right)$ time complexity for estimating the target node $t$'s PageRank with constant relative error and constant failure probability on undirected graphs. We conduct comprehensive experiments to demonstrate the effectiveness of SetPush., Comment: Technical Report

We study the fundamental problem of sampling independent events, called subset sampling. Specifically, consider a set of $n$ events $S=\{x_1, \ldots, x_n\}$, where each event $x_i$ has an associated probability $p(x_i)$. The subset sampling problem aims to sample a subset $T \subseteq S$, such that every $x_i$ is independently included in $S$ with probability $p_i$. A naive solution is to flip a coin for each event, which takes $O(n)$ time. However, the specific goal is to develop data structures that allow drawing a sample in time proportional to the expected output size $\mu=\sum_{i=1}^n p(x_i)$, 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. However, most of the existing subset sampling approaches are conducted in a static setting, where the events or their associated probability in set $S$ is not allowed to be changed over time. These algorithms incur either large query time or update time in a dynamic setting despite the ubiquitous time-evolving events with changing probability in real life. Therefore, it is a pressing need, but still, an open problem, to design efficient dynamic subset sampling algorithms. In this paper, we propose ODSS, the first optimal dynamic subset sampling algorithm. The expected query time and update time of ODSS are both optimal, matching the lower bounds of the subset sampling problem. We present a nontrivial theoretical analysis to demonstrate the superiority of ODSS. We also conduct comprehensive experiments to empirically evaluate the performance of ODSS. Moreover, we apply ODSS to a concrete application: influence maximization. We empirically show that our ODSS can improve the complexities of existing influence maximization algorithms on large real-world evolving social networks., Comment: ACM SIGKDD 2023

Drop-on-demand (DOD) inkjet printing has been considered as one of promising technologies for the fabrication of advanced functional materials. For a DOD printer, high-precision dispensing techniques for achieving satellite-free smaller droplets, have long been desired for patterning thin-film structures. The present study considers the inlet velocity of a liquid chamber located upstream of a dispensing nozzle as a control variable and aims to optimize its waveform using a sample-efficient Bayesian optimization algorithm. Firstly, the droplet dispensing dynamics are numerically reproduced by using an open-source OpenFOAM solver, interFoam, and the results are passed on to another code based on pyFoam. Then, the parameters characterizing the actuation waveform driving a DOD printer are determined by the Bayesian optimization (BO) algorithm so as to maximize a prescribed multi-objective function expressed as the sum of two factors, i.e., the size of a primary droplet and the presence of satellite droplets. The results show that the present BO algorithm can successfully find high-precision dispensing waveforms within 150 simulations. Specifically, satellite droplets can be effectively eliminated and the droplet diameter can be significantly reduced to 24.9% of the nozzle diameter by applying the optimal waveform., Comment: The following article has been submitted to Physics of Fluids

Graph Neural Networks (GNNs) have been widely used for modeling graph-structured data. With the development of numerous GNN variants, recent years have witnessed groundbreaking results in improving the scalability of GNNs to work on static 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. Given a graph G=(V,E) and a source node $s \in V$, a single-source PPR (SSPPR) query asks for the PPR value $\vpi(u)$ with respect to s, which represents the relative importance of node u in the context of the source node s. Among existing algorithms for SSPPR queries, LocalPush is a fundamental method which 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, 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. Hence, 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, both in terms of $\ell_1$-error and normalized additive error. 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., Comment: VLDB 2022, volume 15, issue 7

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. In this paper, we propose Approximate Graph Propagation (AGP), a unified randomized algorithm that computes various proximity queries and GNN feature propagation, including transition probabilities, Personalized PageRank, heat kernel PageRank, Katz, SGC, GDC, and APPNP. Our algorithm provides a theoretical bounded error guarantee and runs in almost optimal time complexity. We conduct an extensive experimental study to demonstrate AGP's effectiveness in two concrete applications: local clustering with heat kernel PageRank and node classification with GNNs. Most notably, we present an empirical study on a billion-edge graph Papers100M, the largest publicly available GNN dataset so far. The results show that AGP can significantly improve various existing GNN models' scalability without sacrificing prediction accuracy., Comment: ACM SIGKDD 2021

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 $\pi(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 \in V$. However, the single-source query only reflects the importance of each node $t$ with respect to $s$. In this paper, we consider the {\em 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., Comment: ACM SIGKDD 2020

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 $10^6$ 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 ExactSim, 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., Comment: ACM SIGMOD 2020