Deep learning has made remarkable progress in medical image analysis, yet its black-box nature still limits interpretability and clinician trust. Concept-based modeling offers a promising direction for explainable AI by integrating human-understandable concepts. However, existing approaches typically rely on global concept annotations and infer diagnosis based solely on the presence or absence of individual concepts. This oversimplified paradigm ignores the rich relationships among concepts and their causal influence on disease outcomes. To overcome these limitations, we propose the Concept Relationship Embedding Model (CREM) for interpretable medical diagnosis. CREM mirrors coarse-to-fine clinical reasoning by first extracting fine-grained subregional concepts, then explicitly encoding their relationships as a concept interaction graph, and finally performing causal inference between concepts and diagnoses to enable reliable and transparent diagnostic predictions. We evaluate CREM on four public medical imaging benchmarks, where it achieves state-of-the-art performance on both concept recognition and disease classification tasks, while exhibiting improved robustness, label efficiency, and interpretability. Furthermore, we deploy CREM as an interactive web-based demo that allows clinicians to visualize concept activations, trace diagnostic reasoning paths, and iteratively refine concept cues, facilitating effective human-in-the-loop decision-making.

Knowledge Tracing (KT) aims to predict learners' future responses by modeling historical learning sequences. However, existing works often overlook the severe disruptions in temporal and interaction continuity arising from large time intervals between interactions, which leads to significant prediction errors. Therefore, we identify and validate thisbreakpointeffect through empirical studies, and try to address it via data augmentation (DA). Existing DA methods usually emphasize sequence diversity or similarity while neglecting the breakpoint effect in KT. Hence, we strive to enhance knowledge tracing via breakpoint-aware sequence augmentation and propose Collaborative Learning Path Augmentation (CLPA), a systematic three-phase method to enhance models' representational capacity and alleviate the breakpoint effects. First, identifying boundary interaction pairs that exhibit the temporal gap and response inconsistency. Second, leveraging cross-sequence collaborative information to infer functional pseudo-paths between identified boundaries. Third, reconstructing and inserting pseudo-learning paths into target sequences to restore sequence continuity; moreover, two refinements of the sampling quantity constraint and the distance-based sampling strategy are proposed to ensure augmentation quality. Comprehensive experiments on four real-world datasets validate the effectiveness of CLPA, which significantly enhances the target KT model's representational capacity and alleviates the breakpoint effects.

Graph pattern queries (GPQ) over RDF graphs extend basic graph patterns to support variable-length paths (VLP), thereby enabling complex knowledge retrieval and navigation. Generally, variable-length paths describe the reachability between two vertices via a given property within a specified range. With the increasing scale of RDF graphs, it is necessary to design a partitioning method to achieve efficient distributed queries. Although many partitioning strategies have been proposed for large RDF graphs, most existing methods result in numerous inter-partition joins when processing GPQs, which impacts query performance. In this paper, we formulate a new partitioning problem, MaxLocJoin, aims to minimize inter-partition joins during distributed GPQ processing. For MaxLocJoin, we propose a partitioning framework (PIP) based on property-induced subgraphs, which consist of edges with a specific set of properties. The framework first finds a locally joinable property set using a cost-driven algorithm, LJPS, where the cost depends on the sizes of weakly connected components within its property-induced subgraphs. Subsequently, the graph is partitioned according to the weakly connected components. The framework can achieve two key objectives: first, it enables complete local processing of all variable-length path queries (eliminating inter-partition joins); second, it can minimize the number of inter-partition joins required for traditional graph pattern queries. Moreover, we identify two types of independently executable queries (IEQ): the locally joinable IEQ and the single-property IEQ. After that, a query decomposition algorithm is designed to transform all GPQ into one of them for independent execution in distributed environments. In experiments, we implement two prototype systems based on Jena and Virtuoso, and evaluate them over both real and synthetic RDF graphs. The results show that MaxLocJoin achieves performance improvements from 2.8x to 10.7x over existing methods.

Spatial crowdsourcing (SC) is becoming increasingly popular recently. As a critical issue in SC, task assignment currently faces challenges due to the imbalanced spatiotemporal distribution of tasks. Hence, many related studies and applications focusing on cross-platform task allocation in SC have emerged. Existing work primarily focuses on the maximization of total revenue for inner platform in cross task assignment. In this work, we formulate a SC problem called Cross Dynamic Task Assignment (CDTA) to maximize the overall utility and propose improved solutions aiming at creating a win-win situation for inner platform, task requesters, and outer workers. We first design a hybrid batch processing framework and a novel cross-platform incentive mechanism. Then, with the purpose of allocating tasks to both inner and outer workers, we present a KM-based algorithm that gets the accurate assignment result in each batch and a density-aware greedy algorithm with high efficiency. To maximize the revenue of inner platform and outer workers simultaneously, we model the competition among outer workers as a potential game that is shown to have at least one pure Nash equilibrium and develop a game-theoretic method. Additionally, a simulated annealing-based improved algorithm is proposed to avoid falling into local optima. Last but not least, since random thresholds lead to unstable results when picking tasks that are preferentially assigned to inner workers, we devise an adaptive threshold selection algorithm based on multi-armed bandit to further improve the overall utility. Extensive experiments demonstrate the effectiveness and efficiency of our proposed algorithms on both real and synthetic datasets.

Graph-structured data appears in domains such as molecular analysis, social networks, and program optimization, where graphs often exhibit implicit heterogeneity, as nodes may look homogeneous in type yet differ significantly in semantics or functionality. Graph Neural Networks (GNNs), while powerful on homophilic graphs, tend to degrade in such settings due to polarity confusion, over-smoothing, and inefficiency caused by dense propagation. We propose a polarity-aware framework for graph classification that addresses these challenges through adaptive directional sparse aggregation. The framework introduces a polarity-aware propagation mechanism that adaptively reinforces or inverts neighbor signals, mitigating contamination under heterophily. A polarity-guided sparse aggregation operator further alleviates over-smoothing, improves scalability by constraining redundant connections, and condenses information flow into more effective representations, while maintaining unbiased estimation with controlled variance. We provide theoretical analyses that characterize the computational complexity, stability properties, and expressive behavior of signed directional aggregation, offering theoretical insights into its computational, stability, and expressive properties. Extensive experiments on molecular and social graph benchmarks with implicit heterophily demonstrate consistent improvements in graph classification accuracy and efficiency. Our method achieves a 2.36% improvement when compared with the strongest baseline on each dataset. In addition, it improves accuracy by 4.53% on average on program optimization strategy recognition tasks, reaching 80.12% overall.

In-memory dynamic graph processing faces three critical challenges: limited DRAM capacity, inefficient concurrent update/query handling, and vulnerability to crashes. Traditional segment-level systems struggle with write amplification on emerging Storage-Class Memory (SCM), while existing persistent-memory systems suffer from coarse-grained synchronization and high recovery overhead. This study presents the Storage-Class Memory Dynamic Graph (SMDG) processing framework, an architecture-level redesign centered on the block as the atomic unit across storage, concurrency, and recovery. The system addresses these challenges through three key innovations. First, a block-granular storage design organizes adjacency data at fixed-size block granularity on heterogeneous DRAM-SCM architecture, employing buffered batched writes to significantly reduce write amplification while preserving logarithmic update complexity. Second, block-level multi-version concurrency control maintains timestamped block versions under per-vertex read-write synchronization to provide task-ordered snapshot visibility for concurrent queries without copying entire vertices or pages. Third, a block-granular crash recovery protocol with decentralized per-vertex logs enables independent parallel reconstruction, ensuring application-level semantic consistency while achieving substantially faster recovery than sequential approaches. Experimental results validate that this unified block-granular design improves update efficiency, sustains mixed update-query workloads with controlled memory overhead, and accelerates crash recovery compared with prior dynamic graph systems.

With the rapid growth of multimodal and multi-view data, multi-view bipartite graph clustering (MVBGC) has emerged as a promising solution for large-scale tasks, which with linear complexity. However, most methods adhere to a unidirectional “encoding” design, where the bipartite graph is directly constructed from input data. Enlightened by the prevalent encoding-decoding in deep learning, this paper rethinks existing paradigms and proposes a novel “auto-encoding” MVBGC framework, named BGAE. Our model seamlessly integrates encoding, bipartite graph learning, and decoding modules within a self-supervised learning framework. The encoding module extracts a joint representation from input data, the bipartite graph learning module learns a discriminative bipartite graph in latent semantic space, and the decoding module reconstructs the input data by the structural information. Extensive experiments verify the superiority of our novel design, particularly highlighting the critical role of “decoding” learning. This work represents the first attempt to explore encoding-decoding design in MVBGC.

Structural Graph Clustering is a well-known problem that aims to identify clusters and distinguish between special roles, such as hub and outlier. However, SCAN, the fundamental structural clustering model, is designed for pairwise graphs and fails to capture the unique structural information inherent in hypergraphs when clustering hypergraphs. Motivated by this, we propose a new structural clustering model, HSCAN, specifically for hypergraphs. We further design an Order-Index to accelerate fetching the key information of the HSCAN and a Lightweight Similarity Bucket Index to reduce the index cost. Next, we present an index-based sequential query algorithm with high performance and a parallel query algorithm to process large hypergraphs faster. Additionally, we provide the algorithms for constructing Order-Index and Lightweight Similarity Bucket Index. Extensive experiments on both real-world and synthetic datasets show that HSCAN performs better than existing models, and the two index-based query algorithms are up to three orders of magnitude faster than the existing algorithm.

This paper addresses the pressing need for effective k-tips decomposition in dynamic bipartite graphs, a crucial aspect of real-time applications that analyze and mine binary relationship patterns. Recognizing the dynamic nature of these graphs, our study is the first to provide a solution for k-tips decomposition in such evolving environments. We introduce a pioneering projection-based algorithm, coupled with advanced incremental maintenance strategies for edge modifications, tailored specifically for dynamic graphs. This novel approach not only fills a significant gap in the analysis of dynamic bipartite graphs but also substantially enhances the accuracy and timeliness of data-driven decisions in critical areas like public health. Our contributions set a new benchmark in the field, paving the way for more nuanced and responsive analyses in various domains reliant on dynamic data interpretation.

Task assignment is a fundamental challenge in Spatial Crowdsourcing which aims to assign location-based tasks to workers under spatial-temporal constraints. Recently, some exciting research has introduced the preference of workers and tasks to improve assignment quality. However, they either primarily focus on the current preferences of both workers and tasks or only consider the unilateral prediction-based preference of workers, overlooking the impact of workers' interconnection and tasks' completed sequences. As a result, they gain suboptimal assignment results in most cases. Inspired by this, we propose a novel problem, named the Predictive Bi-preference Stable Match problem (PBSM), with the goal of maximizing the preferences of both workers and tasks by taking into account the social network of workers and task completion sequence. The PBSM problem is proven to be NP-hard. To tackle this challenging problem, we develop a GCN-enhanced Transformer-based Prediction and Bi-preference Stable Matching (GETBM) framework with two stages: the bi-preference prediction stage and the bilateral assignment stage. In the prediction stage, the Worker Preference Model (WPM) and Task Preference Model (TPM) models are presented to predict the worker-to-task (Worker2Task) and task-to-worker (Task2Worker) preference lists, respectively. Then, we design a bilateral preference-aware stable matching (BPM) algorithm and prove it can gain stable results. To generalize to multiple scenarios, three optimization strategies are devised based on spatial-temporal constraints and priority consideration to gain better assignment performance. Extensive experiments are conducted to prove the superiority of the GETBM framework on two real datasets.

In online social networks (OSNs), people usually join groups for communication. Information diffusion often occurs with some cost, either between individuals or within/among groups; and different opinions may compete with each other. The groups can make decisions based on the majority of the group members. This type of group consensus is common in group activities. However, existing research on maximization of competitive influence often neglects the effects of group consensus. To this end, we introduce the process of group consensus reaching in influence maximization and propose a novel Group consensus-based Competitive Linear Threshold (GCLT) propagation model; then we study the Budgeted Competitive Influence Maximization (BCIM) problem under the GCLT model. We reveal that the problem is NP-hard, and the objective function is proven to be neither submodular nor supermodular. To this end, we construct an equivalent Group consensus-based Competitive Live-Edge (GCLE) model of GCLT by sampling method. Based on GCLE, develop two submodular functions of the upper and lower bounds. Then, we propose the SBG algorithm by applying the Sandwich Approximation framework for the BCIM problem under the GCLT model. In SBG , we provide an approximate solution to the lower bound and the upper bound by the proposed OPIM-B algorithm. Then, we select the seed set of solutions that achieves the best influence spread in Monte Carlo simulations. We also propose two strategies to optimize SBG . The experiments on six real social network datasets verify the effectiveness and scalability of our method and validate the impact of group consensus on the competitive influence dissemination process, as well as the importance of considering the process of reaching group consensus.

Truth discovery endeavors to extract valuable information from multi-source data through weighted aggregation. Some studies have integrated differential privacy techniques into traditional truth discovery algorithms to protect data privacy. However, due to the neglect of outliers and limitations in budget allocation, these schemes still need improvement in the accuracy of discovery results. To solve these challenges, we propose a privacy-preserving scheme called PriPTD to achieve secure and accurate truth discovery services over crowdsourced data streams. Instead of assuming that worker weights are always stable between two neighboring timestamps, we delve deeper to consider outliers where worker weights change rapidly. Accordingly, we develop an outlier-aware weight estimation method with a time series model to capture and handle these outliers. Furthermore, to ensure data utility under a limited budget, we devise a weight-aware budget allocation algorithm. Its core idea is that timestamps with higher importance consume a larger proportion of the remaining budget. Additionally, we design a noise-aware error adjustment approach to mitigate the adverse effects of introduced noise on accuracy. Theoretical analysis and extensive experiments validate our scheme. Final comparative experiments against existing works confirm that our scheme achieves more accurate truth discovery while preserving privacy.

Bipartite graph clustering (BGC) has emerged as a fast-growing research in the clustering community. Despite BGC has achieved promising scalability, most variants still suffer from the following concerns: a) Susceptibility to noisy features. They construct bipartite graphs in the raw feature space, inducing poor robustness to noisy features. b) Inflexible anchor selection strategies. They usually select anchors through heuristic sampling or constrained learning methods, degrading flexibility. c) Partial structure mining. Existing methods are mainly built upon Linear Reconstruction Paradigm (LRP) from subspace clustering or Locally Linear Paradigm (LLP) from manifold learning, which partially exploit linear or locally linear structures, lacking a unified perspective to integrate global complementary structures. To this end, we propose a novel model, termedJoint Robust Embedding and Structural FusionBipartiteGraphClustering (JetBGC), which focuses on three aspects, namely robustness, flexibility, and complementarity. Concretely, we first introduce a robust embedding learning module to extract latent representation that can reduce the impact of noisy features. Then, we optimize anchors via a constraint-free strategy that can flexibly capture data distribution. Furthermore, we revisit the consistency and specificity of LRP and LLP, and design a new unified structural fusion strategy to integrate both linear and locally linear structures from a global perspective. Therefore, JetBGC unifies robust representation learning, flexible anchor optimization, and structural bipartite graph fusion in a framework. Extensive experiments on synthetic and real-world datasets validate our effectiveness against existing baselines.

Sparse data gathering has become a promising solution for reducing measurement costs by leveraging the inherent sparsity of data. However, most existing approaches rely on low-dimensional models such as compressive sensing or matrix completion, which are limited in capturing complex high-dimensional structures. To overcome these limitations, we proposeTensorMon, a novel tensor-based sparse data gathering framework that introduces a cuboid sampling strategy to more effectively exploit multidimensional correlations. Unlike traditional entry-based or tube-based sampling, TensorMon introduces the innovative concept ofcuboid sampling. We further develop a lightweight sampling scheduling algorithm and a non-iterative inference algorithm to ensure efficient measurement planning and accurate reconstruction of unmeasured data. Theoretical analysis establishes a new performance bound for our sampling strategy, which is significantly lower than those in existing literature. To validate our theoretical findings, we conduct extensive experiments on four real-world datasets: two network monitoring datasets, a city-scale crowd flow dataset, and a road traffic speed dataset. Experimental results demonstrate that TensorMon achieves substantial reductions in measurement cost, delivers high inference accuracy, and ensures rapid data recovery, highlighting its effectiveness and practicality across diverse application scenarios.

This paper addresses the pressing need for effective k-tips decomposition in dynamic bipartite graphs, a crucial aspect of real-time applications that analyze and mine binary relationship patterns. Recognizing the dynamic nature of these graphs, our study is the first to provide a solution for k-tips decomposition in such evolving environments. We introduce a pioneering projection-based algorithm, coupled with advanced incremental maintenance strategies for edge modifications, tailored specifically for dynamic graphs. This novel approach not only fills a significant gap in the analysis of dynamic bipartite graphs but also substantially enhances the accuracy and timeliness of data-driven decisions in critical areas like public health. Our contributions set a new benchmark in the field, paving the way for more nuanced and responsive analyses in various domains reliant on dynamic data interpretation.

Machine unlearning involves retracting data records and reducing their influence on trained models, aiding user privacy protection, at a significant computational cost potentially. Weight perturbation-based unlearning is common but typically modifies parameters globally. We propose fine-grained Top-K and Random-k parameters perturbed inexact machine unlearning that address the privacy needs while keeping the computational costs tractable. However, commonly used training data are independent and identically distributed, for inexact machine unlearning, current metrics are inadequate in quantifying unlearning degree that occurs after unlearning. To address this quantification issue, we introduce SPD-GAN, which subtly perturbs data distribution targeted for unlearning. Then, we evaluate unlearning degree by measuring the performance difference of the models on the perturbed unlearning data before and after unlearning. Furthermore, to demonstrate efficacy, we tackle the challenge of evaluating machine unlearning by assessing model generalization across unlearning and remaining data. To better assess the unlearning effect and model generalization, we propose novel metrics, namely, the forgetting rate and memory retention rate. By implementing these innovative techniques and metrics, we achieve computationally efficacious privacy protection in machine learning applications without significant sacrifice of model performance. A by-product of our work is a novel method for evaluating and quantifying unlearning degree.

The serendipity recommendation tries to burst the filter bubble while still meeting user interests. However, serendipity itself has not been well understood in the recommendation system. Thus, factor investigation in recommendation serendipity has attracted much attention, for which two challenges hinder follow-up research: (1) Ambiguity of factors . Different works exploit different factors, and the meanings of factors are inconsistent in various works. (2) Lack of complete impact validation . The importance of these factors in different domains is not yet fully understood. The common approach of user surveys costs much, but the results are usually less objective and limited in quantity. To this end, we strive to comprehensively identify and clarify serendipity factors and explore objective data-driven approaches to validate factor impacts in large-scale cross-domain scenarios. We first conduct a comprehensive literature review to identify all possible factors, from which we find that some factors are being used indistinguishably. To address this issue, we propose two principles of meaning coverage and factor independence to clarify and disentangle serendipity factors. Next, we propose a general experimental framework to explore the impacts of factors. Then, we implement one such framework and run experiments on nine representative datasets to study factor importance on serendipity. We also propose a quantitative method to measure the degree of disentanglement of factors and to test the effects of factor combinations. We gain several useful findings: (1) relevance , diversity , and random are critical factors affecting serendipity; (2) domain features affect factor importance and can guide serendipity recommendation; (3) the disentanglement quantification method benefits the understanding of serendipity and the combination of factors. To our knowledge, this is the first work to comprehensively investigate serendipity factors and experimentally compare their impacts in an objective data-driven approach.

Many researchers primarily rely on modeling user interests for sequential recommendation. However, dynamic user behaviors often accompany unstable interaction histories, and modeling user interests alone is insufficient for comprehensive user features. Some studies notice the problem of interest drift, but they are usually limited to modeling at the item-level, unable to perceive the subtle changes at the feature-level. To this end, we propose a Stability-aware Preference Model (SAPM), which consists of three modules. The LSI module for extracting long and short-term interests, the FLC module for extracting feature-level candidate information, and the SAF module for fusing them according to the stability score. In particular, we propose a Multi-head GRU (MHGRU) structure in the LSI module, which is more efficient than the general GRU and has stronger expression ability. Through extensive experiments, our framework shows significant mitigation of the impact of unstable interactions. On the two real data sets, we improve MRR by 5.7% and 14.0% compared with the recent baselines. Moreover, we conduct an in-depth analysis of user interaction stability and obtain several interesting findings that can benefit future studies.

Diversity is increasingly recognized as a crucial factor in recommendation systems for enhancing user satisfaction. However, existing studies on diversity-enhanced recommendation systems primarily focus on designing recommendation strategies, often overlooking the development of evaluation metrics. Widely used diversity metrics such as CC, ILAD, and ILMD are typically assessed independently of accuracy. This separation leads to a critical limitation: existing diversity measures are unable to distinguish between diversity improvements from effective recommendations and those from in effective recommendations. Our evaluations reveal that the diversity improvements are primarily contributed by ineffective recommendations, which often do not positively contribute to user satisfaction. Furthermore, existing diversity metrics disregard the feature distribution of ground-truth items, potentially skewing the assessment of diversity performance. To address these limitations, we design three new accuracy-aware metrics: DCC, FDCC, and DILAD, and conduct a re-evaluation using these metrics. Surprisingly, our results illustrate that the diversity improvements of existing diversity-enhanced approaches are limited and even negative compared to those of accurate recommendations. This finding underscores the need to explore more sophisticated diversity-enhanced techniques for improving the diversity within effective recommendations.

Task assignment is a fundamental problem in spatial crowdsourcing. In many spatial crowdsourcing platforms, such as Didi, AMAP, and Uber, there are hybrid tasks, including real-time and reservation-type tasks, which are with different constraints and unevenly distributed in spatial and temporal. For these hybrid tasks, most existing studies suffer from low task completion rate and low profit for two reasons: firstly, they focus on homogeneous tasks with uniform constraints, and assign hybrid tasks separately; secondly, they cannot effectively address the uneven distribution of hybrid tasks. Inspired by this, we delve into the problem of online hybrid task assignment (HyTAO) with the goal of maximizing total revenue by simultaneously assigning both real-time and reservation-type tasks online for the first time. We prove the NP-hardness of the offline version of the HyTAO problem. To solve HyTAO effectively, we utilize a cross-platform cooperation model to tackle the challenge of non-uniform distribution. Following this, we design a binary tree-based search algorithm, namely BTS, which is capable of uniformly processing various types of tasks and quickly searching for available workers. Additionally, we discuss the parallel optimization strategies of BTS. To further enhance performance, we develop TBTS, which identifies tasks with high increased revenue based on a threshold. Finally, we conduct a comprehensive analysis of the complexity and competitive ratio of both BTS and TBTS. Extensive experiments are performed to demonstrate the efficiency of our approaches.

Continuous subgraph matching (CSM) is a critical task for analyzing dynamic graphs and has a wide range of applications, such as merchant fraud detection, cyber-attack hunting, and rumor detection. Although many efficient CSM algorithms have been recently proposed, they are mainly designed to process a single query. However, in some application scenarios, multi-query oriented continuous subgraph matching (MQCSM) may be of more interest. To our knowledge, the two existing solutions to MQCSM are outdated due to unsatisfactory performance. In this paper, we propose MQ-Match, an efficient approach to MQCSM. First, we design a compact yet effective index structure CCG, which maintains the local matching result of vertices in the data graph using a directed graph. The directed edges in CCG can be utilized as an effective pruning rule for the subsequent incremental matching algorithm when expanding a partial match. Then, we develop a computation sharing incremental matching algorithm. In specific, a set of matching trees is constructed based on the depth-first search trees of the query graphs. By utilizing CCG, we conduct subgraph matching for the matching tree to collect the incremental matches for the query graphs, where the common structures of query graphs are matched only once. Extensive experiments show that MQ-Match can achieve 3.1x-7071.4x speedup over the competitors, and consumes much less memory under the majority of the experiment settings.

Tensor data is widely used in fields such as smart grids, cloud systems, and deep learning. As the scale of this data increases, storage and transmission costs rise significantly. Many tensor data exhibit low-rank structures, offering the potential for data compression through low-rank decomposition techniques. Tucker decomposition, a typical low-rank decomposition technique, achieves data compression and interpretability by capturing complex data correlations and representing the original tensor with a compact core tensor and factor matrices. However, the compression ratio provided by Tucker decomposition is often insufficient, particularly for large-scale tensors. To tackle this issue, we propose a robust low-rank tensor compression method that leverages Tucker decomposition with quantization and coding. Initially, we establish a robust Tucker decomposition framework that decomposes the low-rank tensor into a core tensor and factor matrices using well-designed Tucker rank-setting rules. This framework effectively handles noise and missing values. Subsequently, we conduct an in-depth analysis of the numerical characteristics of the core tensor and factor matrices within the Tucker decomposition framework. Based on their distinct characteristics, we design tailored quantization and coding schemes to compress the core tensor and factor matrices, respectively, thereby significantly improving the compression ratio of Tucker decomposition while maintaining high accu-racy. Through extensive experiments on four publicly available datasets (which can form 3 or 4 order tensors), we demonstrate that our approach can achieve compression ratios$4\times-10\times$higher than the best competitor, with recovery errors improved by 8% - 42%.

With the popularity of GPS-equipped smart devices, spatial crowdsourcing (SC) techniques have attracted growing attention in both academia and industry. In existing trajectory-aware task assignment approaches, tasks assigned to a worker may be far apart from each other, resulting in a higher detour cost as the worker needs to deviate from the original trajectory more often than necessary. Motivated by the above observations, we investigate a trajectory-aware task coalition assignment (TCA) problem and prove it to be NP-hard. The goal is to maximize the number of assigned tasks by assigning task coalitions to workers based on their preferred trajectories. To tackle the TCA problem, we develop a batch-based three-stage framework consisting of task grouping, planning, and assignment. Extensive experiments on real and synthetic datasets demonstrate the effectiveness and efficiency of the proposed algorithms.

Graph pattern query is a powerful tool for extracting crucial information from property graphs. With the exponential growth of sizes, property graphs are typically divided into multiple subgraphs (referred to as partitions ) and stored across various sites in distributed environments. Existing graph partitioning methods have not been efficiently optimized for pattern queries, resulting in numerous query matches across multiple partitions, called crossing matches. Identifying these matches requires much inter-partition communication, which is the primary performance bottleneck in distributed query processing. To address this issue, this paper introduces a novel connectivity-oriented relationship-disjoint partitioning method, namely RCP (Relationship Connectivity Partitioning), aimed at enhancing the efficiency of graph pattern query processing by reducing crossing matches. By employing each weakly connected component of the subgraph, which is induced by different relationship labels, as a basic unit of partition, RCP ensures that matches for both variable-length path and labeled graph pattern queries are not crossing matches. Here, variable-length path and labeled graph pattern are two common components in graph pattern queries to identify paths meeting specific label constraints and retrieve subgraphs with consistent relationship types, respectively. Moreover, in the query processing phase, we further demonstrate that all graph pattern queries, belonging to these two basic queries or their extensions, can be executed independently under RCP, thereby avoiding crossing matches. In experiments, we implemented two prototype distributed property graph systems based on Neo4j and JanusGraph, which use declarative and functional query language, respectively. Experimental results on billion-scale datasets demonstrate that our approach brings a performance improvement of nearly two orders of magnitude over state-of-the-art partitioning methods.

The enumeration of hop-constrained simple paths is a building block in many graph-based areas. Due to the enormous search spaces in large-scale graphs, a single machine can hardly satisfy the requirements of both efficiency and memory, which causes an urgent need for efficient distributed methods. In practice, it is inevitable to produce plenty of intermediate results when directly extending centralized methods to the distributed environment, thereby causing a memory crisis and weakening the query performance. The state-of-the-art distributed method HybridEnum designed a hybrid search paradigm to enumerate simple paths. However, it makes massive exploration for the redundant vertices not located in any simple path, thereby resulting in poor query performance. To alleviate this problem, we design a distributed approach DistriEnum to optimize query performance and scalability with well-bound memory consumption. Firstly, DistriEnum adopts a graph reduction strategy to rule out the redundant vertices without satisfying the constraint of hop number. Then, a core search paradigm is designed to simultaneously reduce the traversal of shared subpaths and the storage of intermediate results. Moreover, DistriEnum is equipped with a task division strategy to theoretically achieve workload balance. Finally, a vertex migration strategy is devised to reduce the communication cost during the enumeration. The comprehensive experimental results on 10 real-world graphs demonstrate that DistriEnum achieves up to 3 orders of magnitude speedup than HybridEnum in query performance and exhibits superior performances on scalability, communication cost, and memory consumption.

GPUs are commonly utilized to accelerate GNN training, particularly on a multi-GPU server with high-speed interconnects (e.g., NVLink and NVSwitch). However, the rapidly increasing scale of graphs poses a challenge to applying GNN to real-world applications, due to limited GPU memory. This paper presents XGNN, a multi-GPU GNN training system that fully utilizes system memory (e.g., GPU and host memory), as well as high-speed interconnects. The core design of XGNN is the Global GNN Memory Store (GGMS), which abstracts underlying resources to provide a unified memory store for GNN training. It partitions hybrid input data, including graph topological and feature data, across both GPU and host memory. GGMS also provides easy-to-use APIs for GNN applications to access data transparently, forwarding data access requests to the actual physical data partitions automatically. Evaluation on various multi-GPU platforms using three common GNN models with four large-scale datasets shows that XGNN outperforms DGL, Quiver and DGL+C by up to 7.9X (from 2.3X), 15.7X (from 3.3X) and 2.8X (from 1.3X), respectively.

How to construct imperceptible (realistic) fake samples is critical in adversarial attacks. Due to the sample feature diversity of a recommender system (containing both discrete and continuous features), traditional gradient-based adversarial attack methods may fail to construct realistic fake samples. Meanwhile, most recommendation models adopt click-through rate (CTR) predictors, which usually utilize black-box deep models with discrete features as input. Thus, how to efficiently construct realistic fake samples for black-box recommender systems is still full of challenges. In this article, we propose a hierarchical adversarial attack method against black-box CTR models via generating realistic fake samples, named CTRAttack. To better train the generation network, the weights of its embedding layer are shared with those of the substitute model, with both the similarity loss and classification loss used to update the generation network. To ensure that the discrete features of the generated fake samples are all real, we first adopt the similarity loss to ensure that the distribution of the generated perturbed samples is sufficiently close to the distribution of the real features, and then the nearest neighbor algorithm is used to retrieve the most appropriate features for non-existent discrete features from the candidate instance set. Extensive experiments demonstrate that CTRAttack can not only effectively attack the black-box recommender systems but also improve the robustness of these models while maintaining prediction accuracy.

The meteorological environment has a profound impact on global health (e.g., air quality), science and technology (e.g., rocket launches), and economic development (e.g., poverty reduction) etc. Meteorological prediction presents numerous challenges to both academia and industry due to its multifaceted nature which encompasses real-time observations and complex modeling. Recent research adopt graph convolutional recurrent network and establish coordinate information to obtain local spatial-temporal pattern. However, the model only utilizes the local spatial-temporal information and fail to fully consider the dynamic meteorological situation. To address the above limitations, we propose a Dynamic Spatial-Temporal Graph Neural Network (DSTGNN) to learn global-local meteorological features. Specifically, we divide the global spatial-temporal information along the timeline to obtain local spatial-temporal information. For the global aspect, we design a random throwedge module during the neighborhood propagation process in graph neural network (GNN) to extract the features and adapt to the dynamic situation. We also establish convolution operation module to learn the features. Next, we perform information fusion on the two modules to capture sufficient features. In addition, we employ graph ordinary differential equation (ODE) network and utilize the coordinate information to obtain the long-term features and coordinate relationships. In the local aspect, we first construct a GNN to conduct graph embedding. Then, we integrate another GNN into a gated recurrent unit (GRU) and also use the coordinate information to explore the features and coordinate relationships. Finally, we combine the global and local features via a global-local features learning layer for meteorological prediction. Experimental results on the four real-world meteorological datasets show that DSTGNN outperforms the baseline models.

Unsupervised multi-view bipartite graph clustering (MVBGC) is a fast-growing research, due to promising scalability in large-scale tasks. Although many variants are proposed by various strategies, a common design is to construct the bipartite graph directly from the input data, i.e. only consider the unidirectional “encoding” process. However, “encoding-decoding” mechanism is a popular design for deep learning, the most representative one is auto-encoder (AE). Enlightened by this, this paper rethinks existing MVBGC paradigms and transfers the “encoding-decoding” design into graph machine learning, and proposes a novel framework termed auto-encoding multi-view bipartite graph clustering (BGAE), which integrates encoding, bipartite graph construction, and decoding modules in a self-supervised learning manner. The encoding module extracts a latent joint representation from the input data, the bipartite graph construction module learns a bipartite graph with connectivity constraint in latent semantic space, and the decoding module recreates the input data via the bipartite graph. Therefore, our novel BGAE combines representation learning, bipartite graph learning, reconstruction learning, and label inference into a unified framework. All the modules are seamlessly integrated and mutually reinforcing for clustering-friendly purposes. Extensive experiments verify the superiority of our novel design and the significance of “decoding” process. To the best of our knowledge, this is the first attempt to explore “encoding-decoding” design in traditional MVBGC. The code is provided athttps://github.com/liliangnudt/BGAE.

In recommendation systems, Graph Convolutional Networks (GCNs) often suffer from significant computational and memory cost when propagating features across the entire user-item graph. While various sampling strategies have been introduced to reduce the cost, the challenge of neighbor explosion persists, primarily due to the iterative nature of neighbor aggregation. This work focuses on exploring subgraph propagation for scalable recommendation by addressing two primary challenges:efficient and effective subgraph constructionandsubgraph sparsity. To address these challenges, we propose a novelGCNmodel for recommendation based onSubgraph propagation, called SubGCN. One key component of SubGCN is BiPPR, a technique that fuses both source- and target-based Personalized PageRank (PPR) approximations, to overcome the challenge ofefficient and effective subgraph construction. Furthermore, we propose a source-target contrastive learning scheme to mitigate the impact ofsubgraph sparsityfor SubGCN. We conduct extensive experiments on two large and two medium-sized datasets to evaluate the scalability, efficiency, and effectiveness of SubGCN. On medium-sized datasets, compared to full-graph GCNs, SubGCN achieves competitive accuracy while using only 23.79% training time on Gowalla and 16.3% on Yelp2018. On large datasets, where full-graph GCNs ran out of the GPU memory, our proposed SubGCN outperforms widely used sampling strategies in terms of training efficiency and recommendation accuracy.

Robust PCA is a popular anomaly detection technique and has been widely used in many applications. Although Robust PCA is promising, it is usually designed in a two-order matrix form, which is inferior to the tensor that can capture multilinearity features of data. Moreover, the detection accuracy under Robust PCA further suffers due to its sensitivity to the rank parameter which is hard to set in practice and the limitation of PCA method in capturing the non-linear feature in the data. To address the issues, we propose a Robust Tensor Convolutional Autoencoder (RTCAE) where the autoencoder instead of SVD is exploited to recover the normal data from the corrupted measurement tensor data. However, directly exploiting deep autoencoder may suffer from the problem of high memory consumption and computation overhead due to the large number of parameters used in autoencoder. To make our anomaly detection lightweight, we further design a Light Convolutional Autoencoder (LightCAE) which contains a compressed autoencoder by exploiting tensor factorization to largely compress the parameters while significantly reducing the computation complexity. We conduct extensive experiments on three real data traces to compare the performance of our proposed schemes (RTCAE and lightCAE) with that of seven baseline algorithms. The experiment results demonstrate that our proposed RTCAE achieves the highest anomaly detection accuracy. Moreover, our LightCAE requires over 60 times smaller memory storage than that required in RTCAE while achieving the similar anomaly detection accuracy.

With the popularity of GPS-equipped smart devices, spatial crowdsourcing (SC) techniques have attracted growing attention in both academia and industry. A fundamental problem in SC is assigning location-based tasks to workers under spatial-temporal constraints. In many real-life applications, workers choose tasks on the basis of their preferred trajectories. However, by existing trajectory-aware task assignment approaches, tasks assigned to a worker may be far apart from each other, resulting in a higher detour cost as the worker needs to deviate from the original trajectory more often than necessary. Motivated by the above observations, we investigate a trajectory-aware task coalition assignment (TCA) problem and prove it to be NP-hard. The goal is to maximize the number of assigned tasks by assigning task coalitions to workers based on their preferred trajectories. For tackling the TCA problem, we develop a batch-based three-stage framework consisting of task grouping, planning, and assignment. First, we design greedy and spanning grouping approaches to generate task coalitions. Second, to gain candidate task coalitions for each worker efficiently, we design task-based and trajectory-based pruning strategies to reduce the search space. Furthermore, a 2-approximate algorithm, termed MST-Euler, is proposed to obtain a route among each worker and task coalition with a minimal detour cost. Third, the MST-Euler Greedy (MEG) algorithm is presented to compute an assignment that results in the maximal number of tasks assigned and a parallel strategy is introduced to boost its efficiency. Extensive experiments on real and synthetic datasets demonstrate the effectiveness and efficiency of the proposed algorithms.

Federated Learning (FL) combined with Differential Privacy (DP) is widespread in healthcare, finance, and IoT due to its advantages in multi-client data distribution. However, existing FL approaches overlook the differential impact levels among clients and data redundancy issues, resulting in high computational overhead and limited real-time applicability. Additionally, non-independent identical distribution (Non-IID) and imbalanced datasets in multi-clients pose challenges in privacy preservation and model overfitting. Therefore, we propose a balanced weight strategy for multi-stage federated learning against multi-client data skewing, called BM-FL, which involves clients, intermediate trust servers (ITSs), and the central server (CS). Firstly, to protect data privacy, an improved Laplace$\epsilon$-differential privacy method is employed. Secondly, a novel generative adversarial network (GAN) called BC-GAN is introduced. It is used to generate realistic fake samples and maintain a balanced proportion of samples across different categories. Then, to make full use of each client's valuable data, we designe a balanced weight strategy. Moreover, extensive experimental results clearly demonstrate the effectiveness of BM-FL in efficiently handling classification tasks involving Non-IID and imbalanced datasets while maintaining privacy and security. Furthermore, our method attains superior classification accuracy with fewer training epochs compared to relevant classical algorithms. The code is available athttps://github.com/ylxzjy/BMFL.git.

Recent research has revealed that deep generative models including flow-based models and Variational Autoencoders may assign higher likelihoods to out-of-distribution (OOD) data than in-distribution (ID) data. However, we cannot sample OOD data from the model. This counterintuitive phenomenon has not been satisfactorily explained and brings obstacles to OOD detection with flow-based models. In this article, we prove theorems to investigate the Kullback-Leibler divergence in flow-based model and give two explanations for the above phenomenon. Based on our theoretical analysis, we propose a new method KLODS to leverage KL divergence and local pixel dependence of representations to perform anomaly detection. Experimental results on prevalent benchmarks demonstrate the effectiveness and robustness of our method. For group anomaly detection, our method achieves 98.1% AUROC on average with a small batch size of 5. On the contrary, the baseline typicality test-based method only achieves 64.6% AUROC on average due to its failure on challenging problems. Our method also outperforms the state-of-the-art method by 9.1% AUROC. For point-wise anomaly detection, our method achieves 90.7% AUROC on average and outperforms the baseline by 5.2% AUROC. Besides, our method has the least notable failures and is the most robust one.

As a novel intelligent sensing paradigm, spatial crowdsourcing has received extensive attention. Task assignment is a key issue in spatial crowdsourcing. In practice, tasks are unevenly distributed in time and space. Accordingly, the problem of cross task assignment attracts growing attention in both industry and academia. Although there has been a research on this problem, it focuses only on maximizing total revenues for inner platforms. Therefore, it can also be improved to bring a multi-win situation for outer workers and task requesters as well as the inner platform. Inspired by this, we first formulate a new cross dynamic task assignment (CDTA) problem by introducing the reputation scores of workers, and prove it to be NP-hard. For the CDTA problem, a hybrid batch-based framework is presented on the basis of a new cross-platform incentive mechanism and a hybrid batch processing strategy, which are efficient in solving the problem of uneven spatial and time distribution of tasks, respectively. After that, a KM-based algorithm and a density-aware greedy algorithm are proposed to gain an accurate assignment result of tasks in each batch and good performance, respectively. Furthermore, the CDTA problem is modeled as a potential game that is proven to have at least a pure Nash Equilibrium theoretically. Last but not least, a game-theoretic approach is developed to maximize the revenues of the inner platform and outer workers at the same time. Extensive experiments on both real and synthetic datasets are conducted to demonstrate the effectiveness and efficiency of the proposed algorithms.

Bipartite graph is an important data structure that widely exists in disease prevention and control, community detection, and other real-life applications. In a bipartite graph, edges not only connect entries of different types but also are bridges of different communities in the above applications. However, research to date has not yet focused on edge importance in bipartite graphs. Inspired by this, we study a new problem of top-k edge search in bipartite graphs with the goal of finding k most important edges for a given bipartite graph; these edges are crucial bridges among communities. In particular, we introduce the measure of ego-betweenness for evaluating the importance of edges. To handle this problem effectively, a lazy bound-based algorithm is first proposed by integrating an upper bound pruning strategy. After that, to further get better efficiency, a greedy bound-based heuristic algorithm is explored on the basis of a tighter upper bound which contributes to reducing redundant computation for calculating ego-betweenness. Last but not least, two parallel techniques with different levels of granularity, called P -src and P -task, are respectively introduced to further improve the search efficiency. The experimental results on both real-world and synthetic graphs demonstrate the efficiency and scalability of the proposed algorithms.

Virtual machine (VM) replication is a critical task in any cloud computing platform to ensure the availability of the cloud service for the end user. In this task, one primary VM resides on a physical machine (PM) and one or more replicas reside on separate PMs. In cloud computing, VM placement (VMP) is a well‐studied problem in terms of different goals, such as power consumption reduction. The VMP problem can be solved by using heuristics, namely, first‐fit and meta‐heuristics such as the genetic algorithm. Despite extensive research into the VMP problem, there are few works that consider VM replication when choosing a VMP. In this context, we proposed studying the problem of optimal VMP considering VM replication requirements. The proposed work frames the problem at hand as a multiobjective problem and adapts a nondominated sorting genetic algorithm (NSGA‐III) to address the problem. VM replicas’ placement should consider several dimensions such as the geographical distance between the PM hosting the primary VM and the other PMs hosting the replicas. In addition, to this end, the proposed model aims to minimize (1) power consumption, (2) performance degradation, and (3) the distance between the PMs hosting the primary VM and its replica(s). The proposed method is thoroughly tested on a variety of computing environments with various heterogeneous VMs and PMs, including compute‐intensive and memory‐intensive environments. The obtained results illustrate the performance disparity between the adapted NSGA‐III and MOEA/D methods and other methods of comparison, including heuristic and meta‐heuristic approaches, with NSGA‐III outperforming other comparison methods. For instance, in memory‐intensive and in heterogeneous environments, the NSGA‐III method’s performance was superior to the first‐fit, next‐fit, best‐fit, PSO, and MOEA/D methods by 58%, 62%, 64%, 55%, and 31%, respectively.

Distributed deep learning systems effectively respond to the increasing demand for large‐scale data processing in recent years. However, the significant investment in building distributed learning systems with powerful computing nodes places a huge financial burden on developers and researchers. It will be good to predict the precise benefit, i.e., how many times of speedup it can get compared with training on single machine (or a few), before actually building such big learning systems. To address this problem, this paper presents a novel performance model on training iteration time for heterogeneous distributed deep learning systems based on the characteristics of the parameter server (PS) system with bulk synchronous parallel (BSP) synchronization style. The accuracy of our performance model is demonstrated by comparing real measurement results on TensorFlow when training different neural networks with various kinds of hardware testbeds: the prediction accuracy is higher than 90% in most cases.

Unsupervised bipartite graph learning has been a hotpot in multi-view clustering, to tackle the restricted scalability issue of traditional full graph clustering in large-scale applications. However, the existing bipartite graph clustering paradigm pays little attention to the adverse impact of noisy features on learning process. To further facilitate this part of research, apart from simply reweighting features to depress the noisy ones, we take the first step towards analyzing the induced adverse impact via theoretical and experimental investigations. One crucial finding in this paper is that the existence of noisy features will incur “anchor shift” phenomenon, which deviates the potential representations of anchors and then degrades performance. To this end, we propose a coupled noisy feature filter mechanism with automatically finding feature importance to remedy the anchor shift issue in this paper. Apart from leveraging features, we theoretically analyze the bounds of proposed feature-adaptive bipartite graph's fuzzy membership. Specifically, distinguishing features' discrimination will increase the fuzzy membership to achieve soft partitions against the potential inaccurate absolute relationship. With the afore-mentioned merits, our proposed multi-view bipartite graph clustering with coupled noisy feature filter model (MVBGC-NFF) provides novel and interesting insights on the feature level of anchor shift. The effectiveness and efficiency of MVBGC-NFF are demonstrated on synthetic and real-world datasets with improving clustering performance, increasing fuzzy membership, and filtering noisy features. The code is available onhttps://github.com/liliangnudt/MVBGC-NFF.

Influential community search aims to find cohesive subgraphs (communities) with considerable influence. It is a fundamental graph management operator that can play a crucial role in biological network analysis, activity organization, and other real-life applications. Existing research on influential community search is mainly focused on deterministic graphs with the assumption that influences between entities are certain. This assumption is invalid in many cases because it ignores the uncertainty which is an inherent property of influence. Against this backdrop, in this paper, we introduce an uncertain influential community model, namely$(k, \eta)$-influential community, based on which the influential community search problem over uncertain graphs is formulated. Furthermore, we propose an online approach by integrating a peeling-pruning strategy that can progressively refine the given uncertain graph to find the$(k, \eta)$-influential communities. To further improve the search performance, two novel indexes, ICU-Index and FICU-Index, are developed to organize the$(k, \eta)$-influential communities at different probabilistic intervals. The indexes decompose the probabilistic interval into multiple subintervals and based on this, the$(k, \eta)$-influential communities are divided into different groups in turn. Compared with ICU-Index, FICU-Index requires considerably less space with the introduction of two optimization strategies. These indexes help obtain results of an influential community search problem more efficiently. Extensive experiments on large real and synthetic datasets demonstrate the efficiency and effectiveness of our proposed algorithms.

Graph convolutional network (GCN) has been extensively applied to recommender systems (RS) and achieved significant performance improvements through iteratively aggregating high-order neighbors to model the relevance between users and items as well as their characteristics. In the aggregation process, GCN models usually give neighbors the same or trainable weights based on implicit features, ignoring explicit ones. In this work, we take the features with explicit meanings or extracted with specific purpose as explicit ones (e.g., temporal features) and the others contained in user-item network as implicit ones (e.g., user preferences). However, some explicit features and knowledge play an essential role in improving the model representation ability and explainability in recommendation systems. To deal with the limitation, we propose a GCN based framework to embed the explicit features or those extracted with explicit intentions in this work. We also provide specific implementations based on two commonly researched features, temporal evolution and popularity bias. Specifically, we first experimentally analyze the popularity bias of the representation learning in RS based on two commonly used GCN models. Secondly, we propose a general framework to weigh neighbors based on explicit features or intentions. Thirdly, we implement a Temporal and Popularity weighted Aggregator (TPA) for GCN. The Interest-Forgetting Curve is utilized to capture temporal evolution as temporal weights and the data-driven Beta distribution is employed to tune the weights based on the node popularity flexibly. At last, we conduct extensive experiments on three real-world datasets to demonstrate the effectiveness of TPA in improving recommendation accuracy and alleviating the popularity bias.

The legal charge prediction task aims to judge appropriate charges according to the given fact description in cases. Most existing methods formulate it as a multi-class text classification problem and have achieved tremendous progress. However, the performance on low-frequency charges is still unsatisfactory. Previous studies indicate leveraging the charge label information can facilitate this task, but the approaches to utilizing the label information are not fully explored. In this paper, inspired by the vision-language information fusion techniques in the multi-modal field, we propose a novel model (denoted as LeapBank) by fusing the representations of text and labels to enhance the legal charge prediction task. Specifically, we devise a representation fusion block based on the bilinear attention network to interact the labels and text tokens seamlessly. Extensive experiments are conducted on three real-world datasets to compare our proposed method with state-of-the-art models. Experimental results show that LeapBank obtains up to 8.5% Macro-F1 improvements on the low-frequency charges, demonstrating our model's superiority and competitiveness.

Canonical Polyadic Decomposition (CPD) of sparse tensors is an effective tool in various machine learning and data analytics applications, in which sparse Matricized Tensor Times Khatri-Rao Product (MTTKRP) is the major performance bottleneck. To overcome this bottleneck and support efficient applications, this paper presents HPSpTM, an efficient sparse MTTKRP framework, to exploit the multi-level parallelism and reusability on heterogeneous HPC systems. HPSpTM incorporates: (1) a multi-level matrix-driven tiling engine that leverages the process- and thread-level parallelism of the underlying platform and data reusability based on the derived factor matrix-driven MTTKRP algorithm; (2) a tensor-driven parallel execution that enables buffering-aware scheduling and pipeline scheduling to optimize the performance in the tile granularity; (3) a partition-aware light weight data storage that exploits better data locality based on the proposed hierarchical and fine-grained execution; and (4) a performance auto-tuning technique that offers large flexibility for tile size auto-adjusting across various input datasets based on a designed runtime model. Our experiments show that HPSpTM on a Nvidia Tesla P100 obtains the average performance improvement of up to 76.46% over the state-of-the-arts, and HPSpTM achieves the speedup of up to 15.39× when scaling from 8 to 128 core groups, corresponding to processes, on the Sunway TaihuLight supercomputer.

As a typical most-to-most connected quasi-biclique model, k-biplex is a superset of bicliques, which allows nodes on each side of a fully connected subgraph to lose at most$k$connections. In this paper, we investigate the maximum biplex search problem for the first time. The goal here is to find a k-biplex with the maximum number of edges and we have proved that the problem is NP-hard. It is widely used in fraudulent reviewer group detection, gene expression analysis, social recommendation, and other real-life applications. To solve this problem, a maximum k-biplex search algorithm (MBS) is first presented by integrating two pruning strategies, including degree-based and 2-hop-based pruning. In addition, we define a new dense subgraph over bipartite graphs,$\langle x, y\rangle$-core, and develop a core-based maximum k-biplex search algorithm (MBS-Core) which can significantly reduce the search space with the introduction of a core-based graph reduction technique. In particular, it only needs to search these cores instead of the entire graph to obtain the maximum k-biplex. Moreover, a parallel algorithm and a heuristic algorithm are developed to achieve better query performance on larger-scale bipartite graphs. Extensive experiments have been conducted on real-life and synthetic datasets to verify the efficiency and effectiveness of the proposed algorithms. Our results show that MBS-Core is up to 3 orders of magnitude faster than the existing approaches.

Set label-constrained reachability (SLCR) query in edge-labeled graphs is a building block of many graph-based applications. Formally, given two sets$S$and$T$of source and target vertices and a label set (, it returns all reachable vertex pairs (s, t) under the constraint of (, where$s$∊$S$and$t$∊T. There have been abundant index-based approaches to be applied to process the SLCR query. However, distributed approaches are desirable to process large-scale graphs because of the advantages of good scalability and real-time response. Now, there is no efficient distributed approach to the SLCR query. Most index-based approaches face limitations in terms of index construction and query performance when being extended to the distributed environment for processing large-scale graphs. To alleviate these problems, we first build a boundary graph-based index (BoundG) to reduce the time overhead of index construction. Consider the query performance of the BoundG-based approach has no noticeable improvement. We further construct a novel two layers 2-hop index (TL2hop), and a TL2hop-based query algorithm (TLQA) is designed by integrating an early termination strat-egy that reduces the communication overhead and boosts the query performance. Experimental results over eight data graphs demonstrate that the index time of BoundG is comparable to that of the state-of-the-art, and TL2hop significantly outperforms the state-of-the-art technique in terms of query response time (up to 4 orders of magnitude speedup).

Task assignment is a crucial issue in spatial crowd-sourcing. In most existing studies, the results of the task assignment cannot satisfy the workers and tasks at the same time. This is because only one-sided preferences are taken into account. Moreover, tasks are always assigned based on the locations of workers instead of the trajectories. Accordingly, they are not appropriate to the specific applications, such as carpool. Inspired by this, we investigate an interesting problem of task assignment, namely bilateral preference-aware task assignment (BPTA), with the goal of maximizing the overall satisfaction of workers and tasks by assigning tasks to suitable workers based on their routine trajectories. To tackle this problem effectively, we first propose greedy algorithms, namely task preference priority greedy and worker preference priority greedy algorithms, which are task-driven and worker-driven, respectively. Although these algorithms can solve the BPTA problem effectively, they cannot ensure the stability of the task assignment results. In other words, there can be better choices for some workers and tasks. Accordingly, we further explore deferred acceptance algorithms to find a stable matching for workers and tasks by simultaneously considering the preferences of workers and tasks. Moreover, two optimizing strategies, including a parallel strategy and a top-$k$strategy, are introduced to boost the performance in handling the BPTA problem. Extensive experiments on both real and synthetic datasets have validated the efficiency and effectiveness of our proposed algorithms.

Time-series forecasting is an important problem across a wide range of domains. Designing accurate and prompt forecasting algorithms is a non-trivial task, as temporal data that arise in real applications often involve both non-linear dynamics and linear dependencies, and always have some mixtures of sequential and periodic patterns, such as daily, weekly repetitions, and so on. At this point, however, most recent deep models often use Recurrent Neural Networks (RNNs) to capture these temporal patterns, which is hard to parallelize and not fast enough for real-world applications especially when a huge amount of user requests are coming. Recently, CNNs have demonstrated significant advantages for sequence modeling tasks over the de-facto RNNs, while providing high computational efficiency due to the inherent parallelism. In this work, we propose HyDCNN, a novel hybrid framework based on fully Dilated CNN for time-series forecasting tasks. The core component in HyDCNN is a proposed hybrid module, in which our proposed position-aware dilated CNNs are utilized to capture the sequential non-linear dynamics and an autoregressive model is leveraged to capture the sequential linear dependencies. To further capture the periodic temporal patterns, a novel hop scheme is introduced in the hybrid module. HyDCNN is then composed of multiple hybrid modules to capture the sequential and periodic patterns. Each of these hybrid modules targets on either the sequential pattern or one kind of periodic patterns. Extensive experiments on five real-world datasets have shown that the proposed HyDCNN is better compared with state-of-the-art baselines and is at least 200% better than RNN baselines. The datasets and source code will be published in Github to facilitate more future work.

Multi-set membership query is a fundamental issue for network functions such as packet processing and state machines monitoring. Given the rigid query speed and memory requirements, it would be promising if a multi-set query algorithm can be designed based on Bloom filter (BF), a space-efficient probabilistic data structure. However, existing efforts on multi-set query based on BF suffer from at least one of the following drawbacks: low query speed, low query accuracy, limitation in only supporting insertion and query operations, or limitation in the set size. To address the issues, we design a novel B h sequence-based Bloom filter (B h BF) for multi-set query, which supports four operations: insertion, query, deletion, and update. In B h BF, the set ID is encoded as a code in a B h sequence. Exploiting good properties of B h sequences, we can correctly decode the BF cells to obtain the set IDs even when the number of hash collisions is high, which brings high query accuracy. In B h BF, we propose two strategies to further speed up the query speed and increase the query accuracy. On the theoretical side, we analyze the false positive and classification failure rate of our B h BF. Our results from extensive experiments over two real datasets demonstrate that B h BF significantly advances state-of-the-art multi-set query algorithms.

Benefiting from convenient cycling and flexible parking locations, the Dockless Public Bicycle-sharing (DL-PBS) network becomes increasingly popular in many countries. However, redundant and low-utility stations waste public urban space and maintenance costs of DL-PBS vendors. In this article, we propose a Bicycle Station Dynamic Planning (BSDP) system to dynamically provide the optimal bicycle station layout for the DL-PBS network. The BSDP system contains four modules: bicycle drop-off location clustering, bicycle-station graph modeling, bicycle-station location prediction, and bicycle-station layout recommendation. In the bicycle drop-off location clustering module, candidate bicycle stations are clustered from each spatio-temporal subset of the large-scale cycling trajectory records. In the bicycle-station graph modeling module, a weighted digraph model is built based on the clustering results and inferior stations with low station revenue and utility are filtered. Then, graph models across time periods are combined to create a graph sequence model. In the bicycle-station location prediction module, the GGNN model is used to train the graph sequence data and dynamically predict bicycle stations in the next period. In the bicycle-station layout recommendation module, the predicted bicycle stations are fine-tuned according to the government urban management plan, which ensures that the recommended station layout is conducive to city management, vendor revenue, and user convenience. Experiments on actual DL-PBS networks verify the effectiveness, accuracy, and feasibility of the proposed BSDP system.

Multi-task learning plays an important role in face multi-attribute prediction. At present, most researches excavate the shared information between attributes by sharing all convolutional layers. However, it is not appropriate to treat the low-level and high-level features of the face multi-attribute equally, because the high-level features are more biased toward the specific content of the category. In this article, a novel multi-attribute tensor correlation neural network (MTCN) is used to predict face attributes. MTCN shares all attribute features at the low-level layers, and then distinguishes each attribute feature at the high-level layers. To better excavate the correlations among high-level attribute features, each sub-network explores useful information from other networks to enhance its original information. Then a tensor canonical correlation analysis method is used to seek the correlations among the highest-level attributes, which enhances the original information of each attribute. After that, these features are mapped into a highly correlated space through the correlation matrix. Finally, we use sufficient experiments to verify the performance of MTCN on the CelebA and LFWA datasets and our MTCN achieves the best performance compared with the latest multi-attribute recognition algorithms under the same settings.

CANDECOMP/PARAFAC (CP) decomposition is widely used in various online social network (OSN) applications. However, it is inefficient when dealing with massive and incremental data. Some incremental CP decomposition (ICP) methods have been proposed to improve the efficiency and process evolving data, by updating decomposition results according to the newly added data. The ICP methods are efficient, but inaccurate because of serious error accumulation caused by approximation in the incremental updating. To promote the wide use of ICP, we strive to reduce its cumulative errors while keeping high efficiency. We first differentiate all possible errors in ICP into two types: the cumulative reconstruction error and the prediction error. Next, we formulate two optimization problems for reducing the two errors. Then, we propose several restarting strategies to address the two problems. Finally, we test the effectiveness in three typical dynamic OSN applications. To the best of our knowledge, this is the first work on reducing the cumulative errors of the ICP methods in dynamic OSNs.

Answer selection plays a crucial role in natural language processing. and thus has received much attention. Many recent works treat it as an ad-hoc retrieval problem where ranking optimization accounts for a large proportion. Previous works mainly consider the similarity between answer and question, but rarely utilize similarity and dissimilarity relationship in the answers candidate set. In this paper, we propose a similarity aggregation method to rerank the results produced by different baseline neural networks. The key idea of similarity aggregation is that true matches should not only similar to other true matches, but also dissimilar with false matches, and inspired by multi-view verification, the true answers should have the same ranking to the question in different baseline methods and false answers are the same. The empirical results, from the public benchmark task of answer selection, demonstrate that our method has significant improvement over the baseline methods.

Serendipity recommendation has attracted more and more attention in recent years; it is committed to providing recommendations which could not only cater to users’ demands but also broaden their horizons. However, existing approaches usually measure user-item relevance with a scalar instead of a vector, ignoring user preference direction, which increases the risk of unrelated recommendations. In addition, reasonable explanations increase users’ trust and acceptance, but there is no work to provide explanations for serendipitous recommendations. To address these limitations, we propose a Directional and Explainable Serendipity Recommendation method named DESR. Specifically, we extract users’ long-term preferences with an unsupervised method based on GMM (Gaussian Mixture Model) and capture their short-term demands with the capsule network at first. Then, we propose the serendipity vector to combine long-term preferences with short-term demands and generate directionally serendipitous recommendations with it. Finally, a back-routing scheme is exploited to offer explanations. Extensive experiments on real-world datasets show that DESR could effectively improve the serendipity and explainability, and give impetus to the diversity, compared with existing serendipity-based methods.

Traffic flow prediction is crucial for public safety and traffic management, and remains a big challenge because of many complicated factors, e.g., multiple spatio-temporal dependencies, holidays, and weather. Some work leveraged 2D convolutional neural networks (CNNs) and long short-term memory networks (LSTMs) to explore spatial relations and temporal relations, respectively, which outperformed the classical approaches. However, it is hard for these work to model spatio-temporal relations jointly. To tackle this, some studies utilized LSTMs to connect high-level layers of CNNs, but left the spatio-temporal correlations not fully exploited in low-level layers. In this work, we propose novel spatio-temporal CNNs to extract spatio-temporal features simultaneously from low-level to high-level layers, and propose a novel gated scheme to control the spatio-temporal features that should be propagated through the hierarchy of layers. Based on these, we propose an end-to-end framework, multiple gated spatio-temporal CNNs (MGSTC), for citywide traffic flow prediction. MGSTC can explore multiple spatio-temporal dependencies through multiple gated spatio-temporal CNN branches, and combine the spatio-temporal features with external factors dynamically. Extensive experiments on two real traffic datasets demonstrates that MGSTC outperforms other state-of-the-art baselines.

The G-Skyline (GSky) query is a powerful tool to analyze optimal groups in decision support. Compared with other group skyline queries, it releases users from providing an aggregate function. Besides, it can get much comprehensive results without overlooking some important results containing non-skylines. However, it is hard for the users to make sensible choices when facing so many results the GSky query returns, especially over a large, high-dimensional dataset or with a large group size. In this article, we investigate k representative G-Skyline ( k GSky) queries to obtain a manageable size of optimal groups. The k GSky query can also inherit the advantage of the GSky query; its results are representative and diversified. Next, we propose three exact algorithms with novel techniques including an upper bound pruning, a grouping strategy, a layered optimum strategy, and a hybrid strategy to efficiently process the k GSky query. Consider these exact algorithms have high time complexity and the precise results are not necessary in many applications. We further develop two approximate algorithms to trade off some accuracy for efficiency. Extensive experiments on both real and synthetic datasets demonstrate the efficiency, scalability, and accuracy of the proposed algorithms.

Tensors have drawn a growing attention in many applications, such as physics, engineering science, social networks, recommended systems. Tensor decomposition is the key to explore the inherent intrinsic data relationship of tensor. There are many sparse tensor and vector multiplications (SpTV) in tensor decomposition. We analyze a variety of storage formats of sparse tensors and develop a piecewise compression strategy to improve the storage efficiency of large sparse tensors. This compression strategy can avoid storing a large number of empty slices and empty fibers in sparse tensors, and thus the storage space is significantly reduced. A parallel algorithm for the SpTV based on the high-order compressed format based on slices is designed to greatly improve its computing performance on graphics processing unit. Each tensor is cut into multiple slices to form a series of sparse matrix and vector multiplications, which form the pipelined parallelism. The transmission time of the slices can be hidden through pipelined parallel to further optimize the performance of the SpTV.

Nowadays, with the development of e-commerce, a growing number of customers choose to go shopping online. To find attractive products from online shopping marketplaces, the skyline query is a useful tool which offers more interesting and preferable choices for customers. The skyline query and its variants have been extensively investigated. However, to the best of our knowledge, they have not taken into account the requirements of customers in certain practical application scenarios. Recently, online shopping marketplaces usually hold some price promotion campaigns to attract customers and increase their purchase intention. Considering the requirements of customers in this practical application scenario, we are concerned about product selection under price promotion. We formulate a constrained optimal product combination (COPC) problem. It aims to find out the skyline product combinations which both meet a customer's willingness to pay and bring the maximum discount rate. The COPC problem is significant to offer powerful decision support for customers under price promotion, which is certified by a customer study. To process the COPC problem effectively, we first propose a two list exact (TLE) algorithm. The COPC problem is proven to be NP-hard, and the TLE algorithm is not scalable because it needs to process an exponential number of product combinations. Additionally, we design a lower bound approximate (LBA) algorithm that has a guarantee about the accuracy of the results and an incremental greedy (IG) algorithm that has good performance. The experiment results demonstrate the efficiency and effectiveness of our proposed algorithms.

Group skyline query is a powerful tool for optimal group analysis. Most of the existing group skyline queries select optimal groups by comparing the dominance relationship between aggregate-based points; such feature creates difficulties for users to specify an appropriate aggregate function. Besides, many significant groups that have great attractions to users in practice may be overlooked. To address these issues, the group skyline (GSky) query is formulated on the basis of a general definition of group dominance operator. While the existing GSky query algorithms are effective, there is still room for improvement in terms of progressiveness and efficiency. In this paper, we propose some new lemmas which facilitate direct generation of the GSky query results. Consecutively, we design a layered unit-based (LU) algorithm that applies a layered optimum strategy. Additionally, for the GSky query over the data that are dynamically produced and cannot be indexed, we propose a novel index-independent algorithm, called sorted-based progressive (SP) algorithm. The experimental results demonstrate the effectiveness, efficiency, and progressiveness of the proposed algorithms. By comparing with the state-of-the-art algorithm for the GSky query, our LU algorithm is more scalable and two orders of magnitude faster.

Given a high-order, large-scale and sparse data from big data and industrial applications, how can we acquire useful patterns in a real-time and low memory overhead manner? Sparse Non-negative tensor factorization (SNTF) possesses high-order representation, non-negativity and dimension reduction inherence. Thus, SNTF has become a useful tool to represent and analyze the sparse data, which has been incorporated with extra contextual information, i.e., time and location, etc, more than the matrix, which can only model the 2 ways data. However, current SNTF techniques suffer from a) non-linear time and space overhead, b) intermediate data explosion, and c) inability on GPU and multi-GPU. To address these issues, a single-thread-based SNTF is proposed, which involves the feature elements rather than on the whole factor matrices, and can avoid the forming of large-scale intermediate matrices. Then, a CUDA parallelizing single-thread-based SNTF (CUSNTF) model is proposed for industrial applications on GPU and multi-GPU (MCUSNTF). Thus, CUSNTF has linear computing and space complexity, and linear communication cost on multi-GPU. We implement CUSNTF and MCUSNTF on 8 P100 GPUs, and compare it with state-of-the-art parallel and distributed methods. Experimental results from several industrial datasets demonstrate that the linear scalability and efficiency of CUSNTF.

Predicting vehicle flows is of great importance to traffic management and public safety in smart cities, and very challenging as it is affected by many complex factors, such as spatio-temporal dependencies with external factors (e.g., holidays, events and weather). Recently, deep learning has shown remarkable performance on traditional challenging tasks, such as image classification, due to its powerful feature learning capabilities. Some works have utilized LSTMs to connect the high-level layers of 2D convolutional neural networks (CNNs) to learn the spatio-temporal features, and have shown better performance as compared to many classical methods in traffic prediction. However, these works only build temporal connections on the high-level features at the top layer while leaving the spatio-temporal correlations in the low-level layers not fully exploited. In this paper, we propose to apply 3D CNNs to learn the spatio-temporal correlation features jointly from low-level to high-level layers for traffic data. We also design an end-to-end structure, named as MST3D, especially for vehicle flow prediction. MST3D can learn spatial and multiple temporal dependencies jointly by multiple 3D CNNs, combine the learned features with external factors and assign different weights to different branches dynamically. To the best of our knowledge, it is the first framework that utilizes 3D CNNs for traffic prediction. Experiments on two vehicle flow datasets Beijing and New York City have demonstrated that the proposed framework, MST3D, outperforms the state-of-the-art methods.

With the development of the economy, products are significantly enriched, and uncertainty has been their inherent quality. The probabilistic dynamic skyline (PDS) query is a powerful tool for customers to use in selecting products according to their preferences. However, this query suffers several limitations: it requires the specification of a probabilistic threshold, which reports undesirable results and disregards important results; it only focuses on the objects that have large dynamic skyline probabilities; and, additionally, the results are not stable. To address this concern, in this paper, we formulate an uncertain dynamic skyline (UDS) query over a probabilistic product set. Furthermore, we propose effective pruning strategies for the UDS query, and integrate them into effective algorithms. In addition, a novel query type, namely the top$k$favorite probabilistic products (TFPP) query, is presented. The TFPP query is utilized to select$k$products which can meet the needs of a customer set at the maximum level. To tackle the TFPP query, we propose a TFPP algorithm and its efficient parallelization. Extensive experiments with a variety of experimental settings illustrate the efficiency and effectiveness of our proposed algorithms.

Query processing over uncertain data has gained growing attention, because it is necessary to deal with uncertain data in many real-life applications. In this paper, we investigate skyline queries over uncertain data in distributed environments (DSUD query) whose research is only in an early stage. The state-of-the-art algorithm, called e-DSUD algorithm, is designed for processing this query. It has the desirable characteristics of progressiveness and minimum bandwidth consumption. However, it still needs to be perfected in three aspects. (1) Progressiveness. Each time it only returns one query result at most. (2) Efficiency. There are a significant amount of redundant I/O cost and numerous iterations which causes a long total query time. (3) Universality. It is restricted to the case where local skyline tuples are incomparability. To address these concerns, we first present a detailed analysis of the e-DSUD algorithm and then develop an improved framework for the DSUD query, namely IDSUD. Based on the new framework, we propose an adaptive algorithm, called ADSUD, for the DSUD query. In the algorithm, we redefine the approximate global skyline probability and choose local representative tuples due to minimum probabilistic bounding rectangle adaptively. Furthermore, we design a progressive pruning method and apply the reuse mechanism to improve its efficiency. The results of extensive experiments verify the better overall performance of our algorithm than the e-DSUD algorithm.