A hypergraph is a generalization of a graph, in which a hyperedge can connect multiple vertices, modeling complex relationships involving multiple vertices simultaneously. Hypergraph pattern matching, which is to find all isomorphic embeddings of a query hypergraph in a data hypergraph, is one of the fundamental problems. In this paper, we present a novel algorithm for hypergraph pattern matching by introducing (1) the intersection constraint, a necessary and sufficient condition for valid embeddings, which significantly speeds up the verification process, (2) the candidate hyperedge space, a data structure that stores potential mappings between hyperedges in the query hypergraph and the data hypergraph, and (3) the Match-and-Filter framework, which interleaves matching and filtering operations to maintain only compatible candidates in the candidate hyperedge space during backtracking. Experimental results on real-world datasets demonstrate that our algorithm significantly outperforms the state-of-the-art algorithms, by up to orders of magnitude in terms of query processing time.

Reachability in hypergraphs is essential for modeling complex groupwise interactions in real-world applications such as co-authorship, social network, and biological analysis, where relationships go beyond pairwise interactions. In this paper, we introduce the notion of s-reachability, where two vertices are s-reachable if there exists a sequence of hyperedges (i.e., a walk) connecting them, such that each pair of consecutive hyperedges shares at least s vertices. Moreover, we define the max-reachability query as a generalized form of the s-reachability problem, which aims to find the largest value of s that allows one vertex to reach another. To answer max-reachability queries in hypergraphs, we first analyze limitations of the existing vertex-to-vertex and hyperedge-to-hyperedge indexing techniques. We then introduce the HL-index, a compact vertex-to-hyperedge index tailored for the max-reachability problem. To both efficiently and effectively construct a minimal HL-index, we develop a fast covering relationship detection method to eliminate fruitless hypergraph traversals during index construction. A lightweight neighbor-index is further proposed to avoid repeatedly exploring neighbor relationships in hypergraphs and hence accelerate the construction. Extensive experiments on 20 datasets demonstrate the efficiency and scalability of our approach.

For complex networks such as the Web, the Network Dismantling (ND) problem, which asks for the minimum-cost removal of nodes that destroys the giant connected component in the network, is significant in system robustness and misinformation containment. In this paper, we propose a heuristic algorithm, IG+, which is based on reverse dismantling and incorporates novel optimizations. Besides, we design two dynamic algorithms, CCRT-ins and CCRT-rem, employing tree-like indexes to update dismantling results efficiently. Experiments show that our methods outperform state-of-the-art approaches in both effectiveness and efficiency, and can dismantle 10-million-scale networks at arbitrary granularity in a few minutes.

Large Language Models (LLMs) have achieved impressive reasoning abilities, but struggle with temporal understanding, especially when questions involve multiple entities, compound operators, and evolving event sequences. Temporal Knowledge Graphs (TKGs), which capture vast amounts of temporal facts in a structured format, offer a reliable source for temporal reasoning. However, existing TKG-based LLM reasoning methods still struggle with four major challenges: maintaining temporal faithfulness in multi-hop reasoning, achieving multi-entity temporal synchronization, adapting retrieval to diverse temporal operators, and reusing prior reasoning experience for stability and efficiency. To address these issues, we propose MemoTime, a memory-augmented temporal knowledge graph framework that enhances LLM reasoning through structured grounding, recursive reasoning, and continual experience learning. MemoTime decomposes complex temporal questions into a hierarchical Tree of Time, enabling operator-aware reasoning that enforces monotonic timestamps and co-constrains multiple entities under unified temporal bounds. A dynamic evidence retrieval layer adaptively selects operator-specific retrieval strategies, while a self-evolving experience memory stores verified reasoning traces, toolkit decisions, and sub-question embeddings for cross-type reuse. Comprehensive experiments on multiple temporal QA benchmarks show that MemoTime achieves overall state-of-the-art results, outperforming the strong baseline by up to 24.0%. Furthermore, MemoTime enables smaller models (e.g., Qwen3-4B) to achieve reasoning performance comparable to that of GPT-4-Turbo.

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.

Cyberbullying is a pervasive issue on online platforms, yet early intervention via predictive modeling remains an open challenge. This challenge is compounded by the temporal dynamics of user interactions and the sparsity of such interactions in real-world social networks, making reliable modeling difficult. Current methods predominantly focus on detecting cyberbullying after it occurs through user content and profiles, while overlooking the temporal patterns and struggling when social interaction data is limited. We propose TemSoGraph, a unified temporal social graph learning model for cyberbullying detection and prediction. The model leverages a temporal self-attention mechanism to capture time-evolving user interactions and employs joint global and local node updates to represent users with limited interactions. It further incorporates a domain adaptor that learns domain-invariant features, enhancing generalization across datasets even when labeled target data is scarce. Experiments on two real-world datasets, Instagram and Vine, show that TemSoGraph outperforms eight cyberbullying detection models in detection task and six dynamic graph neural networks in prediction task. On the prediction task, TemSoGraph achieves a recall of 97.18% on Instagram with 2.53% improvement and 93.38% on Vine with 6.25% improvement. The model supports both detection and future prediction and provides a strong benchmark for cyberbullying modeling. • We propose TemSoGraph model for cyberbullying detection and prediction. • TemSoGraph works effectively under real-world data sparsity problem. • TemSoGraph integrates domain adaptor for cross-dataset generalization.

Multiplex graphs represent diverse real-world interactions among entities, where multiple relationship types coexist within the same set of entities. These graphs introduce privacy risks, as data collectors can exploit cross-layer dependencies to infer hidden and sensitive connections. In this work, we propose aC2P-Mframework that identifies and protects critical connections while preserving the structural information in multiplex graphs. Unlike conventional methods for single-layer graphs that perturb all edges uniformly,C2P-Mselectively protects critical connections, maintaining the analytical usability of the graph. To achieve this, we introduce the multiplex$p$-cohesion model, which incorporates new score functions that account for both intra-layer and inter-layer dependencies, enabling precise identification of critical connections for each vertex. For privacy protection, our method protects the identified critical connections, leveraging an adaptive Randomized Response (RR) mechanism to ensure$\varepsilon$-Local Differential Privacy (LDP). We formally prove thatC2P-Msatisfies$\varepsilon$-LDP. Extensive experiments on eight real-world multiplex graph datasets demonstrate thatC2P-Msignificantly outperforms baseline privacy-preserving methods, achieving a better privacy-utility trade-off.

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.

Spatio-temporal trajectories carry identifying information and are vulnerable to privacy breaches. Existing studies predominantly focus on the spatial domain. The temporal aspect remains underexplored, leaving privacy risks unaddressed. This paper highlights these risks by introducing a new trajectory matching model, ST-ATT, which leverages attention-enhanced Long Short-Term Memory (LSTM) to effectively capture the spatio-temporal correlations within trajectories. ST-ATT excels in identifying similar trajectories. To defend against linkage attacks on spatio-temporal trajectories, including advanced models like ST-ATT, we propose a novel Differential Privacy (DP) mechanism specifically designed to address the privacy risks. We reveal that the privacy budget and violation probability for each spatial point explicitly depend on earlier timestamps. The privacy budget can be flexibly redistributed between spatial and temporal domains without compromising overall privacy. This mechanism complies with DP, even when spatio-temporal points are reordered due to perturbation. Experiments show that ST-ATT can accurately identify spatio-temporal trajectories perturbed by the existing DP methods adding noise solely to the spatial domain. The proposed spatio-temporal DP mechanism resists ST-ATT, highlighting the need for considering spatio-temporal correlations to ensure robust privacy protection in spatio-temporal trajectories.

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.

Sentiment bias is newly discovered in Recommender Systems (RSs). Critical users and niche items are disadvantaged by such unfair recommendations. To mitigate this bias, we propose a novel approach by counterfactual inference, which is implemented in two stages. Experiment results validate that our model achieves comparable performance in rating prediction, providing better recommendations and effectively mitigating sentiment bias. To the best of our knowledge, this is the first work to employ counterfactual inference on sentiment bias mitigation in RSs.

Signed Graph Neural Networks (SGNNs) are effective in learning expressive representations for signed graphs but typically require substantial task-specific labels, limiting their applicability in label-scarce industrial scenarios. In contrast, unsigned graph structures are abundant and can be readily leveraged to pre-train Graph Neural Networks (GNNs), offering a promising solution to reduce supervision requirements in downstream signed graph tasks. However, transferring knowledge from unsigned to signed graphs is non-trivial due to the fundamental discrepancies in graph types and task objectives between pre-training and downstream phases. To address this challenge, we propose Signed Graph Prompt Tuning (SGPT), a novel graph prompting framework that adapts pre-trained unsigned GNNs to few-shot signed graph tasks. We first design a graph template based on balance theory to disentangle mixed node relationships introduced by negative links, mitigating the structural mismatches between unsigned and signed graphs. We further introduce a task template that reformulates downstream signed tasks into a unified link prediction objective, aligning their optimization goals with the pre-training task. Furthermore, we develop feature prompts that align downstream semantic spaces with the feature spaces learned during pre-training, and semantic prompts to integrate link sign semantics in a task-aware manner. We conduct extensive experiments on seven benchmark signed graph datasets, demonstrating that SGPT significantly outperforms existing state-of-the-art methods, establishing a powerful and generalizable solution for few-shot signed graph learning.

As artificial intelligence technology continues to advance, artificial intelligence-generated content (AIGC) has begun to evolve towards generating complex and structured data, particularly graph data. As an important topic in many fields such as database, data mining, and machine learning, graph generation holds significant value for simulating complex relationships between entities and has shown vast potential for applications in fields such as molecular generation, drug design, and material discovery. In this context, AIGC technology for graph generation has received widespread attention. This tutorial outlines the latest developments in AIGC for graph generation. We categorize existing methods into two main types according to their objectives and motivations: similarity-based generation and function-driven generation. We first provide an overview of AIGC models for graph generation. Then, we conduct a thorough review of the existing works. Finally, we explore the current trends and future directions, discussing potential ways to integrate database and machine learning techniques for graph generation.

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%.

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.

Large Language Models (LLMs) have achieved impressive results in various tasks but struggle with hallucination problems and lack of relevant knowledge, especially in deep complex reasoning and knowledge-intensive tasks.Knowledge Graphs (KGs), which capture vast amounts of facts in a structured format, offer a reliable source of knowledge for reasoning.However, existing KG-based LLM reasoning methods face challenges like handling multi-hop reasoning, multi-entity questions, and effectively utilizing graph structures.To address these issues, we propose Paths-over-Graph (PoG), a novel method that enhances LLM reasoning by integrating knowledge reasoning paths from KGs, improving the interpretability and faithfulness of LLM outputs.PoG tackles multi-hop and multi-entity questions through a three-phase dynamic multi-hop path exploration, which combines the inherent knowledge of LLMs with factual knowledge from KGs.In order to improve the efficiency, PoG prunes irrelevant information from the graph exploration first and introduces efficient three-step pruning techniques that incorporate graph structures, LLM prompting, and a pre-trained language model (e.g., SBERT) to effectively narrow down the explored candidate paths.This ensures all reasoning paths contain highly relevant information captured from KGs, making the reasoning faithful and interpretable in problem-solving.PoG innovatively utilizes graph structure to prune the irrelevant noise and represents the first method to implement multi-entity deep path detection on KGs for LLM reasoning tasks.Comprehensive experiments on five benchmark KGQA datasets demonstrate PoG outperforms the stateof-the-art method ToG across GPT-3.5-Turbo and GPT-4, achieving an average accuracy improvement of 18.9%.Notably, PoG with GPT-3.5-Turbosurpasses ToG with GPT-4 by up to 23.9%.

Subgraph matching is a fundamental task in graph analysis systems. In real-world applications, graph query engines often need to process a large number of subgraph matching queries, many of which share common substructures. Materializing the results of these shared subqueries as view patterns can enable computation reuse and significantly improve query efficiency. However, existing view materialization techniques suffer from either high memory usage or limited acceleration benefits.This paper introduces MAVIS, a novel view-based subgraph matching algorithm. MAVIS partitions view patterns into connected subgraphs called super-nodes and performs super-node-oriented materialization to balance memory consumption and processing speed. To further improve efficiency, it proposes a tree-based super-node partitioning method that avoids generating invalid candidates during materialization. Additionally, a customized query answering algorithm is designed to leverage the materialized views for faster query execution.Extensive experiments on real-world datasets demonstrate that MAVIS achieves a superior trade-off between memory usage and acceleration, and it outperforms existing approaches.

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.

Influence minimization (IMIN) aims to identify a set of nodes to be blocked, such that the expected number of nodes activated by the given seed set is minimized. It has many important applications, such as misinformation suppression, and has been extensively studied in the literature. Existing works for IMIN, however, neglect key temporal information in real-world scenarios. In this paper, we generalize IMIN and study the time-critical influence minimization (TCIM) problem, which aims to minimize the activation duration-aware influence spread of the seed set by a deadline via node blocking. We show that TCIM is NP-hard and APX-hard, and the objective function is non-submodular. To address the problem, we propose CBFM, an efficient and effective algorithm that provides τ(1-1/e-ε)-approximation with at least 1-3δ probability, where τ is a data-driven parameter, ε and δ are tunable error parameters. Novel concentration results are designed to facilitate the establishment of the approximation guarantee. Moreover, we show that CBFM can be extended to tackle the misinformation mitigation (MM) problem. The existing MM solution offers the approximation guarantee only under specific assumptions. Our extended approach is assumption-free yet still attains the same guarantee, thereby bridging the theoretical gap. Finally, we conduct extensive experiments on 11 datasets to validate the performance of proposed algorithms on TCIM, IMIN (a special case of TCIM), and MM problems. The results show that for TCIM, CBFM achieves up to four orders of magnitude speedup over the baseline; for IMIN, CBFM outperforms the state-of-the-art in terms of efficiency, approximation ratio, and memory usage. Moreover, for MM, our solution can be two orders of magnitude faster than the corresponding state-of-the-art.

Multi-way join, which refers to the join operation among multiple tables, is widely used in database systems. With the development of the Internet and social networks, a new variant of the multi-way join query has emerged, requiring continuous monitoring of the query results as the database is updated. This variant is called continuous multi-way join. The join order of continuous multi-way join significantly impacts the operation's cost. However, existing methods for continuous multi-way join order selection are heuristic, which may fail to select the most efficient orders. On the other hand, the high-cost order computation will become a system bottleneck if we directly transfer join order selection algorithms for static multi-way join to the dynamic setting. In this paper, we propose a new A daptive J oin O rder S election algorithm for the C ontinuous multi-way join queries named AJOSC. It uses dynamic programming to find the optimal join order with a new cost model specifically designed for continuous multi-way join. We further propose a lower-bound-based incremental re-optimization algorithm to restrict the search space and recompute the join order with low cost when data distribution changes. Experimental results show that AJOSC is up to two orders of magnitude faster than the state-of-the-art methods.

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.

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.

Cardinality estimation is a fundamental functionality in database systems. Most existing cardinality estimators focus on handling predicates over numeric or categorical data. They have largely omitted an important data type, set-valued data, which frequently occur in contemporary applications such as information retrieval and recommender systems. The few existing estimators for such data either favor high-frequency elements or rely on a partial independence assumption , which limits their practical applicability. We propose ACE, an Attention-based Cardinality Estimator for estimating the cardinality of queries over set-valued data. We first design a distillation-based data encoder to condense the dataset into a compact matrix. We then design an attention-based query analyzer to capture correlations among query elements. To handle variable-sized queries, a pooling module is introduced, followed by a regression model (MLP) to generate final cardinality estimates. We evaluate ACE on three datasets with varying query element distributions, demonstrating that ACE outperforms the state-of-the-art competitors in terms of both accuracy and efficiency.

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.

Machine learning techniques have been proposed to optimize the performance of graph databases in recent years. Due to the NP-hardness of graph database tasks and the complexity of graph data, traditional exact solutions usually encounter efficiency issues, while the performance of approximation solutions can be affected by issues like sampling failure and local optimality. Empowered by the inherent advantages of machine learning, the learning-based techniques show the generalization ability and better performance in many scenarios, including graph data management and graph query processing. Despite the efficiency and accuracy brought by machine learning techniques, machine learning for graph database models still face several critical challenges, including scalability and adaptability. In this tutorial, we first provide an in-depth survey of learning-based graph data management and query processing techniques published in recent database and data mining conferences to sketch the frontier of the research of Machine Learning for Graph Database. We also discuss the open challenges and provide future directions.

Community detection is a fundamental problem and has been extensively studied. With the abundance of information in real-world networks, the discovery of communities in attribute graphs is increasingly valuable. However, numerous previous models in attribute graphs neglect the fairness concept, which plays an important role in ensuring that graph analysis is not biased toward specific groups. In this paper, we propose a novel model, named proportional fair clique (PFC). Specifically, given an attribute graph G = (V, E, A), an integer k and a threshold λ ∊ [0, 1/|A|], a subgraph S of G is a PFC if (i) S is a clique with size at least k and (ii) |Sai |/|S| ≥ λ for each attribute ai in G, where Sai is the node set in S associated with attribute ai. We show that the problem of enumerating all the maximal proportional fair cliques (MPFC) is NP-hard. A reasonable baseline algorithm is first presented by extending the BronKerbosch framework. To scale for large networks, we propose several optimization strategies to accelerate the computation. Finally, comprehensive experiments are conducted over 6 graphs to demonstrate the efficiency and effectiveness of the proposed techniques and model.

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.

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.

Along with the rapid technological and commercial innovation on e-commerce platforms, an increasing number of frauds cause great harm to these platforms. Many frauds are conducted by organized groups of fraudsters for higher efficiency and lower costs, also known as group-based frauds. Despite the high concealment and strong destructiveness of group-based fraud, no existing research can thoroughly exploit the information within the transaction networks of e-commerce platforms for group-based fraud detection. In this work, we analyze and summarize the characteristics of group-based frauds. Based on this, we propose a novel end-to-end semi-supervised Group-based Fraud Detection Network (GFDN) to support such fraud detection in real-world applications. In addition, we introduce a module namedTemporal Group Dynamics Analyzer(TGDA) that strengthens the ability to analyze temporal information on group fraudulent activity. Based on this, we built an enhanced model named TGFDN. Experimental results on large-scale e-commerce datasets from Taobao and Bitcoin trading datasets show our proposed model's superior effectiveness and efficiency for group-based fraud detection on bipartite graphs.

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.

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.

As the field of data science continues to evolve, bipartite graphs have emerged as a fundamental structure in numerous applications, drawing significant interest from both academic and industrial communities. Bipartite graphs are a specific type of graph consisting of two distinct sets of vertices, where connections only occur between vertices of different sets. Examples include e-commerce networks and biological networks. Analytics of bipartite graphs has become an important research topic in the era of big data. This tutorial aims to shed light on analysis methods for bipartite graphs, categorizing them into three areas: classical models, learning-based models, and application-driven models. We start by outlining the importance of bipartite graph analytics, and the unique challenges that need to be addressed. Then, we conduct a thorough review of existing works on bipartite graph analytics. We also compare and analyze the models and solutions in these works. Finally, we point out new research directions.

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.

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.

Finding the optimal Steiner Tree in graphs has been a critical combinatorial optimization challenge that finds widespread applications in network design. Despite its importance, finding the optimal Steiner Tree remains computationally expensive, especially for large graphs due to its NP-hard nature. Traditional approaches often suffer from high time complexity or poor approximation ratio. Machine learning approaches often leverage local graph structure information instead of global graph structure information, and often suffer from the generalization ability issues in practice. In this paper, we propose a novel reinforcement learning based framework to solve STP, in which we reformulate the classical Q-value computation to capture both global graph structure and deterministic information to search for the Steiner tree. Experiments on both synthetic and real-world datasets demonstrate that our framework exhibits better generalization ability compared to the existing machine learning methods, where our framework can be trained on the small graphs and generalize well to larger graphs and the graphs from different distributions.

Logical query answering over Knowledge Graphs (KGs) is a fundamental yet complex task. A promising approach to achieve this is to embed queries and entities jointly into the same embedding space. Research along this line suggests that using multi-modal distribution to represent answer entities is more suitable than uni-modal distribution, as a single query may contain multiple disjoint answer subsets due to the compositional nature of multi-hop queries and the varying latent semantics of relations. However, existing methods based on multi-modal distribution roughly represent each subset without capturing its accurate cardinality, or even degenerate into uni-modal distribution learning during the reasoning process due to the lack of an effective similarity measure. To better model queries with diversified answers, we propose Query2GMM for answering logical queries over knowledge graphs. In Query2GMM, we present the GMM embedding to represent each query using a univariate Gaussian Mixture Model (GMM). Each subset of a query is encoded by its cardinality, semantic center and dispersion degree, allowing for precise representation of multiple subsets. Then we design specific neural networks for each operator to handle the inherent complexity that comes with multi-modal distribution while alleviating the cascading errors. Last, we design a new similarity measure to assess the relationships between an entity and a query's multi-answer subsets, enabling effective multi-modal distribution learning for reasoning. Comprehensive experimental results show that Query2GMM outperforms the best competitor by an absolute average of 6.35%.

Influence Maximization (IM) has promising applications in social network marketing and has been extensively researched over the past years. However, previous IM studies mainly focus on ordinary graphs rather than hypergraphs, where edges cannot accurately describe group interactions or relationships. To model group interactions, we investigate the IM problem on hypergraphs under the Susceptible–Infected spreading model with Contact Process dynamics (SICP) in this paper. In this paper, we proposed a probability distribution-based method, called Multi-hop Influence Estimation (MIE), which can accurately estimate the rank of influence expectation of nodes, to solve the IM problem on hypergraphs. Specifically, we compute the influence score for each node through a constrained Depth First Search (DFS) under a probability model, and then select seed node according to the influence score. In addition, by analysing the characteristics of the influence diffusion model, we find that the influence of a node is significantly related to its neighbourhood structure. Based on the observation, we propose a term named neighbourhood coefficient to describe the neighbourhood structure of a node. Further, an efficient and effective method, called Adaptive Neighbourhood Coefficient Algorithm (Adeff), is proposed to solve the IM problem on hypergraphs. Extensive experiments on real-world datasets demonstrate the effectiveness and efficiency of our proposed methods. Compared with the state-of-the-art approach, our proposed methods can achieve up to 450% improvement in terms of effectiveness.

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.

In this paper, we tackle the challenging problem of Shapley value computation in data markets in a novel setting of data assemblage tasks with binary utility functions among data owners. By modeling these scenarios as cooperative simple games, we leverage pivotal probabilities to transform the computation into a problem of counting beneficiaries. Moreover, we make an insightful observation that the Shapley values can be computed using subsets of minimal syntheses within the inclusion-exclusion framework in combinatorics. Based on this insight, we develop a game decomposition approach and utilize techniques in Boolean function decomposition into disjunctive normal form. One interesting property of our method is that the time complexity depends only on the data owners participating in those minimal syntheses, rather than all the data owners. Extensive experiments with real data sets demonstrate a significant efficiency improvement for computing the Shapley values in data assemblage tasks modeled as simple games.

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.

Real-world directed graphs are dynamically changing, and it is important to identify and maintain the strong connectivity information between nodes, which is useful in numerous applications. Given an input graphG, we study a new problem,minimum strongly connected subgraph collection(MSCSC), which asks for a complete collection of subgraphs, each of which contains amaximalset of nodes that are strongly connected to each other viaminimumnumber of edges inG. MSCSC is NP-hard, and its computation and maintenance are challenging, especially on large-scale dynamic graphs. Thus, we resort to approximate MSCSC with theoretical guarantees. We develop a series of approximate MSCSC methods for both static and dynamic graphs. Specifically, we first develop a static MSCSC method MSC that only needs one scan of the graphG, runs in linear timew.r.t., the number of edges, and provides rigorous approximation guarantees. Then, based on MSC, we leverage a reduced directed acyclic graph ofGto design incremental MSCSC method MSCiwith two variants to handle edge insertions efficiently. We further develop MSCdthat updates MSCSC under edge deletions by efficiently scanning only locally affected subgraphs. Moreover, to demonstrate the high utility, we conduct two use case studies to apply our MSCSC methods to boost the efficiency of dynamic strongly connected component (SCC) maintenance and dynamic SCC-based reachability index maintenance. Extensive experiments on 8 large graphs, including 3 billion-edge graphs, validate the superior efficiency of our methods.

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.

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.

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.

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.

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.

Many real-world interconnections among entities can be characterized as graphs. Collecting local graph information with balanced privacy and data utility has garnered notable interest recently. This paper delves into the problem of identifying and protecting critical information of entity connections for individual participants in a graph based on cohesive subgraph searches. This problem has not been addressed in the literature. To address the problem, we propose to extract the critical connections of a queried vertex using a fortress-like cohesive subgraph model known as$p$-cohesion. A user's connections within a fortress are obfuscated when being released, to protect critical information about the user. Novel merit and penalty score functions are designed to measure each participant's critical connections in the minimal$p$-cohesion., facilitating effective identification of the connections. We further propose to preserve the privacy of a vertex enquired by only protecting its critical connections when responding to queries raised by data collectors. We prove that, under the decentralized differential privacy (DDP) mechanism, one's response satisfies$(\varepsilon , \delta )$-DDP when its critical connections are protected while the rest remains unperturbed. The effectiveness of our proposed method is demonstrated through extensive experiments on real-life graph datasets.

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.

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.

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.

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.

k-peak is a well-regarded cohesive subgraph model in graph analysis. However, the k-peak model only considers the direct neighbors of a vertex, consequently limiting its capacity to uncover higher-order structural information of the graph. To address this limitation, we propose a new model in this paper, named (k,h)-peak, which incorporates higher-order (h-hops) neighborhood information of vertices. Employing the (k,h)-peak model, we explore the higher-order peak decomposition problem that calculates the vertex peakness for all conceivable k values given a particular h. To tackle this problem efficiently, we propose an advanced local computation based algorithm, which is parallelizable, and additionally, devise novel pruning strategies to mitigate unnecessary computation. Experiments as well as case studies are conducted on real-world datasets to evaluate the efficiency and effectiveness of our proposed solutions.

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.

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.

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.

Computing the maximum independent set (MIS) in a graph is a fundamental NP-hard problem, which is widely adopted in many real-world applications. Extensive works have been done on computing an approximate MIS. While the highly dynamic property of real-world graphs calls for efficient MIS maintenance solutions, existing works for dynamic MIS computation in the literature mainly focus on the single-machine scenario. The assumption that a single machine can access the whole graph makes them difficult to be straightforwardly applied for large-scale graphs in distributed environment. Motivated by this, in this paper, we study the problem of maintaining approximate MIS over large-scale dynamic graphs in distributed environments. We propose a new vertex centric algorithm OIMIS. Compared with existing solutions, OIMIS avoids the strong order dependency in distributed computation, which makes it easy to handle dynamic graph updates. OIMIS computes and maintains MIS with high effectiveness and efficiency. In terms of high effectiveness, OIMIS maintains consistent MIS results with the state-of-the-art distributed algorithm to compute MIS in static graphs. In terms of high efficiency, each vertex in OIMIS only updates MIS status according to its neighbor attributes. Novel optimization techniques are also designed to reduce communication and computation cost. We conduct extensive experiments to prove the effectiveness and efficiency of our distributed algorithms.

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.

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.

Along with the rapid technological and commercial innovation on the e-commerce platforms, there are an increasing number of frauds that bring great harm to these platforms. Many frauds are conducted by organized groups of fraudsters for higher efficiency and lower costs, which are also known as group-based frauds. Despite the high concealment and strong destructiveness of group-based fraud, there is no existing research work that can thoroughly exploit the information within the transaction networks of e-commerce platforms for group-based fraud detection. In this work, we analyze and summarize the characteristics of group-based frauds, based on which we propose a novel end-to-end semi-supervised Group-based Fraud Detection Network (GFDN) to support such fraud detection in real-world applications. Experimental results on large-scale e-commerce datasets from Taobao and Bitcoin trading datasets show the superior effectiveness and efficiency of our proposed model for group-based fraud detection on bipartite graphs.

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.

Spatial objects often come with textual information, such as Points of Interest (POIs) with their descriptions, which are referred to as geo-textual data. To retrieve such data, spatial keyword queries that take into account both spatial proximity and textual relevance have been extensively studied. Existing indexes designed for spatial keyword queries are mostly built based on the geo-textual data without considering the distribution of queries already received. However, previous studies have shown that utilizing the known query distribution can improve the index structure for future query processing. In this paper, we propose WISK, a learned index for spatial keyword queries, which self-adapts for optimizing querying costs given a query workload. One key challenge is how to utilize both structured spatial attributes and unstructured textual information during learning the index. We first divide the data objects into partitions, aiming to minimize the processing costs of the given query workload. We prove the NP-hardness of the partitioning problem and propose a machine learning model to find the optimal partitions. Then, to achieve more pruning power, we build a hierarchical structure based on the generated partitions in a bottom-up manner with a reinforcement learning-based approach. We conduct extensive experiments on real-world datasets and query workloads with various distributions, and the results show that WISK outperforms all competitors, achieving up to 8× speedup in querying time with comparable storage overhead.

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.

Bipartite graph embedding (BGE), as the fundamental task in bipartite network analysis, is to map each node to compact low-dimensional vectors that preserve intrinsic properties. The existing solutions towards BGE fall into two groups: metric-based methods and graph neural network-based (GNN-based) methods. The latter typically generates higher-quality embeddings than the former due to the strong representation ability of deep learning. Nevertheless, none of the existing GNN-based methods can handle billion-scale bipartite graphs due to the expensive message passing or complex modelling choices. Hence, existing solutions face a challenge in achieving both embedding quality and model scalability. Motivated by this, we propose a novel graph neural network named AnchorGNN based on global-local learning framework, which can generate high-quality BGE and scale to billion-scale bipartite graphs. Concretely, AnchorGNN leverages a novel anchor-based message passing schema for global learning, which enables global knowledge to be incorporated to generate node embeddings. Meanwhile, AnchorGNN offers an efficient one-hop local structure modelling using maximum likelihood estimation for bipartite graphs with rational analysis, avoiding large adjacency matrix construction. Both global information and local structure are integrated to generate distinguishable node embeddings. Extensive experiments demonstrate that AnchorGNN outperforms the best competitor by up to 36% in accuracy and achieves up to 28 times speed-up against the only metric-based baseline on billion-scale bipartite graphs.

Computing the graph edit distance (GED) between graphs is the core operation in graph similarity search. Recent studies suggest that the existing index structures are ineffective in reducing the overall processing time of graph similarity search, and that directly verifying the GED between the query graph and every data graph in the database is still the best option. The state-of-the-art algorithm for GED verification is the recently proposed AStar-LSa. However, AStar-LSa may consume an extremely large amount of main memory or even run out-of-memory, when the graphs become larger and/or the GED threshold becomes larger. In this paper, we aim to improve the efficiency of GED verification and simultaneously lower the main memory consumption. To achieve that, we propose a new estimation for the lower bounds of partial mappings between graphs. We formally prove that our new lower bound is tighter than the one used in AStar-LSa. Moreover, we also propose efficient algorithms to compute the lower bounds, as well as optimization techniques to improve the efficiency. Empirical studies on real datasets demonstrate that our newly proposed algorithm AStar-BMao runs faster, and at the same time consumes much less main memory, than AStar-LSa.

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.

Heterogeneous graphs, which contain nodes and edges of multiple types, are prevalent in various domains, including bibliographic networks, social media, and knowledge graphs. As a fundamental task in analyzing heterogeneous graphs, relevance measure aims to calculate the relevance between two objects of different types, which has been used in many applications such as web search, recommendation, and community detection. Most of existing relevance measures focus on homogeneous networks where objects are of the same type, and a few measures are developed for heterogeneous graphs, but they often need the pre-defined meta-path. Defining meaningful meta-paths requires much domain knowledge, which largely limits their applications, especially on schema-rich heterogeneous graphs like knowledge graphs. Recently, the Graph Neural Network (GNN) has been widely applied in many graph mining tasks, but it has not been applied for measuring relevance yet. To address the aforementioned problems, we propose a novel GNN-based relevance measure, namely GSim. Specifically, we first theoretically analyze and show that GNN is effective for measuring the relevance of nodes in the graph. We then propose a context path-based graph neural network (CP-GNN) to automatically leverage the semantics in heterogeneous graphs. Moreover, we exploit CP-GNN to support relevance measures between two objects of any type. Extensive experiments demonstrate that GSim outperforms existing measures. (Coda and data is available at this linkhttps://github.com/RManLuo/GSim).

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.

Designing distributed graph systems has drawn a lot of research interests due to the strong expressiveness of the graph model and rapidly increasing graph volume. Most of them require the graph data and all intermediate messages to reside in main memory, which may sacrifice the scalability. Even though several disk-based systems have been studied to remedy such issue, several challenges still exist in achieving both high computational efficiency and low network communication under the limitation of memory usage. In this paper, we design a novel disk-based distributed graph system, called ScaleG. The system provides a series of user-friendly programming interfaces. Unlike previous systems, the programmer in ScaleG does not need to concern any logic regarding the communication between vertices like sending messages and combining messages. In addition to a simple and clear programming model, we propose several techniques to reduce both disk I/Os in each machine and message I/Os via the network. We manage all messages in memory and bound all messages by the number of vertices. We also carefully design the data structure to support partial computation and automatic vertex activation. We conduct extensive experiments on six big graphs to show the high efficiency of our system.

In this article, we study the problem of maximal biclique enumeration on large uncertain bipartite graphs. Given an uncertain bipartite graph$\mathcal {G}=(U,V,E,p)$, a probability threshold$\tau$, and two size constraints$\alpha$and$\beta$, we aim to efficiently enumerate all maximal$\tau$-bicliques in$\mathcal {G}$, where a maximal$\tau$-biclique$B(L,R)$is a complete subgraph of$\mathcal {G}$with (1) the probability of$B$is no less than$\tau$, (2)$|L| \geq \alpha$and$|R| \geq \beta$, and (3)$B$is a maximal complete subgraph satisfying (1) and (2). This problem has many applications, such as biclustering of gene expression data, fraud detection, similar group identification, etc. Despite the wide range of applications, to the best of our knowledge, we note that there are no efficient and scalable solutions to this problem in the literature. This problem is computationally challenging due to its #P-completeness. In this article, we propose a competitive branch-and-bound method, namely${\sf MBEN}$, which explores the search space in a depth-first manner with a variety of pruning techniques. To improve the performance of${\sf MBEN}$, we propose several novel and efficient search processing optimizations. First, we always select the side with fewer candidates to expand the search space. With this search strategy, we have a chance to prune the fruitless branches early. Second, we devise an advanced pruning technique by considering the size pruning and probability pruning at the same time to boost the pruning capacity. Last, we implement${\sf MBEN}$with pre-allocated arrays and pointer maintaining techniques such that the frequent work sets creating operations can be substituted by array element switching operations. In addition, we introduce useful graph reduction techniques to further accelerate the computation. Comprehensive performance studies on 10 real datasets demonstrate that our proposals can significantly outperform the baseline methods by more than two orders of magnitude.

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 model relationships between two types of entities. Community search retrieves densely connected subgraphs containing a query vertex, which has been extensively studied on unipartite graphs. However, it remains largely unexplored on bipartite graphs. Moreover, all existing cohesive subgraph models on bipartite graphs only measure the structure cohesiveness while overlooking the edge weight. In this paper, we study the significant (alpha, beta)-community search problem on weighted bipartite graphs. Given a query vertex q, we aim to find the significant (alpha, beta)-community R of q which adopts (alpha, beta)-core to characterize the engagement level of vertices, and maximizes the minimum edge weight (significance) within R. To support fast retrieval of R, we first obtain the maximal connected subgraph of (alpha, beta)-core containing q (the (alpha, beta)-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 to support retrieving the (alpha, beta)-community in optimal time. Efficient index maintenance techniques are also proposed to handle dynamic graphs. To further obtain R, we develop peeling and expansion algorithms. The experimental results on real graphs validate the effectiveness and efficiency 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.

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 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.

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.

Designing disk-based distributed graph systems has drawn a lot of research due to the strong expressiveness of the graph model and rapidly increasing graph volume. However, several challenges still exist in achieving both high computational efficiency and low network communication under the limitation of memory. In this paper, we design a novel distributed disk-based graph processing system, ScaleG, with a series of user-friendly programming interfaces. We propose several techniques to reduce both disk I/Os in each machine and message I/Os via the network. We manage all messages in memory and bound the volume of all messages by the number of vertices. We also carefully design the data structure to support partial computation and automatic vertex activation. We conduct extensive experiments on real-world big graphs to show the high efficiency of our system.

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.

Trajectory similarity computation is the cornerstone of many applications in the field of trajectory data analysis. To cope with the high time complexity of calculating exact similarity between trajectories, learning-based models have been developed for a good trade-off between the similarity computing time and the accuracy of the learned similarity. As each trajectory can be represented by a fixed-length vector regardless of the size of the trajectory, the similarity computation among the trajectories is highly time-efficient. Nevertheless, we observe that these learning-based models are designed based on recurrent neural networks (RNN), which cannot properly capture the correlations among the trajectories. Moreover, these learning-based models simply use the similarity scores of the pairs of trajectories in the training for a specific similarity metric, while a vital piece of information is neglected: the mappings of the points between two trajectories are readily available when the similarity score is calculated. These motivate us to design a new learning-based model, named TMN, based on attention networks, aiming to significantly improve the accuracy such that a better trade-off between the similarity computing time and the accuracy can be achieved. The proposed matching mechanism associates points across trajectories by computing attention weights of point pairs so that TMN learns to simulate similarity computation between the trajectory pair. Apart from taking interactions between trajectories into consideration, the sequential information of each individual trajectory is also considered, thereby making full use of spatial features of a pair of trajectories. We evaluate various approaches on real-life datasets under extensive trajectory distance metrics. Experimental results demonstrate that TMN outperforms state-of-the-art methods in terms of accuracy. Besides, ablation studies prove the effectiveness of our novel matching mechanism.

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.

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.

Subgraph counting is a fundamental graph analysis task which has been widely used in many applications. As the problem of subgraph counting is NP-complete and hence intractable, approximate solutions have been widely studied, which fail to work with large and complex query graphs. Alternatively, Machine Learning techniques have been recently applied for this problem, yet the existing ML approaches either only support very small data graphs or cannot make full use of the data graph information, which inherently limits their scalability, estimation accuracies and robustness.

Nowadays, ridesharing becomes a popular commuting mode. Dynamically arriving riders post their origins and destinations, then the platform assigns drivers to serve them. In ridesharing, different groups of riders can be served by one driver if their trips can share common routes. Recently, many ridesharing companies (e.g., Didi and Uber) further propose a new mode, namely "ridesharing with meeting points". Specifically, with a short walking distance but less payment, riders can be picked up and dropped off around their origins and destinations, respectively. In addition, meeting points enables more flexible routing for drivers, which can potentially improve the global profit of the system. In this paper, we first formally define the Meeting-Point-based Online Ridesharing Problem (MORP). We prove that MORP is NP-hard and there is no polynomial-time deterministic algorithm with a constant competitive ratio for it. We notice that a structure of vertex set, k -skip cover, fits well to the MORP. k -skip cover tends to find the vertices (meeting points) that are convenient for riders and drivers to come and go. With meeting points, MORP tends to serve more riders with these convenient vertices. Based on the idea, we introduce a convenience-based meeting point candidates selection algorithm. We further propose a hierarchical meeting-point oriented graph (HMPO graph), which ranks vertices for assignment effectiveness and constructs k -skip cover to accelerate the whole assignment process. Finally, we utilize the merits of k -skip cover points for ridesharing and propose a novel algorithm, namely SMDB, to solve MORP. Extensive experiments on real and synthetic datasets validate the effectiveness and efficiency of our algorithms.

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.

Community detection, aiming to group the graph nodes into clusters with dense inner-connection, is a fundamental graph mining task. Recently, it has been studied on the heterogeneous graph, which contains multiple types of nodes and edges, posing great challenges for modeling the high-order relationship between nodes. With the surge of graph embedding mechanism, it has also been adopted to community detection. A remarkable group of works use the meta-path to capture the high-order relationship between nodes and embed them into nodes' embedding to facilitate community detection. However, defining meaningful meta-paths requires much domain knowledge, which largely limits their applications, especially on schema-rich heterogeneous graphs like knowledge graphs. To alleviate this issue, in this paper, we propose to exploit the context path to capture the high-order relationship between nodes, and build a Context Path-based Graph Neural Network (CP-GNN) model. It recursively embeds the high-order relationship between nodes into the node embedding with attention mechanisms to discriminate the importance of different relationships. By maximizing the expectation of the co-occurrence of nodes connected by context paths, the model can learn the nodes' embeddings that both well preserve the high-order relationship between nodes and are helpful for community detection. Extensive experimental results on four real-world datasets show that CP-GNN outperforms the state-of-the-art community detection methods1.

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.

Tree similarity join is useful for analyzing tree structured data. The traditional threshold-based tree similarity join requires a similarity threshold, which is usually a difficult task for users. To remedy this issue, we advocate the problem of top-k tree similarity join. Given a collection of trees and a parameter k, the top-k tree similarity join aims to find k tree pairs with minimum tree edit distance (TED). Although we show that this problem can be resolved by utilizing the threshold-based join, the efficiency is unsatisfactory. In this paper, we propose an efficient algorithm, namely TopKTJoin, which generates the candidate tree pairs incrementally using an inverted index. We also derive TED lower bound for the unseen tree pairs. Together with TED value of the k-th best join result seen so far, we have a chance to terminate the algorithm early without missing any correct results. To further improve the efficiency, we propose two optimization techniques in terms of index structure and verification mechanism. We conduct comprehensive performance studies on real and synthetic datasets. The experimental results demonstrate that TopKTJoin significantly outperforms the baseline method.

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.

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.

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 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.

Abstract With the prevalence of Internet access and online services, various big graphs are generated in many real applications (e.g., online social networks and knowledge graphs). An important task on analyzing and mining these graphs is keyword search. Essentially, given a graphGand queryQassociated with a set of keywords, the keyword search aims to find a substructure (e.g., rooted tree or subgraph)SinGsuch that nodes inScollectively cover part of or all keywords inQ, and in the meanwhile,Sis optimal on some user specified semantics. Keyword search on graphs can be applied in many real-life applications, such as point-of-interests recommendation and web search facility. In spite of the great importance of graph keyword search, we, however, notice that the latest survey on this topic is far out of date. Consequently, there is prompt need to conduct a comprehensive survey in this research direction. Motivated by this, in this survey, we systematically review graph keyword search studies by classifying the existing works into different categories according to the specific problem definition. This survey aims to provide the researchers a comprehensive understanding of existing graph keyword search 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.

Hop-constrained s-t simple path (HC-s-t path) enumeration is a fundamental problem in graph analysis and has received considerable attention recently. Straightforward distributed solutions are inefficient and suffer from poor scalabiltiy when addressing this problem in billion-scale graphs due to the disability of pruning fruitless exploration or huge memory consumption. Motivated by this, in this paper, we aim to devise an efficient and scalable distributed algorithm to enumerate the HC-s-t paths in billion-scale graphs. We first propose a new hybrid search paradigm tailored for HC-s-t path enumeration. Based on the new search paradigm, we devise a distributed enumeration algorithm following the divide-and-conquer strategy. The algorithm can not only prune fruitless exploration, but also well bound the memory consumption with high parallelism. We also devise an effective workload balance mechanism that is automatically triggered by the idle machines to handle skewed workloads. Moreover, we explore the bidirectional search strategy to further improve enumeration efficiency. The experiment results demonstrate the efficiency of our proposed algorithm.

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.

In this paper, we study the problem of ( p , q)-biclique counting and enumeration for large sparse bipartite graphs. Given a bipartite G = ( U, V , E), and two integer parameters p and q, we aim to efficiently count and enumerate all (p, q)-bicliques in G , where a (p, q)-biclique B ( L, R ) is a complete subgraph of G with L ⊆ U, R ⊆ V , |L| = p, and |R| = q. The problem of (p, q)-biclique counting and enumeration has many applications, such as graph neural network information aggregation, densest subgraph detection, and cohesive subgroup analysis, etc. Despite the wide range of applications, to the best of our knowledge, we note that there is no efficient and scalable solution to this problem in the literature. This problem is computationally challenging, due to the worst-case exponential number of (p, q)-bicliques. In this paper, we propose a competitive branch-and-bound baseline method, namely BCList, which explores the search space in a depth-first manner, together with a variety of pruning techniques. Although BCList offers a useful computation framework to our problem, its worst-case time complexity is exponential to p + q. To alleviate this, we propose an advanced approach, called BCList++. Particularly, BCList++ applies a layer based exploring strategy to enumerate ( p, q )-bicliques by anchoring the search on either U or V only, which has a worst-case time complexity exponential to either p or q only. Consequently, a vital task is to choose a layer with the least computation cost. To this end, we develop a cost model, which is built upon an unbiased estimator for the density of 2-hop graph induced by U or V. To improve computation efficiency, BCList++ exploits pre-allocated arrays and vertex labeling techniques such that the frequent subgraph creating operations can be substituted by array element switching operations. We conduct extensive experiments on 16 real-life datasets, and the experimental results demonstrate that BCList++ significantly outperforms the baseline methods by up to 3 orders of magnitude. We show via a case study that (p, q)-bicliques optimize the efficiency of graph neural networks.

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.

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.

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.

A huge volume of spatio-textual objects generated from location-based services enable a wide range of spatial keyword queries. Recently, researchers have proposed a novel query, called Spatial Pattern Matching (SPM), which uses a pattern to capture users' intention. It has been demonstrated to be useful but computationally intractable. Existing algorithms suffer from the low efficiency issue, especially on large scale datasets. To enhance the performance of SPM, in this paper we propose a novel Efficient Spatial Pattern Matching (ESPM) algorithm, which exploits the inverted linear quadtree index and computes matched node pairs and object pairs level by level in a top-down manner. In particular, it focuses on pruning unpromising nodes and node pairs at the high levels, resulting in a large number of unpromising objects and object pairs to be pruned before accessing them from disk. Our experimental results on real large datasets show that ESPM is over one order of magnitude faster than the state-of-the-art algorithm, and also uses much less I/O cost.

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.

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.

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.

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.

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.

With recent advances in information technologies such as global position system and mobile internet, a huge volume of spatio-textual objects have been generated from location-based services, which enable a wide range of spatial keyword queries. Recently, researchers have proposed a novel query, called Spatial Pattern Matching (SPM), which uses a pattern to capture the user's intention. It has been demonstrated to be fundamental and useful for many real applications. Despite its usefulness, the SPM problem is computationally intractable. Existing algorithms suffer from the low efficiency issue, especially on large scale datasets. To enhance the performance of SPM, in this paper we propose a novel Efficient Spatial Pattern Matching (ESPM) algorithm, which exploits the inverted linear quadtree index and computes matched node pairs and object pairs level by level in a top-down manner. In particular, it focuses on pruning unpromising nodes and node pairs at the high levels, resulting in a large number of unpromising objects and object pairs to be pruned before accessing them from disk. We experimentally evaluate the performance of ESPM on real large datasets. Our results show that ESPM is over one order of magnitude faster than the state-of-the-art algorithm, and also uses much less I/O cost.

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.

In social networks, the leave of critical users may significantly break network engagement, i.e., lead a large number of other users to drop out. A popular model to measure social network engagement is k-core, the maximal subgraph in which every vertex has at least k neighbors. To identify critical users, we propose the collapsed k-core problem: given a graph G, a positive integer k and a budget b, we aim to find b vertices in G such that the deletion of the b vertices leads to the smallest k-core. We prove the problem is NP-hard and in approximate. An efficient algorithm is proposed, which significantly reduces the number of candidate vertices. We also study the user leave towards the model of k-truss which further considers tie strength by conducting additional computation w.r.t. k-core. We prove the corresponding collapsed k-truss problem is also NP-hard and in approximate. An efficient algorithm is proposed to solve the problem. The advantages and disadvantages of the two proposed models are experimentally compared. Comprehensive experiments on nine real-life social networks demonstrate the effectiveness and efficiency of our proposed methods.

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.

Given a set of server points (e.g., locations) P and a set of client points (e.g., users) O, the problem of maximizing bichromatic reverse k-nearest neighbor (MaxBRkNN) aims to find a region for setting up a new service site such that it can influence the most clients, i.e., it is in the kNN results of most client points. All existing studies first compute the kNN of client points and then perform the MaxBRkNN search. However, computing kNN for all clients is extremely time consuming especially on large datasets. Observing this, we develop an approach which computes kNN for only promising clients by utilising a two-level grid index (ADPGI) to reduce the cost substantially. Empirical studies on both real and synthetic datasets show that our proposed exact algorithm is 3 to 5 times faster than two state-of-the-art MaxBRkNN algorithms.

In this paper, we study the problem of approximate containment similarity search. Given two records Q and X, the containment similarity between Q and X with respect to Q is |Q intersect X|/ |Q|. Given a query record Q and a set of records S, the containment similarity search finds a set of records from S whose containment similarity regarding Q are not less than the given threshold. This problem has many important applications in commercial and scientific fields such as record matching and domain search. Existing solution relies on the asymmetric LSH method by transforming the containment similarity to well-studied Jaccard similarity. In this paper, we use a different framework by transforming the containment similarity to set intersection. We propose a novel augmented KMV sketch technique, namely GB-KMV, which is data-dependent and can achieve a good trade-off between the sketch size and the accuracy. We provide a set of theoretical analysis to underpin the proposed augmented KMV sketch technique, and show that it outperforms the state-of-the-art technique LSH-E in terms of estimation accuracy under practical assumption. Our comprehensive experiments on real-life datasets verify that GB-KMV is superior to LSH-E in terms of the space-accuracy trade-off, time-accuracy trade-off, and the sketch construction time. For instance, with similar estimation accuracy (F-1 score), GB-KMV is over 100 times faster than LSH-E on some real-life dataset.

Community search is important in graph analysis and can be used in many real applications. In the literature, various community models have been proposed. However, most of them cannot well identify the overlaps between communities which is an essential feature of real graphs. To address this issue, k-clique percolation community model was proposed and has been proven effective in many applications. Motivated by this, in this paper, we adopt the k-clique percolation community model and study the densest clique percolation community search problem which aims to find the k-clique percolation community with the maximum k value that contains a given set of query nodes. We adopt an index based approach to solve this problem. Based on the observation that a k-clique percolation community is a union of maximal cliques, we devise a novel compact index, DCPC-Index, to preserve the maximal cliques and their connectivity information of the input graph. With DCPC-Index, we can answer the densest clique percolation community query efficiently. Besides, we also propose an index construction algorithm based on the definition of DCPC-Index and further improve the algorithm in terms of efficiency and memory consumption. We conduct extensive performance studies on real graphs and the experimental results demonstrate the efficiency of our index-based query processing algorithm and index construction algorithm.

Graph decomposition has been widely used to analyze real-life networks from different perspectives. Recent studies focus on the hierarchical graph decomposition methods to handle big graphs in many real-life applications such as community detection, network analysis, network visualization, internet topology analysis and protein function prediction. In this tutorial, we first highlight the importance of hierarchical graph decomposition in a variety of applications and the unique challenges that need to be addressed. Subsequently, we provide an overview of the existing models and the computation algorithms under different computing environments. Then we discuss the integration of existing models with other approaches to better capture the cohesiveness of subgraphs in real-life scenarios. Finally, we discuss the future research directions in this important and growing research area.

Maximal clique enumeration is a fundamental problem in graph database. In this paper, we investigate this problem in the context of spatial database. Given a set P of spatial objects in a 2-dimensional space (e.g., geo-locations of users or point of interests) and a distance threshold r, we can come up with a spatial neighbourhood graph Prby connecting every pair of objects (vertices) in P within distance r. Given a clique S of Pr, namely a spatial clique, it is immediate that any pairwise distance among objects in S is bounded by r. As the maximal pairwise distance has been widely used to capture the spatial cohesiveness of a group of objects, the maximal spatial clique enumeration technique can identify groups of spatially close objects in a variety of location-based-service (LBS) applications. In addition, we show that the maximal spatial clique enumeration can also be used to identify maximal clique pattern instances in the co-location pattern mining applications. Given the existing techniques for maximal clique enumeration, which can be immediately applied on the spatial neighbourhood graph Pr, two questions naturally arise for the enumeration of maximal spatial cliques: (1) the maximal clique enumeration on general graph is NP hard, can we have a polynomial time solution on the spatial neighbourhood graph? and (2) can we exploit the geometric property of the spatial clique to speed up the computation? In this paper, we give a negative answer to the first question by an example where the number of maximal spatial cliques is exponential to the number of the objects. While the answer to the second question is rather positive: we indeed develop two pruning techniques based on geometric properties of the maximal spatial clique to significantly enhance the computing efficiency. Extensive experiments on real-life geolocation data demonstrate the superior performance of proposed methods compared with two baseline algorithms.

Electroencephalography (EEG) signals reflect and measure activities in certain brain areas. Its zero clinical risk and easy-to-use features make it a good choice of providing insights into the cognitive process. However, effective analysis of time-varying EEG signals remains challenging. First, EEG signal processing and feature engineering are time-consuming and highly rely on expert knowledge, and most existing studies focus on domain-specific classification algorithms, which may not apply to other domains. Second, EEG signals usually have low signal-to-noise ratios and are more chaotic than other sensor signals. In this regard, we propose a generic EEG-based cognitive activity recognition framework that can adaptively support a wide range of cognitive applications to address the above issues. The framework uses a reinforced selective attention model to choose the characteristic information among raw EEG signals automatically. It employs a convolutional mapping operation to dynamically transform the selected information into a feature space to uncover the implicit spatial dependency of EEG sample distribution. We demonstrate the effectiveness of the framework under three representative scenarios: intention recognition with motor imagery EEG, person identification, and neurological diagnosis, and further evaluate it on three widely used public datasets. The experimental results show our framework outperforms multiple state-of-the-art baselines and achieves competitive accuracy on all the datasets while achieving low latency and high resilience in handling complex EEG signals across various domains. The results confirm the suitability of the proposed generic approach for a range of problems in the realm of brain-computer Interface applications.

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.

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.

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.

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.

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.

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.

Community search is important in graph analysis and can be used in many real applications. In the literature, various community models have been proposed. However, most of them cannot well identify the overlaps between communities which is an essential feature of real graphs. To address this issue, the k-clique percolation community model was proposed and has been proven effective in many applications. Motivated by this, in this paper, we adopt the k-clique percolation community model and study the densest clique percolation community search problem which aims to find the k-clique percolation community with the maximum k value that contains a given set of query nodes. We adopt an index-based approach to solve this problem. Based on the observation that a k-clique percolation community is a union of maximal cliques, we devise a novel compact index, DCPC-Index, to preserve the maximal cliques and their connectivity information of the input graph. With DCPC-Index, we can answerthe densest clique percolation community query efficiently. Besides, we also propose an index construction algorithm based on the definition of DCPC-Index and further improve the algorithm in terms of efficiency and memory consumption. We conduct extensive performance studies on real graphs and the experimental results demonstrate the efficiency of our index-based query processing algorithm and index construction algorithm.

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.

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.

This paper studies the problem of efficiently computing a maximum independent set from a large graph, a fundamental problem in graph analysis. Due to the hardness results of computing an exact maximum independent set or an approximate maximum independent set with accuracy guarantee, the existing algorithms resort to heuristic techniques for approximately computing a maximum independent set with good performance in practice but no accuracy guarantee theoretically. Observing that the existing techniques have various limits, in this paper, we aim to develop efficient algorithms (with linear or near-linear time complexity) that can generate a high-quality (large-size) independent set from a graph in practice. In particular, firstly we develop a Reducing-Peeling framework which iteratively reduces the graph size by applying reduction rules on vertices with very low degrees (Reducing) and temporarily removing the vertex with the highest degree (Peeling) if the reduction rules cannot be applied. Secondly, based on our framework we design two baseline algorithms, BDOne and BDTwo, by utilizing the existing reduction rules for handling degree-one and degree-two vertices, respectively. Both algorithms can generate higher-quality (larger-size) independent sets than the existing algorithms. Thirdly, we propose a linear-time algorithm, LinearTime, and a near-linear time algorithm, NearLinear, by designing new reduction rules and developing techniques for efficiently and incrementally applying reduction rules. In practice, LinearTime takes similar time and space to BDOne but computes a higher quality independent set, similar in size to that of an independent set generated by BDTwo. Moreover, in practice NearLinear has a good chance to generate a maximum independent set and it often generates near-maximum independent sets. Fourthly, we extend our techniques to accelerate the existing iterated local search algorithms. Extensive empirical studies show that all our algorithms output much larger independent sets than the existing linear-time algorithms while having a similar running time, as well as achieve significant speedup against the existing iterated local search algorithms.

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.

We study the problem of structural graph clustering, a fundamental problem in managing and analyzing graph data. Given an undirected unweighted graph, structural graph clustering is to assign vertices 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. In this paper, we develop a new two-step paradigm for scalable structural graph clustering based on our three observations. Then, we present a pSCAN approach, within the paradigm, aiming to reduce the number of structural similarity computations, and propose optimization techniques to speed up checking whether two vertices are structure-similar. pSCAN outputs exactly the same clusters as the existing approaches SCAN and SCAN++, and we prove that pSCAN is worst-case optimal. Moreover, we propose efficient techniques for updating the clusters when the input graph dynamically changes, and we also extend our techniques to other similarity measures, e.g., Jaccard similarity. Performance studies on large real and synthetic graphs demonstrate the efficiency of our new approach and our dynamic cluster maintenance techniques. 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.

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 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.

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.

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.

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.

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.

Presents the introductory editorial for this issue of the publication.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Uncertainty is inherent in many important applications, such as location-based services (LBS), sensor monitoring and radio-frequency identification (RFID). Recently, considerable research efforts have been put into the field of uncertainty-aware spatial query processing. In this paper, we study the problem of finding top k most influential facilities over a set of uncertain objects, which is an important 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. Comprehensive experiments on real datasets demonstrate the effectiveness and efficiency of our techniques.

The range searching problem is fundamental in a wide spectrum of applications such as radio frequency identification (RFID) networks, location based services (LBS), and global position system (GPS). As the uncertainty is inherent in those applications, it is highly demanded to address the uncertainty in the range search since the traditional techniques cannot be applied due to the inherence difference between the uncertain data and traditional data. In the paper, we propose a novel indexing structure, named U-Quadtree, to organize the uncertain objects in a multi-dimensional space such that the range searching can be answered efficiently by applying filtering techniques. Particularly, based on some insights of the range search on uncertain data, we propose a cost model which carefully considers various factors that may impact the performance of the range searching. Then an effective and efficient index construction algorithm is proposed to build the optimal U-Quadtree regarding the cost model. Comprehensive experiments demonstrate that our technique outperforms the existing works for range searching on multi-dimensional uncertain objects.

Top-k pairs queries have received significant attention by the research community. k-closest pairs queries, k-furthest pairs queries and their variants are among the most well studied special cases of the top-k pairs queries. In this paper, we present the first approach to answer a broad class of top-k pairs queries over sliding windows. Our framework handles multiple top-k pairs 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. Although the number of possible pairs in the sliding window is quadratic to the number of objects N in the sliding window, we efficiently answer the top-k pairs query by maintaining a small subset of pairs called K-sky band which is expected to consist of O(K log(N/K)) pairs. For all the queries that use the same scoring function, we need to maintain only one K-sky band. We present efficient techniques for the K-sky band 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. We experimentally verify this by comparing our approach with a specially designed supreme algorithm that assumes the existence of an oracle and meets the lower bound cost.

SimFusion has become a captivating measure of similarity between objects in a web graph. It is iteratively distilled from the notion that "the similarity between two objects is reinforced by the similarity of their related objects". The existing SimFusion model usually exploits the Unified Relationship Matrix (URM) to represent latent relationships among heterogeneous data, and adopts an iterative paradigm for SimFusion computation. However, due to the row normalization of URM, the traditional SimFusion model may produce the trivial solution; worse still, the iterative computation of SimFusion may not ensure the global convergence of the solution. This paper studies the revision of this model, providing a full treatment from complexity to algorithms. (1) We propose SimFusion+ based on a notion of the Unified Adjacency Matrix (UAM), a modification of the URM, to prevent the trivial solution and the divergence issue of SimFusion. (2) We show that for any vertex-pair, SimFusion+ can be performed in O(1) time and O(n) space with an O(km)-time precomputation done only once, as opposed to the O(kn3) time and O(n2) space of its traditional counterpart, where n, m, and k denote the number of vertices, edges, and iterations respectively. (3) We also devise an incremental algorithm for further improving the computation of SimFusion+ when networks are dynamically updated, with performance guarantees for similarity estimation. We experimentally verify that these algorithms scale well, and the revised notion of SimFusion is able to converge to a non-trivial solution, and allows us to identify more sensible structure information in large real-world networks.

Given a query graph $q$ and a data graph G, computing all occurrences of q in G, namely exact all-matching, is fundamental in graph data analysis with a wide spectrum of real applications. It is challenging since even finding one occurrence of q in G (subgraph isomorphism test) is NP-Complete. Consider that in many real applications, exploratory queries from users are often inaccurate to express their real demands. In this paper, we study the problem of efficiently computing all approximate occurrences of q in G. Particularly, we study the problem of efficiently retrieving all matches of q in G with the number of possible missing edges bounded by a given threshold θ, namely similarity all-matching. The problem of similarity all-matching is harder than the problem of exact all-matching since it covers the problem of exact all-matching as a special case with θ = 0.

In many applications, including location-based services, queries may not be precise. In this paper, we study the problem of efficiently computing range aggregates in a multidimensional space when the query location is uncertain. Specifically, for a query point Q whose location is uncertain and a set S of points in a multidimensional space, we want to calculate the aggregate (e.g., count, average and sum) over the subset S' of S such that for each p ϵ S', Q has at least probability θ within the distance γ to p. We propose novel, efficient techniques to solve the problem following the filtering-and-verification paradigm. In particular, two novel filtering techniques are proposed to effectively and efficiently remove data points from verification. Our comprehensive experiments based on both real and synthetic data demonstrate the efficiency and scalability of our techniques.

In many applications involving multiple criteria optimal decision making, users may often want to make a personal trade-off among all optimal solutions for selecting one object that fits best their personal needs. As a key feature, the skyline in a multidimensional space provides the minimum set of candidates for such purposes by removing all points not preferred by any (monotonic) utility/scoring functions; that is, the skyline removes all objects not preferred by any user no matter how their preferences vary. Driven by many recent applications with uncertain data, the probabilistic skyline model is proposed to retrieve uncertain objects based on skyline probabilities. Nevertheless, skyline probabilities cannot capture the preferences of monotonic utility functions. Motivated by this, in this article we propose a novel skyline operator, namely stochastic skylines. In the light of the expected utility principle, stochastic skylines guarantee to provide the minimum set of candidates to optimal solutions over a family of utility functions. We first propose the lskyline operator based on the lower orthant orders . lskyline guarantees to provide the minimum set of candidates to the optimal solutions for the family of monotonic multiplicative utility functions. While lskyline works very effectively for the family of multiplicative functions, it may miss optimal solutions for other utility /scoring functions (e.g., linear functions). To resolve this, we also propose a general stochastic skyline operator, gskyline , based on the usual orders . gskyline provides the minimum candidate set to the optimal solutions for all monotonic functions. For the first time regarding the existing literature, we investigate the complexities of determining a stochastic order between two uncertain objects whose probability distributions are described discretely . We firstly show that determining the lower orthant order is NP-complete with respect to the dimensionality; consequently the problem of computing lskyline is NP-complete. We also show an interesting result as follows. While the usual order involves more complicated geometric forms than the lower orthant order, the usual order may be determined in polynomial time regarding all the inputs, including the dimensionality; this implies that gskyline can be computed in polynomial time. A general framework is developed for efficiently and effectively retrieving lskyline and gskyline from a set of uncertain objects, respectively, together with efficient and effective filtering techniques. Novel and efficient verification algorithms are developed to efficiently compute lskyline over multidimensional uncertain data, which run in polynomial time if the dimensionality is fixed, and to efficiently compute gskyline in polynomial time regarding all inputs. We also show, by theoretical analysis and experiments, that the sizes of lskyline and gskyline are both quite similar to that of conventional skyline over certain data. Comprehensive experiments demonstrate that our techniques are efficient and scalable regarding both CPU and IO costs.

Top-k pairs queries have many real applications. k closest pairs queries, k furthest pairs queries and their bichromatic variants are some of the examples of the top-k pairs queries that rank the pairs on distance functions. While these queries have received significant research attention, there does not exist a unified approach that can efficiently answer all these queries. Moreover, there is no existing work that supports top-k pairs queries based on generic scoring functions. In this paper, we present a unified approach that supports a broad class of top-k pairs queries including the queries mentioned above. Our proposed approach allows the users to define a local scoring function for each attribute involved in the query and a global scoring function that computes the final score of each pair by combining its scores on different attributes. We propose efficient internal and external memory algorithms and our theoretical analysis shows that the expected performance of the algorithms is optimal when two or less attributes are involved. Our approach does not require any pre-built indexes, is easy to implement and has low memory requirement. We conduct extensive experiments to demonstrate the efficiency of our proposed approach.

Given a set of objects and a query q, a point p is called the reverse k nearest neighbor (RkNN) of q if q is one of the k closest objects of p. In this paper, we introduce the concept of influence zone which is the area such that every point inside this area is the RkNN of q and every point outside this area is not the RkNN. The influence zone has several applications in location based services, marketing and decision support systems. It can also be used to efficiently process RkNN queries. First, we present efficient algorithm to compute the influence zone. Then, based on the influence zone, we present efficient algorithms to process RkNN queries that significantly outperform existing best known techniques for both the snapshot and continuous RkNN queries. We also present a detailed theoretical analysis to analyse the area of the influence zone and IO costs of our RkNN processing algorithms. Our experiments demonstrate the accuracy of our theoretical analysis.

In many applications involving the multiple criteria optimal decision making, users may often want to make a personal trade-off among all optimal solutions. As a key feature, the skyline in a multi-dimensional space provides the minimum set of candidates for such purposes by removing all points not preferred by any (monotonic) utility/scoring functions; that is, the skyline removes all objects not preferred by any user no mater how their preferences vary. Driven by many applications with uncertain data, the probabilistic skyline model is proposed to retrieve uncertain objects based on skyline probabilities. Nevertheless, skyline probabilities cannot capture the preferences of monotonic utility functions. Motivated by this, in this paper we propose a novel skyline operator, namely stochastic skyline. In the light of the expected utility principle, stochastic skyline guarantees to provide the minimum set of candidates for the optimal solutions over all possible monotonic multiplicative utility functions. In contrast to the conventional skyline or the probabilistic skyline computation, we show that the problem of stochastic skyline is NP-complete with respect to the dimensionality. Novel and efficient algorithms are developed to efficiently compute stochastic skyline over multi-dimensional uncertain data, which run in polynomial time if the dimensionality is fixed. We also show, by theoretical analysis and experiments, that the size of stochastic skyline is quite similar to that of conventional skyline over certain data. Comprehensive experiments demonstrate that our techniques are efficient and scalable regarding both CPU and IO costs.

Given a positive value r, a distance-based range query returns the objects that lie within the distance r of the query location. In this paper, we focus on the distance-based range queries that continuously change their locations in a euclidean space. We present an efficient and effective monitoring technique based on the concept of a safe zone. The safe zone of a query is the area with a property that while the query remains inside it, the results of the query remain unchanged. Hence, the query does not need to be reevaluated unless it leaves the safe zone. Our contributions are as follows: 1) We propose a technique based on powerful pruning rules and a unique access order which efficiently computes the safe zone and minimizes the I/O cost. 2) We theoretically determine and experimentally verify the expected distance a query moves before leaving the safe zone and, for majority of queries, the expected number of guard objects. 3) Our experiments demonstrate that the proposed approach is close to optimal and is an order of magnitude faster than a naïve algorithm. 4) We also extend our technique to monitor the queries in a road network. Our algorithm is up to two order of magnitude faster than a naïve algorithm.

Given a positive value r, a circular range query returns the objects that lie within the distance r of the query location. In this paper, we study the circular range queries that continuously change their locations. We present an efficient and effective technique to monitor such moving range queries by utilising the concept of a safe zone. The safe zone of a query is the area with a property that while the query remains inside it, the results of the query remain unchanged. Hence, the query does not need to be re-evaluated unless it leaves the safe zone. The shape of the safe zone is defined by the so-called guard objects. The cost of checking whether a query lies in the safe zone takes k distance computations, where k is the number of the guard objects. Our contributions are as follows. 1) We propose a technique based on powerful pruning rules and a unique access order which efficiently computes the safe zone and minimizes the I/O cost. 2) To show the effectiveness of the safe zone, we theoretically evaluate the probability that a query leaves the safe zone within one time unit and the expected distance a query moves before it leaves the safe zone. Additionally, for the queries that have diameter of the safe zone less than its expected value multiplied by a constant, we also give an upper bound on the expected number of guard objects. This upper bound turns out to be a constant, that is, it does not depend either on the radius r of the query or the density of the objects. The theoretical analysis is verified by extensive experiments. 3) Our thorough experimental study demonstrates that our proposed approach is close to optimal and is an order of magnitude faster than a nai¿ve algorithm.

K Nearest Neighbor search has many applications including data mining, multi-media, image processing, and monitoring moving objects. In this paper, we study the problem of KNN over multi-valued objects. We aim to provide effective and efficient techniques to identify KNN sensitive to relative distributions of objects.We propose to use quantiles to summarize relative-distribution-sensitive K nearest neighbors. Given a query Q and a quantile ¿ ¿ (0, 1), we firstly study the problem of efficiently computing K nearest objects based on a ¿-quantile distance e.g. median distance from each object to Q. The second problem is to retrieve the K nearest objects to Q based on overall distances in the ¿best population¿ with a given size specified by ¿-quantile for each object. While the first problem can be solved in polynomial time, we show that the 2nd problem is NP-hard. A set of efficient, novel algorithms have been proposed to give an exact solution for the first problem and an approximate solution for the second problem with the approximation ratio. Extensive experiment demonstrates that our techniques are very efficient and effective.

Uncertain data are inherent in many applications such as environmental surveillance and quantitative economics research. As an important problem in many applications, KNN query has been extensively investigated in the literature. In this paper, we study the problem of processing rank based KNN query against uncertain data. Besides applying the expected rank semantic to compute KNN, we also introduce the median rank which is less sensitive to the outliers. We show both ranking methods satisfy nice top-k properties such as exact-k, containment, unique ranking, value invariance, stability and fairfulness. For given query q, IO and CPU efficient algorithms are proposed in the paper to compute KNN based on expected (median) ranks of the uncertain objects. To tackle the correlations of the uncertain objects and high IO cost caused by large number of instances of the uncertain objects, randomized algorithms are proposed to approximately compute KNN with theoretical guarantees. Comprehensive experiments are conducted on both real and synthetic data to demonstrate the efficiency of our techniques.

Uncertain data are inherent in various important applications and reverse nearest neighbor (RNN) query is an important query type for many applications. While many different types of queries have been studied on uncertain data, there is no previous work on answering RNN queries on uncertain data. In this paper, we formalize probabilistic reverse nearest neighbor query that is to retrieve the objects from the uncertain data that have higher probability than a given threshold to be the RNN of an uncertain query object. We develop an efficient algorithm based on various novel pruning approaches that solves the probabilistic RNN queries on multidimensional uncertain data. The experimental results demonstrate that our algorithm is even more efficient than a sampling-based approximate algorithm for most of the cases and is highly scalable.

With the rapid development of various optical, infrared, and radar sensors and GPS techniques, there are a huge amount of multidimensional uncertain data collected and accumulated everyday. Recently, considerable research efforts have been made in the field of indexing, analyzing, and mining uncertain data. As shown in a recent book on uncertain data, in order to efficiently manage and mine uncertain data, effective indexing techniques are highly desirable. Based on the observation that the existing index structures for multidimensional data are sensitive to the size or shape of uncertain regions of uncertain objects and the queries, in this paper, we introduce a novel R-Tree-based inverted index structure, named UI-Tree, to efficiently support various queries including range queries, similarity joins, and their size estimation, as well as top-k range query, over multidimensional uncertain objects against continuous or discrete cases. Comprehensive experiments are conducted on both real data and synthetic data to demonstrate the efficiency of our techniques.

Uncertain data are inherent in many applications such as environmental surveillance and quantitative economics research. Considerable research efforts have been put into the field of analysing uncertain data. In this paper, we study the problem of processing the uncertain location based range aggregate in a multi-dimensional space. We first formally introduce the problem, then propose a general filtering-and-verification framework to solve the problem. Two filtering techniques, named STF and PCR respectively, are proposed to significantly reduce the verification cost.

Skyline computation has many applications including multi-criteria decision making. In this paper, we study the problem of efficient processing of continuous skyline queries over sliding windows on uncertain data elements regarding given probability thresholds. We first characterize what kind of elements we need to keep in our query computation. Then we show the size of dynamically maintained candidate set and the size of skyline. We develop novel, efficient techniques to process a continuous, probabilistic skyline query. Finally, we extend our techniques to the applications where multiple probability thresholds are given or we want to retrieve "top-k" skyline data objects. Our extensive experiments demonstrate that the proposed techniques are very efficient and handle a high-speed data stream in real time.

In this paper, we study the problem of continuous monitoring of reverse k nearest neighbor queries. Existing continuous reverse nearest neighbor monitoring techniques are sensitive towards objects and queries movement. For example, the results of a query are to be recomputed whenever the query changes its location. We present a framework for continuous reverse k nearest neighbor queries by assigning each object and query with a rectangular safe region such that the expensive recomputation is not required as long as the query and objects remain in their respective safe regions. This significantly improves the computation cost. As a by-product, our framework also reduces the communication cost in client-server architectures because an object does not report its location to the server unless it leaves its safe region or the server sends a location update request. We also conduct a rigid cost analysis to guide an effective selection of such rectangular safe regions. The extensive experiments demonstrate that our techniques outperform the existing techniques by an order of magnitude in terms of computation cost and communication cost.

In this paper, we propose a novel type of probabilistic threshold top-k queries on uncertain data, and give an exact algorithm. More details can be found in [4].

Uncertain data is inherent in a few important applications such as environmental surveillance and mobile object tracking. Top-k queries (also known as ranking queries) are often natural and useful in analyzing uncertain data in those applications. In this paper, we study the problem of answering probabilistic threshold top-k queries on uncertain data, which computes uncertain records taking a probability of at least p to be in the top-k list where p is a user specified probability threshold. We present an efficient exact algorithm, a fast sampling algorithm, and a Poisson approximation based algorithm. An empirical study using real and synthetic data sets verifies the effectiveness of probabilistic threshold top-k queries and the efficiency of our methods.

Uncertain data are inherent in many important applications. Recently, considerable research efforts have been put into the field of managing uncertain data. In this paper, we summarize existing techniques to query and model uncertain data and systems that effectively manage uncertain data, mainly from a probabilistic point of view.