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 and distributed systems have been developed to accelerate the mining. However, they often have a huge memory cost, very long running time, suboptimal load balancing, poor scale-out capability, and possibly inaccurate results. In this article, we propose an efficient system called T-FSM for parallel mining of frequent subgraph patterns in a big graph. T-FSM supports a new anti-monotonic frequentness measure called Fraction-Score, which is more accurate than the widely used MNI measure. The execution engine of T-FSM supports both intra-machine parallelism and inter-machine parallelism. For intra-machine parallelism, T-FSM adopts a novel task-based execution model to ensure high multithreading concurrency, bounded memory consumption, and effective load balancing. For inter-machine parallelism, T-FSM ensures good scale-out performance with a lightweight pattern rebalancing approach that reduces workload skewness of pattern evaluations among machines. To avoid recomputing the contexts for migrated patterns, we design a novel context cache table to support concurrent and asynchronous requesting and caching of remote context data, which can timely evict and garbage collect used pattern contexts that are no longer needed to keep memory consumption bounded. Extensive experiments show that T-FSM is orders of magnitude faster than existing state-of-the-art parallel systems (more than 10×, 51×, 131×, 55× speedup over ScaleMine, DistGraph, Pangolin and Peregrine, respectively) and distributed systems (more than 42× and 88× over ScaleMine and DistGraph, respectively) for frequent subgraph pattern mining, and it scales out satisfactorily to 512 CPU cores on the Polaris supercomputer at Argonne National Laboratory.

Accurate and prompt mapping of flood extent is important for effective disaster management. Prior terrain-guided methods utilizing digital elevation model (DEM) data to improve segmentation quality, but are only applicable to small areas with restricted assumptions. We propose ZoneGraph, a scalable flood mapping approach that is generally applicable to any area. Since water level varies a lot from upstream to downstream, and an Earth image may contain multiple river channels or branches, ZoneGraph partitions an Earth image into localized zones each with a consistent water level for intra-region inference using hidden Markov trees (HMTs), and uses a zone adjacency graph for inter-zone regularization to enforce flow direction consistency across adjacent zones. Parallelization techniques are applied to speed up the zonal water level computations. Experiments show ZoneGraph achieves higher accuracy than existing methods, scale to a large area with 24,805 × 40,129 pixels, and yields up to 14.3× parallelization speedup on 32 threads.

Flood extent mapping on Earth imagery is crucial for disaster response and damage assessment. To train a machine learning model for flood map segmentation, the first step is to annotate flood maps on Earth imagery with a high quality. Enabled by USGS's 3D Elevation Program (3DEP), it is now possible to visualize Earth imagery in a 3D terrain view, which enables more intuitive annotation. Terrain also encodes the physical knowledge that a pixel (i.e., location) with an elevation lower (resp. higher) than its adjacent pixel that is clearly flooded (resp. dry) must also be flooded (resp. dry), which provides additional opportunities such as automated label derivation and terrain-guided active learning. We will demonstrate, ALFA, an interactive active-learning-based annotation tool to minimize the annotators' efforts when preparing the ground-truth flood map on Earth imagery. ALFA calibrates the prediction consistency of a segmentation model (1) across training cycles and (2) for various data augmentations, which are integrated into the design of both the acquisition function and the loss function to enhance the robustness of active learning. ALFA recommends those superpixels that the underlying model is most uncertain about, and users can annotate their pixels with minimal clicks with the help of elevation guidance. ALFA is open-sourced at https://github.com/saugatadhikari/alfa.

Numerous geo-foundation models have been pre-trained recently on plentiful unlabeled Earth imagery datasets by self-supervised learning, and they have been demonstrated to enhance performance in downstream supervised geospatial tasks such as flood extent mapping. However, these approaches generally ignore the terrain data that are readily available in the format of digital elevation model (DEM) from sources such as USGS's 3D Elevation Program (3DEP). On the other hand, a few works have shown that elevation guidance can improve the performance of flood extent mapping on conventional models trained from scratch. This is intuitive since in natural disaster events such as flooding, landslide and avalanche, the floodwater, loose earth or snow moves downhill.

A k -plex is a dense subgraph structure where every vertex can be disconnected with at most k vertices. Finding a maximum k -plex (M k P) in a big graph is a key primitive in many real applications such as community detection and biological network analysis. A lot of M k P algorithms have been actively proposed in recent years in top AI and DB conferences, featuring a broad range of sophisticated pruning techniques. In this paper, we study the various pruning techniques from nine recent M k P algorithms including kPlexT, Maple, Seesaw, DiseMKP, kPlexS, KpLeX, Maplex, BnB and BS by unifying them in a common framework called V-M k P. We summarize their proposed techniques into three categories, those for (1) branching, (2) upper bounding, and (3) reduction during subgraph exploration. We find that different pruning techniques can have drastically different performance impacts, but there exists a configuration of the techniques dependent on k that leads to the best performance in vast majority of the time. Interestingly, extensive experiments with our unified framework reveal that some techniques are not effective as claimed in the original works, and we also discover an unmentioned technique that is actually the major performance booster when k > 5. We also study problem variants such as finding all the M k Ps and finding the densest M k P (i.e., with the most edges) to cover community diversity, and effective algorithm parallelization. Our source code is released at https://github.com/akhlaqueak/MKP-Study.

Graph-theoretic algorithms and graph machine learning models are essential tools for addressing many real-life problems, such as social network analysis and bioinformatics. To support large-scale graph analytics, graph-parallel systems have been actively developed for over one decade, such as Google's Pregel and Spark's GraphX, which (i) promote a think-like-a-vertex computing model and target (ii) iterative algorithms and (iii) those problems that output a value for each vertex. However, this model is too restricted for supporting the rich set of heterogeneous operations for graph analytics and machine learning that many real applications demand. In recent years, two new trends emerge in graph-parallel systems research: (1) a novel think-like-a-task computing model that can efficiently support the various computationally expensive problems of subgraph search; and (2) scalable systems for learning graph neural networks. These systems effectively complement the diversity needs of graph-parallel tools that can flexibly work together in a comprehensive graph processing pipeline for real applications, with the capability of capturing structural features. This tutorial will provide an effective categorization of the recent systems in these two directions based on their computing models and adopted techniques, and will review the key design ideas of these systems. Slides are available at https://github.com/akhlaqueak/VLDB-2025-Tutorial.

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.

Graph-theoretic algorithms and graph machine learning models are essential tools for addressing many real-life problems, such as social network analysis and bioinformatics. To support large-scale graph analytics, graph-parallel systems have been actively developed for over one decade, such as Google's Pregel and Spark's GraphX, which (i) promote a think-like-a-vertex computing model and target (ii) iterative algorithms and (iii) those problems that output a value for each vertex. However, this model is too restricted for supporting the rich set of heterogeneous operations for graph analytics and machine learning that many real applications demand.

Climate change has led to a sharp increase in the number and severity of extreme events, such as floods, tornados and wildfires. These events have resulted in adverse effects on human lives and the infrastructure. Swift disaster assessment is crucial for the effective planning of disaster response and relief efforts. AI and big data have provided unprecedented opportunities to enable swift disaster assessment, but two significant hurdles exist: (1) the scarcity of annotated geospatial data to train AI models, and (2) the lack of AI solutions that encode physics knowledge in a geospatial context. My research aims to address both challenges by developing an active-learning-based annotation platform that improves the annotation productivity of geospatial data for geospatial machine learning, and by developing physics-guided machine learning models for accurate natural disaster assessment.

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 all those subgraphs of a big graph that satisfy certain conditions (aka. subgraph finding) is useful in many applications such as community detection and subgraph matching. These problems often generate a search-space tree with size exponential to the size of the input graph. GPUs with thousands of cores are a natural choice to speed up subgraph finding, but existing GPU solutions either conduct BFS on the search-space tree which leads to memory overflow due to intermediate subgraph-size explosion, or they conduct DFS on the search-space tree which is memory-efficient but can be 2 orders of magnitude slower than a BFS solution. In this paper, we present$\mathbf{G}^{2}$-AIMD, a subgraph-centric framework for efficient subgraph Search on GPUs, which enjoys the efficiency of BFS on the search-space tree, while avoids intermediate subgraph-size explosion with novel system designs such as adaptive chunk-size adjustment and host-memory subgraph buffering, inspired by the additive-increase/multiplicative-decrease (AIMD) algorithm in TCP congestion control.$\mathrm{G}^{2}$-AIMD provides a convenient subgraph-centric programming interface to facilitate the implementation of subgraph finding algorithms on top, so as to enjoy the above performance merits.$\mathbf{G}^{2}{-}$AIMD also supports multi-GPU execution where each GPU only needs to load a fraction of the input graph. To demonstrate the efficiency and scalability of$\mathbf{G}^{2}$-AIMD, two algorithms were implemented on top with additional optimization techniques, and they significantly outperform the existing GPU solutions.

Flood inundation mapping from Earth imagery plays a vital role in rapid disaster response and national water forecasting. However, the problem is non-trivial due to significant imagery noise and obstacles, complex spatial dependency on 3D terrains, spatial non-stationarity, and high computational cost. Existing machine learning approaches are mostly terrain-unaware and are prone to produce spurious results due to imagery noise and obstacles, requiring significant efforts in post-processing. Recently, several terrain- aware methods were proposed that incorporate complex spatial dependency (e.g., water flow directions on 3D terrains) but they assume that the inferred flood surface level is spatially stationary, making them insufficient for a large heterogeneous geographic area. To address these limitations, this paper proposes a novel spatial learning framework called hidden Markov forest, which decomposes a large heterogeneous area into local stationary zones, represents spatial dependency on 3D terrains via zonal trees (forest), and jointly infers the class map in different zonal trees with spatial regularization. We design efficient inference algorithms based on dynamic programming and multi-resolution filtering. Evaluations on real-world datasets show that our method outperforms baselines and our proposed computational refinement significantly reduces the time cost.

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.