MLMeihao Liao

Meihao Liao

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Meihao Liao has a total of 19 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Tree+DAG: An Efficient Index for Resistance Distance Computation on Core-Periphery Graphs

    by Meihao Liao, Bao Xing, Rong-Hua Li, Guoren Wang

    Resistance distance computation is a fundamental problem in graph data management. To avoid the high latency of online evaluation, recent work builds offline indexes. Existing approaches, however, fall into two families with complementary weaknesses: loop-erased random-walk methods (e.g., LEIndex) are efficient on fast-mixing graphs but suffer high variance on sparse or tree-like topologies, whereas Cholesky-based methods (e.g., TreeIndex) perform well on small-treewidth graphs but are costly to construct for large, dense networks. In this work, we revisit the probabilistic structure of loop-erased random walks and reveal a previously unexplored connection between their distribution and the Cholesky decomposition of the inverse Laplacian. Building on this insight, we present Tree+DAG, an index that unifies deterministic matrix decomposition with loop-erased random walk sampling. We first apply a core–tree decomposition to split the graph into a tree-like periphery and a dense core. The periphery is isolated via TreeIndex—a compact hierarchical tree labelling that exploits the nonzero pattern of the Cholesky factors of the inverse Laplacian. In the core, random walks mix rapidly and thus erase few cycles; we propose CoreIndex, which stores the DAG encoding the erased cycle structure over the core. This design yields near-linear index size and build time, and low query latency in practice on graphs with a core–periphery structure. Extensive experiments on 10 real-world datasets—including road, social, and web graphs with up to hundreds of millions of edges—show that Tree+DAG delivers at least an order-of-magnitude faster query performance than LEIndex. For example, on Twitter with 21,297,772 nodes and 265,025,545 edges, Tree+DAG attains absolute error 10^-2 with a modest index (3.1 GB, 1.5× the graph) built in 48 minutes, delivering over 3 orders of magnitude faster queries—8×10 -5 seconds vs. 7×10 -1 seconds for LEIndex.

  • Open Access

    Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: A Labelling Approach

    by Meihao Liao, Yueyang Pan, Rong-Hua Li, Guoren Wang

    Resistance distance computation is a fundamental problem in graph analysis, yet existing random walk-based methods are limited to approximate solutions and suffer from poor efficiency on small-treewidth graphs (e.g., road networks). In contrast, shortest-path distance computation achieves remarkable efficiency on such graphs by leveraging cut properties and tree decompositions. Motivated by this disparity, we first analyze the cut property of resistance distance. While a direct generalization proves impractical due to costly matrix operations, we overcome this limitation by integrating tree decompositions, revealing that the resistance distance r(s,t) depends only on labels along the paths from s and t to the root of the decomposition. This insight enables compact labelling structures. Based on this, we propose TreeIndex, a novel index method that constructs a resistance distance labelling of size O(n • h G ) in O(n • h G 2 • d max ) time, where h G (tree height) and d max (maximum degree) behave as small constants in many real-world small-treewidth graphs (e.g., road networks). Our labelling supports exact single-pair queries in O(h G ) time and single-source queries in O(n • h G ) time. Extensive experiments show that TreeIndex substantially outperforms state-of-the-art approaches. For instance, on the full USA road network, it constructs a 405 GB labelling in 7 hours (single-threaded) and answers exact single-pair queries in 10 -3 seconds and single-source queries in 190 seconds-the first exact method scalable to such large graphs.

  • Open Access

    One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor

    by Junjie Zhou, Meihao Liao, Rong-Hua Li, Longlong Lin, Guoren Wang

    Personalized PageRank (PPR) is a fundamental graph proximity measure with a wide range of applications. The single-source Personalized PageRank (SSPPR) query aims to compute the PPR values for all nodes from a given source node. Due to the high computational cost of exact SSPPR computation, most existing solutions focus on approximate queries with accuracy guarantees. The state-of-the-art approaches for approximate SSPPR queries are index-based and are typically designed for a single, fixed value of α. However, real-world applications often require handling multiple values of α, and current index-based methods struggle to adapt to varying values of α without rebuilding the index. To address this limitation, we propose a novel and efficient index approach for SSPPR queries that supports all values of α. A striking feature of our approach is that it stores only a single index for all possible values of α. This is achieved by leveraging the loop-erased α-random walk interpretation of PPR and constructing a stack-style meta-index with a sufficiently large damping factor ā, denoted as StackIndex. Then, we develop a novel technique to efficiently transform StackIndex into a new index for any specified damping factor α, without the need to rebuild the index. We show that our index construction algorithm requires around O (ω n ) time and O (ω n ) space to ensure approximation quality, where ω and n represent the sample size and the number of nodes in the graph, respectively. We also develop an index maintenance technique to update our StackIndex when handling dynamic graphs with edge insertions and deletions. Extensive experiments on 5 large real-world graphs demonstrate that StackIndex offers substantial speedups over previous index-based methods for PPR queries with different α while maintaining the same accuracy guarantee.


  • Open Access

    Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs

    by Meihao Liao, Cheng Li, Rong-Hua Li, Guoren Wang

    In this paper, we study a problem of index maintenance on evolving graphs for effective resistance computation. Unlike an existing matrices-based index, we show that the index can be efficiently maintained by directly preserving samples of random walks and loop-erased walks. This approach not only enables efficient storage and rapid query response but also supports effective maintenance. We propose a novel approach to convert edge updates into landmark node updates. Building upon this, we present two new update algorithms for random walk and loop-erased walk samples respectively. Both algorithms update samples without requiring complete resampling, ensuring accuracy and high efficiency. A particularly challenging and innovative technique involves updating loop-erased walks. Here we develop a novel and powerful cycle decomposition technique for loop-erased walks, enabling us to update samples at the cycle level rather than the node level, significantly enhancing efficiency. Furthermore, we show that both of our methods achieve an Õ (1) time complexity per edge update in real-world graphs under a mild assumption. We conduct extensive experiments using 10 large real-world datasets to evaluate the performance of our approaches. The results show that our best algorithm can be up to two orders of magnitude faster than the baseline methods.


  • Open Access

    Privacy-Preserving Graph Embedding based on Local Differential Privacy

    by Zening Li, Rong-Hua Li, Meihao Liao, Fusheng Jin, Guoren Wang


  • Open Access

    Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee

    by Qiangqiang Dai, Rong-Hua Li, Donghang Cui, Meihao Liao, Yu-Xuan Qiu, Guoren Wang

    A k-biplex is an induced subgraph of a bipartite graph which requires every vertex on the one side disconnecting at most k vertices on the other side. Enumerating all maximal k-biplexes in a bipartite graph is a fundamental operator in bipartite graph analysis and finds applications in various domains, including community detection, online recommendation, and fraud detection in finance networks. The state-of-the-art solutions for maximal k-biplex enumeration suffer from efficiency issues as k increases (k ≥ 2), with the time complexity of O(m 2 n ), where n (m) denotes the number of vertices (edges) in the bipartite graph. To address this issue, we propose two theoretically and practically efficient enumeration algorithms based on novel branching techniques. Specifically, we first devise a new branching rule as a fundamental component. Building upon this, we then develop a novel branch-and-bound enumeration algorithm to efficiently enumerate maximal k-biplexes. We prove that our algorithm achieves a worst-case time complexity of O(mα k n ), where α k < 2, thus significantly improving the time complexity compared to previous algorithms. To enhance the performance, we further propose an improved enumeration algorithm based on a novel pivot-based branching rule. Theoretical analysis reveals that our improved algorithm has a time complexity of O(mβ k n ), where β k is strictly less than α k . In addition, we also present several non-trivial optimization techniques, including graph reduction, upper-bounds based pruning, and ordering-based optimization, to further improve the efficiency of our algorithms. Finally, we conduct extensive experiments on 6 large real-world bipartite graphs to evaluate the efficiency and scalability of the proposed solutions. The results demonstrate that our improved algorithm achieves up to 5 orders of magnitude faster than the state-of-the-art solutions.


  • Open Access

    Efficient and Provable Effective Resistance Computation on Large Graphs: An Index-based Approach

    by Meihao Liao, Junjie Zhou, Rong-Hua Li, Qiangqiang Dai, Hongyang Chen, Guoren Wang

    Effective resistance (ER) is a fundamental metric for measuring node similarities in a graph, and it finds applications in various domains including graph clustering, recommendation systems, link prediction, and graph neural networks. The state-of-the-art algorithm for computing effective resistance relies on a landmark technique, which involves selecting a node that is easy to reach by all the other nodes as a landmark. The performance of this technique heavily depends on the chosen landmark node. However, in many real-life graphs, it is not always possible to find an easily reachable landmark node, which can significantly hinder the algorithm's efficiency. To overcome this problem, we propose a novel multiple landmarks technique which involves selecting a set of landmark nodes V l such that the other nodes in the graph can easily reach any one of a landmark node in V l . Specifically, we first propose several new formulas to compute ER with multiple landmarks, utilizing the concept of Schur complement. These new formulas allow us to pre-compute and maintain several small-sized matrices related to V l as a compact index. With this powerful index technique, we demonstrate that both single-pair and single-source ER queries can be efficiently answered using a newly-developed V l -absorbed random walk sampling or V l -absorbed push technique. Comprehensive theoretical analysis shows that all proposed index-based algorithms achieve provable performance guarantees for both single-pair and single-source ER queries. Extensive experiments on 5 real-life datasets demonstrate the high efficiency of our multiple landmarks-based index techniques. For instance, our algorithms, with a 1.5 GB index size, can be up to 4 orders of magnitude faster than the state-of-the-art algorithms while achieving the same accuracy on a large road network.


  • Open Access

    Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches

    by Meihao Liao, Rong-Hua Li, Qiangqiang Dai, Hongyang Chen, Hongchao Qin, Guoren Wang

    Personalized PageRank (PPR) computation is a fundamental problem in graph analysis. The state-of-the-art algorithms for PPR computation are based on a bidirectional framework which include a deterministic forward push and a Monte Carlo sampling procedure. The Monte Carlo sampling procedure, however, often has a relatively-large variance, thus reducing the performance of the PPR computation algorithms. To overcome this issue, we develop two novel variance-reduced Monte Carlo techniques for PPR computation. Our first technique is to apply power iterations to reduce the variance of the Monte Carlo sampling procedure. We prove that conducting few power iterations can significantly reduce the variance of existing Monte Carlo estimators, only with few additional costs. Moreover, we show that such a simple and novel variance-reduced Monte Carlo technique can achieve comparable estimation accuracy and the same time complexity as the state-of-the-art bidirectional algorithms. Our second technique is a novel progressive sampling method which uses the historical information of former samples to reduce the variance of the Monte Carlo estimator. We develop several novel PPR computation algorithms by integrating both of these variance reduction techniques with two existing Monte Carlo sampling approaches, including random walk sampling and spanning forests sampling. Finally, we conduct extensive experiments on 5 real-life large graphs to evaluate our solutions. The results show that our algorithms can achieve much higher PPR estimation accuracy by using much less time, compared to the state-of-the-art bidirectional algorithms.


  • Open Access

    Hereditary Cohesive Subgraphs Enumeration on Bipartite Graphs: The Power of Pivot-based Approaches

    by Qiangqiang Dai, Rong-Hua Li, Xiaowei Ye, Meihao Liao, Weipeng Zhang, Guoren Wang

    Finding cohesive subgraphs from a bipartite graph is a fundamental operator in bipartite graph analysis. In this paper, we focus on the problem of mining cohesive subgraphs from a bipartite graph that satisfy a hereditary property. Here a cohesive subgraph meets the hereditary property if all of its subgraphs satisfy the same property as itself. We show that several important cohesive subgraph models, such as maximal biclique and maximal k-biplex, satisfy the hereditary property. The problem of enumerating all maximal hereditary subgraphs was known to be NP-hard. To solve this problem, we first propose a novel and general pivot-based enumeration framework to efficiently enumerate all maximal hereditary subgraphs in a bipartite graph. Then, based on our general framework, we develop a new pivot-based algorithm with several pruning techniques to enumerate all maximal bicliques. We prove that the worst-case time complexity of our pivot-based maximal biclique enumeration algorithm is O(m x 2n/2 ) (or O(m\times 1.414^n)) which is near optimal since there exist up to O(2n/2 ) maximal bicliques in a bipartite graph with n vertices and m edges. Moreover, we also show that our algorithm can achieve polynomial-delay time complexity with a slight modification. Third, on the basis of our general framework, we also devise a novel pivot-based algorithm with several non-trivial pruning techniques to enumerate maximal k-biplexes in a bipartite graph. Finally, we conduct extensive experiments using 11 real-world bipartite graphs to evaluate the proposed algorithms. The results show that our pivot-based solutions can achieve one order of magnitude (three orders of magnitude) faster than the state-of-the-art maximal biclique enumeration algorithms (maximal k-biplex enumeration algorithms).