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.

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.

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.

Subgraph search problems such as maximal clique enumeration and subgraph matching generate a search-space tree which is traversed in depth-first manner by serial backtracking algorithms that are recursive. Since Jenkins et al. reported the backtracking paradigm to be sub-optimal for GPU acceleration, breadth-first traversal of the search-space tree is widely adopted by GPU algorithms. However, they produce a lot of intermediate subgraphs that exhaust the GPU device memory. Recent works revive the depth-first backtracking paradigm for GPU acceleration, where each warp is a basic processing unit with its own stack in device memory for subgraph backtracking. However, they adopt complicated methods for load balancing that incur a lot of overheads. They also use hardcoded fixed space for stacks that is determined ad-hoc and may lead to inaccuracy when the allocated space is insufficient. In this paper, we use subgraph matching as a case study to propose novel depth-first GPU solutions to address the above problems. Our approach, called T-DFS, decomposes computation into independent tasks that process search-space subtrees, which are managed by an efficient lock-free circular task queue. Tasks are distributed to different warps for parallel processing, and a novel timeout mechanism is used to eliminate straggler tasks to ensure load balancing. We also support flexible and fine-grained dynamic memory allocation for stack spaces to avoid the stack space allocation pitfalls of existing works. Extensive experiments on real graphs show that T-DFS significantly outperforms existing depth-first GPU solutions for the subgraph matching application.

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.

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.

The k-core of a graph is the largest induced sub-graph with minimum degree k. The problem of k-core decomposition finds the k-cores of a graph for all valid values of k, and it has many applications such as network analysis, computational biology and graph visualization. Currently, there are two types of parallel algorithms for k-core decomposition: (1) degree-based vertex peeling, and (2) iterative h-index refinement. There is, however, few studies on accelerating k-core decomposition using GPU. In this paper, we propose a highly optimized peeling algorithm on a GPU, and compare it with possible implementations on top of think-like-a-vertex graph-parallel GPU systems as well as existing serial and parallel k-core decomposition algorithms on CPUs. Extensive experiments show that our GPU algorithm is the overall winner in both time and space. Our source code is released at https://github.com/akhlaqueak/KCoreGPU.