Jessica Shi

Jessica Shi

Auto-generated profile, based on publicly available information

Jessica Shi

MIT CSAIL, Cambridge, MA, USA

Research Focus & Metrics

Academic Career Length

9Years (2018-Present)

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

Representative Publications

View All Publications
21 October 2022 in ACM Journal of Experimental Algorithmics
Verified
Journal Article
Open access
JSJessica Shi
Jessica Shi
LHLouisa Ruixue Huang
Louisa Ruixue Huang
JSJulian Shun
Julian Shun
Counting the frequency of subgraphs in large networks is a classic research question that reveals the underlying substructures of these networks for important applications. However, subgraph counting is a challenging problem, even for subgraph sizes as small as five, due to the combinatorial explosion in the number of possible occurrences. This article focuses on the five-cycle, which is an important special case of five-vertex subgraph counting and one of the most difficult to count efficiently. We design two new parallel five-cycle counting algorithms and prove that they are work efficient and achieve polylogarithmic span. Both algorithms are based on computing low out-degree orientations, which enables the efficient computation of directed two-paths and three-paths, and the algorithms differ in the ways in which they use this orientation to eliminate double-counting. Additionally, we present new parallel algorithms for obtaining unbiased estimates of five-cycle counts using graph sparsification. We develop fast multicore implementations of the algorithms and propose a work scheduling optimization to improve their performance. Our experiments on a variety of real-world graphs using a 36-core machine with two-way hyper-threading show that our best exact parallel algorithm achieves 10–46× self-relative speedup, outperforms our serial benchmarks by 10–32×, and outperforms the previous state-of-the-art serial algorithm by up to 818×. Our best approximate algorithm, for a reasonable probability parameter, achieves up to 20× self-relative speedup and is able to approximate five-cycle counts 9–189× faster than our best exact algorithm, with between 0.52% and 11.77% error.

12 March 2024 in Proceedings of the ACM on Management of Data
Verified
Journal Article
Open access
JSJessica Shi
Jessica Shi
LDLaxman Dhulipala
Laxman Dhulipala
JSJulian Shun
Julian Shun
Nucleus decompositions have been shown to be a useful tool for finding dense subgraphs. The coreness value of a clique represents its density based on the number of other cliques it is adjacent to. One useful output of nucleus decomposition is to generate a hierarchy among dense subgraphs at different resolutions. However, existing parallel algorithms for nucleus decomposition do not generate this hierarchy, and only compute the coreness values. This paper presents a scalable parallel algorithm for hierarchy construction, with practical optimizations, such as interleaving the coreness computation with hierarchy construction and using a concurrent union-find data structure in an innovative way to generate the hierarchy. We also introduce a parallel approximation algorithm for nucleus decomposition, which achieves much lower span in theory and better performance in practice. We prove strong theoretical bounds on the work and span (parallel time) of our algorithms. On a 30-core machine with two-way hyper-threading, our parallel hierarchy construction algorithm achieves up to a 58.84x speedup over the state-of-the-art sequential hierarchy construction algorithm by Sariyuce et al. and up to a 30.96x self-relative parallel speedup. On the same machine, our approximation algorithm achieves a 3.3x speedup over our exact algorithm, while generating coreness estimates with a multiplicative error of 1.33x on average.

18 July 2023
Verified
Conference Paper
Open access
JSJessica Shi
Jessica Shi
LDLaxman Dhulipala
Laxman Dhulipala
JSJulian Shun
Julian Shun
Discovering dense substructures in graphs is a fundamental topic in graph mining, and has been studied across many areas including computational biology, spam and fraud-detection, and large-scale network analysis. Recently, Sariyuce et al. introduced the nucleus decomposition problem, which generalizes the influential notions of k-cores and k-trusses to k-(r,s) nucleii, and can better capture higher-order structures. Informally, a k-(r,s) nucleus is the maximal induced subgraph such that every r-clique in the subgraph is contained in at least k s-cliques. The goal of the (r, s) nucleus decomposition problem is to identify for each r-clique in the graph, the largest k such that it is in a k-(r,s) nucleus. Solving the (r, s) nucleus decomposition problem is a significant computational challenge for several reasons. First, simply counting and enumerating s-cliques is a challenging task, even for modest s. Second, storing information for all r-cliques can require a large amount of space, even for relatively small graphs. Third, engineering fast and high-performance solutions to this problem requires taking advantage of parallelism due to the computationally-intensive nature of listing cliques. There are two well-known parallel paradigms for approaching the (r, s) nucleus decomposition problem, a global peeling-based model and a local update model that iterates until convergence. The former is inherently challenging to parallelize due to sequential dependencies and necessary synchronization steps, which we address in this paper, and we demonstrate that the latter requires orders of magnitude more work to converge to the same solution and is thus less performant.

2 January 2018
Verified
Conference Paper
Closed access
JLJérémie Lumbroso
Jérémie Lumbroso
JSJessica Shi
Jessica Shi
In this paper, building on previous work by Nakano et al. [23], we develop an alternate technique which almost automatically translates (existing) vertex incremental characterizations of graph classes into asymptotics of that class. Specifically, we construct trees corresponding to the sequences of vertex incremental operations which characterize a graph class, and then use analytic combinatorics to enumerate the trees, giving an upper bound on the graph class. This technique is applicable to a wider set of graph classes compared to the tree decompositions, and we show that this technique produces accurate upper bounds. We first validate our method by applying it to the case of distance-hereditary graphs, and comparing the bound obtained by our method with that obtained by Nakano et al. [23], and the exact enumeration obtained by Chauve et al. [7, 8]. We then illustrate its use by applying it to switch cographs, for which there are few known results: our method provide a bound of ∼6.301n, to be compared with the precise exponential growth, ∼6.159n, which we obtained independently through the relationship between switch cographs and bicolored cographs, first introduced by Hertz [19]. We believe the popularity of vertex incremental characterizations might mean this may prove a fairly convenient to tool for future exploration of graph classes.