Recent advancements in Large Language Models (LLMs) and the proliferation of Text-Attributed Graphs (TAGs) across various domains have positioned LLM-enhanced TAG learning as a critical research area. However, the field faces significant challenges: (1) the absence of a unified framework to systematize the diverse optimization perspectives, and (2) the lack of a robust method capable of handling real-world TAGs, which often suffer from text and edge sparsity, leading to suboptimal performance. To address these challenges, we propose UltraTAG, a unified pipeline for LLM-enhanced TAG learning. UltraTAG provides a comprehensive and domain-adaptive framework that not only organizes existing methodologies but also paves the way for future advancements. Building on this framework, we propose UltraTAG-S, a robust instantiation designed to tackle sparsity issues in real-world TAGs. UltraTAG-S employs LLM-based text propagation and augmentation to mitigate text sparsity, while leveraging LLM-augmented node selection based on PageRank and edge reconfiguration strategies to address edge sparsity. Our experiments demonstrate UltraTAG-S significantly outperforms existing baselines, achieving improvements of 2.12% and 17.47% in ideal and sparse settings, respectively. Moreover, as the data sparsity ratio increases, the performance improvement of UltraTAG-S also rises.

Graph Neural Networks (GNNs) have become a pivotal framework for modeling graph-structured data, enabling a wide range of applications from social network analysis to molecular chemistry. By integrating large language models (LLMs), text-attributed graphs (TAGs) enhance node representations with rich textual semantics, significantly boosting the expressive power of graph-based learning. However, this synergy introduces critical vulnerabilities in both topology and text. Although specialized attack methods have been designed for each of these aspects, no work has yet unified them into a comprehensive approach. In this work, we propose the Interpretable Multi-Dimensional Graph Attack (IMDGA), a human-centric framework orchestrating multi-level perturbations across graph structure and textual features. IMDGA utilizes three tightly integrated modules to craft attacks that balance interpretability and impact, enabling a deeper understanding of Graph-LLM vulnerabilities. Through rigorous theoretical analysis and comprehensive empirical evaluations on diverse datasets and architectures, IMDGA demonstrates superior interpretability, attack effectiveness, stealthiness, and robustness compared to existing methods. By exposing these underexplored semantic vulnerabilities, our work offers valuable insights for improving Graph-LLM resilience. Our code is available at https://github.com/bwfan-bit/IMDGA.

Spatial crowdsourcing platforms have become indispensable in addressing the evolving needs of modern society. These platforms facilitate essential services such as ride-sharing, on-demand food delivery, and efficient parcel distribution. However, the uneven distribution of workers and requests under a single-platform setting may lead to the loss of tasks. To address this issue, we introduce the Cross Online Matching (COM) problem, which facilitates collaboration among multiple platforms. We first propose DemCOM and RamCOM, which adopt deterministic greedy and randomized trade-off strategies, respectively. Furthermore, we develop a Utility-Distribution Aware Cooperative Online Matching (UDACOM) algorithm that leverages supply-demand relationships to optimize decision-making. Theoretical analysis confirms the competitive ratios of our algorithms. Validated on both real and synthetic datasets, our approach significantly outperforms state-of-the-art methods, achieving a 5% increase in total revenue and a 3% improvement in the successful matching rate.

Important communities are densely connected subgraphs containing vertices with high importance values, which have received wide attention recently. However, existing methods, predominantly based on the$k$-core model, suffer from limitations such as rigid degree constraints and suboptimal density, often failing to capture highly important vertices. To address these limitations, we propose a new community model based on pseudoarboricity that guarantees near-optimal density while preserving important vertices. Further, we introduce a novel problem of Psudoarboricity-based Skyline Important Community (PSIC), which uniquely treats density and importance as independent attributes. To efficiently address PSIC, we first devise a basic algorithm climbStairs, which iteratively refines communities by peeling vertices with low importance. To boost efficiency, we develop an advanced algorithm DivAndCon, which employs a recursive divide-and-conquer strategy combined with weight-based and pseudoarboricity-based pruning techniques, significantly reducing the search space. For massive graphs with billions of edges, inspired by a recursive division tree, we develop several parallel algorithms utilizing thread-pool and free-synchronization mechanism. Finally, we conduct extensive experiments on 10 real-world networks, and the results demonstrate the superiority of our solutions in terms of effectiveness, efficiency, and scalability.

Electrical closeness centrality is a classical and robust graph centrality measure. However, existing algorithms for computing electrical closeness centrality are often computationally expensive for large graphs, as they require determining the diagonal elements of the pseudo-inverse of the graph Laplacian matrix, denoted as$L^\dagger$. To address this challenge, we propose novel solutions for approximating$L^\dagger$by establishing a connection with the inverse of a Laplacian submatrix$L_{v}$, which is obtained by removing the$v$-th row and column from the original Laplacian matrix$L$. A key advantage of this connection is that$L_{v}^{-1}$admits various insightful combinatorial interpretations. Specifically, we present two novel interpretations of$L_{v}^{-1}$based on spanning trees and loop-erased random walks, which facilitate the development of efficient sampling algorithms. Building upon these theoretical insights, we introduce two algorithms for efficiently approximating electrical closeness centrality. We extensively evaluate the performance of our algorithms on five real-world datasets. Experimental results demonstrate that our approaches significantly outperform state-of-the-art methods by several orders of magnitude in both running time and estimation accuracy.

In recent years, Graph Neural Networks (GNNs) have made significant advances in processing structured data. However, most of them primarily adopted a model-centric approach, which simplifies graphs by converting them into undirected formats and emphasizes model designs. This approach is inherently limited in real-world applications due to the unavoidable information loss in simple undirected graphs and the model optimization challenges that arise when exceeding the upper bounds of this sub-optimal data representational capacity. As a result, there has been a shift toward data-centric methods that prioritize improving graph quality and representation. Specifically, various types of graphs can be derived from naturally structured data, including heterogeneous graphs, hypergraphs, and directed graphs. Among these, directed graphs offer distinct advantages in topological systems by modeling causal relationships, and directed GNNs have been extensively studied in recent years. However, a comprehensive survey of this emerging topic is still lacking. Therefore, we aim to provide a comprehensive review of directed graph learning, with a particular focus on a data-centric perspective. Specifically, we first introduce a novel taxonomy for existing studies. Subsequently, we re-examine these methods from the data-centric perspective, with an emphasis on understanding and improving data representation. It demonstrates that a deep understanding of directed graphs and their quality plays a crucial role in model performance. Additionally, we explore the diverse applications of directed GNNs across 10+ domains, highlighting their broad applicability. Finally, we identify key opportunities and challenges within the field, offering insights that can guide future research and development in directed graph learning.

Temporal interactions form the crux of numerous real-world scenarios, thus necessitating effective modeling in temporal graph representation learning. Despite extensive research within this domain, we identify a significant oversight in current methodologies: the temporal-spatial dynamics in graphs, encompassing both structural and temporal coherence, remain largely unaddressed. In an effort to bridge this research gap, we present a novel framework termed Graph Representation learning enhanced by Periodic and Community Interactions (GRPCI). GRPCI consists of two primary mechanisms devised explicitly to tackle the aforementioned challenge. Firstly, to utilize latent temporal dynamics, we propose a novel periodicity-based neighborhood aggregation mechanism that underscores neighbors engaged in a periodic interaction pattern. This mechanism seamlessly integrates the element of periodicity into the model. Secondly, to exploit structural dynamics, we design a novel contrastive-based local community representation learning mechanism. This mechanism features a heuristic dynamic contrastive pair sampling strategy aimed at enhancing the modeling of the latent distribution of local com munities within the graphs. Through the incorporation of these two mechanisms, GRPCI markedly augments the performance of graph networks. Empirical evaluations, conducted via a temporal link prediction task across five real-life datasets, attest to the superior performance of GRPCI in comparison to existing state of-the-art methodologies. The results of this study validate the efficacy of GRPCI, thereby establishing a new benchmark for future research in the field of temporal graph representation learning. Our findings underscore the importance of considering both temporal and structural consistency in temporal graph learning, and advocate for further exploration of this paradigm.

A data lake maintains large amounts of heterogeneous data with different data schemas and query interfaces. Efficiently querying and analyzing the heterogeneous data enables users to gain more complete insights. In this article, we study a novel problem of distributed keyword search across heterogeneous data sources. Traditional distributed search algorithms generally require the predefined crossing edges connecting relevant data instances for communication between different sources, which is unpractical for the data lake due to the schema heterogeneity. To effectively perform keyword search over the data lake, we first introduce canonical graphs and then develop a best-first search algorithm called UnifySea, which explores the answers across different sources based on the unified identification of related instances. To further improve the query efficiency, we propose a novel incremental keyword search algorithm called DistSea, which just need to identify the promising relevant data between different sources. DistSea incrementally calculates the optimal answers based on locally partial evaluation. Equipped with several efficient pruning rules, DistSea reduces unpromising tree calculation across different sources. Experimental evaluations on six real-world benchmarks demonstrate the effectiveness, efficiency, and scalability of the proposed algorithms.

As a new distributed graph learning paradigm, Federated Graph Learning (FGL) facilitates collaborative model training across local systems while preserving data privacy. We review existing FGL approaches and categorize their optimization mechanisms into: (1) Server-Client (S-C), where clients upload local model parameters for server-side aggregation and global updates; (2) Client-Client (C-C), which allows direct exchange of information between clients and customizing their local training process. We reveal that C-C shows superior potential due to its refined communication structure. However, existing C-C methods broadcast redundant node representations, incurring high communication costs and privacy risks at the node level. To this end, we propose FedC4, which combines graph Condensation with C-C Collaboration optimization. Specifically, FedC4 employs graph condensation technique to refine the knowledge of each client's graph into a few synthetic embeddings instead of transmitting node-level knowledge. Moreover, FedC4 introduces three novel modules that allow the source client to send distinct node representations tailored to the target client's graph properties. Experiments on eight public real-world datasets show that FedC4 outperforms state-of-the-art baselines in both task performance and communication cost. Our code is now available on https://github.com/Ereshkigal1/FedC4.

Recently, graph neural network (GNN) has emerged as a powerful representation learning tool for graph-structured data. However, most approaches are tailored for undirected graphs, neglecting the abundant information in the edges of directed graphs (digraphs). In fact, digraphs are widely applied in the real world and confirmed to address heterophily challenges. Despite recent advancements, existing spatial- and spectral-based DiGNNs have limitations due to their complex learning mechanisms and reliance on high-quality topology, resulting in low efficiency and unstable performance. To address these issues, we propose Directed Random Walk (DiRW), a plug-and-play strategy for most spatial-based DiGNNs and also an innovative model which offers a new digraph learning paradigm. Specifically, it utilizes a direction-aware path sampler optimized from the perspectives of walk probability, length, and number in a weight-free manner by considering node profiles and topologies. Building upon this, DiRW incorporates a node-wise learnable path aggregator for generalized node representations. Extensive experiments on 9 datasets demonstrate that DiRW: (1) enhances most spatial-based methods as a plug-and-play strategy; (2) achieves SOTA performance as a new digraph learning paradigm. The source code and data are available at https://github.com/dhsiuu/DiRW.

Entity matching (EM) aims to identify whether two entities from different data sources refer to the same real-world entity. Most existing cross-modal EM assume that images have simple scenes containing few objects, or do not fully consider the cross-modal knowledge associated with entities. To support more practical application scenarios such as multi-modal knowledge graph integration and visual question answering in data lakes, we introduce our problem of semantic-driven EM across graph and images in this paper. Current semantically matching solutions over cross-modal data face the obstacle of low training efficiency, since their time complexity quadratically grows with the number of entities. To alleviate this issue, we present a novel framework (namely CrossETR) that follows an exploration-then-refinement paradigm. Firstly, a candidate exploration policy is proposed to boost the training efficiency. It explores candidate pairs according to entity correlations and captures structural semantics by adaptive sampling the most informative neighborhood subgraphs. Secondly, the cross-modal entity representations are refined to break modality heterogeneity to support unsupervised matching prediction. Extensive experimental evaluations on three publicly available benchmarks demonstrate the superiority of CrossETR over state-of-the-art approaches in terms of effectiveness and efficiency. Furthermore, a case study highlights that our proposed semantic-driven EM is promising to improve the performance of downstream tasks such as multi-modal knowledge graph integration.

Entity matching (EM) aims to identify equivalent entities across different data sources. Current EM assumes that these data are either homogeneous with aligned schema or heterogeneous but can be transformed into a unified modality. There is an urgent need to consider the entities with different modalities to support practical application scenarios over data lakes such as multi-modal data integration and recommendation system. It is impractical to unify their data modalities. To support EM on heterogeneous entity with different data formats and modalities, we propose cross-modal entity matching in this paper. Inspired by the promising performance achieved by recent pre-trained models, we perform cross-modal entity matching by prompt-tuning pre-trained multi-modal large models (MMLMs) in an unsupervised manner. However, the prompt-tuning faces three challenging issues: (i) objective gap between pre-training and tuning of MMLMs; (ii) data modality gap between the inputs of MMLMs and our matching task; (iii) prompt efficiency on large data. Therefore, we firstly propose a novel EM framework (namely, CrossEM) that addresses cross-modal EM as a matching probability problem with specific prompt-tuning. Secondly, two alternative prompt generation methods are designed to extract structural knowledge from heterogeneous data to overcome the data modality gap with pre-trained models. Thirdly, we present an improved matching framework (namely, CrossEM+) to boost the prompt efficiency on large heterogeneous data. Experimental evaluations verify that our methods significantly outperform the state-of-the-art approaches on three benchmarks. Furthermore, our case study highlights the considerable potential of cross-modal EM in improving the performance of downstream tasks, thereby benefitting a wider range of research areas.

Mining cohesive subgraphs in attributed graphs is an essential problem in the domain of graph data analysis. The integration of fairness considerations significantly fuels interest in models and algorithms for mining fairness-aware cohesive subgraphs. Notably, the relative fair clique emerges as a robust model, ensuring not only comprehensive attribute coverage but also greater flexibility in distributing attribute vertices. Motivated by the strength of this model, we for the first time pioneer an investigation into the identification of the maximum relative fair clique in large-scale graphs. We introduce a novel concept of colorful support, which serves as the foundation for two innovative graph reduction techniques. These techniques effectively narrow the graph's size by iteratively removing edges that do not belong to relative fair cliques. Furthermore, a series of upper bounds of the maximum relative fair clique size is proposed by incorporating consideration of vertex attributes and colors. The pruning techniques derived from these upper bounds can significantly trim unnecessary search space during the branch-and-bound procedure. Adding to this, we present a heuristic algorithm with a linear time complexity, employing both a degree-based greedy strategy and a colored degree-based greedy strategy to identify a larger relative fair clique. This heuristic algorithm can serve a dual purpose by aiding in branch pruning, thereby enhancing overall search efficiency. Extensive experiments conducted on six real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

With the explosive growth of video data, efficient video analysis technology has garnered widespread attention. Existing online methods train proxy neural networks upon query arrival and use these networks to scan the entire dataset, guiding the invocation of the expensive deep neural network. While index-based methods advance this process to the index-building stage, significantly reducing the time overhead of video queries. However, the data to query often presents a long-tail distribution, and different types of queries are sensitive to different parts of the distribution. Since the index-based methods cannot predict the queries, they can only provide ad-hoc proxy score generating strategies. This paper proposes a query-aware video analysis framework, QaVA, to improve query performance further. QaVA retains the time-consuming, query-independent semantic extraction process during the index-building stage and employs a tunable lightweight adapter network to accurately and quickly focus on the data parts most relevant to the query after it arrives. Meanwhile, QaVA can automatically tune the training strategy of the adapter network by analyzing the data access pattern of historical queries, thus meeting the needs of general users. Experimental results demonstrate that QaVA can significantly reduce the cost of various queries across multiple datasets, and can speed up query processing by up to$9.2\times$compared to the most advanced index-based method. Our code is available: https://github.com/InkosiZhong/QaVA.

With the explosive growth of online service platforms, an increasing number of people and enterprises are undertaking personal and professional tasks online. In real applications such as trip planning and online marketing, planning sessions for a sequence of activities or services will enable social users to receive the optimal services, improving their experience and reducing the cost of their activities. These online platforms are heterogeneous, including different types of services with different attributes. However, the problem of session planning over heterogeneous platforms has not been studied so far. In this paper, we propose a Motivation-Aware Session Planning (MASP) framework for session planning over heterogeneous social platforms. Specifically, we first propose a novel HeterBERT model to handle the heterogeneity of items at both type and attribute levels. Then, we propose to predict user preference using the motivations behind user activities. Finally, we propose an algorithm together with its optimisations for efficient session generation. The extensive tests prove the high effectiveness and efficiency of MASP.

The q-parameterized magnetic Laplacian serves as the foundation of directed graph (digraph) convolution, enabling this kind of digraph neural network (MagDG) to encode node features and structural insights by complex-domain message passing. Despite their success, limitations still exist: (1) The performance of MagDGs depends on selecting an appropriate q-parameter to construct suitable graph propagation equations in the complex domain. This parameter tuning limits model flexibility and significantly increases manual effort. (2) Most approaches treat all nodes with the same complex-domain propagation and aggregation rules, neglecting their unique digraph contexts. This oversight results in sub-optimal performance. To address the above issues, we propose two key techniques: (1) MAP is crafted to be a plug-and-play complex-domain propagation optimization strategy, enabling seamless integration into any MagDG to improve predictions while enjoying high running efficiency. (2) MAP++ is a new digraph learning framework, further incorporating a learnable mechanism to achieve adaptively edge-wise propagation and node-wise aggregation in the complex domain for better performance. Extensive experiments on 12 datasets demonstrate that MAP enjoys flexibility for it can be incorporated with any MagDG, and scalability as it can deal with web-scale digraphs. MAP++ achieves SOTA predictive performance on 4 different downstream tasks.

The classic clique model has properties of hereditaries and cohesiveness. Here hereditaries means a subgraph of a clique is still a clique. Counting small cliques in a graph is a fundamental operation of numerous applications. However, the clique model is often too restrictive for practical use, leading to the focus on other relaxed-cliques with properties of hereditaries and cohesiveness. To address this issue, we investigate a new problem of counting general hereditary cohesive subgraphs (HCS). All subgraphs with properties of hereditaries and cohesiveness can be called a kind of HCS. To count HCS, we propose a general framework called HCSPivot, which can be applied to count all kinds of HCS. HCSPivot can count most HCS combinatorially without explicitly listing them. Two additional noteworthy features of HCSPivot are its ability to (1) simultaneously count HCS of any size and (2) simultaneously count HCS for each node or each edge. Based on our HCSPivot framework, we propose two novel algorithms with several carefully designed pruning techniques to count s-defective cliques and s-plexes, which are two specific types of HCS. We conduct extensive experiments on 8 large real-world graphs, and the results demonstrate the high efficiency and effectiveness of our solutions.

Identifying the maximum edge biclique in bipartite graphs, a complete bipartite subgraph with the largest number of edges, plays a crucial role in uncovering densely-connected communities and has significant applications in domains such as recommendation systems and biological network analysis. However, this problem is NP-hard, and existing methods face inefficiencies both in practice and theory. In this paper, we propose two novel algorithms with distinct branching strategies and provable time guarantees for solving the maximum edge biclique search problem. The first is a refined pivot-based branching algorithm that systematically exploits vertex adjacency relationships to bound the search for the maximum edge biclique, achieving a time complexity of O ( m 1.348 n ). The second is a cover-based algorithm that uncovers a novel duality between maximal bicliques and minimal vertex covers in bipartite graphs, attaining a complexity of O ( m 1.381 n ). To the best of our knowledge, these two algorithms achieve the best-known worst-case time complexities for this problem. Notably, while the cover-based algorithm has a marginally higher theoretical complexity, it typically provides superior practical performance on dense graphs due to its inherent pruning efficiency. To further enhance performance, we introduce advanced pruning techniques, including polynomial-time solvable graph cases, neighbor and non-neighbor constraint-based upper bounds, vertex cover constraint-driven upper bounds, heuristic prioritization, and an improved progressive bounding approach. Additionally, we propose a hybrid framework that deploys the pivot-based approach for sparse graph regions and the cover-based approach for dense regions, balancing efficiency across varying graph structures. Extensive experiments on 12 real-world bipartite graphs demonstrate that our hybrid framework outperforms the state-of-the-art baseline by up to four orders of magnitude and achieves speedups of several times to orders of magnitude over the pivot-based approach on dense graphs.

Using a large training dataset to train a big and powerful model -- a typical practice in modern deep learning, often suffers from two major problems: the expensive and slow training process and the error-prone labels. The existing approaches, targeting either speeding up the training by selecting a subset of representative training instances (subset selection) or eliminating the negative effect of mislabels during training (mislabel detection), do not perform well in this scenario due to overlooking one of these two problems. To fill this gap, we propose Deem, a novel data-efficient framework that selects a subset of representative training instances under label uncertainty. The key idea is to leverage the metadata produced during deep learning training, e.g., training losses and gradients, to estimate the label uncertainty and select the representative instances. In particular, we model the problem of subset selection under uncertainty as a problem of finding a subset that closely approximates the gradient of the whole training data set derived on soft labels. We show that it is an NP-hard problem with submodular property and propose a low complexity algorithm to solve this problem with an approximate ratio. Training on this small subset thus improves the training efficiency while guaranteeing the model's accuracy. Moreover, we propose an efficient strategy to dynamically refine this subset during the iterative training process. Extensive experiments on 6 datasets and 10 baselines demonstrate that Deem accelerates the training process up to 10X without sacrificing the model accuracy.

In this paper, we study a problem of index maintenance on evolving graphs for effective resistance computation. Unlike an existing matrices-based index, we show that the index can be efficiently maintained by directly preserving samples of random walks and loop-erased walks. This approach not only enables efficient storage and rapid query response but also supports effective maintenance. We propose a novel approach to convert edge updates into landmark node updates. Building upon this, we present two new update algorithms for random walk and loop-erased walk samples respectively. Both algorithms update samples without requiring complete resampling, ensuring accuracy and high efficiency. A particularly challenging and innovative technique involves updating loop-erased walks. Here we develop a novel and powerful cycle decomposition technique for loop-erased walks, enabling us to update samples at the cycle level rather than the node level, significantly enhancing efficiency. Furthermore, we show that both of our methods achieve an Õ (1) time complexity per edge update in real-world graphs under a mild assumption. We conduct extensive experiments using 10 large real-world datasets to evaluate the performance of our approaches. The results show that our best algorithm can be up to two orders of magnitude faster than the baseline methods.

Resistance distance computation is a fundamental problem in graph analysis, yet existing random walk-based methods are limited to approximate solutions and suffer from poor efficiency on small-treewidth graphs (e.g., road networks). In contrast, shortest-path distance computation achieves remarkable efficiency on such graphs by leveraging cut properties and tree decompositions. Motivated by this disparity, we first analyze the cut property of resistance distance. While a direct generalization proves impractical due to costly matrix operations, we overcome this limitation by integrating tree decompositions, revealing that the resistance distance r(s,t) depends only on labels along the paths from s and t to the root of the decomposition. This insight enables compact labelling structures. Based on this, we propose TreeIndex, a novel index method that constructs a resistance distance labelling of size O(n • h G ) in O(n • h G 2 • d max ) time, where h G (tree height) and d max (maximum degree) behave as small constants in many real-world small-treewidth graphs (e.g., road networks). Our labelling supports exact single-pair queries in O(h G ) time and single-source queries in O(n • h G ) time. Extensive experiments show that TreeIndex substantially outperforms state-of-the-art approaches. For instance, on the full USA road network, it constructs a 405 GB labelling in 7 hours (single-threaded) and answers exact single-pair queries in 10 -3 seconds and single-source queries in 190 seconds-the first exact method scalable to such large graphs.

Community search in heterogeneous graphs is fundamental to applications such as expert team formation and scholarly collaboration. Many existing studies leverage meta-paths, which are sequences of node and edge types, to capture semantic relationships in heterogeneous graphs. However, most of them only consider the existence of meta-path instances, overlooking their frequency and thus failing to capture relationship strength. This limitation can result in communities that include nodes with numerous but weak relations. To capture the strength of relationships in heterogeneous graphs, we define the Strong Community (StrCom) model, which evaluates the strength between users based on the number of connecting meta-path instances. Building upon this model, we further propose the Budgeted Strong Community (BSC) problem by incorporating a size constraint. We provide theoretical analyses showing that the BSC problem is NP-hard and not in APX. To address this problem, we design three strategies-Shrink, Expand, and Hybrid-along with several optimization techniques to improve efficiency. Extensive experiments on large real-world datasets (e.g., DBLP, YAGO, DBpedia) demonstrate the effectiveness and efficiency of our approach. Specifically, our method achieves 3.49-107.09× higher PathSim scores for StrCom and two to five orders of magnitude higher scores for BSC compared to state-of-the-art baselines, demonstrating that the identified communities are both semantically coherent and structurally compact.

The densest subgraph (DS) search over a directed graph focuses on finding the subgraph with the highest density among all subgraphs. This problem has raised numerous applications, such as fraud detection and community detection. The state-of-the-art DS algorithms have prohibitively high costs or poor approximation ratios, making them unsuitable for practical applications. To address these dilemmas, in this paper, we propose a novel model called integral densest subgraph (IDS). We show that IDS can serve as a near-DS model that has a tight floor relationship with the density of the DS. To compute IDS, we first propose a novel flow network named (α,β)-dense network, based on which we design an exact network-flow algorithm GetIDS with O(p • log |V| • |E| 1.5 ) time complexity, where p is typically a small constant in real-world graphs. Additionally, we propose several non-trivial pruning techniques to further improve the efficiency. Subsequently, we propose a novel (2 + ε)-approximation algorithm MultiCore with near-linear time complexity, providing a good approximation guarantee with high efficiency. Finally, our extensive experiments on 10 real-world graphs demonstrate the effectiveness of the proposed IDS model, and the high efficiency and scalability of the proposed solutions.

Mining dense subgraphs in a bipartite graph is a fundamental task in bipartite graph analysis, with numerous applications in community detection, fraud detection, and e-commerce recommendation. Existing dense subgraph models, such as biclique, k -biplex, k -bitruss, and (α,β)-core, often face challenges due to their high computational complexity or limitations in effectively capturing the density of the graph. To overcome these issues, in this paper, we propose a new dense subgraph model for bipartite graphs, namely (α,β)-dense subgraph, designed to capture the density structure inherent in bipartite graphs. We show that all (α,β)-dense subgraphs are nested within each other, forming a hierarchical density decomposition of the bipartite graph. To efficiently compute the (α,β)-dense subgraph, we develop a novel network flow algorithm with a carefully-designed core pruning technique. The time complexity of our algorithm is O(|E|+|E(R)| 1.5 ), where |E| denotes the number of edges and |E(R)| is the number of edges of the pruned graph, often significantly smaller than |E|. Armed with this algorithm, we also propose a novel and efficient divide-and-conquer algorithm to compute the entire density decomposition of the bipartite graph within O(p ⋅ log d max ⋅ |E| 1.5 ) time, where p is typically a small constant in real-world bipartite graphs and d max is the maximum degree. Extensive experiments and case studies on 11 real-world datasets demonstrate the effectiveness of our (α,β)-dense subgraph model and the high efficiency and scalability of our proposed algorithms.

To fulfill the potential great value of unstructured documents, it is critical to extract structural data (e.g., attributes) from them, which can benefit various applications such as analytical SQL queries and decision-making. Multiple strategies, such as pre-trained language models (PLMs), can be employed for this task. However, these methods often struggle to achieve high-quality results, particularly when dealing with attribute extraction that requires intricate reasoning or semantic comprehension. Recently, large language models (LLMs) have proven to be effective in extracting attributes but incur substantial costs caused by token consumption, making them impractical for large-scale document set. To best trade off quality and cost, we present Doctopus, a system designed for accurate attribute extraction from unstructured documents with a user-specified cost constraint. Overall, Doctopus combines LLMs with non-LLM strategies to achieve a good tradeoff. First, the system employs an index-based approach to efficiently identify and process only relevant text chunks, thereby reducing the LLM cost. Afterwards, it further estimates the quality of multiple strategies for each attribute. Finally, based on the cost and estimated quality, Doctopus dynamically selects the optimal strategies through budget-aware optimization. We have built a comprehensive benchmark including 4 document sets with various characteristics and manually labeled ground truth using 1000 human hours. Extensive experiments on the benchmark show that compared with state-of-the-art baselines, Doctopus can improve the quality by 11% given the same cost constraint.

Recent studies have developed LLM-powered data systems that enable database-like analysis of unstructured text documents. While LLMs excel at attribute extraction from documents, their high computational costs and latency make extraction operations the primary performance bottleneck. Existing systems typically adopt traditional relational database query optimization strategies, which prove ineffective in minimizing LLM-related expenses. To fill this gap, we propose DocDB, a prototype system that features a bunch of novel optimization strategies designated to unstructured document analysis. First, we employ a two-level index to reduce LLM extraction costs by selectively retrieving and processing only text segments relevant to target attributes. Second, DocDB employs adaptive execution, generating document-specific plans to minimize LLM extraction frequency based on varying per-document attribute extraction costs. With a real-life scenario, we demonstrate that DocDB allows users to analyze unstructured documents accurately and affordably using SQL-like queries. The corresponding video is available at https://youtu.be/8yDIKOBHIOg.

Federated graph learning (FGL) is a promising distributed training paradigm for graph neural networks across multiple local systems without direct data sharing. This approach inherently involves large-scale distributed graph processing, which closely aligns with the challenges and research focuses of graph-based data systems. Despite the proliferation of FGL, the diverse motivations from real-world applications, spanning various research backgrounds and settings, pose a significant challenge to fair evaluation. To fill this gap, we propose OpenFGL, a unified benchmark designed for the primary FGL scenarios: Graph-FL and Subgraph-FL. Specifically, OpenFGL includes 42 graph datasets from 18 application domains, 8 federated data simulation strategies that emphasize different graph properties, and 5 graph-based downstream tasks. Additionally, it offers 18 recently proposed SOTA FGL algorithms through a user-friendly API, enabling a thorough comparison and comprehensive evaluation of their effectiveness, robustness, and efficiency. Our empirical results demonstrate the capabilities of FGL while also highlighting its potential limitations, providing valuable insights for future research in this growing field, particularly in fostering greater interdisciplinary collaboration between FGL and data systems.

Truss decomposition is a fundamental approach in graph theory that focuses on uncovering cohesive subgraphs within networks. However, many networks involve groupwise rather than pairwise relationships and are often represented as hypergraphs. Modeling and capturing k-truss in hypergraphs is essential for uncovering tight-knit relationships in such multi-relational networks. In this paper, we tackle the problem of truss decomposition in hypergraph. A hyper k-truss is a subgraph in which each node is part of at least k hyper-triangles. We first introduce a framework for hyper-truss decomposition and determine that the most time-consuming component is counting hyper-triangles. To count all hyper-triangles efficiently, we propose an edge-iterator algorithm. To further reduce redundant computations, we present an improved algorithm that combines edge-iterator and node-iterator techniques to prune non-promising nodes. Next, to handle common nodes in hypergraphs, we develop a novel prefix forest technique to encode all hyperedges and count triangles within this prefix forest. We also propose several optimization strategies that reorder nodes and hyperedges to improve work balancing. Finally, we conduct extensive experiments on real-world hypergraph datasets, demonstrating the efficiency and effectiveness of our algorithms.

Most recently, researchers have started building large language models (LLMs) powered data systems that allow users to analyze unstructured text documents like working with a database because LLMs are very effective in extracting attributes from documents. In such systems, LLM-based extraction operations constitute the performance bottleneck of query execution due to the high monetary cost and slow LLM inference. Existing systems typically borrow the query optimization principles popular in relational databases to produce query execution plans, which unfortunately are ineffective in minimizing LLM cost. To fill this gap, we propose QUEST, which features a bunch of novel optimization strategies for unstructured document analysis. First, we introduce an index-based strategy to minimize the cost of each extraction operation. With this index, QUEST quickly retrieves the text segments relevant to the target attributes and only feeds them to LLMs. Furthermore, we design an evidence-augmented retrieval strategy to reduce the possibility of missing relevant segments. Moreover, we develop an instance-optimized query execution strategy: because the attribute extraction cost could vary significantly document by document, QUEST produces different plans for different documents. For each document, QUEST produces a plan to minimize the frequency of attribute extraction. The innovations include LLM cost-aware operator ordering strategies and an optimized join execution approach that transforms joins into filters. Extensive experiments on 3 real-world datasets demonstrate the superiority of QUEST, achieving 30%-6× cost savings while improving the F1 score by 10% -27% compared with state-of-the-art baselines.

With the development of AI, big data, and mobile communication, intelligent transportation has become popular in recent years. Path planning is a typical topic of intelligent transportation, attracting significant attention from researchers. However, existing studies only focus on the path planning of a single platform, which may lead to unexpected traffic congestion. This is because multiple platforms can provide route planning services, the optimal planning calculated by one single platform may be not good in practice, since multiple platforms may lead the users to the same roads, which causes unexpected traffic congestion. Although in the view of each platform, the planning is optimal. Fortunately, with the rise of data sharing and cross-platform cooperation, the data silos between different platforms are gradually being broken. Based on this, we proposeCooperativeGlobalPathPlanning(CGPP) framework to overcome the above shortcoming. CGPP allows the path planning request target platform to send some queries to cooperative platforms to optimize its path planning results. Such queries should be “easy” enough to answer, and the query frequency should be small. Based on the above principle, we design a query decision model based on multi-agent reinforcement learning in CGPP framework to decide the query range and query frequency. We design action and reward specifically for the CGPP problem. Furthermore, we propose mechanisms to enhance query precision and reduce query overhead. Specifically, the Self-adjusting Query Area(SQA) concept allows refining query parameters, while the Query Reuse Optimization(QRO) algorithm aims to minimize the number of queries. To solve potential overestimation problems in queries, we propose a Distance-based Outer Query (DB-oq) and Distance-Based Vehicle Count Estimation (DB-VCE) Model. To address the issue that the time interval computed by the QRO algorithm might not fully adapt to dynamic traffic environments, we propose the Temporal Sequence Historical Integration for Time Interval Prediction(TSHI-TIP) algorithm. Extensive experiments on real and synthetic datasets confirm the effectiveness and efficiency of our algorithms.

Graphs serve as an essential data structure to model complex relationships in a variety of applications, such as social networks, web graphs, and chemical informatics. Due to the high cost of maintaining large-scale graph data and executing graph queries, data owners often outsource their graph data to a third-party service provider for graph processing. In this scenario, it is crucial to ensure the integrity of query results, as the provider may have the incentive to return only partial or tampered results to save computing resources or serve their own interests. Blockchain, as a promising solution for secure data storage and retrieval, opens up new opportunities for data management in such scenarios. To scale the blockchain, existing studies have concentrated on using off-chain storage while ensuring the integrity of query results for key-value data in hybrid-storage blockchain architectures. To the best of our knowledge, there is no work to enable the blockchain to support subgraph matching queries. In this paper, we first study the problem of authenticated subgraph matching queries. Traditional subgraph matching algorithms follow the filtering-searching paradigm. The main challenge is to design an Authenticated Data Structure (ADS) and aggregation algorithm that efficiently aggregates non-results for verification during the filtering-searching process. We first propose a vertex-based scheme - the novel ADS MELTree can generate candidate vertices and aggregate non-resulting vertices in the filtering phase, while the aggregation algorithm AMatching can aggregate invalid partial results in the search phase. Furthermore, we propose the bidirectional search aggregation algorithm AMatching* and ADS MVPTree to reduce the computational cost in the search phase and to reduce the on-chain storage cost. In addition, we propose a novel path-based scheme to enhance the aggregation of non-results and accelerate the processing. We design the path-based ADS MPETree for generating candidate paths and aggregating non-resulting paths, and the aggregation algorithm PMatching for efficiently aggregating invalid partial results one path at a time. The results of extensive experiments on five real-world graphs demonstrate the efficiency of our proposed ADSs and aggregation algorithms.

A colorful star motif is a star-shaped graph where any two nodes have different colors. Counting the colorful star motif can help to analyze the structural properties of real-life colorful graphs, model higher-order clustering, and accelerate the mining of the densest subgraph exhibiting$h$-clique characteristics in graphs. In this manuscript, we introduce the concept of colorful$h$-star in a colored graph and proposes two higher-order cohesive subgraph models, namely colorful$h$-star core and colorful$h$-star truss. We show that the colorful$h$-stars can be counted and updated very efficiently using a novel dynamic programming (DP) algorithm. Based on the proposed DP algorithm, we develop a colorful$h$-star core decomposition algorithm which takes$O(h m)$time,$O(h n+m)$space; and a colorful$h$-star truss decomposition algorithm which takes$O(h m^{1.5})$time,$O(hm)$space, where$m$and$n$denote the number of edges and nodes of the graph respectively. Moreover, we also propose a graph reduction technique based on our colorful$h$-star core model to accelerate the computation of the approximation algorithm for$ h$-clique densest subgraph mining. The results of comprehensive experiments on 11 large real-world datasets demonstrate the efficiency, scalability and effectiveness of the proposed algorithms.

Influence maximization (IM) aims to identify$k$vertices that maximize influence spread across a network. While well-studied in regular graphs, IM in hypergraphs presents unique challenges: conventional graph-based IM methods fail to capture hypergraph-specific structural properties, and existing hypergraph IM algorithms lack theoretical guarantees for time complexity and approximation quality. We address these gaps withHyperIM, a novel algorithm leveraging stratified sampling to generate random reversible reachable sets for efficient seed selection. Our key innovation lies in dual-perspective stratified sampling: assigning sampling probabilities based on vertex structural properties while applying size-adaptive sampling strategies. This approach optimizes seed selection, reduces computational costs, and provides rigorous theoretical guarantees. We further proposeHyperIM_BRR, which optimizes the required number of reversible reachable sets, achieving substantial cost reduction without sacrificing accuracy. Extensive experiments on real-world hypergraphs demonstrate that our algorithms significantly outperform state-of-the-art methods, delivering faster execution times and superior influence spread.

Given a dataset with incomplete data (e.g., missing values), training a machine learning model over the incomplete data requires two steps. First, it requires a data-effective step that cleans the data in order to improve the data quality (and the model quality on the cleaned data). Second, it requires a data-efficient step that selects a core subset of the data (called coreset) such that the trained models on the entire data and the coreset have similar model quality, in order to save the computational cost of training. The first-data-effective-then-data-efficient methods are too costly, because they are expensive to clean the whole data; while the first-data-efficient-then-data-effective methods have low model quality, because they cannot select high-quality coreset for incomplete data. In this article, we investigate the problem of coreset selection over incomplete data for data-effective and data-efficient machine learning. The essential challenge is how to model the incomplete data for selecting high-quality coreset. To this end, we propose the GoodCore framework towards selecting a good coreset over incomplete data with low cost. To model the unknown complete data, we utilize the combinations of possible repairs as possible worlds of the incomplete data. Based on possible worlds, GoodCore selects an expected optimal coreset through gradient approximation without training ML models. We formally define the expected optimal coreset selection problem, prove its NP-hardness, and propose a greedy algorithm with an approximation ratio. To make GoodCore more efficient, we propose optimization methods that incorporate human-in-the-loop imputation or automatic imputation method into our framework. Moreover, a group-based strategy is utilized to further accelerate the coreset selection with incomplete data given large datasets. Experimental results show the effectiveness and efficiency of our framework with low cost.

Cross-Domain Sequential Recommendation (CDSR) aims to enhance personalized user experiences by leveraging user behaviors across multiple domains. Existing methods primarily focus on fusing information from various domains and modeling global user preferences, but often struggle with negative transfer, where knowledge from one domain impairs recommendation performance in another. For example, a user may enjoy watching sports games in the video domain but have no interest in participating in sports activities. Consequently, this interest does not extend to purchasing related sports gear. In such cases, a recommendation system suggesting sports gear based on the user’s viewing preferences may not elicit a positive response. To tackle this issue, we propose a novel method called Multi-Interest Bridge Recommender (MIBR). In light of the cross-domain scenario, where user preferences are not entirely consistent across domains, we design a Multi-Interest Extraction (MIE) module to capture the diversity of user interests based on a soft clustering approach. In the meantime, we design a cross-domain bridging (CDB) module, with the goal of mitigating the issue of negative transfer. CDB leverages the extracted interests as a bridge for inter-domain information transfer, enabling each domain to adaptively extract relevant information from diverse interests while ignoring unrelated ones. Extensive experiments on three popular datasets reveal MIBR’s significant superiority over baselines, e.g., with up to a 59.27% uplift in terms of HR@10 over C2DSR on the Movie-Book dataset.

Industrial-scale linear assignment problems (LAPs) are frequently encountered in various industrial scenarios, e.g., asset allocation within the domain of credit management. However, optimization algorithms for such problems (e.g., PJ-ADMM) are highly sensitive to hyper-parameters. Existing solving systems rely on empirical parameter selection, which is challenging to achieve convergence and extremely time-consuming. Additionally, the resulting parameter rules are often inefficient. To alleviate this issue, we propose RL-ISLAP, an efficient and lightweight Reinforcement Learning framework for Industrial-Scale Linear Assignment Problems. We formulate the hyper-parameter selection for PJ-ADMM as a sequential decision problem and leverage reinforcement learning to enhance its convergence. Addressing the sparse reward challenge inherent in learning policies for such problems, we devise auxiliary rewards to provide dense signals for policy optimization, and present a rollback mechanism to prevent divergence in the solving process. Experiments on OR-Library benchmark demonstrate that our method is competitive to SOTA stand-alone solvers. Furthermore, the scale-independent design of observations enables us to transfer the acquired hyper-parameter policy to a scenario of LAPs in varying scales. On two real-world industrial-scale LAPs with up to 10 millions of decision variables, our proposed RL-ISLAP achieves solutions of comparable quality in 2/3 of the time when compared to the SOTA distributed solving system employing fine-tuned empirical parameter rules.

Graph embedding has become a powerful tool for learning latent representations of nodes in a graph. Despite its superior performance in various graph-based machine learning tasks, serious privacy concerns arise when the graph data contains personal or sensitive information. To address this issue, we investigate and develop graph embedding algorithms that satisfy local differential privacy (LDP). We introduce a novel privacy-preserving graph embedding framework, named PrivGE, to protect node data privacy. Specifically, we propose an LDP mechanism to obfuscate node data and utilize personalized PageRank as the proximity measure to learn node representations. Furthermore, we provide a theoretical analysis of the privacy guarantees and utility offered by the PrivGE framework. Extensive experiments on several real-world graph datasets demonstrate that PrivGE achieves an optimal balance between privacy and utility, and significantly outperforms existing methods in node classification and link prediction tasks.

Attributed Heterogeneous Information Networks (AHINs) amalgamate the advantages of attributed graphs (AGs) and heterogeneous information networks (HINs) to model intri-cate systems. Within this context, community search-aiming to identify the most probable community containing the queried ver-tex-has been extensively explored in AGs and HINs. However, existing methodologies fall short in simultaneously accommodating heterogeneous attributes and multiple meta-paths in AHINs, posing a substantial challenge in investigating community search within expansive AHINs. Recent studies highlight the efficacy of machine learning-based community search, offering enhanced flexibility and higher-quality communities in comparison to traditional structural-based methods. Yet, semi-supervised learning methods demand substantial labeled data and incur considerable memory and time costs when applied to large AHINs. To tackle these challenges, we propose a MK (Most-likely; K-sized) community search approach. This approach involves defining an MK community and leveraging Graph Neural Networks (GNNs) to amalgamate structures and attributes into a unified goodness metric. Our methodology involves training on local subgraphs sampled via guided random walks based on multiple meta-paths, circumventing the need for training on the entire graph. Moreover, attention-based GNNs adeptly learn meta-path weights to guide weighted walks in subsequent iterations. Additionally, self-training is employed to alleviate the labeling burden. We also demonstrate that pinpointing the location for the MK community is NP-hard and present a heuristic local search strategy that expedites the resolution process through rewriting. Ultimately, the convergence of iterations yields the solution. Extensive experiments conducted on four real-world datasets underscore that the MK framework significantly enhances both effectiveness and efficiency in community search within AHINs. Our code is publicly available at https://github.com/uucxuu/CSAH.

The prevalence of online query services in human life has attracted significant interest from the fields of economics and databases in determining appropriate pricing for such services. Simultaneously, the utilization of graph analytics across various domains has resulted in substantial social and economic benefits in recent years. As the adoption of graph analytics continues to expand, there is a corresponding need to establish fair pricing models for the information contributed by each participant in the data ecosystem. However, current query-based pricing frameworks cannot be applied to price graph statistics, as they fail to consider buyers' affordability and prevent arbitrage trading. To address this gap, in this paper, we propose a novel framework GSHOP for pricing graph statistic queries. Instead of pricing a precise answer for a query, our framework offers the flexibility to price a set of answers injected with noise. Based on the framework, data owners initially create and publish extended local views (ELVs) to represent their graph data. Additionally, it allows buyers to tolerate a certain degree of noise added to the answer to reduce their payments. The framework accurately quantifies the relationship between noise and price to ensure that payment and compensation are reasonable for the buyer and owners, respectively. We also propose algorithms specifically designed for fundamental graph statistics, including node degrees and subgraph counts such as k-stars and k-cliques. Furthermore, we formally prove that the pricing framework is arbitrage-free. Extensive experimental results on real-life graph data validate the good performance of the proposed framework and algorithms.

One primary problem for supervised ML is data scarcity, which refers to the inadequacy of well-labeled training data. Recently, deep generative models have shown the capability of generating data objects that closely resemble real data for datasets in different modalities, including images, natural language, and tabular data. Naturally, a promising approach for tackling data scarcity involves training a generative model to produce a collection of data objects, and then employing machine-labeling solutions (e.g., weak supervision or semi-supervised learning) to incorporate these generated data objects for supervised ML. However, it is important to note that because the provided training data may exhibit a different data distribution compared to the validation (or unseen testing) data, the generative model learned from these seen training data cannot guarantee the generation of high-quality data relative to this ML task. To address this challenge, we introduce an iterative approach that gradually calibrates the generative model by interacting with an environment that tells whether generated tuples are good or bad, by using a validation dataset that is not exposed to the generative model. In each iteration, we first use a pre-trained generative model to create unlabeled data objects, label them, and integrate this freshly generated data into the learning process. Afterwards, the model will be tested in the environment to assess the quality of the generated data. The iterative framework can be naturally controlled using reinforcement learning (RL), where an agent generates and labels tuples, an environment tests the generated tuples and sends reward back to the agent to progressively enhance the generative model for a specific supervised ML task. Experimental results over 8 datasets and multiple baselines demonstrate that our RL guided data synthesis, together with off-the-shelf semi-automatic labeling solutions, can significantly improve the performance of supervised ML models.

Bipartite graphs are commonly used to model relationships between two distinct types of entities, such as customer-product relationships in e-commerce platforms and protein-protein interactions in bioinformatics. Enumerating all maximal bicliques from a bipartite graph is a fundamental graph mining problem that has been widely used in many real-world applications including community search and spam detection. Existing algorithms for maximal biclique enumeration can struggle to scale to large graphs with a vast number of maximal bicliques. In this paper, we propose a novel and highly-efficient algorithm for maximal biclique enumeration in bipartite graphs using prefix trees. Specifically, a prefix tree is a data structure that stores lists of elements as paths in the tree, and we observe that a maximal biclique can be represented uniquely by the vertices in one of its vertex layers and stored compactly in prefix trees. The process of our algorithm is divided into two steps. First, we find the lower layer vertices of all maximal bicliques and organize them in a prefix tree (i.e., the result tree). During this step, we transform the original time-consuming operations of checking maximality and filtering candidates for vertex sets into determining uniqueness and performing extraction from a prefix tree at each level of the recursion. Second, we use the result tree to obtain the upper layer vertices of the maximal bicliques by computing the common neighbors of vertices in the tree. In this step, we further optimize the computation for intersections of vertex sets by compressing the neighbors of each vertex and memoization. In addition, we also propose a pre-processing method based on the order of traversal on the prefix tree to reduce memory usage. We conduct extensive experiments on 10 real-world datasets, and the results demonstrate that the proposed algorithm outperforms existing solutions by up to one order of magnitude.

The last few years have seen the wide applications of ride-sharing, a transportation service that allows users to share their travel routes. A typical problem for ride-sharing is to find an optimal route for each worker to serve the dynamically arriving requests with different objectives. Previous studies focus on the route planning on a single platform. However, a single platform may have an uneven distribution of supply and demand, which causes the platform to lose requests from lack of available workers. Luckily, some ride-sharing platforms provide the same service, which enables their collaborations. The inter-platform collaborations on ride-sharing can ease the worker shortages and greatly improve the service quality, but have not been studied yet. In this paper, we propose a Cross Online Ride-sharing (CORS) problem, which allows a platform to borrow the available workers from other platforms to serve its own requests. We first design two algorithms to select the optimal available worker from other platforms, ROWS and DOWS. ROWS randomly picks an available worker, while DOWS selects the optimal worker with the minimum additional travel distance calculated based on his/er predicted destination direction. Then, we design an efficient CORS framework that embeds the proposed optimal worker selection algorithms for the CORS problem. Extensive experiments on real and synthetic datasets demonstrate the effectiveness and efficiency of our algorithms.

With the development of AI, big data, and mobile communication, intelligent transportation has become popular in recent years. Path planning is a typical topic of intelligent transportation, attracting significant attention from researchers. However, existing studies only focus on the path planning of a single platform, which may lead to unexpected traffic congestion. This is because multiple platforms can provide route planning services, the optimal planning calculated by one single platform may be not good in practice, since multiple platforms may lead the users to the same roads, which causes unexpected traffic congestion. Although in the view of each platform, the planning is optimal. Fortunately, with the rise of data sharing and cross-platform cooperation, the data silos between different platforms are gradually being broken. Based on this, we propose Cooperative Global Path Planning (CG PP) framework to over-come the above shortcoming. CGPP allows the path planning request target platform to send some queries to cooperative platforms to optimize its path planning results. Such queries should be “easy” enough to answer, and the query frequency should be small. Based on the above principle, we design a query decision model based on multi-agent reinforcement learning in CGPP framework to decide the query range and query frequency. We design action and reward specifically for the CGPP problem. Furthermore, we propose the Self-adjusting Query Area algorithm to enhance the precision of query results and the Query Reuse Optimization algorithm to further minimize the number of queries. Extensive experiments on real and synthetic datasets confirm the effectiveness and efficiency of our algorithms.

Cohesive sub graph mining has received much at-tention in the area of graph analysis. A k- truss, defined as a sub graph where each edge is associated with at least$k-2$triangles, serves as a fundamental graph analysis tool. Among all k-trusses, the$k_{\max}$-truss with the maximum$k$value holds significant importance in various practical applications such as community search and keyword retrieval. Furthermore, it is also closely related to many graph analysis problems, particularly those computational complexity problems parameterized by$k$. However, real-world graphs often exhibit large-scale characteris-tics, making it impractical to fully load them into main memory. In this paper, we investigate the problem of finding the$k_{\max}$-truss in external memory settings. To address this problem, we propose an 110 efficient algorithm following a semi-external model, which only allows node information to be loaded into main memory. Our approach leverages greedy strategies and a binary search framework to efficiently find the$k_{\max}$- truss. Subsequently, an elegant data structure is proposed to significantly reduce 110 costs. Furthermore, to address dynamic graph updates, we develop an 110 efficient$k_{\max}$- truss maintenance algorithm based on the local-first update technique. To evaluate the performance of our algorithms, we conduct extensive experiments. The results demonstrate the high efficiency and scalability of our algorithms, which are at least two orders of magnitude faster in runtime and at least one order of magnitude lower in terms of 110 costs compared to the state-of-the-art solutions.

Recently, Federated Graph Learning (FGL) has attracted significant attention as a distributed framework based on graph neural networks, primarily due to its capability to break data silos. Existing FGL studies employ community split on the homophilous global graph by default to simulate federated semisupervised node classification settings. Such a strategy assumes the consistency of topology between the multi-client subgraphs and the global graph, where connected nodes are highly likely to possess similar feature distributions and the same label. However, in real-world implementations, the varying perspectives of local data engineering result in various subgraph topologies, posing unique heterogeneity challenges in FGL. Unlike the well-known label Non-independent identical distribution (Non-iid) problems in federated learning, FGL heterogeneity essentially reveals the topological divergence among multiple clients, namely homophily or heterophily. To simulate and handle this unique challenge, we introduce the concept of structure Non-iid split and then present a new paradigm called Adaptive Federated Graph Learning (AdaFGL), a decoupled two-step personalized approach. To begin with, AdaFGL employs standard multi-client federated collaborative training to acquire the federated knowledge extractor by aggregating uploaded models in the final round at the server. Then, each client conducts personalized training based on the local subgraph and the federated knowledge extractor. Extensive experiments on the 12 graph benchmark datasets validate the superior performance of AdaFGL over state-of-the-art baselines. Specifically, in terms of test accuracy, our proposed AdaFGL outperforms baselines by significant margins of 3.24 % and 5.57 % on community split and structure Non-iid split, respectively.

Community search is a fundamental problem in graph analysis. However, prevailing community search models predominantly focus on non-attributed or vertex-attributed graphs. Real-world graphs often bear crucial information within their edges, depicting intricate interactions among vertices. Integrating this edge-based information becomes pivotal in refining community search methodologies. In this paper, we proposed the Edge-Attributed Community Search (EACS) problem and proved that the EACS problem is NP-hard. Advanced exact and 2-approximation algorithms are proposed to address the EACS problem. Extensive experiments demonstrate the efficiency and effectiveness of our algorithms.

The widespread availability of Internet access and online services has led to the generation of numerous large-scale graphs in various real-world applications, such as online social networks and knowledge graphs. Keyword search stands out as a crucial task in the analysis and mining of these graphs. However, graph data owners tend to outsource storage and computation tasks to the cloud due to limited computing and storage resources. In this case, it is critical to ensure the integrity of the query results, as the cloud may have an incentive to return tampered results to serve its own interests. Currently, blockchain systems can store data efficiently and securely, creating a decentralized, tamper-proof digital platform. This functionality positions blockchain as a crucial complement and enhancement to traditional cloud storage solutions. Mainstream blockchains use a hybrid storage system to improve scalability, storing small meta-data on-chain and outsourcing raw data off-chain. While cryptographic proofs protect data integrity for queries, current schemes only support key-value data. This paper pioneers the study of authenticated keyword searches on graphs in hybrid-storage blockchains. The key challenge is to design an authenticated data structure (ADS) based on the graph data that can efficiently deal with keyword search queries. We propose Merkle Path DAG (MP-DAG), a novel ADS that aggregates the unqualified paths that will not appear in the result trees to efficiently handle authenticated keyword search queries on graphs. Furthermore, to reduce the ADS storage cost, we design an optimization scheme MP-DAG* by combining the similar subgraphs of MP-DAG. Experimental results demonstrate the performance of the proposed ADS and optimization measure.

Graphs serve as an essential data structure to model complex relationships in a variety of applications, such as social networks, web graphs, and chemical informatics. Due to the high cost of maintaining large-scale graph data and executing graph queries, data owners often outsource their graph data to a third-party service provider for graph processing. In this scenario, it is crucial to ensure the integrity of query results, as the provider may have the incentive to return only partial or tampered results to save computing resources or serve their own interests. Blockchain, as a promising solution for secure data storage and retrieval, opens up new opportunities for data management in such scenarios. To scale the blockchain, many works have been conducted using off-chain storage while ensuring the integrity of query results for key-value data in hybrid-storage blockchain architectures. To our knowledge, there is no work to enable the blockchain to support subgraph matching queries. In this paper, we present a novel approach to support authenticated subgraph matching queries for large graphs kept off-chain. We first design the authenticated data structure as MELTree and keep the digests of the roots on-chain. We propose the verification object (VO) construction algorithm AMatching for queries to ensure the completeness and soundness of the results. To further reduce the cost, we propose AMatching* based on a bidirectional search including forward search and reverse search. Moreover, we further optimize the on-chain storage cost by proposing MVPTree, which organizes the structures for vertices and only needs to keep one root digest on-chain for verification. Experimental results show that the proposed algorithms and the optimizations improve the performance significantly.

Federated learning (FL) has become an emerging paradigm via cooperative training models among distributed clients without leaking data privacy. The performance degradation of F1 on heterogeneous data has driven the development of personalized FL (PFL) solutions, where different models are built for individual clients. However, existing PFL approaches often have limited personalization in terms of modeling capability and training strategy. In this paper, we propose a novel PFL solution, Feed, that employs an enhanced shared-private model architecture and equips with a hybrid federated training strategy. Specifically, to model heterogeneous data for different clients, we design an ensemble-based shared encoder that generates an ensemble of embeddings, and a private decoder that adaptively aggregates these embeddings for personalized prediction. In addition, we propose a server-side hybrid federated aggregation strategy to enable effective training of the heterogeneous shared-private model. To prevent personalization degradation in local model updates, we further optimize the personalized local training on the client-side by smoothing the historical encoders. Extensive experiments on MNIST/FEMNIST, CIFARIO/CIFARIOO, and YELP datasets demonstrate that Feed consistently outperforms state-of-the-art approaches.

Recently, graph neural networks (GNNs) have shown prominent performance in semi-supervised node classification by leveraging knowledge from the graph database. However, most existing GNNs follow the homophily assumption, where connected nodes are more likely to exhibit similar feature distributions and the same labels, and such an assumption has proven to be vulnerable in a growing number of practical applications. As a supplement, heterophily reflects dissimilarity in connected nodes, which has gained significant attention in graph learning. To this end, data engineers aim to develop a powerful GNN model that can ensure performance under both homophily and heterophily. Despite numerous attempts, most existing GNNs struggle to achieve optimal node representations due to the constraints of undirected graphs. The neglect of directed edges results in sub-optimal graph representations, thereby hindering the capacity of GNNs. To address this issue, we introduce AMUD, which quantifies the relationship between node profiles and topology from a statistical perspective, offering valuable insights for Adaptively Modeling the natural directed graphs as the Undirected or Directed graph to maximize the benefits from subsequent graph learning. Furthermore, we propose Adaptive Directed Pattern Aggregation (ADPA) as a new directed graph learning paradigm for AMUD. Empirical studies have demonstrated that AMUD guides efficient graph learning. Meanwhile, extensive experiments on 16 benchmark datasets substantiate the impressive performance of ADPA, outperforming baselines by significant margins of 3.96%.

Huawei collaborates with some Chinese large busi-ness companies to store and process exabytes of nationwide operational data in data lake storage to provide business insights. Specifically, our customers will ask to store and process massive log message data to support their real-time and decision-making applications. Thus, we need computation and storage components in the analytic platform to process and store these data cost-efficiently. To meet these user requirements, we have designed a storage system in data lake, StreamLake, which introduces a novel design to serve log message streaming and batch data processing in distributed storage, with high scalability, efficiency, reliability and low cost. Specifically, we introduce a stream (storage) object as a storage abstraction for message streaming data to achieve the storage-disaggregated architecture with high scalability and reliability. Moreover, we utilize the erasure coding and tiered storage to save the storage cost, and furthermore, the stream object can be automatically converted to a table object such that cost-effective stream and batch data processing can be achieved. For tabular data, we implement the lakehouse functionality to support ACID via the table object, with a metadata acceleration to improve the efficiency of data access between the compute and storage engines. Also, we design a LakeBrain optimizer at the storage side to optimize the query performance and resource utilization under the storage-disaggregated architecture. Finally, we have also deployed StreamLake in China Mobile, the world's largest mobile network operator to serve over 20PB production data, and the results demonstrate improvements of 30% to 4x in terms of query performance and over 37% in terms of cost saving.

Periodic group behaviors often exist in temporal interaction networks, such as monthly group meetings, quarterly animal migrations, and yearly birthday parties. In real life, these events are usually quasi-periodic, meaning that the time intervals between two adjacent events are nearly constant but not exactly constant. Most existing studies mainly focus on identifying exact periodic group behaviors, which may result in an incomplete detection of periodic patterns in temporal networks. To fill this gap, we focus on a quasi-periodic community mining problem, which aims to find the most representative cohesive sub graphs, including the quasi-periodic$k$-core and quasi-periodic k-clique. The number of quasi-periodic communities is much larger than that of periodic communities, since the number of quasi-periodic sub-sequences is larger than that of periodic sub-sequences in a given time sequence. To efficiently compute the quasi-periodic communities, we propose a novel two-stage framework. In the first stage, the framework checks whether the time sequence of each vertex contains quasi-periodic sub-sequences. To this end, we develop a new structure, the DAG oracle, which comprises a set of concise DAGs that enables rapid extraction of all quasi-periodic sub-sequences. Based on the DAG oracle, we can easily compute all quasi-periodic sub-sequences for every vertex. In the second stage, the framework computes local quasi-periodic subgraphs that contain the vertex, which allows for the application of existing community mining algorithms. Given the large number of these subgraphs, we propose several carefully -designed pruning rules to further reduce redundant computations. Extensive experiments on 5 real-life datasets demonstrate the efficiency and effectiveness of our proposed solutions.

With the development of permissioned blockchains, transaction processing plays an increasingly crucial role in improving performance. The execution and consensus phases in existing transaction processing methods are based on total order. The consensus phase constructs a total order representing the execution order and submission order of different transactions. Then, in the execution phase, transactions are executed or validated sequentially based on this total order. However, while the total order guarantees consistency across nodes, it also restricts the execution order of any two transactions, even if there is no conflict between them. Additionally, existing methods process transactions based on block snapshots before the consensus phase, but these snapshots are only updated after reaching consensus. The stale data between these phases results in high transaction abort rates due to delays in updated visibility. Therefore, we propose a novel blockchain called Partial Order-Based Ledger (POBL). POBL constructs a partial order of transaction executions in the execution phase and then, in the consensus phase, builds a consistent submission order based on this execution partial order. Notably, POBL allows the visibility of transaction processing results in the execution phase even before committing its block. To ensure the correct execution, the consensus and execution phases need to consider the consistency of data and the dependencies between transactions. Therefore, we use a graph, PGraph, to capture the concurrent partial order in the execution phase. In the consensus phase, we propose a consensus algorithm to conduct the maximal common subgraph, CPGraph, based on the PGraphs of different nodes. We propose to validate blocks and transactions in parallel based on CPGraph, without being restricted by the order between blocks. We perform extensive experiments compared to state-of-the-art architectural systems, and our method significantly outperforms existing work.

Trajectory prediction of moving traffic agents is crucial for the safety of autonomous vehicles, whereas previous approaches usually rely on sufficiently long-observed trajectory (e.g., 2 seconds) to predict the future trajectory of the agents. However, in many real-world scenarios, it is not realistic to collect adequate observed locations for moving agents, leading to the collapse of most prediction models. For instance, when a moving car suddenly appears and is very close to an autonomous vehicle because of the obstruction, it is quite necessary for the autonomous vehicle to quickly and accurately predict the future trajectories of the car with limited observed trajectory locations. In light of this, we focus on investigating the task of instantaneous trajectory prediction, i.e., two observed locations are available during inference. To this end, we put forward a general and plug-and-play instantaneous trajectory prediction approach, called ITPNet. Specifically, we propose a backward forecasting mechanism to reversely predict the latent feature representations of unobserved historical trajectories of the agent based on its two observed locations and then leverage them as complementary information for future trajectory prediction. Meanwhile, due to the inevitable existence of noise and redundancy in the predicted latent feature representations, we further devise a Noise Redundancy Reduction Former (NRRFormer) module, which aims to filter out noise and redundancy from unobserved trajectories and integrate the filtered features and observed features into a compact query representation for future trajectory predictions. In essence, ITPNet can be naturally compatible with existing trajectory prediction models, enabling them to gracefully handle the case of instantaneous trajectory prediction. Extensive experiments on the Argoverse and nuScenes datasets demonstrate ITPNet outperforms the baselines by a large margin and shows its efficacy with different trajectory prediction models.

The quest to identify local dense communities closely connected to predetermined seed nodes is vital across numerous applications. Given the seed nodes R, the R-subgraph density of a subgraph S is defined as traditional graph density of S with penalties on the nodes in S / R. The state-of-the-art (SOTA) anchored densest subgraph model, which is based on R-subgraph density, is designed to address the community search problem. However, it often struggles to efficiently uncover truly dense communities. To eliminate this issue, we propose a novel NR-subgraph density metric, a nuanced measure that identifies communities intimately linked to seed nodes and also exhibiting overall high graph density. We redefine the anchored densest subgraph search problem through the lens of NR-subgraph density and cast it as a Linear Programming (LP) problem. This allows us to transition into a dual problem, tapping into the efficiency and effectiveness of convex programming-based iterative algorithm. To solve this redefined problem, we propose two algorithms: FDP, an iterative method that swiftly attains near-optimal solutions, and FDPE, an exact approach that ensures full convergence. We perform extensive experiments on 12 real-world networks. The results show that our proposed algorithms not only outperform the SOTA methods by 3.6~14.1 times in terms of running time, but also produce subgraphs with superior internal quality.

Scalable graph neural networks (GNNs) have emerged as a promising technique, which exhibits superior predictive performance and high running efficiency across numerous large-scale graph-based web applications. However, (i) Most scalable GNNs tend to treat all nodes with the same propagation rules, neglecting their topological uniqueness; (ii) Existing node-wise propagation optimization strategies are insufficient on web-scale graphs with intricate topology, where a full portrayal of nodes' local properties is required. Intuitively, different nodes in web-scale graphs possess distinct topological roles, and therefore propagating them indiscriminately or neglecting local contexts may compromise the quality of node representations. To address the above issues, we propose Adaptive Topology-aware Propagation (ATP), which reduces potential high-bias propagation and extracts structural patterns of each node in a scalable manner to improve running efficiency and predictive performance. Remarkably, ATP is crafted to be a plug-and-play node-wise propagation optimization strategy, allowing for offline execution independent of the graph learning process in a new perspective. Therefore, this approach can be seamlessly integrated into most scalable GNNs while remaining orthogonal to existing node-wise propagation optimization strategies. Extensive experiments on 12 datasets have demonstrated the effectiveness of ATP.

A k-biplex is an induced subgraph of a bipartite graph which requires every vertex on the one side disconnecting at most k vertices on the other side. Enumerating all maximal k-biplexes in a bipartite graph is a fundamental operator in bipartite graph analysis and finds applications in various domains, including community detection, online recommendation, and fraud detection in finance networks. The state-of-the-art solutions for maximal k-biplex enumeration suffer from efficiency issues as k increases (k ≥ 2), with the time complexity of O(m 2 n ), where n (m) denotes the number of vertices (edges) in the bipartite graph. To address this issue, we propose two theoretically and practically efficient enumeration algorithms based on novel branching techniques. Specifically, we first devise a new branching rule as a fundamental component. Building upon this, we then develop a novel branch-and-bound enumeration algorithm to efficiently enumerate maximal k-biplexes. We prove that our algorithm achieves a worst-case time complexity of O(mα k n ), where α k < 2, thus significantly improving the time complexity compared to previous algorithms. To enhance the performance, we further propose an improved enumeration algorithm based on a novel pivot-based branching rule. Theoretical analysis reveals that our improved algorithm has a time complexity of O(mβ k n ), where β k is strictly less than α k . In addition, we also present several non-trivial optimization techniques, including graph reduction, upper-bounds based pruning, and ordering-based optimization, to further improve the efficiency of our algorithms. Finally, we conduct extensive experiments on 6 large real-world bipartite graphs to evaluate the efficiency and scalability of the proposed solutions. The results demonstrate that our improved algorithm achieves up to 5 orders of magnitude faster than the state-of-the-art solutions.

The study of k -defective cliques, defined as induced subgraphs that differ from cliques by at most k missing edges, has attracted much attention in graph analysis due to their relevance in various applications, including social network analysis and implicit interaction predictions. However, determining the maximum k -defective clique in graphs has been proven to be an NP-hard problem, presenting significant challenges in finding an efficient solution. To address this problem, we develop a theoretically and practically efficient algorithm that leverages newly-designed branch reduction rules and a pivot-based branching technique. Our analysis establishes that the time complexity of the proposed algorithm is bounded by O(mγ k n ), where γ k is a real value strictly less than 2 (e.g., when k= 1, 2, and 3, γ k = 1.466, 1.755, and 1.889, respectively). To our knowledge, this algorithm achieves the best worst-case time complexity to date compared to state-of-the-art solutions. Moreover, to further reduce unnecessary branches, we propose a time-efficient upper bound-based pruning technique, which is obtained by manipulating information such as the number of distinct colors assigned to vertices and the presence of non-neighbors among them. Additionally, we employ an ordering-based heuristic approach as a preprocessing step to improve computational efficiency. Finally, we conduct extensive experiments on a diverse set of over 300 graphs to evaluate the efficiency of the proposed solutions. The results demonstrate that our algorithm achieves a speedup of 3 orders of magnitude over state-of-the-art solutions in processing most of real-world graphs.

Effective resistance (ER) is a fundamental metric for measuring node similarities in a graph, and it finds applications in various domains including graph clustering, recommendation systems, link prediction, and graph neural networks. The state-of-the-art algorithm for computing effective resistance relies on a landmark technique, which involves selecting a node that is easy to reach by all the other nodes as a landmark. The performance of this technique heavily depends on the chosen landmark node. However, in many real-life graphs, it is not always possible to find an easily reachable landmark node, which can significantly hinder the algorithm's efficiency. To overcome this problem, we propose a novel multiple landmarks technique which involves selecting a set of landmark nodes V l such that the other nodes in the graph can easily reach any one of a landmark node in V l . Specifically, we first propose several new formulas to compute ER with multiple landmarks, utilizing the concept of Schur complement. These new formulas allow us to pre-compute and maintain several small-sized matrices related to V l as a compact index. With this powerful index technique, we demonstrate that both single-pair and single-source ER queries can be efficiently answered using a newly-developed V l -absorbed random walk sampling or V l -absorbed push technique. Comprehensive theoretical analysis shows that all proposed index-based algorithms achieve provable performance guarantees for both single-pair and single-source ER queries. Extensive experiments on 5 real-life datasets demonstrate the high efficiency of our multiple landmarks-based index techniques. For instance, our algorithms, with a 1.5 GB index size, can be up to 4 orders of magnitude faster than the state-of-the-art algorithms while achieving the same accuracy on a large road network.

Errors are common in time series due to unreliable sensor measurements. Existing methods focus on univariate data but do not utilize the correlation between dimensions. Cleaning each dimension separately may lead to a less accurate result, as some errors can only be identified in the multivariate case. We also point out that the widely used minimum change principle is not always the best choice. Instead, we try to change the smallest number of data to avoid a significant change in the data distribution. In this paper, we propose MTCSC, the constraint-based method for cleaning multivariate time series. We formalize the repair problem, propose a linear-time method to employ online computing, and improve it by exploiting data trends. We also support adaptive speed constraint capturing. We analyze the properties of our proposals and compare them with SOTA methods in terms of effectiveness, efficiency versus error rates, data sizes, and applications such as classification. Experiments on real datasets show that MTCSC can have higher repair accuracy with less time consumption. Interestingly, it can be effective even when there are only weak or no correlations between the dimensions.

Searching tables from poorly maintained data lakes has long been recognized as a formidable challenge in the realm of data management. There are three pivotal tasks: keyword-based, joinable and unionable table search, which form the backbone of tasks that aim to make sense of diverse datasets, such as machine learning. In this demo, we propose LakeCompass, an end-to-end prototype system that maintains abundant tabular data, supports all above search tasks with high efficacy, and well serves downstream ML modeling. To be specific, LakeCompass manages numerous real tables over which diverse types of indexes are built to support efficient search based on different user requirements. Particularly, LakeCompass could automatically integrate these discovered tables to improve the downstream model performance in an iterative approach. Finally, we provide both Python APIs and Web interface to facilitate flexible user interaction.

Supervised machine learning (ML) models trained on data with mislabeled instances often produce inaccurate results due to label errors. Traditional methods of detecting mislabeled instances rely on data proximity, where an instance is considered mislabeled if its label is inconsistent with its neighbors. However, it often performs poorly, because an instance does not always share the same label with its neighbors. ML-based methods instead utilize trained models to differentiate between mislabeled and clean instances. However, these methods struggle to achieve high accuracy, since the models may have already overfitted mislabeled instances. In this paper, we propose a novel framework, MisDetect, that detects mislabeled instances during model training. MisDetect leverages the early loss observation to iteratively identify and remove mislabeled instances. In this process, influence-based verification is applied to enhance the detection accuracy. Moreover, MisDetect automatically determines when the early loss is no longer effective in detecting mislabels such that the iterative detection process should terminate. Finally, for the training instances that MisDetect is still not certain about whether they are mislabeled or not, MisDetect automatically produces some pseudo labels to learn a binary classification model and leverages the generalization ability of the machine learning model to determine their status. Our experiments on 15 datasets show that MisDetect outperforms 10 baseline methods, demonstrating its effectiveness in detecting mislabeled instances.

Discovering tables from poorly maintained data lakes is a significant challenge in data management. Two key tasks are identifying joinable and unionable tables, crucial for data integration, analysis, and machine learning. However, there's a lack of a comprehensive benchmark for evaluating existing methods. To address this, we introduce LakeBench, a large-scale table discovery benchmark. It evaluates effectiveness, efficiency, and scalability of table join & union search methods. With over 16 million real tables, LakeBench is 1,600X larger than existing datasets and 100X larger in storage size. It includes synthesized and real queries with ground truth, totaling more than 10 thousand queries - 10X more than used in any existing evaluation. We spent over 7,500 human hours labeling these queries and constructing diverse query categories for thorough evaluation. Our benchmark thoroughly evaluates state-of-the-art table discovery methods, providing insights into their performance and highlighting research opportunities.

Most existing graph neural networks (GNNs) are limited to undirected graphs, whose restricted scope of the captured relational information hinders their expressive capabilities and deployment. Compared with undirected graphs, directed graphs (digraphs) fit the demand for modeling more complex topological systems by capturing more intricate relationships between nodes. While some directed GNNs have been introduced, their inspiration mainly comes from deep learning architectures, which lead to redundant complexity and computation, making them inapplicable to large-scale databases. To address these issues, we propose LightDiC, a scalable variant of the digraph convolution based on the magnetic Laplacian. Since topology-related computations are conducted solely during offline pre-processing, LightDiC achieves exceptional scalability, enabling downstream predictions to be trained separately without incurring recursive computational costs. Theoretical analysis shows that LightDiC achieves message passing based on the complex field, which corresponds to the proximal gradient descent process of the Dirichlet energy optimization function from the perspective of digraph signal denoising, ensuring its expressiveness. Experimental results demonstrate that LightDiC performs comparably well or even outperforms other SOTA methods in various downstream tasks, with fewer learnable parameters and higher efficiency.

Graph coarsening techniques aim at simplifying the graph structure while preserving key properties in the resulting coarsened graph, have been widely used in graph partitioning and graph neural networks (GNNs). Existing graph coarsening techniques mainly focus on preserving cuts or graph spectrums. In this paper, we propose a new method that focuses on preserving graph topological features. In particular, we develop a novel graph coarsening approach, called Graph Elementary Collapse (GEC), by extending the concept of elementary collapse in algebraic topology to graph analysis. With this novel method, we can ensure a kind of equivalence relationship called homotopy equivalence of the graph during the coarsening process, thereby preserving numerous topological properties, including connectivity, rings, and voids. To enhance the scalability, we also propose several carefully-designed optimization techniques to reduce the time and memory consumption of our approach. Extensive experiments on several real-world datasets demonstrate the effectiveness and efficiency of our proposed method across various GNN prediction tasks.

The arboricity a ( G ) of a graph G is defined as the minimum number of edge-disjoint forests that the edge set of G can be partitioned into. It is a fundamental metric and has been widely used in many graph analysis applications. However, computing a ( G ) is typically a challenging task. To address this, an easier-to-compute alternative called pseudoarboricity was proposed. Pseudoarboricity has been shown to be closely connected to many important measures in graphs, including the arboricity and the densest subgraph density ρ ( G ). Computing the exact pseudoarboricity can be achieved by employing a parametric max-flow algorithm, but it becomes computationally expensive for large graphs. Existing 2-approximation algorithms, while more efficient, often lack satisfactory approximation accuracy. To overcome these limitations, we propose two new approximation algorithms with theoretical guarantees to approximate the pseudoarboricity. We show that our approximation algorithms can significantly reduce the number of times the max-flow algorithm is invoked, greatly improving its efficiency for exact pseudoarboricity computation. In addition, we also study the pseudoarboricity maintenance problem in dynamic graphs. We propose two novel and efficient algorithms for maintaining the pseudoarboricity when the graph is updated by edge insertions or deletions. Furthermore, we develop two incremental pseudoarboricity maintenance algorithms specifically designed for insertion-only scenarios. We conduct extensive experiments on 195 real-world graphs, and the results demonstrate the high efficiency and scalability of the proposed algorithms in computing pseudoarboricity for both static and dynamic graphs.

Locally-densest subgraph (LDS) decomposition is a fundamental decomposition in graph analysis that finds numerous applications in various domains, including community detection, fraud detection, graph querying, and graph visualization. However, the LDS decomposition is computationally challenging for both static and dynamic graphs. Furthermore, the LDS decomposition often produces an excessive number of dense subgraph layers, leading to the unnecessary partition of tightly-connected subgraphs. To address these limitations, an alternative concept called density decomposition was proposed, which can generate a more reasonable number of dense subgraph layers. However, the state-of-the-art algorithm for density decomposition requires O ( m 2 ) time ( m is the number of edges of the graph), which is very costly for large graphs. In this paper, we conduct an in-depth investigation of density decomposition and propose efficient algorithms for computing it on both static and dynamic graphs. First, we establish a novel relationship between density decomposition and LDS decomposition. Second, based on these relationships, we propose novel algorithms to compute the density decomposition on static graphs with carefully designed network flow and divide-and-conquer techniques. Our proposed static algorithms significantly reduce the time complexity to O ( m 3/2 log p ) ( p is often a very small constant in real-world graphs). Third, for dynamic graphs, we develop three dynamic algorithms with efficient O ( m ) time complexity. Extensive experiments on several large real-world graphs demonstrate the high efficiency, scalability, and effectiveness of the proposed algorithms.

Densest subgraph search, aiming to identify a subgraph with maximum edge density, faces limitations as the edge density inadequately reflects biases towards a given vertex set R. To address this, the R -subgraph density was introduced, refining the doubled edge density by penalizing vertices in a subgraph but not in R , using the degree as a penalty factor. This advancement leads to the Anchored Densest Subgraph (ADS) search problem, which finds the subgraph Š with the highest R -subgraph density for a given set R. Nonetheless, current algorithms for ADS search face significant inefficiencies in handling large-scale graphs or the sizable R set. Furthermore, these algorithms require re-computing the ADS whenever the graph is updated, complicating the efficient maintenance within dynamic graphs. To tackle these challenges, we propose the concept of integer R -subgraph density and study the problem of finding a subgraph S * ⊆ V with the highest integer R -subgraph density. We reveal that the R -subgraph density of S* provides an additive approximation to that of ADS with a difference of less than 1, and hence S * is termed the Approximate Anchored Densest Subgraph (AADS). For searching the AADS, we present an efficient global algorithm incorporating the re-orientation network flow technique and binary search, operating in a time polynomial to the graph's size. Additionally, we propose a novel local algorithm using shortest-path-based methods for the max-flow computation from s to t around R , markedly boosting performance in scenarios with larger R sets. For dynamic graphs, both basic and improved algorithms are developed to efficiently maintain the AADS when an edge is updated. Extensive experiments and a case study demonstrate the efficiency, scalability, and effectiveness of our solutions.

Graph structured data often possess dynamic characters in nature, such as the addition of links and nodes, in many real-world applications. Recent years have witnessed the increasing attentions paid to dynamic graph neural networks for modelling graph data. However, almost all existing approaches operate under the assumption that, upon the establishment of a new link, the embeddings of the neighboring nodes should undergo updates to learn temporal dynamics. Nevertheless, these approaches face the following limitation: If the node introduced by a new connection contains noisy information, propagating its knowledge to other nodes becomes unreliable and may even lead to the collapse of the model. In this paper, we proposeAda-DyGNN: a robust knowledgeAdaptation framework via reinforcement learning forDynamicGraphNeuralNetworks. In contrast to previous approaches, which update the embeddings of the neighbor nodes immediately after adding a new link, Ada-DyGNN adaptively determines which nodes should be updated. Considering that the decision to update the embedding of one neighbor node can significantly impact other neighbor nodes, we conceptualize the node update selection as a sequence decision problem and employ reinforcement learning to address it effectively. By this means, we can adaptively propagate knowledge to other nodes for learning robust node embedding representations. To the best of our knowledge, our approach constitutes the first attempt to explore robust knowledge adaptation via reinforcement learning specifically tailored for dynamic graph neural networks. Extensive experiments on three benchmark datasets demonstrate that Ada-DyGNN achieves the state-of-the-art performance. In addition, we conduct experiments by introducing different degrees of noise into the dataset, quantitatively and qualitatively illustrating the robustness of Ada-DyGNN. The source code of this work is available athttps://github.com/BitLhj/Ada-DyGNN/

Deep subspace clustering based on the self-expressive layer has attracted increasing attention in recent years. Due to the self-expressive layer, these methods need to load the whole dataset into one batch for learning the self-expressive coefficients. Such a learning strategy puts a great burden on memory, which severely prevents from the usage of deeper network architectures (e.g., ResNet), and becomes a bottleneck for applying to large-scale data. In this paper, we propose a new deep subspace clustering framework, in order to address the above challenges. In contrast to previous approaches taking the weights of a fully connected layer as the self-expressive coefficients, we attempt to obtain the self-expressive coefficients by learning an energy based network in a mini-batch training manner. By this means, it is no longer necessary to load all data into one batch for learning, thus avoiding the above issue. Considering the powerful representation ability of the recently popular self-supervised learning, we leverage self-supervised representation learning to learn the dictionary for representing data. Finally, we propose a joint framework to learn both the self-expressive coefficients and the dictionary simultaneously. Extensive experiments on three publicly available datasets demonstrate the effectiveness of our method.

Deep learning models are usually black boxes when deployed on machine learning platforms. Prior works have shown that the attributes (e.g., the number of convolutional layers) of a target black-box model can be exposed through a sequence of queries. There is a crucial limitation: these works assume the training dataset of the target model is known beforehand and leverage this dataset for model attribute attack. However, it is difficult to access the training dataset of the target black-box model in reality. Therefore, whether the attributes of a target black-box model could be still revealed in this case is doubtful. In this paper, we investigate a new problem of black-box reverse engineering, without requiring the availability of the target model’s training dataset. We put forward a general and principled framework DREAM, by casting this problem as out-of-distribution (OOD) generalization. In this way, we can learn a domain-agnostic meta-model to infer the attributes of the target black-box model with unknown training data. This makes our method one of the kinds that can gracefully apply to an arbitrary domain for model attribute reverse engineering with strong generalization ability. Extensive experimental results demonstrate the superiority of our proposed method over the baselines.

Distributed key-value storage and computation are essential components of cloud services. As the demand for high-performance systems has increased significantly, a new architecture has been motivated to separate computing and storage nodes and connect them using RDMA-enabled networks. Existing RDMA-enabled systems use client-side cached indexes to reduce communication overhead and improve performance. However, such approaches could result in high server CPU contention due to heavy dynamic workloads (i.e.,inserts), and cause a large accuracy gap because of the different indexes between client-side and server-side. These drawbacks limit the performance of RDMA-enabled systems. In this paper, to deal with these issues, we introduce AStore to achieve high performance with low memory footprint. AStore employs a new uniformed architecture, utilizing an adaptive learned index as both the server-side learned index and the client-side cached index, to handle dynamic and static workloads. We propose several optimization techniques to optimize dynamic and static workload procedures and design the leaf node lock mechanism to support high concurrent access. Extensive evaluations on YCSB, LGN, and OSM datasets demonstrate that AStore achieves competitive performance on read-only workloads by up to 75.2%, 107.3% and 57.7%, as well as improving performance on write-read workloads by up to 65.7%, 108.7% and 74.3% than XStore.

$K$-clique counting is a fundamental problem in network analysis which has attracted much attention in recent years. Computing the count of$k$-cliques in a graph for a large$k$(e.g.,$k=8$) is often intractable as the number of$k$-cliques increases exponentially w.r.t. (with respect to)$k$. Existing exact$k$-clique counting algorithms are often hard to handle large dense graphs, while sampling-based solutions either require a huge number of samples or consume very high storage space to achieve a satisfactory accuracy. To overcome these limitations, we propose a new framework to estimate the number of$k$-cliques which integrates both the exact$k$-clique counting technique and three novel color-based sampling techniques. The key insight of our framework is that we only apply the exact algorithm to compute the$k$-clique counts in thesparse regionsof a graph, and use the proposed color-based sampling approaches to estimate the number of$k$-cliques in thedense regionsof the graph. Specifically, we develop three novel dynamic programming based$k$-color set sampling techniques to efficiently estimate the$k$-clique counts, where a$k$-color set contains$k$nodes with$k$different colors. Since a$k$-color set is often a good approximation of a$k$-clique in the dense regions of a graph, our sampling-based solutions are extremely efficient and accurate. Moreover, the proposed sampling techniques are space efficient which use near-linear space w.r.t. graph size. We conduct extensive experiments to evaluate our algorithms using 8 real-life graphs. The results show that our best algorithm is at least one order of magnitude faster than the state-of-the-art sampling-based solutions (with the same relative error 0.1%) and can be up to three orders of magnitude faster than the state-of-the-art exact algorithm on large graphs.

Spatial Crowdsourcing (SC) has been proved as an effective paradigm for data acquisition in urban environments. Apart from using human participants, with the rapid development of unmanned vehicles (UVs) technologies, unmanned aerial or ground vehicles (UAVs, UGVs) are equipped with various high-precision sensors, enabling them to become new types of data collectors. However, UGVs’ operational range is constrained by the road network, and UAVs are limited by power supply, it is thus natural to use UGVs and UAVs together as a coalition, and more precisely, UGVs behave as the UAV carriers for range extensions to achieve complicated air-ground SC tasks. In this paper, we propose a novel communication-based multi-agent deep reinforcement learning method called "GARL", which consists of a multi-center attention-based graph convolutional network (GCN) to accurately extract UGV specific features from UGV stop network called "MC-GCN", and a novel GNN-based communication mechanism called "E-Comm" to make the cooperation among UGVs adaptive to constant changing of geometric shapes formed by UGVs. Extensive simulation results on two campuses of KAIST and UCLA campuses show that GARL consistently outperforms eight other baselines in terms of overall efficiency.

Neighborhood inclusion, representing that all the neighbors of a vertex are also adjacent to another vertex, has been recognized as an important relationship between two vertices in a graph. We call a vertex u dominating v, denoted by v ≤ u, if $N(v) \subseteq N(u) \cup \{ u\} $ holds, where (v) denotes the set of neighbors of v. Based on such a domination relationship, we propose a concept called neighborhood skyline. The neighborhood skyline is a set of vertices in which any vertex u cannot be dominated by the other nodes in the graph G, i.e., $\nexists v \in G,u \leq v$. We study a new problem, called neighborhood skyline computation, and develop a filter-refine search framework, FilterRefineSky, to efficiently find the neighborhood skyline by searching the vertices in a small candidate set instead of in the entire graph. We show that our neighborhood skyline technique can be used to speed up the computation of two well-studied group centrality maximization problems and the maximum clique search problem in graphs. Extensive experimental studies conducted on five large real-life datasets demonstrate the effectiveness of neighborhood skyline, and the efficiency and scalability of our algorithms.

Personalized location prediction is key to many mobile applications and services. In this paper, motivated by both statistical and visualized preliminary analysis on three real datasets, we observe a strong spatiotemporal correlation for user trajectories among the visited area-of-interests (AoIs) and different time periods on both weekly and daily basis, which directly motivates our time-aware location prediction model design called "t-LocPred". It models the spatial correlations among AoIs by coarse-grained convolutional processing of the user trajectories in AoIs of different time periods ("ConvAoI"); and predicts his/her fine-grained next visited PoI using a novel memory-augmented attentive LSTM model ("mem-attLSTM") to capture long-term behavior patterns. Experimental results show that t-LocPred outperforms 8 baselines. We also show the impact of hyperparameters and the benefits ConvAoI can bring to these baselines.

This paper presents a novel spatial query, skyline micro-cluster (SMC) query. Given a set of data points P, a query point q, a radius γ and a density parameter k, the SMC query returns the skyline micro-clusters (MCs), where MC is a set of points in P that can be covered by a circle with radius γ and the number of points in MC is at least k. In this paper, we formally define the SMC query. As the brute-force approach to solving the SMC query in massive datasets has high computation and memory costs, we propose a basic skyline micro-cluster query algorithm, BSMC, which can reduce the time complexity from O(2N) to O(N3). Furthermore, on top of BSMC, we propose an efficient skyline micro-cluster query algorithm (ESMC). In ESMC, we use the z-value index and propose a filter to remove the invalid micro-clusters, which reduces significant computation overhead. To reduce the memory overhead, we propose an incremental skyline query method. A comprehensive performance study is conducted on real datasets and the experimental results show that our proposed method, ESMC, can significantly improve the SMC query performance.

Deep Neural Networks (DNNs) have been ubiquitously adopted in internet of things and are becoming an integral of our daily life. When tackling the evolving learning tasks in real world, such as classifying different types of objects, DNNs face the challenge to continually retrain themselves according to the tasks on different edge devices. Federated continual learning is a promising technique that offers partial solutions but yet to overcome the following difficulties: the significant accuracy loss due to the limited on-device processing, the negative knowledge transfer caused by the limited communication of non-IID data, and the limited scalability on the tasks and edge devices. In this paper, we propose FedKNOW, an accurate and scalable federated continual learning framework, via a novel concept of signature task knowledge. FedKNOW is a client side solution that continuously extracts and integrates the knowledge of signature tasks which are highly influenced by the current task. Each client of FedKNOW is composed of a knowledge extractor, a gradient restorer and, most importantly, a gradient integrator. Upon training for a new task, the gradient integrator ensures the prevention of catastrophic forgetting and mitigation of negative knowledge transfer by effectively combining signature tasks identified from the past local tasks and other clients’ current tasks through the global model. We implement FedKNOW in PyTorch and extensively evaluate it against state-of-the-art techniques using popular federated continual learning benchmarks. Extensive evaluation results on heterogeneous edge devices show that FedKNOW improves model accuracy by 63.24% without increasing model training time, reduces communication cost by 34.28%, and achieves more improvements under difficult scenarios such as large numbers of tasks or clients, and training different complex networks.

Link prediction is a significant technique to generate latent interactions for the applications of recommendation in large graphs. As the interactions to be predicted often occur among more than two objects, we pay attention to solving the novel problem of predicting the interactions in hypergraphs. Previous studies focus mainly on predicting binary relations; most of those techniques cannot be directly applied to predict multiple relations. In this work, we study the problem of edge prediction in hypergraphs, where we use a concept, Hypergraph Edit Distance (abbreviated as HGED), to measure the similarity of two nodes. Based on HGED, we can record a Hypergraph Edit Path while searching the optimal edit distance, thus this path enables to explain why one node is similar to another node since their neighborhood structure can be edited to be isomorphic following the edit path. We first propose a general framework which can compute the edit distance of neighborhood structure for two nodes in hypergraph. To improve the efficiency, we propose a BFS search-based method with several tightening lower bounds and upper bounds estimation. To predict the multiple relations, we introduce a cluster model in which nodes in each hyperedge are restricted by the hypergraph edit distance. We further present an on-demand algorithm for computing HGED, which substantially avoids redundant computations. Finally, we conduct extensive empirical studies on real hypergraph datasets, and the results demonstrate the effectiveness, efficiency and scalability of our algorithms.

The rapid development of the spatial crowdsourcing platform in the fields of express delivery, food delivery, and intelligent transportation has attracted widespread attention. As a typical problem in spatial crowdsourcing, online task matching problem has been widely studied. Most of the existing researches are based on the task allocation of different optimizations under one single platform. Recently, in order to solve the situation of non-uniform distribution of tasks and crowd workers on a single platform, cross online task assignment has been proposed aiming at increasing the mutual benefit through cooperations. However, existing methods lead to the situation where the local platform lends workers to other platforms, resulting in a lack of workers of itself. In this paper, we propose a Batch-Based Cooperative Task Assignment(BCTA) problem, which enables multi-platform task assignment to be completed within a tolerant time. We design a BCTA model and propose fixed-t BCTA(FT-BCTA) algorithm and adaptive BCTA(Adt-BCTA) algorithm to solve the BCTA problem. FT-BCTA focuses on a fixed batching strategy, while Adt-BCTA considers the batching strategy adaptively according to the supply and demand of multi-platforms. Extensive experiments on both real datasets and synthetic datasets show the effectiveness and efficiency of our algorithms.

Spatial crowdsourcing (SC) has proven as a promising paradigm to employ human workers to collect data from diverse Point-of-Interests (PoIs) in a given area. Different from using human participants, we propose a novel air-ground SC scenario to fully take advantage of benefits brought by unmanned vehicles (UVs), including unmanned aerial vehicles (UAVs) with controllable high mobility and unmanned ground vehicles (UGVs) with abundant sensing resources. The objective is to maximize the amount of collected data, geographical fairness among all PoIs, and minimize the data loss and energy consumption, integrated as one single metric called "efficiency". We explicitly explore both individuality and cooperation natures of UAVs and UGVs by proposing a multi-agent deep reinforcement learning (MADRL) framework called "h/i-MADRL". Compatible with all multi-agent actor-critic methods, h/i-MADRL adds two novel plug-in modules: (a) h-CoPO, which models the cooperation preference among heterogeneous UAVs and UGVs; and (b) i-EOI, which extracts the UV’s individuality and encourages a better spatial division of work by adding intrinsic reward. Extensive experimental results on two real-world datasets on Purdue and NCSU campuses confirm that h/i-MADRL achieves a better exploration of both individuality and cooperation simultaneously, resulting in a better performance in terms of efficiency compared with five baselines.

Maximal biclique enumeration is a fundamental problem in bipartite graph data analysis. Existing biclique enumeration methods mainly focus on non-attributed bipartite graphs and also ignore the fairness of graph attributes. In this paper, we introduce the concept of fairness into the biclique model for the first time and study the problem of fairness-aware biclique enumeration. Specifically, we propose two fairness-aware biclique models, called single-side fair biclique and bi-side fair biclique respectively. To efficiently enumerate all single-side fair bicliques, we first present two non-trivial pruning techniques, called fair α-β core pruning and colorful fair α-β core pruning, to reduce the graph size without losing accuracy. Then, we develop a branch and bound algorithm, called FairBCEM, to enumerate all single-side fair bicliques on the reduced bipartite graph. To further improve the efficiency, we propose an efficient branch and bound algorithm with a carefully-designed combinatorial enumeration technique. Note that all of our techniques can also be extended to enumerate all bi-side fair bicliques. We also extend the two fairness-aware biclique models by constraining the ratio of the number of vertices of each attribute to the total number of vertices and present corresponding enumeration algorithms. Extensive experimental results on five large real-world datasets demonstrate our methods’ efficiency, effectiveness, and scalability.

Vision applications powered by deep neural networks (DNNs) are widely deployed on edge devices and solve the learning tasks of incoming data streams whose class label and input feature continuously evolve, known as domain shift. Despite its prominent presence in real-world edge scenarios, existing benchmarks used by domain adaptation methods overlook evolving domains and under represent their shifts in label and feature distributions. To address this gap, we present EdgeVisionBench, a benchmark seeking to generate evolving domains of various types and reflect their realistic label and feature shifts encountered by edge-based vision applications. To facilitate evaluating domain adaptation methods on edge devices, we provide an open-source package that automates workload generation, contains popular DNN models and compression techniques, and standardizes evaluations with interactive interfaces. Code and datasets are available at https://github.com/LINC-BIT/EdgeVisionBench.

Hypergraphs provide a powerful tool for representing group interactions in complicated networks. Analyzing statical properties of hypergraphs by sampling is an increasing fundamental research problem in the field of data processing. However, the state-of-the-art sampling methods either focus on pairwise graphs or are insensitive to the structures formed by vertices and hyperedges, resulting in estimations with low accuracy and efficiency. To efficiently characterize the properties of both vertices and hyperedges, this paper first proposes a hybrid random walk based Markov Chain Monte Carlo (MCMC) model theoretically by carefully designing its mixture states and the transition matrix. For simplifying the implementation of this model, we develop an algorithm formed by vertex and hyperedge transitions saving costs for constructing mixture states in practice along with an estimating method for accurate estimations. Furthermore, we employ a non-backtracking strategy in the vertex transitions to accelerate the convergence of the hybrid random walk and propose to skip the sampled vertices in the hyperedge transitions to avoid being trapped in the local subgraph for improving accuracy and reducing query cost. Extensive experimental results on the real-world datasets confirm the higher accuracy and efficiency of our proposed methods than the sophisticated sampling methods.

Coreset selection is a technique for efficient machine learning, which selects a subset of the training data to achieve similar model performance as using the full dataset. It can be performed with or without training machine learning models. Coreset selection with training, which iteratively trains the machine model and updates data items in the coreset, is time consuming. Coreset selection without training can select the coreset before training. Gradient approximation is the typical method, but it can also be slow when dealing with large training datasets as it requires multiple iterations and pairwise distance computations for each iteration. The state-of-the-art (SOTA) results w.r.t. effectiveness are achieved by the latter approach, i.e. gradient approximation.

Multi-agent deep reinforcement learning (MADRL) has been widely used in many scenarios such as robotics and game AI. However, existing methods mainly focus on the optimization of agents' micro policies without considering the macro strategy. As a result, they cannot perform well in complex or sparse reward scenarios like the StarCraft Multi-Agent Challenge (SMAC) and Google Research Football (GRF). To this end, we propose a hierarchical MADRL framework called "HiMacMic" with dynamic asynchronous macro strategy. Spatially, HiMacMic determines a critical position by using a positional heat map. Temporally, the macro strategy dynamically decides its deadline and updates it asynchronously among agents. We validate HiMacMic in four widely used benchmarks, namely: Overcooked, GRF, SMAC and SMAC-v2 with nine chosen scenarios. Results show that HiMacMic not only converges faster and achieves higher results than ten existing approaches, but also shows its adaptability to different environment settings.

Maximal clique enumeration is a fundamental operator in graph analysis. The model of clique, however, is typically too restrictive for real-world applications as it requires an edge for every pair of vertices. To remedy this restriction, practical graph analysis applications often resort to find relaxed cliques as alternatives. In this work, we investigate a notable relaxed clique model, called s-defective clique, which allows at most s edges to be missing. Similar to the complexity of maximal clique enumeration, the problem of enumerating all maximal s-defective cliques is also NP-hard. To solve this problem, we first develop a new polynomial-delay algorithm based on a carefully-designed reverse search technique, which can output two consecutive results within polynomial time. To achieve better practical efficiency, we propose a branch-and-bound algorithm with a novel pivoting technique. We prove that the time complexity of this algorithm depends only on O(α_sn) or O(αsδ) when using a degeneracy ordering optimization, where αs is a positive real number strictly less than 2, and δ (δ 0). We also develop several new pruning techniques to further improve the efficiency of our branch-and-bound algorithm to enumerate all relatively-large maximal s-defective cliques. In addition, we further generalize our pivot-based branch-and-bound algorithm to enumerate all maximal subgraphs satisfying a hereditary property. Here we call a graph meeting the hereditary property if all its subgraphs have the same property as itself. Finally, extensive experiments on 11 datasets demonstrate the efficiency, effectiveness, and scalability of the proposed solutions.

Finding cohesive subgraphs from a bipartite graph is a fundamental operator in bipartite graph analysis. In this paper, we focus on the problem of mining cohesive subgraphs from a bipartite graph that satisfy a hereditary property. Here a cohesive subgraph meets the hereditary property if all of its subgraphs satisfy the same property as itself. We show that several important cohesive subgraph models, such as maximal biclique and maximal k-biplex, satisfy the hereditary property. The problem of enumerating all maximal hereditary subgraphs was known to be NP-hard. To solve this problem, we first propose a novel and general pivot-based enumeration framework to efficiently enumerate all maximal hereditary subgraphs in a bipartite graph. Then, based on our general framework, we develop a new pivot-based algorithm with several pruning techniques to enumerate all maximal bicliques. We prove that the worst-case time complexity of our pivot-based maximal biclique enumeration algorithm is O(m x 2n/2 ) (or O(m\times 1.414^n)) which is near optimal since there exist up to O(2n/2 ) maximal bicliques in a bipartite graph with n vertices and m edges. Moreover, we also show that our algorithm can achieve polynomial-delay time complexity with a slight modification. Third, on the basis of our general framework, we also devise a novel pivot-based algorithm with several non-trivial pruning techniques to enumerate maximal k-biplexes in a bipartite graph. Finally, we conduct extensive experiments using 11 real-world bipartite graphs to evaluate the proposed algorithms. The results show that our pivot-based solutions can achieve one order of magnitude (three orders of magnitude) faster than the state-of-the-art maximal biclique enumeration algorithms (maximal k-biplex enumeration algorithms).

Resistance distance is a fundamental metric to measure the similarity between two nodes in graphs which has been widely used in many real-world applications. In this paper, we study two problems on approximately computing resistance distance: (i) single-pair query which aims at calculating the resistance distance r(s, t) for a given pair of nodes (s, t); and (ii) single-source query which is to compute all the resistance distances r(s, u) for all nodes u in the graph with a given source node s. Existing algorithms for these two resistance distance query problems are often costly on large graphs. To efficiently solve these problems, we first establish several interesting connections among resistance distance, a new concept called v-absorbed random walk, random spanning forests, and a newly-developed v-absorbed push procedure. Based on such new connections, we propose three novel and efficient sampling-based algorithms as well as a deterministic algorithm for single-pair query; and we develop an online and two index-based approximation algorithms for single-source query. We show that the two index-based algorithms for single-source query take almost the same running time as the algorithms for single-pair query with the aid of a linear-size index. The striking feature of all our algorithms is that they are allowed to select an easy-to-hit node by random walks on the graph. Such an easy-to-hit landmark node v can make the v-absorbed random walk sampling, spanning tree sampling, as well as the v-absorbed push more efficient, thus significantly improving the performance of our algorithms. Extensive experiments on 5 real-life datasets show that our algorithms substantially outperform the state-of-the-art algorithms for two resistance distance query problems in terms of both running time and estimation errors.

Personalized PageRank (PPR) computation is a fundamental problem in graph analysis. The state-of-the-art algorithms for PPR computation are based on a bidirectional framework which include a deterministic forward push and a Monte Carlo sampling procedure. The Monte Carlo sampling procedure, however, often has a relatively-large variance, thus reducing the performance of the PPR computation algorithms. To overcome this issue, we develop two novel variance-reduced Monte Carlo techniques for PPR computation. Our first technique is to apply power iterations to reduce the variance of the Monte Carlo sampling procedure. We prove that conducting few power iterations can significantly reduce the variance of existing Monte Carlo estimators, only with few additional costs. Moreover, we show that such a simple and novel variance-reduced Monte Carlo technique can achieve comparable estimation accuracy and the same time complexity as the state-of-the-art bidirectional algorithms. Our second technique is a novel progressive sampling method which uses the historical information of former samples to reduce the variance of the Monte Carlo estimator. We develop several novel PPR computation algorithms by integrating both of these variance reduction techniques with two existing Monte Carlo sampling approaches, including random walk sampling and spanning forests sampling. Finally, we conduct extensive experiments on 5 real-life large graphs to evaluate our solutions. The results show that our algorithms can achieve much higher PPR estimation accuracy by using much less time, compared to the state-of-the-art bidirectional algorithms.

A (p,q)-biclique is a complete subgraph (X,Y) that |X|=p, |Y|=q. Counting (p,q)-bicliques in bipartite graphs is an important operator for many bipartite graph analysis applications. However, getting the count of (p,q)-bicliques for large p and q (e.g., p,q ≥ 10) is extremely difficult, because the number of (p,q)-bicliques increases exponentially with respect to p and q. The state-of-the-art algorithm for this problem is based on the (p,q)-biclique enumeration technique which is often costly due to the exponential blowup in the enumeration space of (p,q)-bicliques. To overcome this problem, we first propose a novel exact algorithm, called EPivoter, based on a newly-developed edge-pivoting technique. The striking feature of EPivoter is that it can count (p,q)-bicliques for all pairs of (p,q) using a combinatorial technique, instead of exhaustively enumerating all (p,q)-bicliques. Second, we propose a novel dynamic programming (DP) based h-zigzag sampling technique to provably approximate the count of the (p,q)-bicliques for all pairs of (p,q), where an h-zigzag is an ordered simple path in G with length 2h-1 (h = min{p,q}). We show that our DP-based sampling technique is very efficient. Third, to further improve the efficiency, we also propose a hybrid framework that integrates both the exact EPivoter algorithm and sampling-based algorithms. Extensive experiments on 7 real-world graphs show that our algorithms are several orders of magnitude faster than the state-of-the-art algorithm.

Spatial platforms have become increasingly important in people's daily lives. Task assignment is a critical problem in these platforms that matches real-time orders to suitable workers. Most studies only focus on independent platforms that are in a competitive relationship. Recently, an emerging service model was proposed, where orders are shared with multiple similar platforms. It aims to solve the imbalance between supply and demand through cooperation. However, it faces the following main challenges: 1) Coordinating independent platforms fairly based on the limited information; 2) Building a task assignment process with personalized algorithms. In this paper, we study real applications and define the Autonomy and Coordination Task Assignment problem (ACTA) to maximize the global revenue and fairness. We propose a framework to solve ACTA that consists of public order sending, local matching, global conflict adjustment and results notification. The framework uses mid-products and public data to train a revenue estimation model to coordinate participants. We further propose dynamic weight task assignment algorithms to guarantee fairness. Through the experiments, we prove that the platforms can obtain higher revenue, which shows the effectiveness and efficiency of our work.

Federated Graph Learning (FGL) is a distributed machine learning paradigm that enables collaborative training on large-scale subgraphs across multiple local systems. Existing FGL studies fall into two categories: (i) FGL Optimization, which improves multi-client training in existing machine learning models; (ii) FGL Model, which enhances performance with complex local models and multi-client interactions. However, most FGL optimization strategies are designed specifically for the computer vision domain and ignore graph structure, presenting dissatisfied performance and slow convergence. Meanwhile, complex local model architectures in FGL Models studies lack scalability for handling large-scale subgraphs and have deployment limitations. To address these issues, we propose Federated Graph Topology-aware Aggregation (FedGTA), a personalized optimization strategy that optimizes through topology-aware local smoothing confidence and mixed neighbor features. During experiments, we deploy FedGTA in 12 multi-scale real-world datasets with the Louvain and Metis split. This allows us to evaluate the performance and robustness of FedGTA across a range of scenarios. Extensive experiments demonstrate that FedGTA achieves state-of-the-art performance while exhibiting high scalability and efficiency. The experiment includes ogbn-papers100M, the most representative large-scale graph database so that we can verify the applicability of our method to large-scale graph learning. To the best of our knowledge, our study is the first to bridge large-scale graph learning with FGL using this optimization strategy, contributing to the development of efficient and scalable FGL methods.

Anomaly detection in time series data has been studied for decades in both statistics and computer science. Various algorithms have been proposed for different scenarios, such as fraud detection, environmental monitoring, manufacturing, and healthcare. However, there is a lack of comparative evaluation of these state-of-the-art approaches, especially in the same test environment and with the same benchmark, making it difficult for users to select an appropriate method for real-world applications. In this paper, we present a taxonomy of anomaly detection methods based on the main features, i.e., data dimension, processing technique, and anomaly type and six inner classes. We perform systematic intra- and inter-class comparisons of seventeen state-of-the-art algorithms on real and synthetic datasets with a point metric commonly used in classification problems and a range metric specifically designed for subsequence anomalies in time series data. We analyze the properties of these algorithms and test them in terms of effectiveness, efficiency, and robustness to anomaly rates, data sizes, number of dimensions, anomaly patterns, and threshold settings. We also test their performance in different use cases. Finally, we provide a practical guide for detecting anomalies in time series and discussions.

With the exponential growth of video data, there is a pressing need for efficient video analysis technology. Modern query frameworks aim to accelerate queries by reducing the frequency of calls to expensive deep neural networks, which often overlook the overhead associated with video decoding and retrieval. Furthermore, video storage frameworks optimize video retrieval through video partition or caching, often relying on prior information about the query workload. To further accelerate queries, this study introduces a novel tile-based video management framework, called TVM, which leverages the semantic information embedded in videos, without being dependent on specific query workloads. By constructing a tile-based semantic index for newly ingested videos, TVM effectively reduces the size of decoded and processed video data. To achieve this, TVM introduces an optimal index construction algorithm that utilizes cost function and pseudo-labels. Additionally, the framework proposes a query-driven tile parallel decoding algorithm and resource caching algorithms, which further expedite the retrieval of video frames. Experimental results demonstrate that TVM can significantly enhance the throughput of various query tasks, achieving a notable speedup of more than 5.6×.

Core decomposition on uncertain graphs is a fundamental problem in graph analysis. Given an uncertain graph G, the core decomposition problem is to determine all (k, \eta)-cores in G, where a (k, \eta)-core is a maximal subgraph of G such that each node has an \eta-degree no less than k within the subgraph. The state-of-the-art algorithm for solving this problem is based on a peeling technique which iteratively removes nodes with the smallest \eta-degrees and also dynamically updates their neighbors' \eta-degrees. Unfortunately, we find that such a peeling algorithm with the dynamical \eta-degree updating technique is incorrect due to the inaccuracy of the recursive floating-point number division operations involved in the dynamical updating procedure. To solve this problem, we propose a bottom-up algorithm based on an on-demand computational strategy. To further improve the efficiency, we also develop a more-efficient top-down algorithm with several nontrivial optimization techniques. Both of our algorithms do not involve any floating-point number division operations, thus the correctness can be guaranteed. We conduct extensive experiments to evaluate our algorithms using five large real-life datasets. The results show that our algorithms are at least three orders of magnitude faster than the existing exact algorithms on large uncertain graphs.

Online spatial crowdsourcing platforms provide popular O2O services in people's daily. Users submit real-time tasks through the Internet and require the platform to immediately assign workers to serve them. However, the imbalance distribution of tasks and workers leads to the rejection of some tasks, which reduces the profit of the platform. In this paper, we propose that similar platforms can form an alliance to make full use of the global service supply through cooperation. We name the problem asGlobalTaskAssignment (GTA), in which platforms are allowed to hire idle workers from other platforms to improve the profit of all the platforms together. Different from relevant works, the decision-makers in GTA are platforms rather than individual workers, which can better assign workers in all platforms and improve the overall profit. We design an auction-based incentive mechanism (AIM), to motivate platforms to rent idle workers to other platforms so that increase their own profit. Based on the mechanism, we propose a greedy-based assignment algorithm (BaseGTA), in which platforms greedily maximizes their current profit. We further propose a prediction-based assignment algorithm (ImpGTA), in which platforms make decisions based on the spatial-temporal distribution in the future time. Experimental results show that platforms using our algorithms can achieve higher profit than the existing studies.

Anomaly detection (AD) aims to distinguish abnormal instances from what is defined as normal, which strongly correlates with the safe and robust applications of machine learning. A well-performed anomaly detector often relies on the training on massive labeled data, while it is of high cost to annotate data in practice. Fortunately, this dilemma can be solved by transferring the knowledge of a label-rich dataset (source domain) to assist the learning on the label-scarce dataset (target domain), which is known as domain adaptation in transfer learning. In this paper, we propose a Multi-spectral Cross-domain Representation Alignment (MsRA) method for the anomaly detection in the domain adaptation setting, where we can only access normal source data andlimitednormal target data. Specifically, MsRA first constructs multi-spectral feature representations by fusing different frequency components of the original features, which mitigates the information scarcity due to limited target training data by capturing richer input pattern information. Then we employ the adversarial training strategy to learn domain-invariant features and force the features of normal data to be more compact by the center clustering. Finally, the distance of each sample to the prototype of normal class can be used as its anomaly score, where the prototype is the center of both source and target data. In this way, we achieve anomaly detection in an end-to-end manner, without two-stage training for feature extraction and anomaly detection. Comprehensive experiments on cross-domain anomaly detection benchmarks validate the effectiveness of MsRA.

Recommender systems are playing a significant role in modern society to alleviate the information/choice overload problem, since Internet users may feel hard to identify the most favorite items or products from millions of candidates. Thanks to the recent successes in computer vision, auxiliary learning has become a powerful means to improve the performance of a target (primary) task. Even though helpful, the auxiliary learning scheme is still less explored in recommendation models. To integrate the auxiliary learning scheme, we propose a novel meta auxiliary learning framework to facilitate the recommendation model training, i.e., user and item latent representations. Specifically, we construct two self-supervised learning tasks, regarding both users and items, as auxiliary tasks to enhance the representation effectiveness of users and items. Then the auxiliary and primary tasks are further modeled as a meta learning paradigm to adaptively control the contribution of auxiliary tasks for improving the primary recommendation task. This is achieved by an implicit gradient method guaranteeing less time complexity compared with conventional meta learning methods. Via a comparison using four real-world datasets with a number of state-of-the-art methods, we show that the proposed model outperforms the best existing models on the Top-K recommendation by 3% to 23%.

Unsupervised domain adaptation enables knowledge transfer from a labeled source domain to an unlabeled target domain by reducing the cross-domain distribution discrepancy, and the adversarial learning based paradigm has achieved remarkable success. On top of this, recent works seeks to further regularize the classification decision boundary via self-training to learn target adaptive classifier with pseudo-labeled target samples. However, since pseudo labels are inevitably noisy, most of prior methods focus on manually designing elaborate target selection algorithms or optimization objectives. Different from them, we propose a meta-learning based target-reweighting regularization algorithm called MetaReg. Specifically, MetaReg is motivated by the intuition that an ideal target classifier trained on correct target pseudo labels should make small classification errors on target-like source samples. Therefore, we explicitly define a meta reweighting problem that aims to find optimal weights for different samples by minimizing the classification loss on a class-balanced set consisting of source samples that are most similar to target ones. The optimization problem is solved efficiently with a simplified approximation technique. As a result, the automatically learned optimal weights are utilized to reweight pseudo-labeled target samples and regularize the model learning. Comprehensive experiments verify that MetaReg outperforms the non-regularized UDA counterparts with state-of-the-art performance.

Given a graph, searching for a community containing a query vertex is a fundamental problem and has found many applications. Most existing community search models are based on non-attributed or vertex-attributed graphs. In many real-world graphs, however, the edges carry the richest information to describe the interactions between vertices; hence, it is important to take the information into account in community search. In this paper, we conduct a pioneer study on the community search on edge-attributed graphs. We proposed the Edge-Attributed Community Search (EACS) problem, which aims to extract a subgraph that contains the given query vertex while its edges have the maximum attribute similarity. We prove that the EACS problem is NP-hard and propose both exact and 2-approximation algorithms to address EACS. Our exact algorithms run up to 2320.34 times faster than the baseline solution. Our approximate algorithms further improve the efficiency by up to 2.93 times. We conducted extensive experiments to demonstrate the efficiency and effectiveness of our algorithms.

Exploiting the correlations between medical features is essential to the success of healthcare data analysis. However, most existing methods are either suffering large estimation variance for data insufficiency or inflexible in terms of demanding task-specific medical knowledge. In this paper, we propose a novel patient health representation learning framework dubbedSAFARI.SAFARIlearns a compact representation by imposing a clinical-fact-inspired task-agnostic correlational sparsity prior to the correlations of medical feature pairs. Specifically, we learn the compact representation by solving the bi-level optimization problem, which involves solving the high-level inter-group correlations and the nested lower-level intra-group correlations. We leverage the Laplacian kernel as a robust metric for feature grouping and graph neural networks for solving the bi-level optimization problem following the optimal value reformulation paradigm. Experiments on five datasets of various inputs and tasks demonstrate the efficacy ofSAFARI. The discovered findings are also consistent with our insights and medical literature, which can provide valuable clinical explanations.

Recommender systems across many Internet services have become a critical part of online businesses, as consumers would refer to them before making decisions. However, the lack of explicit ratings for items on many services makes it challenging to capture user preferences and item characteristics. Both academia and the industry have drawn attention to rating predications as a fundamental problem in recommendation systems. With the emergence of social networks, social recommender systems have been proposed to utilize the relationship between users and items to alleviate the data sparsity problem for rating predictions. However, they either concentrate on the opinion mining for each user and item, or consider the connections between users only. In this paper, we present an effective framework, Triple-hierarchical Attention Graph-based social rating prediction (TAG), to exploit the social relationships between users, the user-item interest relationships, the correlation relationships between items, and reviews for rating predictions. In order to consider opinions from reviews and these complex relationships, we first employ two triple-hierarchical attention to extract user and item features from reviews. We then design an inductive GNN, which generates effective embedding for users and items. Experiments over Yelp show that TAG outperforms state-of-the-art methods across RMSE, MAE, and NDCG metrics.

Densest subgraphs are often interpreted ascommunities, based on a basic assumption that the connections inside a community are much denser than those between communities. In a graph with temporal information, a densest periodic subgraph is the most densely connected periodic behavior which needs to be captured. Unfortunately, the existing work do not model the densest periodic subgraph in temporal graphs, and the current algorithms for mining the densest subgraph cannot be applied to detect the densest periodic subgraph in the temporal networks. To tackle this problem, we propose a novel model, called the densest$\sigma$-periodic subgraph, which presents the densest periodic subgraph whose period size is$\sigma$. We prove that finding the densest$\sigma$-periodic subgraph can be solved in polynomial time, but it is still challenging because the naive algorithm needs to repeatedly invoke a maximum flow algorithm for many periodic subgraphs. To compute the densest$\sigma$-periodic subgraph efficiently, we first develop an effective pruning technique based on the degeneracy of the graph to significantly prune the number of the periodic subgraphs. Then, we present a more efficient algorithm that can reduce the computations for the degeneracy and maximum flow. Next, we develop a greedy algorithm that can compute the approximate densest$\sigma$-periodic subgraph and achieve an approximation ratio of 1/2. Finally, the results of extensive experiments on several real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

Data warehouse and OLAP (Online Analytical Processing) are effective tools for decision support on traditional relational data and static multidimensional network data. However, many real-world multidimensional networks are often modeled as temporal multidimensional networks, where the edges in the network are associated with temporal information. Such temporal multidimensional networks typically cannot be handled by traditional data warehouse and OLAP techniques. To fill this gap, we propose a novel data warehouse model, named$\mathsf {Temporal{ }\; Graph{ }\; Cube}$, to support OLAP queries on temporal multidimensional networks. Through supporting OLAP queries in any time range, users can obtain summarized information of the network in the time range of interest, which cannot be derived by using traditional static graph OLAP techniques. We propose a segment-tree based indexing technique to speed up the OLAP queries, and also develop an index-updating technique to maintain the index when the temporal multidimensional network evolves over time. In addition, we also propose a novel concept called$\mathsf {similarity{ }\; of{ }\; snapshots}$which shows a strong correlation with the efficiency of indexing technique and can provide a good reference on the necessity of building the index. The results of extensive experiments on two large real-world datasets demonstrate the effectiveness and efficiency of the proposed method.

Unsupervised domain adaptation (UDA) aims to utilize knowledge from a label-rich source domain to understand a similar yet distinct unlabeled target domain. Notably, global distribution statistics across domains and local semantic characteristics across samples, are two essential factors of data analysis that should be fully explored. Most existing UDA approaches either harness only one of them or fail to closely associate them for efficient adaptation. In this work, we propose a unified framework, called Collaborative Alignment Framework (CAF), which simultaneously reduces the global domain discrepancy and preserves the local semantic consistency for cross-domain knowledge transfer in a collaborative manner. Specifically, for domain-oriented alignment, we utilize adversarial training or minimize the Wasserstein distance between the two distributions to learn domain-level invariant representations. For semantic-oriented matching, we capture the semantic discrepancy between the predictions of two diverse task-specific classifiers and enhance the features of target data to be near the support of the source data class-wisely, which promotes semantic consistency across domains effectively. These two adaptation processes can be deeply intertwined in CAF via collaborative training, thus CAF can learn domain-invariant and semantic-consistent feature representations. Extensive experiments on four popular benchmarks, including DomainNet, VisDA-2017, Office-31, and ImageCLEF, demonstrate the proposed methods significantly outperform the existing methods, especially on the large-scale dataset. The code is available athttps://github.com/BIT-DA/CAF.

Cohesive subgraph mining on attributed graphs is a fundamental problem in graph data analysis. Existing cohesive subgraph mining algorithms on attributed graphs do not consider thefairnessof attributes in the subgraph. In this article, we, for the first time, introduce fairness into the widely-used clique model to mine fairness-aware cohesive subgraphs. In particular, we propose three novel fairness-aware maximal clique models on attributed graphs, called weak fair clique, strong fair clique and relative fair clique, respectively. To enumerate all weak fair cliques, we develop an efficient backtracking algorithm called$\mathsf{WFCEnum}$equipped with a novel colorful$k$-core based pruning technique. We also propose an efficient enumeration algorithm called$\mathsf{SFCEnum}$to find all strong fair cliques based on a new attribute-alternatively-selection search technique. To further improve the efficiency, we also present several non-trivial ordering techniques for both weak and strong fair clique enumerations. To enumerate all relative fair cliques, we design an enhanced colorful$k$-core based pruning technique for 2D attributes, and develop two efficient search algorithms:$\mathsf{RFCRefineEnum}$and$\mathsf{RFCAlterEnum}$for arbitrary dimension attributes. The results of extensive experiments on four real-world graphs demonstrate the efficiency, scalability and effectiveness of the proposed algorithms.

In this paper, we study a new problem of seeking stable subgraph isomorphisms for a query graph in a temporal graph. To solve our problem, we first develop a pruning-based search algorithm using several new pruning tricks to prune the unpromising matching results during the search procedure. To further improve the efficiency, we propose a novel index structure called BCCIndex, based on an idea of bi-connected component decomposition of the query graph, which can efficiently support the stable subgraph isomorphism search. Equipped with the BCCIndex, we present an efficient query processing algorithm based on a carefully designed tree join technique. We conduct extensive experiments to evaluate our algorithms on four large real-life datasets, and the results demonstrate the efficiency and effectiveness of our algorithms.

Hypergraph streams provide an efficient model to express and preserve complex connections in various applications. Triangles in a hypergraph can be formed by vertices and hyperedges. The specific counts of triangles are important to analyze various applications. Due to the huge costs of counting triangles based on the whole datasets, a sampling-and-estimating framework has low overhead while obtaining a relatively accurate result. However, existing sampling algorithms focus on pairwise graph streams, they estimate the counts of triangles formed by vertices with large estimation errors and can not be applied to count triangles formed by hyperedges. Therefore, this paper first proposes a sampling-and-estimating framework that produces hyperedge samples using a reservoir with static capacity to estimate the total counts of triangles by inferring the probabilities of forming the triangles respectively. Furthermore, to improve the estimation accuracy, this paper proposes another sampling-and-estimating framework to produce samples in the form of hyperedge pairs which can be used to compute the probabilities of the formations of triangles more accurately and then estimate the total triangle counts with smaller estimation variances. The extensive experiments based on real-world datasets confirm the efficiency and accuracy of our proposed frameworks for counting triangles in different types of hypergraphs at a small sampling ratio.

Searching subgraph containment, also called subgraph matching in hypergraphs, is to enumerate all the embeddings of a data hypergraph with a given query hypergraph, which plays an important role in the analysis of hypergraph-modeled applications. However, existing subgraph matching frameworks mainly focus on pairwise graphs and the existing techniques can not efficiently be applied to search subgraph containment at low costs. Therefore, this paper proposes HyperISO to efficiently search subgraph containment that consists of three parts: 1) new filtering techniques driven by exploring the properties and connections of hyperedges to reduce unpromising products for the sake of low matching costs, 2) a novel ordering strategy that is able to generate an optimized matching process by considering both the sizes of hyperedge candidates and the unmatched vertices of the hyperedges, and 3) a dual enumeration algorithm to list both the vertex and hyperedge mappings. Extensive experiments on both real and synthetic data show that HyperISO outperforms the best among the sophisticated subgraph matching frameworks and meanwhile verify the efficiency of HyperISO in various types of hypergraphs.

Surface cracks in infrastructure are a key indicator of structural safety and degradation. Visual-based crack detection is a critical task for the enormous application demands of infrastructure industries. Convolution operations have been widely deployed due to the strong feature learning abilities. However, global feature dependencies of multi-scale cracks are ignored due to the limited receptive field.In addition, the detection of cracks with low contrast suffers a serious performance loss.Therefore, to address the scale-adaptive crack detection problem, we propose a context-aware correlation convolutional network for scale-adaptive crack detection named CASA-Net. CASA-Net is capable of extracting multi-scale crack features for distinguishing between cracks and surface backgrounds, and evaluating feature correlations to capture global contexts. CASA-Net is composed of the multi-scale distinguishing feature extraction (MDFE) module and the context-aware feature correlation (CAFC) module. Specifically, the MDFE module consists of multiple cascaded convolutional layers and distinguishing feature extraction layers (DFLayers). The CAFC module consists of a mapping block and cascaded correlators to capture the context-aware features for long-range interactions. The performance of CASA-Net is evaluated on a benchmark crack dataset. The experimental results indicate that CASA-Net outperforms rival methods by achieving an F1-Score of 0.65 and an AP50 of 63.9%.

Finding all maximal k-plexes on networks is a fundamental research problem in graph analysis due to many important applications, such as community detection, biological graph analysis, and so on. A k-plex is a subgraph in which every vertex is adjacent to all but at most k vertices within the subgraph. In this paper, we study the problem of enumerating all large maximal k-plexes of a graph and develop several new and efficient techniques to solve the problem. Specifically, we first propose several novel upper-bounding techniques to prune unnecessary computations during the enumeration procedure. We show that the proposed upper bounds can be computed in linear time. Then, we develop a new branch-and-bound algorithm with a carefully-designed pivot re-selection strategy to enumerate all k-plexes, which outputs all k-plexes in O(n2?k n) time theoretically, where n is the number of vertices of the graph and ? k is strictly smaller than 2. In addition, a parallel version of the proposed algorithm is further developed to scale up to process large real-world graphs. Finally, extensive experimental results show that the proposed sequential algorithm can achieve up to 2× to 100× speedup over the state-of-the-art sequential algorithms on most benchmark graphs. The results also demonstrate the high scalability of the proposed parallel algorithm. For example, on a large real-world graph with more than 200 million edges, our parallel algorithm can finish the computation within two minutes, while the state-of-the-art parallel algorithm cannot terminate within 24 hours.

Data is increasingly being bought and sold online, and data market platforms have emerged to facilitate these activities. However, current mechanisms for pricing data mainly focus on traditional relational data. In this paper, we propose a framework GQP for pricing graph data on the data market platform. Specifically, given a set of graph price points and a graph query, we can efficiently compute the price of the query based on the graph price points. We first identify an important property (called arbitrage-free) GQP should satisfy with, such that GQP can effectively price the graph query. We then study the exact pricing problem (NP-completeness) and develop an efficient approximation algorithm to solve the problem. We also study the approximate pricing when the query cannot be answered by price points exactly. Furthermore, to avoid the expensive computing cost of updating graph price points, we study the dynamic query pricing and propose novel solutions to reuse the computed graph price points to reduce the computational complexity. Finally, we use real-life data and synthetic data to experimentally verify that the proposed algorithms are able to effectively and efficiently price large graph data based on the framework GQP.

Core decomposition on uncertain graphs is shown to be a key problem in graph analysis. However, existing algorithms for solving this problem are based on a peeling algorithm with the dynamically updating technique, which can lead to relatively large errors due to the inaccuracy of the recursive floating-point number division operations. In this paper, we first develop two novel algorithms, a bottom-up approach and a top-down approach, which do not involve any floating-point number division operations to guarantee correctness. Then, we develop a parallel version for each approach to deal with large graphs. Extensive experimental results evidence the efficiency, effectiveness, and scalability of our proposed algorithms.

The h-clique based higher-order cohesive subgraph mining is an important operator in graph analysis. The h-clique core and h-clique densest subgraph are two representative higher-order cohesive subgraph models which have been widely used in many practical applications. However, computing these two models on large graphs is often very costly due to the hardness of counting the h-cliques. In this paper, we propose a relaxed higher-order cohesive subgraph model, called colorful h-star core, based on counting the number of colorful h-stars. Unlike the h-cliques, we show that the colorful h-stars can be counted and updated very efficiently using a novel dynamic programming (DP) algorithm. Based on the proposed DP algorithm, we develop an efficient colorful h-star core decomposition algorithm which takes O(h × m) time and uses O(h × n+m) space, where$m$and$n$denote the number of edges and nodes of the graph respectively. In addition, we also propose a graph reduction technique based on our colorful h-star core model to accelerate the computation of the state-of-the-art approximation algorithm for h-clique densest subgraph mining. Moreover, we show that the colorful h-star core can also provide a very good approximation of the h-clique densest subgraph. The results of comprehensive experiments on 11 large real-world datasets demonstrate the efficiency, scalability and effectiveness of the proposed algorithms.

Cohesive sub graph mining on attributed graphs is a fundamental problem in graph data analysis. Existing cohesive sub graph mining algorithms on attributed graphs do not consider the fairness of attributes in the subgraph. In this paper, we for the first time introduce fairness into the widely-used clique model to mine fairness-aware cohesive subgraphs. In particular, we propose two novel fairness-aware maximal clique models on attributed graphs, called weak fair clique and strong fair clique respectively. To enumerate all weak fair cliques, we develop an efficient backtracking algorithm called WFCEnum equipped with a novel colorful k-core based pruning technique. We also propose an efficient enumeration algorithm called SFCEnum to find all strong fair cliques based on a new attribute-alternatively-selection search technique. To further improve the efficiency, we also present several non-trivial ordering techniques for both weak and strong fair clique enumeration. The results of extensive experiments on four real-world graphs demonstrate the efficiency and effectiveness of the proposed algorithms.

Spatial crowdsourcing (SC) has been proved quite successful by employing human participants to achieve certain tasks like Uber and Gigwalk. Meanwhile, with the fast devel-opment of unmanned aerial vehicles (e.g., drones), they have become a new source of data collectors equipped with a variety of different sensors. In this paper, we propose a novel SC scenario, enabling human participants to work collaboratively with drones in the presence of multiple charging stations to achieve certain data collection tasks, like videography and surveillance. We propose a novel deep reinforcement learning (D RL) framework called “FD- MAPPO (Cubic Map)”, which consists of a fully de-centralized multi-agent DRL (MADRL) algorithm called “Fully Decentralized Multi-Agent Proximal Policy Optimization (FD-MAPPO)”, and a spatiotemporal memory augmented neural network with novel cubic writing and spatially contextual reading mechanisms called “Cubic Map”. Cubic Map extracts long-term spatiotemporal features, navigates drones to accurately locate the position of the target, i.e., charging stations or sensors. Extensive results on two real datasets of KAIST and NCSU campuses show that FD- MAPPO (Cubic Map) consistently outperforms six other baselines in terms of efficiency.

The influence maximization in a social network has been extensively studied, however, existing works have neglected the fact that time-dependent reachable information plays an important role in this query processing. Many real-world applications, such as location-based recommendations, location-based advertisements, and location-based emergency message distribution, require such a query. In this paper, we formally define reachability-driven influence maximization (RDIM) in time-dependent road-social networks, to find a seed set that maximizes the expected influence over potential users, i.e., target users, who are likely to reach a given location within a deadline. To efficiently compute the influence diffusion, we define a versatile influence (VI) diffusion model based on user relationships and time-dependent location information. The RDIM has two critical challenges: identifying the target users and finding the seed nodes. We propose a TS-index with temporal and regional dimensions for identifying the target users by employing a reachable region. To find seed nodes, we construct a CTS-index by extending a community dimension into the TS-index to enhance the calculation of social influence by using the relationship between communities and the reachable region. Finally, we use the real road and social network data to empirically verify the efficiency and effectiveness of our solutions.

Subgraph matching over graphs has been extensive-ly studied, due to its wide applications in knowledge bases, social networks, and among others. To catch the inconsistency and errors that commonly exist in these graphs, this paper studies consistent subgraph matching (CSM), i.e., finding the common matches in every consistent graph repair w.r.t a set of conditional graph dependencies (CGDs). We concentrate on subset, superset and symmetric difference graph repairs. We study fundamental problems for CGDs and CSM. We show that the satisfiability, im-plication, and validation problems of CGDs are coNP-complete, coNP-complete and NP-complete, respectively. We also show that the CSM problem (under any kind of repair) is NP-complete. We provide (parallel) algorithms to solve CSM, and guarantee to reduce running time when given more processors. Using real-life and synthetic graphs, we empirically verify the efficiency and effectiveness of our algorithms.

Betweenness centrality, measured by the number of times a vertex occurs on all shortest paths of a graph, has been recognized as a key indicator for the importance of a vertex in the network. However, the betweenness of a vertex is often very hard to compute because it needs to explore all the shortest paths between the other vertices. Recently, a relaxed concept called ego-betweenness was introduced which focuses on computing the betweenness of a vertex in its ego network. In this work, we study a problem of finding the top-k vertices with the highest ego-betweennesses. We first develop two novel search algorithms equipped with a basic upper bound and a dynamic upper bound to efficiently solve this problem. Then, we propose local-update and lazy-update solutions to maintain the ego-betweennesses for all vertices and the top-k results when the graph is updated by an edge insertion and deletion, respectively. In addition, we also present two efficient parallel algorithms to further improve the efficiency. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

Knowledge distillation (KD) has demonstrated its effectiveness to boost the performance of graph neural networks (GNNs), where its goal is to distill knowledge from a deeper teacher GNN into a shallower student GNN. However, it is actually difficult to train a satisfactory teacher GNN due to the well-known over-parametrized and over-smoothing issues, leading to invalid knowledge transfer in practical applications. In this paper, we propose the first Free-direction Knowledge Distillation framework via Reinforcement learning for GNNs, called FreeKD, which is no longer required to provide a deeper well-optimized teacher GNN. The core idea of our work is to collaboratively build two shallower GNNs in an effort to exchange knowledge between them via reinforcement learning in a hierarchical way. As we observe that one typical GNN model often has better and worse performances at different nodes during training, we devise a dynamic and free-direction knowledge transfer strategy that consists of two levels of actions: 1) node-level action determines the directions of knowledge transfer between the corresponding nodes of two networks; and then 2) structure-level action determines which of the local structures generated by the node-level actions to be propagated. In essence, our FreeKD is a general and principled framework which can be naturally compatible with GNNs of different architectures. Extensive experiments on five benchmark datasets demonstrate our FreeKD outperforms two base GNNs in a large margin, and shows its efficacy to various GNNs. More surprisingly, our FreeKD has comparable or even better performance than traditional KD algorithms that distill knowledge from a deeper and stronger teacher GNN.

A data lake is a repository for massive raw and heterogeneous data, which includes multiple data models with different data schemas and query interfaces. Keyword search can extract valuable information for users without the knowledge of underlying schemas and query languages. However, conventional keyword searches are restricted to a certain data model and cannot easily adapt to a data lake. In this paper, we study a novel keyword search. To achieve high accuracy and efficiency, we introduce canonical graphs and then integrate semantically related vertices based on vertex representations. A matching entity based keyword search algorithm is presented to find answers across multiple data sources. Finally, extensive experimental study shows the effectiveness and efficiency of our solution.

Maximal clique enumeration on uncertain graphs is a fundamental problem in uncertain graph analysis. In this paper, we study a problem of enumerating all maximal (k,n)-cliques on an uncertain graph G, where a vertex set H of G is a maximal (k,n)-clique if (1) H (|H| ≥ k) is a clique with probability no less than n, and (2) H is a maximal vertex set satisfying (1). The state-of-the-art algorithms for enumerating all maximal (k,n)-cliques are based on a set enumeration technique which are often very costly. This is because the set enumeration based techniques may explore all subsets of a maximal (k,n)-clique, thus resulting in many unnecessary computations. To overcome this issue, we propose several novel and efficient pivot-based algorithms to enumerate all maximal (k,n)-cliques based on a newly-developed pivot-based pruning principle. Our pivot-based pruning principle is very general which can be applied to speed up the enumeration of any maximal subgraph that satisfies a hereditary property. Here the hereditary property means that if a maximal subgraph H satisfies a property P, any subgraph of H also meets P. To the best of our knowledge, our work is the first to systematically explore the idea of pivot for maximal clique enumeration on uncertain graphs. In addition, we also develop a nontrivial size-constraint based pruning technique and a new graph reduction technique to further improve the efficiency. Extensive experiments on nine real-world graphs demonstrate the efficiency, effectiveness, and scalability of the proposed algorithms.

Computing the personalized PageRank vector is a fundamental problem in graph analysis. In this paper, we propose several novel algorithms to efficiently compute the personalized PageRank vector with a decay factor α based on an interesting connection between the personalized PageRank values and the weights of random spanning forests of the graph. Such a connection is derived based on a newly-developed matrix forest theorem on graphs. Based on this, we present an efficient spanning forest sampling algorithm via simulating loop-erased α-random walks to estimate the personalized PageRank vector. Compared to all existing methods, a striking feature of our approach is that its performance is insensitive w.r.t. (with respect to) the parameter α. As a consequence, our algorithm is often much faster than the state-of-the-art algorithms when α is small, which is the demanding case for many graph analysis tasks. We show that our technique can significantly improve the efficiency of the state-of-the-art algorithms for answering two well-studied personalized PageRank queries, including single source query and single target query. Extensive experiments on seven large real-world graphs demonstrate the efficiency of the proposed method.

K-clique counting is a fundamental problem in network analysis which has attracted much attention in recent years. Computing the count of k-cliques in a graph for a large k (e.g., k = 8) is often intractable as the number of k-cliques increases exponentially w.r.t. (with respect to) k. Existing exact k-clique counting algorithms are often hard to handle large dense graphs, while sampling-based solutions either require a huge number of samples or consume very high storage space to achieve a satisfactory accuracy. To overcome these limitations, we propose a new framework to estimate the number of k-cliques which integrates both the exact k-clique counting technique and two novel color-based sampling techniques. The key insight of our framework is that we only apply the exact algorithm to compute the k-clique counts in the sparse regions of a graph, and use the proposed sampling-based techniques to estimate the number of k-cliques in the dense regions of the graph. Specifically, we develop two novel dynamic programming based k-color set sampling techniques to efficiently estimate the k-clique counts, where a k-color set contains k nodes with k different colors. Since a k-color set is often a good approximation of a k-clique in the dense regions of a graph, our sampling-based solutions are extremely efficient and accurate. Moreover, the proposed sampling techniques are space efficient which use near-linear space w.r.t. graph size. We conduct extensive experiments to evaluate our algorithms using 8 real-life graphs. The results show that our best algorithm is at least one order of magnitude faster than the state-of-the-art sampling-based solutions (with the same relative error 0.1%) and can be up to three orders of magnitude faster than the state-of-the-art exact algorithm on large graphs.

With the continuous development of spatial crowdsourcing platform, online task assignment problem has been widely studied as a typical problem in spatial crowdsourcing. Most of the existing studies are based on a single-platform task assignment to maximize the platform's revenue. Recently, cross online task assignment has been proposed, aiming at increasing the mutual benefit through cooperations. However, existing methods fail to consider the data privacy protection in the process of cooperation and cause the leakage of sensitive data such as the location of a request and the historical data of cooperative platforms. In this paper, we propose Privacy-preserving Cooperative Online Matching (PCOM), which protects the privacy of the users and workers on their respective platforms. We design a PCOM framework and provide theoretical proof that the framework satisfies the differential privacy property. We then propose two PCOM algorithms based on two different privacy-preserving strategies. Extensive experiments on real and synthetic datasets confirm the effectiveness and efficiency of our algorithms.

Temporal graphs are ubiquitous. Mining communities that are bursting in a period of time is essential for seeking real emergency events in temporal graphs. Unfortunately, most previous studies on community mining in temporal networks ignore the bursting patterns of communities. In this paper, we study the problem of seeking bursting communities in a temporal graph. We propose a novel model, called the ( l , δ)-maximal bursting core, to represent a bursting community in a temporal graph. Specifically, an ( l , δ)-maximal bursting core is a temporal subgraph in which each node has an average degree no less than δ in a time segment with length no less than l. To compute the ( l , δ)-maximal bursting core, we first develop a novel dynamic programming algorithm that can reduce time complexity of calculating the segment density from O (| T |) 2 to O (| T |). Then, we propose an efficient updating algorithm which can update the segment density in O ( l ) time. In addition, we develop an efficient algorithm to enumerate all ( l , δ)-maximal bursting cores that are not dominated by the others in terms of l and δ. The results of extensive experiments on 9 real-life datasets demonstrate the effectiveness, efficiency and scalability of our algorithms.

As a variant task of time-series segmentation, trajectory segmentation is a key task in the applications of transportation pattern recognition and traffic analysis. However, segmenting trajectory is faced with challenges of implicit patterns and sparse results. Although deep neural networks have tremendous advantages in terms of high-level feature learning performance, deploying as a blackbox seriously limits the real-world applications. Providing explainable segmentations has significance for result evaluation and decision making. Thus, in this article, we address trajectory segmentation by proposing a Bayesian Encoder-Decoder Network (BED-Net) to provide accurate detection with explainability and references for the following active-learning procedures. BED-Net consists of a segmentation module based on Monte Carlo dropout and an explanation module based on uncertainty learning that provides results evaluation and visualization. Experimental results on both benchmark and real-world datasets indicate that BED-Net outperforms the rival methods and offers excellent explainability in the applications of trajectory segmentation.

Real-life graph datasets extracted from the Web are inevitably full of incompleteness, conflicts, and redundancies, so graph data cleaning shows its necessity. Although rules like data dependencies have been widely studied in relational data repairing, very few works exist to repair graph data. In this article, we introduce a repairing semantics for graphs, calledGraph-Repairing Rules(${\sf GRR}$s). This semantics can capture the incompleteness, conflicts, and redundancies in graphs and indicate how to correct these errors. However, this graph repairing semantics can only repair the graphs strictly isomorphic to the rule patterns, which decreases the utility of the rules. To overcome this shortcoming, we further propose a flexible rule-based graph repairing semantics (called$\delta$-GRR). We study three fundamental problems associated with both${\sf GRR}$s and$\delta$-GRRs, consistency, implication, and termination, which show whether a given set of rules make sense. Repairing the graph data using${\sf GRR}$s or$\delta$-GRRs involves a problem of finding isomorphic subgraphs of the graph data, which is NP-complete. To efficiently circumvent the complex calculation of subgraph isomorphism, we design a decomposition-and-join strategy to solve this problem. Extensive experiments on real datasets show that our two graph repairing semantics and corresponding repairing algorithms can effectively and efficiently repair real-life graph data.

Degeneracy is an important concept to measure the sparsity of a graph which has been widely used in many network analysis applications. Many network analysis algorithms, such as clique enumeration and truss decomposition, perform very well in graphs having small degeneracies. In this paper, we propose an I/O-efficient algorithm to compute the degeneracy of the massive graph that cannot be fully kept in the main memory. The proposed algorithm only uses$O(n)$memory, where$n$denotes the number of nodes of the graph. We also develop an I/O-efficient algorithm to incrementally maintain the degeneracy on dynamic graphs. Extensive experiments show that our algorithms significantly outperform the state-of-the-art degeneracy computation algorithms in terms of both running time and I/O costs. The results also demonstrate high scalability of the proposed algorithms. For example, in a real-world web graph with 930 million nodes and 13.3 billion edges, the proposed algorithm takes only 633 seconds and uses less than 4.5GB memory to compute the degeneracy.

Multimodal path queries over transportation networks are receiving increasing attention due to their widespread applications. A multimodal path query consists of finding multimodal journeys from source to destination in transportation networks, including unrestricted walking, driving, cycling, and schedule-based public transportation. Transportation networks are generally continent-sized. This characteristic highlights the need for parallel computing to accelerate multimodal path queries. Meanwhile, transportation networks are often fragmented and distributively stored on different machines. This situation calls for exploiting parallel computing power for these distributed systems. Therefore, in this paper, we studydistributed multimodal path (DMP) queriesover large transportation networks. We develop algorithms to explore parallel computation. When evaluating a DMP query$Q$on a distributed multimodal graph$Gmult$, we show that the algorithms possess the following performance guarantees, irrespective of how$Gmult$is fragmented and distributed: (1) each machine is visited only once; (2) the total network traffic is determined by the size of$Q$and the fragmentation of$Gmult$; (3) the response time is decided by the largest fragment of$Gmult$; and (4) the algorithm is parallel scalable. Using real-life and synthetic data, we experimentally verify that the algorithms are scalable on large graphs.

Personalized location prediction is key to many mobile applications and services. In this paper, motivated by both statistical and visualized preliminary analysis on three real datasets, we observe a strong spatiotemporal correlation for user trajectories among the visited area-of-interests (AoIs) and different time periods on both weekly and daily basis, which directly motivates our time-aware location prediction model design called “$t$t-LocPred”. It models the spatial correlations among AoIs by coarse-grained convolutional processing of the user trajectories in AoIs of different time periods (“ConvAoI”); and predicts his/her fine-grained next visited PoI using a novel memory-augmented attentive LSTM model (“mem-attLSTM”) to capture long-term behavior patterns. Experimental results show that$t$t-LocPred outperforms 8 baselines. We also show the impact of hyperparameters and the benefits ConvAoI can bring to these baselines.

Periodicity is a frequently happening phenomenon for social interactions in temporal networks. Mining periodic communities are essential to understanding periodic group behaviors in temporal networks. Unfortunately, most previous studies for community mining in temporal networks ignore the periodic patterns of communities. In this paper, we study the problem of seeking periodic communities in a temporal network, where each edge is associated with a set of timestamps. We propose novel models, including$\sigma$-periodic$k$-core and$\sigma$-periodic$k$-clique, that represent periodic communities in temporal networks. Specifically, a$\sigma$-periodic$k$-core (or$\sigma$-periodic$k$-clique) is a$k$-core (or clique with size larger than$k$) that appears at least$\sigma$times periodically in the temporal graph. The problem of searching periodic core is efficient but the resulting communities may be not enough cohesive; the problem of enumerating all periodic cliques is not efficient (NP-hard) but the resulting communities are very cohesive. To compute all of them efficiently, we first develop two effective graph reduction techniques to significantly prune the temporal graph. Then, we transform the temporal graph into a static graph and prove that mining the periodic communities in the temporal graph equals mining communities in the transformed graph. Subsequently, we propose a decomposition algorithm to search maximal$\sigma$-periodic$k$-core, a Bron-Kerbosch style algorithm to enumerate all maximal$\sigma$-periodic$k$-cliques, and a branch-and-bound style algorithm to find the maximum$\sigma$-periodic clique. The results of extensive experiments on five real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

Core decomposition is a fundamental operator in network analysis. In this paper, we study a problem of computing distance-generalized core decomposition on a network. A distance-generalized core, also termed (k, h)-core, is a maximal subgraph in which every vertex has at least k other vertices at distance no larger than h. The state-of-the-art algorithm for solving this problem is based on a peeling technique which iteratively removes the vertex (denoted by v) from the graph that has the smallest h-hop degree. The h-hop degree of a vertex v denotes the number of other vertices that are reachable from v within h hops. Such a peeling algorithm, however, needs to frequently recompute the h-hop degrees of v's neighbors after deleting v, which is typically very costly for a large h. To overcome this limitation, we propose an efficient peeling algorithm based on a novel h-hop degree updating technique. Instead of recomputing the h-hop degrees, our algorithm can dynamically maintain the h-hop degrees for all vertices via exploring a very small subgraph, after peeling a vertex. We show that such an h-hop degree updating procedure can be efficiently implemented by an elegant bitmap technique. In addition, we also propose a sampling-based algorithm and a parallelization technique to further improve the efficiency. Finally, we conduct extensive experiments on 12 real-world graphs to evaluate our algorithms. The results show that, when h≥3, our exact and sampling-based algorithms can achieve up to 10x and 100x speedup over the state-of-the-art algorithm, respectively.

Route planning problem has been well studied in static road networks, since it has wide applications in transportation networks. However, recently there have been more actual requirements that current path planning algorithms cannot solve, such as food delivery, ride-sharing and crowdsourced parcel delivery. These requirements are in a dynamic scenario, but the existing algorithms are offline. These requirements need to find the least total travel time path from the source through the nodes that appear dynamically over time to the destination, which referred to as the online route planning. On the other hand, the costs of edges in road networks always change over time, since real road networks are dynamic. Such road networks can be modelled as time-dependent road networks. Therefore, in this paper, we study the online route planning over time-dependent road networks (ORPTD). We formally proof that the ORPTD problem is NP-complete and its competitive ratio cannot be guaranteed. To attack the hard problem, we first propose two efficient heuristic algorithms. To adapt to large-scale time-dependent road networks, we further speed up the two heuristic algorithms by incorporating indexing techniques into them. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real datasets.

Given a location-based social network, how to find the communities that are highly relevant to query users and have top overall scores in multiple attributes according to user preferences? Typically, in the face of such a problem setting, we can model the network as a multi-attributed road-social network, in which each user is linked with location information and d (≥1) numerical attributes. In practice, user preferences (i.e., weights) are usually inherently uncertain and can only be estimated with bounded accuracy, because a human user is not able to designate exact values with absolute precision. Inspired by this, we introduce a normative community model suitable for multi-criteria decision making, called multi-attributed community (MAC), based on the concepts of k-core and a novel dominance relationship specific to preferences. Given uncertain user preferences, namely, an approximate representation of weights, the MAC search reports the exact communities for each of the possible weight settings. We devise an elegant index structure to maintain the dominance relationships, based on which two algorithms are developed to efficiently compute the top-j MACs. The efficiency and scalability of our algorithms and the effectiveness of MAC model are demonstrated by extensive experiments on both real-world and synthetic road-social networks.

Understanding the movement patterns of humans and vehicles traveling in a city is important for many applications like emergency evacuation and rescue, as well as city planning and management. In this paper, we aim to predict citywide crowd flows within a period in the future to give aid to urban management, through modeling spatiotemporal patterns of recent crowd flows. We present a novel deep model for this task, called "AttConvLSTM", which leverages a convolutional LSTM (ConvLSTM), Convolutional Neural Networks (CNNs) along with an attention mechanism, where ConvLSTM keeps spatial information as intact as possible during sequential analysis, and the attention mechanism can focus important crowd flow variations which cannot be identified by the recurrent module. We conducted extensive experiments for performance evaluation using three large datasets, including Beijing Taxi dataset, Rome Taxi dataset, and Chengdu Didi chauffeuring trace. The experimental results show that AttConvLSTM significantly outperforms several widely-used baselines in terms of Root Mean Squared Error (RMSE), and Mean Average Percentage Error (MAPE), indicating that our approach can deal with crowd flows with different dynamics in both spatial and temporal domains, and make valid predictions several steps ahead.

Constrained route planning (CRP) on transportation networks has been extensively studied because of its broad applications, such as route recommendation. However, the existing works on CRP neglect the time-dependent and multi-modal properties of transportation networks. This paper proposes an approach for CRP over multi-modal time-dependent networks. Specifically, we design two novel constrained route planning algorithms, function-dependent routing and labeling-index-based routing. While function-dependent routing generates an accurate route to CRP by traversing the network, labeling-index-based one ensures the fast response with the support of an efficient index and the compression scheme of networks. In order to demonstrate the efficiency and effectiveness of our proposed algorithms, experiments are performed over real datasets.

Fast and efficient access to environmental and life data is key to the successful disaster response. Vehicular crowdsourcing (VC) by a group of unmanned vehicles (UVs) like drones and unmanned ground vehicles to collect these data from Point-of-Interests (PoIs) e.g., possible survivor spots and fire site, provides an efficient way to assist disaster rescue. In this paper, we explicitly consider to navigate a group of UVs in a 3-dimensional (3D) disaster workzone to maximize the amount of collected data, geographical fairness, energy efficiency, while minimizing data dropout due to limited transmission rate. We propose DRL-DisasterVC(3D), a distributed deep reinforcement learning framework, with a repetitive experience replay (RER) to improve learning efficiency, and a clipped target network to increase learning stability. We also use a 3D convolutional neural network (3D CNN) with multi-head-relational attention (MHRA) for spatial modeling, and add auxiliary pixel control (PC) for spatial exploration. We designed a novel disaster response simulator, called "DisasterSim", and conduct extensive experiments to show that DRL-DisasterVC(3D) outperforms all five baselines in terms of energy efficiency when varying the numbers of UVs, PoIs and SNR threshold.

Many real-life applications require processing graph data across heterogeneous sources. In this paper, we define the graph federation that indicates that the graph data sources are temporarily federated and offer their data for users. Next, we propose a new framework FedGraph to efficiently and effectively perform subgraph matching, which is a crucial application in graph federation. FedGraph consists of three phases, including query decomposition, distributed matching, and distributed joining. We also develop new efficient approximation algorithms and apply them in each phase to attack the NP-hard problem. The evaluations are conducted in a real test bed using both real-life and synthetic graph datasets. FedGraph outperforms the state-of-the-art methods, reducing the execution time and communication cost by 37.3 × and 61.8 ×, respectively.

In recent years, online Event Based Social Network (EBSN) platforms have become increasingly popular. One typical task of EBSN platforms is to help users make suitable and personalized plans for participating in different interesting social events. Existing techniques either ignore the minimum-participant requirement constraint for each event, which is crucially needed for some events to be held successfully, or assume that events would not change once announced. In this paper, we address the above inadequacies of existing EBSN techniques. We formally define the Global Event Planning with Constraints (GEPC) problem, and its incremental variant. Since these problems are NP-hard, and provide approximate solutions. Finally, we verify the effectiveness and efficiency of our proposed algorithms through extensive experiments over real and synthetic datasets.

The group nearest neighbor (GNN) search on a road network$G_r$, i.e., finding the spatial objects as activity assembly points with the smallest sum of distances to query users on$G_r$, has been extensively studied; however, previous works neglected the fact that social relationships among query users, which ensure the maximally favorable atmosphere in the activity, can play an important role in GNN queries. Meanwhile, the ratings of spatial objects can also be used as recommended guidelines. Many real-world applications, such as location-based social networking services, require such queries. In this paper, we study two new problems: (1) a GNN search on a road network that incorporates cohesive social relationships (CGNN) and (2) a CGNN query under multi-criteria (MCGNN). Specifically, both the query users of highest closeness and the corresponding top-$j$objects are retrieved. To address critical challenges on the effectiveness of results and the efficiency of computation over large road-social networks: (1) for CGNN, we propose a filtering-and-verification framework. During filtering, we prune substantial unpromising users and objects using social and geospatial constraints. During verification, we obtain the object candidates, among which the top$j$are selected, with respect to the qualified users; (2) for MCGNN, we propose threshold-based selection and expansion strategies, where different strict boundaries are proposed to ensure that correct top-$j$objects are found early. Moreover, we further optimize search strategies to improve query performance. Finally, experimental results on real social and road networks significantly demonstrate the efficiency and efficacy of our solutions.

The core of many large-scale machine learning (ML) applications, such as neural networks (NN), support vector machine (SVM), and convolutional neural network (CNN), is the training algorithm that iteratively updates model parameters by processing massive datasets. From a plethora of studies aiming at accelerating ML, being data parallelization and parameter server, the prevalent assumption is that all data points are equivalently relevant to model parameter updating. In this article, we challenge this assumption by proposing a criterion to measure a data point's effect on model parameter updating, and experimentally demonstrate that the majority of data points are non-critical in the training process. We develop a slim learning framework, termed SlimML, which trains the ML models only on the critical data and thus significantly improves training performance. To such an end, SlimML efficiently leverages a small number of aggregated data points per iteration to approximate the criticalness of original input data instances. The proposed approach can be used by changing a few lines of code in a standard stochastic gradient descent (SGD) procedure, and we demonstrate experimentally, on NN regression, SVM classification, and CNN training, that for large datasets, it accelerates model training process by an average of 3.61 times while only incurring accuracy losses of 0.37 percent.

Mining cohesive subgraphs from a network is a fundamental problem in network analysis. Most existing cohesive subgraph models are mainly tailored to unsigned networks. In this paper, we study the problem of seeking cohesive subgraphs in a signed network, in which each edge can be positive or negative, denoting friendship or conflict, respectively. We propose a novel model, called maximal (a, k)-clique, that represents a cohesive subgraph in signed networks. Specifically, a maximal (α, k)-clique is a clique in which every node has at most k negative neighbors and at least ⌈ak⌉ positive neighbors (α ≥ 1). We show that the problem of enumerating all maximal (a, k)-cliques in a signed network is NP-hard. To enumerate all maximal (a, k)-cliques efficiently, we first develop an elegant signed network reduction technique to significantly prune the signed network. Then, we present an efficient branch and bound enumeration algorithm with several carefully-designed pruning rules to enumerate all maximal (a, k)-cliques in the reduced signed network. In addition, we also propose an efficient algorithm with three novel upper-bounding techniques to find the maximum (a, k)-clique in a signed network. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

In-memory databases (IMDBs) are gaining increasing popularity in big data applications, where clients commit updates intensively. Specifically, it is necessary for IMDBs to have efficient snapshot performance to support certain special applications (e.g., consistent checkpoint, HTAP). Formally, the in-memory consistent snapshot problem refers to taking an in-memory consistent time-in-point snapshot with the constraints that 1) clients can read the latest data items and 2) any data item in the snapshot should not be overwritten. Various snapshot algorithms have been proposed in academia to trade off throughput and latency, but industrial IMDBs such as Redis adhere to the simple fork algorithm. To understand this phenomenon, we conduct comprehensive performance evaluations on mainstream snapshot algorithms. Surprisingly, we observe that the simple fork algorithm indeed outperforms the state-of-the-arts in update-intensive workload scenarios. On this basis, we identify the drawbacks of existing research and propose two lightweight improvements. Extensive evaluations on synthetic data and Redis show that our lightweight improvements yield better performance than fork, the current industrial standard, and the representative snapshot algorithms from academia. Finally, we have opensourced the implementation of all the above snapshot algorithms so that practitioners are able to benchmark the performance of each algorithm and select proper methods for different application scenarios.

A distance search in Hamming space finds binary vectors whose Hamming distances are no more than a threshold from a query vector. It is a fundamental problem in many applications, such as image retrieval, near-duplicate Web page detection, and scientific databases. State-of-the-art approaches to Hamming distance search are mainly based on the pigeonhole principle to generate a set of candidates and then verify them. We observe that the constraint by the pigeonhole principle is not always tight and may bring about unnecessary candidates. We also observe that the distribution in real data is often skewed, but most existing solutions adopt a simple equi-width partitioning and allocate the same threshold to all the parts, hence failing to exploit the data skewness to optimize query processing. In this paper, we propose a new form of the pigeonhole principle which allows variable partitioning and threshold allocation. Based on the new principle, we develop a tight constraint of candidates and devise cost-aware methods for partitioning and threshold allocation to optimize query processing. In addition, we extend our methods to answer Hamming distance join queries. We also discuss the application of the pigeonhole principle in set similarity search, a problem that can be converted to Hamming distance search equivalently. Our evaluation on datasets with various data distributions shows the robustness of our solution and its superior query processing performance to the state-of-the-art methods.

With the development of mobile communication techniques, spatial crowdsourcing has become popular recently. A typical topic of spatial crowdsourcing is task assignment, which assigns crowd workers to users' requests in real time and maximizes the total revenue. However, it is common that the available crowd workers over a platform are too far away to serve the requests, so some user requests may be rejected or responded at high money cost after long waiting. Fortunately, the neighbors of a platform usually have available resources for the same services. Collaboratively conducting the task allocation among different platforms can greatly improve the quality of services, but have not been investigated yet. In this paper, we propose a Cross Online Matching (COM), which enables a platform to "borrow" unoccupied crowd workers from other platforms for completing the user requests. We propose two algorithms, deterministic cross online matching (DemCOM) and randomized cross online matching (RamCom) for COM. DemCOM focuses on the largest obtained revenue in a greedy manner, while RamCom considers the trade-off between the obtained revenue and the probability of request being accepted by the borrowed workers. Extensive experimental results verify the effectiveness and efficiency of our algorithms.

With the boom in cloud computing, data outsourcing in location-based services is proliferating and has attracted increasing interest from research communities and commercial applications. Nevertheless, since the cloud server is probably both untrusted and malicious, concerns of data security and result integrity have become on the rise sharply. However, there exist little work that can commendably assure the data security and result integrity using a unified way. In this paper, we study the problem of secure and verifiable k nearest neighbor query (SVkNN). To support SVkNN, we first propose a novel unified structure, called verifiable and secure index (VSI). Based on this, we devise a series of secure protocols to facilitate query processing and develop a compact verification strategy. Given an SVkNN query, our proposed solution can not merely answer the query efficiently while can guarantee: 1) preserving the privacy of data, query, result and access patterns; 2) authenticating the correctness and completeness of the results without leaking the confidentiality. Finally, the formal security analysis and complexity analysis are theoretically proven and the performance and feasibility of our proposed approaches are empirically evaluated and demonstrated.

Spatial crowdsourcing (SC) utilizes the potential of a crowd to accomplish certain location based tasks. Although worker scheduling has been well studied recently, most existing works only focus on the static deployment of workers but ignore their temporal movement continuity. In this paper, we explicitly consider the use of unmanned vehicular workers, e.g., drones and driverless cars, which are more controllable and can be deployed in remote or dangerous areas to carry on long-term and hash tasks as a vehicular crowdsourcing (VC) campaign. We propose a novel deep reinforcement learning (DRL) approach for curiosity-driven energy-efficient worker scheduling, called "DRL-CEWS", to achieve an optimal trade-off between maximizing the collected amount of data and coverage fairness, and minimizing the overall energy consumption of workers. Specifically, we first utilize a chief-employee distributed computational architecture to stabilize and facilitate the training process. Then, we propose a spatial curiosity model with a sparse reward mechanism to help derive the optimal policy in large crowdsensing space with unevenly distributed data. Extensive simulation results show that DRL-CEWS outperforms the state-of-the-art methods and baselines, and we also visualize the benefits curiosity model brings and show the impact of two hyperparameters.

The structural diversity of an edge, which is measured by the number of connected components of the edge's ego-network, has recently been recognized as a key metric for analyzing social influence and information diffusion in social networks. Given this, an important problem in social network analysis is to identify top-k edges that have the highest structural diversities. In this work, we for the first time perform a systematical study for the top-k edge structural diversity search problem on large graphs. Specifically, we first develop a new online search framework with two basic upper-bounding rules to efficiently solve this problem. Then, we propose a new index structure using near-linear space to process the top-k edge structural diversity search in near-optimal time. To create such an index structure, we devise an efficient algorithm based on an interesting connection between our problem and the 4-clique enumeration problem. In addition, we also propose efficient index maintenance techniques to handle dynamic graphs. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

Graph queries have emerged as one of the fundamental techniques to support modern search services, such as PageRank web search, social networking search and knowledge graph search. As such graphs are maintained globally and very huge (e.g., billions of nodes), we need to efficiently process graph queries across multiple geographically distributed datacenters, running geo-distributed graph queries. Existing graph computing frameworks may not work well for geographically distributed datacenters, because they implement a Bulk Synchronous Parallel model that requires excessive inter-datacenter transfers, thereby introducing extremely large latency for query processing. In this paper, we propose GeoGraph --a universal framework to support efficient geo-distributed graph query processing based on clustering datacenters and meta-graph, while reducing the inter-datacenter communication. Our new framework can be applied to many types of graph algorithms without any modification. The framework is developed on the top of Apache Giraph. The experiments were conducted by applying four important graph queries, i.e., shortest path, graph keyword search, subgraph isomorphism and PageRank. The evaluation results show that our proposed framework can achieve up to 82% faster convergence, 42% lower WAN bandwidth usage, and 45% less total monetary cost for the four graph queries, with input graphs stored across ten geo-distributed datacenters.

The group nearest neighbor (GNN) search on a road network Gr, i.e., finding the spatial objects as activity assembly points with the smallest sum of distances to query users on Gr, has been extensively studied; however, previous works have neglected the fact that social relationships among query users, which ensure the maximally favorable atmosphere in the activity, can play an important role in GNN queries. Many real-world applications, such as location-based social networking services, require such queries. In this paper, we study a new problem: a GNN search on a road network that incorporates cohesive social relationships (CGNN). Specifically, both the query users of highest closeness and the corresponding top-j objects are retrieved. One critical challenge is to speed up the computation of CGNN queries over large social and road networks. To address this challenge, we propose a filtering-and-verification framework for efficient query processing. During filtering, we prune substantial unpromising users and objects using social and geographically spatial constraints. During verification, we obtain the object candidates, among which the top j are selected, with respect to the qualified users. Moreover, we further optimize search strategies to improve query performance. Finally, experimental results on real social and road networks significantly demonstrate the efficiency and efficacy of our solutions.

Enumerating maximal cliques from an uncertain graph is a fundamental problem in uncertain graph analysis. Given an uncertain graph G, a set of nodes C in G is a maximal (k, τ)-clique if (1) |C|>k and C is a clique with probability at least τ, and (2) C is a maximal node set meeting (1). The state-of-the-art algorithm for enumerating all maximal (k, τ)-cliques is very costly when handling large uncertain graphs, as its time complexity is proportional to 2^n where n is the number of nodes in the uncertain graph. To overcome this issue, we propose two new core-based pruning algorithms to reduce the uncertain graph size without missing any maximal (k, τ)-clique. We also develop a novel cut-based optimization technique to further improve the pruning performance of the core-based pruning algorithms. Based on these pruning techniques, we propose an improved algorithm to enumerate all maximal (k, τ)-cliques, and a new algorithm with several novel upper-bounding techniques to compute one of maximum (k, τ)-cliques from the pruned uncertain graph. The results of extensive experiments on six real-world datasets demonstrate the efficiency and effectiveness of the proposed algorithms.

Periodicity is a frequently happening phenomenon for social interactions in temporal networks. Mining periodic communities are essential to understanding periodic group behaviors in temporal networks. Unfortunately, most previous studies for community mining in temporal networks ignore the periodic patterns of communities. In this paper, we study a problem of seeking periodic communities in a temporal network, where each edge is associated with a set of timestamps. We propose a novel model, called maximal σ-periodic k-clique, that represents a periodic community in temporal networks. Specifically, a maximal σ-periodic k-clique is a clique with size larger than k that appears at least σ times periodically in the temporal graph. We show that the problem of enumerating all those periodic cliques is NP-hard. To compute all of them efficiently, we first develop two effective graph reduction techniques to significantly prune the temporal graph. Then, we present an efficient enumeration algorithm to enumerate all maximal σ-periodic k-cliques in the reduced graph. The results of extensive experiments on five real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

Weight-constrained route planning (WRP) over static graphs has been extensively studied due to its wide application to transportation networks. However, real transportation networks often evolve over time and are thus modeled as time-dependent graphs. In this paper, we study the WRP problem over a large time-dependent graph by incorporating continuous time and weight functions into it. Most existing works regarding route planning over time-dependent graphs are based on the first-in-first-out (FIFO) property. Unfortunately, the FIFO property does not hold for our problem. To solve the problem, we propose two novel route planning algorithms, namely, a baseline algorithm and an advanced algorithm. Specifically, the advanced algorithm is even more efficient than the baseline algorithm, as the advanced algorithm incorporates a fast traversal scheme and tight bounds of time functions to terminate the traversal as early as possible. We confirm the effectiveness and efficiency of our algorithms by extensive experiments on real datasets.

The popularity of mobile Internet techniques and Online-To-Offline(O2O) business models has led to the emergence of various spatial crowdsourcing (SC) platforms in our daily life. A core issue of SC platforms is to assign tasks to suitable crowd workers. Existing approaches usually focus on the matching of two types of objects,tasks and workers, and let workers to travel to the location of usersto provide services, which is a 2D matching problem. However, recent services provided by some new platforms, such as person-alized haircut service1and station ride-sharing, need users andworkers travel together to a third workplace to complete the service, which is indeed a 3D matching problem. Approaches in the existingstudies either cannot solve such 3D matching problem, or lack aassignment plan satisfying both users' and workers' preference inreal applications. Thus, in this paper, we propose a 3-Dimensional Stable Spatial Matching(3D-SSM) for the 3D matching problem innew SC services. We prove that the 3D-SSM problem is NP-hard, and propose two baseline algorithms and two efficient approximatealgorithms with bounded approximate ratios to solve it. Finally, weconduct extensive experiment studies which verify the efficiencyand effectiveness of the proposed algorithms on real and synthetic datasets.

Abstract A time-dependent graph is, informally speaking, a graph structure dynamically changes with time. In such graphs, the weights associated with edges dynamically change over time, that is, the edges in such graphs are activated by sequences of time-dependent elements. Many real-life scenarios can be better modeled by time-dependent graphs, such as bioinformatics networks, transportation networks, and social networks. In particular, the time-dependent graph is a very broad concept, which is reflected in the related research with many names, including temporal graphs, evolving graphs, time-varying graphs, historical graphs, and so on. Though static graphs have been extensively studied, for their time-dependent generalizations, we are still far from a complete and mature theory of models and algorithms. In this paper, we discuss the definition and topological structure of time-dependent graphs, as well as models for their relationship to dynamic systems. In addition, we review some classic problems on time-dependent graphs, e.g., route planning, social analysis, and subgraph problem (including matching and mining). We also introduce existing time-dependent systems and summarize their advantages and limitations. We try to keep the descriptions consistent as much as possible and we hope the survey can help practitioners to understand existing time-dependent techniques.

The constrained shortest path (CSP) query over static graphs has been extensively studied, since it has wide applications in transportation networks, telecommunication networks and etc. Such networks are dynamic and evolve over time, being modeled as time-dependent graphs. Therefore, in this paper, we study the CSP query over a large time-dependent graph. Specifically, we study the point CSP (PCSP) query and interval CSP (ICSP) query. We formally prove that it is NP-complete to process a PCSP query and at least EXPSPACE to answer an ICSP query. We propose approximate sequential algorithms to answer the PCSP and ICSP queries efficiently. We also develop parallel algorithms for the queries that guarantee to scale with big time-dependent graphs. Using real-life graphs, we experimentally verify the efficiency and scalability of our algorithms.

Structural clustering is a fundamental graph mining operator which is not only able to find densely-connected clusters, but it can also identify hub vertices and outliers in the graph. Previous structural clustering algorithms are tailored to deterministic graphs. Many real-world graphs, however, are not deterministic, but are probabilistic in nature because the existence of the edge is often inferred using a variety of statistical approaches. In this paper, we formulate the problem of structural clustering on probabilistic graphs, with the aim of finding reliable clusters in a given probabilistic graph. Unlike the traditional structural clustering problem, our problem relies mainly on a novel concept called reliable structural similarity which measures the probability of the similarity between two vertices in the probabilistic graph. We develop a dynamic programming algorithm with several powerful pruning strategies to efficiently compute the reliable structural similarities. With the reliable structural similarities, we adapt an existing solution framework to calculate the structural clustering on probabilistic graphs. Comprehensive experiments on five real-life datasets demonstrate the effectiveness and efficiency of the proposed approaches.

Continuous top-k query over streaming data is a fundamental problem in database. In this paper, we focus on sliding window scenario, where a continuous top-k query returns the top-k objects within each query window on the data stream. Existing algorithms support this type of queries via incrementally maintaining a subset of objects in the window and try to retrieve the answer from this subset as much as possible whenever the window slides. However, since all the existing algorithms are sensitive to query parameters and data distribution, they all suffer from expensive incremental maintenance cost. In this paper, we propose a self-adaptive partition framework to support continuous top-k query. It partitions the window into subwindows and only maintains a small number of candidates with highest scores in each sub-window. Based on this framework, we have developed several partition algorithms to cater for different object distributions and query parameters. It is the first algorithm that achieves logarithmic complexity w.r.t. k for incremental maintaining the candidate set even in the worst case.

Real-life graph datasets extracted from Web are inevitably full of incompleteness, conflicts, and redundancies, so graph data cleaning shows its necessity. One of the main issues is to automatically repair the graph with some repairing rules. Although rules like data dependencies have been widely studied in relational data repairing, very few works exist to repair the graph data. In this paper, we introduce an automatic repairing semantic for graphs, calledGraph-Repairing Rules(GRRs). This semantic can capture the incompleteness, conflicts, and redundancies in the graphs and indicate how to correct these errors. We study three fundamental problems associated with GRRs, implication, consistency and termination, which show whether a given set of GRRs make sense. Repairing the graph data using GRRs involves a problem of finding isomorphic subgraphs of the graph data for each GRR, which is NP-complete. To efficiently circumvent the complex calculation of subgraph isomorphism, we design a decomposition-and-join strategy to solve this problem. Extensive experiments on real datasets show that our GRR semantic and corresponding repairing algorithms can effectively and efficiently repair real-life graph data.

Mining cohesive subgraphs from a network is a fundamental problem in network analysis. Most existing cohesive subgraph models are mainly tailored to unsigned networks. In this paper, we study the problem of seeking cohesive subgraphs in a signed network, in which each edge can be positive or negative, denoting friendship or conflict respectively. We propose a novel model, called maximal (α, k)-clique, that represents a cohesive subgraph in signed networks. Specifically, a maximal (α, k)-clique is a clique in which every node has at most. negative neighbors and at least [αk] positive neighbors (α ≥ 1). We show that the problem of enumerating all maximal (α, k)- cliques in a signed network is NP-hard. To enumerate all maximal (α,k)-cliques efficiently, we first develop an elegant signed network reduction technique to significantly prune the signed network. Then, we present an efficient branch and bound enumeration algorithm with several carefully-designed pruning rules to enumerate all maximal (α,k)-cliques in the reduced signed network. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

In-memory databases (IMDBs) are gaining increasing popularity in big data applications, where clients commit updates intensively. Consistent snapshot is a key step in backup and recovery of IMDBs, thus an important factor for system performance of IMDBs. Formally, the in-memory consistent snapshot problem refers to taking an in-memory consistent time-in-point snapshot with the constraints that 1) clients can read the latest data items, and 2) any data item in the snapshot should not be overwritten. Various snapshot algorithms have been proposed in the academia to trade off throughput and latency, yet industrial IMDBs such as Redis still stick to the simple fork algorithm. As an understanding of this phenomenon, we conduct comprehensive performance evaluations on mainstream snapshot algorithms. Surprisingly, we observe that the simple fork algorithm indeed outperforms the state-of-the-arts in update-intensive workload scenarios. On this basis, we identify the drawbacks of existing research and propose two lightweight improvements. Extensive evaluations on synthetic data and Redis show that our lightweight improvements yield better performance than fork, the current industrial standard, and the representative snapshot algorithms from the academia. Finally, we have opensourced the implementation of all the above snapshot algorithms to facilitate practitioners to benchmark the performance of each algorithm and select proper methods for different application scenarios.

In recent years, online Event Based Social Network (EBSN) platforms have become increasingly popular. One typical task of EBSN platforms is to help users make suitable and personalized plans for participating in different interesting social events. Existing techniques either ignore the minimum-participant requirement constraint for each event, which is crucially needed for some events to be held successfully, or assume that events would not change once announced. In this paper, we address the above inadequacies of existing EBSN techniques. We formally define the Global Event Planning with Constraints (GEPC) problem, and its incremental variant. We prove that both are NP-hard, and provide approximate solutions. Finally, we verify the effectiveness and efficiency of our proposed algorithms through extensive experiments over real and synthetic datasets.

Graph keyword search has drawn many research interests, since graph models can generally represent both structured and unstructured databases and keyword searches can extract valuable information for users without the knowledge of the underlying schema and query language. In practice, data graphs can be extremely large, e.g., a Web-scale graph containing billions of vertices. The state-of-the-art approaches employ centralized algorithms to process graph keyword searches, and thus they are infeasible for such large graphs, due to the limited computational power and storage space of a centralized server. To address this problem, we investigate keyword search for Web-scale graphs deployed in a distributed environment. We first give a naive search algorithm to answer the query efficiently. However, the naive search algorithm uses a flooding search strategy that incurs large time and network overhead. To remedy this shortcoming, we then propose a signature-based search algorithm. Specifically, we design a vertex signature that encodes the shortest-path distance from a vertex to any given keyword in the graph. As a result, we can find query answers by exploring fewer paths, so that the time and communication costs are low. Moreover, we reorganize the graph data in the cluster after its initial random partitioning so that the signature-based techniques are more effective. Finally, our experimental results demonstrate the feasibility of our proposed approach in performing keyword searches over Web-scale graph data.

Continuous top-k query over streaming data is a fundamental problem in database. In this paper, we focus on the sliding window scenario, where a continuous top-k query returns the top-k objects within each query window on the data stream. Existing algorithms support this type of queries via incrementally maintaining a subset of objects in the window and try to retrieve the answer from this subset as much as possible whenever the window slides. However, since all the existing algorithms are sensitive to query parameters and data distribution, they all suffer from expensive incremental maintenance cost. In this paper, we propose a self-adaptive partition framework to support continuous top-k query. It partitions the window into sub-windows and only maintains a small number of candidates with highest scores in each sub-window. Based on this framework, we have developed several partition algorithms to cater for different object distributions and query parameters. To our best knowledge, it is the first algorithm that achieves logarithmic complexity w.r.t. k for incrementally maintaining the candidate set even in the worstcase scenarios.

A representative skylinecontains$k$skyline points that can represent its corresponding full skyline. The existing measuring criteria of$k$representative skylines are specifically designed for static data, and they cannot effectively handle streaming data. In this paper, we focus on the problem of calculating the$k$representative skyline over data streams. First, we propose a new criterion to choose$k$skyline points as the$k$representative skyline for data stream environments, termed the$k$largest dominance skyline ($k$-LDS), which is representative to the entire data set and is highly stable over the streaming data. Second, we propose an efficient exact algorithm, called Prefix-based Algorithm (PBA), to solve the$k$-LDS problem in a 2-dimensional space. The time complexity of PBA is only$\mathcal {O}((M-k)\times k)$where$M$is the size of the full skyline set. Third, the$k$-LDS problem for a$d$-dimensional ($d\ge 3$) space turns out to be very complex. Therefore, a greedy algorithm is designed to answer$k$-LDS queries. To further accelerate the calculation, we propose a$\epsilon$-greedy algorithm which can achieve an approximate factor of$\frac{1}{(1+\epsilon)}(1-\frac{1}{\sqrt{e}})$. Experimental results on both synthetic and real-world data show that our$k$-LDS significantly outperforms its competitors in data stream environments. Furthermore, we demonstrate that the proposed$\epsilon$-greedy algorithm can solve$k$-LDS efficiently and with a competitive accuracy.

Resource Description Framework (RDF) has been widely used in the Semantic Web to describe resources and their relationships. The RDF graph is one of the most commonly used representations for RDF data. However, in many real applications such as the data extraction/integration, RDF graphs integrated from different data sources may often contain uncertain and inconsistent information (e.g., uncertain labels or that violate facts/rules), due to the unreliability of data sources. In this paper, we formalize the RDF data by inconsistent probabilistic RDF graphs, which contain both inconsistencies and uncertainty. With such a probabilistic graph model, we focus on an important problem, quality-aware subgraph matching over inconsistent probabilistic RDF graphs (QA-gMatch), which retrieves subgraphs from inconsistent probabilistic RDF graphs that are isomorphic to a given query graph and with high quality scores (considering both consistency and uncertainty). In order to efficiently answer QA-gMatch queries, we provide two effective pruning methods, namely adaptive label pruning and quality score pruning, which can greatly filter out false alarms of subgraphs. We also design an effective index to facilitate our proposed pruning methods, and propose an efficient approach for processing QA-gMatch queries. Finally, we demonstrate the efficiency and effectiveness of our proposed approaches through extensive experiments.

Although$k$NN search on a road network$G_r$, i.e., finding$k$nearest objects to a query user$q$on$G_r$, has been extensively studied, existing works neglected the fact that the$q$'s social information can play an important role in this$k$NN query. Many real-world applications, such as location-based social networking services, require such a query. In this paper, we study a new problem:$k$NN search on road networks by incorporating social influence (RSkNN). Specifically, the state-of-the-artIndependent Cascade(IC) model in social network is applied to define social influence. One critical challenge of the problem is to speed up the computation of the social influence over large road and social networks. To address this challenge, we propose three efficient index-based search algorithms, i.e., road network-based (RN-based), social network-based (SN-based), and hybrid indexing algorithms. In the RN-based algorithm, we employ a filtering-and-verification framework for tackling the hard problem of computing social influence. In the SN-based algorithm, we embed social cuts into the index, so that we speed up the query. In the hybrid algorithm, we propose an index, summarizing the road and social networks, based on which we can obtain query answers efficiently. Finally, we use real road and social network data to empirically verify the efficiency and efficacy of our solutions.

Many studies have been conducted on seeking an efficient solution for pattern matching over graphs. This interest is largely due to large number of applications in many fields, which require efficient solutions for pattern matching, including protein complex prediction, social network analysis and structural pattern recognition. However, in many real applications, the graph data are often noisy, incomplete, and inaccurate. In other words, there exist many uncertain graphs. Therefore, in this paper, we study pattern matching in a large uncertain graph. Specifically, we want to retrieve all qualified matches of a query pattern in the uncertain graph. Though pattern matching over an uncertain graph is NP-hard, we employ a filtering-and verification framework to speed up the search. In the filtering phase, we propose a probabilistic matching tree, PM-tree, based on match cuts obtained by a cut selection process. Based on PM-tree, we devise a collective pruning strategy to prune a large number of unqualified matches. During the verification phase, we develop an efficient sampling algorithm to validate the remaining candidates. Extensive experimental results demonstrate the effectiveness and efficiency of the proposed algorithms.

In this demonstration, we present a system that recommends to the user the locations and activities she/he might be interested in according to history GPS trajectories and public places of interest (POI) data. Its innovation lies in the acceptable performance of recommendations in cases where no user comments on activity types are available. Such situations are more realistic considering the restrictions on mobile devices' abilities, users' privacies, or business secret. For this purpose, we first extract stay points according to uses' trajectories, and label them with the top-k common activities which have the most possibility in terms of the POI dataset. Then, by taking stay points as observations, and activities as hidden states, a Hidden Markov model is built to learn the transfer possibilities between activities and the generation probabilities between activities and stay points. Finally, with the obtained model, our system can perform two types of recommendation, i.e. the history based recommendation and the similarity based recommendation. The results of former type are those stay points from user's own history positions. While, the latter one conducts collaborative filtering by taking history based recommendation results from similar users. The demonstration shows the running effects of the implemented prototype system, in which the Microsoft GeoLife trajectories dataset and the "DianPing.com" POI dataset were loaded. The preliminary experimental results demonstrate the feasibility.

Advanced microarray technologies have enabled to simultaneously monitor the expression levels of all genes. An important problem in microarray data analysis is to discover phenotype structures. The goal is to 1) find groups of samples corresponding to different phenotypes (such as disease or normal), and 2) for each group of samples, find the representative expression pattern or signature that distinguishes this group from others. Some methods have been proposed for this issue, however, a common drawback is that the identified signatures often include a large number of genes but with low discriminative power. In this paper, we propose a $(g^\ast)$-sequence model to address this limitation, where the ordered expression values among genes are profitably utilized. Compared with the existing methods, the proposed sequence model is more robust to noise and allows to discover the signatures with more discriminative power using fewer genes. This is important for the subsequent analysis by the biologists. We prove that the problem of phenotype structure discovery is NP-complete. An efficient algorithm, FINDER, is developed, which includes three steps: 1) trivial $(g^\ast)$-sequences identifying, 2) phenotype structure discovery, and 3) refinement. Effective pruning strategies are developed to further improve the efficiency. We evaluate the performance of FINDER and the existing methods using both synthetic and real gene expression data sets. Extensive experimental results show that FINDER dramatically improves the accuracy of the phenotype structures discovered (in terms of both statistical and biological significance) and detects signatures with high discriminative power. Moreover, it is orders of magnitude faster than other alternatives.

Global skyline, as an important variant of skyline, has been widely applied in multiple criteria decision making, business planning and data mining, while there are no previous studies on the global skyline query in the subspace. Hence in this paper we propose subspace global skyline (SGS) query, which is concerned about global skyline in ad hoc subspace. Firstly, we propose an appropriate index structure RB-tree to rapidly find the initial scan positions of query. Secondly, by making analysis of basic properties of SGS, we propose a single SGS algorithm based on RB-tree (SSRB) to compute SGS points. Then an optimized single SGS algorithm based on RB-tree (OSSRB) is proposed, which can reduce the scan space and improve the computation efficiency in contrast to SSRB. Next, by sharing the scan space of different queries, a multiple SGS algorithm based on RB-tree (MSRB) is proposed to compute multiple SGS (MSGS). Finally, the performances of our proposed algorithms are verified through a large number of simulation experiments.

As a popular search mechanism, keyword search has been applied to retrieve useful data in documents, texts, graphs, and even relational databases. However, so far, there is no work on keyword search over uncertain graph data even though the uncertain graphs have been widely used in many real applications, such as modeling road networks, influential detection in social networks, and data analysis on PPI networks. Therefore, in this paper, we study the problem of top-k keyword search over uncertain graph data. Following the similar answer definition for keyword search over deterministic graphs, we consider a subtree in the uncertain graph as an answer to a keyword query if 1) it contains all the keywords; 2) it has a high score (defined by users or applications) based on keyword matching; and 3) it has low uncertainty. Keyword search over deterministic graphs is already a hard problem as stated in [1], [2], [3]. Due to the existence of uncertainty, keyword search over uncertain graphs is much harder. Therefore, to improve the search efficiency, we employ a filtering-and-verification strategy based on a probabilistic keyword index, PKIndex. For each keyword, we offline compute path-based top-k probabilities, and attach these values to PKIndex in an optimal, compressed way. In the filtering phase, we perform existence, path-based and tree-based probabilistic pruning phases, which filter out most false subtrees. In the verification, we propose a sampling algorithm to verify the candidates. Extensive experimental results demonstrate the effectiveness of the proposed algorithms.

With the exponential increment of data, compression technology becomes an important tool in the field of data management, especially in text management. An increasing pressing challenge is how to efficiently query these massive amounts of sequence data in their compressed format. In this paper we study the problem of answering subsequence-search queries on LZ78 format of texts. We propose the concept of conditional common sub strings of queries to improve query performance. We present a techniques to find minimal conditional common sub strings in compressed text and a local uncompressing technique to verify and locate positions of answers in text. Finally, the experimental results over real data demonstrate the efficiency of our algorithm.

Tag-based social image search predominately focus on using user-annotated tags to find out the results of user query. However, the performance of tag-based social image search is usually unable to satisfy the needs of users. In this paper, we propose a novel framework based on Social Relationship Graph for Social Image Search (SRGSIS), which involves two stages. In the first stage, we use heterogeneous data from multiple modalities to build a social relationship graph. Then, for the given query keywords, we execute an efficient keyword search algorithm over the social relationship graph and obtain top-k candidate results based on relevance score. We model these results as the answer trees connecting keyword nodes that match keywords in the query. In the second stage, for refining the candidate results, each image in social relationship graph is represented as a region adjacency graph by using the visual content of image. We further model these region adjacency graphs as a closure tree and compute approximate graph similarity between the candidate results and the closure tree to obtain more desirable results. Extensive experimental results demonstrate the effectiveness of the proposed approach.

The Earth Mover's Distance, or EMD for short, has been proven to be effective for content-based image retrieval. However, due to the cubic complexity of EMD computation, it remains difficult to use EMD in applications with stringent requirement for efficiency. In this paper, we present our new system, called EUDEMON, which utilizes new techniques to support fast Online Video Frame Copy Detection based on the EMD. Given a group of registered frames as queries and a set of targeted detection videos, EUDEMON is capable of identifying relevant frames from the video stream in real time. The significant improvement on efficiency mainly relies on the primal-dual theory in linear programming and well-designed B+tree filters for adaptive candidate pruning. Generally speaking, our system includes a variety of new features crucial to the deployment of EUDEMON in real applications. First, EUDEMON achieves high throughput even when a large number of queries are registered in the system. Second, EUDEMON contains self-optimization component to automatically enhance the effectiveness of the filters based on the recent content of the video stream. Finally, EUDEMON provides a user-friendly visualization interface, named EMD Flow Chart, to help the users to better understand the alarm with the perspective of the EMD.

Many studies have been conducted on seeking the efficient solution for subgraph similarity search over certain (deterministic) graphs due to its wide application in many fields, including bioinformatics, social network analysis, and Resource Description Framework (RDF) data management. All these works assume that the underlying data are certain. However, in reality, graphs are often noisy and uncertain due to various factors, such as errors in data extraction, inconsistencies in data integration, and privacy preserving purposes. Therefore, in this paper, we study subgraph similarity search on large probabilistic graph databases. Different from previous works assuming that edges in an uncertain graph are independent of each other, we study the uncertain graphs where edges' occurrences are correlated. We formally prove that subgraph similarity search over probabilistic graphs is #P-complete, thus, we employ a filter-and-verify framework to speed up the search. In the filtering phase, we develop tight lower and upper bounds of subgraph similarity probability based on a probabilistic matrix index, PMI. PMI is composed of discriminative subgraph features associated with tight lower and upper bounds of subgraph isomorphism probability . Based on PMI, we can sort out a large number of probabilistic graphs and maximize the pruning capability. During the verification phase, we develop an efficient sampling algorithm to validate the remaining candidates. The efficiency of our proposed solutions has been verified through extensive experiments.

The graph structure is a very important means to model schemaless data with complicated structures, such as protein-protein interaction networks, chemical compounds, knowledge query inferring systems, and road networks. This paper focuses on the index structure for similarity search on a set of large sparse graphs and proposes an efficient indexing mechanism by introducing the Q-Gram idea. By decomposing graphs to small grams (organized by κ-Adjacent Tree patterns) and pairing-up on those κ-Adjacent Tree patterns, the lower bound estimation of their edit distance can be calculated for candidate filtering. Furthermore, we have developed a series of techniques for inverted index construction and online query processing. By building the candidate set for the query graph before the exact edit distance calculation, the number of graphs need to proceed into exact matching can be greatly reduced. Extensive experiments on real and synthetic data sets have been conducted to show the effectiveness and efficiency of the proposed indexing mechanism.

Reverse skyline query plays an important role in many sensing applications, such as environmental monitoring, habitat monitoring, and battlefield monitoring. Due to the limited power supplies of wireless sensor nodes, the existing centralized approaches, which do not consider energy efficiency, cannot be directly applied to the distributed sensor environment. In this paper, we investigate how to process reverse skyline queries energy efficiently in wireless sensor networks. Initially, we theoretically analyzed the properties of reverse skyline query and proposed a skyband-based approach to tackle the problem of reverse skyline query answering over wireless sensor networks. Then, an energy-efficient approach is proposed to minimize the communication cost among sensor nodes of evaluating range reverse skyline query. Moreover, optimization mechanisms to improve the performance of multiple reverse skylines are also discussed. Extensive experiments on both real-world data and synthetic data have demonstrated the efficiency and effectiveness of our proposed approaches with various experimental settings.

A significant number of applications on graph require the key relations among a group of query nodes. Given a relational graph such as social network or biochemical interaction, an informative subgraph is urgent, which can best explain the relationships among a group of given query nodes. Based on Particle Swarm Optimization (PSO), a new framework of SISP (Searching the Informative Subgraph based on PSO) is proposed. SISP contains three key stages. In the initialization stage, a random spreading method is proposed, which can effectively guarantee the connectivity of the nodes in each particle; In the calculating stage of fitness, a fitness function is designed by incorporating a sign function with the goodness score; In the update stage, the intersection-based particle extension method and rule-based particle compression method are proposed. To evaluate the qualities of returned subgraphs, the appropriate calculating of goodness score is studied. Considering the importance and relevance of a node together, we present the PNR method, which makes the definition of informativeness more reliable and the returned subgraph more satisfying. At last, we present experiments on a real dataset and a synthetic dataset separately. The experimental results confirm that the proposed methods achieve increased accuracy and are efficient for any query set.

Diagnostic genes refer to the genes closely related to a specific disease phenotype, the powers of which to distinguish between different classes are often high. Most methods to discovering the powerful diagnostic genes are either singleton discriminability-based or combination discriminability-based. However, both ignore the abundant interactions among genes, which widely exist in the real world. In this paper, we tackle the problem from a new point of view and make the following contributions: (1) we propose an EWave model, which profitably exploits the ordered expressions among genes based on the defined equivalent dimension group sequences taking into account the "noise" universal in the real data, (2) we devise a novel sequence rule, namely interesting non-redundant contrast sequence rule, which is able to capture the difference between different phenotypes in a high accuracy using as few as possible genes, (3) we present an efficient algorithm called NRMINER to find such rules. Unlike the conventional column enumeration and the more recent row enumeration, it performs a novel template-driven enumeration by making use of the special characteristic of micro array data modeled by EWave. Extensive experiments conducted on various synthetic and real datasets show that: (1) NRMINER is significantly faster than the competing algorithm by up to about one order of magnitude, (2) it provides a higher accuracy using fewer genes. Many diagnostic genes discovered by NRMINER are proved biologically related to some disease.

With the increasing amount of data and the need to integrate data from multiple data sources, one of the challenging issues is to identify near-duplicate records efficiently. In this article, we focus on efficient algorithms to find a pair of records such that their similarities are no less than a given threshold. Several existing algorithms rely on the prefix filtering principle to avoid computing similarity values for all possible pairs of records. We propose new filtering techniques by exploiting the token ordering information; they are integrated into the existing methods and drastically reduce the candidate sizes and hence improve the efficiency. We have also studied the implementation of our proposed algorithm in stand-alone and RDBMS-based settings. Experimental results show our proposed algorithms can outperform previous algorithms on several real datasets.

Objects, such as a digital image, a text document or a DNA sequence are usually represented in a high dimensional feature space. A fundamental issue in (peer-to-peer) P2P systems is to support an efficient similarity search for high-dimensional data in metric spaces. Prior works suffer from some fundamental limitations, such as being not adaptive to a highly dynamic network, poor search efficiency under skewed data scenarios, large maintenance overhead and etc. In this study, we propose an efficient scheme, Dragon, to support P2P similarity search in metric spaces. Dragon achieves the efficiency through the following designs: 1) Dragon is based on our previous designed P2P network, Phoenix, which has the optimal routing efficiency in dynamic scenarios. 2) We design a locality-preserving naming algorithm and a routing tree for each peer in Phoenix to support range queries. A radius-estimated method is proposed to transform a kNN query to a range query. 3) A load-balancing algorithm is given to support strong query processing under skewed data distributions. Extensive experiments verify the superiority of Dragon over existing works.

Concept-Based Semantic Video Retrieval(CBSVR) usually uses semantic representations of videos to handle user's retrieval requests. It is obvious that the accuracy of semantic video retrieval depends on results of concept detectors, but the detection results are usually imprecise and uncertain . In this paper, we propose a multi-information fusion approach (MIF) which is dedicated to solving the problem of uncertain semantic representations of videos for improving retrieval accuracy. This approach is based on a novel two-phase framework that involves the inferring phase and the fusing phase. In the inferring phase, the most relevant concepts to the user's query are chosen by exploring both contextual correlation among concepts and temporal correlation among shots. In the fusing phase, the inferred probabilities of the related concepts are fused together with the detection results via minimization of potential function to refine the detector prediction. Experiments on the widely used TRECVID datasets demonstrate that our approach can effectively improve the accuracy of semantic concept detection.

Traditional databases manage only deterministic information, but now many applications that use databases involve uncertain data. For example, it is infeasible for a sensor database to contain only the exact value of each sensor at all points in time. The uncertainty is inherent in these systems due to measurement and sampling errors, and resource limitations. This paper aims at the query processing algorithm of twig patterns on probabilistic XML documents. The existing algorithms evaluate twig patterns in a traversal way. The main shortcoming of this way is scanning the whole probabilistic XML document to get the final results. In this paper, we first represent a probabilistic XML document in the form of probabilistic tag streams and then match them in a holistic way. Extensive experiments are conducted and show that the proposed holistic way has the higher performance than the traversal way.

Clustering is a popular technique for analyzing microarray data sets, with n genes and m experimental conditions. As explored by biologists, there is a real need to identify coregulated gene clusters, which include both positive and negative regulated gene clusters. The existing pattern-based and tendency-based clustering approaches cannot directly be applied to find such coregulated gene clusters, because they are designed for finding positive regulated gene clusters. In this paper, in order to cluster coregulated genes, we propose a coding scheme that allows us to cluster two genes into the same cluster if they have the same code, where two genes that have the same code can be either positive or negative regulated. Based on the coding scheme, we propose a new algorithm for finding maximal subspace coregulated gene clusters with new pruning techniques. A maximal subspace coregulated gene cluster clusters a set of genes on a condition sequence such that the cluster is not included in any other subspace coregulated gene clusters. We conduct extensive experimental studies. Our approach can effectively and efficiently find maximal subspace coregulated gene clusters. In addition, our approach outperforms the existing approaches for finding positive regulated gene clusters.

Similarity-based time series retrieval has been a subject of long term study due to its wide usage in many applications, such as financial data analysis, weather data forecasting, and multimedia data retrieval. Its original task was to find those time series similar to a pattern (query) time series data, where both the pattern and data time series are static. Recently, with an increasing demand on stream data management, similarity-based stream time series retrieval has raised new research issues due to its unique requirements during the stream processing, such as one-pass search and fast response. In this paper, we address the problem of matching patterns over high-speed stream time series data. We will develop a novel representation, called multi-scaled segment mean (MSM), for stream time series data, which can be incrementally computed and thus perfectly adapted to the stream characteristics. Most importantly, we propose a novel multi-step filtering mechanism over the multi-scaled representation. Analysis indicates that the mechanism can greatly prune the search space and thus offer fast response. Extensive experiments show the multi-scaled representation together with the multi-step filtering scheme can efficiently filter out false candidates and detect patterns, compared to the multiscaled wavelet.

This paper focuses on the performance improvement for long-path XML query processing. It is motivated by the fact that the existing inverted index and join algorithms are efficient for short path XML queries, but are inefficient for long path XML queries since the response time of the existing approaches is exponential to the length of paths. We propose a clustering based indexing method, called PathGuide, in this paper, which enhances the XML inverted index with the clustering technique. The element nodes are clustered based on their path patterns and the summary for such path information is kept in a suffix tree as the index of these element nodes. In addition, new operations are proposed to fully utilize PathGuide. With the assistance of PathGuide, unlike the path expansion approach used in Lore, the set of a relative location path can be found via one-step index lookup. Compared to the existing structural join method, PathGuide significantly reduces both join overhead and disk I/O cost. The extensive experimental studies are conducted and our results show that PathGuide outperforms the structural joins at least four times in most cases.

XML is emerging as a major standard for representing data on the World-Wide-Web. Recently, many XML storage models have been proposed to manage XML data. We propose several benchmarks including XMark and XMach in order to assess an XML database's abilities to deal with XML queries. We report our first set of results on benchmarking a set of XML database implementations using two XML benchmarks. In general, XML data can be managed as text files, by existing DBMSs, or by the so-called native XML engines. We implemented three XML database systems. VXMLR, and XParent were built on top of RDBMS, and XBase was implemented as a native XML engine. For each approach, variations on schema mapping and storage methods were also implemented for comparison.

With the extensive use of XML in applications over the Web, how to update XML data is becoming an important issue because the role of XML has expanded beyond traditional applications, in which XML is used as a mean for data representation and exchange on the Web. This paper presents a novel declarative XML update language, which is an extension of the XML-RL query language. Compared with other existing XML update languages, it has the following features. First, it is the only XML data manipulation language based on a higher data model. All of the other update languages adopt so-called graph-based or tree-based data models. Therefore, update requests can be expressed in a more intuitive and natural way in our language than in the other languages. Second, our language is designed to deal with ordered and unordered data. Some of the existing languages cannot handle the order of documents. Third, our language can express complex update requests at multiple level in a hierarchy in a simple and fast way. Some existing languages have to express such complex requests in nested updates, which is too complicated and nonintuitive to comprehend for end users. Fourth, our language directly supports the functionality of updating complex objects while all other update language do not support these operations. Lastly, most of existing languages use rename to modify attribute and element names, which is a different way from updates on value. Our language modifies tag names, values, and objects in a unified way by the introduction of three kinds of logical binding variables: object variables, value variables, and name variables. The powerful ability of our language is shown by various examples.

Use of path expressions is a common feature in most XML query languages, and many evaluation methods for path expression queries have been proposed recently. However, there are few researches on the issue of optimizing regular path expression queries. In this paper, two kinds of path expression optimization principles are proposed, named path shortening and path complementing, respectively. The path shortening principle reduces the querying cost by shortening the path expressions with the knowledge of XML schema. While the path complementing principle substitutes the user queries with the equivalent lower-cost path expressions. The experimental results show that these two techniques can largely improve the performance of path expression query processing.

With the rapid development of the Internet and the World Wide Web (WWW), very large amount of information is available and ready for downloading, most of which are free of charge. At the same time, hard disks with large capacity are available at affordable prices. Most of us nowadays often dump a large number of various types of documents into our computers without much thinking. On the other hand, file systems have not changed too much during the past decades. Most of them organize files in directories that form a tree structure, and a file is identified by its name and pathname in the directory tree. Remembering name of files created sometime ago and digging them out from a disk with dozen gigabytes of data in hundred thousands of files becomes never an easy task. Tools available for helping such a search are still far from satisfactory.Xbase (XML-based document BASE) is a prototype system aiming at addressing the above problem. By XML-based, we meant that XML is used to define the metadata. The current version of XBase stores text-based files, including semi-structured data such as XML, HTML, plain text documents (e.g., tex files, computer programs) and those files that can be converted into text (e.g., postscript files, PDF files). In XBase, file name is optional. Users can just load a file into XBase without giving a name and the directory where it should be stored. XBase will automatically associate it with attributes such as the time when the file was saved, its source, its size and type, and etc., To retrieve those files, XBase provides three access methods, explorative browsing, querying using query languages, and keyword based search.

Proposes a new parallel algorithm for computing path expressions, named the "parallel cascade semi-join" (PCSJ) algorithm. Moreover, a new scheduling strategy called the "right-deep zigzag tree" is designed to further improve the performance of the PCSJ algorithm. The experiments have been implemented in a distributed and parallel NOW (network of workstations) environment. The results show that the PCSJ algorithm outperforms two other parallel algorithms [the parallel forward pointer chasing (PFPC) algorithm and the index-splitting parallel algorithm (IndexSplit)] when computing path expressions with restrictive predicates, and that the right-deep zigzag tree scheduling strategy has a better performance than the right-deep tree scheduling strategy.