Electrocardiogram (ECG) analysis is crucial for the diagnosis of cardiovascular disease. However, real-world deployment faces three key challenges: (1) the need for large amounts of manually labeled ECG data, which is time-consuming to collect. (2) the necessity of flexible addressing issues such as variations in clinical data distribution, noise, and low data quality. (3) the requirement for models to generalize across ECG data from different application scenarios. To address these issues, we propose ECGMind, a self-supervised foundational model for various ECG classification tasks. ECGMind is trained on unlabeled data and utilizes a masked autoencoder (MAE) backbone to selectively mask critical regions (e.g., R waves), thereby promoting the reconstruction of diagnostically important features. A dynamic energy score adjusts the importance of each ECG patch based on reconstruction difficulty, prioritizing hard-to-reconstruct areas to enhance feature learning. Our experiments are conducted on both static and dynamic ECG datasets, involving different classification tasks. The results demonstrate ECGMind 's superior performance and scalability, offering a solution for both clinical and ambulatory ECG analysis. ECGMind has deployed as an intelligent diagnostic service at http://heartmind.ecgdb.com. The core code can be evaluated at https://github.com/tianti1/ECGMind.

Real-world temporal graphs are largely driven by sequential dynamics, and edge repetitions are rare. This characteristic has spotlighted a key limitation of existing temporal graph neural networks (T-GNNs): on such graphs, state-of-the-art T-GNNs often achieve less than 70% MRR on link prediction. Two factors drive this shortfall: (1) Memory modules and neighbor co-occurrence encodings in existing T-GNNs often fail since they rely on memorizing exact neighbor identities and on the co-occurrence assumption. (2) Existing T-GNNs are sensitive to abrupt events, which are common in sequential settings that can exceed ten million updates, thereby compromising generalization. To tackle the challenges of sequential dynamics, we propose SeqFilter, a simple yet robust neural network that functions as a composite filter for link prediction on temporal graphs. SeqFilter comprises two modules: a node rhythm memory and a frequency-selective structure encoder. The node rhythm memory shifts the focus from who interacts to when, modeling absolute timestamps with recency awareness to capture each node's interaction rhythm. To model temporal structures in complex sequential dynamics, we propose a frequency-selective structure encoder that amplifies or suppresses specific frequencies in the neighbor spectrum, enabling the effective modeling of local structure correlations. Theoretically, this encoder functions as a cascade of three learnable filters that approximate the optimal linear denoiser, helping capture the underlying structural patterns. Last, SeqFilter fuses the outputs of two modules to generate high-quality node embeddings. Extensive experiments across eight sequential dynamic datasets show that SeqFilter outperforms 11 baselines by an average improvement of 15.82% in MRR while achieving an order of magnitude speedup compared to the frequency-enhanced baseline.

With growing demands for data privacy and model robustness, graph unlearning (GU), which erases the influence of specific data on trained GNN models, has gained significant attention. However, existing exact unlearning methods suffer from either low efficiency or poor model performance. While more utility-preserving and efficient, current approximate methods require access to the forget set during unlearning, which makes them inapplicable in immediate deletion scenarios, thereby undermining privacy. Additionally, these approximate methods, which attempt to directly perturb model parameters, still raise significant concerns regarding unlearning power in empirical studies. To fill the gap, we propose Transferable Condensation Graph Unlearning (TCGU), a data-centric solution to graph unlearning. Specifically, we first develop a two-level alignment strategy to pre-condense the original graph into a compact yet utility-preserving dataset for subsequent unlearning tasks. Upon receiving an unlearning request, we fine-tune the pre-condensed data with a low-rank plugin, to directly align its distribution with the remaining graph, thus efficiently revoking the information of deleted data without accessing them. A novel similarity distribution matching approach and a discrimination regularizer are proposed to effectively transfer condensed data and preserve its utility in GNN training, respectively. Finally, we retrain the GNN on the transferred condensed data. Extensive experiments on 7 benchmark datasets demonstrate that TCGU can achieve superior performance in terms of model utility, unlearning efficiency, and unlearning efficacy compared to existing GU methods. To the best of our knowledge, this is the first study to explore graph unlearning with immediate data removal using a data-centric approximate method.

Self-supervised learning (SSL) provides a promising paradigm for hypergraph representation learning without reliance on costly labels. However, existing hypergraph SSL methods predominantly employ contrastive learning with instance level discrimination, encountering two significant challenges: (1) Unreliable negative sampling, where arbitrarily selected negative samples introduce bias by misclassifying similar and dissimilar pairs; and (2) High computational cost, as effective training requires a large number of negative samples. To address these limitations, we propose SE-HSSL, a hypergraph SSL frame work with three sampling-efficient self-supervised objectives. Specifically, two sampling-free objectives based on canonical correlation analysis serve as node- and group-level signals, while a hierarchical membership-level contrastive objective exploits the cascading overlap structure of hypergraphs. Overall, these designs mitigate negative sampling bias and enhance sampling efficiency, leading to better downstream performance and faster training. Beyond these challenges, deep hypergraph models are prone to biased predictions against groups defined by sensitive attributes (e.g., gender and race). To address fairness concerns, we first theoretically show that imbalanced contributions of demographic groups during hypergraph message passing amplify sensitive biases in the training data. Motivated by this, we propose FairHSSL, a fairness-aware variant of SE-HSSL equipped with a two-level debiasing augmentation strategy. To generate a fair hypergraph view, the augmentation integrates two complementary components: feature-level debiasing and structure-level perturbation. Specifically, orthogonal projection is applied at the feature level to decouple node features from sensitive attributes, while rebalance-based perturbation is introduced at the structure level to equalize the contributions of different sensitive groups during message passing. Finally, by aligning the fair augmented and original biased views in SSL, we mitigate the influence of sensitive information. Extensive experiments on 10 real-world hypergraphs demonstrate the superior effectiveness and efficiency of SE-HSSL. Moreover, FairHSSL consistently outperforms state of-the-art (SOTA) baselines in terms of utility-fairness trade-off across all datasets.

Bipartite graphs are commonly used to model relationships between two distinct entities in real-world applications, such as user-product interactions, user-movie ratings and collaborations between authors and publications. A butterfly (a 2×2 bi-clique) is a critical substructure in bipartite graphs, playing a significant role in tasks like community detection, fraud detection, and link prediction. As more real-world data is presented in a streaming format, efficiently counting butterflies in streaming bipartite graphs has become increasingly important. However, most existing algorithms typically assume that duplicate edges are absent, which is hard to hold in real-world graph streams, as a result, they tend to sample edges that appear multiple times, leading to inaccurate results. The only algorithm designed to handle duplicate edges is FABLE, but it suffers from significant limitations, including high variance, substantial time complexity, and memory inefficiency due to its reliance on a priority queue. To overcome these limitations, we introduce DEABCpro (Duplicate-Edge-Aware Butterfly Counting), an innovative method that uses bucket-based priority sampling to accurately estimate the number of butterflies, accounting for duplicate edges. Compared to existing methods, DEABCpro significantly reduces memory usage by storing only the essential sampled edge data while maintaining high accuracy. We provide rigorous proofs of the unbiasedness and variance bounds for DEABCpro, ensuring they achieve high accuracy. We compare DEABCpro with state-of-the-art algorithms on real-world streaming bipartite graphs. The results show that our DEABCpro outperforms existing methods in memory efficiency and accuracy, while also achieving significantly higher throughput.

Account risk detection, which aims to identify accounts at forced liquidation risk within financial account-asset bipartite graphs, is crucial for ensuring financial market stability and economic resilience. Although traditional node-classification-based anomaly detection techniques can be applied to this task, these approaches often exhibit two key limitations: (1) insufficient consideration of asset fluctuations, resulting in unsatisfactory accuracy; and (2) scalability challenges, making them unsuitable for large-scale financial graphs. To address these issues, we propose RiskGuard, a novel framework for account risk detection that integrates auxiliary asset prediction and gradient-based sampling. First, we introduce an auxiliary asset prediction paradigm to capture the critical influence of asset fluctuations on account risk. Rather than solely predicting account risk, our unified model employs aTemporal-AttentionNet(TANet) to jointly predict asset fluctuations and account risk. This auxiliary task enables the model to learn fluctuation-aware asset representations, significantly enhancing prediction accuracy. To overcome scalability challenges, we design GLUE, an online graph sampler leveraging gradient entropy. GLUE dynamically adjusts sampling weights based on model gradients and graph structure, prioritizing high-entropy nodes in the neighborhood for improved efficiency. Extensive experiments on five financial datasets demonstrate that RiskGuard outperforms existing techniques in accuracy while achieving high efficiency in processing large financial graphs.

Hierarchical directed acyclic graph (DAG) is an essential model for representing terminologies and their hierarchical relationships, such as Disease Ontology and ImageNet categories. Due to the vast number of terminologies and complex structures in a large DAG, it becomes challenging for humans to effectively analyze and explore the hierarchical relationships they encode. Therefore, summarizing hierarchical DAGs is essential for enhancing the interpretability and visualization of the underlying hierarchy. Beyond visual data exploration, hierarchical DAG summarization also supports a range of applications, such as biomedical ontology analytics, snippet generation for information search, and summarized recommendation. In this article, we address a new problem of finding k representative vertices to summarize a hierarchical DAG. To capture diverse summarization and identify important vertices, we design a summary score function that reflects vertices diversity coverage and structure correlation. The studied problem is theoretically proven to be NP-hard. To tackle it efficiently, we propose a greedy algorithm with an approximation guarantee that iteratively adds vertices with significant summary contributions to the answers. To further enhance the answer quality, we introduce a subtree extraction-based method that is proven to achieve higher-quality answers. Additionally, we develop a scalable algorithm, \(\mathsf {k}\) - \(\mathsf {PCGS}\) , which employs candidate pruning and DAG compression for large-scale hierarchical DAGs. For the query-dependent problem, we propose an index-based method and several optimization techniques to improve efficiency. Extensive experiments on large real-world datasets demonstrate the effectiveness and efficiency of our proposed algorithms.

Abstract Hypergraph decomposition is a fundamental problem in hypergraph analysis which breaks down hypergraphs into cohesive subgraphs and functional units with dense interactions. Hyperedge intersections and overlaps capture the unique property of shared elements (vertices) between groups (hyperedges) in hypergraphs, revealing cohesive substructures not apparent when focusing solely on individual connections. Despite the significance of hyperedge overlap as a measure of hypergraph cohesiveness, existing models for hypergraph decomposition fail to capture this feature. In this paper, we study the problem of hypergraph decomposition with intersection bounds. We propose the ( k , s )-core, a new cohesive subgraph model incorporating both a vertex degree constraint k and a hyperedge intersection constraint s . This model includes two types: (1) strong ( k , s )-cores, where connected hyperedges share at least s vertices, enforcing strong hyperedge overlap, and (2) weak ( k , s )-cores, where hyperedges are connected through s -walks, allowing for a looser overlap. We prove that our definition of ( k , s )-cores exhibits uniqueness and hierarchical properties. Based on the properties, we develop two decomposition algorithms: a bottom-up algorithm for strong ( k , s )-cores, which uses a heuristic hyperedge removal mechanism to maintain consistent decomposition results and employs a union-find data structure for efficient connectivity identification, and a top-down algorithm for weak ( k , s )-cores that preserves the subgraph containment relationship. Our algorithms achieve traversal efficiency by processing each hyperedge in the hypergraph only once. Additionally, all ( k , s )-cores can be efficiently stored with minimal memory overhead. Comprehensive experiments and case studies show that the ( k , s )-core model outperforms existing methods in capturing cohesive subgraphs with overlaps in hypergraphs. Furthermore, the proposed algorithms demonstrate high efficiency and scalability, making them well-suited for real-world hypergraphs.

In the drug discovery process, the low success rate of drug candidate screening often leads to insufficient labeled data, causing the few-shot learning problem in molecular property prediction. Existing methods for few-shot molecular property prediction overlook the sample selection bias, which arises from non-random sample selection in chemical experiments. This bias in data representativeness leads to suboptimal performance. To overcome this challenge, we present a novel method named Contextual Representation Anchor Network (CRANet), where an anchor refers to a cluster center of the representations of molecules and serves as a bridge to transfer enriched contextual knowledge into molecular representations and enhance their expressiveness. CRANet introduces a dual-augmentation mechanism that includes context augmentation, which dynamically retrieves analogous unlabeled molecules and captures their task-specific contextual knowledge to enhance the anchors, and anchor augmentation, which leverages the anchors to augment the molecular representations. We evaluate our approach using the MoleculeNet and FS-Mol benchmarks, as well as through domain transfer experiments. The outcomes indicate that CRANet surpasses current state-of-the-art methods by 0.10% to 5.48% in AUC and 2.52% in ΔAUC-PR metrics, showcasing its exceptional generalization abilities.

Data generation is a fundamental research problem in data management due to its diverse use cases, ranging from testing database engines to data-specific applications. However, real-world entities often involve complex interactions that cannot be effectively modeled by traditional tabular data. Therefore, graph data generation has attracted increasing attention recently. Although various graph generators have been proposed in the literature, there are three limitations: i) They cannot capture the co-evolution pattern of graph structure and node attributes. ii) Few of them consider edge direction, leading to substantial information loss. iii) Current state-of-the-art dynamic graph generators are based on the temporal random walk, making the simulation process time-consuming. To fill the research gap, we introduce VRDAG, a novel variational recurrent framework for efficient dynamic attributed graph generation. Specifically, we design a bidirectional message-passing mechanism to encode both directed structural knowledge and attribute information of a snapshot. Then, the temporal dependency in the graph sequence is captured by a recurrence state updater, generating embeddings that can preserve the evolution pattern of early graphs. Based on the hidden node embeddings, a conditional variational Bayesian method is developed to sample latent random variables at the neighboring timestep for new snapshot generation. The proposed generation paradigm avoids the time-consuming path sampling and merging process in existing random walk-based methods, significantly reducing the synthesis time. Finally, comprehensive experiments on real-world datasets are conducted to demonstrate the effectiveness and efficiency of the proposed model.

Uncertain butterflies are fundamental and popular graphlet motifs within uncertain bipartite networks, serving as a crucial metric in structural analysis. Despite extensive research have studied butterflies sufficiently on deterministic networks, few of works explore uncertain butterflies. In this paper, we introduce the Most Probable Maximum Weighted Butterfly (MPMB), which holds the highest probability of becoming a maximum weighted butterfly on an uncertain bipartite network. Proved that searching MPMBs is NP-Hard, we then proposed two samplingbased methods, namely Ordering Sampling (OS), and Ordering-Listing Sampling (OLS). The OS method is suitable for singletrial sampling, while the OLS method is optimized for multiple trials, which first finds candidate butterflies in rough before searching MPMBs. Our experimental results indicate that our basic method (OS) performs 1000× faster than the baseline and the optimized method (OLS) achieves another 180× speedup.

In the current era of data-intensive applications, the demand for high-performance, cost-effective storage solutions is paramount. This paper introduces a Space-Performance Cost Model for key-value store, designed to guide cost-effective storage configuration decisions. The model quantifies the trade-offs between performance and storage costs, providing a framework for optimizing resource allocation in large-scale data serving environments. Guided by this cost model, we present Tier-Base, a distributed key-value store developed by Ant Group that optimizes total cost by strategically synchronizing data between cache and storage tiers, maximizing resource utilization and effectively handling skewed workloads. To enhance cost-efficiency, TierBase incorporates several optimization techniques, including pre-trained data compression, elastic threading mechanisms, and the utilization of persistent memory. We detail TierBase's architecture, key components, and the implementation of cost optimization strategies. Extensive evaluations using both synthetic benchmarks and real-world workloads demonstrate TierBase's superior cost-effectiveness compared to existing solutions. Furthermore, case studies from Ant Group's production environments showcase TierBase's ability to achieve up to 62% cost reduction in primary scenarios, highlighting its practical impact in large-scale online data serving.

Nowadays, ride-sharing is developing rapidly because of its economic and environmental advantages. Recent studies investigate the benefits of introducing meeting points during task assignments, allowing riders to be picked up or dropped off near their requested locations. In this paper, we study the route and area matching (ROAM) problem in dynamic road networks. ROAM query aims to find a detour path from source to destination visiting an area, meanwhile satisfying a detour budget. Existing method excludes unmatched queries in a compacted sketch graph, but the Dijkstra-based routing process is still time-consuming. Moreover, maintaining the sketch graph in frequently changing road networks is challenging because it requires computing from scratch. To overcome the limitations, we propose a simple yet effective framework named meeting point search (MPS). A novel index structure named GS-Tree is constructed to integrate spatial information for selecting meeting points and graph shortcuts for routing queries. GSTree has structural stability and can be efficiently maintained in dynamic networks. Theoretical analysis and experimental studies demonstrate the superiority of our methods. The optimal MPS with GS-Tree averagely outperforms the existing methods by two orders of magnitude.

In this paper, we study the problem of maximal similar-weight biclique enumeration for large bipartite graphs. Given an edge-weighted bipartite graph$G=(U,\ V,\ E)$and a weight difference threshold$\delta$, we aim to efficiently enumerate all maximal similar-weight bicliques in$G$, where a maximal similar-weight biclique is a maximal complete subgraph$B(L,\ R)$of$G$such that the weight difference of edges in$E(B)$is not larger than$\delta$. This problem has many applications, such as item recommendation, fraud detection, and biclustering of gene expression data, etc. To the best of our knowledge, we are the first to systematically study this problem. It is very challenging to efficiently solve this problem due to its #P-completeness. In this paper, we propose a two-phase branch-and-bound baseline method, namely MSWBE, which explores the search space in a depth-first manner. Although MSWBE offers a useful computation framework to our problem, its performance is not yet satisfactory due to the large candidate set during the enumeration. To alleviate this, we propose an advanced approach, called MSWBE++. In particular, MSWBE++ exploits the search space by utilizing the edge connectivity and weight information simultaneously, and therefore refines the candidate set significantly. Observing that a straightforward implementation of MSWBE++ by following a depth-first search strategy may generate non-maximal bicliques, we develop a breadth-first search strategy to realize MSWBE++, which can discard the non-maximal sets at an early stage. To accelerate the computation, we introduce effective graph reduction techniques. Our extensive experimental results on 10 real-life datasets demonstrate that MSWBE++ significantly outperforms the baseline methods by up to 2 orders of magnitude. We conduct a case study to show that maximal similar-weight bicliques can provide useful searching hints for fraudulent rating detection.

Structural graph clustering (SCAN) is one of the most popular graph clustering paradigms, and has attracted plenty of attention recently. Existing solutions assume that the input graphs is homogeneous, i.e., the vertices are of the same type. However, in many real applications, such as bibliographic networks and knowledge graphs, the input graphs is heterogeneous information networks which consist of multi-typed and interconnected objects, which makes SCAN cannot be applied to cluster. Therefore, in this paper, we study the SCAN problem over heterogeneous information networks. Based on the concept of meta-path, we propose two new structural graph clustering models first. Following these two new models, we design new algorithms to support the efficient clustering of a heterogeneous information network. We conduct extensive experiments on six real heterogeneous information networks, and the results demonstrate the effectiveness of our new models and the efficiency of our proposed clustering algorithms.

Ridesharing services play an essential role in modern transportation, which significantly reduces traffic congestion and exhaust pollution. In the ridesharing problem, improving the sharing rate between riders can not only save the travel cost of drivers but also utilize vehicle resources more efficiently. The existing online-based and batch-based methods for the ridesharing problem lack the analysis of the sharing relationship among riders, leading to a compromise between efficiency and accuracy. In addition, the graph is a powerful tool to analyze the structure information between nodes. Therefore, in this paper, we propose a framework, namely StructRide, to utilize the structure information to improve the results for ridesharing problems. Specifically, we extract the sharing relationships between riders to construct a shareability graph. Then, we define a novel measurement, namely shareability loss, for vehicles to select groups of requests such that the unselected requests still have high probabilities of sharing with other requests. Our SARD algorithm can efficiently solve dynamic ridesharing problems to achieve dramatically improved results. Through extensive experiments, we demonstrate the efficiency and effectiveness of our SARD algorithm on two real datasets. Our SARD can run up to 72.68 times faster and serve up to 50% more requests than the state-of-the-art algorithms.

Edge connectivity is a crucial concept in graph theory, which often serves as a fundamental metric for analyzing and improving the robustness, efficiency, and reliability of various types of networks. A graph is k-connected if it is still connected after removing arbitrarily fewer than$k$edges. Sparse certificate is the lossless compression of a graph in terms of k-connectivity with a bounded size, which enables processing connectivity-driven queries in a more efficient way. Existing studies mainly focus on computing a sparse certificate in static graphs. Motivated by the prevalence of highly dynamic graphs, we aim to propose algorithms to maintain a sparse certificate when an edge is in-serted or deleted. We propose efficient algorithms to significantly improve the theoretical running time for both edge insertion and edge deletion compared with the baseline. We also propose a novel strategy for the search process in edge deletion. The strategy improves the efficiency compared with other potential methods with a theoretical guarantee. Extensive performance studies have been conducted on fourteen real-world datasets. The results demonstrate the significant advantages of our algorithms.

Temporal hypergraph representation learning is a concept that integrates high-order structure learning with temporal dynamics, enabling more accurate analysis of temporal and high-order interactions. To enhance model expressiveness, the latest work samples multi-hop hyperedge-centric neighbors directly from temporal hypergraphs and encodes them for high-order structure learning, achieving promising performance. Such modeling, however, incurs prohibitive computational complexity, which increases exponentially with model depth and quadratically with average hyperedge cardinality, thereby limiting model scalability. In this paper, we propose FastHeP, a fast and accurate approach for temporal hyperedge prediction, which can handle large temporal hypergraphs. The key idea is to minimize computational complexity while maintaining model expressiveness. Concretely, we design an online hyperedge-centric neighbor store, which can store time-aware and redundancy-aware neighbors for nodes with rational theoretical guarantees. Upon the neighbor store, we propose a novel hybrid message passing to model temporal high-order structures, theoretically preserving strong expressive power. This explicitly learns local high-order structures for nodes of each hyperedge via graph attention, generating the node-wise structure features. These structure features are then fused into global correlations modeling among hyperedges, with a theoretical guarantee of permutation invariance. Last, FastHeP leverages local and global high-order semantics to generate temporal hyperedge embeddings, which is efficient in a linear complexity w.r.t. model depth and average hyperedge cardinality. Extensive experiments show that FastHeP achieves up to two orders of magnitude speed-up against baselines, with an average accuracy improvement of 5.1%.

Path enumeration is a fundamental problem and has been extensively studied in the literature. Given two query vertices and a weight threshold, the problem aims to identify all simple paths with weight not exceeding the threshold. Existing studies on path enumeration include DFS-based solutions and join-based solutions, where the join-based solutions only work for unweighted graphs. In this paper, we are the first to propose a join-based framework for weighted graphs. By observing the characteristics of DFS, we design a series of novel data structures and operations based on the join-based framework. In this way, our final solution combines the advantages of both join and DFS. We conduct experiments on several real large graphs. For weighted graphs, our method is much more efficient than existing algorithms. For unweighted graphs, our method is still competitive compared with the state-of-the-art solution which only works for unweighted graphs.

The k-clique structure in graphs has been investigated in various real-world applications, such as community detection in complex networks, functional module discovery in biological networks, and link spam detection in web graphs. Despite extensive research on k-clique enumeration, the large number of k-cliques in many graphs poses a challenge for practical application and computation. To address this, we explore the k-clique τ-cover problem, a generalization of the vertex cover problem. The problem aims to find a small set of vertices that can effectively represent all k-cliques in the graph. We prove the NP-hardness of finding the minimum k-clique cover. We propose a hierarchical solution that computes a small cover without enumerating k-cliques. Extensive experiments on real-world graphs verify the efficiency and effectiveness of our solution.

Ranking is an essential and practical task on dynamic graphs, which aims to prioritize future interaction candidates for given queries. While existing solutions achieve promising ranking performance, they leverage a single listwise loss to jointly optimize candidate sets, which leads to the gradient vanishing issue; and they employ neural networks to model complex temporal structures within a shared latent space, which fails to accurately capture multi-scale temporal patterns due to the frequency aliasing issue. To address these issues, we propose BandRank, a novel and robust band-pass disentangled ranking approach for dynamic graphs in the frequency domain. Concretely, we propose a band-pass disentangled representation (BPDR) approach, which disentangles complex temporal structures into multiple frequency bands and employs non-shared frequency-enhanced multilayer perceptrons (MLPs) to model each band independently. We prove that our BPDR approach ensures effective multi-scale learning for temporal structures by demonstrating its multi-scale global convolution property. Besides, we design a robust Harmonic Ranking (HR) loss to jointly optimize candidate sets and continuously track comparisons between real and virtual candidates, where we theoretically guarantee its ability to alleviate the gradient vanishing issue. Extensive experimental results show that our BandRank achieves an average improvement of 21.31% against eight baselines while demonstrating superior robustness across different learning scenarios.

Counting the number of triangles in a graph is a fundamental task and has been extensively studied recently. In real-world applications, continuously releasing the triangle count of a graph poses a significant privacy risk for users. To protect sensitive edge information from a central server, we study the problem of estimating the number of triangles under edge local differential privacy (edge LDP). Existing approaches adopt a multi-round computing scheme, allowing the vertices to perform local triangle counting using the noisy graph constructed in the previous round. However, these algorithms not only restrict the noisy graph that can be downloaded to each vertex, but also have coarse upper bounds for the scale of noise added to the estimates. In this paper, we propose a vertex-centric triangle counting algorithm under edge LDP, which improves data utility by leveraging a larger part of the noisy adjacency matrix. Our approach fully exploits the local graph structure to obtain refined estimates of per-vertex triangle counts. We also devise tight bounds for global sensitivities to not only comply with privacy requirements but also control the scale of added noise. Furthermore, we perform a rigorous analysis of the L2 loss of our unbiased estimators and design optimizations for allocating the privacy budget to minimize L2 loss based on the input graph. Extensive experiments on 12 datasets validate the effectiveness and efficiency of our proposed algorithms.

The rise of graph analytics platforms has led to the development of various benchmarks for evaluating and comparing platform performance. However, existing benchmarks often fall short of fully assessing performance due to limitations in core algorithm selection, data generation processes (and the corresponding synthetic datasets), as well as the neglect of API usability evaluation. To address these shortcomings, we propose a novel graph analytics benchmark. First, we select eight core algorithms by extensively reviewing both academic and industrial settings. Second, we design an efficient and flexible data generator and produce eight new synthetic datasets as the default datasets for our benchmark. Lastly, we introduce a multi-level large language model (LLM)-based framework for API usability evaluation-the first of its kind in graph analytics benchmarks. We conduct comprehensive experimental evaluations on existing platforms (GraphX, PowerGraph, Flash, Grape, Pregel+, Ligra, and G-thinker). The experimental results demonstrate the superiority of our proposed benchmark.

Triangle counting in hypergraph streams-including both hyper-vertex and hyper-edge triangles-is a fundamental problem in hypergraph analytics, with broad applications. However, existing methods face two key limitations: (i) an incomplete classification of hyper-vertex triangle structures, typically considering only inner or outer triangles; and (ii) inflexible sampling schemes that predefine the number of sampled hyperedges, which is impractical under strict memory constraints due to highly variable hyperedge sizes. To address these challenges, we first introduce a complete classification of hyper-vertex triangles, including inner, hybrid, and outer triangles. Based on this, we develop HTCount, a reservoir-based algorithm that dynamically adjusts the sample size based on the available memory M. To further improve memory utilization and reduce estimation error, we develop HTCount-P, a partition-based variant that adaptively partitions unused memory into independent sample subsets. We provide theoretical analysis of the unbiasedness and variance bounds of the proposed algorithms. Case studies demonstrate the expressiveness of our triangle structures in revealing meaningful interaction patterns. Extensive experiments on real-world hypergraphs show that both our algorithms achieve highly accurate triangle count estimates under strict memory constraints, with relative errors that are 1 to 2 orders of magnitude lower than those of existing methods and consistently high throughput.

Overlapping Community Search (OCS) identifies nodes that interact with multiple communities based on a specified query. Existing community search approaches fall into two categories: algorithm-based models and Machine Learning-based (ML) models. Despite the long-standing focus on this topic within the database domain, current solutions face two major limitations: 1) Both approaches fail to address personalized user requirements in OCS, consistently returning the same set of nodes for a given query regardless of user differences. 2) Existing ML-based CS models suffer from severe training efficiency issues. In this paper, we formally redefine the problem of OCS. By analyzing the gaps in both types of approaches, we then propose a general solution for OCS named S parse S ubspace F ilter (SSF), which can extend any ML-based CS model to enable personalized search in overlapping structures. To overcome the efficiency issue in the current models, we introduce S implified M ulti-hop Attention N etworks (SMN), a lightweight yet effective community search model with larger receptive fields. To the best of our knowledge, this is the first ML-based study of overlapping community search. Extensive experiments validate the superior performance of SMN within the SSF pipeline, achieving a 13.73% improvement in F1-Score and up to 3 orders of magnitude acceleration in model efficiency compared to state-of-the-art approaches.

Minimum Spanning Tree (MST) is a fundamental structure in graph analytics and can be applied in various applications. The problem of maintaining MSTs in dynamic graphs is significant, as many real-world graphs are frequently updated. Existing studies on MST maintenance primarily focus on theoretical analysis and lack practical efficiency. In this paper, we propose a novel algorithm to maintain MST in dynamic graphs, which achieves high practical efficiency. In addition to the tree structure, our main idea is to maintain a replacement edge for each tree edge. In this way, the tree structure can be immediately updated when a tree edge is deleted. We propose algorithms to maintain the replacement edge for each tree edge by sharing the computation cost in the updating process. Our performance studies on large datasets demonstrate considerable improvements over state-of-the-art solutions.

With the increasing complexity of urban transportation systems and the growing demand for dynamic, real-time responsiveness, Time-Dependent Minimum Travel Time Queries (TD-MTTQs) in time-dependent road networks have become a core challenge in intelligent transportation system research. To address the trade-offs between preprocessing complexity and query efficiency in existing index-based methods for large-scale road network applications, this paper proposes a 4-hop index method, TD-TNR-CH. The core methodology involves establishing local indexes from each node to its nearest critical nodes (named transit nodes) through strategic critical node selection, while simultaneously constructing query tables associated with candidate sets between these critical nodes. This architecture enables rapid computation of medium-to-long distance queries through efficient index lookups, while ensuring high responsiveness for short-distance queries via TCH-based local searches. Extensive experimental results on large-scale real-world road networks demonstrate that our method exhibits superior scalability, achieving query efficiency of up to 103 times that of the fastest existing algorithms. Furthermore, it shows exceptional stability across queries of varying distances. Additionally, leveraging its parallelized architecture, TD-TNR-CH requires only approximately 30 minutes of preprocessing time for large-scale networks, significantly outperforming comparable methods in terms of preprocessing efficiency.

Hypergraphs provide a versatile framework for modeling complex relationships beyond pairwise interactions, finding applications in various domains. k -core decomposition is a fundamental task in hypergraph analysis that decomposes hypergraphs into cohesive substructures. Existing studies capture the cohesion in hypergraphs based on the vertex neighborhood size. However, such decomposition poses unique challenges, including the efficiency of core value updates, redundant computation, and high memory consumption. We observe that the state-of-the-art algorithms do not fully address the above challenges and are unable to scale to large hypergraphs. In this paper, we propose an efficient approach for hypergraph k -core decomposition. Novel concepts and strategies are developed to compute the core value of each vertex and reduce redundant computation of vertices. Experimental results on real-world and synthetic hypergraphs demonstrate that our approach significantly outperforms the state-of-the-art algorithm by 7 times on average while reducing the average memory usage by 36 times. Moreover, while existing algorithms fail on tens of millions hyperedges, our approach efficiently handles billion-scale hypergraphs in only a single thread.

Streaming data collection is indispensable for stream data analysis, such as event monitoring. However, publishing these data directly leads to privacy leaks. w -event privacy is a valuable tool to protect individual privacy within a given time window while maintaining high accuracy in data collection. Most existing w -event privacy studies on infinite data stream only focus on homogeneous privacy requirements for all users. In this paper, we propose personalized w -event privacy protection that allows different users to have different privacy requirements in private data stream estimation. Specifically, we design a mechanism that allows users to maintain constant privacy requirements at each time slot, namely Personalized Window Size Mechanism (PWSM). Then, we propose two solutions to accurately estimate stream data statistics while achieving w -Event є -Personalized Differential Privacy (( w,є )-EPDP), namely Personalized Budget Distribution (PBD) and Personalized Budget Absorption (PBA). PBD always provides at least the same privacy budget for the next time step as the amount consumed in the previous release. PBA fully absorbs the privacy budget from the previous k time slots, while also borrowing from the privacy budget of the next k time slots, to increase the privacy budget for the current time slot. We prove that both PBD and PBA outperform the state-of-the-art private stream estimation methods while satisfying the privacy requirements of all users. We demonstrate the efficiency and effectiveness of our PBD and PBA on both real and synthetic datasets, compared with the recent uniformity w -event approaches, Budget Distribution (BD) and Budget Absorption (BA). Our PBD achieves 68% less error than BD on average on real datasets. Besides, our PBA achieves 24.9% less error than BA on average on synthetic datasets.

Subgraph counting is a fundamental problem in graph analytics with broad applications, yet remains computationally intractable due to its #P-hardness. To address this, numerous approximate solutions have been proposed, though they often suffer from limited efficiency and accuracy. In this paper, we introduce FlowSC, a novel approach that achieves both high accuracy and efficiency in subgraph counting. Our method starts with an enhanced candidate filtering algorithm, which significantly improves the pruning capability of bipartite graph-based techniques with minimal overhead. Building on this, we propose a bottom-up flow-learning model based on a new Graph Neural Network (GNN) architecture. By employing a carefully designed message-passing mechanism, the model explicitly controls the direction, range, and iterations of information flow, enabling a simulation of the candidate tree-based counting process. This mechanism is further empowered by a customized message aggregation technique, alongside a pretraining strategy that facilitates model training. Extensive experiments show that FlowSC can achieve up to 4 orders of magnitude improvement in accuracy and 3× improvement in efficiency over the baselines across datasets, while scaling to billion-edge graphs.

Log data is a vital resource for capturing system events and states. With the increasing complexity and widespread adoption of modern software systems and IoT devices, the daily volume of log generation has surged to tens of petabytes, leading to significant collection and storage costs. To address this challenge, lossless log compression has emerged as an effective solution, enabling substantial resource savings without compromising log information. In this paper, we first conduct a characterization study on extensive public log datasets and identify four key observations. Building on these insights, we propose LogLite, a lightweight, plug-and-play, streaming lossless compression algorithm designed to handle both TEXT and JSON logs throughout their life cycle. LogLite requires no predefined rules or pre-training and is inherently adaptable to evolving log structures. Our evaluation shows that, compared to state-of-the-art baselines, LogLite achieves Pareto optimality in most scenarios, delivering an average improvement of up to 67.8% in compression ratio and up to 2.7X in compression speed.

Missing data imputation, which aims to impute the missing values in the raw datasets, is crucial for modern data-driven models like large language models (LLMs). Despite its importance, existing solutions either 1) only support numerical and categorical data or 2) show an unsatisfactory performance due to their design prioritizing text data and overlooking intrinsic characteristics of tabular data. In this paper, we propose UnIMP, a Un ified IMP utation framework that leverages LLM and high-order message passing to enhance the imputation of mixed-type data, including numerical, categorical, and text data. Specifically, we first introduce a cell-oriented hypergraph to model the table. We then propose BiHMP, an efficient Bidirectional High-order Message-Passing network to aggregate global-local and high-order information while capturing the inter-column heterogeneity and intra-column homogeneity. To align the capacity of the LLM with the information aggregated by BiHMP, we introduce Xfusion, which, together with BiHMP, acts as adapters for the LLM. We follow a pre-training and fine-tuning pipeline to train UnIMP, integrating two optimizations: chunking technique, which divides tables into smaller chunks to enhance efficiency; and progressive masking technique, which gradually adapts the model to learn more complex data patterns. Both theoretical proofs and empirical experiments on 10 real-world datasets highlight the superiority of UnIMP over existing techniques.

Semantic caching significantly reduces computational costs and improves efficiency by storing and reusing large language model (LLM) responses. However, existing systems rely primarily on matching individual queries, lacking awareness of multi-turn dialogue contexts, which leads to incorrect cache hits when similar queries appear in different conversational settings. This demonstration introduces ContextCache, a context-aware semantic caching system for multi-turn dialogues. ContextCache employs a two-stage retrieval architecture that first executes vector-based retrieval on the current query to identify potential matches and then integrates current and historical dialogue representations through self-attention mechanisms for precise contextual matching. Evaluation of real-world conversations shows that ContextCache improves precision and recall compared to existing methods. Additionally, cached responses exhibit approximately 10 times lower latency than direct LLM invocation, enabling significant computational cost reductions for LLM conversational applications.

Approximate nearest neighbor search (ANNS) is a fundamental problem in vector databases and AI infrastructures. Recent graph-based ANNS algorithms have achieved high search accuracy with practical efficiency. Despite the advancements, these algorithms still face performance bottlenecks in production, due to the random memory access patterns of graph-based search and the high computational overheads of vector distance. In addition, the performance of a graph-based ANNS algorithm is highly sensitive to parameters, while selecting the optimal parameters is cost-prohibitive, e.g., manual tuning requires repeatedly re-building the index. This paper introduces VSAG , an open-source framework that aims to enhance the in production performance of graph-based ANNS algorithms. VSAG has been deployed at scale in the services of Ant Group, and it incorporates three key optimizations: ( i) efficient memory access : it reduces L3 cache misses with pre-fetching and cache-friendly vector organization; ( ii) automated parameter tuning : it automatically selects performance-optimal parameters without requiring index rebuilding; ( iii) efficient distance computation : it leverages modern hardware, scalar quantization, and smartly switches to low-precision representation to dramatically reduce the distance computation costs. We evaluate VSAG on real-world datasets. The experimental results show that VSAG achieves the state-of-the-art performance and provides up to 4× speedup over HNSWlib (an industry-standard library) while ensuring the same accuracy.

In this paper, we study two different problems that investigate relations between given vertices$s$and$t$. The first problem is to generate the$k$-hop-constrained$s$-$t$path graph, i.e., the subgraph consisting of all paths from$s$to$t$, where each path is not longer than$k$s.t.$s$and$t$appear only once. To solve the first problem, we propose theA-BiBFS$^{++}$t++method enhanced with the reduced neighbor index and an approximate vertex grouping strategy. The second problem is to generate the$k$-hop-constrained$s$-$t$simple path graph, i.e., the subgraph consisting of all$k$-hop-constrained simple paths from$s$to$t$, which is proved to be NP-hard on directed graphs. Based onA-BiBFS$^{++}$t++, we propose theEVEmethod to tackle the second problem, which exploits the paradigm of edge-wise examination rather than exhaustively enumerating all simple paths. Extensive experiments show that bothA-BiBFS$^{++}$s++andEVEsignificantly outperform all baselines. Moreover, by takingEVEas a built-in block, state-of-the-art for hop-constrained simple path enumeration can be accelerated by up to an order of magnitude.

Fraud detection, a classical data mining problem in finance applications, has risen in significance amid the intensifying confrontation between fraudsters and anti-fraud forces. Recently, an increasing number of criminals are constantly expanding the scope of fraud activities to covet the property of innocent victims. However, most existing approaches require abundant historical records to mine fraud patterns from financial transaction behaviors, thereby leading to significant challenges to protect minority groups, who are less involved in the modern financial market but also under the threat of fraudsters nowadays. Therefore, in this paper, we propose a novel community-enhanced multi-relation graph neural network-based model, named CMR-GNN, to address the important defects of existing fraud detection models in the tail effect situation. In particular, we first construct multiple types of relation graphs from historical transactions and then devise a clustering-based neural network module to capture diverse patterns from transaction communities. To mitigate information lacking tailed nodes, we proposed tailed-groups learning modules to aggregate features from similarly clustered subgraphs by graph convolution networks. Extensive experiments on both the real-world and public datasets demonstrate that our method not only surpasses the state-of-the-art baselines but also could effectively harness information within transaction communities while mitigating the impact of tail effects.

Cohesive subgraph computation on bipartite graphs has drawn significant research interest recently. As a popular cohesive subgraph model,$k$-bitruss is defined as the maximal subgraph where each edge is contained in at least$k$butterflies (i.e., a (2, 2)-biclique). The bitruss decomposition problem is widely studied, which aims to compute all$k$-bitrusses for$k \geq 0$. The state-of-the-art CPU-based solutions require extensive costs to construct an index structure for grouping butterflies, leading to scalability challenges on large bipartite graphs. In this paper, we explore bitruss decomposition with GPU by leveraging the parallel computing capabilities of GPU architectures. As the index-based approach requires extensive space and the memory resources of GPUs are limited, we proposeGBiD, which is a peeling-based algorithm on GPUs that utilizes a block-centric computation scheme to enable space-efficient bitruss decomposition without any indexing structure. In addition, cost-aware common neighbor exploration and neighbor list accessing optimizations are proposed to enhanceGBiDby reducing the cost of enumerating butterflies and accessing the graph structure during the peeling process. Extensive experiments conducted on 10 real-world datasets demonstrate that our proposed techniques significantly surpass existing CPU-based solutions in terms of both space and time efficiency.

Link prediction, which aims to predict the existence of a link between two nodes in a network, has various applications ranging from friend recommendation to protein interaction prediction. Recently, Graph Neural Network (GNN)-based link prediction has demonstrated its advantages and achieved the state-of-the-art performance. Typically, GNN-based link prediction can be formulated as a binary classification problem. However, in link prediction, we only have positive data (observed links) and unlabeled data (unobserved links), but no negative data. Therefore, Positive Unlabeled (PU) learning naturally fits the link prediction scenario. Unfortunately, the unknown class prior and data imbalance of networks impede the use of PU learning in link prediction. To deal with these issues, this paper proposes a novel model-agnostic PU learning algorithm for GNN-based link prediction by means ofPositive-Unlabeled Area Under the Receiver Operating Characteristic Curve(PU-AUC) optimization. The proposed method is free of class prior estimation and able to handle the data imbalance. Moreover, we propose an accelerated method to reduce the operational complexity of PU-AUC optimization from quadratic to approximately linear. Extensive experiments back up our theoretical analysis and validate that the proposed method is capable of boosting the performance of the state-of-the-art GNN-based link prediction models.

A$k$-plex is a subgraph in which each vertex can miss edges to at most$k$vertices, including itself.$k$-plex can find many real-world applications such as social network analysis and product recommendation. Previous studies about$k$-plex mainly focus on static graphs. However, in reality, relationships between two entities often occur at some specific timestamps, which can be modeled as temporal graphs. Directly extending the$k$-plex model may fail to find some critical groups in temporal graphs, which exhibit certain frequent occurring patterns. To fill the gap, in this paper, we develop a novel model, named$(k,l)$-plex, which is a vertex set that exists in no less than$l$timestamps, at each of which the subgraph induced is a$k$-plex. To identify practical results, we propose and investigate two important problems, i.e., large maximal$(k,l)$-plex (MalKLP) enumeration and maximum$(k,l)$-plex (MaxKLP) identification. For the MalKLP enumeration problem, a reasonable baseline method is first proposed by extending the Bron-Kerbosch (BK) framework. To overcome the limitations in baseline and scale for large graphs, optimized strategies are developed, including novel graph reduction approach and search branch pruning techniques. For the MaxKLP identification task, we first design a baseline method by extending the proposed enumeration framework. Additionally, to accelerate the search, a new search framework with efficient branch pruning rules and refined graph reduction method is developed. Finally, comprehensive experiments are conducted on 14 real-world datasets to validate the efficiency and effectiveness of the proposed techniques.

Dynamic graphs, which capture time-evolving edges between nodes, are formulated in continuous-time or discrete-time dynamic graphs. They differ in temporal granularity: Continuous-Time Dynamic Graphs (CTDGs) exhibit rapid, localized changes, while Discrete-Time Dynamic Graphs (DTDGs) show gradual, global updates. This difference leads to isolated developments in representation learning for each type. To advance dynamic graph representation learning, recent research attempts to design a unified model capable of handling both CTDGs and DTDGs, achieving promising results. However, it typically focuses on local dynamic propagation for temporal structure learning in the time domain, failing to accurately capture the underlying structural evolution associated with each temporal granularity and thus compromising model effectiveness. In addition, existing works-whether specific or unified-often overlook the issue of temporal noise, compromising the model's robustness. To better model both types of dynamic graphs, we propose UniDyG, a unified and effective representation learning approach, which can scale to large dynamic graphs. Specifically, we first propose a novel Fourier Graph Attention (FGAT) mechanism that can model local and global structural correlations based on recent neighbors and complex-number selective aggregation, while theoretically ensuring consistent representations of dynamic graphs over time. Based on approximation theory, we demonstrate that FGAT is well-suited to capture the underlying structures in both CTDGs and DTDGs. We further enhance FGAT to resist temporal noise by designing an energy-gated unit, which adaptively filters out high-frequency noise according to the energy. Last, we leverage our proposed FGAT mechanisms for temporal structure learning and employ the frequency-enhanced linear function for node-level dynamic updates, facilitating the generation of high-quality temporal embeddings. Extensive experiments show that our UniDyG achieves an average improvement of 14.4% over sixteen baselines across nine dynamic graphs while exhibiting superior robustness in noisy scenarios.

Exploring the hierarchical structure of graphs presents notable advantages for graph analysis, revealing insights ranging from individual vertex behavior to community distribution and overall graph stability. This paper studies hierarchical structures within hypergraphs, where a hyperedge can connect multiple vertices. We observed that directly extending hierarchical frameworks from pairwise graphs to hypergraphs overlooks high-order interactions and can result in either high computational complexity or sparse hierarchy structure. To address this challenge, we introduce a dual-layer hypergraph hierarchy consisting of a primary hierarchy and a secondary hierarchy, enabling the construction of a refined hypergraph hierarchy in linear time. The dual-layer hierarchy establishes a global hierarchy based on vertex cohesion, utilizing vertex-induced subhypergraphs, and a local hierarchy based on hyperedge containment, employing edge-induced subhypergraphs. The combination of global and local hierarchy mitigates the homogeneity and sparsity issues inherent in single-layer hierarchies, allowing more effective modeling of high-order interactions. Furthermore, we propose an efficient hierarchical construction algorithm by leveraging a novel hyperedge-based disjoint set to identify connected subhypergraphs. Additionally, to optimize the local hierarchy further and prevent the emergence of excessively redundant levels, we introduce a compact local hierarchy by defining a restricted subgraph metric to eliminate redundancy caused by large-sized hyperedges. Empirical studies on real-world hypergraphs demonstrate the effectiveness of our approach.

Temporal graph neural networks (T-GNNs) have emerged as leading approaches for representation learning over dynamic graphs. However, existing solutions typically suffer from exponential time complexity with model depth and excessive GPU memory usage due to acceleration techniques, and cannot handle large dynamic graphs. Furthermore, the core component of T-G NNs, temporal message passing, still predominantly derives from static GNNs. This neglects the distinct characteristics of two types of features, timestamps and edge features, and results in sub-optimal embedding quality. Consequently, existing T-GNNs fail to scale to large dynamic graphs and generalize well in unseen or complex scenarios, limiting their applicability. To bridge the gap, this paper first proposes a simple yet effective temporal message passing paradigm for T-GNNs, called the divided temporal message passing (DT-MP) paradigm, which enables effective feature learning for each feature type. We theoretically demonstrate that the DT-MP paradigm can reduce GPU memory usage compared to existing T-GNNs. Building on this foundation, we propose TimeSGN, a scalable and effective temporal graph neural network, which can handle billion-scale dynamic graphs. Specifically, we design a linear state updater to effectively capture node dynamic evolution and instantiate the DT-MP paradigm using two 1-layer self-attention mechanisms for temporal message passing to generate temporal embeddings. As a result, TimeSGN fundamentally avoids exponential time complexity and significantly reduces GPU memory usage. Extensive experiments demonstrate that TimeSGN achieves an average 10.56% improvement in accuracy, up to 42.48% reduction in training GPU memory, and up to 5 x speedup in per-epoch training time compared to the state-of-the-art baselines, while being one order of magnitude faster than vanilla T-GNNs.

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.

Butterfly counting on bipartite graphs has gained increasing attention in past decades. Inevitably, butterfly counts can reveal the presence of certain edges, posing a privacy risk in real applications. Edge local differential privacy (edge LDP), which requires each vertex to perturb its neighbors locally, has been applied to protect edge privacy in graphs. This paper, for the first time, investigates butterfly counting on bipartite graphs with edge LDP. Although a straightforward approach that allows each vertex to perturb its incident edges locally to construct a noisy graph and perform butterfly counting preserves edge LDP, it often results in severe over-counting and significant bias since the resulting noisy graph is generally much denser than the input graph. To obtain unbiased butterfly counts, we propose a multiple-round interaction algorithm to allow the vertices to download the noisy graph and compute local motif counts. Moreover, to avoid adding substantial noise to satisfy edge LDP, we further propose the Download-free Butterfly. Estimation (DBE) algorithm, which captures motif transformation probabilities and relies on motif counts from the noisy graph to yield unbiased butterfly estimates. DBE significantly enhances accuracy via reduced communication between vertices and the data curator. Extensive experiments on 14 datasets validate the effectiveness and efficiency of our proposed techniques.

In many real-world scenarios, relationships between two different entities can be naturally represented as bipartite graphs, such as author-paper, user-item, and people-location. Cohesive subgraph search, which aims to find densely connected subgraphs, is a popular research topic on bipartite graphs. While various cohesive subgraph models are proposed on bipartite graphs, none of them consider the temporal dimension, which expresses dynamic changes occurring in cohesive subgraphs over time. In this paper, we propose the first cohesive subgraph model$(\alpha,\ \beta,\ \mathcal{T})$-core on temporal bipartite graphs. Given degree constraints$\alpha$and$\beta$, as well as a time window$\mathcal{T}=[t_{s},t_{e}],(\alpha,\beta,\ \mathcal{T})$-core guarantees that each vertex in the upper or lower layer has at least$\alpha$or$\beta$neighbors, respectively, within the snapshot over the time window$\mathcal{T}$. An intuitive solution to compute the$(\alpha,\ \beta,\ \mathcal{T})$-core is to iteratively remove the vertices that do not satisfy the degree constraints in the snapshot, which suffers from inefficiency and is impractical on large temporal bipartite graphs. Therefore, we turn to index-based methods to enhance query performance. To support efficient arbitrary$(\alpha,\ \beta,\ \mathcal{T})$-core queries, we propose a vertex-partitioning historical index called VH-Index and a time-partitioning historical index called TH-Index. Note that these two indexes need to store$(\alpha,\ \beta,\ \mathcal{T})$-core for each possible combination of$\alpha, \beta$, and$a\mathcal{T}$and incur large construction costs. Therefore, we further propose a temporal intersection index called TH*-Index to strike a balance between the efficiency of query processing and the space cost of the index. We develop both sequential and parallel algorithms for efficiently constructing the temporal-intersection index. Extensive experiments are conducted on 10 real-world temporal bipartite graphs to validate the effectiveness of the$(\alpha,\ \beta,\ \mathcal{T})$-core model and the efficiency of our proposed algorithms.

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

The advancement in location technology and the increase in trajectory data have made trajectory data mining a focal point in the field of spatiotemporal data analysis. Unlike the extensive research focused on the similarity of entire trajectories, this paper delves into subtrajectory similarity within collections containing a large number of trajectories, under a specified trajectory similarity metric. We propose the Top-k Representative Similar Subtrajectory Query problem, with the objective of identifying the top-k representative subtrajectories which are most similar to the query trajectory within a large trajectory set. To ensure diversity in the results, we adopt the concept of representative similarity, where only the subtrajectory with the highest similarity score to the query trajectory is reported, thus avoiding the redundancy in the top-$k$results. To address the challenge of high computational costs, we propose a learning-based framework, leveraging a deep learning model called Representative Similarity Score Estimation (RSSE) to approximate subtrajectory similarity scores efficiently and reduce the candidate set significantly. Empirical evaluations conducted on various real-world datasets substantiate the effectiveness and efficiency of our proposed method.

Supergraph search is a fundamental graph query processing problem. Supergraph search aims to find all data graphs contained in a given query graph based on the subgraph isomorphism. In other words, the goal is to determine if part of the query graph is the same as a smaller data graph. Existing algorithms construct the indices and adopt the filtering-and-verification framework, which is usually computationally expensive and can cause redundant computations. Recently, various learning-based methods have been proposed for a good trade-off between accuracy and efficiency for query processing tasks. However, to our knowledge, no learning-based method is proposed for the supergraph search task. In this paper, we propose the first learning-based method for similarity search on supergraph containment, named Neural Supergraph similarity Search (NSS). NSS first learns the representations for query and data graphs and then efficiently conducts the supergraph search on the representation space, the complexity of which is linear to the number of data graphs. The carefully designed Wasserstein discriminator and reconstruction network enable NSS to capture better the interrelation, structural and label information between and within the query and data graphs. Experiments demonstrate that the NSS is up to 6 orders of magnitude faster than the state-of-the-art exact supergraph search algorithm in query processing and is more accurate than the other learning-based solutions.

Maximal k-plex enumeration is an important problem in graph analysis and can find many real-world applications. A k-plex is a subgraph in which every vertex can miss edges to at most$k$vertices (including itself). Previous studies mainly focus on static graphs. However, in reality, relationships between two entities often occur at some specific timestamps, which can be modeled as temporal graphs. Directly extending the k-plex model may fail to find some critical groups in temporal graphs, which exhibit certain frequent occurring phenomenon. To fill the gap, in this paper, we propose a novel model called$(k,\ l)$-plex, which is a vertex set that exists in no less than$I$timestamps, at each of which the subgraph induced is a$k$-plex. To identify practical results, we introduce the concept of large maximal$(k,\ l)$-plex (MalKLP), i.e., maximal$(k,\ l)$-plex with size no less than a given threshold. In this paper, we conduct the first attempt to propose and investigate the MalKLP enumeration problem, which is proved to be NP-hard. A reasonable baseline method called KLPE-BK is developed by extending the Bron-Kerbosch framework. To overcome the three limitations in KLPE-BK and scale for larger graphs, novel optimized strategies are proposed, including graph reduction, search branch pruning and maximality checking approaches. Finally, we present our optimized algorithm KLPE+ by integrating the techniques proposed. Comprehensive experiments on 8 real-world datasets are conducted to validate the efficiency and scalability of the proposed techniques. Compared with the baseline method, KLPE + can achieve up to two orders of magnitude speedup. A case study is conducted to verify the effectiveness of our model.

Hop-constrained s-t simple path (HC-s-t path) enu-meration is a fundamental problem in graph analysis. Existing solutions for this problem focus on optimizing the processing performance of a single query. However, in practice, it is more often that multiple H C-s-t path queries are issued simultaneously and processed as a batch. Therefore, we study the problem of batch H C-s-t path query processing in this paper and aim to compute the results of all queries concurrently and efficiently as a batch. To achieve this goal, we first propose the concept of H C-s path query which can precisely characterize the common computation among different queries. We then devise a two-phase H C-s path query detection algorithm to identify the common H C-5 path queries for the given H C-s-t path queries. Based on the detected HC-s path queries, we further devise an efficient HC-s-t path enumeration algorithm in which the common computation represented by H C-s path queries are effectively shared. We conduct extensive experiments on real-world graphs and the experimental results demonstrate that our proposed algorithm is efficient and scalable regarding processing multiple HC-s-t path queries in large graphs at billion-scale.

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 ubiquitous smart devices, shared mobility services, such as food delivery, ridesharing and crowdsourced parcel delivery, and the related problems, such as task assignment and route planning have drawn much attention from academia and industry. Specifically, shared mobility services enable one worker to deliver more than one package/passenger together such that their routes can share some common sub-routes. Tardiness (the exceeded time) can harm users' experience and reduce the revenue of workers and platforms, which is not well handled in the existing studies. In this paper, we propose a framework, TrendSharing, to minimize the total tardiness when serving all tasks. In TrendSharing, we first build a flow tree to group tasks together. Then, we propose a concept of trend, which represents a group of tasks with high sharability in the flow tree. Furthermore, we devise a decision factor$\epsilon$-score to properly select the trend from the flow tree. In addition, we devise an indicator k-regret to quantify the likelihood of tardiness for each task and devise a greedy algorithm to conduct task assignment. We observe that the insertion operation that is widely used by existing works has little effect on the objective of minimizing total tardiness. Thus, we adopt a simple yet effective strategy, which will continuously append newly planned routes to the workers' existing routes. Moreover, we design an algorithm to plan a route for the trend with an approximation ratio of 2.5. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches on real datasets.

As a popular data structure, bipartite graph is widely used to model the complex relationships between two types of entities widely in many real world application domains[1]. Detecting cohesive subgraphs, such as biclique, is a fundamental problem in graph analysis[2], [3]. Given a bipartite graph$G$, a subgraph$B=(X,\ Y)$is a biclique if$B$is a complete subgraph.

Ridesharing services, such as Uber or Didi, have attracted considerable attention in recent years due to their positive impact on environmental protection and the economy. Existing studies require quick responses to orders, which lack the flexibility to accommodate longer wait times for better grouping opportunities. In this paper, we address a NP-hard ridesharing problem, called Minimal Extra Time RideSharing (METRS), which balances waiting time and group quality (i.e., detour time) to improve riders' satisfaction. To tackle this problem, we propose a novel approach called WATTER (WAit To be fasTER), which leverages an order pooling management algorithm allowing orders to wait until they can be matched with suitable groups. The key challenge is to customize the extra time threshold for each order by reducing the original optimization objective into a convex function of threshold, thus offering a theoretical guarantee to be optimized efficiently. We model the dispatch process using a Markov Decision Process (MDP) with a carefully designed value function to learn the threshold. Through extensive experiments on three real datasets, we demonstrate the efficiency and effectiveness of our proposed approaches.

Urban traffic flow data is useful in transport ap-plications, playing an important role in various tasks such as road planning, site selection, ad services, etc. However, traffic flow data is the composition of personal driving trajectories, which can reveal sensitive information such as home and work locations, leading to privacy issues. Thus publishing traffic flow data while not disclosing private information remains a challenge for urban managers. To address this challenge, we study the noisy publication of traffic flow data in this paper. The noise is added to the data with respect to the differential privacy paradigm, which ensures data safety but deteriorates its utility. On the other hand, we find that the inherent relations of the flow data inherited from the road network structure can be used to correct data without hurting the privacy property. Hence, we propose post-processing techniques, which exploit the data's inherent relations for corrections over the global and local differentially private traffic flow data, respectively. Extensive experiments on real data show that the proposed post-processing techniques improve the data utility by 29.7%-41.1% and 17.3%-48.6% subjecting to the global and local differential privacy paradigm, respectively.

Unsupervised Outlier Detection (UOD) is an important data mining task. With the advance of deep learning, deep Outlier Detection (OD) has received broad interest. Most deep UOD models are trained exclusively on clean datasets to learn the distribution of the normal data, which requires huge manual efforts to clean the real-world data if possible. Instead of relying on clean datasets, some approaches directly train and detect on unlabeled contaminated datasets, leading to the need for methods that are robust to such challenging conditions. Ensemble methods emerged as a superior solution to enhance model robustness against contaminated training sets. However, the training time is greatly increased by the ensemble mechanism.

The popularity of decentralized finance has drawn attention to liquidity mining (LM). In LM, a user deposits her cryptocurrencies into liquidity pools to provide liquidity for exchanges and earn yields. Different liquidity pools offer varying yields and require different pairs of cryptocurrencies. A user can exchange a cryptocurrency for another with some exchange costs. Thus, an LM solution consists of exchange transactions and deposit transactions, guaranteeing (1) each exchange transaction must exchange one cryptocurrency for another at a specific rate (i.e., the exchange constraint); (2) the amounts of cryptocurrencies deposited in a liquidity pool must exceed the required threshold (i.e., the minimum constraint); (3) each deposit transaction must deposit a specific pair of cryptocurrencies at a certain rate in a liquidity pool (i.e., the deposit constraint); and (4) the cryptocurrencies used in the solution do not exceed the cryptocurrencies that the user has (i.e., the budget constraint). Selecting the most profitable LM solution is challenging due to the vast number of candidate solutions. To address this challenge, we define the yield maximization liquidity mining (YMLM) problem. Given a set of liquidity pools, a set of the user's cryptocurrencies, a set of exchange rates, and an evaluation function, YMLM aims to find an LM solution with maximal yields, satisfying the minimum, exchange, deposit, and budget constraints. We prove that YMLM is NP-hard and cannot be solved by algorithms with constant approximation ratios. To tackle YMLM, we propose two algorithms, namely YMLM\_GD and YMLM\_SK, with parameterized approximation ratios. Extensive experiments on both real and synthetic datasets show that our approaches outperform the baselines in yields.

As the volume and ubiquity of graphs increase, a compact graph representation becomes essential for enabling efficient storage, transfer, and processing of graphs. Given a graph, the graph summarization problem asks for a compact representation that consists of a summary graph and the corrections, such that we can recreate the original graph from the representation exactly. Although this problem has been studied extensively, the existing works either trade summary compactness for efficiency, or vice versa. In particular, a well-known greedy method provides the most compact summary but incurs prohibitive time cost, while the state-of-the-art algorithms with practical overheads are more than 20% behind in summary compactness in our comparison with the greedy method. This paper presents Mags and Mags-DM, two algorithms that aim to bridge the compactness and efficiency in graph summarization. Mags adopts the existing greedy paradigm that provides state-of-the-art compactness, but significantly improves its efficiency with a novel algorithm design. Meanwhile, Mags-DM follows a different paradigm with practical efficiency and overcomes its limitations in compactness. Moreover, both algorithms can support parallel computing environments. We evaluate Mags and Mags-DM on graphs up to billion-scale and demonstrate that they achieve state-of-the-art in both compactness and efficiency, rather than in one of them. Compared with the method that offers state-of-the-art compactness, Mags and Mags-DM have a small difference (< 0.1% and < 2.1%) in compactness. For efficiency, Mags is on average 11.1x and 4.2x faster than the two state-of-the-art algorithms with practical overheads, while Mags-DM can further reduce the running time by 13.4x compared with Mags. This shows that graph summarization algorithms can be made practical while still offering a compact summary.

Bipartite graphs, formed by two vertex layers, arise as a natural fit for modeling the relationships between two groups of entities. In bipartite graphs, common neighborhood computation between two vertices on the same vertex layer is a basic operator, which is easily solvable in general settings. However, it inevitably involves releasing the neighborhood information of vertices, posing a significant privacy risk for users in real-world applications. To protect edge privacy in bipartite graphs, in this paper, we study the problem of estimating the number of common neighbors of two vertices on the same layer under edge local differential privacy (edge LDP). The problem is challenging in the context of edge LDP since each vertex on the opposite layer of the query vertices can potentially be a common neighbor. To obtain efficient and accurate estimates, we propose a multiple-round framework that significantly reduces the candidate pool of common neighbors and enables the query vertices to construct unbiased estimators locally. Furthermore, we improve data utility by incorporating the estimators built from the neighbors of both query vertices and devise privacy budget allocation optimizations. These improve the estimator's robustness and consistency, particularly against query vertices with imbalanced degrees. Extensive experiments on 15 datasets validate the effectiveness and efficiency of our proposed techniques.

We study the historical connectivity query in temporal graphs where edges continuously arrive. Given an arbitrary time window, and two query vertices, the problem aims to identify if two vertices are connected by a path in the snapshot of the window. The state-of-the-art method designs an index based on the two-hop cover, and updating the index is costly when new edges arrive. In this paper, we propose a new framework and design a novel forest-based index for historical connectivity queries. The index enables us to answer queries by searching if two vertices are connected in the forest. We update the index by modifying a forest structure. Our techniques also work for connectivity query processing in a sliding window of temporal graphs. Extensive experiments have been conducted to show the considerable advantages of our approach compared with the state-of-the-art methods in both historical connectivity queries and sliding-window connectivity queries.

We study the problem of missing data imputation, which is a fundamental task in the area of data quality that aims to impute the missing data to achieve the completeness of datasets. Though the recent distribution-modeling-based techniques (e.g., distribution generation and distribution matching) can achieve state-of-the-art performance in terms of imputation accuracy, we notice that (1) they deploy a sophisticated deep learning model that tends to be overfitting for missing data imputation; (2) they directly rely on a global data distribution while overlooking the local information. Driven by the inherent variability in both missing data and missing mechanisms, in this paper, we explore the uncertain nature of this task and aim to address the limitations of existing works by proposing an uNcertainty-driven netwOrk for Missing data Imputation, termed NOMI. NOMI has three key components, i.e., the retrieval module, the neural network gaussian process imputator (NNGPI) and the uncertainty-based calibration module. NOMI~ runs these components sequentially and in an iterative manner to achieve a better imputation performance. Specifically, in the retrieval module, NOMI~ retrieves local neighbors of the incomplete data samples based on the pre-defined similarity metric. Subsequently, we design NNGPI~ that merges the advantages of both the Gaussian Process and the universal approximation capacity of neural networks. NNGPI~ models the uncertainty by learning the posterior distribution over the data to impute missing values while alleviating the overfitting issue. Moreover, we further propose an uncertainty-based calibration module that utilizes the uncertainty of the imputator on its prediction to help the retrieval module obtain more reliable local information, thereby further enhancing the imputation performance. We also demonstrate that our NOMI~ can be reformulated as an instance of the well-known Expectation Maximization (EM) algorithm, highlighting the strong theoretical foundation of our proposed methods. Extensive experiments are conducted over 12 real-world datasets. The results demonstrate the excellent performance of NOMI in terms of both accuracy and efficiency.

Connectivity query processing is a fundamental problem in graph processing. Given an undirected graph and two query vertices, the problem aims to identify whether they are connected via a path. Given frequent edge updates in real graph applications, in this paper, we study connectivity query processing in fully dynamic graphs, where edges are frequently inserted or deleted. A recent solution, called D-tree, maintains a spanning tree for each connected component and applies several heuristics to reduce the depth of the tree. To improve the efficiency, we propose a new spanning-tree-based solution by maintaining a disjoint-set tree simultaneously. By combining the advantages of two trees, we achieve the constant query time complexity and also significantly improve the theoretical running time in both edge insertion and edge deletion. Our performance studies on real large datasets show considerable improvement of our algorithms.

Subgraph matching is a fundamental problem in graph analysis. In recent years, many subgraph matching algorithms have been proposed, making it pressing and challenging to compare their performance and identify their strengths and weaknesses. We observe that (1) The embedding enumeration in the classic filtering-ordering-enumerating framework dominates the overall performance, and thus enhancing the backtracking paradigm is becoming a current research trend; (2) Simply changing the limitation of output size results in a substantial variation in the ranking of different methods, leading to biased performance evaluation; (3) The techniques employed at different stages of subgraph matching interact with each other, making it less feasible to replace and evaluate a single technique in isolation. Therefore, a comprehensive survey and experimental study of subgraph matching is necessary to identify the current trends, ensure unbiasedness, and investigate the potential interactions. In this paper, we comprehensively review the methods in the current trend and experimentally confirm their advantage over prior approaches. We unbiasedly evaluate the performance of these algorithms by using an effective metric, namely embeddings per second. To fully investigate the interactions between various techniques, we select 10 representative techniques for each stage and evaluate all the feasible combinations.

Structural diversity of a vertex refers to the diversity of connections within its neighborhood and has been applied in various fields such as viral marketing and user engagement. The paper studies querying the structural diversity of a vertex for any query time windows in streaming graphs. Existing studies are limited to static graphs which fail to capture vertices' structural diversities in snapshots evolving over time. We design an elegant index structure to significantly reduce the index size compared to the basic approach. We propose an optimized incremental algorithm to update the index for continuous edge arrivals. Extensive experiments on real-world streaming graphs demonstrate the effectiveness of our framework.

The biclique is a fundamental model of bipartite cohesive subgraphs. To analyze a bipartite graph, many existing works seek the maximum biclique, that is, the biclique with the largest number of edges. However, our finding is that the most similar biclique (i.e., the biclique whose vertices are the most similar to each other) can be a good alternative for understanding the network. Using the model, we can detect meaningful communities with high similarity and avoid unnecessary searches based on vertex similarity. In particular, we aim to find (i) local most similar biclique : the biclique that contains a query node q and the similarity between vertices is the highest, and (ii) global most similar biclique : the biclique with the highest similarity between vertices. Despite the NP-hardness of the problems, this paper presents two efficient algorithms, Mosib and Mosib-GloApp. Specifically, our Mosib is an exact algorithm for the most similar biclique search. The algorithm incorporates three novel graph reduction rules that can reduce the size of the bipartite graph while preserving the most similar biclique, as well as two similarity-first search rules that can prioritize the bicliques with high similarity in the search. These techniques can significantly improve the practical efficiency of the algorithm. Meanwhile, our Mosib-GloApp is an approximate algorithm that adopts a novel MinHash-based dividing method, and it can further improve the efficiency of the global most similar biclique search. We experimentally evaluate our algorithms on real-world networks, and show that the most similar biclique models can find meaningful results while being computed efficiently.

Public transportation plays a vital role in mitigating traffic congestion and reducing carbon emissions. The Top-k Nearest Neighbor ( k NN) search in public transportation networks is a fundamental problem in location-based services, which aims to find k nearest objects from a given query point. The traditional method, Dijkstra's algorithm has been employed to tackle the k NN problem, however, it is notably inefficient in processing queries. While other works precompute an index to speed up query processing. However, they are still slow in processing queries. Furthermore, they cannot scale to large graphs due to their reliance on resource-intensive path indexes. To address these limitations, we introduce a novel index-based approach that utilizes a simple yet effective index structure to handle k NN queries with a near-optimal time complexity. The index does not rely on a path index, making it efficient to construct and scalable to large graphs. Extensive experiments are conducted on real-world datasets to demonstrate the efficiency and scalability of our approach. The results show that our approach outperforms existing solutions by up to four orders of magnitude in query processing and two orders of magnitude in index construction.

There are two fundamental problems in regular simple path queries (RSPQs). One is the reachability problem which asks whether there exists a simple path between the source and the target vertex matching the given regular expression, and the other is the enumeration problem which aims to find all the matched simple paths. As an important computing component of graph databases, RSPQs are supported in many graph database query languages such as PGQL and openCypher. However, answering RSPQs is known to be NP-hard, making it challenging to design scalable solutions to support a wide range of expressions. In this paper, we first introduce the class of transitive restricted expression , which covers more than 99% of real-world queries. Then, we propose an efficient algorithm framework to support both reachability and enumeration problems under transitive restricted expression constraints. To boost the performance, we develop novel techniques for reachability detection, the search of candidate vertices, and the reduction of redundant path computation. Extensive experiments demonstrate that our exact method can achieve comparable efficiency to the state-of-the-art approximate approach, and outperforms the state-of-the-art exact methods by up to 2 orders of magnitude.

Community search has aroused widespread interest in the past decades. Among existing solutions, the learning-based models exhibit outstanding performance in terms of accuracy by leveraging labels to 1) train the model for community score learning, and 2) select the optimal threshold for community identification. However, labeled data are not always available in real-world scenarios. To address this notable limitation of learning-based models, we propose a pre-trained graph Trans former based community search framework that uses Zero label (i.e., unsupervised), termed TransZero. TransZero has two key phases, i.e., the offline pre-training phase and the online search phase. Specifically, in the offline pre-training phase, we design an efficient and effective community search graph transformer ( CSGphormer ) to learn node representation. To pre-train CSGphormer without the usage of labels, we introduce two self-supervised losses, i.e., personalization loss and link loss, motivated by the inherent uniqueness of node and graph topology, respectively. In the online search phase, with the representation learned by the pre-trained CSGphormer , we compute the community score without using labels by measuring the similarity of representations between the query nodes and the nodes in the graph. To free the framework from the usage of a label-based threshold, we define a new function named expected score gain to guide the community identification process. Furthermore, we propose two efficient and effective algorithms for the community identification process that run without the usage of labels. Extensive experiments over 10 public datasets illustrate the superior performance of TransZero regarding both accuracy and efficiency.

Given a graph G , a budget k and a misinformation seed set S, Influence Minimization (IMIN) via node blocking aims to find a set of k nodes to be blocked such that the expected spread of S is minimized. This problem finds important applications in suppressing the spread of misinformation and has been extensively studied in the literature. However, existing solutions for IMIN still incur significant computation overhead, especially when k becomes large. In addition, there is still no approximation solution with non-trivial theoretical guarantee for IMIN via node blocking prior to our work. In this paper, we conduct the first attempt to propose algorithms that yield data-dependent approximation guarantees. Based on the Sandwich framework, we first develop submodular and monotonic lower and upper bounds for our non-submodular objective function and prove the computation of proposed bounds is #P-hard. In addition, two advanced sampling methods are proposed to estimate the value of bounding functions. Moreover, we develop two novel martingale-based concentration bounds to reduce the sample complexity and design two non-trivial algorithms that provide (1 - 1/ e - ϵ )-approximate solutions to our bounding functions. Comprehensive experiments on 9 real-world datasets are conducted to validate the efficiency and effectiveness of the proposed techniques. Compared with the state-of-the-art methods, our solutions can achieve up to two orders of magnitude speedup and provide theoretical guarantees for the quality of returned results.

Betweenness centrality (BC), a classic measure which quantifies the importance of a vertex to act as a communication "bridge" between other vertices in the network, is widely used in many practical applications. With the advent of large heterogeneous information networks (HINs) which contain multiple types of vertices and edges like movie or bibliographic networks, it is essential to study BC computation on HINs. However, existing works about BC mainly focus on homogeneous networks. In this paper, we are the first to study a specific type of vertices' BC on HINs, e.g., find which vertices with typeAare important bridges to the communication between other vertices also with typeA?We advocate a meta path-based BC framework on HINs and formalize both coarse-grained and fine-grained BC (cBC and fBC) measures under the framework. We propose a generalized basic algorithm which can apply to computing not only cBC and fBC but also their variants in more complex cases. We develop several optimization strategies to speed up cBC or fBC computation by network compression and breadth-first search directed acyclic graph (BFS DAG) sharing. Experiments on several real-world HINs show the significance of cBC and fBC, and the effectiveness of our proposed optimization strategies.

Top- k Nearest Neighbors ( k NN) problem on road network has numerous applications on location-based services. As direct search using the Dijkstra's algorithm results in a large search space, a plethora of complex-index-based approaches have been proposed to speedup the query processing. However, even with the current state-of-the-art approach, long query processing delays persist, along with significant space overhead and prohibitively long indexing time. In this paper, we depart from the complex index designs prevalent in existing literature and propose a simple index named KNN-Index. With KNN-Index, we can answer a k NN query optimally and progressively with small and size-bounded index. To improve the index construction performance, we propose a bidirectional construction algorithm which can effectively share the common computation during the construction. Theoretical analysis and experimental results on real road networks demonstrate the superiority of KNN-Index over the state-of-the-art approach in query processing performance, index size, and index construction efficiency.

Cohesive subgraph mining is a fundamental problem in bipartite graph analysis. In reality, relationships between two types of entities often occur at some specific timestamps, which can be modeled as a temporal bipartite graph. However, the temporal information is widely neglected by previous studies. Moreover, directly extending the existing models may fail to find some critical groups in temporal bipartite graphs, which appear in a unilateral (i.e., one-layer) form. To fill the gap, in this paper, we propose a novel model, called maximal λ -frequency group (MFG). Given a temporal bipartite graph 𝒢 = (U, V, ℰ ), a vertex set V S ⊆ V is an MFG if i ) there are no less than λ timestamps, at each of which V S can form a ( τ U , τ V )-biclique with some vertices in U at the corresponding snapshot, and ii ) it is maximal. To solve the problem, a filter-and-verification (FilterV) method is proposed based on the Bron-Kerbosch framework, incorporating novel filtering techniques to reduce the search space and array-based strategy to accelerate the frequency and maximality verification. Nevertheless, the cost of frequency verification in each valid candidate set computation and maximality check could limit the scalability of FilterV to larger graphs. Therefore, we further develop a novel verification-free (VFree) approach by leveraging the advanced dynamic counting structure proposed. Theoretically, we prove that VFree can reduce the cost of each valid candidate set computation in FilterV by a factor of O (| V |). Furthermore, VFree can avoid the explicit maximality verification because of the developed search paradigm. Finally, comprehensive experiments on 15 real-world graphs are conducted to demonstrate the efficiency and effectiveness of the proposed techniques and model.

Competitive viral marketing considers the product competition of multiple companies, where each user may adopt one product and propagate the product to other users. Existing studies focus on a traditional seeding strategy where a company only selects seeds from the users with no adopted product to maximize its influence (i.e., the number of users who will adopt its product). However, influential users are often rare, and the gain from traditional seeding will degrade as the number of seeds increases. Therefore, in this paper, we study the promisingcounteringstrategy which is to counter some users who initially use other products s.t. they will turn to adopting the target product and recommending it to others. We propose the problem ofinfluence countering: given a graph, a budgetb, a target companyCt, and a setSof the seeds adopting different companies (where each seed adopts one company), we counterbusers inSwho do not adoptCtto turn to adoptCts.t. the expected number of users who eventually adoptCtin the influence diffusion is maximized. Following existing studies, we formalize the diffusion process by the Multi-Campaigner Independent Cascade model. We prove the influence countering problem is #P-complete and its influence computation is #P-hard. Then, we propose two novel algorithmsMICandMIC+to address the problem. In general,MICestimates seed influence by its empirical average influence in multiple graph samplings, whileMIC+improvesMICby reducing the cost of influence estimation and the required number of samples. Given pre-setεandl, both algorithms return a (1 -ε)-approximate solution with at least 1 -n-lprobability. We also design an index forMIC+to efficiently process graphs that are frequently updated. The experiments on 8 real-world datasets show that our algorithms are efficient in practice while offering strong result quality.

Continuously monitoring structural patterns in streaming graphs is a critical task in many real-time graph-based applications. In this paper, we study the problem of time-constrained continuous subgraph matching (shorted as TCSM) over streaming graphs. Given a query graph Q with timing order constraint and a data graph stream G , TCSM aims to report all incremental matches of Q in G for each update of G , where a match should obey both structure constraint (i.e., isomorphism) and timing order constraint of Q. Although TCSM has a wide range of applications, such as cyber-attack detection and credit card fraud detection, we note that this problem has not been well addressed. The state-of-the-art bears the limitations of high index space cost and intermediate result maintenance cost. In this paper, we propose TC-Match, an effective approach to TCSM. First, we design a space and time cost-effective index CSS, which is essentially a k -partite graph structure where a node corresponds to an edge in G. By carefully creating links between nodes, we can encapsulate into CSS the partial embedding and timing order information between edges in G. We theoretically show that CSS has polynomial space and construction time complexities. Second, based on the property of CSS, we develop an efficient incremental matching algorithm with an effective node merging optimization. Extensive experiments show that TC-Match can achieve up to 3 orders of magnitude query performance improvement over the baseline methods, and meanwhile the memory consumption is reduced by 48.7%-86.7%.

Hypergraphs, which use hyperedges to capture groupwise interactions among different entities, have gained increasing attention recently for their versatility in effectively modeling real-world networks. In this paper, we study the problem of computing hyper-triangles (formed by three fully-connected hyperedges), which is a basic structural unit in hypergraphs. Although existing approaches can be adopted to compute hyper-triangles by exhaustively examining hyperedge combinations, they overlook the structural characteristics distinguishing different hyper-triangle patterns. Consequently, these approaches lack specificity in computing particular hyper-triangle patterns and exhibit low efficiency. In this paper, we unveil a new formation pathway for hyper-triangles, transitioning from hyperedges to hyperwedges before assembling into hyper-triangles, and classify hyper-triangle patterns based on hyperwedges. Leveraging this insight, we introduce a two-step framework to reduce the redundant checking of hyperedge combinations. Under this framework, we propose efficient algorithms for computing a specific pattern of hyper-triangles. Approximate algorithms are also devised to support estimated counting scenarios. Furthermore, we introduce a fine-grained hypergraph clustering coefficient measurement that can reflect diverse properties of hypergraphs based on different hyper-triangle patterns. Extensive experimental evaluations conducted on 11 real-world datasets validate the effectiveness and efficiency of our proposed techniques.

Computing the reachability between two vertices in a graph is a fundamental problem in graph data analysis. Most of the existing works assume that the edges in the graph have no labels, but in many real application scenarios, edges naturally come with edge-labels, and label constraints may be placed on the edges appearing on a valid path between two query vertices. Therefore, we study the label-constrained reachability (LCR) queries in this paper, where we are given a source vertex s , a target vertex t , a label set Δ, and the goal is to check whether there exists any path from s to t such that all the labels of edges on the path belong to Δ. A plethora of methods have been proposed in the literature to support the LCR queries. All these methods take the assumption that the graph is resident in the main memory of a machine. Nevertheless, the graphs in many real application scenarios are generally big and may not reside in memory. In these cases, existing methods suffer from serious scalability problem, i.e., result in huge I/O costs. Motivated by this, in this paper, we study the I/O efficient LCR query problem and aim to efficiently answer the LCR queries when the graph cannot fit in the main memory. To achieve this goal, we propose a reduction-based indexing approach. We introduce two elegant graph reduction operators which aims to reduce the size of the graph loaded in memory while preserving the LCR information among the remaining vertices. With these two operators, we devise an index named LCR-Index and propose algorithms to adaptively construct the index based on the available memory. Equipped with LCR-Index, we can answer a LCR query by only scanning the LCR-Index sequentially. Experiments demonstrate our query processing algorithm can handle graphs with billions of edges.

Shortest path query on road networks is a fundamental problem to support many location-based services and wide variant applications. Contraction Hierarchies(CH) is widely adopted to accelerate the shortest path query by leveraging shortcuts among vertices. However, the state-of-the-art CH construction method named$\mathsf{VCHCons}$suffers from inefficiencies due to their strong reliance on pre-determined vertex order. This leads to the generation of a large number of invalid shortcuts and the limit of parallel processing capability. Motivated by it, in this paper, an innovative CH construction algorithm called$\mathsf{ECHCons}$is devised following an edge-centric paradigm, which addresses the issue of invalid shortcut production by introducing a novel edge-ordering strategy. Furthermore, it optimizes shortcut calculation within a dynamically constructed optimal subgraph, which is significantly smaller than the original network, thus shrinking the traversal space during index construction. To further enhance efficiency and overcome the limitations in parallelism inherent to$\mathsf{VCHCons}$, our approach leverages batch contraction of edges and introduces a well-defined lower bound technique to unlock more efficient parallel computation resources. Our approach provides both theoretical guarantee and practical advancement in CH construction. Extensive and comprehensive experiments are conducted on real road networks. The experimental results demonstrate the effectiveness and efficiency of our proposed approach.

The interactions between structured entities play important roles in a wide range of applications such as chemistry, material science, biology, and medical science. Recently, graph-based methods have been exploited to effectively predict the interactions among structured entities. However, these methods usually only focus on structural information of the entities and are incapable of fully utilizing the interaction information between the entities. In this paper, we propose a Denoising Variational Graph of Graphs Auto-encoder (DVGGA) which follows the graph of graphs framework to capture both structural information in structured entities and interaction information among structured entities. With denoising criterion, DVGGA is able to capture the information from the useful structures of the local graph and address the overfitting issue caused by redundant substructures. Extensive experiments conducted on real-world datasets show that DVGGA outperforms the state-of-the-art structured entity interaction prediction methods.

Being the most cutting-edge generative methods, diffusion methods have shown great advances in wide generation tasks. Among them, graph generation attracts significant research attention for its broad application in real life. In our survey, we systematically and comprehensively review on diffusion-based graph generative methods. We first make a review on three mainstream paradigms of diffusion methods, which are denoising diffusion probabilistic models, score-based genrative models, and stochastic differential equations. Then we further categorize and introduce the latest applications of diffusion models on graphs. In the end, we point out some limitations of current studies and future directions of future explorations.

The mode of$k$-core and its hierarchical decomposition have been applied in many areas, such as sociology, the world wide web, and biology. Algorithms on related studies often need an input value of parameter$k$, while there is no existing solution other than manual selection. In this paper, given a graph and a scoring metric, we aim to find the best value of$k$such that the score of the$k$-core (or$k$-core set) is the highest. The problem is challenging because there are various community scoring metrics and the computation is costly on large datasets. With the well-designed vertex ordering, we propose time-and-space-optimal algorithms to compute the best$k$, which are applicable to most community metrics. As real-world networks are often fast-evolving, we also design a novel framework to maintain the best$k$-core (set) against graph dynamics. We prove the dynamic algorithms are bounded, i.e., the update cost is decided by the changes of input and output. The proposed algorithms can benefit the solutions to$k$-core-related problems and their dynamic counterparts. Extensive experiments are conducted on 10 real-world networks with size up to billion-scale, which validates the efficiency of our algorithms and the effectiveness of the resulting$k$-cores.

Graphs in real-world applications usually evolve constantly presenting dynamic behaviors such as social networks and transportation networks. Hence, dynamic graph embedding has gained much attention recently. In dynamic graphs, both the topology and node attributes could change over time, which pose great challenges for developing effective embedding models. Typically, the evolution process of a dynamic graph can be recorded as a series of snapshots. We observe that the evolution process inherently provides both prior information (previous snapshots) and validation information (the next snapshot). The prior information can be used to fit the evolution process, while the validation information can be used to improve the generalization ability of a graph embedding model. However, existing dynamic graph embedding models only utilize the prior information, but overlook the validation information. To tackle this issue, this paper proposes a novel dynamic graph embedding method via Model-Agnostic Meta-Learning, which utilizes both kinds of information to obtain better graph representation. The extensive experiments on eight real-world datasets demonstrate the superiority of our proposed method over state-of-the-art methods on various graph analysis tasks.

Computing Multi-source Shortest Path query with Assembly points ($\mathsf {MSPA}$) is a fundamental graph problem. The$\mathsf {MSPA}$problem locates a set of assembly points to minimize the overall distance for transporting objects from different sources to a destination, where we can assemble objects at assembly points to reduce the total cost. We prove that the$\mathsf {MSPA}$problem is NP-hard. The intuitive method for computing the optimal set of assembly points and the corresponding set of paths is by Branch-and-Bound. However, the combination of different assembly points is exponential. By analyzing the structure of the path set based on the proposed distance graph, we find that the used paths can be combined into a tree. Hence, by defining the state of subtrees and the state transition equation, we propose a dynamic programming (DP) algorithm by pruning the redundant computation of subtrees. The experiment shows that the DP algorithm can achieve three orders of magnitude speedup in query processing time compared with the optimized Branch-and-Bound algorithm. Moreover, we reduce the transition candidates of the DP algorithm from the entire vertex set to certain neighbors. Extensive experiments are conducted on different types of real-world networks to demonstrate the performance of our DP algorithm.

Finding bicliques is a fundamental problem in bipartite graph analysis, and can find numerous applications. However, previous studies only focus on unsigned bipartite graphs. Signed information, such as friend and enemy, naturally exists in real-world networks. It is critical to leverage signed information to better characterize biclique. To fill this gap, we propose a novel biclique model, named balanced signed biclique, by leveraging the property of balance theory. Specifically, given a signed bipartite graph$G$and two positive integers$\tau _{U}, \tau _{V}$, a subgraph$S=(U_{S},V_{S},E_{S})$of$G$is a balanced signed biclique if$i)$$S$is a biclique without any unstable motif, i.e., unbalanced butterfly, and$ii)$$|U_{S}| \geq \tau _{U}$and$|V_{S}| \geq \tau _{V}$. In this paper, we propose and investigate two important problems, i.e., maximal balanced signed biclique enumeration and maximum balanced signed biclique identification. Due to the unique features of signed bipartite graphs, the previous works cannot be applied to our problems directly. For the enumeration task, to construct a reasonable baseline, we extend the existing biclique enumeration framework for unsigned bipartite graphs and integrate the developed balanced bipartite graph property. To scale for large networks, optimized strategies are proposed to overcome the three limitations in the baseline method. For the identification task, we first propose a baseline method by leveraging the proposed enumeration framework. Moreover, employing novel optimizations, an anchor balanced bipartite graph based search framework is introduced to accelerate the search. Finally, extensive experiments are conducted on 8 real-world datasets to demonstrate the efficiency and effectiveness of the proposed techniques and model.

Despite remarkable advancements in graph contrastive learning techniques, the identification of interdependent relationships when maximizing cross-view mutual information remains a challenging issue, primarily due to the complexity of graph topology. In this study, we propose to formulate cross-view interdependence from the innovative perspective of information flow. Accordingly, IDEAL, a simple yet effective framework, is proposed for interdependence-adaptive graph contrastive learning. Compared with existing methods, IDEAL concurrently addresses same-node and distinct-node interdependence, circumvents the reliance on additional distribution mining techniques, and is augmentation-aware. Besides, the objective of IDEAL takes advantage of both contrastive and generative learning objectives and is thus capable of learning a uniform embedding distribution while retaining essential semantic information. The effectiveness of IDEAL is validated by extensive empirical evidence. It consistently outperforms state-of-the-art self-supervised methods by considerable margins across seven benchmark datasets with diverse scales and properties and, at the same time, showcases promising training efficiency.

In this paper, we study the problem of maximal biclique enumeration on large signed bipartite graphs. Given a signed bipartite graph$G=(U,V,E,s)$, a parameter$\theta \in [0.5, 1.0]$, our goal is to efficiently enumerate all maximal$\theta$-bicliques in$G$, where a maximal$\theta$-biclique$B(L,R)$is a complete subgraph of$G$with (1) the proportion of positive neighbors for each vertex in$B$is at least$\theta$, and (2)$B$is not contained in another biclique$B^{\prime }$, while$B^{\prime }$also satisfies (1). This problem has many applications, such as biclustering for genes, recommendation of similar groups, collaboration in communities, etc. However, it is computationally challenging due to its #P-completeness. Besides, we prove that even determining the maximality of a$\theta$-biclique is NP-hard. To the best of our knowledge, there is no efficient and scalable solution to this problem in the literature. In this paper, we first propose a branch-and-bound framework, namely${\sf MSiBE}$, which enumerates all maximal$\theta$-bicliques in a depth-first manner. Then, we develop three effective optimizations to improve the performance of${\sf MSiBE}$. (1) The local information of each search space is utilized to enhance the pruning capacity. (2) When expanding the partial biclique, we always focus on the side with fewer candidates first, by which fruitless search branches can be skipped early. (3) We implement${\sf MSiBE}$with efficient array reordering techniques and set intersection strategy. To further accelerate the computation, we introduce useful graph reduction techniques. Comprehensive performance studies on 10 real datasets demonstrate that our proposals can significantly outperform the baseline methods by up to 3 orders of magnitude.

Supergraph search is a fundamental graph query processing problem. Supergraph search aims to find all data graphs contained in a given query graph based on the subgraph isomorphism. Existing algorithms construct the indices and adopt thefiltering-and-verificationframework which is usually computationally expensive and can cause redundant computations. Recently, various learning-based methods have been proposed for a good trade-off between accuracy and efficiency for query processing tasks. However, to the best of our knowledge, there is no learning-based method proposed for the supergraph search task. In this paper, we propose the first learning-based method for similarity search on supergraph containment, named Neural Supergraph similarity Search (NSS).NSSfirst learns the representations for query and data graphs and then efficiently conducts the supergraph search on the representation space whose complexity is linear to the number of data graphs. The carefully designed Wasserstein discriminator and reconstruction network enableNSSto better capture the interrelation, structural and label information between and within the query and data graphs. Experiments demonstrate that theNSSis up to 6 orders of magnitude faster than the state-of-the-art exact supergraph search algorithm in terms of query processing and more accurate compared to the other learning-based solutions.

With the rapid development of mobile Internet technology, on-demand car-hailing services have become essential for people's daily commuting. Order dispatch is a critical problem in on-demand car-hailing services. However, in most existing works, the service provider is asked to set a unified pick-up distance to prevent long waiting time for requesters. Indeed, different requesters have different tolerance for pick-up distance, and some requesters may accept longer pick-ups if offered discounts for payment. Regarding this fact, we formulate discount-based order dispatch as a coupling of two subproblems, discount determination and order dispatch, aiming to dispatch more orders and thereby more platform profits. We propose customized methods to solve the problems for shared and non-shared mobility services, respectively. We also conduct extensive experiments to evaluate the effectiveness and efficiency of our proposed methods on a real dataset, which shows that our methods can achieve 170% improvements in non-shard services and 43% improvements in ridesharing services on average in terms of attained profit compared to the widely adopted baselines.

The requirement for appropriate ways to measure the similarity between data objects is a common but vital task in various domains, such as data mining, machine learning and so on. Driven by abundant real-world applications, many well-known similarity (distance) metrics are proposed to measure the pairwise similarity of data pairs, e.g., graph edit distance for graphs and dynamic time warping for time series. However, many similarity metrics suffer from the high time complexity. More specifically, most of the well-known similarity metrics often need quadratic time or even much more time to compute the ground truth similarity and some of them are proven to be NP-hard. With the development of deep learning techniques, there is an emerging research trend on the learning for similarity computation on various data types in the field of database (DB) and data mining, which is quite different with the metric learning studies in the machine learning (ML) literature. Specifically, the studies in the ML focus on the learning for semantic similarity in specific tasks, which is implicitly indicated by the training data, on the data in the feature space. While the studies in the DB literature usually consider the learning for well-defined similarity metrics (e.g., graph edit distance) on the data objects (e.g., graphs), such that it can benefit the similarity computation on data in terms of multiple aspects, such as computation time, metric quality and search heuristic, and the learned representation of data can also be naturally fed to downstream tasks. This survey paper provides a comprehensive review of similarity computation learning on several data types, including set, sequence and graph. Moreover, we first classify the learning-based approaches in terms of their learning target into three categories, i.e., similarity learning, cost matrix learning and search heuristic learning. Then we detail some representative approaches for each category on every data type, and analyze some key features that are utilized by these approaches. Finally, we discuss some challenges and future directions towards the learning for similarity learning on these data types.

Graph Neural Networks (GNNs) with data augmentation obtain promising results among existing solutions for graph classification. Mixup-based augmentation methods for graph classification have already achieved state-of-the-art performance. However, existing mixup-based augmentation methods either operate in the input space and thus face the challenge of balancing efficiency and accuracy, or directly conduct mixup in the latent space without similarity guarantee, thus leading to lacking semantic validity and limited performance. To address these limitations, this paper proposes$\mathcal {G}$-MixCon, a novel framework leveraging the strengths ofMixup-based augmentation and supervisedContrastive learning (SCL). To the best of our knowledge, this is the first attempt to develop an SCL-based approach for learning graph representations. Specifically, the mixup-based strategy within the latent space named$GDA_{gl}$and$GDA_{nl}$are proposed, which efficiently conduct linear interpolation between views of the node or graph level. Furthermore, we design a dual-objective loss function namedSupMixConthat can consider both the consistency among graphs and the distances between the original and augmented graph.SupMixConcan guide the training process for SCL in$\mathcal {G}$-MixCon while achieving a similarity guarantee. Comprehensive experiments are conducted on various real-world datasets, the results show that$\mathcal {G}$-MixCon demonstrably enhances performance, achieving an average accuracy increment of 6.24%, and significantly increases the robustness of GNNs against noisy labels.

As a fundamental graph problem, community search is applied in various areas, e.g., social networks, the world wide web, and biology. A common requirement from real applications is to return a community with a bounded size while most existing solutions do not constrain community size. Recent studies on size-constrained community search still have some critical issues, e.g., the existence of a better cohesiveness objective, some queries returning empty results, and inefficiency on partial queries. Thus, in this paper, we study the size-constrained truss community search (STCS). Given a graph$G$, a query vertex$q$, and size constraint$[l,h]$, the STCS problem aims to find a subgraph containing$q$with the largest min-support among all connected subgraphs having at least$l$and at most$h$vertices. We prove the STCS problem is NP-hard and APX-hard unless P = NP. An effective heuristic is proposed to quickly find a high-quality initial result. Then, a branch and bound algorithm is introduced to find the exact result, with novel optimizations, e.g., budget-cost-based bounding and branching strategies. Extensive experiments verify that the community quality returned by our algorithm is better and our algorithm is faster by up to 5 orders of magnitude, compared with the state-of-the-art.

Set intersection is a fundamental operation in many applications, such as common neighbor computation in graph-based algorithms, set similarity computation, item recommendation, etc. In the literature, many set intersection methods are proposed. We observe that the state-of-the-art algorithm${\sf RCode}$bears several limitations, such as high index time complexity, inefficient for large-sized sets, and not friendly to the generic set intersection. In this paper, we introduce theBucket Signature forSet(${\sf BigSet}$), an efficient generic set intersection algorithm.${\sf BigSet}$consists of two phases, namely the preprocessing phase and the query phase. In the preprocessing phase,${\sf BigSet}$partitions the elements of a record into$O(2^{k})$buckets and uses a bitmap to indicate the status of the buckets where$n$is the record length and$k$is the number of bits in the signature. In the query phase,${\sf BigSet}$calculates the results using a candidate generating-and-verification framework. Specifically, a set of candidate elements is identified as those falling in the same buckets. Then, for each bucket,${\sf BigSet}$collects the common elements using a merge-based method. To improve the performance, we introduce two optimizations, including bucket sharing and size-aware signature construction techniques. We conduct experiments on 10 real graph datasets and 5 real generic set datasets to evaluate the performance of our proposals. The experiment results show that${\sf BigSet}$is 20× faster than the leading generic set intersection algorithms. Besides it outperforms the${\sf RCode}$with 5× speedup, and while uses up to 8× less memory.

Hypergraphs are a generalisation of graphs in which a hyperedge can connect any number of vertices. It can describe n-ary relationships and high-order information among entities compared to conventional graphs. In this paper, we study the fundamental problem of subgraph matching on hypergraphs (i.e., subhypergraph matching). Existing methods directly extend sub-graph matching algorithms to the case of hypergraphs. However, this approach delays hyperedge verification and underutilises the high-order information in hypergraphs, which leads to large search space and high enumeration costs. Furthermore, with the growing size of hypergraphs, it is becoming hard to compute subhypergraph matching sequentially. Thus, we propose an efficient and parallel subhypergraph matching system, HGMatch, to handle subhypergraph matching in massive hypergraphs. We propose a novel match-by-hyperedge framework to utilise high-order information in hypergraphs and use set operations for efficient candidate generation. Moreover, we develop an optimised parallel execution engine in HGMatch based on the dataflow model, which features a task-based scheduler and fine-grained dynamic work stealing to achieve bounded memory execution and better load balancing. Experimental evaluation on 10 real-world datasets shows that HGMatch outperforms the extended version of the state-of-the-art subgraph matching algorithms (CFL, DAF, CECI, and RapidMatch) by orders of magnitude when using a single thread, and achieves almost linear scalability when the number of threads increases.

Information cascade in online social networks can be rather negative, e.g., the spread of rumors may trigger panic. To limit the influence of misinformation in an effective and efficient manner, the influence minimization (IMIN) problem is studied in the literature: given a graph G and a seed set S, blocking at most b vertices such that the influence spread of the seed set is minimized. In this paper, we are the first to prove the IMIN problem is NP-hard and hard to approximate. Due to the hardness of the problem, existing works resort to greedy solutions and use Monte-Carlo Simulations to solve the problem. However, they are cost-prohibitive on large graphs since they have to enumerate all the candidate blockers and compute the decrease of expected spread when blocking each of them. To improve the efficiency, we propose the AdvancedGreedy algorithm (AG) based on a new graph sampling technique that applies the dominator tree structure, which can compute the decrease of the expected spread of all candidate blockers at once. Besides, we further propose the GreedyReplace algorithm (GR) by considering the relationships among candidate blockers. Extensive experiments on 8 real-life graphs demonstrate that our AG and GR algorithms are significantly faster than the state-of-the-art by up to 6 orders of magnitude, and GR can achieve better effectiveness with its time cost close to AG.

Biclique percolation community (BPC) search is a fundamental problem in bipartite graph analysis and have many applications. Existing online approach has to enumerate all the maximal bicliques and compute the results based on these bicliques. Considering the large number of maximal bicliques in real graphs and the high frequency of BPC search requests issued in real applications, existing approach is cost prohibitive to obtain the result. Motivated by this, we devise an index-based (BPC-Index) approach to address the problem. Based on the index, we can obtain the result in near-optimal time with well-bounded index space. We further devise an efficient index construction algorithm. Moreover, we also extend our indexing method to address the personalized BPC search problem, which is one of the most common variants of BPC search. We conduct extensive experiments on 10 real bipartite graphs, and the experimental results demonstrate the effectiveness of the BPC model, and the efficiency of our BPC search algorithms and index construction algorithms. Remarkably, our approach can achieve up to 8 orders of magnitude speedup compared to the existing online approach.

Data collection is indispensable for spatial crowd-sourcing services, such as resource allocation, policymaking, and scientific explorations. However, privacy issues make it challenging for users to share their information unless receiving sufficient compensation. Differential Privacy (DP) is a promising mechanism to release helpful information while protecting individuals’ privacy. However, most DP mechanisms only consider a fixed compensation for each user’s privacy loss. In this paper, we design a task assignment scheme that allows workers to dynamically improve their utility with dynamic distance privacy leakage. Specifically, we propose two solutions to improve the total utility of task assignment results, namely Private Utility Conflict-Elimination (PUCE) approach and Private Game Theory (PGT) approach, respectively. We prove that PUCE achieves higher utility than the state-of-the-art works. We demonstrate the efficiency and effectiveness of our PUCE and PGT approaches on both real and synthetic data sets compared with the recent distance-based approach, Private Distance Conflict-Elimination (PDCE). PUCE is always better than PDCE slightly. PGT is 50% to 63% faster than PDCE and can improve 16% utility on average when worker range is large enough.

A large number of studies on Graph Outlier Detection (GOD) have emerged in recent years due to its wide applications, in which Unsupervised Node Outlier Detection (UNOD) on attributed networks is an important area. UNOD focuses on detecting two kinds of typical outliers in graphs: the structural outlier and the contextual outlier. Most existing works conduct experiments based on datasets with injected outliers. However, we find that the most widely-used outlier injection approach has a serious data leakage issue. By only utilizing such data leakage, a simple approach can achieve state-of-the-art performance in detecting outliers. In addition, we observe that existing algorithms have a performance drop with the mitigated data leakage issue. The other major issue is on balanced detection performance between the two types of outliers, which has not been considered by existing studies.In this paper, we analyze the cause of the data leakage issue in depth since the injection approach is a building block to advance UNOD. Moreover, we devise a novel variance-based model to detect structural outliers, which outperforms existing algorithms significantly and is more robust at kinds of injection settings. On top of this, we propose a new framework, Variance-based Graph Outlier Detection (VGOD), which combines our variance-based model and attribute reconstruction model to detect outliers in a balanced way. Finally, we conduct extensive experiments to demonstrate the effectiveness and efficiency of VGOD. The results on 5 real-world datasets validate that VGOD achieves not only the best performance in detecting outliers but also a balanced detection performance between structural and contextual outliers.

As a result of decades of studies, a broad spectrum of graph algorithms have been developed for graph analytics, including clustering, centrality, traversal, matching, mining, etc. However, the majority of recent graph processing frameworks only focus on a handful of fix-point graph algorithms such as breadth-first search, PageRank, shortest path, etc. It leaves the distributed computation of a large variety of graph algorithms suffering from low efficiency, limited expressiveness, or high implementation complexity with existing frameworks.In this paper, we propose Flash, a framework for programming distributed graph processing algorithms, which achieves good expressiveness, productivity and efficiency at the same time. Thanks to its high-level interface, Flash allows users to implement complex distributed graph algorithms with high performance with only a few lines of code. We have implemented 72 graph algorithms for 49 different problems in Flash. In further evaluations, we found that Flash beats other state-of-the-art graph processing frameworks with the speedups of up to 2 orders of magnitudes while takes up to 92% less lines of code.

Vertex engagement has extraordinary significance for social resilience and network stability. There have been lots of existing work studying this fundamental problem in pairwise graphs, but in the more generalized hypergraphs, it has not been well explored, due to the great challenges of sparsity, complex connectivity and dynamicity of hypergraphs. In this work, we initialize the study of the vertex engagement problem in hypergraphs. Based on the observation that the engagement of vertices in hypergraphs needs to consider two critical parameters, group engagement and neighbor engagement, we propose a vertex engagement model integrating the merits of these two measures, called constrained core, to address the ineffectiveness and incomprehensiveness caused by just using a single engagement factor. By giving an algorithm for the constrained core decomposition, we show that the constrained core number of vertices can be computed in linear time. Furthermore, by showing a localized property of contained core, efficient maintenance algorithms for updating the constrained core number of vertices in dynamic hypergraphs are proposed, to avoid the large amount of redundant computations caused by the decomposition from scratch. Extensive experiments conducted on real-world hypergraphs well exhibit the effectiveness of our model and the efficiency of the proposed algorithms.

The feedback vertex set is one of 21 Np-complete problems proposed by Karp, aiming at breaking all cycles in a given graph. It could be used in numerous areas, e.g., program analysis, database systems. In reality, users are concerned the cycles with constraints, e.g., the cycles with a hop constraint. For instance, in the E-commerce networks, the fraud detection team would discard cycles with a high number of hops since they are less relevant and grow exponentially in size. Thus, it is quite reasonable to investigate the feedback vertex set problem with hop-constrained cycles, namely hop-constrained cycle cover problem. It is concerned with determining a vertex set that covers all hop-constrained cycles in a given directed graph. A common method is to use a bottom-up algorithm, where it iteratively selects cover vertices into the result set. Based on this paradigm, the existing works mainly focus on the vertices orders and several heuristic strategies. In this paper, a totally opposite cover process top-down is proposed and bounds are presented on it. Surprisingly, both theoretical and practical performance are improved. On the theoretical side, this work is the first to achieve O(k•n•m) time complexity, whereas the state-of-the-art method achieves time complexity of O(nk).1On the practical level, the proposed algorithm, namely TDB++, outperforms the state-of-the-art by 2 to 3 orders of magnitude on average while preserving the minimal property. As a result, the method in this paper outperforms the state-of-the-art approaches in terms of both running time and theoretical time complexity. The hop-constrained cycle cover problem on billion-scale networks has been solved with a minimal2cover set for k > 3.

One of the fundamental concept in the graph-related problem is the shortest path distance. This problem is widely studied for decades, and has numerous real-life applications. Nevertheless, quality constraints are naturally associated with edges. For instance, finding the distance between two vertices along valid edges (i.e., edges that satisfy a given quality constraint) is also critical. To fill this research gap, we investigate this vital problem, i.e., the quality constraint shortest distance problems. An efficient index structure is proposed based on 2-hop labeling approaches. By using a path dominance relationship into both quality and length information, it is demonstrated that the new index could ensure the minimal property. To further speed up the performance, we present an efficient query processing algorithm. Extensive experimental studies over real-life datasets demonstrates efficiency and effectiveness of our techniques.

Network alignment task, which aims to identify corresponding nodes in different networks, is of great significance for many subsequent applications. Without the need for labeled anchor links, unsupervised alignment methods have been attracting more and more attention. However, the topological consistency assumptions defined by existing methods are generally low-order and less accurate because only the edge-indiscriminative topological pattern is considered, which is especially risky in an unsupervised setting. To reposition the focus of the alignment process from low-order to higher-order topological consistency, in this paper, we propose a fully unsupervised network alignment framework named HTC. The proposed higher-order topological consistency is formulated based on edge orbits, which is merged into the information aggregation process of a graph convolutional network so that the alignment consistencies are transformed into the similarity of node embeddings. Furthermore, the encoder is trained to be multi-orbit-aware and then is refined to identify more trusted anchor links. Node correspondence is comprehensively evaluated by integrating all different orders of consistency. In addition to sound theoretical analysis, the superiority of the proposed method is also empirically demonstrated through extensive experimental evaluation. On three pairs of real-world datasets and two pairs of synthetic datasets, our HTC consistently outperforms a wide variety of unsupervised and supervised methods with the least or comparable time consumption. It also exhibits robustness to structural noise as a result of our multiorbit-aware training mechanism.

Maximum biclique identification, which aims to find the biclique with the largest size, can find a wide spectrum of applications in different domains, such as E-Commerce, healthcare and bioinformatics. However, the previous studies mainly focus on unsigned bipartite graphs. The signed information naturally exists in real applications, such as like and dislike. The neglect of signed information may fail to discover the inherent properties of networks. In this paper, we propose a novel model, named signed (k,l)-biclique (SKLB), by enforcing constraints over the number of positive and negative connections. Specifically, given a signed bipartite graph and two positive integers k,l, SKLB is a biclique, where each vertex has no less than k positive neighbors and no more than l negative neighbors. We prove the problem of finding the maximum signed (k,l)-biclique (MaxSKLB) is NP-hard. Moreover, we show that the problem is still NP-hard, even if the input graph is a biclique itself. A baseline algorithm is first presented through biclique enumeration, which tries to find the MaxSKLB for each encountered biclique and return the largest one. However, considering that the extraction of MaxSKLB from a biclique is still NP-hard, a greedy strategy is developed to accelerate the processing with competitive result. Furthermore, to efficiently handle large graphs, we optimize the algorithm from different perspectives, including unnecessary search branches and unpromising vertices filtering. Finally, comprehensive experiments are conducted over 10 graphs to validate the efficiency and effectiveness of proposed techniques and model.

Shortest path counting computes the number of shortest paths between two vertices on a graph, which can be used in the applications such as social network search and POI (Point of Interest) recommendation. The state-of-the-art approach leverages index to speed up the query processing. However, this approach incurs not only significant space overheads but also prohibitive indexing time, which makes it inapplicable to handle such queries on large graphs. Motivated by this, in this paper, we aim to propose a new solution to scale up the shortest path counting. To achieve this goal, we first propose a novel size-tunable indexing framework, which allows users to tune the index space consumption based on their requirements for query processing efficiency and available memory. Based on the size-tunable indexing framework, we devise a new parallel paradigm to accelerate index construction. We conduct experiments on 15 real graphs and the experimental results demonstrate that our new approach significantly outperforms the state-of-the-art approach regarding the index space cost and index construction cost, and is able to handle billion-scale graphs that the state-of-the-art approach cannot process with less than 5 milliseconds query processing time on all test cases.

Logical queries on Knowledge Graphs (KGs) is a fundamental sub-task of knowledge graph reasoning. A promising paradigm for answering logical queries, recently, has been proposed based on versatile deep learning techniques. In this line, the query is first broken down into a series of first-order logical predicates, and then both the query and knowledge graph entities are jointly encoded in the same embedding space. Some approaches are able to support the full range of traditional First-Order Logic (FOL) operations for complex queries in real-world scenarios, while others have attempted to create a new combination of FOL operations by replacing the negation operation with the difference operation due to the poor performance of the negation operation. Our empirical observations show that the difference operator is more effective for multi-hop reasoning, while the negation operator is better suited for use as the final operation in the query, particularly in single-hop settings. In addition, other fundamental limitations such as linear transformation assumption for negation operator and the fixed-lossy problem for difference operator further degrade the performance of these methods. In light of these, we propose the HaLk, a holistic approach for answering logical queries that, to our knowledge, is the first to support a full set of logical operators in a unified end-to-end framework. In this approach, we propose specific neural models for each operator by considering their own intrinsic properties, based on which HaLk effectively mitigates the cascading error of projection and negation operators as well as delicately provides closed-formed solutions for difference operator. Extensive experimental results on three datasets demonstrate that HaLk outperforms all competitors and achieves up to 32% improvement in accuracy.

Hop-constrained s-t simple path (k-st path) enumeration is a fundamental problem in graph databases and plays an important role in many real-world applications. Given a dynamic graph G, a source-target pair s-t, and a hop constraint k, we aim to efficiently compute k-st paths: list all simple paths within length k from s to t, and then continuously maintain the results against edge updates. Although the k-st path enumeration has been well studied in static setting, the existing works on static graphs cannot be applied or adapted to handle dynamic graphs efficiently. To address the challenges on dynamic computation, we propose a partial path-based index structure and an efficient enumeration algorithm based on the index. We also propose several well-designed techniques to efficiently maintain the index and locate the affected results with graph updates. Comprehensive experiments verify that our proposed CPEupdatealgorithm outperforms the state-of-the-art methods by up to 4 orders of magnitude on dynamic graphs. The experiment results also show that the time cost of our initialization step CPEstartup(including index construction) is similar to the state-of-the-art static method.

Quantifying node importance on engagement dynamics is critical to support network stability. We can motivate or retain the users in a social platform according to their importance s.t. the network is more sustainable. Existing studies validate that the coreness of a node is the "best practice" on network topology to estimate the engagement of the node. In this paper, the importance of a node is the effect on the engagement of other nodes when its engagement is strengthened or weakened. Specifically, the importance of a node is quantified via two novel concepts: the anchor power to measure the engagement effect of node strengthening (i.e., the overall coreness gain) and the collapse power to measure the engagement effect of node weakening (i.e., the overall coreness loss). We find the computation of the two concepts can be naturally integrated into a shell component-based framework, and propose a unified static algorithm to compute both the anchored and collapsed followers. For evolving networks, efficient maintenance techniques are designed to update the follower sets of each node, which is faster than redoing the static algorithm by around 3 orders of magnitude. Extensive experiments on real-life data demonstrate the effectiveness of our model and the efficiency of our algorithms.

Abstract In the real world, road networks with weight and label on edges can be applied in several application domains. The shortest path query with label restrictions has been receiving increasing attention recently. To efficiently answer such kind of queries, a novel index, namely Contraction Hierarchies with Label Restrictions (CHLR), is proposed in the literature. However, existing studies mainly focus on the static road networks and do not support the CHLR maintenance when the road networks are dynamically changed. Motivated by this, in this paper, we investigate the CHLR maintenance problem in dynamic road networks. We first devise a baseline approach to update CHLR by recomputing the potential affected shortcuts. However, many shortcuts recomputed in baseline do not change in fact, which leads to unnecessary overhead of the baseline. To overcome the drawbacks of baseline, we further propose a novel CHLR maintenance algorithm which can only travel little shortcuts through an update propagate chain with accuracy guarantee. Moreover, an optimization strategy is presented to further improve the efficiency of index maintenance. Considering the frequency of edge changes, we also propose a batch index maintenance algorithm to handle batch edge changes which can process a large number of edge changes at once. Furthermore, a parallel method is proposed to further accelerate calculations. Extensive and comprehensive experiments are conducted on real road networks. The experimental results demonstrate the efficiency and effectiveness of our proposed algorithms.

Graphs have been widely used in real-world applications, in which investigating relations between vertices is an important task. In this paper, we study the problem of generating the k-hop-constrained s-t simple path graph, i.e., the subgraph consisting of all simple paths from vertex s to vertex t of length no larger than k. To our best knowledge, we are the first to formalize this problem and prove its NP-hardness on directed graphs. To tackle this challenging problem, we propose an efficient algorithm namedEVE, which exploits the paradigm of edge-wise examination rather than exhaustively enumerating all paths. Powered by essential vertices appearing in all simple paths between vertex pairs,EVE distinguishes the edges that are definitely (or not) contained in the desired simple path graph, producing a tight upper-bound graph in the time cost O(k2|E|). Each remaining undetermined edge is further verified to deliver the exact answer. Extensive experiments are conducted on 15 real networks. The results show thatEVE significantly outperforms all baselines by several orders of magnitude. Moreover, by takingEVE as a built-in block, state-of-the-art for hop-constrained simple path enumeration can be accelerated by up to an order of magnitude.

In this paper, we study the k-clique densest subgraph problem, which detects the subgraph that maximizes the ratio between the number of k-cliques and the number of vertices in it. The problem has been extensively studied in the literature and has many applications in a wide range of fields such as biology and finance. Existing solutions rely heavily on repeatedly computing all the k-cliques, which are not scalable to handle large k values on large-scale graphs. In this paper, by adapting the idea of "pivoting", we propose the SCT*-Index to compactly organize the k-cliques. Based on the SCT*-Index, our SCTL algorithm can directly obtain the k-cliques from the index and efficiently achieve near-optimal approximation. To further improve SCTL, we propose SCTL* that includes novel graph reductions and batch-processing optimizations to reduce the search space and decrease the number of visited k-cliques, respectively. As evaluated in our experiments, SCTL* significantly outperform existing approaches by up to two orders of magnitude. In addition, we propose a sampling-based approximate algorithm that can provide reasonable approximations for any k value on billion-scale graphs. Extensive experiments on 12 real-world graphs validate both the efficiency and effectiveness of the proposed techniques.

Machine-generated data is rapidly growing and poses challenges for data-intensive systems, especially as the growth of data outpaces the growth of storage space. To cope with the storage issue, compression plays a critical role in storage engines, particularly for data-intensive applications, where a high compression ratio and efficient random access are essential. However, existing compression techniques tend to focus on general-purpose and data block approaches, but overlook the inherent structure of machine-generated data and hence result in low compression ratios or limited lookup efficiency. To address these limitations, we introduce the Pattern-Based Compression (PBC) algorithm, which specifically targets patterns in machine-generated data to achieve Pareto-optimality in most cases. Unlike traditional data block-based methods, PBC compresses data on a per-record basis, facilitating rapid random access. Our experimental evaluation demonstrates that PBC, on average, achieves a compression ratio twice as high as the state-of-the-art techniques while maintaining competitive compression and decompression speeds. We also integrate PBC to a production database system and achieve improvements on both comparison ratio and throughput.

Similar subtrajectory search is a finer-grained operator that can better capture the similarities between one query trajectory and a portion of a data trajectory than the traditional similar trajectory search, which requires that the two checking trajectories are similar in their entirety. Many real applications (e.g., trajectory clustering and trajectory join) utilize similar subtrajectory search as a basic operator. It is considered that the time complexity is O ( mn 2 ) for exact algorithms to solve the similar subtrajectory search problem under most trajectory distance functions in the existing studies, where m is the length of the query trajectory and n is the length of the data trajectory. In this paper, to the best of our knowledge, we are the first to propose an exact algorithm to solve the similar subtrajectory search problem in O ( mn ) time for most of widely used trajectory distance functions (e.g., WED, DTW, ERP, EDR and Frechet distance). Through extensive experiments on three real datasets, we demonstrate the efficiency and effectiveness of our proposed algorithms.

The payment channel network (PCN) is a promising solution to increase the throughput of blockchains. However, unidirectional transactions can deplete a user's deposits in a payment channel (PC), reducing the success ratio of transactions (SRoT). To address this depletion issue, rebalance protocols are used to shift tokens from well-deposited PCs to under-deposited PCs. To improve SRoT, it is beneficial to increase the balance of a PC with a lower balance and a higher weight (i.e., more transaction executions rely on the PC). In this paper, we define the utility of a transaction and the utility-aware rebalance (UAR) problem. The utility of a transaction is proportional to the weight of the PC and the amount of the transaction, and inversely proportional to the balance of the receiver. To maximize the effect of improving SRoT, UAR aims to find a set of transactions with maximized utilities, satisfying the budget and conservation constraints. The budget constraint limits the number of tokens shifted in a PC. The conservation constraint requires that the number of tokens each user sends equals the number of tokens received. We prove that UAR is NP-hard and cannot be approximately solved with a constant ratio. Thus, we propose two heuristic algorithms, namely Circuit Greedy and UAR_DC. Extensive experiments show that our approaches outperform the existing approach by at least 3.16 times in terms of utilities.

Clique is one of the most fundamental models for cohesive subgraph mining in network analysis. Existing clique model mainly focuses on unsigned networks. However, in real world, many applications are modeled as signed networks with positive and negative edges. As the signed networks hold their own properties different from the unsigned networks, the existing clique model is inapplicable for the signed networks. Motivated by this, we propose the balanced clique model that considers the most fundamental and dominant theory, structural balance theory, for signed networks. Following the balanced clique model, we study themaximalbalancedcliqueenumeration problem (${\mathsf {MBCE}}$) which computes all the maximal balanced cliques in a given signed network. Moreover, in some applications, users prefer a unique and representative balanced clique with maximum size rather than all balanced cliques. Thus, we also study themaximumbalancedcliquesearch problem (${\mathsf {MBCS}}$) which computes the balanced clique with maximum size. We show that${\mathsf {MBCE}}$problem and${\mathsf {MBCS}}$problem are both NP-Hard. For the${\mathsf {MBCE}}$problem, a straightforward solution is to treat the signed network as two unsigned networks and leverage the off-the-shelf techniques for unsigned networks. However, such a solution is inefficient for large signed networks. To address this problem, in this paper, we first propose a new maximal balanced clique enumeration algorithm by exploiting the unique properties of signed networks. Based on the new proposed algorithm, we devise two optimization strategies to further improve the efficiency of the enumeration. For the${\mathsf {MBCS}}$problem, we first propose a baseline solution. To overcome the huge search space problem of the baseline solution, we propose a new search framework based on search space partition. To further improve the efficiency of the new framework, we propose multiple optimization strategies regarding to redundant search branches and invalid candidates. We conduct extensive experiments on large real datasets. The experimental results demonstrate the efficiency, effectiveness and scalability of our proposed algorithms for${\mathsf {MBCE}}$problem and${\mathsf {MBCS}}$problem.

Multi-task Learning (MTL), which involves the simultaneous learning of multiple tasks, can achieve better performance than learning each task independently. It has achieved great success in various applications, ranging from Computer Vision (CV) to Natural Language Processing (NLP). In MTL, the losses of the including tasks are jointly optimized. However, it is common for these tasks to be competing. When the tasks are competing, minimizing the losses of some tasks increases the losses of others, which accordingly increases the task variance (variance between the task-specific loss); furthermore, it induces under-fitting in some tasks and over-fitting in others, which degenerates the generalization performance of an MTL model. To address this issue, it is necessary to control the task variance; thus, task variance regularization is a natural choice. While intuitive, task variance regularization remains unexplored in MTL. Accordingly, to fill this gap, we study the generalization error bound of MTL through the lens of task variance and propose the task variance matters the generalization performance of MTL. Furthermore, this paper investigates how the task variance might be effectively regularized, and consequently proposes a multi-task learning method based on adversarial multi-armed bandit. The proposed method, dubbed BanditMTL, regularizes the task variance by means of a mirror gradient ascent-descent algorithm. Adopting BanditMTL both in CV and NLP applications is found to achieve state-of-the-art performance. The results of extensive experiments back up our theoretical analysis and validate the superiority of our proposals.

Clique, as a fundamental model for graph analysis, is widely investigated in the literature. However, with the emergence of various graph data, such as signed graph, novel clique model is desired to better capture the cohesiveness within these graphs. Different from unsigned graphs, where only one type of edge exists, in signed graphs, nodes can be connected either positively or negatively (e.g., friend or enemy). In this article, we propose a novel clique model, called signed$k$-clique, which aims to find cohesive subgraphs in signed networks based on the classic clique model and balance theory. Given a signed graph$G$, an induced subgraph$S$is a signed$k$-clique if$|S| \geq k$and$S$is a clique without any unbalanced triangle. Moreover, we propose and investigate two fundamental problems, i.e., maximal signed$k$-clique enumeration and maximum signed$k$-clique identification, both of which are shown to be NP-hard. For maximal signed$k$-clique enumeration, novel balance graph based search framework and optimization techniques are proposed to eliminate the limitations in the developed baseline. For maximum signed$k$-clique identification, different upper bound based techniques are developed to early terminate the search. Furthermore, the support of finding top-$\gamma$results is also discussed. Finally, comprehensive experiments on seven real-world datasets are conducted to demonstrate the efficiency and effectiveness of the proposed techniques. Compared with the baseline, the optimized algorithm can achieve up to four orders of magnitude speedup.

Unsupervised contrastive learning has recently become increasingly popular due to its amazing performance without the need for costly annotations. However, indiscriminate sampling of negative pairs is accompanied by the uniformity-tolerance dilemma, which is especially serious in node-level graph contrastive learning due to the smoothing property of graph convolutional operators. Previous negative mining strategies that either overly emphasize hard negatives or rely on precise distribution estimation can make minor improvements or even degrade the performance in such a case. In this article, we investigate the role of hard negatives in the uniformity-tolerance dilemma and propose a novel contrastive objective with a progressive hard negative masking scheme. The proposed objective, as an asymptotically-tightened lower bound of mutual information, is theoretically and empirically demonstrated to be capable of allowing higher local tolerance and stronger contrastive effects, thus leading to higher-quality embedding distributions and considerable performance improvement in downstream node classification tasks.

Given a bipartite graph, the maximum edge biclique problem (MEB) aims to find a biclique with the largest number of edges. MEB is a fundamental problem with many real applications, such as community analysis, E-commerce services and bioinformatics. However, in some scenarios, the weight of an edge reflects valuable and important information on the relationship between two entities. Motivated by this, in this paper, we investigate the problem of maximum edge-weighted biclique search (MEWB), which finds a biclique with the largest total weight of edges in a weighted bipartite graph. MEWB has many real applications, including item recommendation, fraud detection, gene clustering, etc. Although we show that MEWB can be resolved by adapting the search algorithm designed for MEB, the performance of this method is yet unsatisfactory. To improve the computation efficiency, two optimizations in terms of upper bound and search order are proposed. For the upper bound, we consider the degree distribution for vertices in the candidate set, and thus have a chance to discard a few edges to tighten the upper bound. For search order, we theoretically show that a vertex order generating the most similar search depth on vertices can achieve the least time cost for MEWB. Guided by this fact, we propose the global summation vertex order. To further accelerate the computation, we extend our approach to a parallel environment, and develop a heuristic approach to deal with large-scale graphs by slightly sacrificing the answer quality. Extensive performance studies conducted on real datasets demonstrate that our proposals can significantly outperform the baseline method by up to two orders of magnitude. Besides, our heuristic approach gives the optimal result on 8 out of 10 real datasets, while achieving more than an order of magnitude of speed-up.

In this article, we propose the$(\alpha,\beta,\eta)$-core model, which is the first cohesive subgraph model on uncertain bipartite graphs. To capture the uncertainty of relationships/edges,$\eta$-degree is adopted to measure the vertex engagement level, which is the largest integer$k$such that the probability of a vertex having at least$k$neighbors is not less than$\eta$. Given degree constraints$\alpha$and$\beta$, and a probability threshold$\eta$, the$(\alpha,\beta,\eta)$-core requires that each vertex on the upper or lower level have$\eta$-degree no less than$\alpha$or$\beta$, respectively. An$(\alpha,\beta,\eta)$-core can be obtained by iteratively removing the vertices with$\eta$-degrees below the degree constraints. Apart from the online computation algorithm, we propose a probability-aware index to strike a balance between time and space costs. To efficiently build such an index, we design a top-down index construction algorithm to allow computation sharing. Then, we show how to parallelize our query algorithms and index construction algorithms. In addition, we study community search on uncertain bipartite graphs by adopting the$(\alpha,\beta,\eta)$-core model. Extensive experiments are conducted on 13 datasets to validate the efficiency and effectiveness of our proposed techniques.

Bipartite graphs are widely used to capture the relationships between two types of entities. In bipartite graph analysis, finding the maximum balanced biclique (MBB) is an important problem with numerous applications. A biclique is balanced if its two disjoint vertex sets are of equal size. However, in real-world scenarios, each vertex is associated with a weight to denote its properties, such as influence, i.e., weighted bipartite graph. For weighted bipartite graphs, the previous studies for MBB are no longer applicable due to the ignorance of weight. To fill the gap, in this paper, we propose a reasonable definition of “balance” by restricting the weight difference between two sides of a biclique within$k$. Given a weighted bipartite graph$G$and a constraint$k$, we aim to find the maximum$k$-balanced biclique (Max$k$BB) with the maximum weight. To address the problem, we first propose an approach based on biclique enumeration on single side of$G$following the Branch-and-Bound framework. To improve the performance, we further devise three optimization strategies to prune invalid search branches. Moreover, we utilize graph reduction strategy to reduce the redundant search space. Extensive experiments are conducted on 12 real bipartite datasets to demonstrate the efficiency, effectiveness and scalability of our proposed algorithms. The experimental results show that our algorithms can address MBB detection problem efficiently, and the case study demonstrates the effectiveness of our model compared with MBB model.

Event data are often dirty owing to various recording conventions or simply system errors. These errors may cause serious damage to real applications, such as inaccurate provenance answers, poor profiling results, or concealing interesting patterns from event data. Cleaning dirty event data is strongly demanded. While existing event data cleaning techniques view event logs as sequences, structural information does exist among events, such as the task passing relationships between staffs in workflow or the invocation relationships among different micro-services in monitoring application performance. We argue that such structural information enhances not only the accuracy of repairing inconsistent events but also the computation efficiency. It is notable that both the structure and the names (labeling) of events could be inconsistent. In real applications, while an unsound structure is not repaired automatically (which requires manual effort from business actors to handle the structure error), it is highly desirable to repair the inconsistent event names introduced by recording mistakes. In this article, we first prove that the inconsistent label repairing problem is NP-complete. Then, we propose a graph repair approach for (1) detecting unsound structures, and (2) repairing inconsistent event names. Efficient pruning techniques together with two heuristic solutions are also presented. Extensive experiments over real and synthetic datasets demonstrate both the effectiveness and efficiency of our proposal.

Abstract Bipartite graphs are of great importance in many real-world applications. Butterfly, which is a complete $$2 \times 2$$ 2 × 2 biclique, plays a key role in bipartite graphs. In this paper, we investigate the problem of efficient counting the number of butterflies. The most advanced techniques are based on enumerating wedges which is the dominant cost of counting butterflies. Nevertheless, the existing algorithms cannot efficiently handle large-scale bipartite graphs. This becomes a bottleneck in large-scale applications. In this paper, instead of the existing layer-priority-based techniques, we propose a vertex-priority-based paradigm $${\mathsf {BFC}}$$ BFC - $${\mathsf {VP}}$$ VP to enumerate much fewer wedges; this leads to a significant improvement of the time complexity of the state-of-the-art algorithms. In addition, we present cache-aware strategies to further improve the time efficiency while theoretically retaining the time complexity of $${\mathsf {BFC}}$$ BFC - $${\mathsf {VP}}$$ VP . We also show that our proposed techniques can work efficiently in external and parallel contexts. Moreover, we study the butterfly counting problem on batch-dynamic graphs. Specifically, given a bipartite graph G and a batch-update of edges B , we aim to maintain the number of butterflies in G . To tackle this problem, fast vertex-priority-based algorithms are proposed with optimizations for reducing the computation of existing wedges in G . Our extensive empirical studies demonstrate that the proposed techniques significantly outperform the baseline solutions on real datasets.

The existence of anomalies is quite common, but they are hidden within the complex structure and high-dimensional node attributes of the attributed networks. As a latent hazard in existing systems, anomalies can be transformed into important instruction information once we detect them, e.g., computer network admins can react to the leakage of sensitive data if network traffic anomalies are identified. Extensive research in anomaly detection on attributed networks has proposed various techniques, which do improve the quality of data in networks, while they rarely cope with the few-shot anomaly detection problem. Few-shot anomaly detection task with only a few dozen labeled anomalies is more practical since anomalies are rare in number for real-world systems.

In this paper, we study the problem of constrained path search with submodular function maximization (CPS-SM). We aim to find the path with the best submodular function score under a given constraint (e.g., a length limit), where the submodular function score is computed over the set of nodes in this path. This problem can be used in many applications. For example, tourists may want to search the most diversified path (e.g., a path passing by the most diverse facilities such as parks and museums) given that the traveling time is less than 6 hours. We show that the CPS-SM problem is NP-hard. We first propose a concept called “submodular$\alpha$-dominance” by utilizing the submodular function properties, and we develop an algorithm with a guaranteed error bound based on this concept. By relaxing the submodular$\alpha$-dominance conditions, we design another more efficient algorithm that has the same error bound. We also utilize the way of bi-directional path search to further improve the efficiency of the algorithms. We finally propose a heuristic algorithm that is efficient yet effective in practice. The experiments conducted on several real datasets show that our proposed algorithms can achieve high accuracy and are faster than one state-of-the-art method by orders of magnitude.

The model of k-core discovers a novel hierarchical structure of a network, which has been widely applied in various areas, e.g., sociology, biology, and brain science. Based on the containment relations of k-cores with different$k$, the hierarchical core decomposition (HCD) of a graph formalizes the hierarchy of all k-cores for each possible$k$• HCD is effective in locating high-quality subgraphs (e.g., densest subgraph search) and exploring particular network phenomena (e.g., user engagement study). However, existing solutions of HCD are still not efficient enough, for both the hierarchy construction and the subgraph search on the hierarchy. In this paper, we propose the first parallel construction algorithm PHCD for HCD, using a new union-find-based paradigm, and the first parallel algorithm PBKS to search high-quality subgraphs from the hierarchy with respect to various community scoring metrics. We prove the problem of hierarchy construction is$\mathcal{P}$-complete (difficult to parallelize effectively). Despite the negative result, our PHCD has a near-linear time cost, and PBKS is time-optimal in score computation for most community metrics. Extensive experiments are conducted on 10 real-world networks, where our proposed parallel algorithms significantly outperform the existing solutions, for both the hierarchy construction and the subgraph search.

With the ever-increasing prevalence of graph data in a wide spectrum of applications, it becomes essential to analyze structural trends in dynamic graphs on a continual basis. The shortest cycle is a fundamental pattern in graph analytics. In this paper, we investigate the problem of shortest cycle counting for a given vertex in dynamic graphs in light of its applicability to problems such as fraud detection. To address such queries efficiently, we propose a 2-hop labeling based algorithm called Counting Shortest Cycle (CSC for short). Additionally, techniques for dynamically updating the CSC index are explored. Comprehensive experiments are conducted to demonstrate the efficiency and effectiveness of our method. In particular, CSC enables query evaluation in a few hundreds of microseconds for graphs with millions of edges, and improves query efficiency by two orders of magnitude when compared to the baseline solutions. Also, the update algorithm could efficiently cope with edge insertions (deletions).

Bipartite networks, which model relationships between two different types of entities, are prevalent in many real-world applications. On bipartite networks, the cascading node departure undermines the networks' ability to provide sustainable services, which makes reinforcing bipartite networks a vital problem. Although network reinforcement is extensively studied on unipartite networks, it remains largely unexplored on bipartite graphs. On bipartite networks, ($\alpha, \beta$) -core is a stable structure that ensures different minimum engagement levels of the vertices from different layers, and we aim to reinforce bipartite networks by maximizing the ($\alpha, \beta$) -core. Specifically, given a bipartite network$G$, degree constraints$\alpha$and$\beta$, budgets$b_{1}$and$b_{2}$, we aim to find$b_{1}$upper layer vertices and$b_{2}$lower layer vertices as anchors and bring them into the ($\alpha, \beta$) -core s.t. the number of non-anchor vertices entering in the ($\alpha, \beta$) -core is maximized. We prove the problem is NP-hard and propose a heuristic algorithm FILVER to solve the problem. FILVER runs$b_{1}+b_{2}$iterations and choose the best anchor in each iteration. Under a filter-verification framework, it reduces the pool of candidate anchors (in the filter stage) and computes the resulting ($\alpha, \beta$) - core for each anchor vertex more efficiently (in the verification stage). In addition, filter-stage optimizations are proposed to further reduce “dominated” anchors and allow computation-sharing across iterations. To optimize the verification stage, we explore the cumulative effect of placing multiple anchors, which effectively reduces the number of running iterations. Extensive experiments on 18 real-world datasets and a billion-scale synthetic dataset validate the effectiveness and efficiency of our proposed techniques.

Node importance estimation is a fundamental task in graph data analysis. Extensive studies have focused on this task, and various downstream applications have benefited from it, such as recommendation, resource allocation optimization, and missing value completion. However, existing works either focus on the homogeneous network or only study importance-based ranking. We are the first to consider the node importance values as heterogeneous values in heterogeneous information networks (HINs). A typical HIN is built of several distinguished node types where each type has its own measure of importance value (e.g., in the DBLP network, the importance values of authors and papers can be reflected by their h-index and citation numbers, respectively). This characteristic makes the above problem more challenging than computing the node importance in conventional homogeneous networks. In this paper, we formally introduce the problem of node importance value estimation in HINs; that is, given the importance values of a subset of nodes in an HIN, we aim to estimate the importance values of the remaining nodes. To solve this problem, we propose an effective graph neural network (GNN) model, called HIN Importance Value Estimation Network (HIVEN). HIVEN traces the local information of each node, specifically by utilizing the heterogeneity of the HIN. Furthermore, the meta schema is deployed to alleviate the node type domination issue. Additionally, HIVEN exploits the node similarity within each type to remedy the shortcoming of GNN models in capturing global information. Extensive experiments on real-world HIN datasets demonstrate that HIVEN superiorly outperforms the baseline methods.

With the development of traffic prediction technology, spatiotemporal prediction models have attracted more and more attention from academia communities and industry. However, most existing researches focus on reducing model's prediction error but ignore the error caused by the uneven distribution of spatial events within a region. In this paper, we study a region partitioning problem, namely optimal grid size selection problem (OGSS), which aims to minimize the real error of spatiotemporal prediction models by selecting the optimal grid size. In order to solve OGSS, we analyze the upper bound of real error of spatiotemporal prediction models and minimize the real error by minimizing its upper bound. Through in-depth analysis, we find that the upper bound of real error will decrease then increase when the number of model grids increase from 1 to the maximum allowed value. Then, we propose two algorithms, namely Ternary Search and Iterative Method, to automatically find the optimal grid size. Finally, the experiments verify that the error of prediction has the same trend as its upper bound, and the change trend of the upper bound of real error with respect to the increase of the number of model grids will decrease then increase. Meanwhile, in a case study, by selecting the optimal grid size, the order dispatching results of a state-of-the-art prediction-based algorithm can be improved up to 13.6%, which shows the effectiveness of our methods on tuning the region partition for spatiotemporal prediction models.

Structural clustering (SCAN) is one of the most popular graph clustering paradigms. However, SCAN assumes that the input graph is undirected and can not cluster the directed graphs. To address this problem, in this paper, we propose a new structural clustering model based on SCAN to cluster directed graphs. Following the new model, we propose an index-based approach to support the efficient clustering of a given graph. Moreover, we also devise efficient index maintenance algorithms to handle the case that the input graph is dynamically updated. We conduct extensive experiments on nine real directed graphs, one of which contains more than 2 billion edges. The results demonstrate the effectiveness and efficiency of our proposed methods.

Maximal biclique enumeration is a fundamental problem in bipartite graph analysis, and can find numerous applications. However, previous studies only focus on unsigned bipartite graphs. Signed information, such as friend and enemy, naturally exists in real-world networks. It is critical to leverage signed information to better characterize biclique. To fill this gap, in this paper, we propose a novel biclique model, named balanced signed biclique, by leveraging the property of balance theory. Specifically, given a signed bipartite graph$G$, two positive integers$\tau_{U}, \tau_{V}$, a subgraph$S=(U_{S},\ V_{S},\ E_{S})$of$G$is a balanced signed biclique if$i$)$S$is a biclique without any unstable motif, i.e., unbalanced butterfly, and ii)$\vert U_{S}\vert \geq\tau_{U}$and$\vert V_{S}\vert \geq\tau_{V}$. In this paper, we aim to enumerate all the maximal balanced signed bicliques, which is proved to be NP-hard. Moreover, due to the unique features of signed bipartite graphs, the previous works cannot be applied to our problem directly. To construct a reasonable baseline, we extend the existing biclique enumeration framework for unsigned bipartite graphs and integrate the developed balanced bipartite graph property. To scale for larger networks, novel optimized strategies are proposed to overcome the three limitations in the baseline method. Extensive experi-ments are conducted on 8 real-world datasets to demonstrate the efficiency and effectiveness of proposed techniques and model. Compared with the baseline approach, the optimized algorithm can achieve up to 3 orders of magnitude speedup.

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.

Bipartite graphs are naturally used to model relationships between two different types of entities. On bipartite graphs, maximum biclique search is a fundamental problem that aims to find the complete bipartite subgraph (biclique) with the maximum number of edges and is widely adopted for many applications such as anomaly detection in E-commerce and social network analysis. However, maximum biclique search only identifies the biclique whose size is globally maximum, whereas fast microscopic (personalized) analysis is needed in many real-world scenarios. For instance, when a suspected user is identified in an E-commerce network (e.g., a user-product network), it is important to quickly find the anomalous group containing the user and send the group of users for further human expert investigation. To fill this research gap, for the first time, we study the efficient personalized maximum biclique search problem, which aims to find the maximum biclique containing a specific query vertex in real-time. Apart from online computation algorithms, we explore index-based approaches and propose the PMBC-Index. With the PMBC-Index, the query algorithm is up to five orders of magnitude faster than the baseline algorithms. Furthermore, effective pruning strategies and parallelization techniques are devised to support efficient index construction. Extensive experiments on 10 real-world graphs validate both the effectiveness and the efficiency of our proposed techniques.

Bipartite graph is a widely used model to describe relationships between two different types of entities. Exploring graph hierarchy with cohesive subgraphs has been extensively studied on unipartite graphs, while only a few works focus on bipartite graphs. In this paper, we propose the bipartite hierarchy, which is the first model to discover the hierarchical structure of bipartite graphs based on the concept of$(\alpha_{2}\beta){-}$core and graph connectivity. Notably,$(\alpha, \beta)-\text{core}$is a vertex- centric model that conforms to the special structure of bipartite graphs (i.e., formed by two different vertex layers). Accordingly, the bipartite hierarchy has two parts (i.e., the upper and lower hierarchies) to record the hierarchical relationships among upper and lower vertices, respectively. We theoretically prove that the bipartite hierarchy is space-efficient (i.e., its space cost is linear to the graph size) and clearly illustrate its structure via visualization. In addition, efficient algorithms for building the bipartite hierarchy are proposed by utilizing the nested property of$(\alpha, \beta)-\text{core}$. Since bipartite graphs can be dynamically changed in real-world scenarios, we also study the bipartite hierarchy maintenance algorithms against the edge insertion/deletion cases. These algorithms can effectively identify the affected regions to limit computation scope and avoid re-building the bipartite hierarchy from scratch. Extensive experiments on 10 real-world graphs not only demonstrate the effectiveness of the proposed bipartite hierarchy but also validate the efficiency of our hierarchy construction and maintenance algorithms.

Subgraph matching is a fundamental problem in various fields that use graph structured data. Subgraph matching algorithms enumerate all isomorphic embeddings of a query graph$q$in a data graph G. An important branch of matching algorithms exploit the backtracking search approach which recursively extends intermediate results following a matching order of query vertices. It has been shown that the matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In recent years, many advanced techniques for query vertex ordering (i.e., matching order generation) have been proposed to reduce the unpromising intermediate results according to the preset heuristic rules. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms. Instead of using the fixed heuristics to generate the matching order, our model could capture and make full use of the graph information, and thus determine the query vertex order with the adaptive learning-based rule that could significantly reduces the number of redundant enumerations. With the help of the reinforcement learning framework, our model is able to consider the long-term benefits rather than only consider the local information at current ordering step. Extensive experiments on six real-life data graphs demonstrate that our proposed matching order generation technique could reduce up to two orders of magnitude of query processing time compared to the state-of-the-art algorithms.

The approximate nearest neighbor (ANN) search in high-dimensional space offers a wide spectrum of applications across many domains such as database, machine learning, multimedia and computer vision. A variety of ANN search algorithms have been proposed in the literature. In recent years, proximity graph-based approaches have attracted considerable attention from both industry and academic settings due to the superior search performance in terms of speed and accuracy. A recent work utilizes a graphics processing unit (GPU) to accelerate the ANN search on proximity graphs. Though significantly reducing the distance computation time by taking advantage of the massive parallelism of GPUs, the algorithm suffers from the high expenses of data structure operations. In this paper, we propose a novel GPU -accelerated algorithm that designs a novel GPU-friendly search framework on proximity graphs to fully exploit the massively parallel processing power of GPUs at key steps of the search. Also, we propose GPU-accelerated proximity graph construction algorithms which can build high-quality representative proximity graphs with efficient parallel implementations. Extensive experiments on benchmark high-dimensional datasets demonstrate the outstanding performance of our proposed algorithms in both ANN search and proximity graph construction.

Listing all k-cliques is a fundamental problem in graph mining, with applications in finance, biology, and social network analysis. However, owing to the exponential growth of the search space as$k$increases, listing all k-cliques is algorithmically challenging. DDegree and DDegCol are the state-of-the-art algorithms that exploit ordering heuristics based on degree ordering and color ordering, respectively. Both DDegree and DDegCol induce high time and space overhead for set intersections cause they construct and maintain all induced subgraphs. Meanwhile, it is non-trivial to implement the data level parallelism to further accelerate on DDegree and DDegCol. In this paper, we propose two efficient algorithms SDegree and BitCol for k-clique listing. We mainly focus on accelerating the set intersections for k-clique listing. Both SDegree and BitCol exploit the data level parallelism for further acceleration with single instruction multiple data (SIMD) or vector instruction sets. Furthermore, we propose two preprocessing techniques Pre-Core and Pre-List, which run in linear time. The preprocessing techniques significantly reduce the size of the original graph and prevent exploring a large number of invalid nodes. In the theoretical analysis, our algorithms have a comparable time complexity and a slightly lower space complexity than the state-of-the-art algorithms. The comprehensive experiments reveal that our algorithms outperform the state-of-the-art algorithms by 3.75x for degree ordering and 5.67x for color ordering on average.

Real-world graphs are typically distributed across multiple data centers. When performing reachability queries on these distributed graphs, reachability labeling methods ensure fast query processing by using lightweight indexes. One of the best-known labeling methods is TOL; however, TOL is a serial algorithm and cannot handle distributed graphs. The main goal of this paper is to design new labeling methods that can work in parallel while producing the same index as TOL. To this end, we investigate the limitation of TOL and thus propose a filtering-and-refinement framework for index creation. This framework first obtains a super-set of each vertex's label sets and then eliminates the invalid elements. Based on this framework, we design distributed labeling algorithms and then use batch processing to improve efficiency. Experimental results on real-world graphs show that the proposed algorithms can index distributed graphs efficiently.

Bipartite graphs are extensively used to model relationships between two different types of entities. In many real-world bipartite graphs, relationships are naturally uncertain due to various reasons such as data noise, measurement error and imprecision of data, leading to uncertain bipartite graphs. In this paper, we propose the ($\alpha,\beta,\eta$)-core model, which is the first cohesive subgraph model on uncertain bipartite graphs. To capture the uncertainty of relationships/edges,$\eta$-degree is adopted to measure the vertex engagement level, which is the largest integer$k$such that the probability of a vertex having at least$k$neighbors is not less than$\eta$. Given degree constraints$\alpha$and$\beta$, and a probability threshold$\eta$, the ($\alpha, \beta, \eta$)-core requires that each vertex on the upper or lower level have$\eta$-degree no less than$\alpha$or$\beta$, respectively. An ($\alpha, \beta, \eta$)-core can be derived by iteratively removing a vertex with$\eta$-degree below the degree constraint and updating the$\eta$-degrees of its neighbors. This incurs prohibitively high cost due to the$\eta$-degree computation and updating, and is not scalable to large bipartite graphs. This motivates us to develop index-based approaches. We propose a basic full index that stores ($\alpha, \beta, \eta$)-core for all possible$\alpha, \beta$, and$\eta$combinations, thus supporting optimal retrieval of the vertices in any ($\alpha, \beta, \eta$)-core. Due to its long construction time and high space complexity, we further propose a probability-aware index to achieve a balance between time and space costs. To efficiently build the probability-aware index, we design a bottom-up index construction algorithm and a top-down index construction algorithm. Extensive experiments are conducted on real-world datasets with generated edge probabilities under different distributions, which show that (1) ($\alpha,\beta,\eta$)-core is an effective model; (2) index construction and query processing are significantly sped up by the proposed techniques.

In spite of its wide usage in various applications, existing construction methods for Knowledge Base (KB) are still on their way to obtaining 100% correct facts. Thus, employing crowd workers to validate a KB has been proposed to improve its reliability. Most of the existing works focus on devising games with proper incentives to engage workers in validating more facts, but rarely consider matching facts with proper workers. Facts have diverse domains (topics), which naturally require workers of different expertise. In addition, they also generally have different utilities, i.e., some are more heavily used than others. Thus, distinguishing the facts in terms of utility to give them different validation priorities is meaningful, especially when the budget is limited. To this end, we study the crowdsourced fact validation problem which considers worker domains and fact utilities, and find that with some reductions, it can be solved by the existing minimum cost network flow method. However, directly employing that method requires a huge time cost. We thereby propose an optimized network flow method which reduces the network complexity to save the time cost by properly grouping the facts. Furthermore, we propose an incremental validation method, which utilizes the previous results for validating an evolving KB. We finally conduct extensive experiments to demonstrate the effectiveness of the proposed methods.

Given a graph, eccentricity measures the distance from each node to its farthest node. Eccentricity indicates the centrality of each node and collectively encodes fundamental graph properties: the radius and the diameter --- the minimum and maximum eccentricity, respectively, over all the nodes in the graph. Computing the eccentricities for all the graph nodes, however, is challenging in theory: any approach shall either complete in quadratic time or introduce a 1/3 relative error under certain hypotheses. In practice, the state-of-the-art approach PLLECC in computing exact eccentricities relies heavily on a precomputed all-pair-shortest-distance index whose expensive construction refrains PLLECC from scaling up. This paper provides insights to enable scalable exact eccentricity computation that does not rely on any index. The proposed algorithm IFECC handles billion-scale graphs that no existing approach can process and achieves up to two orders of magnitude speedup over PLLECC. As a by-product, IFECC can be terminated at any time during execution to produce approximate eccentricities, which is empirically more stable and reliable than KBFS, the state-of-the-art algorithm for approximately computing eccentricities.

Given a heterogeneous information network (HIN) H, a head node h , a meta-path P, and a tail node t , the meta-path prediction aims at predicting whether h can be linked to t by an instance of P. Most existing solutions either require predefined meta-paths, which limits their scalability to schema-rich HINs and long meta-paths, or do not aim at predicting the existence of an instance of P. To address these issues, in this article, we propose a novel prediction model, called ABLE, by exploiting the A ttention mechanism and B i L STM for E mbedding. Particularly, we present a concatenation node embedding method by considering the node types and a dynamic meta-path embedding method that carefully considers the importance and positions of edge types in the meta-paths by the Attention mechanism and BiLSTM model, respectively. A triplet embedding is then derived to complete the prediction. We conduct extensive experiments on four real datasets. The empirical results show that ABLE outperforms the state-of-the-art methods by up to 20% and 22% of improvement of AUC and AP scores, respectively.

Abstract Maximum biclique search, which finds the biclique with the maximum number of edges in a bipartite graph, is a fundamental problem with a wide spectrum of applications in different domains, such as E-Commerce, social analysis, web services, and bioinformatics. Unfortunately, due to the difficulty of the problem in graph theory, no practical solution has been proposed to solve the issue in large-scale real-world datasets. Existing techniques for maximum clique search on a general graph cannot be applied because the search objective of maximum biclique search is two-dimensional, i.e., we have to consider the size of both parts of the biclique simultaneously. In this paper, we divide the problem into several subproblems each of which is specified using two parameters. These subproblems are derived in a progressive manner, and in each subproblem, we can restrict the search in a very small part of the original bipartite graph. We prove that a logarithmic number of subproblems is enough to guarantee the algorithm correctness. To minimize the computational cost, we show how to reduce significantly the bipartite graph size for each subproblem while preserving the maximum biclique satisfying certain constraints by exploring the properties of one-hop and two-hop neighbors for each vertex. Furthermore, we study the diversified top-kbiclique search problem which aims to findkmaximal bicliques that cover the most edges in total. The basic idea is to repeatedly find the maximum biclique in the bipartite graph and remove it from the bipartite graphktimes. We design an efficient algorithm that considers to share the computation cost among thekresults, based on the idea of deriving the same subproblems of different results. We further propose two optimizations to accelerate the computation by pruning the search space with size constraint and refining the candidates in a lazy manner. We use several real datasets from various application domains, one of which contains over 300 million vertices and 1.3 billion edges, to demonstrate the high efficiency and scalability of our proposed solution. It is reported that 50% improvement on recall can be achieved after applying our method in Alibaba Group to identify the fraudulent transactions in their e-commerce networks. This further demonstrates the usefulness of our techniques in practice.

In this paper, we study the privacy-preserving task assignment problem in spatial crowdsourcing, where the locations of both workers and tasks, prior to their release to the server, are perturbed with Geo-Indistinguishability (a differential privacy notion for location-based systems). Different from the previously studied online setting, where each task is assigned immediately upon arrival, we target the batch-based setting, where the server maximizes the number of successfully assigned tasks after a batch of tasks arrive. To achieve this goal, we propose the k-Switch solution, which first divides the workers into small groups based on the perturbed distance between workers/tasks, and then utilizes Homomorphic Encryption (HE) based secure computation to enhance the task assignment. Furthermore, we expedite HE-based computation by limiting the size of the small groups under k. Extensive experiments demonstrate that, in terms of the number of successfully assigned tasks, the k-Switch solution improves batch-based baselines by 5.9X and the existing online solution by 1.74X, with no privacy leak.

Label-Constraint Reachability query (LCR) which extracts of reachability information from large edge-labeled graphs, has attracted tremendous interest. Various LCR algorithms have been proposed to solve this fundamental query, which has a wide range of applications in social networks, biological networks, economic networks, etc. In this paper, we implement the state-of-the-art P2H+ algorithm as well as functions to analyze the effectiveness. Moreover, our Dynamic LCR Query (DLQ) system also supports dynamic updates with the 2-hop labeling method. In this demonstration, we present the DLQ system for Label-Constrained Reachability Queries that utilize the 2-hop labeling algorithm with dynamic graph maintenance.

Bipartite graphs arise naturally when modeling two different types of entities such as user-item, author-paper, and director-board. In recent years, driven by numerous real-world applications in these networks, mining cohesive structures in bipartite graphs becomes a popular research topic. In this paper, we propose the first cohesive-structure-based bipartite graph analytics system, CohBGA. The key innovative features of our system are as follows. Firstly, we involve several cohesive-structure-based models and statistics in our system to analyze bipartite graphs at different levels of granularity. Secondly, CohBGA has a user-friendly and interactive visual interface with various functional tools to meet users' diverse query requirements. Thirdly, we implement state-of-the-art algorithms in CohBGA to support efficient query processing. Furthermore, as a generic framework is designed in CohBGA, CohBGA is going to be an open-source bipartite graph analytics platform that allows researchers to evaluate the effectiveness of more cohesive-structure-based models and algorithms for bipartite graphs.

In many real-world applications, bipartite graphs are naturally used to model relationships between two types of entities. Community discovery over bipartite graphs is a fundamental problem and has attracted much attention recently. However, all existing studies overlook the weight (e.g., influence or importance) of vertices in forming the community, thus missing useful properties of the community. In this paper, we propose a novel cohesive subgraph model named Pareto-optimal (α β), which is the first to consider both structure cohesiveness and weight of vertices on bipartite graphs. The proposed Pareto-optimal (α β) model follows the concept of (α, β)-core by imposing degree constraints for each type of vertices, and integrates the Pareto-optimality in modelling the weight information from two different types of vertices. An online query algorithm is developed to retrieve Pareto-optimal (α β) with the time complexity of O(p. m) where p is the number of resulting communities, and m is the number of edges in the bipartite graph G. To support efficient query processing over large graphs, we also develop index-based approaches. A complete index i is proposed, and the query algorithm based on i achieves linear query processing time regarding the result size (i.e., the algorithm is optimal). Nevertheless, the index i incurs prohibitively expensive space complexity. To strike a balance between query efficiency and space complexity, a space-efficient compact index 𝕀 is proposed. Computation-sharing strategies are devised to improve the efficiency of the index construction process for the index 𝕀. Extensive experiments on 9 real-world graphs validate both the effectiveness and the efficiency of our query processing algorithms and indexing techniques.

Simulation and its variants (e.g., bisimulation and degree-preserving simulation) are useful in a wide spectrum of applications. However, all simulation variants are coarse "yes-or-no" indicators that simply confirm or refute whether one node simulates another, which limits the scope and power of their utility. Therefore, it is meaningful to develop a fractional χ-simulation measure to quantify the degree to which one node simulates another by the simulation variant χ. To this end, we first present several properties necessary for a fractional χ-simulation measure. Then, we present FSimχ, a general fractional χ-simulation computation framework that can be configured to quantify the extent of all χ-simulations. Comprehensive experiments and real-world case studies show the measure to be effective and the computation framework to be efficient.

Subgraph matching is a basic operation widely used in many applications. However, due to its NP-hardness and the explosive growth of graph data, it is challenging to compute subgraph matching, especially in large graphs. In this paper, we aim at scaling up subgraph matching on a single machine using FPGAs. Specifically, we propose a CPU-FPGA co-designed framework. On the CPU side, we first develop a novel auxiliary data structure called candidate search tree (CST) which serves as a complete search space of subgraph matching. CST can be partitioned and fully loaded into FPGAs' on-chip memory. Then, a workload estimation technique is proposed to balance the load between the CPU and FPGA. On the FPGA side, we design and implement the first FPGA-based subgraph matching algorithm, called FAST. To take full advantage of the pipeline mechanism on FPGAs, task parallelism optimization and task generator separation strategy are proposed for FAST, achieving massive parallelism. Moreover, we carefully develop a BRAM-only matching process to fully utilize FPGA's on-chip memory, which avoids the expensive intermediate data transfer between FPGA's BRAM and DRAM. Comprehensive experiments show that FAST achieves up to 462.0x and 150.0x speedup compared with the state-of-the-art algorithm DAF and CECI, respectively. In addition, FAST is the only algorithm that can handle the billion-scale graph using one machine in our experiments.

Graph plays a vital role in representing entities and their relationships in a variety of fields, such as e-commerce networks, social networks and biological networks. Given two verticessandt, one of the fundamental problems in graph databases is to investigate the relationships betweensandt. A well-studied problem in such area is k-hop constraineds-tsimple path enumeration. Nevertheless, all existing algorithms targeting this problem follow the DFS-based paradigm, which cannot scale up well. Moreover, using hardware devices like FPGA to accelerate graph computation has become popular. Motivated by this, in this paper, we propose the first FPGA-based algorithm PEFP to solve the problem of k-hop constrained s-t simple path enumeration efficiently. On the host side, we propose a preprocessing algorithm Pre-BFS to reduce the graph size and search space. On the FPGA side in PEFP, we propose a novel DFS-based batching technique to save on-chip memory efficiently. In addition, we also propose caching techniques to cache necessary data in BRAM, which overcome the latency bottleneck brought by the read/write operations from/to FPGA DRAM. Finally, we propose a data separation technique to enable dataflow optimization for the path verification module; hence the sub-stages in that module can be executed in parallel. Comprehensive experiments show that PEFP outperforms the state-of-the-art algorithm JOIN by more than 1 order of magnitude by average, and up to 2 orders of magnitude in terms of preprocessing time, query processing time and total time, respectively.

The studies of k-truss based community search demonstrated that it can find high-quality personalized com-munities with good properties such as high connectivity and bounded diameter. Motivated by natural restrictions from real applications, in this paper, we investigate the search of triangle-connected k-truss with size constraint (denoted by SCkT) in a graph G: given a size constraint s, an integer k, and query set Q, SCkT search aims to find a triangle-connected k-truss H containing the vertices in Q and with size (i.e., total number of vertices in H) not exceeding s. We prove that the SCkT search problem is NP-hard. To tame the hardness, we fully exploit the properties of triangle-connected k-truss subgraphs s.t. a practically-efficient exact solution for SCkT search is developed. A novel and effective lower bound is proposed to early terminate unpromising search branches and narrow down the search space. Two search strategies, expansion and shrinking, are investigated to tailor for efficient support of SCkT search. A hybrid search method is proposed combining the expansion and shrinking strategies, where a score function is used to guide the search order. Our extensive experiments on real-life and synthetic graphs demonstrate the effectiveness of the SCkT model and the efficiency of the proposed techniques.

In this paper, we study exact hypercore maintenance in large-scale dynamic hypergraphs. A hypergraph, whose hyperedges may contain a set of vertices rather than two vertices in pairwise graphs, can represent complex interactions in more sophisticated applications. However, the exponential number of hyperedges incurs unaffordable costs to recompute the hypercore number of vertices and hyperedges when updating a hypergraph. This motivates us to propose an efficient approach for exact hypercore maintenance with the intention of significantly reducing the hypercore updating time comparing with recomputation approaches. The proposed algorithms can pinpoint the vertices and hyperedges whose hypercore numbers have to be updated by only traversing a small sub-hypergraph. Extensive experiments on real-world and temporal hypergraphs demonstrate the superiority of our algorithms in terms of efficiency.

To encourage users to buy more products, many online stores offer coupons. When a customer finds that the price of the products she/he wants to order is below the threshold of a coupon, she/he might want to place the order together with others to meet this threshold and enjoy more instant rebates. However, to conduct these orders and deliver products to receivers, users may need to pay extra delivery costs. When an order comprises several receivers' requests, the products in the order should first be delivered from stores to an assigned warehouse, packed into different packages, and delivered to the different receivers. It may be costly than directly delivering products from stores to receivers. For the benefits of buyers, we propose a platform, the Crowdrebate platform, which collects requests from users, groups requests into a set of orders to get more rebates, and relays products to different receivers in an order. The platform will make a profit by getting a proportion from the benefit of the receiver (defined as the rebate minus the extra cost) of orders as its revenue. In this paper, we define the Crowdrebate problem, which aims to maximize the benefit of receivers. We prove the NP-hardness of the Crowdrebate problem. Therefore, we propose a heuristic solution to address the problem. Moreover, we evaluate the effectiveness and efficiency of our algorithm via comprehensive experiments.

Bipartite graphs are widely used to model relation-ships between two types of entities. Community search retrieves densely connected subgraphs containing a query vertex, which has been extensively studied on unipartite graphs. However, community search on bipartite graphs remains largely unexplored. Moreover, all existing cohesive subgraph models on bipartite graphs can only be applied to measure the structure cohesiveness between two sets of vertices while overlooking the edge weight in forming the community. In this paper, we study the significant (α, β)-community search problem on weighted bipartite graphs. Given a query vertex q, we aim to find the significant (α, β)-community ℛ of q which adopts (α, β)-core to characterize the engagement level of vertices, and maximizes the minimum edge weight (significance) within ℛ.To support fast retrieval of ℛ, we first retrieve the maximal connected subgraph of (α, β)-core containing the query vertex (the (α, β)-community), and the search space is limited to this subgraph with a much smaller size than the original graph. A novel index structure is presented which can be built in O(δ·m) time and takes O(δ·m) space where m is the number of edges in G, δ is bounded by √m and is much smaller in practice. Utilizing the index, the (α, β)-community can be retrieved in optimal time. To further obtain ℛ, we develop peeling and expansion algorithms to conduct searches by shrinking from the (α, β)-community and expanding from the query vertex, respectively. The experimental results on real graphs not only demonstrate the effectiveness of the significant (α, β)-community model but also validate the efficiency of our query processing and indexing techniques.

Advances of the sensor and GPS techniques have motivated the proliferation of trajectory data in a wide spectrum of applications. Trajectory similarity computation is one of the most fundamental problems in trajectory analytics. Considering that the high complexity of similarity computation is usually a bottleneck for large-scale trajectory data analysis, there are many research efforts for reducing the complexity such as the approximate algorithms. However, most of them are proposed for only one or two specific similarity measures, and thus cannot support different similarity measures well. In this paper, we propose a deep learning based model, namely T3S, which embeds each trajectory (i.e., a sequence of points) into a vector (point) in a d-dimensional space, and hence can significantly accelerate the similarity computation between the trajectories. By applying recurrent and attention neural networks, T3S can capture various unique characteristics of the trajectories such as the ordering of the points, spatial and structural information. Furthermore, our learning based T3S can easily handle any trajectory similarity measures by adjusting its parameters through the training. Extensive experiments on two real-life datasets demonstrate the effectiveness and efficiency of T3S. T3S outperforms state-of-the-art deep learning based methods under four popular trajectories similarity measures.

Triangle listing is an important topic in many practical applications. We have observed that this problem has not yet been studied systematically in the context of batch-dynamic graphs. In this paper, we aim to fill this gap by developing novel and efficient parallel solutions. Specifically, given a graph G and a batch-update of edges B, we report the updated triangles (deleted triangles and new triangles) resulting from the batch of updates. We notice that it is cost expensive to directly apply state-of-the-art triangle listing algorithms because they are designed to enumerate the complete set of triangles from a given graph, whereas only the updated ones are the relevant output for our problem setting. In this paper, we developed an efficient algorithm, namely DPTL, based on a newly designed orientation technique, which only outputs the updated triangles while ensuring that each triangle solution is identified without any duplicate solutions. We follow up by taking advantage of a graph's degree distributions and designed a more sophisticated algorithm, namely DPTL+. We show that DPTL+ can achieve the best performance in terms of both practical performance and theoretical time complexity. Our comprehensive experiments over 28 real-life large graphs show the superior performance of the DPTL+ algorithm when compared against DPTL and two baseline solutions. Theoretically, we also show that DPTL+ has a time complexity of Θ(Σ〈u,v〉∈Bmin{deg(u), deg(v)}+m) where deg(x) is the degree of a vertex x, and m is the number of edges adjacent to the vertices in the batch-update. This time complexity is more promising than that of other solutions.

Matrix Factorization (MF) has been widely applied in machine learning and data mining. Due to the large computational cost of MF, we aim to improve the efficiency of SGD-based MF computation by utilizing the massive parallel processing power of heterogeneous multiprocessors. The main challenge in parallel SGD algorithms on heterogeneous CPU-GPU systems lies in the strategy to assign tasks. We design a novel strategy to divide the matrix into a set of blocks by considering two aspects. First, we observe that the matrix should be divided nonuniformly, and relatively large blocks should be assigned to GPUs to saturate the computing power of GPUs. In addition to exploiting the characteristics of hardware, the workloads assigned to two types of hardware should be balanced. We design a cost model tailored for our problem to accurately estimate the performance of hardware on different data sizes. Extensive experiments show that our proposed algorithm achieves high efficiency with a high quality of training quality.

With the advent of a wide spectrum of recent applications, querying heterogeneous information networks (HINs) has received a great deal of attention from both academic and industrial societies. HINs involve objects (vertices) and links (edges) that are classified into multiple types; examples include bibliography networks, knowledge networks, and user-item networks in E-business. An important component of these HINs is the cohesive subgraph, or a subgraph containing vertices that are densely connected internally. Searching cohesive subgraphs over HINs has found many real applications, such as community search, product recommendation, fraud detection, and so on. Consequently, how to design effective cohesive subgraph models and how to efficiently search cohesive subgraphs on large HINs become important research topics in the era of big data. In this tutorial, we first highlight the importance of cohesive subgraph search over HINs in various applications and the unique challenges that need to be addressed. Subsequently, we conduct a thorough review of existing works of cohesive subgraph search over HINs. Then, we analyze and compare the models and solutions in these works. Finally, we point out new research directions. We believe that this tutorial not only helps researchers to have a better understanding of existing cohesive subgraph search models and solutions, but also provides them insights for future study.

Subgraph query processing (also known as subgraph search) and subgraph matching are fundamental graph problems in many application domains. A lot of efforts have been made to develop practical solutions for these problems. Despite the efforts, existing algorithms showed limited running time and scalability in dealing with large and/or many graphs. In this paper, we propose a new subgraph search algorithm using equivalences of vertices in order to reduce search space: (1) static equivalence of vertices in a query graph that leads to an efficient matching order of the vertices, and (2) dynamic equivalence of candidate vertices in a data graph, which enables us to capture and remove redundancies in search space. These techniques for subgraph search also lead to an improved algorithm for subgraph matching. Experiments show that our approach outperforms state-of-the-art subgraph search and subgraph matching algorithms by up to several orders of magnitude with respect to query processing time.

Due to the growing popularity of indoor location-based services, indoor data management has received significant research attention in the past few years. However, we observe that the existing indexing and query processing techniques for the indoor space do not fully exploit the properties of the indoor space. Consequently, they provide below par performance which makes them unsuitable for large indoor venues with high query workloads. In this demonstration, we present IndoorViz, a new indoor spatial data management system that integrates three novel index structures proposed in [4] and [6] with well designed query processing algorithms and 3D visualization functions. The IndoorViz is able to support indoor spatial object indexing, efficient query processing and interactive 3D display.

In privacy-preserving blockchain systems, to protect a sender's identity of a transaction in privacy-preserving blockchain systems, ring signature (RS) schemes have been widely implemented, which allow users to obscure consumed tokens via including "mixin'' (i.e., chaff tokens). However, recent works point out that existing RS schemes are vulnerable to the "chain-reaction'' analysis, where adversaries eliminate mixins of RSs by utilizing the fact that each token can only be consumed in a RS. By "chain-reaction'' analysis, adversaries can find some definite token-RS pair sets (DTRSs) to confirm the sender's identity of a RS. Besides, the existing RS schemes do not consider the diversity of mixins when generating a RS. Moreover, since the transaction fee is proportional to the number of mixins, a use is motivated to use a RS with the minimum number of mixins. In this paper, we formally define the diversity-aware mixins selection (DA-MS) problem, which aims to generate a RS with the minimum number of mixins satisfying the constraints of its diversity and the anonymity of other RSs. We prove the DA-MS problem is $\#P$ and propose a breadth-first search algorithm to get the optimal solution. Furthermore, to efficiently solve the DA-MS problem, we propose two practical configurations and two approximation algorithms with theoretic guarantees. Through comprehensive experiments on real data sets as well as synthetic data sets, we illustrate the effectiveness and the efficiency of our solutions.

Subgraph enumeration is a fundamental problem in graph analytics, which aims to find all instances of a given query graph on a large data graph. In this paper, we propose a system called HUGE to efficiently process subgraph enumeration at scale in the distributed context. HUGE features 1) an optimiser to compute an advanced execution plan without the constraints of existing works; 2) a hybrid communication layer that supports both pushing and pulling communication; 3) a novel two-stage execution mode with a lock-free and zero-copy cache design; 4) a BFS/DFS-adaptive scheduler to bound memory consumption; and 5) two-layer intra- and inter-machine load balancing. HUGE is generic such that all existing distributed subgraph enumeration algorithms can be plugged in to enjoy automatic speed up and bounded-memory execution.

With the rapid development of smart mobile devices, the car-hailing platforms (e.g., Uber or Lyft) have attracted much attention from the academia and the industry. In this paper, we consider a dynamic car-hailing problem, namely maximum revenue vehicle dispatching (MRVD), in which rider requests dynamically arrive and drivers need to serve riders such that the entire revenue of the platform is maximized. We prove that the MRVD problem is NP-hard and intractable. To handle the MRVD problem, we propose a queueing-based vehicle dispatching framework, which first uses existing machine learning models to predict the future vehicle demand of each region, then estimates the idle time periods of drivers through a double-sided queueing model for each region. With the information of the predicted vehicle demands and estimated idle time periods of drivers, we propose two batch-based vehicle dispatching algorithms to efficiently assign suitable drivers to riders such that the expected overall revenue of the platform is maximized during each batch processing. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic datasets. In summary, our methods can achieve 3% ~ 10% increase on overall revenue without sacrificing on running speed compared with the state-of-the-art solutions.

Bipartite graphs are naturally used to model relationships between two different types of entities, such as people-location, author-paper, and customer-product. When modeling real-world applications like disease outbreaks, edges are often enriched with temporal information, leading to temporal bipartite graphs. While reachability has been extensively studied on (temporal) unipartite graphs, it remains largely unexplored on temporal bipartite graphs. To fill this research gap, in this paper, we study the reachability problem on temporal bipartite graphs. Specifically, a vertex u reaches a vertex w in a temporal bipartite graph G if u and w axe connected through a series of consecutive wedges with time constraints. Towards efficiently answering if a vertex can reach the other vertex, we propose an index-based method by adapting the idea of 2-hop labeling. Effective optimization strategies and parallelization techniques are devised to accelerate the index construction process. To better support real-life scenarios, we further show how the index is leveraged to efficiently answer other types of queries, e.g., single-source reachability query and earliest-arrival path query. Extensive experiments on 16 real-world graphs demonstrate the effectiveness and efficiency of our proposed techniques.

The model of k -core and its decomposition have been applied in various areas, such as social networks, the world wide web, and biology. A graph can be decomposed into an elegant k -core hierarchy to facilitate cohesive subgraph discovery and network analysis. As many real-life graphs are fast evolving, existing works proposed efficient algorithms to maintain the coreness value of every vertex against structure changes. However, the maintenance of the k -core hierarchy in existing studies is not complete because the connections among different k -cores in the hierarchy are not considered. In this paper, we study hierarchical core maintenance which is to compute the k -core hierarchy incrementally against graph dynamics. The problem is challenging because the change of hierarchy may be large and complex even for a slight graph update. In order to precisely locate the area affected by graph dynamics, we conduct in-depth analyses on the structural properties of the hierarchy, and propose well-designed local update techniques. Our algorithms significantly outperform the baselines on runtime by up to 3 orders of magnitude, as demonstrated on 10 real-world large graphs.

A bipartite network is a network with two disjoint vertex sets and its edges only exist between vertices from different sets. It has received much interest since it can be used to model the relationship between two different sets of objects in many applications (e.g., the relationship between users and items in E-commerce). In this paper, we study the problem of efficient bi-triangle counting for a large bipartite network, where a bi-triangle is a cycle with three vertices from one vertex set and three vertices from another vertex set. Counting bi-triangles has found many real applications such as computing the transitivity coefficient and clustering coefficient for bipartite networks. To enable efficient bi-triangle counting, we first develop a baseline algorithm relying on the observation that each bi-triangle can be considered as the join of three wedges. Then, we propose a more sophisticated algorithm which regards a bi-triangle as the join of two super-wedges, where a wedge is a path with two edges while a super-wedge is a path with three edges. We further optimize the algorithm by ranking vertices according to their degrees. We have performed extensive experiments on both real and synthetic bipartite networks, where the largest one contains more than one billion edges, and the results show that the proposed solutions are up to five orders of magnitude faster than the baseline method.

Many real-world relationships between entities can be modeled as temporal graphs, where each edge is associated with a timestamp or a time interval representing its occurrence. K -core is a fundamental model used to capture cohesive subgraphs in a simple graph and have drawn much research attention over the last decade. Despite widespread research, none of the existing works support the efficient querying of historical k -cores in temporal graphs. In this paper, given an integer k and a time window, we study the problem of computing all k -cores in the graph snapshot over the time window. We propose an index-based solution and several pruning strategies to reduce the index size. We also design a novel algorithm to construct this index, whose running time is linear to the final index size. Lastly, we conducted extensive experiments on several real-world temporal graphs to show the high effectiveness of our index-based solution.

Driven by many real applications, we study the problem of seeded graph matching. Given two graphs and , and a small set of pre-matched node pairs where and , the problem is to identify a matching between and growing from , such that each pair in the matching corresponds to the same underlying entity. Recent studies on efficient and effective seeded graph matching have drawn a great deal of attention and many popular methods are largely based on exploring the similarity between local structures to identify matching pairs. While these recent techniques work provably well on random graphs, their accuracy is low over many real networks. In this work, we propose to utilize higher-order neighboring information to improve the matching accuracy and efficiency. As a result, a new framework of seeded graph matching is proposed, which employs Personalized PageRank (PPR) to quantify the matching score of each node pair. To further boost the matching accuracy, we propose a novel postponing strategy, which postpones the selection of pairs that have competitors with similar matching scores. We show that the postpone strategy indeed significantly improves the matching accuracy. To improve the scalability of matching large graphs, we also propose efficient approximation techniques based on algorithms for computing PPR heavy hitters. Our comprehensive experimental studies on large-scale real datasets demonstrate that, compared with state-of-the-art approaches, our framework not only increases the precision and recall both by a significant margin but also achieves speed-up up to more than one order of magnitude.

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.

Given a directed graph G , the directed densest subgraph (DDS) problem refers to the finding of a subgraph from G , whose density is the highest among all the subgraphs of G . The DDS problem is fundamental to a wide range of applications, such as fraud detection, community mining, and graph compression. However, existing DDS solutions suffer from efficiency and scalability problems: on a 3,000-edge graph, it takes three days for one of the best exact algorithms to complete. In this article, we develop an efficient and scalable DDS solution. We introduce the notion of [ x , y ]-core, which is a dense subgraph for G , and show that the densest subgraph can be accurately located through the [ x , y ]-core with theoretical guarantees. Based on the [ x , y ]-core, we develop exact and approximation algorithms. We further study the problems of maintaining the DDS over dynamic directed graphs and finding the weighted DDS on weighted directed graphs, and we develop efficient non-trivial algorithms to solve these two problems by extending our DDS algorithms. We have performed an extensive evaluation of our approaches on 15 real large datasets. The results show that our proposed solutions are up to six orders of magnitude faster than the state-of-the-art.

Entity alignment (EA) is the task of identifying the entities that refer to the same real-world object but are located in different knowledge graphs (KGs). For entities to be aligned, existing EA solutions treat them separately and generate alignment results as ranked lists of entities on the other side. Nevertheless, this decision-making paradigm fails to take into account the interdependence among entities. Although some recent efforts mitigate this issue by imposing the 1-to-1 constraint on the alignment process, they still cannot adequately model the underlying interdependence and the results tend to be sub-optimal. To fill in this gap, in this work, we delve into the dynamics of the decision-making process, and offer a reinforcement learning (RL)–based model to align entities collectively. Under the RL framework, we devise the coherence and exclusiveness constraints to characterize the interdependence and restrict collective alignment. Additionally, to generate more precise inputs to the RL framework, we employ representative features to capture different aspects of the similarity between entities in heterogeneous KGs, which are integrated by an adaptive feature fusion strategy. Our proposal is evaluated on both cross-lingual and mono-lingual EA benchmarks and compared against state-of-the-art solutions. The empirical results verify its effectiveness and superiority.

In this paper, we propose and study a novel cohesive subgraph model, named (k,p)-core, which is a maximal subgraph where each vertex has at least k neighbours and at least p fraction of its neighbours in the subgraph. The model is motivated by the finding that each user in a community should have at least a certain fraction p of neighbors inside the community to ensure user engagement, especially for users with large degrees. Meanwhile, the uniform degree constraint k, as applied in the k-core model, guarantees a minimum level of user engagement in a community, and is especially effective for users with small degrees. We propose an O(m) algorithm to compute a (k,p)-core with given k and p, and an O(dm) algorithm to decompose a graph by (k,p)-core, where m is the number of edges in the graph G and d is the degeneracy of G. A space efficient index is designed for time-optimal (k,p)-core query processing. Novel techniques are proposed for the maintenance of (k,p)-core index against graph dynamic. Extensive experiments on 8 reallife datasets demonstrate that our (k,p)-core model is effective and the algorithms are efficient.

Graph similarity search retrieves from a database all graphs whose edit distance (GED) to a query graph is within a threshold. As GED computation is NP-hard, the existing works adopt the filtering-and-verification paradigm to reduce the number of GED verifications, and they mainly focus on designing filtering techniques while using the now out-dated algorithm A*GED for verification. In this paper, we aim to speed up GED verification, which is orthogonal to the index structures used in the filtering phase. We propose a best-first search algorithm AStar+-LSa which improves A*GED by (1) reducing memory consumption, (2) tightening lower bound estimation, and (3) improving the time complexity for lower bound computation. We formally show that AStar+-LSa has a lower space and time complexity than A*GED. We further modify AStar+-LSa into a depth-first search algorithm to contrast these two search paradigms, and we extend our algorithms for exact GED computation. We conduct extensive empirical studies on real graph datasets, and show that our algorithm AStar+-LSa outperforms the state-of-the-art algorithms by several orders of magnitude for both GED verification and GED computation.

Structural node similarity is widely used in analyzing complex networks. As one of the structural node similarity metrics, role similarity has the good merit of indicating automorphism (isomorphism). Existing algorithms to compute role similarity (e.g., RoleSim and NED) suffer from severe performance bottlenecks, and thus cannot handle large real-world graphs. In this paper, we propose a new framework StructSim to compute nodes' role similarity. Under this framework, we prove that StructSim is guaranteed to be an admissible role similarity metric based on the maximum matching. While maximum matching is too costly to scale, we then devise the BinCount matching to speed up the computation. BinCount-based StructSim admits a precomputed index to query one single pair in O(k log D) time, where k is a small user-defined parameter and D is the maximum node degree. Extensive empirical studies show that StructSim is significantly faster than existing works for computing structural node similarities on the real-world graphs, with comparable effectiveness.

The mode of k-core and its hierarchical decomposition have been applied in many areas, such as sociology, the world wide web, and biology. Algorithms on related studies often need an input value of parameter k, while there is no existing solution other than manual selection. In this paper, given a graph and a scoring metric, we aim to efficiently find the best value of k such that the score of the k-core (or k-core set) is the highest. The problem is challenging because there are various community scoring metrics and the computation is costly on large datasets. With the well-designed vertex ordering techniques, we propose time and space optimal algorithms to compute the best k, which are applicable to most community metrics. The proposed algorithms can compute the score of every k-core (set) and can benefit the solutions to other k-core related problems. Extensive experiments are conducted on 10 real-world networks with size up to billion-scale, which validates both the efficiency of our algorithms and the effectiveness of the resulting k-cores.

Large networks with labeled nodes are prevalent in various applications, such as biological graphs, social networks, and e-commerce graphs. To extract insight from this rich information source, we propose MC-Explorer, which is an advanced analysis and visualization system. A highlight of MC-Explorer is its ability to discover motif-cliques from a graph with labeled nodes. A motif, such as a 3-node triangle, is a fundamental building block of a graph. A motif-clique is a "complete" subgraph in a network with respect to a desired higher-order connection pattern. For example, on a large biological graph, we found out some motif-cliques, which disclose new side effects of a drug, and potential drugs for healing diseases. MC-Explorer includes online and interactive facilities for exploring a large labeled network through the use of motif-cliques. We will demonstrate how MC-Explorer can facilitate the analysis and visualization of a labeled biological network.An online demo video of MC-Explorer can be accessed from https://www.dropbox.com/s/vkalumc28wqp8yl/demo.mov.

Approximate nearest neighbour search (ANNS) in high dimensional space is a fundamental problem in many applications, such as multimedia database, computer vision and information retrieval. Among many solutions, data-sensitive hashing-based methods are effective to this problem, yet few of them are designed for external storage scenarios and hence do not optimized for I/O efficiency during the query processing. In this paper, we introduce a novel data-sensitive indexing and query processing framework for ANNS with an emphasis on optimizing the I/O efficiency, especially, the sequential I/Os. The proposed index consists of several lists of point IDs, ordered by values that are obtained by learned hashing (i.e., mapping) functions on each corresponding data point. The functions are learned from the data and approximately preserve the order in the high-dimensional space. We consider two instantiations of the functions (linear and non-linear), both learned from the data with novel objective functions. We also develop an I/O efficient ANNS framework based on the index. Comprehensive experiments on six benchmark datasets show that our proposed methods with learned index structure perform much better than the state-of-the-art external memory-based ANNS methods in terms of I/O efficiency and accuracy.

Ubiquitous smart devices and high-quality wireless networks enable people to participate in spatial crowdsourcing tasks easily, which require workers to physically move to specific locations to conduct their assigned tasks. Spatial crowdsourcing has attracted much attention from both academia and industry. In this paper, we consider a spatial crowdsourcing scenario, where the tasks may have some dependencies among them. Specifically, one task can only be dispatched when its dependent tasks have already been assigned. In fact, task dependencies are quite common in many real-life applications, such as house repairing and holding sports games. We formally define the dependency-aware spatial crowdsourcing (DA-SC), which focuses on finding an optimal worker-and-task assignment under the constraints of dependencies, skills of workers, moving distances and deadlines to maximize the successfully assigned tasks. We prove that the DA-SC problem is NP-hard and thus intractable. Therefore, we propose two approximation algorithms, including a greedy approach and a game-theoretic approach, which can guarantee the approximate bounds of the results in each batch process. Through extensive experiments on both real and synthetic data sets, we demonstrate the efficiency and effectiveness of our DA-SC approaches.

Cohesive subgraph mining in bipartite graphs becomes a popular research topic recently. An important structure k-bitruss is the maximal cohesive subgraph where each edge is contained in at least k butterflies (i.e., (2,2)-bicliques). In this paper, we study the bitruss decomposition problem which aims to find all the k-bitrusses for k ≥ 0. The existing bottom-up techniques need to iteratively peel the edges with the lowest butterfly support. In this peeling process, these techniques are time-consuming to enumerate all the supporting butterflies for each edge. To relax this issue, we first propose a novel online index - the BE-Index which compresses butterflies into k-blooms (i.e., (2,k)-bicliques). Based on the BE-Index, the new bitruss decomposition algorithm BiT-BU is proposed, along with two batch-based optimizations, to accomplish the butterfly enumeration of the peeling process in an efficient way. Furthermore, the BiT-PC algorithm is devised which is more efficient against handling the edges with high butterfly supports. We theoretically show that our new algorithms significantly reduce the time complexities of the existing algorithms. Also, we conduct extensive experiments on real datasets and the results demonstrate that our new techniques can speed up the state-of-the-art techniques by up to two orders of magnitude.

Reachability is a fundamental problem in graph analysis. In applications such as social networks and collaboration networks, edges are always associated with timestamps. Most existing works on reachability queries in temporal graphs assume that two vertices are related if they are connected by a path with non-decreasing timestamps (time-respecting) of edges. This assumption fails to capture the relationship between entities involved in the same group or activity with no time-respecting path connecting them. In this paper, we define a new reachability model, called span-reachability, designed to relax the time order dependency and identify the relationship between entities in a given time period. We adopt the idea of two-hop cover and propose an index-based method to answer span-reachability queries. Several optimizations are also given to improve the efficiency of index construction and query processing. We conduct extensive experiments on 17 real-world datasets to show the efficiency of our proposed solution.

Recently, the topic of truss computation has gained plenty of attention, where the k-truss of a graph is the maximum subgraph in which each edge participates in at least (k-2) triangles. Existing solutions mainly focus on homogeneous networks, where vertices are of the same type, and thus cannot be applied to heterogeneous information networks which consist of multi-typed and interconnected objects, such as the bibliographic networks and knowledge graphs. In this paper, we study the problem of truss computation over HINs, which aims to find groups of vertices that are of the same type and densely connected. To model the relationship between two vertices of the same type, we adopt the well-known concept of meta-path, which is a sequence of vertex types and edge types between two given vertex types. We then introduce two kinds of HIN triangles for three vertices, regarding a specific meta-path P. The first one requires that each pair of vertices is connected by an instance of P, while the second one also has such a connectivity constraint but further needs that the three instances of P form a circle. Based on these two kinds of triangles, we propose two HIN truss models respectively. We further develop efficient truss computation algorithms. We have performed extensive experiments on five real large HINs, and the results show that the proposed solutions are highly effective and efficient.

With the prevalence of Internet access and user generated content, a large number of documents/records, such as news and web pages, have been continuously generated in an unprecedented manner. In this paper, we study the problem of efficient stream set similarity join over distributed systems, which has broad applications in data cleaning and data integration tasks, such as on-line near-duplicate detection. In contrast to prefix-based distribution strategy which is widely adopted in offline distributed processing, we propose a simple yet efficient length-based distribution framework which dispatches incoming records by their length. A load-aware length partition method is developed to find a balanced partition by effectively estimating local join cost to achieve good load balance. Our length-based scheme is surprisingly superior to its competitors since it has no replication, small communication cost, and high throughput. We further observe that the join results from the current incoming record can be utilized to guide the index construction, which in turn can facilitate the join processing of future records. Inspired by this observation, we propose a novel bundle-based join algorithm by grouping similar records on-the-fly to reduce filtering cost. A by-product of this algorithm is an efficient verification technique, which verifies a batch of records by utilizing their token differences to share verification costs, rather than verifying them individually. Extensive experiments conducted on Storm, a popular distributed stream processing system, suggest that our methods can achieve up to one order of magnitude throughput improvement over baselines.

Entity alignment (EA) identifies entities that refer to the same real-world object but locate in different knowledge graphs (KGs), and has been harnessed for KG construction and integration. When generating EA results, current solutions treat entities independently and fail to take into account the interdependence between entities. To fill this gap, we propose a collective EA framework. We first employ three representative features, i.e., structural, semantic and string signals, which are adapted to capture different aspects of the similarity between entities in heterogeneous KGs. In order to make collective EA decisions, we formulate EA as the classical stable matching problem, which is further effectively solved by deferred acceptance algorithm. Our proposal is evaluated on both cross-lingual and mono-lingual EA benchmarks against state-of-the-art solutions, and the empirical results verify its effectiveness and superiority.

In indexing a graph for distance queries, distance labeling is a common practice; in particular, 2-hop labeling which guarantees the exactness of the query results is widely adopted. When it comes to a massive real graph with a relatively large treewidth such as social networks and web graphs, however, 2-hop labeling can hardly be constructed due to the oversized index. This paper discloses the theoretical relationships between the graph treewidth and 2-hop labeling's index size and query time. To scale up distance labeling, this paper proposes Core-Tree (CT) Index to facilitate a critical and effective trade-off between the index size and query time. The reduced index size enables CT-Index to handle massive graphs that no existing approaches can process while the cost in the query time is negligible: the query time is below 0.4 milliseconds on all tested graphs including one graph with 5.5 billion edges.

The stability of a social network has been widely studied as an important indicator for both the network holders and the participants. Existing works on reinforcing networks focus on a local view, e.g., the anchored k-core problem aims to enlarge the size of the k-core with a fixed input k. Nevertheless, it is more promising to reinforce a social network in a global manner: considering the engagement of every user (vertex) in the network. Since the coreness of a user has been validated as the "best practice" for capturing user engagement, we propose and study the anchored coreness problem in this paper: anchoring a small number of vertices to maximize the coreness gain (the total increment of coreness) of all the vertices in the network. We prove the problem is NP-hard and show it is more challenging than the existing local-view problems. An efficient heuristic algorithm is proposed with novel techniques on pruning search space and reusing the intermediate results. Extensive experiments on real-life data demonstrate that our model is effective for reinforcing social networks and our algorithm is efficient.

Given a directed graph G, the directed densest subgraph (DDS) problem refers to the finding of a subgraph from G, whose density is the highest among all the subgraphs of G. The DDS problem is fundamental to a wide range of applications, such as fraud detection, community mining, and graph compression. However, existing DDS solutions suffer from efficiency and scalability problems: on a three-thousand-edge graph, it takes three days for one of the best exact algorithms to complete. In this paper, we develop an efficient and scalable DDS solution. We introduce the notion of [x, y]-core, which is a dense subgraph for G, and show that the densest subgraph can be accurately located through the [x, y]-core with theoretical guarantees. Based on the [x, y]-core, we develop exact and approximation algorithms. We have performed an extensive evaluation of our approaches on eight real large datasets. The results show that our proposed solutions are up to six orders of magnitude faster than the state-of-the-art.

Computing top-k nearest neighbors (kNN) is a fundamental problem in road networks. Existing solutions either need a complicated parameter configuration in index construction or incur high costs when scanning an unbounded number of vertices in query processing. In this paper, we propose a novel parameter-free index-based solution for the kNN query based on the concept of tree decomposition in large road networks. Based on our index structure, we propose an efficient and progressive algorithm that returns each result in a bounded delay. We also optimize the index structure, which improves the efficiency of both index construction and index maintenance in large road networks. We conduct extensive experiments to show the efficiency of our proposed algorithms and the effectiveness of our optimization techniques in real-world road networks from ten regions.

Clique is one of the most fundamental models for cohesive subgraph mining in network analysis. Existing clique model mainly focuses on unsigned networks. In real world, however, many applications are modeled as signed networks with positive and negative edges. As the signed networks hold their own properties different from the unsigned networks, the existing clique model is inapplicable for the signed networks. Motivated by this, we propose the balanced clique model that considers the most fundamental and dominant theory, structural balance theory, for signed networks, and study the maximal balanced clique enumeration problem which computes all the maximal balanced cliques in a given signed network. We show that the maximal balanced clique enumeration problem is NP-Hard. A straightforward solution for the maximal balanced clique enumeration problem is to treat the signed network as two unsigned networks and leverage the off-the-shelf techniques for unsigned networks. However, such a solution is inefficient for large signed networks. To address this problem, in this paper, we first propose a new maximal balanced clique enumeration algorithm by exploiting the unique properties of signed networks. Based on the new proposed algorithm, we devise two optimization strategies to further improve the efficiency of the enumeration. We conduct extensive experiments on large real and synthetic datasets. The experimental results demonstrate the efficiency, effectiveness and scalability of our proposed algorithms.

Recently, the topic of community search (CS) has gained plenty of attention. Given a query vertex, CS looks for a dense subgraph that contains it. Existing studies mainly focus on homogeneous graphs in which vertices are of the same type, and cannot be directly applied to heterogeneous information networks (HINs) that consist of multi-typed, interconnected objects, such as the bibliographic networks and knowledge graphs. In this paper, we study the problem of community search over large HINs; that is, given a query vertex q , find a community from an HIN containing q , in which all the vertices are with the same type of q and have close relationships. To model the relationship between two vertices of the same type, we adopt the well-known concept of meta-path , which is a sequence of relations defined between different types of vertices. We then measure the cohesiveness of the community by extending the classic minimum degree metric with a meta-path. We further propose efficient query algorithms for finding communities using these cohesiveness metrics. We have performed extensive experiments on five real large HINs, and the results show that the proposed solutions are effective for searching communities. Moreover, they are much faster than the baseline solutions.

Supergraph search is one of fundamental graph query processing problems in many application domains. Given a query graph and a set of data graphs, supergraph search is to find all the data graphs contained in the query graph as subgraphs. In existing algorithms, index construction or filtering approaches are computationally expensive, and search methods can cause redundant computations. In this paper, we introduce four new concepts to address these limitations: (1) DAG integration, (2) dynamic programming between integrated DAG and graph, (3) active-first search, and (4) relevance-size order, which together lead to a much faster and scalable algorithm for supergraph search. Extensive experiments with real datasets show that our approach outperforms state-of-the-art algorithms by up to orders of magnitude in terms of indexing time and query processing time.

Maximum biclique search, which finds the biclique with the maximum number of edges in a bipartite graph, is a fundamental problem with a wide spectrum of applications in different domains, such as E-Commerce, social analysis, web services, and bioinformatics. Unfortunately, due to the difficulty of the problem in graph theory, no practical solution has been proposed to solve the issue in large-scale real-world datasets. Existing techniques for maximum clique search on a general graph cannot be applied because the search objective of maximum biclique search is two-dimensional, i.e., we have to consider the size of both parts of the biclique simultaneously. In this paper, we divide the problem into several subproblems each of which is specified using two parameters. These subproblems are derived in a progressive manner, and in each subproblem we can restrict the search in a very small part of the original bipartite graph. We prove that a logarithmic number of subproblems is enough to guarantee the algorithm correctness. To minimize the computational cost, we show how to reduce significantly the bipartite graph size for each subproblem while preserving the maximum biclique satisfying certain constraints by exploring the properties of one-hop and two-hop neighbors for each vertex. We use several real datasets from various application domains, one of which contains over 300 million vertices and 1.3 billion edges, to demonstrate the high efficiency and scalability of our proposed solution. It is reported that 50% improvement on recall can be achieved after applying our method in Alibaba Group to identify the fraudulent transactions in their e-commerce networks. This further demonstrates the usefulness of our techniques in practice.

Computing the shortest path between two vertices is a fundamental problem in road networks that is applied in a wide variety of applications. To support efficient shortest path query processing, a plethora of index-based methods have been proposed in the literature, but few of them can support dynamic road networks commonly encountered in practice, as their corresponding index structures cannot be efficiently maintained when the input road network is dynamically updated. Motivated by this, we study the shortest path index maintenance problem on dynamic road networks in this paper. We adopt Contraction Hierarchies (CH) as our underlying shortest path computation method because of its outstanding overall performance in pre-processing time, space cost, and query processing time and aim to design efficient algorithms to maintain the index structure, shortcut index , of CH when the input road network is dynamically updated. To achieve this goal, we propose a shortcut-centric paradigm focusing on exploring a small number of shortcuts to maintain the shortcut index. Following this paradigm, we design an auxiliary data structure named SS-Graph and propose a shortcut weight propagation mechanism based on the SS-Graph. With them, we devise efficient algorithms to maintain the shortcut index in the streaming update and batch update scenarios with non-trivial theoretical guarantees. We experimentally evaluate our algorithms on real road networks and the results demonstrate that our approach achieves 2--3 orders of magnitude speedup compared to the state-of-the-art algorithm for the streaming update.

In this paper, we study the problem of label-constrained reachability (LCR) query which is fundamental in many applications with directed edge-label graphs. Although the classical reachability query (i.e., reachability query without label constraint) has been extensively studied, LCR query is much more challenging because the number of possible label constraint set is exponential to the size of the labels. We observe that the existing techniques for LCR queries only construct partial index for better scalability, and their worst query time is not guaranteed and could be the same as an online breadth-first search (BFS). In this paper, we propose novel label-constrained 2-hop indexing techniques with novel pruning rules and order strategies. It is shown that our worst query time could be bounded by the in-out index entry size. With all these techniques, comprehensive experiments show that our proposed methods significantly outperform the state-of-the-art technique in terms of query response time (up to 5 orders of magnitude speedup), index size and index construction time. In particular, our proposed method can answer LCR queries within microsecond over billion-scale graphs in a single machine.

The dramatic development of shared mobility in food delivery, ridesharing, and crowdsourced parcel delivery has drawn great concerns. Specifically, shared mobility refers to transferring or delivering more than one passenger/package together when their traveling routes have common sub-routes or can be shared. A core problem for shared mobility is to plan a route for each driver to fulfill the requests arriving dynamically with given objectives. Previous studies greedily and incrementally insert each newly coming request to the most suitable worker with a minimum travel cost increase, which only considers the current situation and thus not optimal. In this paper, we propose a demand-aware route planning (DARP) for shared mobility services. Based on prediction, DARP tends to make optimal route planning with more information about requests in the future. We prove that the DARP problem is NP-hard, and further show that there is no polynomial-time deterministic algorithm with a constant competitive ratio for the DARP problem unless P=NP. Hence, we devise an approximation algorithm to realize the insertion operation for our goal. With the insertion algorithm, we devise a prediction based solution for the DARP problem. Extensive experiment results on real datasets validate the effectiveness and efficiency of our technique.

Nearest neighbor search is a fundamental and essential operation in applications from many domains, such as databases, machine learning, multimedia, and computer vision. Because exact searching results are not efficient for a high-dimensional space, a lot of efforts have turned to approximate nearest neighbor search. Although many algorithms have been continuously proposed in the literature each year, there is no comprehensive evaluation and analysis of their performance. In this paper, we conduct a comprehensive experimental evaluation of many state-of-the-art methods for approximate nearest neighbor search. Our study (1) is cross-disciplinary (i.e., including 19 algorithms in different domains, and from practitioners) and (2) has evaluated a diverse range of settings, including 20 datasets, several evaluation metrics, and different query workloads. The experimental results are carefully reported and analyzed to understand the performance results. Furthermore, we propose a new method that achieves both high query efficiency and high recall empirically on majority of the datasets under a wide range of settings.

Graph pattern matching is one of the most fundamental problems in graph database and is associated with a wide spectrum of applications. Due to its computational intensiveness, researchers have primarily devoted their efforts to improving the performance of the algorithm while constraining the graphs to have singular labels on vertices (edges) or no label. Whereas in practice graphs are typically associated with rich properties, thus the main focus in the industry is instead on powerful query languages that can express a sufficient number of pattern matching scenarios. We demo PatMat in this work to glue together the academic efforts on performance and the industrial efforts on expressiveness. To do so, we leverage the state-of-the-art join-based algorithms in the distributed contexts and Cypher query language - the most widely-adopted declarative language for graph pattern matching. The experiments demonstrate how we are capable of turning complex Cypher semantics into a distributed solution with high performance.

In many applications, graphs often involve the nodes with multi-dimensional numerical attributes, and it is desirable to retrieve a group of nodes that are both highly connected (e.g., clique) and optimal according to some ranking functions. It is well known that the skyline returns candidates for the optimal objects when ranking functions are not specified. Motivated by this, in this paper we formulate the novel model of skyline k-cliques over multi-valued attributed graphs and develop efficient algorithms to conduct the computation. To verify the group based dominance between two k-cliques, we make use of maximum bipartite matching and develop a set of optimization techniques to improve the verification efficiency. Then, a progressive computation algorithm is developed which enumerates the k-cliques in an order such that a k-clique is guaranteed not to be dominated by those generated after it. Novel pruning and early termination techniques are developed to exclude unpromising nodes or cliques by investigating the structural and attribute properties of the multi-valued attributed graph. Empirical studies on four real datasets demonstrate the effectiveness of the skyline k-clique model and the efficiency of the novel computing techniques.

Distance labeling approaches are widely adopted to speed up the online performance of shortest distance queries. The construction of the distance labeling, however, can be exhaustive especially on big graphs. For a major category of large graphs, small-world networks, the state-of-the-art approach is Pruned Landmark Labeling (PLL). PLL prunes distance labels based on a node order and directly constructs the pruned labels by performing breadth-first searches in the node order. The pruning technique, as well as the index construction, has a strong sequential nature which hinders PLL from being parallelized. It becomes an urgent issue on massive small-world networks whose index can hardly be constructed by a single thread within a reasonable time. This paper scales distance labeling on small-world networks by proposing a Parallel Shortest-distance Labeling (PSL) scheme and further reducing the index size by exploiting graph and label properties. PSL insightfully converts the PLL's node-order dependency to a shortest-distance dependence, which leads to a propagation-based parallel labeling in D rounds where D denotes the diameter of the graph. Extensive experimental results verify our efficiency on billion-scale graphs and near-linear speedup in a multi-core environment.

The problem of computing (α, β)-core in a bipartite graph for given α and β is a fundamental problem in bipartite graph analysis and can be used in many applications such as online group recommendation, fraudsters detection, etc. Existing solution to computing (α, β)-core needs to traverse the entire bipartite graph once. Considering the real bipartite graph can be very large and the requests to compute (α, β)-core can be issued frequently in real applications, the existing solution is too expensive to compute the (α, β)-core. In this paper, we present an efficient algorithm based on a novel index such that the algorithm runs in linear time regarding the result size (thus, the algorithm is optimal since it needs at least linear time to output the result). We prove that the index only requires O(m) space where m is the number of edges in the bipartite graph. Moreover, we devise an efficient algorithm with time complexity O(δ·m) for index construction where δ is bounded by √m and is much smaller than √m in practice. We also discuss efficient algorithms to maintain the index when the bipartite graph is dynamically updated and parallel implementation of the index construction algorithm. The experimental results on real and synthetic graphs (more than 1 billion edges) demonstrate that our algorithms achieve up to 5 orders of magnitude speedup for computing (α, β)-core and up to 3 orders of magnitude speedup for index construction, respectively, compared with existing techniques.

Abstract In this paper, we study the problem of selectivity estimation on set containment search. Given a query record Q and a record dataset $${\mathcal {S}}$$ S , we aim to accurately and efficiently estimate the selectivity of set containment search of query Q over $${\mathcal {S}}$$ S . We first extend existing distinct value estimating techniques to solve this problem and develop an inverted list and G-KMV sketch-based approach IL-GKMV. We analyze that the performance of IL-GKMV degrades with the increase in vocabulary size. Motivated by limitations of existing techniques and the inherent challenges of the problem, we resort to developing effective and efficient sampling approaches and propose an ordered trie structure-based sampling approach named OT-Sampling. OT-Sampling partitions records based on element frequency and occurrence patterns and is significantly more accurate compared with simple random sampling method and IL-GKMV. To further enhance the performance, a divide-and-conquer-based sampling approach, DC-Sampling, is presented with an inclusion/exclusion prefix to explore the pruning opportunities. Meanwhile, we consider weighted set containment selectivity estimation and devise stratified random sampling approach named StrRS. We theoretically analyze the proposed techniques regarding various accuracy estimators. Our comprehensive experiments on nine real datasets verify the effectiveness and efficiency of our proposed techniques.

Densest subgraph discovery (DSD) is a fundamental problem in graph mining. It has been studied for decades, and is widely used in various areas, including network science, biological analysis, and graph databases. Given a graph G , DSD aims to find a subgraph D of G with the highest density (e.g., the number of edges over the number of vertices in D ). Because DSD is difficult to solve, we propose a new solution paradigm in this paper. Our main observation is that the densest subgraph can be accurately found through a k -core (a kind of dense subgraph of G ), with theoretical guarantees. Based on this intuition, we develop efficient exact and approximation solutions for DSD. Moreover, our solutions are able to find the densest subgraphs for a wide range of graph density definitions, including clique-based- and general pattern-based density. We have performed extensive experimental evaluation on both real and synthetic datasets. Our results show that our algorithms are up to four orders of magnitude faster than existing approaches.

Recently there emerge many distributed algorithms that aim at solving subgraph matching at scale. Existing algorithm-level comparisons failed to provide a systematic view of distributed subgraph matching mainly due to the intertwining of strategy and optimization. In this paper, we identify four strategies and three general-purpose optimizations from representative state-of-the-art algorithms. We implement the four strategies with the optimizations based on the common Timely dataflow system for systematic strategy-level comparison. Our implementation covers all representative algorithms. We conduct extensive experiments for both unlabelled matching and labelled matching to analyze the performance of distributed subgraph matching under various settings, which is finally summarized as a practical guide.

As one of the most representative cohesive subgraph models,k-core model has recently received significant attention in the literature. In this paper, we investigate the problem of the minimumk-core search: given a graphG, an integerkand a set of query verticesQ= {q}, we aim to find the smallestk-core subgraph containing every query vertexqϵQ.It has been shown that this problem is NP-hard with a huge search space, and it is very challenging to find the optimal solution. There are several heuristic algorithms for this problem, but they rely on simple scoring functions and there is no guarantee as to the size of the resulting subgraph, compared with the optimal solution. Our empirical study also indicates that the size of their resulting subgraphs may be large in practice. In this paper, we develop an effective and efficient progressive algorithm, namelyPSA, to provide a good trade-off between the quality of the result and the search time. Novel lower and upper bound techniques for the minimumk-core search are designed. Our extensive experiments on 12 real-life graphs demonstrate the effectiveness and efficiency of the new techniques.

Bipartite networks are of great importance in many real-world applications. In bipartite networks, butterfly (i.e., a complete 2 x 2 biclique) is the smallest non-trivial cohesive structure and plays a key role. In this paper, we study the problem of efficient counting the number of butterflies in bipartite networks. The most advanced techniques are based on enumerating wedges which is the dominant cost of counting butterflies. Nevertheless, the existing algorithms cannot efficiently handle large-scale bipartite networks. This becomes a bottleneck in large-scale applications. In this paper, instead of the existing layer-priority-based techniques, we propose a vertex-priority-based paradigm BFC-VP to enumerate much fewer wedges; this leads to a significant improvement of the time complexity of the state-of-the-art algorithms. In addition, we present cache-aware strategies to further improve the time efficiency while theoretically retaining the time complexity of BFC-VP. Moreover, we also show that our proposed techniques can work efficiently in external and parallel contexts. Our extensive empirical studies demonstrate that the proposed techniques can speed up the state-of-the-art techniques by up to two orders of magnitude for the real datasets.

Depth-first search (DFS) is a fundamental and important algorithm in graph analysis. It is the basis of many graph algorithms such as computing strongly connected components, testing planarity, and detecting biconnected components. The result of a DFS is normally shown as a DFS-Tree. Given the frequent updates in many real-world graphs (e.g., social networks and communication networks), we study the problem of DFS-Tree maintenance in dynamic directed graphs. In the literature, most works focus on the DFS-Tree maintenance problem in undirected graphs and directed acyclic graphs. However, their methods cannot easily be applied in the case of general directed graphs. Motivated by this, we propose a framework and corresponding algorithms for both edge insertion and deletion in general directed graphs. We further give several optimizations to speed up the algorithms. We conduct extensive experiments on 12 real-world datasets to show the efficiency of our proposed algorithms.

Uncertainty is intrinsic to a wide spectrum of real-life applications, which inevitably applies to graph data. Representative uncertain graphs are seen in bio-informatics, social networks, etc. This paper motivates the problem of frequent subgraph mining on single uncertain graphs, and investigates two different - probabilistic and expected - semantics in terms of support definitions. First, we present an enumeration-evaluation algorithm to solve the problem under probabilistic semantics. By showing the support computation under probabilistic semantics is #P-complete, we develop an approximation algorithm with accuracy guarantee for efficient problem-solving. To enhance the solution, we devise computation sharing techniques to achieve better mining performance. Afterwards, the algorithm is extended in a similar flavor to handle the problem under expected semantics, where checkpoint-based pruning and validation techniques are integrated. Experiment results on real-life datasets confirm the practical usability of the mining algorithms.

Supergraph search is a fundamental problem in graph databases that is widely applied in many application scenarios. Given a graph database and a query-graph, supergraph search retrieves all data-graphs contained in the query-graph from the graph database. Most existing solutions for supergraph search follow the pruning-and-verification framework, which prune false answers based on features in the pruning phase and perform subgraph isomorphism testings on the remaining graphs in the verification phase. However, they are not scalable to handle large-sized data-graphs and query-graphs due to three drawbacks. First, they rely on a frequent subgraph mining algorithm to select features which is expensive and cannot generate large features. Second, they require a costly verification phase. Third, they process features in a fixed order without considering their relationships to the query-graph. In this paper, we address the three drawbacks and propose new indexing and query processing algorithms. In indexing, we select features directly from the data-graphs without expensive frequent subgraph mining. The features form a feature-tree that contains all-sized features and both the cost sharing and pruning power of the features are considered. In query processing, we propose a new algorithm, where the order to process features is query-dependent by considering both the cost sharing and the pruning power. We explore two optimization strategies to further improve the algorithm efficiency. The first strategy applies a lightweight graph compression technique and the second strategy optimizes the inclusion of answers. We further introduce how to efficiently maintain the index incrementally when the graph database is updated dynamically. Moreover, we propose an approximation approach to significantly reduce the computational cost for large data-graphs and/or query-graphs while preserving a high result quality. Finally, we conduct extensive performance studies on two real large datasets to demonstrate the efficiency and effectiveness of our algorithms.

Core decomposition is a fundamental graph problem with a large number of applications. Most existing approaches for core decomposition assume that the graph is kept in memory of a machine. Nevertheless, many real-world graphs are too big to reside in memory. In this paper, we study I/O efficient core decomposition following a semi-external model, which only allows node information to be loaded in memory. We propose a semi-external algorithm and an optimized algorithm for I/O efficient core decomposition. To handle dynamic graph updates, we firstly show that our algorithm can be naturally extended to handle edge deletion. Then, we propose an I/O efficient core maintenance algorithm to handle edge insertion, and an improved algorithm to further reduce I/O and CPU cost. In addition, based on our core decomposition algorithms, we further propose an I/O efficient semi-external algorithm for degeneracy ordering, which is an important graph problem that is highly related to core decomposition. We also consider how to maintain the degeneracy order. We conduct extensive experiments on 12 real large graphs. Our optimal core decomposition algorithm significantly outperforms the existing I/O efficient algorithm in terms of both processing time and memory consumption. They are very scalable to handle web-scale graphs. As an example, we are the first to handle a web graph with 978.5 million nodes and 42.6 billion edges using less than 4.2 GB memory. We also show that our proposed algorithms for degeneracy order computation and maintenance can handle big graphs efficiently with small memory overhead.

Given a graph, how can we quantify similarity between two nodes in an effective and scalable way? SimRank is an attractive measure of pairwise similarity based on graph topologies. Its underpinning philosophy that “two nodes are similar if they are pointed to (have incoming edges) from similar nodes” can be regarded as an aggregation of similarities based on incoming paths. Despite its popularity in various applications (e.g., web search and social networks), SimRank has an undesirable trait, i.e., “zero-similarity”: it accommodates only the paths of equal length from a common “center” node, whereas a large portion of other paths are fully ignored. In this paper, we propose an effective and scalable similarity model, SimRank*, to remedy this problem. (1) We first provide a sufficient and necessary condition of the “zero-similarity” problem that exists in Jeh and Widom’s SimRank model, Li et al. ’s SimRank model, Random Walk with Restart (RWR), and ASCOS++. (2) We next present our treatment, SimRank*, which can resolve this issue while inheriting the merit of the simple SimRank philosophy. (3) We reduce the series form of SimRank* to a closed form, which looks simpler than SimRank but which enriches semantics without suffering from increased computational overhead. This leads to an iterative form of SimRank*, which requires O(Knm) time and $$O(n^2)$$ memory for computing all $$(n^2)$$ pairs of similarities on a graph of n nodes and m edges for K iterations. (4) To improve the computational time of SimRank* further, we leverage a novel clustering strategy via edge concentration. Due to its NP-hardness, we devise an efficient heuristic to speed up all-pairs SimRank* computation to $$O(Kn{\tilde{m}})$$ time, where $${\tilde{m}}$$ is generally much smaller than m. (5) To scale SimRank* on billion-edge graphs, we propose two memory-efficient single-source algorithms, i.e., ss-gSR* for geometric SimRank*, and ss-eSR* for exponential SimRank*, which can retrieve similarities between all n nodes and a given query on an as-needed basis. This significantly reduces the $$O(n^2)$$ memory of all-pairs search to either $$O(Kn + {\tilde{m}})$$ for geometric SimRank*, or $$O(n + {\tilde{m}})$$ for exponential SimRank*, without any loss of accuracy, where $${\tilde{m}} \ll n^2$$ . (6) We also compare SimRank* with another remedy of SimRank that adds self-loops on each node and demonstrate that SimRank* is more effective. (7) Using real and synthetic datasets, we empirically verify the richer semantics of SimRank*, and validate its high computational efficiency and scalability on large graphs with billions of edges.

In social networks, dense relationships among users contribute to stable networks. Breakdowns of some relationships may cause users to leave the network hence decrease the network stability. A popular metric to measure the stability of a network is k-core, i.e., the maximal subgraph of a social network in which each node has at least k neighbors. In this paper, we propose a novel problem, called k-core minimization. Given a graph G, an integer k and a budget b, we aim to identify a set B of edges with size b, so that we can get the minimum k-core by deleting B from G. We first formally define the problem and prove its NP-hardness. Then a baseline greedy algorithm is proposed. To handle large graphs, an optimized algorithm, named KC-Edge, is developed by adopting novel pruning rules. Finally, comprehensive experiments on 6 real social networks are conducted to demonstrate the efficiency and effectiveness of our proposed methods.

This paper studies the efficiency issue on computing the exact eccentricity-distribution of a small-world network. Eccentricity-distribution reflects the importance of each node in a graph, which is beneficial for graph analysis. Moreover, it is key to computing two fundamental graph characters: diameter and radius. Existing eccentricity computation algorithms, however, are either inefficient in handling large-scale networks emerging nowadays in practice or approximate algorithms that are inappropriate to small-world networks. We propose an efficient approach for exact eccentricity computation. Our approach is based on a plethora of insights on the bottleneck of the existing algorithms — one-node eccentricity computation and the upper/lower bounds update. Extensive experiments demonstrate that our approach outperforms the state-of-the-art up to three orders of magnitude on real large small-world networks.

As uncertainty is inherent in a wide spectrum of graph applications such as social network and brain network, it is highly demanded to re-visit classical graph problems in the context of uncertain graphs. Driven by real-applications, in this paper, we study the problem of k-core computation on uncertain graphs and propose a new model, namely (k,θ)-core, which consists of nodes with probability at least θ to be k-core member in the uncertain graph. We show the computation of (k,θ)-core is NP-hard, and hence resort to sampling based methods. Effective and efficient pruning techniques are proposed to significantly reduce the candidate size. To further reduce the cost of k-core computation on multiple sampled graphs, we design a k-core membership check algorithm following a novel expansion-based search paradigm. Extensive experiments on real-life graphs demonstrate the effectiveness and efficiency of our proposed techniques.

A similarity 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, including image retrieval, near-duplicate Web page detection, and machine learning. State-of-the-art approaches to answering such queries are mainly based on the pigeonhole principle to generate a set of candidates and then verify them. We observe that the constraint based on the pigeonhole principle is not always tight and hence may bring about unnecessary candidates. We also observe that the distribution in real data is often skew, but most existing solutions adopt a simple equiwidth partitioning and allocate the same threshold to all the partitions, and hence fail to exploit the data skewness to optimize the query processing. In this paper, we propose a new form of the pigeonhole principle which allows variable partition size and threshold. Based on the new principle, we first develop a tight constraint of candidates, and then devise cost-aware methods for dimension partitioning and threshold allocation to optimize query processing. 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.

Driven by real-life applications in geo-social networks, in this paper, we investigate the problem of computing the radius-bounded k-cores (RB-k-cores) that aims to find cohesive subgraphs satisfying both social and spatial constraints on large geo-social networks. In particular, we use k-core to ensure the social cohesiveness and we use a radius-bounded circle to restrict the locations of users in a RB-k-core. We explore several algorithmic paradigms to compute RB-k-cores, including a triple vertex-based paradigm, a binary-vertex-based paradigm, and a paradigm utilizing the concept of rotating circles. The rotating circle-based paradigm is further enhanced with several pruning techniques to achieve better efficiency. The experimental studies conducted on both real and synthetic datasets demonstrate that our proposed rotating-circle-based algorithms can compute all RB-k-cores very efficiently. Moreover, it can also be used to compute the minimum-circle-bounded k-core and significantly outperforms the existing techniques for computing the minimum circle-bounded k-core.

User engagement and tie strength are fundamental and important components in social networks. The model of k-truss not only captures actively engaged users, but also ensures strong tie strength among these users. It motivates us to utilize the model of k-truss in preventing network unraveling, which simultaneously considers both of the basic components. In this paper, we propose and investigate the anchored k-truss problem to reinforce a network by anchoring critical users who can significantly stop the unraveling. We prove the problem is NP-hard for k ≥ 4. A fast edge deletion order based algorithm, named AKT, is proposed with efficient candidate exploration and pruning techniques based on the order. Comprehensive experiments on 10 real-life graphs demonstrate the effectiveness of our model and the efficiency of our methods.

Computing the shortest distance between two vertices is a fundamental problem in road networks. Since a direct search using the Dijkstra's algorithm results in a large search space, researchers resort to indexing-based approaches. State-of-the-art indexing-based solutions can be categorized into hierarchy-based solutions and hopbased solutions. However, the hierarchy-based solutions require a large search space for long-distance queries while the hop-based solutions result in a high computational waste for short-distance queries. To overcome the drawbacks of both solutions, in this paper, we propose a novel hierarchical 2-hop index (H2H-Index) which assigns a label for each vertex and at the same time preserves a hierarchy among all vertices. With the H2H-Index, we design an efficient query processing algorithm with performance guarantees by visiting part of the labels for the source and destination based on the vertex hierarchy. We also propose an algorithm to construct the H2H-Index based on distance preserved graphs. The algorithm is further optimized by computing the labels based on the partially computed labels of other vertices. We conducted extensive performance studies using large real road networks including the whole USA road network. The experimental results demonstrate that our approach can achieve a speedup of an order of magnitude in query processing compared to the state-of-the-art while consuming comparable indexing time and index size.

Community search over large graphs is a fundamental problem in graph analysis. Recent studies propose to compute top- k influential communities, where each reported community not only is a cohesive subgraph but also has a high influence value. The existing approaches to the problem of top- k influential community search can be categorized as index-based algorithms and online search algorithms without indexes. The index-based algorithms, although being very efficient in conducting community searches, need to pre-compute a special-purpose index and only work for one built-in vertex weight vector. In this paper, we investigate online search approaches and propose an instance-optimal algorithm LocalSearch whose time complexity is linearly proportional to the size of the smallest subgraph that a correct algorithm needs to access without indexes. In addition, we also propose techniques to make LocalSearch progressively compute and report the communities in decreasing influence value order such that k does not need to be specified. Moreover, we extend our framework to the general case of top- k influential community search regarding other cohesiveness measures. Extensive empirical studies on real graphs demonstrate that our algorithms outperform the existing online search algorithms by several orders of magnitude.

As graph data is prevalent for an increasing number of Internet applications, continuously monitoring structural patterns in dynamic graphs in order to generate real-time alerts and trigger prompt actions becomes critical for many applications. In this paper, we present a new system GraphS to efficiently detect constrained cycles in a dynamic graph, which is changing constantly, and return the satisfying cycles in real-time. A hot point based index is built and efficiently maintained for each query so as to greatly speed-up query time and achieve high system throughput. The GraphS system is developed at Alibaba to actively monitor various online fraudulent activities based on cycle detection. For a dynamic graph with hundreds of millions of edges and vertices, the system is capable to cope with a peak rate of tens of thousands of edge updates per second and find all the cycles with predefined constraints with a 99.9% latency of 20 milliseconds.

SimRank is an appealing pair-wise similarity measure based on graph structure. It iteratively follows the intuition that two nodes are assessed as similar if they are pointed to by similar nodes. Many real graphs are large, and links are constantly subject to minor changes. In this article, we study the efficient dynamical computation of all-pairs SimRanks on time-varying graphs. Existing methods for the dynamical SimRank computation [e.g., LTSF (Shao et al. in PVLDB 8(8):838–849, 2015) and READS (Zhang et al. in PVLDB 10(5):601–612, 2017)] mainly focus on top-k search with respect to a given query. For all-pairs dynamical SimRank search, Li et al.’s approach (Li et al. in EDBT, 2010) was proposed for this problem. It first factorizes the graph via a singular value decomposition (SVD) and then incrementally maintains such a factorization in response to link updates at the expense of exactness. As a result, all pairs of SimRanks are updated approximately, yielding $$O({r}^{4}n^2)$$ time and $$O({r}^{2}n^2)$$ memory in a graph with n nodes, where r is the target rank of the low-rank SVD. Our solution to the dynamical computation of SimRank comprises of five ingredients: (1) We first consider edge update that does not accompany new node insertions. We show that the SimRank update $${\varvec{\Delta }}{} \mathbf{S}$$ in response to every link update is expressible as a rank-one Sylvester matrix equation. This provides an incremental method requiring $$O(Kn^2)$$ time and $$O(n^2)$$ memory in the worst case to update $$n^2$$ pairs of similarities for K iterations. (2) To speed up the computation further, we propose a lossless pruning strategy that captures the “affected areas” of $${\varvec{\Delta }}{} \mathbf{S}$$ to eliminate unnecessary retrieval. This reduces the time of the incremental SimRank to $$O(K(m+|{\textsf {AFF}}|))$$ , where m is the number of edges in the old graph, and $$|{\textsf {AFF}}| \ (\le n^2)$$ is the size of “affected areas” in $${\varvec{\Delta }}{} \mathbf{S}$$ , and in practice, $$|{\textsf {AFF}}| \ll n^2$$ . (3) We also consider edge updates that accompany node insertions, and categorize them into three cases, according to which end of the inserted edge is a new node. For each case, we devise an efficient incremental algorithm that can support new node insertions and accurately update the affected SimRanks. (4) We next study batch updates for dynamical SimRank computation, and design an efficient batch incremental method that handles “similar sink edges” simultaneously and eliminates redundant edge updates. (5) To achieve linear memory, we devise a memory-efficient strategy that dynamically updates all pairs of SimRanks column by column in just $$O(Kn+m)$$ memory, without the need to store all $$(n^2)$$ pairs of old SimRank scores. Experimental studies on various datasets demonstrate that our solution substantially outperforms the existing incremental SimRank methods and is faster and more memory-efficient than its competitors on million-scale graphs.

This paper studies the problem of top-k structural diversity search, which is to compute k users with the highest structural diversities that is measured by the number of connected components in the neighborhood of a user. As the existing algorithms are not scalable for processing large graphs due to their limits, in this paper we propose a scalable algorithm Div-TriE to improve the efficiency. Div-TriE has two optimal features compared with the existing algorithms. Firstly, we show that as a key building block, we only need to enumerate each triangle at most once in Div-TriE, in contrast to the up-to three times in the existing techniques. Secondly, we develop e cient techniques so that the computation against each enumerated triangle is (amortized) constant, in contrast to the non-constant costs in the corresponding costs of the existing techniques. Extensive experimental results on real graphs show that Div-TriE outperforms the existing techniques by one order of magnitude.

Given a positive integer k, a social network G and a certain propagation model M, influence maximization aims to find a set of k nodes that has the largest influence spread. The state-of-the-art method IMM is based on the reverse influence sampling (RIS) framework. By using the martingale technique, it greatly outperforms the previous methods in efficiency. However, IMM still has limitations in scalability due to the high overhead of deciding a tight sample size. In this paper, instead of spending the effort on deciding a tight sample size, we present a novel bottomk sketch based RIS framework, namely BKRIS, which brings the order of samples into the RIS framework. By applying the sketch technique, we can derive early termination conditions to significantly accelerate the seed set selection procedure. Moreover, we provide several optimization techniques to reduce the cost of generating and processing samples. Finally, we conduct experiments over 10 real social networks to demonstrate the efficiency and effectiveness of the proposed method. Further details are reported in [1].

In this paper, we study the problem of set containment join. Given two collections R and S of records, the set containment join R ∞I⊆ S retrieves all record pairs {(r, s)} ∈ R × S such that r ⊆ s. This problem has been extensively studied in the literature and has many important applications in commercial and scientific fields. Recent research focuses on the in-memory set containment join algorithms, and several techniques have been developed following intersection-oriented or union-oriented computing paradigms. Nevertheless, we observe that two computing paradigms have their limits due to the nature of the intersection and union operators. Particularly, intersection-oriented method relies on the intersection of the relevant inverted lists built on the elements of S. A nice property of the intersection-oriented method is that the join computation is verification free. However, the number of records explored during the join process may be large because there are multiple replicas for each record in S. On the other hand, the union-oriented method generates a signature for each record in R and the candidate pairs are obtained by the union of the inverted lists of the relevant signatures. The candidate size of the union-oriented method is usually small because each record contributes only one replica in the index. Unfortunately, union-oriented method needs to verify the candidate pairs, which may be cost expensive especially when the join result size is large. As a matter of fact, the state-of-the-art union-oriented solution is not competitive compared to the intersection-oriented ones. In this paper, we propose a new union-oriented method, namely TT-Join, which not only enhances the advantage of the previous union-oriented methods but also integrates the goodness of intersection-oriented methods by imposing a variant of prefix tree structure. We conduct extensive experiments on 20 real-life datasets by comparing our method with 7 existing methods. The experiment results demonstrate that TT-Join significantly outperforms the existing algorithms on most of the datasets, and can achieve up to two orders of magnitude speedup.

In many modern applications, input data is represented as matrices and often arrives continuously. The ability to summarize and approximate data matrices in streaming fashion has become a common requirement in many emerging environments. In these applications, input data is usually generated at multiple distributed sites and simply centralizing all data is often infeasible. Therefore, novel algorithmic techniques are required. Furthermore, in most of these applications, queries must be answered solely based on the recently observed data points (e.g., data collected over the last hour/day/month), which makes the problem even more challenging. In this paper, we propose to study the problem of tracking matrix approximations over distributed sliding windows. In this problem, there are m distributed sites each observing a stream of d-dimensional data points. The goal is to continuously track a small matrix B as an approximation to Aw, the matrix consists of data points in the union of the streams which arrived during the last W time units. The quality of the approximation is measured by the covariance error kAT wAw? BTBk = kAk2 F [1], and the primary goal is to minimize communication, while providing provable error guarantee. We propose novel communication-efficient algorithms for this problem. Our sampling-based algorithms continuously track a weighted sample of rows according to their squared norms, which generalize and simplify the sampling techniques in [2]. We also propose deterministic tracking algorithms that require only one-way communication and provide better error guarantee. All algorithms have provable guarantees, and extensive experimental studies on real and synthetic datasets validate our theoretical claims and demonstrate the efficiency of these algorithms.

A sketch or synopsis of a large dataset captures vital properties of the original data while typically occupying much less space. In this paper, we consider the problem of computing a sketch of a massive data matrix A ∈ℜnxd, which is distributed across a large number of s servers. Our goal is to output a matrix B∈ℜℓ x d which is significantly smaller than but still approximates A well in terms of covariance error, i.e., ||ATA-BTB||2||. Here, for a matrix A, ||A||2|| is the spectral norm of A, which is defined as the largest singular value of A. Following previous works, we call B a covariance sketch of A. We are mainly focused on minimizing the communication cost, which is arguably the most valuable resource in distributed computations. We show a gap between deterministic and randomized communication complexity for computing a covariance sketch. More specifically, we first prove a tight deterministic lower bound, then show how to bypass this lower bound using randomization. In Principle Component Analysis (PCA), the goal is to find a low-dimensional subspace that captures as much of the variance of a dataset as possible. Based on a well-known connection between covariance sketch and PCA, we give a new algorithm for distributed PCA with improved communication cost. Moreover, in our algorithms, each server only needs to make one pass over the data with limited working space.

With the pervasive availability of smart devices, billions of users' trajectories are recorded and collected. The aggregated human behaviors reveal users' interests and characteristics, becoming invaluable to reflect their demographic preference, i.e., gender, age, marital status and even personality, occupation. Occupation profiling from trajectory data is an attractive option for advertisement targeting and other applications, without severe privacy concerns. However, it carries great difficulties in sparsity and vagueness.

As one of the most well known graph computation problems, Personalized PageRank is an effective approach for computing the similarity score between two nodes, and it has been widely used in various applications, such as link prediction and recommendation. Due to the high computational cost and space cost of computing the exact Personalized PageRank Vector (PPV), most existing studies compute PPV approximately. In this paper, we propose novel and efficient distributed algorithms that compute PPV exactly based on graph partitioning on a general coordinator-based share-nothing distributed computing platform. Our algorithms takes three aspects into account: the load balance, the communication cost, and the computation cost of each machine. The proposed algorithms only require one time of communication between each machine and the coordinator at query time. The communication cost is bounded, and the work load on each machine is balanced. Comprehensive experiments conducted on five real datasets demonstrate the efficiency and the scalability of our proposed methods.

Exact set similarity join, which finds all the similar set pairs from two collections of sets, is a fundamental problem with a wide range of applications. The existing solutions for set similarity join follow a filtering-verification framework, which generates a list of candidate pairs through scanning indexes in the filtering phase, and reports those similar pairs in the verification phase. Though much research has been conducted on this problem, set relations, which we find out is quite effective on improving the algorithm efficiency through computational cost sharing, have never been studied. Therefore, in this paper, instead of considering each set individually, we explore the set relations in different levels to reduce the overall computational costs. First, it has been shown that most of the computational time is spent on the filtering phase, which can be quadratic to the number of sets in the worst case for the existing solutions. Thus we explore index-level set relations to reduce the filtering cost to be linear to the size of the input while keeping the same filtering power. We achieve this by grouping related sets into blocks in the index and skipping useless index probes in joins. Second, we explore answer-level set relations to further improve the algorithm based on the intuition that if two sets are similar, their answers may have a large overlap. We derive an algorithm which incrementally generates the answer of one set from an already computed answer of another similar set rather than compute the answer from scratch to reduce the computational cost. Finally, we conduct extensive performance studies using 21 real datasets with various data properties from a wide range of domains. The experimental results demonstrate that our algorithm outperforms all the existing algorithms across all datasets and can achieve more than an order of magnitude speedup against the state- of-the-art algorithms.

Graph clustering is a fundamental problem widely experienced across many industries. The structural graph clustering (SCAN) method obtains not only clusters but also hubs and outliers. However, the clustering results closely depend on two sensitive parameters, ϵ and μ, while the optimal parameter setting depends on different graph properties and various user requirements. Moreover, all existing SCAN solutions need to scan at least the whole graph, even if only a small number of vertices belong to clusters. In this paper we propose an index-based method for SCAN. Based on our index, we cluster the graph for any ϵ and μ in O (Σ c ϵℂ | E C |) time, where ℂ is the result set of all clusters and | E C | is the number of edges in a specific cluster C. In other words, the time expended to compute structural clustering depends only on the result size, not on the size of the original graph. Our index's space complexity is bounded by O ( m ), where m is the number of edges in the graph. To handle dynamic graph updates, we propose algorithms and several optimization techniques for maintaining our index. We conduct extensive experiments to practically evaluate the performance of all our proposed algorithms on 10 real-world networks, one of which contains more than 1 billion edges. The experimental results demonstrate that our approaches significantly outperform existing solutions.

Graph coloring is a fundamental graph problem that is widely applied in a variety of applications. The aim of graph coloring is to minimize the number of colors used to color the vertices in a graph such that no two incident vertices have the same color. Existing solutions for graph coloring mainly focus on computing a good coloring for a static graph. However, since many real-world graphs are highly dynamic, in this paper, we aim to incrementally maintain the graph coloring when the graph is dynamically updated. We target on two goals: high effectiveness and high efficiency. To achieve high effectiveness, we maintain the graph coloring in a way such that the coloring result is consistent with one of the best static graph coloring algorithms for large graphs. To achieve high efficiency, we investigate efficient incremental algorithms to update the graph coloring by exploring a small number of vertices. We design a color-propagation based algorithm which only explores the vertices within the 2-hop neighbors of the update-related and color-changed vertices. We then propose a novel color index to maintain some summary color information and, thus, bound the explored vertices within the neighbors of these vertices. Moreover, we derive some effective pruning rules to further reduce the number of propagated vertices. The experimental results demonstrate the high effectiveness and efficiency of our approach.

In this paper, we investigate the problem of ( k,r )-core which intends to find cohesive subgraphs on social networks considering both user engagement and similarity perspectives. In particular, we adopt the popular concept of k -core to guarantee the engagement of the users (vertices) in a group (subgraph) where each vertex in a ( k,r )-core connects to at least k other vertices. Meanwhile, we consider the pairwise similarity among users based on their attributes. Efficient algorithms are proposed to enumerate all maximal ( k,r )-cores and find the maximum ( k,r )-core, where both problems are shown to be NP-hard. Effective pruning techniques substantially reduce the search space of two algorithms. A novel ( k,k' )-core based ( k,r )-core size upper bound enhances performance of the maximum ( k,r )-core computation. We also devise effective search orders for two mining algorithms where search priorities for vertices are different. Comprehensive experiments on real-life data demonstrate that the maximal/maximum ( k,r )-cores enable us to find interesting cohesive subgraphs, and performance of two mining algorithms is effectively improved by proposed techniques.

In this paper, we study the problem of the anchored k -core. Given a graph G , an integer k and a budget b , we aim to identify b vertices in G so that we can determine the largest induced subgraph J in which every vertex, except the b vertices, has at least k neighbors in J . This problem was introduced by Bhawalkar and Kleinberg e t al. in the context of user engagement in social networks, where a user may leave a community if he/she has less than k friends engaged. The problem has been shown to be NP-hard and inapproximable. A polynomial-time algorithm for graphs with bounded tree-width has been proposed. However, this assumption usually does not hold in real-life graphs, and their techniques cannot be extended to handle general graphs. Motivated by this, we propose an efficient algorithm, namely onion-layer based anchored k-core (OLAK), for the anchored k -core problem on large scale graphs. To facilitate computation of the anchored k -core, we design an onion layer structure, which is generated by a simple onion-peeling-like algorithm against a small set of vertices in the graph. We show that computation of the best anchor can simply be conducted upon the vertices on the onion layers , which significantly reduces the search space. Based on the well-organized layer structure, we develop efficient candidates exploration, early termination and pruning techniques to further speed up computation. Comprehensive experiments on 10 real-life graphs demonstrate the effectiveness and efficiency of our proposed methods.

Location prediction is widely used to forecast users' next place to visit based on his/her mobility logs. It is an essential problem in location data processing, invaluable for surveillance, business, and personal applications. It is very challenging due to the sparsity issues of check-in data. An often ignored problem in recent studies is the variety across different check-in scenarios, which is becoming more urgent due to the increasing availability of more location check-in applications. In this paper, we propose a new feature fusion based prediction approach, GALLOP, i.e., GlobAL feature fused LOcation Prediction for different check-in scenarios. Based on the carefully designed feature extraction methods, we utilize a novel combined prediction framework. Specifically, we set out to utilize the density estimation model to profile geographical features, i.e., context information, the factorization method to extract collaborative information, and a graph structure to extract location transition patterns of users' temporal check-in sequence, i.e., content information. An empirical study on three different check-in datasets demonstrates impressive robustness and improvement of the proposed approach.

Presents the introductory editorial for this issue of the publication.

SimRank is a widely adopted similarity measure for objects modeled as nodes in a graph, based on the intuition that two objects are similar if they are referenced by similar objects. The recursive nature of SimRank definition makes it expensive to compute the similarity score even for a single pair of nodes. This defect limits the applications of SimRank. To speed up the computation, some existing works replace the original model with an approximate model to seek only rough solution of SimRank scores. In this work, we propose a novel solution for computing all-pair SimRank scores. In particular, we propose to convert SimRank to the problem of solving a linear system in matrix form, and further prove that the system is non-singular, diagonally dominate, and symmetric definite positive (for undirected graphs). Those features immediately lead to the adoption of Conjugate Gradient (CG) and Bi-Conjugate Gradient (BiCG) techniques for efficiently computing SimRank scores. As a result, a significant improvement on the convergence rate can be achieved; meanwhile, the sparsity of the adjacency matrix is not damaged all the time. Inspired by the existing common neighbor sharing strategy, we further reduce the computational complexity of the matrix multiplication and resolve the scalable issues. The experimental results show our proposed algorithms significantly outperform the state-of-the-art algorithms.

Presents the editorial for this issue of the publication.

Given a social network and a positive integer k, the influence maximization problem aims to identify a set of k nodes in that can maximize the influence spread under a certain propagation model. As the proliferation of geo-social networks, location-aware promotion is becoming more necessary in real applications. In this paper, we study the distance-aware influence maximization (DAIM) problem, which advocates the importance of the distance between users and the promoted location. Unlike the traditional influence maximization problem, DAIM treats users differently based on their distances from the promoted location. In this situation, the k nodes selected are different when the promoted location varies. In order to handle the large number of queries and meet the online requirement, we develop two novel index-based approaches, MIA-DA and RIS-DA, by utilizing the information over some pre-sampled query locations. MIA-DA is a heuristic method which adopts the maximum influence arborescence (MIA) model to approximate the influence calculation. In addition, different pruning strategies as well as a priority-based algorithm are proposed to significantly reduce the searching space. To improve the effectiveness, in RIS-DA, we extend the reverse influence sampling (RIS) model and come up with an unbiased estimator for the DAIM problem. Through carefully analyzing the sample size needed for indexing, RIS-DA is able to return a 1 - 1=e - ε approximate solution with at least 1 - δ probability for any given query. Finally, we demonstrate the efficiency and effectiveness of proposed methods over real geo-social networks.

As a key problem in viral marketing, influence maximization has been extensively studied in the literature. Given a positive integer$k$, a social network$\mathcal {G}$and a certain propagation model, it aims to find a set of$k$nodes that have the largest influence spread. The state-of-the-art method IMM is based on the reverse influence sampling (RIS) framework. By using the martingale technique, it greatly outperforms the previous methods in efficiency. However, IMM still has limitations in scalability due to the high overhead of deciding a tight sample size. In this paper, instead of spending the effort on deciding a tight sample size, we present a novel bottom-ksketch based RIS framework, namely BKRIS, which brings the order of samples into the RIS framework. By applying the sketch technique, we can derive early termination conditions to significantly accelerate the seed set selection procedure. Moreover, we provide a cost-effective method to find a proper sample size to bound the quality of returned result. In addition, we provide several optimization techniques to reduce the cost of generating samples’ order and efficiently deal with the worst-case scenario. We demonstrate the efficiency and effectiveness of the proposed method over 10 real world datasets. Compared with the IMM approach, BKRIS can achieve up to two orders of magnitude speedup with almost the same influence spread. In the largest dataset with 1.8 billion edges, BKRIS can return 50 seeds in 1.3 seconds and return 5,000 seeds in 36.6 seconds. It takes IMM 55.32 second and 3,664.97 seconds, respectively.

In this paper, we study the problem of structural graph clustering, a fundamental problem in managing and analyzing graph data. Given a large graph G = (V, E), structural graph clustering is to assign vertices in V to clusters and to identify the sets of hub vertices and outlier vertices as well, such that vertices in the same cluster are densely connected to each other while vertices in different clusters are loosely connected to each other. Firstly, we prove that the existing SCAN approach is worst-case optimal. Nevertheless, it is still not scalable to large graphs due to exhaustively computing structural similarity for every pair of adjacent vertices. Secondly, we make three observations about structural graph clustering, which present opportunities for further optimization. Based on these observations, in this paper we develop a new two-step paradigm for scalable structural graph clustering. Thirdly, following this paradigm, we present a new approach aiming to reduce the number of structural similarity computations. Moreover, we propose optimization techniques to speed up checking whether two vertices are structure-similar to each other. Finally, we conduct extensive performance studies on large real and synthetic graphs, which demonstrate that our new approach outperforms the state-of-the-art approaches by over one order of magnitude. Noticeably, for the twitter graph with 1 billion edges, our approach takes 25 minutes while the state-of-the-art approach cannot finish even after 24 hours.

The existing works on spatial keyword search focus on finding a group of spatial objects covering all the query keywords and minimizing the diameter of the group. However, we observe that such a formulation may not address what users need in some application scenarios. In this paper, we introduce a novel spatial keyword cover problem (SK-COVER for short), which aims to identify the group of spatio-textual objects covering all keywords in a query and minimizing a distance cost function that leads to fewer proximate objects in the answer set. We prove that SK-COVER is not only NP-hard but also does not allow an approximation better than O(log m) in polynomial time, where m is the number of query keywords. We establish an O(log m)-approximation algorithm, which is asymptotically optimal in terms of the approximability of SK-COVER. Furthermore, we devise effective accessing strategies and pruning rules to improve the overall efficiency and scalability. In addition to our algorithmic results, we empirically show that our approximation algorithm always achieves the best accuracy, and the efficiency of our algorithm is comparable to a state-of-the-art algorithm that is intended for mCK, a problem similar to yet theoretically easier than SK-COVER.

The paper studies two fundamental problems in graph analytics: computing Connected Components (CCs) and computing BiConnected Components (BCCs) of a graph. With the recent advent of Big Data, developing effcient distributed algorithms for computing CCs and BCCs of a big graph has received increasing interests. As with the existing research efforts, in this paper we focus on the Pregel programming model, while the techniques may be extended to other programming models including MapReduce and Spark. The state-of-the-art techniques for computing CCs and BCCs in Pregel incur O(m × #supersteps) total costs for both data communication and computation, where m is the number of edges in a graph and #supersteps is the number of supersteps. Since the network communication speed is usually much slower than the computation speed, communication costs are the dominant costs of the total running time in the existing techniques. In this paper, we propose a new paradigm based on graph decomposition to reduce the total communication costs from O(m×#supersteps) to O(m), for both computing CCs and computing BCCs. Moreover, the total computation costs of our techniques are smaller than that of the existing techniques in practice, though theoretically they are almost the same. Comprehensive empirical studies demonstrate that our approaches can outperform the existing techniques by one order of magnitude regarding the total running time.

Supergraph search is a fundamental problem in graph databases that is widely applied in many application scenarios. Given a graph database and a query-graph, supergraph search retrieves all data-graphs contained in the query-graph from the graph database. Most existing solutions for supergraph search follow the pruning-and-verification framework, which prunes false answers based on features in the pruning phase and performs subgraph isomorphism testings on the remaining graphs in the verification phase. However, they are not scalable to handle large-sized data-graphs and query-graphs due to three drawbacks. First, they rely on a frequent subgraph mining algorithm to select features which is expensive and cannot generate large features. Second, they require a costly verification phase. Third, they process features in a fixed order without considering their relationship to the query-graph. In this paper, we address the three drawbacks and propose new indexing and query processing algorithms. In indexing, we select features directly from the data-graphs without expensive frequent subgraph mining. The features form a feature-tree that contains all-sized features and both the cost sharing and pruning power of the features are considered. In query processing, we propose a verification-free algorithm, where the order to process features is query-dependent by considering both the cost sharing and the pruning power. We explore two optimization strategies to further improve the algorithm efficiency. The first strategy applies a lightweight graph compression technique and the second strategy optimizes the inclusion of answers. Finally, we conduct extensive performance studies on two real large datasets to demonstrate the high scalability of our algorithms.

Given a set of facilities F, a set of users U and a query facility q, a reverse k furthest neighbors (RkFN) query retrieves every user u ∈ U for which q is one of its k-furthest facilities. RkFN query is the natural complement of reverse k-nearest neighbors (RkNN) query that returns every user u for which q is one of its k-nearest facilities. While RkNN query returns the users that are highly influenced by a query q, RkFN query aims at finding the users that are least influenced by a query q. RkFN query has many applications in location-based services, marketing, facility location, clustering, and recommendation systems etc. While there exist several algorithms that answer RkFN query for k = 1, we are the first to propose a solution for arbitrary value of k. Based on several interesting observations, we present an efficient algorithm to process the RkFN queries. We also present a rigorous theoretical analysis to study various important aspects of the problem and our algorithm. An extensive experimental study is conducted using both real and synthetic data sets, demonstrating that our algorithm outperforms the state-of-the-art algorithm even for k = 1. The accuracy of our theoretical analysis is also verified by the experiments.

Influence maximization is a key problem in viral marketing. Given a social network G and a positive integer k, it aims to identify a seed set of k nodes in G that can maximize the expected influence spread in a certain propagation model. With the proliferation of geo-social networks, location-aware product promotion is becoming more necessary in real applications. However, the importance of the distance between users and the promoted location is underestimated in existing models. For instance, when opening a restaurant in downtown, through online promotion, the owner may expect to influence more customers who are close to the restaurant, instead of people that are far away from it. In this paper, we formally define the distance-aware influence maximization problem, to find a seed set that maximizes the expected influence over users who are more likely to be the potential customers of the promoted location. To efficiently calculate the influence spread, we adopt the maximum influence arborescence (MIA) model for influence approximation. To speed up the search, we propose three pruning strategies to prune unpromising nodes from expensive evaluation and achieve potential early termination in each iteration without sacrificing the final result's approximation ratio. In addition, novel index structures are developed to compute the bounds used in the three pruning strategies. By integrating these pruning strategies, we propose a priority based algorithm which searches users based on their order of influence. The algorithm achieves an approximation ratio of 1 − 1 over e under the MIA model. In the final, comprehensive experiments over real datasets demonstrate the efficiency and effectiveness of the proposed algorithms and pruning strategies.

Core decomposition is a fundamental graph problem with a large number of applications. Most existing approaches for core decomposition assume that the graph is kept in memory of a machine. Nevertheless, many real-world graphs are big and may not reside in memory. In the literature, there is only one work for I/O efficient core decomposition that avoids loading the whole graph in memory. However, this approach is not scalable to handle big graphs because it cannot bound the memory size and may load most parts of the graph in memory. In addition, this approach can hardly handle graph updates. In this paper, we study I/O efficient core decomposition following a semi-external model, which only allows node information to be loaded in memory. This model works well in many web-scale graphs. We propose a semi-external algorithm and two optimized algorithms for I/O efficient core decomposition using very simple structures and data access model. To handle dynamic graph updates, we show that our algorithm can be naturally extended to handle edge deletion. We also propose an I/O efficient core maintenance algorithm to handle edge insertion, and an improved algorithm to further reduce I/O and CPU cost by investigating some new graph properties. We conduct extensive experiments on 12 real large graphs. Our optimal algorithm significantly outperform the existing I/O efficient algorithm in terms of both processing time and memory consumption. In many memory-resident graphs, our algorithms for both core decomposition and maintenance can even outperform the in-memory algorithm due to the simple structures and data access model used. Our algorithms are very scalable to handle web-scale graphs. As an example, we are the first to handle a web graph with 978.5 million nodes and 42.6 billion edges using less than 4.2 GB memory.

The popularity of e-business and preference learning techniques have contributed a huge amount of product and user preference data. Analyzing the influence of an existing or new product among the users is critical to unlock the great scientific and social-economic value of these data. In this paper, we advocate the problem of influence-based cost optimization for the user preference and product data, which is fundamental in many real applications such as marketing and advertising. Generally, we aim to find a cost optimal position for a new product such that it can attract at least k or a particular percentage of users for the given user preference functions and competitors' products. Although we show the solution space of our problem can be reduced to a finite number of possible positions (points) by utilizing the classical k-level computation techniques, the computation cost is still very expensive due to the nature of the high combinatorial complexity of the k-level problem. To alleviate this issue, we develop efficient pruning and query processing techniques to significantly improve the performance. In particular, our traverse-based 2-dimensional algorithm is very efficient with time complexity O(n) where n is the number of user preference functions. For general multi-dimensional spaces, we develop space partition based algorithm to significantly improve the performance by utilizing cost-based, influence-based and local dominance based pruning techniques. Then, we show that the performance of the partition based algorithm can be further enhanced by utilizing sampling approach, where the problem can be reduced to the classical half-space intersection problem. We demonstrate the efficiency of our techniques with extensive experiments over real and synthetic datasets.

Clustering short texts by their meaning is a challenging task. The semantic hashing approach encodes the meaning of a text into a compact binary code. Thus, to tell if two texts have similar meanings, we only need to check if they have similar codes. The encoding is created by a deep neural network, which is trained on texts represented by word-count vectors. Unfortunately, for short texts such as search queries, such representations are insufficient to capture the underlying semantics. We propose a method to add more semantic signals to enrich short texts. Furthermore, we introduce a simplified deep learning network constructed by stacked auto-encoders to do semantic hashing. Experiments show that our method significantly improves the understanding of short texts, including text retrieval, classification and other general text-related tasks.

In this paper, we investigate the problem of supergraph containment search over uncertain data graphs gu where each edge in a gu has an occurrence probability, namely probabilistic supergraph search, which has a wide spectrum of applications.

In this paper, we study the problem of subgraph matching that extracts all subgraph isomorphic embeddings of a query graph q in a large data graph G. The existing algorithms for subgraph matching follow Ullmann's backtracking approach; that is, iteratively map query vertices to data vertices by following a matching order of query vertices. It has been shown that the matching order of query vertices is a very important aspect to the efficiency of a subgraph matching algorithm. Recently, many advanced techniques, such as enforcing connectivity and merging similar vertices in query or data graphs, have been proposed to provide an effective matching order with the aim to reduce unpromising intermediate results especially the ones caused by redundant Cartesian products. In this paper, for the first time we address the issue of unpromising results by Cartesian products from "dissimilar" vertices. We propose a new framework by postponing the Cartesian products based on the structure of a query to minimize the redundant Cartesian products. Our second contribution is proposing a new path-based auxiliary data structure, with the size O(|E(G)| x |V(q)|), to generate a matching order and conduct subgraph matching, which significantly reduces the exponential size O(|V(G)||V(q)|-1) of the existing path-based auxiliary data structure, where V (G) and E (G) are the vertex and edge sets of a data graph G, respectively, and V (q) is the vertex set of a query $q$. Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms by up to $3$ orders of magnitude.

The CPU cache performance is one of the key issues to efficiency in database systems. It is reported that cache miss latency takes a half of the execution time in database systems. To improve the CPU cache performance, there are studies to support searching including cache-oblivious, and cache-conscious trees. In this paper, we focus on CPU speedup for graph computing in general by reducing the CPU cache miss ratio for different graph algorithms. The approaches dealing with trees are not applicable to graphs which are complex in nature.

Subgraph enumeration aims to find all the subgraphs of a large data graph that are isomorphic to a given pattern graph. As the subgraph isomorphism operation is computationally intensive, researchers have recently focused on solving this problem in distributed environments, such as MapReduce and Pregel. Among them, the state-of-the-art algorithm, Twin TwigJoin, is proven to be instance optimal based on a left-deep join framework. However, it is still not scalable to large graphs because of the constraints in the left-deep join framework and that each decomposed component (join unit) must be a star. In this paper, we propose SEED - a scalable sub-graph enumeration approach in the distributed environment. Compared to Twin TwigJoin, SEED returns optimal solution in a generalized join framework without the constraints in Twin TwigJoin. We use both star and clique as the join units, and design an effective distributed graph storage mechanism to support such an extension. We develop a comprehensive cost model, that estimates the number of matches of any given pattern graph by considering power-law degree distribution in the data graph. We then generalize the left-deep join framework and develop a dynamic-programming algorithm to compute an optimal bushy join plan. We also consider overlaps among the join units. Finally, we propose clique compression to further improve the algorithm by reducing the number of the intermediate results. Extensive performance studies are conducted on several real graphs, one containing billions of edges. The results demonstrate that our algorithm outperforms all other state-of-the-art algorithms by more than one order of magnitude.

As the prevalence of social media and GPS-enabled devices, a massive amount of geo-textual data has been generated in a stream fashion, leading to a variety of applications such as location-based recommendation and information dissemination. In this paper, we investigate a novel real-time top- k monitoring problem over sliding window of streaming data; that is, we continuously maintain the top-k most relevant geo-textual messages (e.g., geo-tagged tweets) for a large number of spatial-keyword subscriptions (e.g., registered users interested in local events ) simultaneously. To provide the most recent information under controllable memory cost, sliding window model is employed on the streaming geo-textual data. To the best of our knowledge, this is the first work to study top- k spatial-keyword publish/subscribe over sliding window. A novel system, called Skype (Top-k Spatial-keyword Publish/Subscribe), is proposed in this paper. In Skype, to continuously maintain top- k results for massive subscriptions, we devise a novel indexing structure upon subscriptions such that each incoming message can be immediately delivered on its arrival. Moreover, to reduce the expensive top- k re-evaluation cost triggered by message expiration, we develop a novel cost-based k-skyband technique to reduce the number of re-evaluations in a cost-effective way. Extensive experiments verify the great efficiency and effectiveness of our proposed techniques.

The problem of computing k -edge connected components ( k -ECCs) of a graph G for a specific k is a fundamental graph problem and has been investigated recently. In this paper, we study the problemof ECC decomposition, which computes the k -ECCs of a graph G for all k values. ECC decomposition can be widely applied in a variety of applications such as graph-topology analysis, community detection, Steiner component search, and graph visualization. A straightforward solution for ECC decomposition is to apply the existing k -ECC computation algorithm to compute the k -ECCs for all k values. However, this solution is not applicable to large graphs for two challenging reasons. First, all existing k -ECC computation algorithms are highly memory intensive due to the complex data structures used in the algorithms. Second, the number of possible k values can be very large, resulting in a high computational cost when each k value is independently considered. In this paper, we address the above challenges, and study I/O efficient ECC decomposition via graph reduction. We introduce two elegant graph reduction operators which aim to reduce the size of the graph loaded in memory while preserving the connectivity information of a certain set of edges to be computed for a specific k . We also propose three novel I/O efficient algorithms, Bottom-Up, Top-Down, and Hybrid, that explore the k values in different orders to reduce the redundant computations between different k values. We analyze the I/O and memory costs for all proposed algorithms. In our experiments, we evaluate our algorithms using seven real large datasets with various graph properties, one of which contains 1.95 billion edges. The experimental results show that our proposed algorithms are scalable and efficient.

For various entering and transmission issues raised by human or system, missing events often occur in event data, which record execution logs of business processes. Without recovering the missing events, applications such as provenance analysis or complex event processing built upon event data are not reliable. Following the minimum change discipline in improving data quality, it is also rational to find a recovery that minimally differs from the original data. Existing recovery approaches fall short of efficiency owing to enumerating and searching over all of the possible sequences of events. In this paper, we study the efficient techniques for recovering missing events. According to our theoretical results, the recovery problem appears to be NP-hard. Nevertheless, advanced indexing, pruning techniques are developed to further improve the recovery efficiency. The experimental results demonstrate that our minimum recovery approach achieves high accuracy, and significantly outperforms the state-of-the-art technique for up to five orders of magnitudes improvement in time performance.

Microblogging platforms, such as Twitter, serve as an important and efficient channel for sharing information. With the prevalence of geo-position enabled devices, a rapidly growing amount of microblogs are associated with geo-tags. Consequently, real-time analysis of the geo-tagged microblog stream has attracted great attentions. In this paper, we advocate the significance of keyword co-occurrence for geo-tagged microblogs analysis, which has been overlooked by existing studies. The co-occurrence of keywords is necessary to resolve the ambiguity in event analysis, especially when different events have overlapping descriptions. Given a geo-tagged microblog stream, we formally define the problem of identifying local (top-$K$) maximal frequent keyword co-occurrence patterns over geo-tagged microblog stream, namely LFP (LKFP) query. Given a query region, LFP query aims to retrieve the local maximal keyword patterns with frequency exceeding a given threshold; while LKFP query aims to identify$K$maximal keyword patterns with highest local frequency, in case users do not have a threshold in mind. To handle the high volume microblog stream and meet the requirement when a large number of queries are issued, we develop novel data structures to maintain the data stream, and propose efficient algorithms to process LFP and LKFP queries with theoretical underpinnings. The extensive empirical study on real dataset confirms the effectiveness and efficiency of our approaches.

Clustering short texts (such as news titles) by their meaning is a challenging task. The semantic hashing approach encodes the meaning of a text into a compact binary code. Thus, to tell if two texts have similar meanings, we only need to check if they have similar codes. The encoding is created by a deep neural network, which is trained on texts represented by word-count vectors (bag-of-word representation). Unfortunately, for short texts such as search queries, tweets, or news titles, such representations are insufficient to capture the underlying semantics. To cluster short texts by their meanings, we propose to add more semantic signals to short texts. Specifically, for each term in a short text, we obtain its concepts and co-occurring terms from a probabilistic knowledge base to enrich the short text. Furthermore, we introduce a simplified deep learning network consisting of a 3-layer stacked auto-encoders for semantic hashing. Comprehensive experiments show that, with more semantic signals, our simplified deep learning model is able to capture the semantics of short texts, which enables a variety of applications including short text retrieval, classification, and general purpose text processing.

Given a query graph$q$, retrieving the data graphs$g$from a set$D$of data graphs such that$q$contains$g$, namely supergraph containment search, is fundamental in graph data analysis with a wide range of real applications. It is very challenging due to the NP-Completeness of subgraph isomorphism testing. Driven by many real applications, in this paper, we study the problem of probabilistic supergraph search; that is, given a set$D$of uncertain data graphs, a certain query graph$q$and a probability threshold$\theta$, we retrieve the data graphs$g^{u}$from$D$such that the probability of$q$containing$g^{u}$is not smaller than$\theta$. We show that besides the NP-Completeness of subgraph isomorphism testing, the problem of calculating probabilities is #P-Complete; thus, it is even more challenging than the supergraph containment search. To tackle the computational hardness, we first propose two novel pruning rules, based on probabilistic connectivity and features, respectively, to efficiently prune non-promising data graphs. Then, efficient verification algorithms are developed with the aim of sharing computation and terminating non-promising computation as early as possible. Extensive performance studies on both real and synthetic data demonstrate the efficiency and effectiveness of our techniques in practice.

With advances in geo-positioning technologies and geo-location services, there are a rapidly growing amount ofspatio-textualobjects collected in many applications such as location based services and social networks, in which an object is described by its spatial location and a set of keywords (terms). Consequently, the study of spatial keyword search which explores both location and textual description of the objects has attracted great attention from the commercial organizations and research communities. In the paper, we study two fundamental problems in the spatial keyword queries: top$k$spatial keyword search (TOPK-SK), and batch top$k$spatial keyword search (BTOPK-SK). Given a set ofspatio-textualobjects, a query location and a set of query keywords, the TOPK-SK retrieves the closest$k$objects each of which contains all keywords in the query. BTOPK-SK is the batch processing of sets of TOPK-SK queries. Based on the inverted index and the linear quadtree, we propose a novel index structure, called inverted linear quadtree (IL-Quadtree), which is carefully designed to exploit both spatial and keyword based pruning techniques to effectively reduce the search space. An efficient algorithm is then developed to tackle top$k$spatial keyword search. To further enhance the filtering capability of the signature of linear quadtree, we propose a partition based method. In addition, to deal with BTOPK-SK, we design a new computing paradigm which partition the queries into groups based on both spatial proximity and the textual relevance between queries. We show that the IL-Quadtree technique can also efficiently support BTOPK-SK. Comprehensive experiments on real and synthetic data clearly demonstrate the efficiency of our methods.

Query autocompletion has become a standard feature in many search applications, especially for search engines. A recent trend is to support theerror-tolerant autocompletion, which increases the usability significantly by matching prefixes of database strings and allowing a small number of errors. In this article, we systematically study the query processing problem for error-tolerant autocompletion with a given edit distance threshold. We propose a general framework that encompasses existing methods and characterizes different classes of algorithms and the minimum amount of information they need to maintain under different constraints. We then propose a novel evaluation strategy that achieves the minimum active node size by eliminating ancestor-descendant relationships among active nodes entirely. In addition, we characterize the essence of edit distance computation by a novel data structure namededit vector automaton(EVA). It enables us to compute new active nodes and their associated states efficiently by table lookups. In order to support large distance thresholds, we devise a partitioning scheme to reduce the size and construction cost of the automaton, which results in theuniversal partitioned EVA(UPEVA) to handle arbitrarily large thresholds. Our extensive evaluation demonstrates that our proposed method outperforms existing approaches in both space and time efficiencies.

The range search on trajectories is fundamental in a wide spectrum of applications such as environment monitoring and location based services. In practice, a large portion of spatio-temporal data in the above applications is generated with low sampling rate and the uncertainty arises between two subsequent observations of a moving object. To make sense of the uncertain trajectory data, it is critical to properly model the uncertainty of the trajectories and develop efficient range search algorithms on the new model. Assuming uncertain trajectories are modeled by the popular Markov Chains, in this paper we investigate the problem of range search on uncertain trajectories. In particular, we propose a general framework for range search on uncertain trajectories following the filtering-and-refinement paradigm where summaries of uncertain trajectories are constructed to facilitate the filtering process. Moreover, statistics based and partition based filtering techniques are developed to enhance the filtering capabilities. Comprehensive experiments demonstrate the effectiveness and efficiency of our new techniques.

© 2015, Copyright is with the authors. Driven by many applications, in this paper we study the problem of computing the top-k shortest paths from one set of target nodes to another set of target nodes in a graph, namely the top-k shortest path join (KPJ) between two sets of target nodes. While KPJ is an extension of the problem of computing the top-k shortest paths (KSP) between two target nodes, the existing technique by converting KPJ to KSP has several deficiencies in conducting the computation. To resolve these, we propose to use the best-first paradigm to recursively divide search subspaces into smaller subspaces, and to compute the shortest path in each of the subspaces in a prioritized order based on their lower bounds. Consequently, we only compute shortest paths in subspaces whose lower bounds are larger than the length of the current k-th shortest path. To improve the efficiency, we further propose an iteratively bounding approach to tightening lower bounds of subspaces. Moreover, we propose two index structures which can be used to reduce the exploration area of a graph dramatically; these greatly speed up the computation. Extensive performance studies based on real road networks demonstrate the scalability of our approaches and that our approaches outperform the existing approach by several orders of magnitude. Furthermore, our approaches can be immediately used to compute KSP. Our experiment also demonstrates that our techniques outperform the state-of-the-art algorithm for KSP by several orders of magnitude.

Event data are often dirty owing to various recording conventions or simply system errors. These errors may cause many serious damages to real applications, such as inaccurate provenance answers, poor profiling results or concealing interesting patterns from event data. Cleaning dirty event data is strongly demanded. While existing event data cleaning techniques view event logs as sequences, structural information do exist among events. We argue that such structural information enhances not only the accuracy of repairing inconsistent events but also the computation efficiency. It is notable that both the structure and the names (labeling) of events could be inconsistent. In real applications, while unsound structure is not repaired automatically (which needs manual effort from business actors to handle the structure error), it is highly desirable to repair the inconsistent event names introduced by recording mistakes. In this paper, we propose a graph repair approach for 1) detecting unsound structure, and 2) repairing inconsistent event name.

We investigate the problem of processing a large amount of continuous spatial-keyword queries over streaming data, which is essential in many applications such as location-based recommendation and advertising, thanks to the proliferation of geo-equipped devices and the ensuing location-based social media applications. For example, a location-based e-coupon system may allow potentially millions of users to register their continuous spatial-keyword queries (e.g., interests in nearby sales) by specifying a set of keywords and a spatial region; the system then delivers each incoming spatial-textual object (e.g., a geo-tagged e-coupon) to all the matched queries (i.e., users) whose spatial and textual requirements are satisfied. While there are several prior approaches aiming at providing efficient query processing techniques for the problem, their approaches belong to spatial-first indexing method which cannot well exploit the keyword distribution. In addition, their textual filtering techniques are built upon simple variants of traditional inverted indexes, which do not perform well for the textual constraint imposed by the problem. In this paper, we address the above limitations and provide a highly efficient solution based on a novel adaptive index, named AP-Tree. The AP-Tree adaptively groups registered queries using keyword and spatial partitions, guided by a cost model. The AP-Tree also naturally indexes ordered keyword combinations. We present index construction algorithm that seamlessly and effectively integrates keyword and spatial partitions. Consequently, our method adapts well to the underlying spatial and keyword distributions of the data. Our extensive experiments demonstrate that AP-Tree achieves up to an order of magnitude improvement on efficiency compared with prior state-of-the-art methods.

Maximal clique enumeration is a fundamental problem in graph theory and has been extensively studied. However, maximal clique enumeration is time-consuming in large graphs and always returns enormous cliques with large overlaps. Motivated by this, in this paper, we study the diversified top-k clique search problem which is to find top-k maximal cliques that can cover most number of nodes in the graph. Diversified top-k clique search can be widely used in a lot of applications including community search, motif discovery, and anomaly detection in large graphs. A naive solution for diversified top-k clique search is to keep all maximal cliques in memory and then find k of them that cover most nodes in the graph by using the approximate greedy max k-cover algorithm. However, such a solution is impractical when the graph is large. In this paper, instead of keeping all maximal cliques in memory, we devise an algorithm to maintain k candidates in the process of maximal clique enumeration. Our algorithm has limited memory footprint and can achieve a guaranteed approximation ratio. We also introduce a novel light-weight PNP-Index, based on which we design an optimal maximal clique maintenance algorithm. We further explore three optimization strategies to avoid enumerating all maximal cliques and thus largely reduce the computational cost. We conduct extensive performance studies on six real graphs one of which contains 0.3 billion edges, and the results demonstrate the high efficiency and effectiveness of our approach.

Uncertainty is intrinsic to a wide spectrum of real-life applications, which inevitably applies to graph data. Representative uncertain graphs are seen in bio-informatics, social networks, etc. This paper motivates the problem of frequent subgraph mining on single uncertain graphs. We present an enumeration-evaluation algorithm to solve the problem. By showing support computation on an uncertain graph is #P-hard, we develop an approximation algorithm with accuracy guarantee for this purpose. To enhance the solution, we devise optimization techniques to achieve better mining performance. Experiment results on real-life data confirm the usability of the algorithm.

Hashing has gained considerable attention on large-scale similarity search, due to its enjoyable efficiency and low storage cost. In this paper, we study the problem of learning hash functions in the context of multi-modal data for cross-modal similarity search. Notwithstanding the progress achieved by existing methods, they essentially learn only one common hamming space, where data objects from all modalities are mapped to conduct similarity search. However, such method is unable to well characterize the flexible and discriminative local (neighborhood) structure in all modalities simultaneously, hindering them to achieve better performance. Bearing such stand-out limitation, we propose to learn heterogeneous hamming spaces with each preserving the local structure of data objects from an individual modality. Then, a novel method to learning bridging mapping for cross-modal hashing, named LBMCH, is proposed to characterize the cross-modal semantic correspondence by seamlessly connecting these distinct hamming spaces. Meanwhile, the local structure of each data object in a modality is preserved by constructing an anchor based representation, enabling LBMCH to characterize a linear complexity w.r.t the size of training set. The efficacy of LBMCH is experimentally validated against real-world cross-modal datasets.

With the proliferation of graph applications, the problem of efficiently computing all $k$-edge connected components of a graph G for a user-given k has been recently investigated. In this paper, we study the problem of efficiently computing the steiner component with the maximum connectivity; that is, given a set q of query vertices in a graph G, we aim to find the maximum induced subgraph g of G such that g contains q and g has the maximum connectivity, where g is denoted as SMCC. To accommodate online query processing, we present an efficient algorithm based on a novel index such that the algorithm runs in linear time regarding the result size; thus, the algorithm is optimal since it needs at least linear time to output the result. Moreover, in this paper we also investigate variations of the above problem. We show that such a problem with the constraint that the size of the SMCC is not smaller than a given size can also be solved in linear time regarding the result size (thus, optimal). We also show that the problem of computing the connectivity (rather than the graph details) of SMCC can be solved in linear time regarding the query size (thus, optimal). To build the index, we extend the techniques in [7] to accommodate batch processing and computation sharing. To efficiently support the applications with graph updates, we also present novel increment techniques. Finally, we conduct extensive performance studies on large real and synthetic graphs, which demonstrate that our index-based algorithms significantly outperform baseline algorithms by several orders of magnitude and our indexing algorithms are efficient.

In many domains such as computational geometry and database management, an object may be described by multiple instances (points). Then the distance (or similarity) between two objects is captured by the pair-wise distances among their instances. In the past, numerous nearest neighbor (NN) functions have been proposed to define the distance between objects with multiple instances and to identify the NN object. Nevertheless, considering that a user may not have a specific NN function in mind, it is desirable to provide her with a set of NN candidates. Ideally, the set of NN candidates must include every object that is NN for at least one of the NN functions and must exclude every non-promising object. However, no one has studied the problem of NN candidates computation from this perspective. Although some of the existing works aim at returning a set of candidate objects, they do not focus on the NN functions while computing the candidate objects. As a result, they either fail to include an NN object w.r.t. some NN functions or include a large number of unnecessary objects that have no potential to be the NN regardless of the NN functions.

Driven by many real applications, graph pattern matching has attracted a great deal of attention recently. Consider that a twig-pattern matching may result in an extremely large number of matches in a graph; this may not only confuse users by providing too many results but also lead to high computational costs. In this paper, we study the problem of top- k tree pattern matching; that is, given a rooted tree T , compute its top- k matches in a directed graph G based on the twig-pattern matching semantics. We firstly present a novel and optimal enumeration paradigm based on the principle of Lawler's procedure. We show that our enumeration algorithm runs in O ( n T + log k ) time in each round where n T is the number of nodes in T. Considering that the time complexity to output a match of T is O ( n T ) and n T ≥ log k in practice, our enumeration technique is optimal. Moreover, the cost of generating top-1 match of T in our algorithm is O ( m R ) where m R is the number of edges in the transitive closure of a data graph G involving all relevant nodes to T. O ( m R ) is also optimal in the worst case without pre-knowledge of G. Consequently, our algorithm is optimal with the running time O ( m R + k ( n T + log k )) in contrast to the time complexity O ( m R log k + kn T (log k + d T )) of the existing technique where d T is the maximal node degree in T. Secondly, a novel priority based access technique is proposed, which greatly reduces the number of edges accessed and results in a significant performance improvement. Finally, we apply our techniques to the general form of top- k graph pattern matching problem (i.e., query is a graph) to improve the existing techniques. Comprehensive empirical studies demonstrate that our techniques may improve the existing techniques by orders of magnitude.

Subgraph enumeration, which aims to find all the subgraphs of a large data graph that are isomorphic to a given pattern graph, is a fundamental graph problem with a wide range of applications. However, existing sequential algorithms for subgraph enumeration fall short in handling large graphs due to the involvement of computationally intensive subgraph isomorphism operations. Thus, some recent researches focus on solving the problem using MapReduce. Nevertheless, exiting MapReduce approaches are not scalable to handle very large graphs since they either produce a huge number of partial results or consume a large amount of memory. Motivated by this, in this paper, we propose a new algorithm TwinTwigJoin based on a left-deep-join framework in MapReduce, in which the basic join unit is a TwinTwig (an edge or two incident edges of a node). We show that in the Erdös-Rényi random-graph model, TwinTwigJoin is instance optimal in the left-deep-join framework under reasonable assumptions, and we devise an algorithm to compute the optimal join plan. Three optimization strategies are explored to improve our algorithm. Furthermore, we discuss how our approach can be adapted in the power-law random-graph model. We conduct extensive performance studies in several real graphs, one of which contains billions of edges. Our approach significantly outperforms existing solutions in all tests.

Given a set of users, a set of facilities and a query facility q , a reverse k nearest neighbors (R k NN) query returns every user u for which the query is one of its k closest facilities. R k NN queries have been extensively studied under a variety of settings and many sophisticated algorithms have been proposed to answer these queries. However, the existing experimental studies suffer from a few limitations. For example, some studies estimate the I/O cost by charging a fixed penalty per I/O and we show that this may be misleading. Also, the existing studies either use an extremely small buffer or no buffer at all which puts some algorithms at serious disadvantage. We show that the performance of these algorithms is significantly improved even when a small buffer (containing 100 pages) is used. Finally, in each of the existing studies, the proposed algorithm is mainly compared only with its predecessor assuming that it was the best algorithm at the time which is not necessarily true as shown in our experimental study. Motivated by these limitations, we present a comprehensive experimental study that addresses these limitations and compares some of the most notable algorithms under a wide variety of settings. Furthermore, we also present a carefully developed filtering strategy that significantly improves TPL which is one of the most popular R k NN algorithms. Specifically, the optimized version is up to 20 times faster than the original version and reduces its I/O cost up to two times.

SimRank is a powerful model for assessing vertex-pair similarities in a graph. It follows the concept that two vertices are similar if they are referenced by similar vertices. The prior work [18] exploits partial sums memoization to compute SimRank in O(Kmn) time on a graph of n vertices and m edges, for K iterations. However, computations among different partial sums may have redundancy. Besides, to guarantee a given accuracy ε, the existing SimRank needs K = [log C alterations, where C is a damping factor, but the geometric rate of convergence is slow if a high accuracy is expected. In this paper, (1) a novel clustering strategy is proposed to eliminate duplicate computations occurring in partial sums, and an efficient algorithm is then devised to accelerate SimRank computation to O(Kd'n2) time, where d' is typically much smaller than mn. (2) A new differential SimRank equation is proposed, which can represent the SimRank matrix as an exponential sum of transition matrices, as opposed to the geometric sum of the conventional counterpart. This leads to a further speedup in the convergence rate of SimRank iterations. (3) In bipartite domains, a novel finer-grained partial max clustering method is developed to speed up the computation of the Minimax SimRank variation from O(Kmn) to O(Km'n) time, where m' (≤m) is the number of edges in a reduced graph after edge clustering, which can be typically much smaller than m. Using real and synthetic data, we empirically verify that (1) our approach of partial sums sharing outperforms the best known algorithm by up to one order of magnitude; (2) the revised notion of SimRank further achieves a 5X speedup on large graphs while also fairly preserving the relative order of original SimRank scores; (3) our finer-grained partial max memoization for the Minimax SimRank variation in bipartite domains is 5X-12X faster than the baselines.

Due to a variety of reasons including data randomness and incompleteness, noise, privacy, etc., uncertainty is inherent in many important applications, such as location-based services (LBS), sensor network monitoring, and radio-frequency identification (RFID). Recently, considerable research efforts have been devoted into the field of uncertainty-aware spatial query processing such that the uncertainty of the data can be effectively and efficiently tackled. In this paper, we study the problem of finding top k most influential facilities over a set of uncertain objects, which is an important and fundamental spatial query in the above applications. Based on the maximal utility principle, we propose a new ranking model to identify the top k most influential facilities, which carefully captures influence of facilities on the uncertain objects. By utilizing two uncertain object indexing techniques, R-tree and U-Quadtree, effective and efficient algorithms are proposed following the filtering and verification paradigm, which significantly improves the performance of the algorithms in terms of CPU and I/O costs. To effectively support uncertain objects with a large number of instances, we also develop randomized algorithms with accuracy guarantee. Then, a hybrid algorithm is devised which effectively combines the randomized and exact algorithms. Comprehensive experiments on real datasets demonstrate the effectiveness and efficiency of our techniques.

The computation of k-lower envelope is a classical problem and has been very well studied for main memory non-indexed data. In this paper, we study the problem from the database perspective and present the first algorithm which utilizes the presence of the index and achieves access optimality, i.e., it accesses a node of the index only if the correctness of the results cannot be guaranteed without accessing this node. We also demonstrate the applications of k-lower envelope in ranking systems. Let an object be called valuable if it is one of the top-k objects according to at least one linear scoring function. In this paper, we answer the following important questions that may be asked by different users: 1) I am not sure what scoring function I should use, therefore, return me the set of valuable objects so that I can select an object I like the most; 2) How can I modify the attributes (e.g., price) of my product such that it becomes a valuable object; 3) What are the preference functions for which a given object is among the top-k objects. These three questions are formalized and called k-snippet, k-depth contour and reverse top-k query, respectively. We propose a unified framework to solve these queries by utilizing k-lower envelope as a common foundation. Our main algorithm is access optimal for k-snippet and k-lower envelope computation. We also demonstrate its access optimality for the k-depth contour problem when k is smaller than the minimum number of objects in any leaf node of the index structure. Our algorithms outperform state-of-the-art algorithms by more than an order of magnitude in terms of both CPU and I/O cost.

With the increasing pervasiveness of the geo-positioning tech-nologies, there is an enormous amount of spatio-textual ob-jects available in many applications such as location based services and social networks. Consequently, various types of spatial keyword searches which explore both locations and textual descriptions of the objects have been intensively studied by the research communities and commercial orga-nizations. In many important applications (e.g., location based services), the closeness of two spatial objects is mea-sured by the road network distance. Moreover, the result diversification is becoming a common practice to enhance the quality of the search results. Motived by the above facts, in this paper we study the problem of diversified spa-tial keyword search on road networks which considers both the relevance and the spatial diversity of the results. An efficient signature-based inverted indexing technique is pro-posed to facilitate the spatial keyword query processing on road networks. Then we develop an efficient diversified spa-tial keyword search algorithm by taking advantage of spatial keyword pruning and diversity pruning techniques. Com-prehensive experiments on real and synthetic data clearly demonstrate the efficiency of our methods. 1.

Given a set of facilities and a set of users, a reverse k nearest neighbors (RkNN) query q returns every user for which the query facility is one of the k-closest facilities. Due to its importance, RkNN query has received significant research attention in the past few years. Almost all of the existing techniques adopt a pruning-and-verification framework. Regions-based pruning and half-space pruning are the two most notable pruning strategies. The half-space based approach prunes a larger area and is generally believed to be superior. Influenced by this perception, almost all existing RkNN algorithms utilize and improve the half-space pruning strategy. We observe the weaknesses and strengths of both strategies and discover that the regions-based pruning has certain strengths that have not been exploited in the past. Motivated by this, we present a new RkNN algorithm called SLICE that utilizes the strength of regions-based pruning and overcomes its limitations. Our extensive experimental study on synthetic and real data sets demonstrate that SLICE is significantly more efficient than the existing algorithms. We also provide a detailed theoretical analysis to analyze various aspects of our algorithm such as I/O cost, the unpruned area, and the cost of its verification phase etc. The experimental study validates our theoretical analysis.

SimRank is an arresting measure of node-pair similarity based on hyperlinks. It iteratively follows the concept that 2 nodes are similar if they are referenced by similar nodes. Real graphs are often large, and links constantly evolve with small changes over time. This paper considers fast incremental computations of SimRank on link-evolving graphs. The prior approach [12] to this issue factorizes the graph via a singular value decomposition (SVD) first, and then incrementally maintains this factorization for link updates at the expense of exactness. Consequently, all node-pair similarities are estimated in O(r4n2) time on a graph of n nodes, where r is the target rank of the low-rank approximation, which is not negligibly small in practice. In this paper, we propose a novel fast incremental paradigm. (1) We characterize the SimRank update matrix ΔS, in response to every link update, via a rank-one Sylvester matrix equation. By virtue of this, we devise a fast incremental algorithm computing similarities of n2node-pairs in O(Kn2) time for K iterations. (2) We also propose an effective pruning technique capturing the “affected areas” of ΔS to skip unnecessary computations, without loss of exactness. This can further accelerate the incremental SimRank computation to O(K(nd+|AFF|)) time, where d is the average in-degree of the old graph, and |AFF| (≤ n2) is the size of “affected areas” in ΔS, and in practice, |AFF| ≪ n2. Our empirical evaluations verify that our algorithm (a) outperforms the best known link-update algorithm [12], and (b) runs much faster than its batch counterpart when link updates are small.

With the prevalence of the geo-position enabled devices and services, a rapidly growing amount of tweets are associated with geo-tags. Consequently, the real time search on geo-tagged Twitter streams has attracted great attentions.In this paper, we advocate the significance of the co-occurrence of keywords for the geo-tagged tweets data analytics, which is overlooked by existing studies. Particularly, we formally introduce the problem of identifying local frequent keyword co-occurrence patterns over the geo-tagged Twitter streams, namely LFP\xspace query. To accommodate the high volume and the rapid updates of the Twitter stream, we develop an inverted KMV sketch (IK\xspace sketch for short) structure to capture the co-occurrence of keywords in limited space. Then efficient algorithms are developed based on IK\xspace sketch to support LFP\xspace queries as well as its variant. The extensive empirical study on real Twitter dataset confirms the effectiveness and efficiency of our approaches.

MapReduce has become one of the most popular parallel computing paradigms in cloud, due to its high scalability, reliability, and fault-tolerance achieved for a large variety of applications in big data processing. In the literature, there are MapReduce Class MRC and Minimal MapReduce Class MMC to define the memory consumption, communication cost, CPU cost, and number of MapReduce rounds for an algorithm to execute in MapReduce. However, neither of them is designed for big graph processing in MapReduce, since the constraints in MMC can be hardly achieved simultaneously on graphs and the conditions in MRC may induce scalability problems when processing big graph data. In this paper, we study scalable big graph processing in MapReduce. We introduce a Scalable Graph processing Class SGC by relaxing some constraints in MMC to make it suitable for scalable graph processing. We define two graph join operators in SGC, namely, EN join and NE join, using which a wide range of graph algorithms can be designed, including PageRank, breadth first search, graph keyword search, Connected Component (CC) computation, and Minimum Spanning Forest (MSF) computation. Remarkably, to the best of our knowledge, for the two fundamental graph problems CC and MSF computation, this is the first work that can achieve O(log(n)) MapReduce rounds with $O(n+m)$ total communication cost in each round and constant memory consumption on each machine, where $n$ and $m$ are the number of nodes and edges in the graph respectively. We conducted extensive performance studies using two web-scale graphs Twitter and Friendster with different graph characteristics. The experimental results demonstrate that our algorithms can achieve high scalability in big graph processing.

The dominance operator plays an important role in a wide spectrum of multi-criteria decision making applications. Generally speaking, a dominance operator is a partial order on a set O of objects, and we say the dominance operator has the monotonic property regarding a family of ranking functions F if o1 dominates o2 implies f(o1) ≥ f(o2) for any ranking function f ∈ F and objects o1, o2 ∈ O. The dominance operator on the multi-dimensional points is well defined, which has the monotonic property regarding any monotonic ranking (scoring) function. Due to the uncertain nature of data in many emerging applications, a variety of existing works have studied the semantics of ranking query on uncertain objects. However, the problem of dominance operator against multi-dimensional uncertain objects remains open. Although there are several attempts to propose dominance operator on multi-dimensional uncertain objects, none of them claims the monotonic property on these ranking approaches.

Nearest neighbor searches in high-dimensional space have many important applications in domains such as data mining, and multimedia databases. The problem is challenging due to the phenomenon called "curse of dimensionality". An alternative solution is to consider algorithms that returns a c -approximate nearest neighbor ( c -ANN) with guaranteed probabilities. Locality Sensitive Hashing (LSH) is among the most widely adopted method, and it achieves high efficiency both in theory and practice. However, it is known to require an extremely high amount of space for indexing, hence limiting its scalability. In this paper, we propose several surprisingly simple methods to answer c -ANN queries with theoretical guarantees requiring only a single tiny index. Our methods are highly flexible and support a variety of functionalities, such as finding the exact nearest neighbor with any given probability. In the experiment, our methods demonstrate superior performance against the state-of-the-art LSH-based methods, and scale up well to 1 billion high-dimensional points on a single commodity PC.

In this paper, we investigate the selectivity estimation problem for streaming spatio-textual data, which arises in many social network and geo-location applications. Specifically, given a set of continuously and rapidly arriving spatio-textual objects, each of which is described by a geo-location and a short text, we aim to accurately estimate the cardinality of a spatial keyword query on objects seen so far, where a spatial keyword query consists of a search region and a set of query keywords. To the best of our knowledge, this is the first work to address this important problem. We first extend two existing techniques to solve this problem, and show their limitations. Inspired by two key observations on the "locality" of the correlations among query keywords, we propose a local correlation based method by utilizing an augmented adaptive space partition tree ( A 2 SP -tree for short) to approximately learn a local Bayesian network on-the-fly for a given query and estimate its selectivity. A novel local boosting approach is presented to further enhance the learning accuracy of local Bayesian networks. Our comprehensive experiments on real-life datasets demonstrate the superior performance of the local correlation based algorithm in terms of estimation accuracy compared to other competitors.

Given a scoring function that computes the score of a pair of objects, a top-$k$pairs query returns$k$pairs with the smallest scores. In this paper, we present a unified framework for answering generic top-$k$pairs queries including$k$-closest pairs queries,$k$-furthest pairs queries and their variants. Note that$k$-closest pairs query is a special case of top-$k$pairs queries where the scoring function is the distance between the two objects in a pair. We are the first to present a unified framework to efficiently answer a broad class of top-$k$queries including the queries mentioned above. We present efficient algorithms and provide a detailed theoretical analysis that demonstrates that the expected performance of our proposed algorithms is optimal for two dimensional data sets. Furthermore, our framework does not require pre-built indexes, uses limited main memory and is easy to implement. We also extend our techniques to support top-$k$pairs queries on multi-valued (or uncertain) objects. We also demonstrate that our framework can handle exclusive top-$k$pairs queries. Our extensive experimental study demonstrates effectiveness and efficiency of our proposed techniques.

Similarity query is a fundamental problem in database, data mining and information retrieval research. Recently, querying incomplete data has attracted extensive attention as it poses new challenges to traditional querying techniques. The existing work on querying incomplete data addresses the problem where the data values on certain dimensions are unknown. However, in many real-life applications, such as data collected by a sensor network in a noisy environment, not only the data values but also the dimension information may be missing. In this work, we propose to investigate the problem of similarity search on dimension incomplete data. A probabilistic framework is developed to model this problem so that the users can find objects in the database that are similar to the query with probability guarantee. Missing dimension information poses great computational challenge, since all possible combinations of missing dimensions need to be examined when evaluating the similarity between the query and the data objects. We develop the lower and upper bounds of the probability that a data object is similar to the query. These bounds enable efficient filtering of irrelevant data objects without explicitly examining all missing dimension combinations. A probability triangle inequality is also employed to further prune the search space and speed up the query process. The proposed probabilistic framework and techniques can be applied to both whole and subsequence queries. Extensive experimental results on real-life data sets demonstrate the effectiveness and efficiency of our approach.

Top-k pairs and top-k objects queries have received significant attention by the research community. In this paper, we present the first approach to answer a broad class of top-k pairs and top-k objects queries over sliding windows. Our framework handles multiple top-k queries and each query is allowed to use a different scoring function, a different value of k, and a different size of the sliding window. Furthermore, the framework allows the users to define arbitrarily complex scoring functions and supports out-of-order data streams. For all the queries that use the same scoring function, we need to maintain only one K-skyband. We present efficient techniques for the K-skyband maintenance and query answering. We conduct a detailed complexity analysis and show that the expected cost of our approach is reasonably close to the lower bound cost. For top-k pairs queries, we demonstrate the efficiency of our approach by comparing it with a specially designed supreme algorithm that assumes the existence of an oracle and meets the lower bound cost. For top-k objects queries, our experimental results demonstrate the superiority of our algorithm over the state-of-the-art algorithm.

As the uncertainty is inherent in a wide spectrum of applications such as radio frequency identification (RFID) networks and location-based services (LBS), it is highly demanded to address the uncertainty of the objects. In this paper, we propose a novel indexing structure, named $(U)$-Quadtree, to organize the uncertain objects in the multidimensional space such that the queries can be processed efficiently by taking advantage of $(U)$-Quadtree. Particularly, we focus on the range search on multidimensional uncertain objects since it is a fundamental query in a spatial database. We propose a cost model which carefully considers various factors that may impact the performance. Then, an effective and efficient index construction algorithm is proposed to build the optimal $(U)$-Quadtree regarding the cost model. We show that $(U)$-Quadtree can also efficiently support other types of queries such as uncertain range query and nearest neighbor query. Comprehensive experiments demonstrate that our techniques outperform the existing works on multidimensional uncertain objects.

In this paper, we tackle a novel problem of ranking multivalued objects, where an object has multiple instances in a multidimensional space, and the number of instances per object is not fixed. Given an ad hoc scoring function that assigns a score to a multidimensional instance, we want to rank a set of multivalued objects. Different from the existing models of ranking uncertain and probabilistic data, which model an object as a random variable and the instances of an object are assumed exclusive, we have to capture the coexistence of instances here. To tackle the problem, we advocate the semantics of favoring widely preferred objects instead of majority votes, which is widely used in many elections and competitions. Technically, we borrow the idea from Borda Count (BC), a well-recognized method in consensus-based voting systems. However, Borda Count cannot handle multivalued objects of inconsistent cardinality, and is costly to evaluate top (k) queries on large multidimensional data sets. To address the challenges, we extend and generalize Borda Count to quantile-based Borda Count, and develop efficient computational methods with comprehensive cost analysis. We present case studies on real data sets to demonstrate the effectiveness of the generalized Borda Count ranking, and use synthetic and real data sets to verify the efficiency of our computational method.

Many real-world objects described by multiple attributes or features can be decomposed as multiple "views" (e.g., an image can be described by a color view or a shape view), which often provides complementary information to each other. Learning a metric (similarity measures) for multi-view data is primary due to its wide applications in practices. However, leveraging multi-view information to produce a good metric is a great challenge and existing techniques are concerned with pairwise similarities, leading to undesirable fusion metric and high computational complexity. In this paper, we propose a novel Metric Fusion technique via cross-view graph Random Walk, named MFRW, regarding a multi-view based similarity graphs (with each similarity graph constructed under each view). Instead of using pairwise similarities, we seek a high-order metric yielded by graph random walks over constructed similarity graphs. Observing that ``outlier views" may exist in the fusion process, we incorporate the coefficient matrices representing the correlation strength between any two views into MFRW, named WMFRW. The principle of \textsf{WMFRW} is implemented by exploring the ``common latent structure" between views. The empirical studies conducted on real-world databases demonstrate that our approach outperforms the state-of-the-art competitors in terms of effectiveness and efficiency.

Given a set of criterions, an object o dominates another object ó if o is more preferable than ó according to every criterion. A skyline query returns every object that is not dominated by any other object. In this paper, we study the problem of continuously monitoring a moving skyline query where one of the criterions is the distance between the objects and the moving query. We propose a safe zone based approach to address the challenge of efficiently updating the results as the query moves. A safe zone is the area such that the results of a query remain unchanged as long as the query lies inside this area. Hence, the results are required to be updated only when the query leaves its safe zone. Although the main focus of this paper is to present the techniques for Euclidean distance metric, the proposed techniques are applicable to any metric distance (e.g., Manhattan distance, road network distance). We present several non-trivial optimizations and propose an efficient algorithm for safe zone construction. Our experiments demonstrate that the cost of our safe zone based approach is reasonably close to a lower bound cost and is three orders of magnitude lower than the cost of a naïve algorithm.

Skyline analysis is a key in a wide spectrum of real applications involving multi-criteria optimal decision making. In recent years, a considerable amount of research has been contributed on efficient computation of skyline probabilities over uncertain environment. Most studies if not all, assume uncertainty lies only in attribute values. To the extent of our knowledge, only one study addresses the skyline probability computation problem in scenarios where uncertainty resides in attribute preferences, instead of values. However this study takes a problematic approach by assuming independent object dominance, which we find is not always true in uncertain preference scenarios. In fact this assumption has already been shown to be not necessarily true in uncertain value scenarios. Motivated by this, we revisit the skyline probability computation over uncertain preferences in this paper.

Evaluating similarity between sets is a fundamental task in computer science. However, there are many applications in which elements in a set may be uncertain due to various reasons. Existing work on modeling such probabilistic sets and computing their similarities suffers from huge model sizes or significant similarity evaluation cost, and hence is only applicable to small probabilistic sets. In this paper, we propose a simple yet expressive model that supports many applications where one probabilistic set may have thousands of elements. We define two types of similarities between two probabilistic sets using the possible world semantics; they complement each other in capturing the similarity distributions in the cross product of possible worlds. We design efficient dynamic programming-based algorithms to calculate both types of similarities. Novel individual and batch pruning techniques based on upper bounding the similarity values are also proposed. To accommodate extremely large probabilistic sets, we also design sampling-based approximate query processing methods with strong probabilistic guarantees. We have conducted extensive experiments using both synthetic and real datasets, and demonstrated the effectiveness and efficiency of our proposed methods.

SimRank has been a powerful model for assessing the similarity of pairs of vertices in a graph. It is based on the concept that two vertices are similar if they are referenced by similar vertices. Due to its self-referentiality, fast SimRank computation on large graphs poses significant challenges. The state-of-the-art work [17] exploits partial sums memorization for computing SimRank in O(Kmn) time on a graph with n vertices and m edges, where K is the number of iterations. Partial sums memorizing can reduce repeated calculations by caching part of similarity summations for later reuse. However, we observe that computations among different partial sums may have duplicate redundancy. Besides, for a desired accuracy ϵ, the existing SimRank model requires K = [logCϵ] iterations [17], where C is a damping factor. Nevertheless, such a geometric rate of convergence is slow in practice if a high accuracy is desirable. In this paper, we address these gaps. (1) We propose an adaptive clustering strategy to eliminate partial sums redundancy (i.e., duplicate computations occurring in partial sums), and devise an efficient algorithm for speeding up the computation of SimRank to 0(Kd'n2) time, where d' is typically much smaller than the average in-degree of a graph. (2) We also present a new notion of SimRank that is based on a differential equation and can be represented as an exponential sum of transition matrices, as opposed to the geometric sum of the conventional counterpart. This leads to a further speedup in the convergence rate of SimRank iterations. (3) Using real and synthetic data, we empirically verify that our approach of partial sums sharing outperforms the best known algorithm by up to one order of magnitude, and that our revised notion of SimRank further achieves a 5X speedup on large graphs while also fairly preserving the relative order of original SimRank scores.

With advances in geo-positioning technologies and geo-location services, there are a rapidly growing amount of spatio-textual objects collected in many applications such as location based services and social networks, in which an object is described by its spatial location and a set of keywords (terms). Consequently, the study of spatial keyword search which explores both location and textual description of the objects has attracted great attention from the commercial organizations and research communities. In the paper, we study the problem of top k spatial keyword search (TOPK-SK), which is fundamental in the spatial keyword queries. Given a set of spatio-textual objects, a query location and a set of query keywords, the top k spatial keyword search retrieves the closest k objects each of which contains all keywords in the query. Based on the inverted index and the linear quadtree, we propose a novel index structure, called inverted linear quadtree (IL-Quadtree), which is carefully designed to exploit both spatial and keyword based pruning techniques to effectively reduce the search space. An efficient algorithm is then developed to tackle top k spatial keyword search. In addition, we show that the IL-Quadtree technique can also be applied to improve the performance of other spatial keyword queries such as the direction-aware top k spatial keyword search and the spatio-textual ranking query. Comprehensive experiments on real and synthetic data clearly demonstrate the efficiency of our methods.

Random Walk with Restart (RWR) has become an appealing measure of node proximities in emerging applications \eg recommender systems and automatic image captioning. In practice, a real graph is typically large, and is frequently updated with small changes. It is often cost-inhibitive to recompute proximities from scratch via \emph{batch} algorithms when the graph is updated. This paper focuses on the incremental computations of RWR in a dynamic graph, whose edges often change over time. The prior attempt of RWR [1] deploys \kdash to find top-$k$ highest proximity nodes for a given query, which involves a strategy to incrementally \emph{estimate} upper proximity bounds. However, due to its aim to prune needless calculation, such an incremental strategy is \emph{approximate}: in $O(1)$ time for each node. The main contribution of this paper is to devise an \emph{exact} and fast incremental algorithm of RWR for edge updates. Our solution, \IRWR\!, can incrementally compute any node proximity in $O(1)$ time for each edge update without loss of exactness. The empirical evaluations show the high efficiency and exactness of \IRWR for computing proximities on dynamic networks against its batch counterparts.

Efficiently computing k-edge connected components in a large graph, G = (V, E), where V is the vertex set and E is the edge set, is a long standing research problem. It is not only fundamental in graph analysis but also crucial in graph search optimization algorithms. Consider existing techniques for computing k-edge connected components are quite time consuming and are unlikely to be scalable for large scale graphs, in this paper we firstly propose a novel graph decomposition paradigm to iteratively decompose a graph G for computing its k-edge connected components such that the number of drilling-down iterations h is bounded by the "depth" of the k-edge connected components nested together to form G, where h usually is a small integer in practice. Secondly, we devise a novel, efficient threshold-based graph decomposition algorithm, with time complexity O(l × |E|), to decompose a graph G at each iteration, where l usually is a small integer with l « |V|. As a result, our algorithm for computing k-edge connected components significantly improves the time complexity of an existing state-of-the-art technique from O(|V|2|E| + |V|3 log |V|) to O(h × l × |E|). Finally, we conduct extensive performance studies on large real and synthetic graphs. The performance studies demonstrate that our techniques significantly outperform the state-of-the-art solution by several orders of magnitude.

A process trace describes the processes taken in a workflow to generate a particular result. Given many process traces, each with a large amount of very low level information, it is a challenge to make process traces meaningful to different users. It is more challenging to compare two complex process traces generated by heterogenous systems and have different levels of granularity. We present CTrace, a system that (1) lets users explore the conceptual abstraction of large process traces with different levels of granularity, and (2) provides semantic comparison among traces in which both the structural and the semantic similarity are considered. The above functions are underpinned by a novel notion of multi-granularity process trace and efficient multi-granularity similarity comparison algorithms.

A strongly connected component (SCC) is a maximal subgraph of a directed graph G in which every pair of nodes are reachable from each other in the SCC. With such a property, a general directed graph can be represented by a directed acyclic graph DAG by contracting an SCC of G to a node in DAG. In many real applications that need graph pattern matching, topological sorting, or reachability query processing, the best way to deal with a general directed graph is to deal with its DAG representation. Therefore, finding all SCCs in a directed graph G is a critical operation. The existing in-memory algorithms based on depth first search (DFS) can find all SCCs in linear time w.r.t. the size of a graph. However, when a graph cannot resident entirely in the main memory, the existing external or semi-external algorithms to find all SCCs have limitation to achieve high I/O efficiency. In this paper, we study new I/O efficient semi-external algorithms to find all SCCs for a massive directed graph G that cannot reside in main memory entirely. To overcome the deficiency of the existing DFS based semi-external algorithm that heavily relies on a total order, we explore a weak order based on which we investigate new algorithms. We propose a new two phase algorithm, namely, tree construction and tree search. In the tree construction phase, a spanning tree of G can be constructed in bounded sequential scans of G. In the tree search phase, it needs to sequentially scan the graph once to find all SCCs. In addition, we propose a new single phase algorithm, which combines the tree construction and tree search phases into a single phase, with three new optimization techniques. They are early acceptance, early rejection, and batch processing. By the single phase algorithm with the new optimization techniques, we can significantly reduce the number of I/Os and CPU cost. We conduct extensive experimental studies using 4 real datasets including a massive real dataset, and several synthetic datasets to confirm the I/O efficiency of our approaches.

For various entering and transmission issues raised by human or system, missing events often occur in event data, which record execution logs of business processes. Without recovering these missing events, applications such as provenance analysis or complex event processing built upon event data are not reliable. Following the minimum change discipline in improving data quality, it is also rational to find a recovery that minimally differs from the original data. Existing recovery approaches fall short of efficiency owing to enumerating and searching over all the possible sequences of events. In this paper, we study the efficient techniques for recovering missing events. According to our theoretical results, the recovery problem is proved to be NP-hard. Nevertheless, we are able to concisely represent the space of event sequences in a branching framework. Advanced indexing and pruning techniques are developed to further improve the recovery efficiency. Our proposed efficient techniques make it possible to find top-k recoveries. The experimental results demonstrate that our minimum recovery approach achieves high accuracy, and significantly outperforms the state-of-the-art technique for up to 5 orders of magnitudes improvement in time performance.

Similarity assessment is one of the core tasks in hyperlink analysis. Recently, with the proliferation of applications, e.g. , web search and collaborative filtering, SimRank has been a well-studied measure of similarity between two nodes in a graph. It recursively follows the philosophy that "two nodes are similar if they are referenced (have incoming edges) from similar nodes", which can be viewed as an aggregation of similarities based on incoming paths. Despite its popularity, SimRank has an undesirable property, i.e. , "zero-similarity": It only accommodates paths with equal length from a common "center" node. Thus, a large portion of other paths are fully ignored. This paper attempts to remedy this issue. (1) We propose and rigorously justify SimRank*, a revised version of SimRank, which resolves such counter-intuitive "zero-similarity" issues while inheriting merits of the basic SimRank philosophy. (2) We show that the series form of SimRank* can be reduced to a fairly succinct and elegant closed form, which looks even simpler than SimRank, yet enriches semantics without suffering from increased computational cost. This leads to a fixed-point iterative paradigm of SimRank* in O ( Knm ) time on a graph of n nodes and m edges for K iterations, which is comparable to SimRank. (3) To further optimize SimRank* computation, we leverage a novel clustering strategy via edge concentration. Due to its NP-hardness, we devise an efficient and effective heuristic to speed up SimRank* computation to O ( Kn m) time, where m is generally much smaller than m. (4) Using real and synthetic data, we empirically verify the rich semantics of SimRank*, and demonstrate its high computation efficiency.

Graphs are widely used to model complex data in many applications, such as bioinformatics, chemistry, social networks, pattern recognition, etc. A fundamental and critical query primitive is to efficiently search similar structures in a large collection of graphs. This paper studies the graph similarity queries with edit distance constraints. Existing solutions to the problem utilize fixed-size overlapping substructures to generate candidates, and thus become susceptible to large vertex degrees or large distance thresholds. In this paper, we present a partition-based approach to tackle the problem. By dividing data graphs into variable-size non-overlapping partitions, the edit distance constraint is converted to a graph containment constraint for candidate generation. We develop efficient query processing algorithms based on the new paradigm. A candidate pruning technique and an improved graph edit distance algorithm are also developed to further boost the performance. In addition, a cost-aware graph partitioning technique is devised to optimize the index. Extensive experiments demonstrate our approach significantly outperforms existing approaches.

Clustering on uncertain data, one of the essential tasks in mining uncertain data, posts significant challenges on both modeling similarity between uncertain objects and developing efficient computational methods. The previous methods extend traditional partitioning clustering methods like $(k)$-means and density-based clustering methods like DBSCAN to uncertain data, thus rely on geometric distances between objects. Such methods cannot handle uncertain objects that are geometrically indistinguishable, such as products with the same mean but very different variances in customer ratings. Surprisingly, probability distributions, which are essential characteristics of uncertain objects, have not been considered in measuring similarity between uncertain objects. In this paper, we systematically model uncertain objects in both continuous and discrete domains, where an uncertain object is modeled as a continuous and discrete random variable, respectively. We use the well-known Kullback-Leibler divergence to measure similarity between uncertain objects in both the continuous and discrete cases, and integrate it into partitioning and density-based clustering methods to cluster uncertain objects. Nevertheless, a naïve implementation is very costly. Particularly, computing exact KL divergence in the continuous case is very costly or even infeasible. To tackle the problem, we estimate KL divergence in the continuous case by kernel density estimation and employ the fast Gauss transform technique to further speed up the computation. Our extensive experiment results verify the effectiveness, efficiency, and scalability of our approaches.