Given a large graph$G$, a subgraph query$Q$finds the set of all subgraphs of$G$that satisfy certain conditions specified by$Q$. Examples of subgraph queries including finding a community containing designated members to organize an event, and subgraph matching. To overcome the weakness of existing graph-parallel systems that underutilize CPU cores when finding subgraphs, our prior system, G-thinker, was proposed that adopts a novel think-like-a-task (TLAT) parallel programming model. However, G-thinker targets offline analytics and cannot support interactive online querying where users continually submit subgraph queries with different query contents. The challenges here are (i) how to maintain fairness that queries are answered in the order that they are received: a later query is processed only if earlier queries cannot saturate the available computation resources; (ii) how to track the progress of active queries (each with many tasks under computation) so that users can be timely notified as soon as a query completes; and (iii) how to maintain memory boundedness and high task concurrency as in G-thinker. In this article, we propose a novel TLAT programming framework, called G-thinkerQ, for answering online subgraph queries. G-thinkerQ inherits the memory boundedness and high task concurrency of G-thinker by organizing the tasks of each query using a “task capsule” structure, and designs a novel task-capsule list is to ensure fairness among queries. A novel lineage-based mechanism is also designed to keep track of when the last task of a query is completed. Parallel counterparts of the state-of-the-art algorithms for 4 recent advanced subgraph queries are implemented on G-thinkerQ to demonstrate its CPU-scalability.

Mining dense subgraphs from a big graph is important in applications such as community (or module) detection in social (or biological) networks. While most dense structures are defined on undirected graphs, recent efforts have generalized these notions to directed graphs. In this demonstration paper, we present DirDense, an interactive tool that makes it easy for end-users to mine dense structures from a big directed graph. DirDense currently supports the mining of maximal (γ1, γ2)-quasi-cliques, maximal (k 1,k 1)-plexes, and the directed densest subgraph. DirDense facilitates parameter tuning for each type of the structure-mining tasks, and provides intuitive interfaces to visualize and examine the dense directed structures. Using real-world data, we showcase how users can mine dense directed structures by parameter tuning in DirDense, and how they can conveniently examine these structures and cascade the mining tasks to find progressively larger dense subgraphs more quickly.

In this demonstration paper, we describe FSM-Explorer, an interactive tool that makes it easier for end-users to mine frequent subgraph patterns from a big graph$G$, and to explore the subgraph instances in$G$that match the patterns. FSM-Explorer not only supports the popular MNI support measure, but also the recently proposed Fraction-Score measure that is more accurate. Its backend engine is built on top of our recently developed T-FSM system that ensures high concurrency, bounded memory consumption, and effective load balancing. Using real-world data, we showcase how users can mine frequent subgraph patterns by parameter tuning in FSM-Explorer, and how they can conveniently examine the many matched instances in$G$one batch at a time to improve productivity.

Finding frequent subgraph patterns in a big graph is an important problem with many applications such as classifying chemical compounds and building indexes to speed up graph queries. Since this problem is NP-hard, some recent parallel systems have been developed to accelerate the mining. However, they often have a huge memory cost, very long running time, suboptimal load balancing, and possibly inaccurate results. In this paper, we propose an efficient system called T-FSM for parallel mining of frequent subgraph patterns in a big graph. T-FSM adopts a novel task-based execution engine design to ensure high concurrency, bounded memory consumption, and effective load balancing. It also supports a new anti-monotonic frequentness measure called Fraction-Score, which is more accurate than the widely used MNI measure. Our experiments show that T-FSM is orders of magnitude faster than SOTA systems for frequent subgraph pattern mining. Our system code has been released at https://github.com/lyuheng/T-FSM.

Accurate and timely mapping of flood extent plays a crucial role in disaster management such as damage assessment and relief activities. In recent years, high-resolution optical imagery becomes increasingly available with the wide deployment of satellites and drones. However, analyzing such imagery data to extract flood extent poses unique challenges due to noises such as obstacles (e.g., tree canopies, clouds). In this paper, we propose an elevation-guided annotation tool for flood extent mapping, which allows annotators to provide the flooded/dry labels for just a few pixels to cover a large area where the labels of most other pixels are automatically inferred. The physical rule we use here to guide the automatic label inference is that if a location is flooded (resp. dry), then its adjacent locations with a lower (resp. higher) elevation must also be flooded (resp. dry). In this way, annotators just need to label the pixels that they are confident with, and the true labels of many ambiguous pixels such as tree-canopy ones can be automatically inferred. We demonstrate the usage of our annotation tool using high-resolution aerial imagery from National Oceanic and Atmospheric Administration (NOAA) National Geodetic Survey (NGS) together with the corresponding Digital Elevation Model (DEM) data. The annotated data can be used to train machine learning models for flood extent mapping, and we train U-Net models to infer the flood map for an unseen region and achieve a high accuracy. Our annotation tool is open-sourced at https://github.com/SaugatAdhikari/Flood-Annotation-Tool.

App-based ride-hailing services, such as Uber and Lyft, have become popular thanks to technology advancements including smartphones and 4G/5G network. However, little is known about to what degree their operations impact urban traffic since Transportation Network Companies seldom share their ride data due to business and user privacy reasons. Recently, transportation engineering researchers began to collect data in large cities trying to understand the transportation impacts of ride-hailing services, so as to assist transport planning and policy making. However, (1) there does not exist a general data collection approach applicable to any city, and (2) the studies were based on historical data and cannot project the future easily even though ride-hailing services are developing quickly.

Quasi-cliques are a type of dense subgraphs that generalize the notion of cliques, important for applications such as community/module detection in various social and biological networks. However, the existing quasi-clique definition and algorithms are only applicable to undirected graphs. In this paper, we generalize the concept of quasi-cliques to directed graphs by proposing (γ1, γ2) -quasi-cliques which have density requirements in both inbound and outbound directions of each vertex in a quasi-clique subgraph. An efficient recursive algorithm is proposed to find maximal (γ1,γ2)-quasi-cliques which integrates many effective pruning rules that are validated by ablation studies. We also study the finding of top-k large quasi-cliques directly by bootstrapping the search from more compact quasi-cliques, to scale the mining to larger networks. The algorithms are parallelized with effective load balancing, and we demonstrate that they can scale up effectively with the number of CPU cores.

Decision trees and tree ensembles are popular supervised learning models on tabular data. Two recent research trends on tree models stand out: (1) bigger and deeper models with many trees, and (2) scalable distributed training frameworks. However, existing implementations on distributed systems are IO-bound leaving CPU cores underutilized. They also only find best node-splitting conditions approximately due to row-based data partitioning scheme. In this paper, we target the exact training of tree models by effectively utilizing the available CPU cores. The resulting system called TreeServer adopts a column-based data partitioning scheme to minimize communication, and a node-centric task-based engine to fully explore the CPU parallelism. Experiments show that TreeServer is up to 10× faster than models in Spark MLlib. We also showcase TreeServer's high training throughput by using it to build big “deep forest” models.

iPSCs are pluripotent stem cells generated from adult tissue through a process called cellular reprogramming. However, cellular reprogramming is a lengthy and inefficient process since only a small fraction of cells can reliably become iPSCs. The reprogramming efficiency is generally measured by counting the number of reprogrammed colonies that emerge and grow as rounded clusters of compact cells around 20 days after adding the reprogramming vectors. However, counting colonies manually is labor-intensive, time-consuming, and error-prone.This work develops a semi-automated tool for colony counting from iPSC culture plate images, where colonies are automatically annotated with their centers. Our model uses multi-task learning to jointly predict the colony centers and conduct colony segmentation, in hope that the latter will improve the performance of the former. An annotation tool is developed to facilitate the collection of ground-truth masks by crowdsourcing. Two center-based loss functions are investigated and compared, one based on oriented Gaussian kernel and the other based on average Hausdorff distance. Extensive experiments verify that (i) the former loss outperforms the latter, (ii) the segmentation head is effective in improving center predictions. Our code has been released at https://github.com/MTSami/iPSC-Colony-Counting.

Micromobility refers to small, lightweight vehicles such as shared bicycles and electric scooters (e-scooters). Recently, shared micromobility services see increasing deployment in urban areas to solve the "last mile´ problem, where the travel distance is considered long when walking on foot, but not worth driving a car (e.g., to avoid parking). A key question to ask when deciding whether to deploy a shared micromobility service in an area is: how much car traffic can be reduced during peak hours if this service is deployed? This work answers this question by agent-based transportation simulation. The key challenge here is to generate a realistic synthetic population of the target area along with their travel day-plans. We propose to use an area-specific travel survey plus openly available data sources for this purpose, and demonstrate our approach through a case study that studied the traffic impacts of deploying dockless e-scooters in Birmingham, AL. A demo of our simulation is available at https://youtu.be/zh_mHQ6ck4U.

Micromobility refers to small, lightweight vehicles such as shared bicycles and electric scooters (e-scooters). Recently, shared micromobility services see increasing deployment in urban areas, especially for trips where the travel distance is considered long for walking, but not worth driving a car (e.g., to avoid parking). A key question to ask when deciding whether to deploy a shared micromobility service in an area is: how much car traffic can be reduced during peak hours if this service is deployed? This work answers this question by agent-based transportation simulation. The key contribution is to generate a realistic synthetic population of transportation users in the target area along with their travel day-plans, using an area-specific travel survey plus openly available data sources. We demonstrate our approach through a case study on the deployment of dockless e-scooters in Birmingham, AL, with a demo at https://youtu.be/zh_mHQ6ck4U.

Given a user-specified minimum degree threshold γ , a γ -quasiclique is a subgraph g = (V g , E g ) where each vertex ν ∈ V g connects to at least γ fraction of the other vertices (i.e., ⌈ γ · (| V g |- 1)⌉ vertices) in g. Quasi-clique is one of the most natural definitions for dense structures useful in finding communities in social networks and discovering significant biomolecule structures and pathways. However, mining maximal quasi-cliques is notoriously expensive. In this paper, we design parallel algorithms for mining maximal quasi-cliques on G-thinker, a distributed graph mining framework that decomposes mining into compute-intensive tasks to fully utilize CPU cores. We found that directly using G-thinker results in the straggler problem due to (i) the drastic load imbalance among different tasks and (ii) the difficulty of predicting the task running time. We address these challenges by redesigning G-thinker's execution engine to prioritize long-running tasks for execution, and by utilizing a novel timeout strategy to effectively decompose long-running tasks to improve load balancing. While this system redesign applies to many other expensive dense subgraph mining problems, this paper verifies the idea by adapting the state-of-the-art quasi-clique algorithm, Quick, to our redesigned G-thinker. Extensive experiments verify that our new solution scales well with the number of CPU cores, achieving 201× runtime speedup when mining a graph with 3.77M vertices and 16.5M edges in a 16-node cluster.

MATSim is the state-of-the-art open source software for agent-based transport simulation, intended for use to evaluate transportation planning models. A standard approach to use MATSim is to conduct a user survey about their day-plans of travel, from which a synthetic dataset of agents' day-plans for an entire region is generated for transport simulation. The simulation output can be used for various evaluations, such as congestion conditions of road segments and their peak hours.This paper aims to conduct a transportation simulation on MATSim for the region of Birmingham, AL. A traditional approach based on Iterative Proportional Fitting (IPF) is not sufficient for generating a realistic synthetic population due to the small data problem: Birmingham is a small city with limited transport data statistics, and we only have a survey of 451 people for their day-plans. To tackle the small data problem, we seek the assistance of abundant open data such as US Census data, OpenStreetMap, OpenAddresses and Birmingham Business}{Alliance to complete the fine details realistically. We also utilize various data science and machine learning techniques to build models that utilize these open data to generate a realistic population. Preliminary tests demonstrate reasonable accuracy of the simulation results.

This poster aims to conduct a transportation simulation on MATSim, the state-of-the-art open source software for agent-based transportation simulation, for the region of Birmingham, AL, where a synthetic population is generated from a survey of 451 people with their day-plans of traveling. To tackle the small data problem, we seek the assistance of abundant open data such as US Census data, OpenStreetMap, OpenAddresses and Birmingham Business Alliance to complete the fine details realistically. We also utilize data science and machine learning techniques as well as iterative proportional fitting to build models that utilize these open data to generate a realistic population. Good accuracy of the simulation is achieved; see https://youtu.be/ZIm0WsmKB4E for a demo.