Xiaowei Ye

Xiaowei Ye

Auto-generated profile, based on publicly available information

Xiaowei Ye

Beijing Institute of Technology, Beijing, China

Research Focus & Metrics

Academic Career Length

4Years (2023-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
26 May 2023 in Proceedings of the ACM on Management of Data
Verified
Journal Article
Open access
XYXiaowei Ye
Xiaowei Ye
RLRonghua Li
Ronghua Li
QDQiangqiang Dai
Qiangqiang Dai
HQHongchao Qin
Hongchao Qin
GWGuoren Wang
Guoren Wang
A (p,q)-biclique is a complete subgraph (X,Y) that |X|=p, |Y|=q. Counting (p,q)-bicliques in bipartite graphs is an important operator for many bipartite graph analysis applications. However, getting the count of (p,q)-bicliques for large p and q (e.g., p,q ≥ 10) is extremely difficult, because the number of (p,q)-bicliques increases exponentially with respect to p and q. The state-of-the-art algorithm for this problem is based on the (p,q)-biclique enumeration technique which is often costly due to the exponential blowup in the enumeration space of (p,q)-bicliques. To overcome this problem, we first propose a novel exact algorithm, called EPivoter, based on a newly-developed edge-pivoting technique. The striking feature of EPivoter is that it can count (p,q)-bicliques for all pairs of (p,q) using a combinatorial technique, instead of exhaustively enumerating all (p,q)-bicliques. Second, we propose a novel dynamic programming (DP) based h-zigzag sampling technique to provably approximate the count of the (p,q)-bicliques for all pairs of (p,q), where an h-zigzag is an ordered simple path in G with length 2h-1 (h = min{p,q}). We show that our DP-based sampling technique is very efficient. Third, to further improve the efficiency, we also propose a hybrid framework that integrates both the exact EPivoter algorithm and sampling-based algorithms. Extensive experiments on 7 real-world graphs show that our algorithms are several orders of magnitude faster than the state-of-the-art algorithm.

13 June 2023 in Proceedings of the ACM on Management of Data
Verified
Journal Article
Open access
QDQiangqiang Dai
Qiangqiang Dai
RLRonghua Li
Ronghua Li
XYXiaowei Ye
Xiaowei Ye
MLMeihao Liao
Meihao Liao
WZWeipeng Zhang
Weipeng Zhang
GWGuoren Wang
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).

24 August 2024
Verified
Conference Paper
Open access
XYXiaowei Ye
Xiaowei Ye
RLRonghua Li
Ronghua Li
LLLei Liang
Lei Liang
ZLZhizhen Liu
Zhizhen Liu
LLLonglong Lin
Longlong Lin
GWGuoren Wang
Guoren Wang
The quest to identify local dense communities closely connected to predetermined seed nodes is vital across numerous applications. Given the seed nodes R, the R-subgraph density of a subgraph S is defined as traditional graph density of S with penalties on the nodes in S / R. The state-of-the-art (SOTA) anchored densest subgraph model, which is based on R-subgraph density, is designed to address the community search problem. However, it often struggles to efficiently uncover truly dense communities. To eliminate this issue, we propose a novel NR-subgraph density metric, a nuanced measure that identifies communities intimately linked to seed nodes and also exhibiting overall high graph density. We redefine the anchored densest subgraph search problem through the lens of NR-subgraph density and cast it as a Linear Programming (LP) problem. This allows us to transition into a dual problem, tapping into the efficiency and effectiveness of convex programming-based iterative algorithm. To solve this redefined problem, we propose two algorithms: FDP, an iterative method that swiftly attains near-optimal solutions, and FDPE, an exact approach that ensures full convergence. We perform extensive experiments on 12 real-world networks. The results show that our proposed algorithms not only outperform the SOTA methods by 3.6~14.1 times in terms of running time, but also produce subgraphs with superior internal quality.

12 September 2023 in IEEE Transactions on Knowledge and Data Engineering
Verified
Journal Article
Closed access
XYXiaowei Ye
Xiaowei Ye
RLRonghua Li
Ronghua Li
QDQiangqiang Dai
Qiangqiang Dai
HCHongzhi Chen
Hongzhi Chen
GWGuoren Wang
Guoren Wang
$K$ -clique counting is a fundamental problem in network analysis which has attracted much attention in recent years. Computing the count of $k$ -cliques in a graph for a large $k$ (e.g., $k=8$ ) is often intractable as the number of $k$ -cliques increases exponentially w.r.t. (with respect to) $k$ . Existing exact $k$ -clique counting algorithms are often hard to handle large dense graphs, while sampling-based solutions either require a huge number of samples or consume very high storage space to achieve a satisfactory accuracy. To overcome these limitations, we propose a new framework to estimate the number of $k$ -cliques which integrates both the exact $k$ -clique counting technique and three novel color-based sampling techniques. The key insight of our framework is that we only apply the exact algorithm to compute the $k$ -clique counts in the sparse regions of a graph, and use the proposed color-based sampling approaches to estimate the number of $k$ -cliques in the dense regions of the graph. Specifically, we develop three novel dynamic programming based $k$ -color set sampling techniques to efficiently estimate the $k$ -clique counts, where a $k$ -color set contains $k$ nodes with $k$ different colors. Since a $k$ -color set is often a good approximation of a $k$ -clique in the dense regions of a graph, our sampling-based solutions are extremely efficient and accurate. Moreover, the proposed sampling techniques are space efficient which use near-linear space w.r.t. graph size. We conduct extensive experiments to evaluate our algorithms using 8 real-life graphs. The results show that our best algorithm is at least one order of magnitude faster than the state-of-the-art sampling-based solutions (with the same relative error 0.1%) and can be up to three orders of magnitude faster than the state-of-the-art exact algorithm on large graphs.

22 September 2025 in Proceedings of the ACM on Management of Data
Verified
Journal Article
Open access
XYXiaowei Ye
Xiaowei Ye
RLRonghua Li
Ronghua Li
GWGuoren Wang
Guoren Wang
Clique enumeration, including maximal clique enumeration and k -clique enumeration, is a fundamental problem in graph analysis. However, existing clique enumeration algorithms often struggle to efficiently handle complex real-world graphs. To address this issue, we propose a novel Core Clique Removal (CCR) technique that removes a large core clique from the original graph. After removing the core clique, the remaining graph is expected to become sparser. We show that the clique enumeration problem on the original graph can be reduced to the problem of enumerating cliques in the remaining sparser graph, thus reducing computational complexity. Building upon the CCR technique, we propose two innovative and efficient algorithms: CCRMCE for maximal clique enumeration and CCRKCE for k -clique enumeration. Both algorithms are non-trivial and offer substantial improvements over previous approaches. Our extensive experiments on 20 real-world graphs highlight the efficiency of our methods. CCRMCE demonstrates multiple times faster performance, while CCRKCE achieves an order of magnitude speedup compared to state-of-the-art algorithms.

22 April 2025
Verified
Conference Paper
Open access
RLRonghua Li
Ronghua Li
XYXiaowei Ye
Xiaowei Ye
FJFusheng Jin
Fusheng Jin
YWYu-Ping Wang
Yu-Ping Wang
Ye YuanYe Yuan
Ye Yuan
GWGuoren Wang
Guoren Wang