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.

The goal of the 24 th International Workshop on Data Mining in Bioinformatics (BIOKDD 2025) is to encourage KDD researchers to solve the numerous problems and challenges in Bioinformatics using Data Mining technologies.Based on the organizers' expertise and communities, BIOKDD 2025 features the theme "Generative AI in Biomolecular Designs".This theme encourages using large language models to design and optimize proteins or other biomolecules such as compounds, natural products, and RNAs with generative AI techniques.We also welcome broader research applying data mining to address biomedical problems.The key goal is to accelerate the convergence between Data Mining and Bioinformatics communities to expedite discoveries in basic biology, medicine and healthcare.

Given a graph pair (G 1 , G 2 ), graph edit distance (GED) is defined as the minimum number of edit operations converting G 1 to G 2 . GED is a fundamental operation widely used in many applications, but its exact computation is NP-hard, so the approximation of GED has gained a lot of attention. Data-driven learning-based methods have been found to provide superior results compared to classical approximate algorithms, but they directly fit the coupling relationship between a pair of vertices from their vertex features. We argue that while pairwise vertex features can capture the coupling cost (discrepancy) of a pair of vertices, the vertex coupling matrix should be derived from the vertex-pair cost matrix through a more well-established method that is aware of the global context of the graph pair, such as optimal transport. In this paper, we propose an ensemble approach that integrates a supervised learning-based method and an unsupervised method, both based on optimal transport. Our learning method, GEDIOT, is based on inverse optimal transport that leverages a learnable Sinkhorn algorithm to generate the coupling matrix. Our unsupervised method, GEDGW, models GED computation as a linear combination of optimal transport and its variant, Gromov-Wasserstein discrepancy, for node and edge operations, respectively, which can be solved efficiently without needing the ground truth. Our ensemble method, GEDHOT, combines GEDIOT and GEDGW to further boost the performance. Extensive experiments demonstrate that our methods significantly outperform the existing methods in terms of the performance of GED computation, edit path generation, and model generalizability.

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.

Explaining black-box models is fundamental to gaining trust and deploying these models in real applications. As existing explanation methods have been shown to lack robustness against adversarial perturbations, there has been a growing interest in generating robust explanations. However, existing works resort to empirical defense strategies and these heuristic methods fail against powerful adversaries. In this paper, we certify the robustness of explanations motivated by the success of randomized smoothing. Specifically, we compute a tight radius in which the robustness of the explanation is certified. While a challenge is how to formulate the robustness of the explanation mathematically, we quantize the explanation into discrete spaces to mimic classification in randomized smoothing. To address the high computational cost of randomized smoothing, we introduce randomized gradient smoothing. Also, we explore the robustness of the semantic explanation by certifying the robustness of capsules. In the experiment, we demonstrate the effectiveness of our method on benchmark datasets from the perspectives of post-hoc explanation and semantic explanation respectively. Our work is a promising step towards filling the gap between the theoretical robustness bound and empirical explanations. Our code has been released at https://github.com/NKUShaw/CertifiedExplanation.

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.

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.

The goal of the 22 nd International Workshop on Data Mining in Bioinformatics (BIOKDD 2023) is to encourage KDD researchers to solve the numerous problems and challenges in Bioinformatics using Data Mining technologies.Based on the organizers' expertise and communities, BIOKDD 2023 features the theme "Large-Scale Data-Driven Methods for Bioinformatics".This theme encourages the use of high-performance computing (HPC) to support the training of large machine learning models for problems in Bioinformatics and Computational Biology.The key goal is to accelerate the convergence between Data Mining and Bioinformatics communities to expedite discoveries in basic biology, medicine and healthcare.The goal of the 23 rd International Workshop on Data Mining in Bioinformatics (BIOKDD 2024) is to encourage KDD researchers to solve the numerous problems and challenges in Bioinformatics using Data Mining technologies.Based on the organizers' expertise and communities, BIOKDD 2024 features the theme "Advancing Bioinformatics with LLMs and GenAI".This theme encourages the use of large language models and generative artificial intelligence to solve problems in Bioinformatics and Computational Biology.The key goal is to accelerate the convergence between Data Mining and Bioinformatics communities to expedite discoveries in basic biology, medicine and healthcare.

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.

Co-location patterns, which capture the phenomenon that objects with certain labels are often located in close geographic proximity, are defined based on a support measure which quantifies the prevalence of a pattern candidate in the form of a label set. Existing support measures share the idea of counting the number of instances of a given label set$C$as its support, where an instance of$C$is an object set whose objects collectively carry all labels in$C$and are located close to one another. However, they suffer from various weaknesses, e.g., fail to capture all possible instances, or overlook the cases when multiple instances overlap. In this paper, we propose a new measure called Fraction-Score which counts instancesfractionallyif they overlap. Fraction-Score captures all possible instances, and handles the cases where instances overlap appropriately (so that the supports defined are more meaningful and anti-monotonic). We develop efficient algorithms to solve the co-location pattern mining problem defined with Fraction-Score. Furthermore, to obtain representative patterns, we develop an efficient algorithm for mining the maximal co-location patterns, which are those patterns without proper superset patterns. We conduct extensive experiments using real and synthetic datasets, which verified the superiority of our proposals.

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.

As the popularity of graph data increases, there is a growing need to count the occurrences of subgraph patterns of interest, for a variety of applications. Many graphs are massive in scale and also fully dynamic (with insertions and deletions of edges), rendering exact computation of these counts to be infeasible. Common practice is, instead, to use a small set of edges as a sample to estimate the counts. Existing sampling algorithms for fully dynamic graphs sample the edges with uniform probability. In this paper, we show that we can do much better if we sample edges based on their individual properties. Specifically, we propose a weighted sampling algorithm called WSD for estimating the subgraph count in a fully dynamic graph stream, which samples the edges based on their weights that indicate their importance and reflect their properties. We determine the weights of edges in a data-driven fashion, using a novel method based on reinforcement learning. We conduct extensive experiments to verify that our technique can produce estimates with smaller errors while often running faster compared with existing algorithms.

The goal of the 22nd International Workshop on Data Mining in Bioinformatics (BIOKDD 2023) is to encourage KDD researchers to solve the numerous problems and challenges in Bioinformatics using Data Mining technologies. Based on the organizers' expertise and communities, BIOKDD 2023 features the theme ''Large-Scale Data-Driven Methods for Bioinformatics.'' This theme encourages the use of high-performance computing (HPC) to support the training of large machine learning models for problems in Bioinformatics and Computational Biology. The key goal is to accelerate the convergence between Data Mining and Bioinformatics communities to expedite discoveries in basic biology, medicine and healthcare.

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.

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.

Context has been recognized as an important factor to consider in personalized recommender systems. Particularly in location-based services (LBSs), a fundamental task is to recommend to a mobile user where he/she could be interested to visit next at the right time. Additionally, location-based social networks (LBSNs) allow users to share location-embedded information with friends who often co-occur in the same or nearby points-of-interest (POIs) or share similar POI visiting histories, due to the social homophily theory and Tobler's first law of geography. So, both the time information and LBSN friendship relations should be utilized for POI recommendation. Tensor completion has recently gained some attention in time-aware recommender systems. The problem decomposes a user-item-time tensor into low-rank embedding matrices of users, items and times using its observed entries, so that the underlying low-rank subspace structure can be tracked to fill the missing entries for time-aware recommendation. However, these tensor completion methods ignore the social-spatial context information available in LBSNs, which is important for POI recommendation since people tend to share their preferences with their friends, and near things are more related than distant things. In this paper, we utilize the side information of social networks and POI locations to enhance the tensor completion model paradigm for more effective time-aware POI recommendation. Specifically, we propose a regularization loss head based on a novel social Hausdorff distance function to optimize the reconstructed tensor. We also quantify the popularity of different POIs with location entropy to prevent very popular POIs from being over-represented hence suppressing the appearance of other more diverse POIs. To address the sensitivity of negative sampling, we train the model on the whole data by treating all unlabeled entries in the observed tensor as negative, and rewriting the loss function in a smart way to reduce the computational cost. Through extensive experiments on real datasets, we demonstrate the superiority of our model over state-of-the-art tensor completion methods.

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.

Recent studies on federated learning (FL) have sought to solve the system heterogeneity issue by designing customized local models for different clients. However, public dataset introduction, sensitive information exchange, non-trivial computational cost, or particular architecture requirement limit the applicability of most of them in real scenarios. This paper presents a novel federated fingerprint learning model for making full use of the computing power of each client with the customized local models for improving the FL convergence, while keeping the data and sensitive information safe and local. First, we decompose the parameters of each local model into two types of parameters: rigid ones that have fixed model architecture for ensuring the convergence of global model training and elastic ones that contain customized model structure and size for allowing to make full use of the computing power of each client based on individual data scale. Second, we adopt the standard FL scheme to update and aggregate the local rigid parameters. We introduce a Gaussian distribution as auxiliary input and output K local fingerprints respectively for the elastic parameters of all K local models. The server aggregates K local fingerprints into a global one and sends it back to the clients. A fingerprint-based aggregation strategy makes the local models indirectly receive the aggregated elastic parameters through the aggregation of K local fingerprints while fixing data locally. Last but not least, we design a parameter masking method to mask the rigid parameters irrelevant to the local classification task in the local models. We develop a parameter separation method to guarantee that the combination of unmasked rigid parameters in all local models are able to cover all the rigid parameters as many as possible, for further raising the utilization rate of each rigid parameter.

Depression is one of the leading factors in global disability and a top driver for suicides. Studies have shown that depression has an effect on language usage. In recent years, especially during the COVID pandemic, social media platforms have become the de facto platform for many individuals to self-disclose or discuss mental health issues like depression. This trend presents a unique opportunity for researchers and healthcare professionals to detect potential mental illnesses for early intervention or treatment by taking advantage of the recent advances in machine learning approaches. Existing depression detection methods on social media, however, suffer from two major limitations. First, these solutions heavily rely on the amount, quality, and type of user-posted content. Second, the overlooked social circle impact should be leveraged to enhance the prediction capabilities. In this paper, we propose a depression detection framework, MentalNet, based on heterogeneous graph convolution by capturing users’ interactions (replies, mentions, and quotetiveets) with their friends on social media and differentiating the intimacy of users’ social circles (e.g., family, friends, or acquaintances). Specifically, we formulate the problem of depression detection on social media as a graph classification problem by representing users’ social circles in the format of heterogeneous graphs. MentalNet embraces three modules, (1) extraction of ego-network node features, (2) construction of user interaction graphs, and (3) depression detection based on heterogeneous graph classification. The extensive experiments on Twitter data demonstrate that MentalNet consistently and significantly outperforms the state-of-the-art methods in terms of all the effectiveness metrics. Compared to the baseline methods, MentalNet is able to effectively predict early depression in Twitter users with up to 24% improvement on F1 score.

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.

The goal of the 21th International Workshop on Data Mining in Bioinformatics (BIOKDD 2022) is to encourage KDD researchers to solve the numerous problems and challenges in Bioinformatics using Data Mining technologies. Based on the organizers' expertise and communities, BIOKDD 2022 features 2 closely related themes "Biomedical Ontologies" and "Biological Data Visualization". These themes encourage the knowledge graph community and the data visualization community to work together to solve the many challenging problems in Bioinformatics with new perspectives. The key goal is to accelerate the convergence between Data Mining and Bioinformatics communities to expedite discoveries in basic biology, medicine and healthcare.

Given raster imagery features and imperfect vector training labels with registration uncertainty, this paper studies a deep learning framework that can quantify and reduce the registration uncertainty of training labels as well as train neural network parameters simultaneously. The problem is important in broad applications such as streamline classification on Earth imagery or tissue segmentation on medical imagery, whereby annotating precise vector labels is expensive and time-consuming. However, the problem is challenging due to the gap between the vector representation of class labels and the raster representation of image features and the need for training neural networks with uncertain label locations. Existing research on uncertain training labels often focuses on uncertainty in label class semantics or characterizes label registration uncertainty at the pixel level (not contiguous vectors). To fill the gap, this paper proposes a novel learning framework that explicitly quantifies vector labels' registration uncertainty. We propose a registration-uncertainty-aware loss function and design an iterative uncertainty reduction algorithm by re-estimating the posterior of true vector label locations distribution based on a Gaussian process. Evaluations on real-world datasets in National Hydrography Dataset refinement show that the proposed approach significantly outperforms several baselines in the registration uncertainty estimations performance and classification performance.

Mining maximal subgraphs with cohesive structures from a bipartite graph has been widely studied. One important cohesive structure on bipartite graphs is k-biplex, where each vertex on one side disconnects at most k vertices on the other side. In this paper, we study the maximal k-biplex enumeration problem which enumerates all maximal k-biplexes. Existing methods suffer from efficiency and/or scalability issues and have the time of waiting for the next output exponential w.r.t. the size of the input bipartite graph (i.e., an exponential delay). In this paper, we adopt a reverse search framework called bTraversal, which corresponds to a depth-first search (DFS) procedure on an implicit solution graph on top of all maximal k-biplexes. We then develop a series of techniques for improving and implementing this framework including (1) carefully selecting an initial solution to start DFS, (2) pruning the vast majority of links from the solution graph of bTraversal, and (3) implementing abstract procedures of the framework. The resulting algorithm is called iTraversal, which has its underlying solution graph significantly sparser than (around 0.1% of) that of bTraversal. Besides, iTraversal provides a guarantee of polynomial delay. Our experimental results on real and synthetic graphs, where the largest one contains one billion edges, show that our algorithm is up to four orders of magnitude faster than existing algorithms.

Given earth imagery with spectral features on a terrain surface, this paper studies surface segmentation based on both explanatory features and surface topology. The problem is important in many spatial and spatiotemporal applications such as flood extent mapping in hydrology. The problem is uniquely challenging for several reasons: first, the size of earth imagery on a terrain surface is often much larger than the input of popular deep convolutional neural networks; second, there exists topological structure dependency between pixel classes on the surface, and such dependency can follow an unknown and non-linear distribution; third, there are often limited training labels. Existing methods for earth imagery segmentation often divide the imagery into patches and consider the elevation as an additional feature channel. These methods do not fully incorporate the spatial topological structural constraint within and across surface patches and thus often show poor results, especially when training labels are limited. Existing methods on semi-supervised and unsupervised learning for earth imagery often focus on learning representation without explicitly incorporating surface topology. In contrast, we propose a novel framework that explicitly models the topological skeleton of a terrain surface with a contour tree from computational topology, which is guided by the physical constraint (e.g., water flow direction on terrains). Our framework consists of two neural networks: a convolutional neural network (CNN) to learn spatial contextual features on a 2D image grid, and a graph neural network (GNN) to learn the statistical distribution of physics-guided spatial topological dependency on the contour tree. The two models are co-trained via variational EM. Evaluations on the real-world flood mapping datasets show that the proposed models outperform baseline methods in classification accuracy, especially when training labels are limited.

Network alignment, which aims at learning a matching between the same entities across multiple information networks, often suffers challenges from feature inconsistency, high-dimensional features, to unstable alignment results. This article presents a novel network alignment framework, Unsupervised Adversarial learning based Network Alignment(UANA), that combines generative adversarial network (GAN) and reinforcement learning (RL) techniques to tackle the above critical challenges. First, we propose a bidirectional adversarial network distribution matching model to perform the bidirectional cross-network alignment translations between two networks, such that the distributions of real and translated networks completely overlap together. In addition, two cross-network alignment translation cycles are constructed for training the unsupervised alignment without the need of prior alignment knowledge. Second, in order to address the feature inconsistency issue, we integrate a dual adversarial autoencoder module with an adversarial binary classification model together to project two copies of the same vertices with high-dimensional inconsistent features into the same low-dimensional embedding space. This facilitates the translations of the distributions of two networks in the adversarial network distribution matching model. Finally, we develop an RL based optimization approach to solve the vertex matching problem in the discrete space of the GAN model, i.e., directly select the vertices in target networks most relevant to the vertices in source networks, without unstable similarity computation that is sensitive to discriminative features and similarity metrics. Extensive evaluation on real-world graph datasets demonstrates the outstanding capability of UANA to address the unsupervised network alignment problem, in terms of both effectiveness and scalability.

Given a data matrix \( D \) , a submatrix \( S \) of \( D \) is an order-preserving submatrix (OPSM) if there is a permutation of the columns of \( S \) , under which the entry values of each row in \( S \) are strictly increasing. OPSM mining is widely used in real-life applications such as identifying coexpressed genes and finding customers with similar preference. However, noise is ubiquitous in real data matrices due to variable experimental conditions and measurement errors, which makes conventional OPSM mining algorithms inapplicable. No previous work on OPSM has ever considered uncertain value intervals using the well-established possible world semantics. We establish two different definitions of significant OPSMs based on thepossible world semantics: (1) expected support-based and (2) probabilistic frequentness-based. An optimized dynamic programming approach is proposed to compute the probability that a row supports a particular column permutation, with a closed-form formula derived to efficiently handle the special case of uniform value distribution and an accurate cubic spline approximation approach that works well with any uncertain value distributions. To efficiently check the probabilistic frequentness, several effective pruning rules are designed to efficiently prune insignificant OPSMs; two approximation techniques based on the Poisson and Gaussian distributions, respectively, are proposed for further speedup. These techniques are integrated into our two OPSM mining algorithms, based on prefix-projection and Apriori, respectively. We further parallelize our prefix-projection-based mining algorithm using PrefixFPM, a recently proposed framework for parallel frequent pattern mining, and we achieve a good speedup with the number of CPU cores. Extensive experiments on real microarray data demonstrate that the OPSMs found by our algorithms have a much higher quality than those found by existing approaches.

Fast diagnostic prediction of brain dysfunctions such as autism spectrum disorder (ASD), attention deficit hyperactivity disorder (ADHD) and Alzheimer’s disease is important due to their prevalence in the population. A typical workflow for brain dysfunction prediction is to preprocess a brain image into a network of connected brain regions, where indicative features are extracted using simple linear or convolutional models to be used for prediction. However, due to restrictions on patient data sharing such as HIPAA rules, the number of training samples is often very limited. Even with efforts like the ABIDE initiative that aggregated brain imaging data from laboratories around the world, the subject number merely reaches around 1,000, limiting the effectiveness of data-driven models such as deep learning models.To overcome this data scarcity problem, we propose a GAN-based data augmentation technique to generate realistic brain region networks, which are used to increase the size of an existing training set so that a brain dysfunction classifier can be better trained to achieve a higher prediction accuracy. In the brain region network setting, we propose a generator that considers each brain region as an embedding, so that the connectivity between two regions can be computed using the inner product of their embeddings. This generator is trained along with a phenotype-enhanced BrainNetCNN, a domain-specific discriminator (i.e., classifier), to improve its prediction accuracy. Our embedding-based generator generates samples following the original data feature distribution (i.e., age, gender, and health condition), which improves generator quality and avoids mode collapse.Our design is generally applicable to various neuroimaging data, and experimental results obtained on two real datasets ABIDE-I and ADHD200 confirmed the effectiveness of the proposed method. Our model has been open-sourced on GitHub at https://github.com/binwsh/GAN-for-Neural-Graph.

Matrix completion is a well-known approach for recommender systems. It predicts the values of the missing entries in a sparse user-item interaction matrix, based on the low-rank structure of the rating matrix. However, existing matrix completion methods do not take node polysemy and side information of social relationships into consideration, which can otherwise further improve the performance. In this paper, we propose a novel matrix completion method that employs both users’ friendships and rating entries to predict the missing values in a user-item matrix. Our approach adopts a graph-based modeling where nodes are users and items, and two types of edges are considered: user friendships and user-item interactions. Polysemy-aware node features are extracted from this heterogeneous graph through a graph convolution network by considering the multifaceted factors for edge formation, which are then connected to a hybrid loss function with two heads: (1) a social-homophily head to address node polysemy, and (2) an error head for user-item rating regression. The latter is formulated on all matrix entries to combat the sensitivity of negative sampling of the vast majority of missing entries during training, with a smart technique to reduce the time complexity. Extensive experiments over real datasets verify that our model outperforms the state-of-the-art matrix completion methods by a significant margin.

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.

Various industries use towers as part of their daily operations, such as transmission towers (aka. electricity pylons), telecommunications towers and water towers. These towers re- quire regular maintenance, and before the maintenance work can be done, a preliminary survey must be conducted to determine where to work. More and more, such surveys are being conducted via drones. This work develops a detection model to help locate tower issues from the video frames of drones. However, it does not provide satisfactory performance to directly train such an object detection model with the annotated problem locations from domain experts. Therefore, we propose to improve the quality of the extracted image features with the help of another separate task which detects the various parts that are involved in the tower issues, such as bolts, nuts, washers and pins, the annotations of which can be done without the need of domain expertise. Through this multi-task learning scheme, we improved the problem detection recall from 59.6% to 71.5%, providing much more effective recommendations of potential issues for inspectors to examine further. Also, the average number of problem detections in each image is merely 5.54 so inspectors are not overwhelmed by the recommended locations.

While depression is rated as the most important leading factor to global disability, early detection of depression is a non-trivial task. Existing depression detection mechanisms harvesting social media data suffer from two major limitations. First, existing solutions rely heavily on the amount, quality, and variety of content types (textual, visual, etc.) posted by users to make accurate inferences, therefore suffering from the cold-start problem when coping with users with limited training data (e.g., most existing works exclude users with fewer than 25 tweets). Second, existing approaches ignore the social impact or indication from users' social circles that can be leveraged to enhance the inference results. In this paper, we present MentalSpot, a social-contagion based depression early-screening framework using meta-learning. Specifically, we first construct a social-contagion driven data repository PsycheNet, filling the void of social-circle based depression datasets. We design a triplet network to extract users' embeddings based on the similarities of the linguistic features extracted from written texts. Afterwards, for each target user, we employ dynamic mean shift pruning to select her top-k homogeneous friends in the metric space, the texts written by whom will then be leveraged to train a friend based depression detection model. Extensive experiments show that MentalSpot outperforms the state of the art in terms of all effectiveness metrics, especially for users with very few tweets. Specifically, by using only five tweets per user, MentalSpot successfully yields an F1 score that would otherwise be achieved by the state-of-the-art methods requiring at least twenty tweets. Our approach represents a step forward to address the cold-start problem that deep learning techniques struggle with for their applications in psychiatric diagnosis. The principal beneficiaries of this study are healthcare professionals in medical institutions to determine timely and targeted interventions in a clinical setting. This study also supports non-profit groups in reaching out to people with mental health issues, helping in a global health task that cannot be fully covered by clinicians.

Knowing the locations of tweets can benefit a wide variety of applications such as venue recommendation, event detection, and monitoring disaster outbreaks. However, the problem of fine-grained tweet geolocation prediction is challenging since tweets are short and therefore may not contain any geo-indicative words or may contain ambiguous, noisy information. Existing solutions either yield an unsatisfactory accuracy in practical applications or make predictions that even experts struggle to interpret, failing to engender sufficient trust and actionability for real-world deployment. Our paper presents a tweet geolocation prediction framework, EDGE (Entity-Diffusion Gaussian Ensemble), which delivers predictions that are both accurate and highly interpretable without requiring any additional contextual information such as user profile and location history. In EDGE, we cast the geolocation problem as a neutral network optimization problem by learning probabilistic generative models. Compared with existing works, EDGE has two distinctive features: (1) the inference builds on mining the correlation between non geo-indicative entities and geo-indicative entities by diffusing their semantic embeddings over the constructed graph neural network (Entity Diffusion) and (2) each prediction result is represented as a Gaussian mixture instead of specific geographical coordinates (Gaussian Ensemble). Extensive experiments using real-world tweet datasets validate the superiority of EDGE over the state of the art in terms of all distance-based and POI-based metrics.

Real-time traffic prediction is essential for mitigating traffic congestion and reducing travel time. Recent advancement in graph convolutional network (GCN) has motivated a series of GCN-based models for traffic forecasting on an urban road network. However, these graph-based methods cannot capture the intricate dependencies of consecutive road segments such as no left turn, and dynamic spatial dependency. In this paper, we propose Trajectory WaveNet, or T-wave in short, a traffic forecasting model that utilizes the actual vehicle trajectories to capture the above intricate dependencies to improve prediction performance. Both trajectories and traffic data are obtained from the floating car data collected by ridesharing companies such as DiDi. T-wave treats vehicle trajectories as first-class citizens, and applies dilated causal convolutions along both the temporal dimension (i.e., recent, daily-periodic and weekly-periodic historical traffic data) and the spatial dimension (i.e., trajectories). For effective training, a trajectory mini-batch sampling technique is devised considering both spatial and temporal proximity. Extensive experiments on real datasets show that T-wave consistently bests the state-of-the-art models.

This paper studies weakly supervised learning on spatial raster data based on imperfect vector training labels. Given raster feature imagery and imperfect (weak) vector labels with location registration errors, our goal is to learn a deep learning model for pixel classification and refine vector labels simultaneously. The problem is important in many geoscience applications such as streamline delineation and road mapping from earth imagery, where annotating imperfect coarse vector labels is far more efficient than drawing precise labels. But the problem is challenging due to the misalignment of vector labels with raster feature pixels and the need to infer true vector label location while learning neural network parameters. Existing works on weakly supervised learning often focus on noise and errors in label semantics, assuming label locations to be either correct or irrelevant (e.g., identical and independently distributed). A few works exist on label registration errors, but these methods often focus on label misalignment on object segment boundaries at the pixel level without guaranteeing vector continuity. To fill the gap, this paper proposes a spatial learning framework based on Expectation-Maximization that iteratively updates deep neural network parameters while inferring true vector label locations. Specifically, inference of true vector locations is based on both the current pixel class predictions and the geometric properties of vectors. Evaluations on real-world high-resolution remote sensing datasets in National Hydrography Dataset (NHD) refinement show that the proposed framework outperforms baseline methods in classification accuracy and refined vector quality.

The goal of the 20th International Workshop on Data Mining in Bioinformatics (BIOKDD 2021) is to encourage KDD researchers to tackle the numerous problems and challenges in Bioinformatics using Data Mining technologies. Based on the organizers' expertise and the BIOKDD communities, BIOKDD 2021 features the theme of "Artificial Intelligence in Medicine". This topic focuses on the use of machine learning and data mining techniques for the analysis of large amounts of heterogeneous, complex, biological and medical data, with a particular focus on deep learning methods that have seen rapid advance and wider adoption in Bioinformatics (e.g., DeepVariant, AlphaFold 2). We also particularly welcome COVID-19 related research. The key goal is to accelerate the convergence between Data Mining and Bioinformatics communities to expedite discoveries in basic biology, medicine and healthcare.

Ridesharing companies such as Ube and DiDi provide ride-hailing services where passengers and drivers are matched via mobile apps. As a result, large amounts of vehicle trajectories and vehicle speed data are collected that can be used for traffic prediction. The recent popularity of graph convolutional networks (GCNs) has opened up new possibilities for real-time traffic prediction and many GCN-based models have been proposed to capture the spatial correlation on the urban road network. However, the graph-based approaches fail to capture the intricate dependencies of consecutive road segments that are well captured by trajectories.

Given a 3D surface defined by an elevation function on a 2D grid as well as non-spatial features observed at each pixel, the problem of surface segmentation aims to classify pixels into contiguous classes based on both non-spatial features and surface topology.The problem has important applications in hydrology, planetary science, and biochemistry but is uniquely challenging for several reasons.First, the spatial extent of class segments follows surface contours in the topological space, regardless of their spatial shapes and directions.Second, the topological structure exists in multiple spatial scales based on different surface resolutions.Existing widely successful deep learning models for image segmentation are often not applicable due to their reliance on convolution and pooling operations to learn regular structural patterns on a grid.In contrast, we propose to represent surface topological structure by a contour tree skeleton, which is a polytree capturing the evolution of surface contours at different elevation levels.We further design a graph neural network based on the contour tree hierarchy to model surface topological structure at different spatial scales.Experimental evaluations based on real-world hydrological datasets show that our model outperforms several baseline methods in classification accuracy.

Stock investment is a vehicle for many people to grow their wealth. However, market downturns can cause huge losses and need to be predicted for a timely sell. In fact, with effective prediction, stocks are a good investment even during periods of market volatility as many stocks are "on sale".News is an important source of signal for stock price movement. However, stock analysts usually adjust their analysis according to the news in a subject manner, and wrong judgments can cause investors huge losses.Twitter is a great source for breaking news, and provides a timely stream of signals on stock trends. News on Twitter also tends to have a great impact on the market due to the large number of Twitter users. This paper proposes a data-driven pipeline to timely incorporate Twitter news about a company into a time series prediction model on the company's stock price. Our approach, called BERT-LSTM (BELT), extracts informative features on stock price direction from Twitter news using the state-of-the-art natural language processing (NLP) model BERT, which are then used as covariates to a many-to-many stacked LSTM model that also utilizes historical stock prices to predict the direction of future stock price. Utilizing a carefully curated stock news dataset, we fine-tune BERT to effectively identify those news tweets that are relevant, and to extract NLP features that are indicative of price rises and falls. All model parameters are trained end-to-end to provide a data-driven and objective pipeline to incorporate news signals so as to avoid subjective analysis. Extensive experiments on real stock prices and Twitter news show that BELT is able to predict stock prices more accurately utilizing news information than if historical price data are used alone for prediction, and beats StockNet which is the current state of the art for news-based stock movement prediction.

Network alignment techniques, which aim to identify the same entities across multiple networks, often suffer challenges from feature inconsistency to transitivity law preservation. This paper presents a purely unsupervised network alignment method, KEMINA, with three original contributions. First, in order to address the feature inconsistency issue, an adversarial kernel embedding technique is proposed to extract network-invariant information among multiple networks without prior alignment knowledge, and project them into the common embedding space. Second, a multinomial generative adversarial network (GAN) model is developed to train multiple network alignment tasks simultaneously in an unsupervised manner with preserving the transitivity law property. Third but last, a variational inference model is designed to alleviate the data sparsity and inadequate training issues by filling realistic detail for vertices with sparse features and generating real-looking supplementary vertex samples within limited training opportunity of each pair of source and target networks.

The availability of high-frequency trade data has made it possible for the intraday forecast of price patterns. With the help of technical indicators, recent studies have shown that LSTM based deep learning models are able to predict price directions (a binary classification problem) with performance better than a random guess. However, only naive recurrent networks were adopted, and these works did not compare with the tools used by finance practitioners. Our experiments show that GARCH beats their LSTM models by a large margin.

With the rapid progress of global urbanization and function division among different geographical regions, it is of urgent need to develop methods that can find regions of desired future function distributions in applications. For example, a company tends to open a new branch in a region where the growth trend of industrial sectors fits its strategic goals, or is similar to that of an existing company location; while a job hunter tends to search regions where his/her expertise aligns with the industrial growth trend providing sufficient job opportunities to sustain future employment and job-hopping.

Mining from a big graph those subgraphs that satisfy certain conditions is useful in many applications such as community detection and subgraph matching. These problems have a high time complexity, but existing systems to scale them are all IO-bound in execution. We propose the first truly CPU-bound distributed framework called G-thinker that adopts a user-friendly subgraph-centric vertex-pulling API for writing distributed subgraph mining algorithms. To utilize all CPU cores of a cluster, G-thinker features (1) a highly-concurrent vertex cache for parallel task access and (2) a lightweight task scheduling approach that ensures high task throughput. These designs well overlap communication with computation to minimize the CPU idle time. Extensive experiments demonstrate that G-thinker achieves orders of magnitude speedup compared even with the fastest existing subgraph-centric system, and it scales well to much larger and denser real network data. G-thinker is open-sourced at http://bit.ly/gthinker with detailed documentation.

Frequent pattern mining (FPM) has been a focused theme in data mining research for decades, but there lacks a general programming framework that can be easily customized to mine different kinds of frequent patterns, and existing solutions to FPM over big transaction databases are IO-bound rendering CPU cores underutilized even though FPM is NP-hard. This paper presents, PrefixFPM, a general-purpose framework for FPM that is able to fully utilize the CPU cores in a multicore machine. PrefixFPM follows the idea of prefix projection to partition the workloads of PFM into independent tasks by divide and conquer. PrefixFPM exposes a unified programming interface to users who can customize it to mine their desired patterns, and the parallel execution engine is transparent to end-users and can be reused for mining all kinds of patterns. We have adapted the state-of-the-art serial algorithms for mining frequent patterns including subsequences, subtrees, and subgraphs on top of PrefixFPM, and extensive experiments demonstrate an excellent speedup ratio of PrefixFPM with the number of cores. A demo is available at https://youtu.be/PfioC0GDpsw; the code is available at https://github.com/yanlab19870714/PrefixFPM.

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.

Precipitation nowcasting, which predicts rainfall intensity in the near future, has been studied by meteorologists for decades. Currently, computer vision techniques, especially optical flow based methods, are widely adopted by observatories since they deliver reasonable performance without the need of model training. However, their performance is highly sensitive to model parameters which require a lot of empirical knowledge to optimize. With the recent success of deep learning (DL), machine learning researchers have started to explore the use of spatiotemporal DL models for precipitation nowcasting, which have demonstrated a better performance than optical flow based methods. However, DL models are not easy to conFigure for nonDL experts such as meteorologists. In this poster, we introduce EasyRain, a platform with a user-friendly web interface to help users without domain knowledge (in DL and/or meteorology) to efficiently build DL and optical flow based models. We will demonstrate the efficiency and usability of EasyRain for training, tuning, and comparing precipitation nowcasting models.

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.

Co-location patterns are well-established on spatial objects with categorical labels, which capture the phenomenon that objects with certain labels are often located in close geographic proximity. Similar to frequent itemsets, co-location patterns are defined based on a support measure which quantifies the popularity (or prevalence) of a pattern candidate (a label set). Quite a few support measures exist for defining co-location patterns and they share an idea of counting the number of instances of a given label set C as its support, where an instance of C is an object set whose objects carry all the labels in C and are located close to one another. Unfortunately, these measures suffer from various weaknesses, e.g., some fail to capture all possible instances while some others overlook the cases when multiple instances overlap. In this paper, we propose a new measure called Fraction-Score whose idea is to count instances fractionally if they overlap. Compared to existing measures, Fraction-Score not only captures all possible instances, but also handles the cases where instances overlap appropriately (so that the supports defined are more meaningful and consistent with the desirable anti-monotonicity property). To solve the co-location pattern mining problem based on Fraction-Score, we develop efficient algorithms which are significantly faster than a baseline that adapts the state-of-the-art. We conduct extensive experiments using both real and synthetic datasets, which verified the superiority of Fraction-Score and also the efficiency of our developed algorithms.

Given a data matrix D, a submatrix S of D is an order-preserving submatrix (OPSM) if there is a permutation of the columns of S, under which the entry values of each row in S are strictly increasing. OPSM mining is widely used in real-life applications such as identifying coexpressed genes, and finding customers with similar preference. However, noise is ubiquitous in real data matrices due to variable experimental conditions and measurement errors, which makes conventional OPSM mining algorithms inapplicable. No previous work has ever combated uncertain value intervals using the possible world semantics. We establish two different definitions of significant OPSMs based on the possible world semantics: (1) expected support based and (2) probabilistic frequentness based. An optimized dynamic programming approach is proposed to compute the probability that a row supports a particular column permutation, and several effective pruning rules are introduced to efficiently prune insignificant OPSMs. These techniques are integrated into our two OPSM mining algorithms, based on prefix-projection and Apriori respectively. Extensive experiments on real microarray data demonstrate that the OPSMs found by our algorithms have a much higher quality than those found by existing approaches.

De novo genome assembly is the process of stitching short DNA sequences to generate longer DNA sequences, without using any reference sequence for alignment. It enables high-throughput genome sequencing and thus accelerates the discovery of new genomes. In this paper, we present a toolkit, called PPA-assembler, for de novo genome assembly in a distributed setting. PPA-assembler adopts the popular de Bruijn graph based approach, and the operations run on Google's Pregel framework with strong performance guarantees. PPA-assembler demonstrates superior performance compared with existing assemblers, and is open-sourced at https://github.com/yaobaiwei/PPAAssembler. The full version of this paper can be found at https://arxiv.org/abs/1801.04453.

Many graphs in real-world applications, such as telecommunications networks, social-interaction graphs and co-authorship graphs, contain temporal information. However, existing graph mining algorithms fail to exploit these temporal information and the resulting subgraph patterns do not contain any temporal attribute. In this paper, we study the problem of mining a set of diversified temporal subgraph patterns from a temporal graph, where each subgraph is associated with the time interval that the pattern spans. This problem motivates important applications such as finding social trends in social networks, or detecting temporal hotspots in telecommunications networks. We propose a divide-and-conquer algorithm along with effective pruning techniques, and our approach runs 2 to 3 orders of magnitude faster than a baseline algorithm and obtains high-quality temporal subgraph patterns in real temporal graphs.

In recent years we have witnessed a surging interest in developing Big Graph processing systems. To date, tens of Big Graph systems have been proposed. This tutorial provides a timely and comprehensive review of existing Big Graph systems, and summarizes their pros and cons from various perspectives. We start from the existing vertex-centric systems, which which a programmer thinks intuitively like a vertex when developing parallel graph algorithms. We then introduce systems that adopt other computation paradigms and execution settings. The topics covered in this tutorial include programming models and algorithm design, computation models, communication mechanisms, out-of-core support, fault tolerance, dynamic graph support, and so on. We also highlight future research opportunities on Big Graph analytics.

Inspired by Google's Pregel, many distributed graph processing systems have been developed recently to process big graphs. These systems expose a vertex-centric programming interface to users, where a programmer thinks like a vertex when designing parallel graph algorithms. However, existing systems are designed for tasks where most vertices in a graph participate in the computation, and they are not suitable for processing light-workload graph queries which only access a small portion of vertices. This is because their programming model can seriously under-utilize the resources in a cluster for processing graph queries. In this demonstration, we introduce a general-purpose system for querying big graphs, called Quegel, which treats queries as first-class citizens in the design of its computing model. Quegel adopts a novel superstep-sharing execution model to overcome the weaknesses of existing systems. We demonstrate it is user-friendly to write parallel graph-querying programs with Quegel's interface; and we also show that Quegel is able to achieve real-time response time in various applications, including the two applications that we plan to demonstrate: point-to-point shortest-path queries and XML keyword search.

Pioneered by Google's Pregel, many distributed systems have been developed for large-scale graph analytics. These systems employ a user-friendly "think like a vertex" programming model, and exhibit good scalability for tasks where the majority of graph vertices participate in computation. However, the design of these systems can seriously under-utilize the resources in a cluster for processing light-workload graph queries, where only a small fraction of vertices need to be accessed. In this work, we develop a new open-source system, called Quegel , for querying big graphs. Quegel treats queries as first-class citizens in its design: users only need to specify the Pregel-like algorithm for a generic query, and Quegel processes light-workload graph queries on demand, using a novel superstep-sharing execution model to effectively utilize the cluster resources. Quegel further provides a convenient interface for constructing graph indexes, which significantly improve query performance but are not supported by existing graph-parallel systems. Our experiments verified that Quegel is highly efficient in answering various types of graph queries and is up to orders of magnitude faster than existing systems.

Core decomposition has been applied widely in the visualization and analysis of massive networks. However, existing studies of core decomposition were only limited to non-temporal graphs, while many real-world graphs can be naturally modeled as temporal graphs (e.g., the interaction between users at different time in online social networks, the phone call or messaging records between friends over time, etc.). In this paper, we define the problem of core decomposition in a temporal graph, propose efficient distributed algorithms to compute the cores in massive temporal graphs, and discuss how the technique can be used in temporal graph analysis.

Massive graphs, such as online social networks and communication networks, have become common today. To efficiently analyze such large graphs, many distributed graph computing systems have been developed. These systems employ the "think like a vertex" programming paradigm, where a program proceeds in iterations and at each iteration, vertices exchange messages with each other. However, using Pregel's simple message passing mechanism, some vertices may send/receive significantly more messages than others due to either the high degree of these vertices or the logic of the algorithm used. This forms the communication bottleneck and leads to imbalanced workload among machines in the cluster. In this paper, we propose two effective message reduction techniques: (1)vertex mirroring with message combining, and (2)an additional request-respond API. These techniques not only reduce the total number of messages exchanged through the network, but also bound the number of messages sent/received by any single vertex. We theoretically analyze the effectiveness of our techniques, and implement them on top of our open-source Pregel implementation called Pregel+. Our experiments on various large real graphs demonstrate that our message reduction techniques significantly improve the performance of distributed graph computation.

The convex hull of a set of two-dimensional points, P, is the minimal convex polygon that contains all the points in P. Convex hull is important in many applications such as GIS, statistical analysis and data mining. Due to the ubiquity of data uncertainty such as location uncertainty in real-world applications, we study the concept of convex hull over uncertain data in 2D space. We propose the Probabilistic Convex Hull(PCH) query and demonstrate its applications, such as Flickr landscape photo extraction and activity region visualization, where location uncertainty is incurred by GPS devices or sensors. To tackle the problem of possible world explosion, we develop an O(N3) algorithm based on geometric properties, where N is the data size. We further improve this algorithm with spatial indices and effective pruning techniques, which prune the majority of data instances. To achieve better time complexity, we propose another O(N2log N) algorithm, by maintaining a probability oracle in the form of a circular array with nice properties. Finally, to support applications that require fast response, we develop a Gibbs-sampling-based approximation algorithm which efficiently finds the PCH with high accuracy. Extensive experiments are conducted to verify the efficiency of our algorithms for answering PCH queries.

With the prevalence of graph data in real-world applications (e.g., social networks, mobile phone networks, web graphs, etc.) and their ever-increasing size, many distributed graph computing systems have been developed in recent years to process and analyze massive graphs. Most of these systems adopt Pregel's vertex-centric computing model, while various techniques have been proposed to address the limitations in the Pregel framework. However, there is a lack of comprehensive comparative analysis to evaluate the performance of various systems and their techniques, making it difficult for users to choose the best system for their applications. We conduct extensive experiments to evaluate the performance of existing systems on graphs with different characteristics and on algorithms with different design logic. We also study the effectiveness of various techniques adopted in existing systems, and the scalability of the systems. The results of our study reveal the strengths and limitations of existing systems, and provide valuable insights for users, researchers and system developers.

The rapid growth in the volume of many real-world graphs (e.g., social networks, web graphs, and spatial networks) has led to the development of various vertex-centric distributed graph computing systems in recent years. However, real-world graphs from different domains have very different characteristics, which often create bottlenecks in vertex-centric parallel graph computation. We identify three such important characteristics from a wide spectrum of real-world graphs, namely (1)skewed degree distribution, (2)large diameter, and (3)(relatively) high density. Among them, only (1) has been studied by existing systems, but many real-world power-law graphs also exhibit the characteristics of (2) and (3). In this paper, we propose a block-centric framework, called Blogel, which naturally handles all the three adverse graph characteristics. Blogel programmers may think like a block and develop efficient algorithms for various graph problems. We propose parallel algorithms to partition an arbitrary graph into blocks efficiently, and block-centric programs are then run over these blocks. Our experiments on large real-world graphs verified that Blogel is able to achieve orders of magnitude performance improvements over the state-of-the-art distributed graph computing systems.

Graphs in real life applications are often huge, such as the Web graph and various social networks. These massive graphs are often stored and processed in distributed sites. In this paper, we study graph algorithms that adopt Google's Pregel, an iterative vertex-centric framework for graph processing in the Cloud. We first identify a set of desirable properties of an efficient Pregel algorithm, such as linear space, communication and computation cost per iteration, and logarithmic number of iterations. We define such an algorithm as a practical Pregel algorithm (PPA). We then propose PPAs for computing connected components (CCs), biconnected components (BCCs) and strongly connected components (SCCs). The PPAs for computing BCCs and SCCs use the PPAs of many fundamental graph problems as building blocks, which are of interest by themselves. Extensive experiments over large real graphs verified the efficiency of our algorithms.

Data uncertainty is inherent in many real-world applications such as environmental surveillance and mobile tracking. Mining sequential patterns from inaccurate data, such as those data arising from sensor readings and GPS trajectories, is important for discovering hidden knowledge in such applications. In this paper, we propose to measure pattern frequentness based on the possible world semantics. We establish two uncertain sequence data models abstracted from many real-life applications involving uncertain sequence data, and formulate the problem of mining probabilistically frequent sequential patterns (or p-FSPs) from data that conform to our models. However, the number of possible worlds is extremely large, which makes the mining prohibitively expensive. Inspired by the famous PrefixSpan algorithm, we develop two new algorithms, collectively called U-PrefixSpan, for p-FSP mining. U-PrefixSpan effectively avoids the problem of “possible worlds explosion”, and when combined with our four pruning and validating methods, achieves even better performance. We also propose a fast validating method to further speed up our U-PrefixSpan algorithm. The efficiency and effectiveness of U-PrefixSpan are verified through extensive experiments on both real and synthetic datasets.

Given two sets of points, S and T, in a road network, G, a distance-preserving subgraph (DPS) query returns a subgraph of G that preserves the shortest path from any point in S to any point in T. DPS queries are important in many real world applications, such as route recommendation systems, logistics planning, and all kinds of shortest-path-related applications that run on resource-limited mobile devices. In this paper, we study efficient algorithms for processing DPS queries in large road networks. Four algorithms are proposed with different tradeoffs in terms of DPS quality and query processing time, and the best one is a graph-partitioning based index, called RoadPart, that finds a high quality DPS with short response time. Extensive experiments on large road networks demonstrate the merits of our algorithms, and verify the efficiency of RoadPart for finding a high-quality DPS.

Crowd selection is essential to crowd sourcing applications, since choosing the right workers with particular expertise to carry out crowdsourced tasks is extremely important. The central problem is simple but tricky: given a crowdsourced task, who are the most knowledgable users to ask? In this demo, we show our framework that tackles the problem of crowdsourced task assignment on Twitter according to the social activities of its users. Since user profiles on Twitter do not reveal user interests and skills, we transfer the knowledge from categorized Yahoo! Answers datasets for learning user expertise. Then, we select the right crowd for certain tasks based on user expertise. We study the effectiveness of our system using extensive user evaluation. We further engage the attendees to participate a game called--Whom to Ask on Twitter?. This helps understand our ideas in an interactive manner. Our crowd selection can be accessed by the following url http://webproject2.cse.ust.hk:8034/tcrowd/.

RFID (radio frequency identification) technology has been widely used for object tracking in many real-life applications, such as inventory monitoring and product flow tracking. These applications usually rely on passive RFID technologies rather than active ones, since passive RFID tags are more attractive than active ones in many aspects, such as lower tag cost and simpler maintenance.

Finding reverse nearest neighbors (RNNs) is an important operation in spatial databases. The problem of evaluating RNN queries has already received considerable attention due to its importance in many real-world applications, such as resource allocation and disaster response. While RNN query processing has been extensively studied in Euclidean space, no work ever studies this problem on land surfaces. However, practical applications of RNN queries involve terrain surfaces that constrain object movements, which rendering the existing algorithms inapplicable.

Data uncertainty is inherent in many real-world applications such as environmental surveillance and mobile tracking. As a result, mining sequential patterns from inaccurate data, such as sensor readings and GPS trajectories, is important for discovering hidden knowledge in such applications. Previous work uses expected support as the measurement of pattern frequentness, which has inherent weaknesses with respect to the underlying probability model, and is therefore ineffective for mining high-quality sequential patterns from uncertain sequence databases.

Uncertain data is inherently important in a lot of real-world applications, such as environmental surveillance and mobile tracking. Probabilistic convex hull is very useful for discovering the territory of imprecise data in such applications with a high confidence. In order to deal with this, we propose and study probabilistic convex hull queries based on the possible world semantics, which are able to retrieve the objects whose probability of being on the convex hull is at least α. The demonstration is based on animal tracking whose GPS coordinate is no longer considered to be precise due to device limitation or privacy issues. We demonstrate two interesting results from studying the migration habit of one specific species and the correlation between species through probabilistic convex hull queries.

Given a set S of servers and a set C of clients, an optimal-location query returns a location where a new server can attract the greatest number of clients. Optimal-location queries are important in a lot of real-life applications, such as mobile service planning or resource distribution in an area. Previous studies assume that a client always visits its nearest server, which is too strict to be true in reality. In this paper, we relax this assumption and propose a new model to tackle this problem. We further generalize the problem to finding top-k optimal locations. The main challenge is that, even the fastest approach in existing studies needs to take hours to answer an optimal-location query on a typical real world dataset, which significantly limits the applications of the query. Using our relaxed model, we design an efficient grid-based approximation algorithm called FILM (Fast Influential Location Miner) to the queries, which is orders of magnitude faster than the best-known previous work and the number of clients attracted by a new server in the result location often exceeds 98% of the optimal. The algorithm is extended to finding k influential locations. Extensive experiments are conducted to show the efficiency and effectiveness of FILM on both real and synthetic datasets.