Query optimization is essential for efficient SQL query execution in DBMS, and remains attractive over time due to the growth of data volumes and advances in hardware. Existing traditional optimizers struggle with the cumbersome hand-tuning required for complex workloads, and the learning-based methods face limitations in ensuring generalization. With the great success of Large Language Model (LLM) across diverse downstream tasks, this paper explores how LLMs can be incorporated to enhance the generalization of learned optimizers. Though promising, such an incorporation still presents challenges, mainly including high model inference latency, and the substantial fine-tuning cost and suboptimal performance due to inherent discrepancy between the token sequences in LLM and structured SQL execution plans with rich numerical features. In this paper, we focus on recurring queries in offline optimization to alleviate the issue of high inference latency, and propose \textbf{LLM4Hint} that leverages moderate-sized backbone LLMs to recommend query optimization hints. LLM4Hint achieves the goals through: (i) integrating a lightweight model to produce a soft prompt, which captures the data distribution in DBMS and the SQL predicates to provide sufficient optimization features while simultaneously reducing the context length fed to the LLM, (ii) devising a query rewriting strategy using a larger commercial LLM, so as to simplify SQL semantics for the backbone LLM and reduce fine-tuning costs, and (iii) introducing an explicit matching prompt to facilitate alignment between the LLM and the lightweight model, which can accelerate convergence of the combined model. Experiments show that LLM4Hint, by leveraging the LLM's stronger capability to understand the query statement, can outperform the state-of-the-art learned optimizers in terms of both effectiveness and generalization.

Learned plan-selection optimizers combine the conventional and learned approaches by generating diverse candidate plans through multiple optimizers and selecting the best via value models. However, these eagerly-generated plans incur high optimization overhead, as they require multiple invocations of the native optimizer. In this article, we propose MoEPlan, which learns a routing policy to select top- \( k \) experts (different optimizers) via query embedding and learnable parameters, avoiding pre-generation of candidate plans. Our approach integrates two optimization strategies: (1) a virtual ideal expert to guide the best plan selection through learned plan similarities, and (2) a query-irrelevant expert sampling strategy to balance the training cost and effectiveness of selected plans in the first round of expert selection. Furthermore, we design a two-phase training process: the first phase pre-trains the model with complete expert feedback, while the second phase filters the full expert pool to yield a promising subset and refines the selection to pinpoint the optimal expert. Experimental studies show that MoEPlan, with only two plans generated, takes less inference time, while still producing more efficient plans than other learned plan-selection optimizers.

Denoising Diffusion Probabilistic Models (DDPMs) have recently demonstrated exceptional performance in generating high-quality data. In this work, we propose CommunityDF, a novel framework that applies DDPMs to the community search problem, which involves identifying subgraphs containing nodes closely related to a given query node. However, three key challenges arise in this context: (I) learning effective node representations from limited examples, (II) discretizing continuous node representations into community members, and (III) reducing the number of diffusion steps without sacrificing performance. To tackle these, CommunityDF introduces several innovations. First, we focus on subgraphs around the query node to reduce interference from unrelated nodes, improve scalability. We then employ a contrastive learning approach, treating node states at different diffusion steps as positive examples and designing various negative sampling strategies to learn high-quality node representations from limited examples. Second, we propose a dynamic thresholding mechanism that effectively converts continuous representations into community members. Finally, we reduce the number of diffusion steps by leveraging the rough communities to initialize the process with rough community structures, which accelerates convergence while maintaining high accuracy. Extensive experiments on seven real-world datasets demonstrate that CommunityDF outperforms existing methods by 16%-47%, establishing it as a state-of-the-art solution for community search. The source code is available at https://github.com/JiazunChen/CommunityDF.

The detection of malicious social bots has become a crucial task, as bots can be easily deployed and manipulated to spread disinformation, promote conspiracy messages, and more. Most existing approaches utilize graph neural networks (GNNs) to capture both user profile and structural features, achieving promising progress. However, they still face limitations including the expensive training on large underlying graph, the performance degradation when “similar neighborhood patterns” assumption preferred by GNNs is not satisfied, and the distinguishable features of bots in a highly adversarial context. Motivated by these limitations, this paper proposes a method named BSG4Bot with an intuition that GNNs training on Biased SubGraphs can improve both performance and time/space efficiency in bot detection. Specifically, BSG4Bot first pre-trains a classifier on node features efficiently to define the node similarities, and constructs biased subgraphs by combining the similarities computed by the pre-trained classifier and the node importances computed by Personalized PageRank (PPR scores). BSG4Bot then introduces a heterogeneous GNN over the constructed subgraphs to detect bots effectively and efficiently. The relatively stable features, including the content category and temporal activity features, are explored and incorporated into BSG4Bot after preliminary verification on sample data. The extensive experimental studies show that BSG4Bot outperforms the state-of-the-art bot detection methods, while only needing nearly 1/4 training time.

Table union search (TUS) represents a fundamental operation in data lakes to find tables unionable to the given one. Recent approaches to TUS mainly learn column representations for searching by introducing Pre-trained Language Models (PLMs), especially on columns with linguistic data. However, a significant amount of non-linguistic data, notably represented by domain-specific strings and numerical data in the data lake, are still under-explored in the existing methods. To address this issue, we propose LIFTus, an adaptive multi-aspect column representation for table unionable search, where aspect refers to a concept more flexible than data types, so that a single column can exhibit multiple aspects simultaneously. LIFTus aims at combining different aspects of a column (including both linguistic and non-linguistic aspects) to promote the effectiveness and generalization of TUS in a self-supervised manner. Specifically, besides employing PLMs to extract the linguistic aspects from an individual column, LIFTus trains a pattern encoder to learn possible character-level sequential patterns for the column, and builds a number encoder to capture numerical aspects of the column, including the distribution and magnitude features. LIFTus further utilizes a hierarchical cross-attention aided by aspect-relevant statistics to combine these aspects adaptively in producing the final column representations, which are indexed by vector retrieval techniques to achieve efficient search. Extensive experimental results demonstrate that LIFTus has outperformed the current state-of-the-art methods in terms of effectiveness, and achieved much better generalization capability to support unseen data.

Most large enterprises build predefined data pipelines and execute them periodically to process operational data using SQL queries for various tasks. A key issue in minimizing the overall makespan of these pipelines is the efficient scheduling of concurrent queries within the pipelines. Existing tools mainly rely on simple heuristic rules due to the difficulty of expressing the complex features and mutual influences of queries. The latest reinforcement learning (RL) based methods have the potential to capture these patterns from feedback, but it is non-trivial to apply them directly due to the large scheduling space, high sampling cost, and poor sample utilization. Motivated by these challenges, we propose BQSched, a non-intrusive Scheduler for Batch concurrent Queries via reinforcement learning. Specifically, BQSched designs an attention-based state representation to capture the complex query patterns, and proposes IQ-PPO, an auxiliary task-enhanced proximal policy optimization (PPO) algorithm, to fully exploit the rich signals of Individual Query completion in logs. Based on the RL framework above, BQSched further introduces three optimization strategies, including adaptive masking to prune the action space, scheduling gain-based query clustering to deal with large query sets, and an incremental simulator to reduce sampling cost. To our knowledge, BQSched is the first non-intrusive batch query scheduler via RL. Extensive experiments show that BQSched can significantly improve the efficiency and stability of batch query scheduling, while also achieving remarkable scalability and adaptability in both data and queries. For example, across all DBMSs and scales tested, BQSched reduces the overall makespan of batch queries on TPC-DS benchmark by an average of 34% and 13%, compared with the commonly used heuristic strategy and the adapted RL-based scheduler, respectively. The source code of BQSched is available at https://github.com/chxu2000/BQSched.

Accurate cardinality estimation of substring queries, which are commonly expressed using the SQL LIKE predicate, is crucial for query optimization in database systems. While both rule-based methods and machine learning-based methods have been developed to optimize various aspects of cardinality estimation, their absence of error bounds may result in substantial estimation errors, leading to suboptimal execution plans. In this paper, we propose SSCard, a novel S ub S tring Card inality estimator that leverages a space-efficient FM-Index into flexible database applications. SSCard first extends the FM-Index to support multiple strings naturally, and then organizes the FM-index using a pruned suffix tree. The suffix tree structure enables precise cardinality estimation for short patterns and achieves high compression via a pushup operation, especially on a large alphabet with skewed character distributions. Furthermore, SSCard incorporates a spline interpolation method with an error bound to balance space usage and estimation accuracy. Additional innovations include a bidirectional estimation algorithm and incremental update strategies. Extensive experimental results in five real-life datasets show that SSCard outperforms both traditional methods and recent learning-based methods, which achieves an average reduction of 20% in the average q-error, 80% in the maximum q-error, and 50% in the construction time, compared with second-best approaches.

Graph matching is a critical task with diverse real-world applications. Present cutting-edge methodologies incorporate graph neural architectures combined with incremental anchor refinement, calculating the matching similarity directly via node embeddings. The graph neural architectures provide enhanced encoding of both structural and attribute information, yielding more accurate results, and incremental anchor refinement contributes to the overall low complexity of these methods. However, this method of direct similarity calculation expects all neighboring nodes of one anchor to bear a resemblance in their embeddings to all neighbors of its counterpart. This requirement might obscure the distinctiveness of nodes within a localized region. Moreover, the integration of incorrectly identified anchor pairs during the incremental refinement process can significantly degrade subsequent matching performance. To tackle the challenges, we introduce a novel method, Deep Neighbor Matching (DeepNM), designed to explicitly measure the similarity between the neighborhoods of nodes, thereby functioning as a graph matching training loss. Further, we demonstrate that this similarity measurement, based on common neighbor statistics, is more resilient to inaccurately identified anchor pairs. Our comprehensive experiments on both synthetic and real-world datasets offer empirical evidence that DeepNM is compatible with the incremental graph matching paradigm and has outstanding performance. Graph matching is a critical task with diverse real-world applications. Current cutting-edge methodologies incorporate GNN (Graph Neural Network) combined with incremental anchor refinement, calculating the matching similarity directly via node embeddings. However, the direct similarity computation based on aggregated embeddings from GNN may obscure the distinctiveness of nodes within a localized region. In addition, the possible wrongly added anchor pairs in the iterations and the lack of capturing the relationships to anchors may further affect the performance. In order to tackle these challenges, this paper proposes a method named DeepNM, which attempts to find node matching based on their neighbors' similarities. Specifically, DeepNM introduces a Sinkhorn-based similarity on a node's neighborhood's embeddings, which serves as both a training loss and a matching metric tailored to the graph matching problem. Additionally, we demonstrate that the Sinkhorn-based similarity, which relies on common neighbor statistics, is highly resilient to inaccurately identified anchor pairs within the context of incremental graph matching. Our comprehensive experiments on synthetic and real-world datasets demonstrate that DeepNM, compatible with the incremental graph matching paradigm, excels particularly well at matching graphs where common neighbors provide good matches. Applying the DeepNM pipeline to real social networks results in a 6% improvement, and applying the Sinkhorn similarity on knowledge graphs results in an average improvement of 1.7% over the best baseline.

In recent years, there has been a growing interest in the application of deep reinforcement learning (DRL) techniques on query execution plan generation. Although current DRL-based query optimizers achieve competitive performance against traditional methods on specific query workloads, these methods encounter issues when generalizing to workloads unseen during training. Thus, we propose GLO to address the limitations and step towards generalized learned query optimization. First, rather than using ungeneralizable table-specific one-hot labels in almost all existing work, GLO relies on statistical information of the well-established underlying DBMS along with table patterns extracted via a clustering algorithm, enabling GLO to enhance generalization in different scenarios. Second, GLO improves the information capture of plans by integrating Transformer layers into the DRL value model, empowering the model's capability to handle diverse queries with deeper networks and more parameters in plan generation. In addition, GLO allows the injection of cost estimations from the DBMS as external knowledge for better generalization. Third, GLO recognizes and replaces disastrously poor plans by making comparisons between generated plans and those produced by the DBMS. We establish our experiments on composite workloads that combine various query sets including JOB, Extended JOB, TPC-DS, and Stack. The results demonstrate that GLO outperforms previous state-of-the-art learned optimizers, with a speed 1.4x faster than LOGER and 2.1x faster than Balsa on TPC-DS when TPC-DS queries are completely unknown during training. To the best of our knowledge, GLO is the first learned optimizer that directly generates plans while possessing the preliminary generalization ability across different query workloads.

Abstract Personalized review generation is significant for e-commerce applications, such as providing explainable recommendation and assisting the composition of reviews. With the success of pre-trained language models (PLMs), prompt learning-based approaches have been employed to handle this task. However, the existing approach neglects the historical user-item interactions as well as the diverse semantics of the reviews (including semantically relevant reviews and semantically irrelevant reviews). In this paper, we propose GRAPA, a graph-enhanced prompt learning approach for personalized review generation. Specifically, GRAPA extracts topic-level information for each review to address the semantic diversity of reviews. Moreover, GRAPA employs a heterogeneous graph neural network (GNN) to explore the collaborative information hidden in historical user-item interactions. User and item representations generated by the GNN module as well as their ID embeddings are used as prompts and fed into a PLM to guide the generation process. To alleviate the interference of semantically irrelevant reviews, GRAPA further proposes a contrastive learning module to distinguish them. Experimental results on public datasets show that GRAPA outperforms existing methods by up to 4.3% in BLEU-4 and 5.4% in ROUGE2-F.

Query optimization based on deep reinforcement learning (DRL) has become a hot research topic recently. Despite the achieved promising progress, DRL optimizers still face great challenges of robustly producing efficient plans, due to the vast search space for both join order and operator selection and the highly varying execution latency taken as the feedback signal. In this paper, we propose LOGER, a learned optimizer towards generating efficient and robust plans, aiming at producing both efficient join orders and operators. LOGER first utilizes Graph Transformer to capture relationships between tables and predicates. Then, the search space is reorganized, in which LOGER learns to restrict specific operators instead of directly selecting one for each join, while utilizing DBMS built-in optimizer to select physical operators under the restrictions. Such a strategy exploits expert knowledge to improve the robustness of plan generation while offering sufficient plan search flexibility. Furthermore, LOGER introduces ε -beam search, which keeps multiple search paths that preserve promising plans while performing guided exploration. Finally, LOGER introduces a loss function with reward weighting to further enhance performance robustness by reducing the fluctuation caused by poor operators, and log transformation to compress the range of rewards. We conduct experiments on Join Order Benchmark (JOB), TPC-DS and Stack Overflow, and demonstrate that LOGER can achieve a performance better than existing learned query optimizers, with a 2.07x speedup on JOB compared with PostgreSQL.

Example-based community search utilizes hidden patterns of given examples rather than explicit rules, reducing users' burden and enhancing flexibility. However, existing works face challenges such as low scalability, high training cost, and improper termination during the search. Aiming at tackling all these issues, this paper proposes a community search framework named CommunityAF with three well-designed components. The first is a GNN (graph neural network) component that combines community-aware structure features to incrementally learn node embeddings over a large graph for the other two components. The second is an autoregres-sive flow-based generation component designed for fast training and model stability. The third is a scoring component that evaluates the communities and provides scores for a stable termination. Moreover, to show that CommunityAF has the sufficient expressive power to cover the rules, we demonstrate that the scoring component with node features weighted by degree-related factors is able to mimic the existing structure-based community metrics. We introduce a square ranking loss to guide the training of the scoring component, and further devise a flexible termination strategy based on the inferred score change pattern over a sequence of candidate communities using beam search. We compare CommunityAF with four different categories of community search methods on six real-world datasets. The results illustrate that CommunityAF outperforms these community search methods, and achieves an average 15.3% improvement in effectiveness and 4x to 20x speedups on different datasets relative to the state-of-the-art generative method.

This paper concentrates on group anomalies in general large-scale networks. Existing algorithms on group anomalies mainly focus on homogeneous or bipartite networks, and thus are difficult to apply to heterogeneous networks directly. Moreover, these algorithms follow the non-overlapping hypothesis of groups implicitly, which is improper in many scenarios. For example, fraud users in Alibaba E-commerce platform may join more than one organization at the same time. In this paper, we introduce a novel algorithm calledAdaptive Label Propagation (ALP)to solve these problems. ALP is designed based on label propagation (LP) frameworks, for the reason that LP-based frameworks are simple in thought and easy to scale. ALP is able to find overlapping groups by label propagation with belonging coefficients, and can be applied to heterogeneous networks for its design of adaptive neighbor weighting. Assigning different weights to neighbors in label propagation is a challenging task. Inspired by the combinatorial multi-armed bandit mechanism, ALP views the neighbors of each node as arms to be selected, and iteratively updates their weights by evaluating their expected rewards in following iterations. Experiments are conducted on four real-world networks (including two bipartite ones and two heterogeneous ones). The results show that LP-based methods are effective for detecting group anomalies, and the comparison results with several state-of-the-art label propagation based community detection methods show the effectiveness of the proposed method.

Unsupervised graph embedding method generates node embeddings to preserve structural and content features in a graph without human labeling. However, most unsupervised graph representation learning methods suffer issues like poor scalability or limited utilization of content/structural relationships, especially on attributed graphs. In this paper, we propose SAGES, a graph sampling based autoencoder framework, which can alleviate these issues. Specifically, we propose a graph sampler considering both structural and content features, in which nodes with greater influence on each other have more chances to be sampled in the same subgraph. In addition, an unbiased Graph Autoencoder (GAE) with structure-level, content-level, and community-level reconstruction loss is built from the properly sampled subgraph each iteration. The time and space complexity analysis is carried out to show the scalability of SAGES. We conducted experiments on three medium-size attributed graphs and three large attributed graphs. Experimental results illustrate that SAGES achieves the competitive performance in unsupervised attributed graph learning on various downstream tasks including node classification, link prediction, and node clustering.

Community Search, which locates the desired sub-graph containing the query node, is a fundamental operation in network analysis. Most of the existing systems rely on pre-defined rules to find the community, while we argue that the target community is always specific for different purposes and the pre-defined rules may not be suitable. In this work, we demonstrate VICS-GNN, a Visual Interactive system for Community Search via graph Neural Network. VICS-GNN provides end users with a flexible, user-friendly front end to manage and explore the sub-graph around the query node, allows users labeling nodes to guide G NN models in learning community rules by combining content and structural features, and locates the community interactively and iteratively. In the demonstration, demo visitors will be invited to experience the VICS-GNN system using real-world data from Wikipedia and Sina Weibo to feel how convenient and intuitive it is to help with community search.

Graph Neural Networks (GNNs) have achieved great success in various graph mining tasks. However, drastic performance degradation is always observed when a GNN is stacked with many layers. As a result, most GNNs only have shallow architectures, which limits their expressive power and exploitation of deep neighborhoods. Most recent studies attribute the performance degradation of deep GNNs to the over-smoothing issue. In this paper, we disentangle the conventional graph convolution operation into two independent operations: Propagation (P) and Transformation (T). Following this, the depth of a GNN can be split into the propagation depth (Dp) and the transformation depth (Dt). Through extensive experiments, we find that the major cause for the performance degradation of deep GNNs is the model degradation issue caused by large Dt rather than the over-smoothing issue mainly caused by large Dp. Further, we present Adaptive Initial Residual (AIR), a plug-and-play module compatible with all kinds of GNN architectures, to alleviate the model degradation issue and the over-smoothing issue simultaneously. Experimental results on six real-world datasets demonstrate that GNNs equipped with AIR outperform most GNNs with shallow architectures owing to the benefits of both large DD_p$ and Dt, while the time costs associated with AIR can be ignored.

Impression regulation plays an important role in various online ranking systems, e.g. , e-commerce ranking systems always need to achieve local commercial demands on some pre-labeled target items like fresh item cultivation and fraudulent item counteracting while maximizing its global revenue. However, local impression regulation may cause “butterfly effects” on the global scale, e.g. , in e-commerce, the price preference fluctuation in initial conditions (overpriced or underpriced items) may create a significantly different outcome, thus affecting shopping experience and bringing economic losses to platforms. To prevent “butterfly effects”, some researchers define their regulation objectives with global constraints, by using contextual bandit at the page-level that requires all items on one page sharing the same regulation action, which fails to conduct impression regulation on individual items. To address this problem, in this article, we propose a personalized impression regulation method that can directly makes regulation decisions for each user-item pair. Specifically, we model the regulation problem as a C onstrained D ual-level B andit (CDB) problem, where the local regulation action and reward signals are at the item-level while the global effect constraint on the platform impression can be calculated at the page-level only. To handle the asynchronous signals, we first expand the page-level constraint to the item-level and then derive the policy updating as a second-order cone optimization problem. Our CDB approaches the optimal policy by iteratively solving the optimization problem. Experiments are performed on both offline and online datasets, and the results, theoretically and empirically, demonstrate CDB outperforms state-of-the-art algorithms.

Irregularly, asynchronously and sparsely sampled multivariate time series (IASS-MTS) are characterized by sparse non-uniform time intervals between successive observations and different sampling rates amongst series. Those properties pose substantial challenges to mainstream machine learning models for learning complicated relations within and across IASS-MTS. This is because that most of the models assume that the time series in question are even, complete (fixed-dimensional features) and synchronous. To address these challenges, we present a novel time-aware Dual-Attention and Memory-Augmented Network (DAMA-Net). The proposed model can leverage both time irregularity, multi-sampling rates and global temporal patterns information inherent in IASS-MTS so as to learn more effective representations for improving prediction performance. Comprehensive experiments on real datasets show that the DAMA-Net outperforms the state-of-the-art methods in multivariate time series classification task.

Node mapping between large graphs (or network alignment) plays a key preprocessing role in joint-graph data mining applications like social link prediction, cross-platform recommendation, etc. Most existing approaches attempt to perform alignment at the granularity of entire graphs, while handling the whole graphs may lower the scalability and the noisy nodes/edges in the graphs may impact the effectiveness. From the observation that potential node mappings always appear near known corresponding nodes, we propose iMAP, a novel sub-graph expansion based alignment framework to incrementally construct meaningful sub-graphs and perform alignment on each sub-graph pair iteratively, which reduces the unnecessary computation cost in the original raw networks and improves effectiveness via excluding possible noises. Specifically, iMap builds a candidate sub-graph around known matched nodes initially. In each following iteration, iMap trains an alignment model to infer the node mapping relationship between sub-graphs, from which the sub-graphs are further extended and refined. In addition, we design a Graph Neural Network(GNN) based model named MAP on each sub-graph pair in the iMap framework. MAP utilizes trainable Multi-layer Perception (MLP) prediction heads for similarity computation and employs a mixed loss function consisting of the ranking loss for contrastive learning and the cross-entropy loss for classification. Extensive experiments conducted on real social networks demonstrate superior efficiency and effectiveness (above 12% improvement) of our proposed method compared to several state-of-the-art methods.

Graph Neural Networks (GNNs), combining node features and structure information flexibly, have been widely studied and applied in many fields. The growth of graph size and rich features generates a considerable demand for achieving scalability while maintaining good classification performance in the research of GNNs. Graph partition technique, as used in a recent work ClusterGCN, which divides the graph into several sub-graphs, has become an important strategy to achieve the scalability, but the loss of information still affects the results. In this paper, AdClusterGCN is proposed to establish the interaction between graph partition and node classification, in which they can promote each other, and the effectiveness and efficiency of the model can be ensured at the same time. AdClusterGCN combines GNN models trained on a sequence of graph partitions to capture different features, where the current partition is affected using adjusted node/edge weights computed from the results of GNN models on previous partitions. The PageRank and resampling techniques are adopted to keep sufficient attention on important nodes in different models. We implement our method with TensorFlow and experimental studies show that AdClusterGCN achieves state-of-the-art performance on several public benchmarks.

A relational database, consisting of multiple tables, provides heterogeneous information across various entities, widely used in real-world services. This paper studies the supervised learning task on multiple tables, aiming to predict one label column with the help of multiple-tabular data. However, classical ML techniques mainly focus on single-tabular data. Multiple-tabular data refers to many-to-many mapping among joinable attributes and n-ary relations, which cannot be utilized directly by classical ML techniques. Besides, current graph techniques, like heterogeneous information network (HIN) and graph neural networks (GNN), are infeasible to be deployed directly and automatically in a multi-table environment, which limits the learning on databases.

Searching a community containing a given query vertex in an online social network enjoys wide applications like recommendation, team organization, etc. When applied to real-life networks, the existing approaches face two major limitations. First, they usually take two steps, i.e. , crawling a large part of the network first and then finding the community next, but the entire network is usually too big and most of the data are not interesting to end users. Second, the existing methods utilize hand-crafted rules to measure community membership, while it is very difficult to define effective rules as the communities are flexible for different query vertices. In this paper, we propose an Interactive Community Search method based on Graph Neural Network (shortened by ICS-GNN) to locate the target community over a subgraph collected on the fly from an online network. Specifically, we recast the community membership problem as a vertex classification problem using GNN, which captures similarities between the graph vertices and the query vertex by combining content and structural features seamlessly and flexibly under the guide of users' labeling. We then introduce a k -sized Maximum-GNN-scores (shortened by kMG ) community to describe the target community. We next discover the target community iteratively and interactively. In each iteration, we build a candidate subgraph using the crawled pages with the guide of the query vertex and labeled vertices, infer the vertex scores with a GNN model trained on the subgraph, and discover the kMG community which will be evaluated by end users to acquire more feedback. Besides, two optimization strategies are proposed to combine ranking loss into the GNN model and search more space in the target community location. We conduct the experiments in both offline and online real-life data sets, and demonstrate that ICS-GNN can produce effective communities with low overhead in communication, computation, and user labeling.

Helpful reviews in e-commerce sites can help customers acquire detailed information about a certain item, thus affecting customers' buying decisions. Predicting review helpfulness automatically in Taobao is an essential but challenging task for two reasons: (1) whether a review is helpful not only relies on its text, but also is related with the corresponding item and the user who posts the review, (2) the criteria of classifying review helpfulness under different items are not the same. To handle these two challenges, we propose CA-GNN (Category Aware Graph Neural Networks), which uses graph neural networks (GNNs) to identify helpful reviews in a multi-task manner --- we employ GNNs with one shared and many item-specific graph convolutions to learn the common features and each item's specific criterion for classifying reviews simultaneously. To reduce the number of parameters in CA-GNN and further boost its performance, we partition the items into several clusters according to their category information, such that items in one cluster share a common graph convolution.We conduct solid experiments on two public datasets and demonstrate that CA-GNN outperforms existing methods by up to 10.9% in AUC. We also deployed our system in Taobao with online A/B Test and verify that CA-GNN still outperforms the baseline system in most cases.

Data-driven recommender systems that can help to predict users' preferences are deployed in many real online service platforms. Several studies show that they are vulnerable to data poisoning attacks, and attackers have the ability to mislead the system to perform as their desires. Considering the realistic scenario, where the recommender system is usually a black-box for attackers and complex algorithms may be deployed in them, how to learn effective attack strategies on such recommender systems is still an under-explored problem. In this paper, we propose an adaptive data poisoning framework, PoisonRec, which can automatically learn effective attack strategies on various recommender systems with very limited knowledge. PoisonRec leverages the reinforcement learning architecture, in which an attack agent actively injects fake data (user behaviors) into the recommender system, and then can improve its attack strategies through reward signals that are available under the strict black-box setting. Specifically, we model the attack behavior trajectory as the Markov Decision Process (MDP) in reinforcement learning. We also design a Biased Complete Binary Tree (BCBT) to reformulate the action space for better attack performance. We adopt 8 widely-used representative recommendation algorithms as our testbeds, and make extensive experiments on 4 different real-world datasets. The results show that PoisonRec has the ability to achieve good attack performance on various recommender systems with limited knowledge.

Fraud sellers in e-commerce usually promote their products via fake transactions. Such behaviors damage the reputation of the e-commerce platform and jeopardize the business environment in the platform. The search engine of existing e-commerce platforms mainly focuses on generating transactions by matching users' queries and sellers' products. The most common method to defense fraud sellers is to set up a blacklist based on fraud detection and manual investigation, and then punish those sellers in the list, which is inefficient and can only cover a small fraction of potential fraud sellers. In this paper, we propose the first fraud aware impression regulation system (FAIR) which is data-driven and can work in large-scale e-commerce platforms. Its main function is to actively regulate the impressions received by all potential fraud sellers in a real-time fashion. It utilizes the reinforcement learning architecture to dynamically adjust the impression regulation strategy under different reward settings, which can not only promote the impression regulation effects, but also improve the revenue of the platform simultaneously. We deploy FAIR on the Taobao platform of Alibaba, one of the world's largest e-commerce search platform, and perform an A/B test for two weeks. The results show that FAIR can effectively reduce the fraud impressions and improve the overall platform revenue at the same time.

Product bundling, offering a combination of items to customers, is one of the marketing strategies commonly used in online e-commerce and offline retailers. A high-quality bundle generalizes frequent items of interest, and diversity across bundles boosts the user-experience and eventually increases transaction volume. In this paper, we formalize the personalized bundle list recommendation as a structured prediction problem and propose a bundle generation network (BGN), which decomposes the problem into quality/diversity parts by the determinantal point processes (DPPs). BGN uses a typical encoder-decoder framework with a proposed feature-aware softmax to alleviate the inadequate representation of traditional softmax, and integrates the masked beam search and DPP selection to produce high-quality and diversified bundle list with an appropriate bundle size. We conduct extensive experiments on three public datasets and one industrial dataset, including two generated from co-purchase records and the other two extracted from real-world online bundle services. BGN significantly outperforms the state-of-the-art methods in terms of quality, diversity and response time over all datasets. In particular, BGN improves the precision of the best competitors by 16% on average while maintaining the highest diversity on four datasets, and yields a 3.85x improvement of response time over the best competitors in the bundle list recommendation problem.

SimRank is an important measure of vertex-pair similarity according to the structure of graphs. Although progress has been achieved, existing methods still face challenges to handle large graphs. Besides huge index construction and maintenance cost, existing methods may require considerable search space and time overheads in the online SimRank query. In this paper, we design a Monte Carlo based method, UniWalk, to enable the fast top-k SimRank computation over large undirected graphs. UniWalk directly locates the top-k similar vertices for any single source vertex u via R sampling paths originating from u, which avoids selecting candidate vertex set C and the following O(1C1R) bidirectional sampling paths. We also devise a path enumeration strategy to improve the SimRank precision by using path probabilities instead of path frequencies when sampling, a space-efficient method to reduce intermediate results, and a path-sharing strategy to lower the redundant path sampling cost for multiple source vertices. Furthermore, we extend UniWalk to existing distributed graph processing frameworks to improve its scalability. We conduct extensive experiments to illustrate that UniWalk has high scalability, and outperforms the state-of-the-art methods by orders of magnitude.

SimRank is an effective structural similarity measurement between two vertices in a graph, which can be used in many applications like recommender systems. Although progresses have been achieved, existing methods still face challenges to handle large graphs. Besides huge index construction and maintenance cost, the existing methods require considerable search space and time overheads in the online SimRank query. In this paper, we design a Monte Carlo based method, Uni-Walk, to enable the fast top-k SimRank computation over large undirected graphs without indexing. UniWalk directly locates the top-k similar vertices for any single source vertex u via O(R) sampling paths originating from u only, which avoids the selection of candidate vertex set C and the following O(|C|R) bidirectional sampling paths starting from u and each candidate respectively in existing methods. We also design a space-efficient method to reduce intermediate results, and a path-sharing strategy to optimize path sampling for multiple source vertices. Furthermore, we extend UniWalk to existing distributed graph processing frameworks to improve its scalability. We conduct extensive experiments to illustrate that UniWalk has high scalability, and outperforms the state-of-the-art methods by orders of magnitude, and such an improvement is achieved without any indexing overheads.

It is highly desired for existing distributed graph processing systems to support both offline analytics and online queries adaptively. Existing offline graph analytics systems are mostly based on synchronous model. Although achieving high throughput, they suffer relatively high latency in answering simple queries due to synchronization overhead and slow convergence. On the other hand, online graph query systems adopting asynchronous model can response at any time, while incur overwhelmed messages and network packets, making them unable to meet the high throughput demand of offline analytics. In this work, we propose an adaptive asynchronous message processing (AAMP) method, which improves the efficiency of network communication while maintains low latency, to efficiently support offline analytics and online queries in one graph processing framework. We then design GiraphAsync, an implementation of AAMP on top of Apache Giraph, and evaluate it using several representative offline analytics and online queries on large graph datasets. Experimental results show that GiraphAsync gains an up to 10X improvement over synchronous model systems for graph analytics, while performs as well as specialized systems for online graph queries.

With the rapid growth of graphs in different applications, it is inevitable to leverage existing distributed data processing frameworks in managing large graphs. Although these frameworks ease the developing cost, it is still cumbersome and error-prone for developers to implement complex graph analysis tasks in distributed environments. Additionally, developers have to learn the details of these frameworks quite well, which is a key to improve the performance of distributed jobs. This paper introduces a high level query language called GLog and proposes its evaluation method to overcome these limitations. Specifically, we first design a RG (Relational-Graph) data model to mix relational data and graph data, and extend Datalog to GLog on RG tables to support various graph analysis tasks. Second, we define operations on RG tables, and show translation templates to convert a GLog query into a sequence of MapReduce jobs. Third, we propose two strategies, namely rule merging and iteration rewriting, to optimize the translated jobs. The final experiments show that GLog can not only express various graph analysis tasks in a more succinct way, but also achieve a better performance for most of the graph analysis tasks than Pig, another high level dataflow system.

Continuous pattern detection plays an important role in monitoring-related applications. The large size and dynamic update of graphs, along with the massive search space, pose huge challenges in developing an efficient continuous pattern detection system. In this paper, we leverage a distributed graph processing framework to approximately detect a given pattern over a large dynamic graph. We aim to improve the scalability and precision, and reduce the response time and message cost in the detection. We convert a given query pattern into a Single-Sink DAG (Directed Acyclic Graph), and propose an evaluation plan with message transitions on the DAG, which is shorten by SSD plan, to detect the pattern in a large dynamic graph. SSD plan can guide the data graph exploration via messages, and the messages will converge at data sink vertices, which then detect existences of the query pattern. We also conduct join operations over partial vertices during the graph exploration to improve the precision of pattern detection. In addition, we show that SSD plan can support the continuous query over dynamic graphs with slight extensions. We further design various sink vertex selection strategies and neighborhood based transition rule attachment to lower the evaluation cost. The experiments on billion-edge real-life graphs using Giraph, an open source implementation of Pregel, illustrate the efficiency and effectiveness of our method.

Existing distributed graph processing frameworks, e.g. , Pregel, Giraph, GPS and GraphLab, mainly exploit main memory to support flexible graph operations for efficiency. Due to the complexity of graph analytics, huge memory space is required especially for those graph analytics that spawn large intermediate results. Existing frameworks may terminate abnormally or degrade performance seriously when the memory is exhausted or the external storage has to be used. In this paper, we propose MOCgraph, a scalable distributed graph processing framework to reduce the memory footprint and improve the scalability, based on message online computing. MOCgraph consumes incoming messages in a streaming manner, so as to handle larger graphs or more complex analytics with the same memory capacity. MOCgraph also exploits message online computing with external storage to provide an efficient out-of-core support. We implement MOCgraph on top of Apache Giraph, and test it against several representative graph algorithms on large graph datasets. Experiments illustrate that MOCgraph is efficient and memory-saving, especially for graph analytics with large intermediate results.

This paper takes the shortest path discovery to study efficient relational approaches to graph search queries. We first abstract three enhanced relational operators, based on which we introduce an FEM framework to bridge the gap between relational operations and graph operations. We show new features introduced by recent SQL standards, such as window function and merge statement, can improve the performance of the FEM framework. Second, we propose an edge weight aware graph partitioning schema and design a bi-directional restrictive BFS (breadth-first-search)over partitioned tables, which improves the scalability and performance without extra indexing overheads. The final extensive experimental results illustrate our relational approach with optimization strategies can achieve high scalability and performance.

Motivated by the needs such as group relationship analysis, this paper introduces a new operation on graphs, named top-k path join, which discovers the top-k simple shortest paths between two given node sets. Rather than discovering the top-k simple paths between each node pair, this paper proposes a holistic join method which answers the top-k path join by finding constrained top-k simple shortest paths between two nodes, and then devises an efficient method to handle the latter problem. Specifically, we transform the graph by encoding the precomputed shortest paths to the target node, and use the transformed graph in the candidate path searching. We show that the candidate path searching on the transformed graph not only has the same result as that on the original graph but also can be terminated much earlier with the aid of precomputed results. We also discuss two other optimization strategies, including considering the join constraint in the candidate path generation as early as possible, and pruning search space in each candidate path generation with an adaptively determined threshold. The final extensive experimental results also show that our method offers a significant performance improvement over existing ones.

With the advent of cloud computing, it becomes desirable to utilize cloud computing to efficiently process complex operations on large graphs without compromising their sensitive information. This paper studies shortest distance computing in the cloud, which aims at the following goals: i) preventing outsourced graphs from neighborhood attack, ii) preserving shortest distances in outsourced graphs, iii) minimizing overhead on the client side. The basic idea of this paper is to transform an original graph G into a link graph Gl kept locally and a set of outsourced graphs Go. Each outsourced graph should meet the requirement of a new security model called 1-neighborhood-d-radius. In addition, the shortest distance query can be answered using Gl and Go. Our objective is to minimize the space cost on the client side when both security and utility requirements are satisfied. We devise a greedy method to produce Gl and Go, which can exactly answer the shortest distance queries. We also develop an efficient transformation method to support approximate shortest distance answering under a given additive error bound. The final experimental results illustrate the effectiveness and efficiency of our method.

With the rapid growth of large graphs, we cannot assume that graphs can still be fully loaded into memory, thus the disk-based graph operation is inevitable. In this paper, we take the shortest path discovery as an example to investigate the technique issues when leveraging existing infrastructure of relational database (RDB) in the graph data management. Based on the observation that a variety of graph search queries can be implemented by iterative operations including selecting frontier nodes from visited nodes, making expansion from the selected frontier nodes, and merging the expanded nodes into the visited ones, we introduce a relational FEM framework with three corresponding operators to implement graph search tasks in the RDB context. We show new features such as window function and merge statement introduced by recent SQL standards can not only simplify the expression but also improve the performance of the FEM framework. In addition, we propose two optimization strategies specific to shortest path discovery inside the FEM framework. First, we take a bi-directional set Dijkstra's algorithm in the path finding. The bi-directional strategy can reduce the search space, and set Dijkstra's algorithm finds the shortest path in a set-at-a-time fashion. Second, we introduce an index named SegTable to preserve the local shortest segments, and exploit SegTable to further improve the performance. The final extensive experimental results illustrate our relational approach with the optimization strategies achieves high scalability and performance.

With the wide applications of large scale graph data such as social networks, the problem of finding the top-k shortest paths attracts increasing attention. This paper focuses on the discovery of the top-k simple shortest paths (paths without loops). The well known algorithm for this problem is due to Yen, and the provided worstcase bound O(kn(m + nlogn)), which comes from O(n) times single-source shortest path discovery for each of k shortest paths, remains unbeaten for 30 years, where n is the number of nodes and m is the number of edges. In this paper, we observe that there are shared sub-paths among O(kn) single-source shortest paths. The basic idea behind our method is to pre-compute the shortest paths to the target node, and utilize them to reduce the discovery cost at running time. Specifically, we transform the original graph by encoding the pre-computed paths, and prove that the shortest path discovered over the transformed graph is equivalent to that in the original graph. Most importantly, the path discovery over the transformed graph can be terminated much earlier than before. In addition, two optimization strategies are presented. One is to reduce the total iteration times for shortest path discovery, and the other is to prune the search space in each iteration with an adaptively-determined threshold. Although the worst-case complexity cannot be lowered, our method is proven to be much more efficient in a general case. The final extensive experimental results (on both real and synthetic graphs) also show that our method offers a significant performance improvement over the existing ones.

Mobile communication data analysis has been often used as a background application to motivate many data mining problems. However, very few data mining researchers have a chance to see a working data mining system on real mobile communication data. In this demo, we showcase our new system MobileMiner on a real mobile communication data set, which presents a case study of business solutions using state-of-the-art data mining techniques. MobileMiner adaptively profiles users' behavior from their calling and moving record streams. Customer segmentation and social community analysis can be conducted based on user profiles. We show how data mining techniques can help in mobile communication data analysis. Moreover, we also show some interesting observations which still cannot be mined by the current techniques, and thus may motivate new research and development.

In the Vehicle Ad-hoc NETwork (VANET), moving vehicles organize into a mobile wireless Ad-hoc network to share online traffic information. Each vehicle can issue a declarative query for aggregating the traffic information from others in order to facilitate the navigation and avoid traffic jam. Existing query methods suffer from high latency, incomplete results, and large messages due to the movement of the vehicles in VANET. In this paper, we propose an adaptive query evaluation method based on the road network. In order to overcome the problems incurred by the movement, a relative static query evaluation plan is constructed based on the road network, and each vehicle can participate in the query evaluation plan autonomously. We also introduce control messages to notify the changed location of the query originator to other vehicles involved in the evaluation plan. In addition, we propose an one time message transferring based results collecting method to reduce the message cost. The optimization over the multiple queries is also discussed to reduce the messages further. We evaluate the performance of our method by extensive simulations. Experimental results show that our method can provide complete results within a short response time and small traffic overhead.

As WWW becomes more and more popular and powerful, how to search information on the web in database way becomes an important research topic. COMMIX, which is developed in the DB group in Peking University (China), is a system towards building very large database using data from the Web for information extraction, integration and query answering. COMMIX has some innovative features, such as ontology-based wrapper generation, XML-based information integration, view-based query answering, and QBE-style XML query interface.