Index recommendation is crucial for optimizing database performance. However, existing heuristic- and learning-based methods often rely on inefficient exhaustive search and estimated costs, leading to low efficiency (due to the vast search space) and unsatisfactory actual latency (due to inaccurate estimations). Inspired by the refinement strategies of experienced DBAs-who efficiently identify and iteratively refine indexes with database feedback-we present LLMIA, an out-of-the-box, tuning-free index advisor leveraging large language models (LLMs) through in-context learning for index recommendation. LLMIA injects database expertise into the LLM using a high-quality demonstration pool and comprehensive workload feature extraction, while iteratively incorporating database feedback to guide the index refinement. This design enables LLMIA to emulate the decision-making process of expert DBAs: efficiently recommending and refining indexes for various workloads within just a few interactions with the DBMS. We validate LLMIA with extensive experiments on five standard OLAP benchmarks (TPC-H with different scales, JOB, TPC-DS, SSB), where it consistently outperforms or matches 12 baselines by producing superior index recommendations with minimal database interactions. Additionally, LLMIA demonstrates robust generalization on two real-world commercial workloads, delivering high-quality recommendations without the need for additional adaptation or retraining, highlighting its out-of-the-box capability.

Efficiently execution of join operations over large-scale distributed data is critical in modern analytical engines, yet costly shuffle operations involving extensive network transfer and remote I/O often hinder performance. Existing data layout techniques struggle with complex multi-table joins due to inflexible distribution key assignments, suboptimal cluster key choices that require significant manual tuning, and weak co-optimization with downstream join strategy selection. This paper introduces PAC-Tree ( P artition- A ligned C o-Join Tree ), a novel query-aware data layout designed to comprehensively address these limitations in an end-to-end manner. PAC-Tree features a two-level hierarchical structure: the upper level replicates fact tables with diverse distribution keys to improve co-location across join patterns, while the lower level applies advanced multidimensional partitioning with predicate-aware splits for fine-grained intra-shard data skipping. Leveraging PAC-Tree’s statistics, we further propose a block-grouping algorithm to construct co-partitions under memory constraints and a PRIM-based reordering policy for multi-table joins, together significantly reducing shuffle overhead. Experiments on a real Spark cluster demonstrate that PAC-Tree reduces query latency by up to 45.7% and improves throughput by up to 2 \(\times\) compared with state-of-the-art layouts, especially for join-heavy workloads.

Clustering traditionally aims to reveal a natural grouping structure within unlabeled data. However, this structure may not always align with users' preferences. In this paper, we propose a personalized clustering method that explicitly performs targeted representation learning by interacting with users via modicum task information (e.g., must-link or cannot-link pairs) to guide the clustering direction. We query users with the most informative pairs, i.e., those pairs most hard to cluster and those most easy to miscluster, to facilitate the representation learning in terms of the clustering preference. Moreover, by exploiting attention mechanism, the targeted representation is learned and augmented. By leveraging the targeted representation and constrained contrastive loss as well, personalized clustering is obtained. Theoretically, we verify that the risk of personalized clustering is tightly bounded, guaranteeing that active queries to users do mitigate the clustering risk. Experimentally, extensive results show that our method performs well across different clustering tasks and datasets, even when only a limited number of queries are available.

Catastrophic forgetting is a key challenge in incremental named entity recognition (INER). Existing methods often address this issue through distillation-based approaches, which involve transferring previously learned knowledge from the old model to the new one. However, these methods may not fully equip the new model with an adequate understanding of the characteristics about old entity types, leading to confusion when classifying tokens associated with these entity types. To address this challenge, we propose a novel method called Prototypical Replay with Old-class Focusing Knowledge Distillation (POF) for INER. Our approach focuses on preserving the main characteristics of each previous entity type by storing compact prototypes and replaying them with appropriate frequency. This replay strategy makes the new model review the knowledge of old entity types while minimizing storage needs. Additionally, we introduce an old-class focusing knowledge distillation (OFKD) loss, which distills features only in old-class regions to maintain the quality of old-class prototypes and prevent ineffective prototypical replay while preserving sufficient plasticity for learning new entity types. We conducted experiments on three benchmark datasets (i.e., Few-NERD, I2B2 and OntoNotes5), and the results demonstrate that our method outperforms all previous state-of-the-art methods.

Pruning has become a widely adopted technique for reducing the hardware requirements of large language models (LLMs). To recover model performance after pruning, post-training is commonly employed to mitigate the resulting performance degradation. While post-training benefits from larger datasets, once the dataset size is already substantial, increasing the training data provides only limited performance gains. To balance post-training cost and model performance, it is necessary to explore the optimal amount of post-training data. Through extensive experiments on the Llama-3 and Qwen-2.5 series models, pruned using various common pruning methods, we uncover the scaling Law for Post-training after model Pruning, referred to as the P^2 Law. This law identifies four key factors for predicting the pruned model’s post-training loss: the model size before pruning, the number of post-training tokens, the pruning rate, and the model’s loss before pruning. Moreover, P^2 Law can generalize to larger dataset sizes, larger model sizes, and higher pruning rates, offering valuable insights for the post-training of pruned LLMs.

Yuxuan Hu, Ke Wang, Xiaokang Zhang, Fanjin Zhang, Cuiping Li, Hong Chen, Jing Zhang. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

Federated learning-based Named Entity Recognition (FNER) has attracted widespread attention through decentralized training on local clients. However, most FNER models assume that entity types are pre-fixed, so in practical applications, local clients constantly receive new entity types without enough storage to access old entity types, resulting in severe forgetting on previously learned knowledge. In addition, new clients collecting only new entity types may join the global training of FNER irregularly, further exacerbating catastrophic forgetting. To overcome the above challenges, we propose a Forgetting-Subdued Learning (FSL) model which solves the forgetting problem on old entity types from both intra-client and inter-client two aspects. Specifically, for intra-client aspect, we propose a prototype-guided adaptive pseudo labeling and a prototypical relation distillation loss to surmount catastrophic forgetting of old entity types with semantic shift. Furthermore, for inter-client aspect, we propose a task transfer detector. It can identify the arrival of new entity types that are protected by privacy and store the latest old global model for relation distillation. Qualitative experiments have shown that our model has made significant improvements compared to several baseline methods.

This paper introduces LLM-Streamline, a pioneer work on layer pruning for large language models (LLMs). It is based on the observation that different layers have varying impacts on hidden states, enabling the identification of less important layers to be pruned. LLM-Streamline comprises two parts: layer pruning, which removes consecutive layers with the lowest importance based on target sparsity, and layer replacement, a novel module that trains a lightweight network to replace the pruned layers to mitigate performance loss. Additionally, a new metric called stability is proposed to address the limitations of the widely used accuracy metric in evaluating model compression. Experiments show that LLM-Streamline outperforms both previous and concurrent state-of-the-art pruning methods in terms of both performance and training efficiency. Our code is available at \href{https://github.com/RUCKBReasoning/LLM-Streamline}{this repository}.

Class distribution mismatch (CDM) refers to the discrepancy between class distributions in training data and target tasks. Previous methods address this by designing classifiers to categorize classes known during training, while grouping unknown or new classes into an "other" category. However, they focus on semi-supervised scenarios and heavily rely on labeled data, limiting their applicability and performance. To address this, we propose Unsupervised Learning for Class Distribution Mismatch (UCDM), which constructs positive-negative pairs from unlabeled data for classifier training. Our approach randomly samples images and uses a diffusion model to add or erase semantic classes, synthesizing diverse training pairs. Additionally, we introduce a confidence-based labeling mechanism that iteratively assigns pseudo-labels to valuable real-world data and incorporates them into the training process. Extensive experiments on three datasets demonstrate UCDM’s superiority over previous semi-supervised methods. Specifically, with a 60\% mismatch proportion on Tiny-ImageNet dataset, our approach, without relying on labeled data, surpasses OpenMatch (with 40 labels per class) by 35.1%, 63.7%, and 72.5% in classifying known, unknown, and new classes.

Database knob tuning is a long-standing challenge in the database community, aimed at enhancing the performance of database management systems (DBMSs) by minimizing latency and maximizing throughput. Manual tuning, which relies heavily on human expertise, is often inefficient and impractical for large-scale or dynamic deployments. Recent work has explored automating this process using machine learning (ML) and large language models (LLMs). However, existing methods typically require hundreds of workload replays or rely on extensive training data, leading to low tuning efficiency or high preparation costs. Moreover, they also risk generating invalid configurations that can degrade performance or even crash the database. To address these limitations, we introduce AgentTune, the first agent-based knob tuning framework powered by LLMs, designed for efficiency, adaptability, and reliability. AgentTune decomposes the tuning process into four specialized agents: Workload Analyzer, Knob Selector, Range Pruner, and Configuration Recommender, each responsible for a distinct subtask. These agents collaborate through structured prompt chaining. AgentTune first analyzes the input workload to identify impactful knobs and reconstructs their valid ranges to reduce the search space. It then employs a tree-based search strategy to efficiently explore the configuration space and identify suitable knob values. We conduct extensive evaluations across diverse workloads (public benchmarks and real-world workloads), metrics (latency and throughput), DBMSs (PostgreSQL, MySQL, and TiDB), hardware environments, and database scales. Experimental results demonstrate that, compared to existing baselines, AgentTune is able to identify superior configurations using significantly fewer workload replays. Furthermore, AgentTune rarely generates invalid configurations during the tuning process, ensuring reliability and suitability for real-world deployments.

Semi-supervised learning (SSL) confronts a formidable challenge under class distribution mismatch, wherein unlabeled data contain numerous categories absent in the labeled dataset. Traditional SSL methods undergo performance deterioration in such mismatch scenarios due to the invasion of those instances from unknown categories. Despite some technical efforts to enhance SSL by mitigating the invasion, the profound theoretical analysis of SSL under class distribution mismatch is still under study. Accordingly, in this work, we propose Bi-Objective Optimization Mechanism (BOOM) to theoretically analyze the excess risk between the empirical optimal solution and the population-level optimal solution. Specifically, BOOM reveals that the SSL error is the essential contributor behind excess risk, resulting from both the pseudo-labeling error and invasion error. Meanwhile, BOOM unveils that the optimization objectives of SSL under mismatch are binary: high-quality pseudo-labels and adaptive weights on the unlabeled instances, which contribute to alleviating the pseudo-labeling error and the invasion error, respectively. Moreover, BOOM explicitly discovers the fundamental factors crucial for optimizing the bi-objectives, guided by which an approach is then proposed as a strong baseline for SSL under mismatch. Extensive experiments on benchmark and real datasets confirm the effectiveness of our proposed algorithm.

Text-to-SQL, the task of translating natural language questions into SQL queries, plays a crucial role in enabling non-experts to interact with databases. While recent advancements in large language models (LLMs) have significantly enhanced text-to-SQL performance, existing approaches face notable limitations in real-world text-to-SQL applications. Prompting-based methods often depend on closed-source LLMs, which are expensive, raise privacy concerns, and lack customization. Fine-tuning-based methods, on the other hand, suffer from poor generalizability due to the limited coverage of publicly available training data. To overcome these challenges, we propose a novel and scalable text-to-SQL data synthesis framework for automatically synthesizing large-scale, high-quality, and diverse datasets without extensive human intervention. Using this framework, we introduce SynSQL-2.5M, the first million-scale text-to-SQL dataset, containing 2.5 million samples spanning over 16,000 synthetic databases. Each sample includes a database, SQL query, natural language question, and chain-of-thought (CoT) solution. Leveraging SynSQL-2.5M, we develop OmniSQL, a powerful open-source text-to-SQL model available in three sizes: 7B, 14B, and 32B. Extensive evaluations across nine datasets demonstrate that OmniSQL achieves state-of-the-art performance, matching or surpassing leading closed-source and open-source LLMs, including GPT-4o and DeepSeek-V3, despite its smaller size. We release all code, datasets, and models to support further research.

Learned indexes, emerging as a promising alternative to traditional indexes like B+Tree, utilize machine learning models to enhance query performance and reduce memory usage. However, the widespread adoption of learned indexes is limited by their expensive training cost and the need for high accuracy of internal models. Although some studies attempt to optimize the building process of these learned indexes, existing methods are restrictive in scope and applicability. They are usually tailored to specific index types and heavily rely on pre-trained model knowledge, making deployment a challenging task. In this work, we introduce the Learned Index Optimization Framework (LIOF), a general and easily integrated solution aimed at expediting the training process and improving the accuracy of index model for one-dimensional and multi-dimensional learned indexes. The optimization of LIOF for the learned indexes is intuitive, directly providing optimized parameters for index models based on the distribution of node data. By leveraging the correlation between key distribution and node model parameters, LIOF significantly reduces the training epochs required for each node model. Initially, we introduce an optimization strategy inspired by optimization-based meta-learning to train the LIOF to generate optimized initial parameters for index node models. Subsequently, we present a data-driven encoder and a parameter-centric decoder network, which adaptively translate key distribution into a latent variable representation and decode it into optimized node model initialization. Additionally, to further utilize characteristics of key distribution, we propose a monotonic regularizer and focal loss, guiding LIOF training towards efficiency and precision. Through extensive experimentation on real-world and synthetic datasets, we demonstrate that LIOF provides substantial enhancements in both training efficiency and the predictive accuracy for learned indexes.

Vertical partitioning is a crucial physical design strategy in databases that enhances data management and retrieval through optimal data placement. However, current research often overlooks the use of query predicates for effective data block allocation, resulting in potential performance bottlenecks. Moreover, selecting an appropriate partitioning technique based solely on historical experimental results from research articles is challenging due to variability in storage devices, evaluation metrics, and database schemas. We propose PARS to address these issues by offering end-to-end input/output, customizable database configurations, and prioritized optimization objectives to aid database administrators (DBAs) in making informed partitioning decisions. Additionally, PARS introduces a novel algorithm that leverages both numeric and non-numeric query predicates to partition the tablespace into finer data blocks, reducing query latency by 36.1% when benchmarked against the state-of-the-art (SOTA) method.

Previous methods on knowledge base question generation (KBQG) primarily focus on refining the quality of a single generated question. However, considering the remarkable paraphrasing ability of humans, we believe that diverse texts can express identical semantics through varied expressions. The above insights make diversifying question generation an intriguing task, where the first challenge is evaluation metrics for diversity. Current metrics inadequately assess the aforementioned diversity. They calculate the ratio of unique n-grams in the generated question, which tends to measure duplication rather than true diversity. Accordingly, we devise a new diversity evaluation metric, which measures the diversity among top-k generated questions for each instance while ensuring their relevance to the ground truth. Clearly, the second challenge is how to enhance diversifying question generation. To address this challenge, we introduce a dual model framework interwoven by two selection strategies to generate diverse questions leveraging external natural questions. The main idea of our dual framework is to extract more diverse expressions and integrate them into the generation model to enhance diversifying question generation. Extensive experiments on widely used benchmarks for KBQG show that our approach can outperform pre-trained language model baselines and text-davinci-003 in diversity while achieving comparable performance with ChatGPT.

Conversational Question Generation (CQG) enhances the interactivity of conversational question-answering systems in fields such as education, customer service, and entertainment.However, traditional CQG, focusing primarily on the immediate context, lacks the conversational foresight necessary to guide conversations toward specified conclusions.This limitation significantly restricts their ability to achieve conclusion-oriented conversational outcomes.In this work, we redefine the CQG task as Conclusion-driven Conversational Question Generation (CCQG) by focusing on proactivity, not merely reacting to the unfolding conversation but actively steering it towards a conclusion-oriented question-answer pair.To address this, we propose a novel approach, called Proactive Conversational Question Planning with self-Refining (PCQPR).Concretely, by integrating a planning algorithm inspired by Monte Carlo Tree Search (MCTS) with the analytical capabilities of large language models (LLMs), PCQPR predicts future conversation turns and continuously refines its questioning strategies.This iterative self-refining mechanism ensures the generation of contextually relevant questions strategically devised to reach a specified outcome.Our extensive evaluations demonstrate that PCQPR significantly surpasses existing CQG methods, marking a paradigm shift towards conclusion-oriented conversational question-answering systems. * This work was done during an

Open-world semi-supervised learning (Open-world SSL) for node classification, that classifies unlabeled nodes into seen classes or multiple novel classes, is a practical but under-explored problem in the graph community. As only seen classes have human labels, they are usually better learned than novel classes, and thus exhibit smaller intra-class variances within the embedding space (named as imbalance of intra-class variances between seen and novel classes). Based on empirical and theoretical analysis, we find the variance imbalance can negatively impact the model performance. Pre-trained feature encoders can alleviate this issue via producing compact representations for novel classes. However, creating general pre-trained encoders for various types of graph data has been proven to be challenging. As such, there is a demand for an effective method that does not rely on pre-trained graph encoders. In this paper, we propose an IMbalance-A ware method named OpenIMA for Open-world semi-supervised node classification, which trains the node classification model from scratch via contrastive learning with bias-reduced pseudo labels. Extensive experiments on seven popular graph benchmarks demonstrate the effectiveness of OpenIMA, and the source code has been available on GitHub11https://github.com/RUCKBReasoning/OpenIMA.

Various works have utilized deep learning to address the query optimization problem in database system. They either learn to construct plans from scratch in a bottom-up manner or steer the plan generation behavior of traditional optimizer using hints. While these methods have achieved some success, they face challenges in either low training efficiency or limited plan search space. To address these challenges, we introduce FOSS, a novel framework for query optimization based on deep reinforcement learning. FOSS initiates optimization from the original plan generated by a traditional optimizer and incrementally refines suboptimal nodes of the plan through a sequence of actions. Additionally, we devise an asymmetric advantage model to evaluate the advantage between two plans. We integrate it with a traditional optimizer to form a simulated environment. Leveraging this simulated environment, FOSS can bootstrap itself to rapidly generate a large amount of high-quality simulated experiences. FOSS then learns from these experiences to improve its optimization capability. We evaluate the performance of FOSS on Join Order Benchmark, TPC-DS, and Stack Overflow. The experimental results demonstrate that FOSS outperforms the state-of-the-art methods in terms of latency performance. Compared to PostgreSQL, FOSS achieves speedup ranging from 1.15x to 8.33x in total latency across different benchmarks.

Language models have shown promising performance on the task of translating natural language questions into SQL queries (Text-to-SQL). However, most of the state-of-the-art (SOTA) approaches rely on powerful yet closed-source large language models (LLMs), such as ChatGPT and GPT-4, which may have the limitations of unclear model architectures, data privacy risks, and expensive inference overheads. To address the limitations, we introduce CodeS, a series of pre-trained language models with parameters ranging from 1B to 15B, specifically designed for the text-to-SQL task. CodeS is a fully open-source language model, which achieves superior accuracy with much smaller parameter sizes. This paper studies the research challenges in building CodeS. To enhance the SQL generation abilities of CodeS, we adopt an incremental pre-training approach using a specifically curated SQL-centric corpus. Based on this, we address the challenges of schema linking and rapid domain adaptation through strategic prompt construction and a bi-directional data augmentation technique. We conduct comprehensive evaluations on multiple datasets, including the widely used Spider benchmark, the newly released BIRD benchmark, robustness-diagnostic benchmarks such as Spider-DK, Spider-Syn, Spider-Realistic, and Dr.Spider, as well as two real-world datasets created for financial and academic applications. The experimental results show that our CodeS achieves new SOTA accuracy and robustness on nearly all challenging text-to-SQL benchmarks.

Triangle count estimation is a fundamental task in federated graph analysis. Yet, directly collecting local counts from users exposes individuals to severe privacy risks, as the local reports may reveal sensitive social connections. Protecting edge privacy in triangle count estimation is extremely challenging due to the strong data correlation among distinct users and large data sensitivity. Though many efforts have been put into addressing this issue, the existing works fail to provide a stringent privacy guarantee as well as a promising data utility. Motivated by this, we first propose an enhanced privacy notion namely Edge Relationship Local Differential Privacy (Edge-RLDP) that formally considers data correlations and provides a stringent privacy guarantee by hiding multiple edges in the global graph. Based on Edge-RLDP, we further propose a PRIvacy-preserved federated Estimator for Triangle count (PRIVET) with three perturbation algorithms, which enhances the estimation accuracy by designing specialized noise calibration schemes and leveraging a triangle-subsample trick. Theoretically, we prove that PRIVET achieves (ε δ)-Edge-RLDP. Empirically, we verify that PRIVET provides promising estimation accuracy in terms of mean relative error.

One of the recent best attempts at Text-to-SQL is the pre-trained language model. Due to the structural property of the SQL queries, the seq2seq model takes the responsibility of parsing both the schema items (i.e., tables and columns) and the skeleton (i.e., SQL keywords). Such coupled targets increase the difficulty of parsing the correct SQL queries especially when they involve many schema items and logic operators. This paper proposes a ranking-enhanced encoding and skeleton-aware decoding framework to decouple the schema linking and the skeleton parsing. Specifically, for a seq2seq encoder-decode model, its encoder is injected by the most relevant schema items instead of the whole unordered ones, which could alleviate the schema linking effort during SQL parsing, and its decoder first generates the skeleton and then the actual SQL query, which could implicitly constrain the SQL parsing. We evaluate our proposed framework on Spider and its three robustness variants: Spider-DK, Spider-Syn, and Spider-Realistic. The experimental results show that our framework delivers promising performance and robustness. Our code is available at https://github.com/RUCKBReasoning/RESDSQL.

Lingxi Zhang, Jing Zhang, Yanling Wang, Shulin Cao, Xinmei Huang, Cuiping Li, Hong Chen, Juanzi Li. Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2023.

In many real scenarios, data are often divided into a handful of artificial super categories in terms of expert knowledge rather than the representations of images. Concretely, a superclass may contain massive and various raw categories, such as refuse sorting. Due to the lack of common semantic features, the existing classification techniques are intractable to recognize superclass without raw class labels, thus they suffer severe performance damage or require huge annotation costs. To narrow this gap, this paper proposes a superclass learning framework, called SuperClass Learning with Representation Enhancement(SCLRE), to recognize super categories by leveraging enhanced representation. Specifically, by exploiting the self-attention technique across the batch, SCLRE collapses the boundaries of those raw categories and enhances the representation of each superclass. On the enhanced representation space, a superclassaware decision boundary is then reconstructed. Theoretically, we prove that by leveraging attention techniques the generalization error of SCLRE can be bounded under superclass scenarios. Experimentally, extensive results demonstrate that SCLRE outperforms the baseline and other contrastive-based methods on CIFAR-100 datasets and four high-resolution datasets.

Math word problems (MWP) involving advanced operators such as linear equation solver cannot be easily tackled by earlier MWP methods, because the existing generation methods suffer from repeated sub-expression generation and deductive methods are restricted to dealing with binary operations.This paper propose a new multivariate directed acyclic graph (mDAG) as an alternative to the generation methods' binary expression tree or the deductive methods' binary directed acyclic graph.Then to produce the topological ordering of mDAG, we propose a generation-based deductive (GeDe) model, which equips a generation model with a re-encoder to keep the deductive property but avoid the expensive enumeration of the deductive methods.GeDe performs well on math problems with many operators on the widely used benchmarks as well as solving multivariate operators on our own CMWPA benchmark.Our code is available at

Semi-Supervised Learning (SSL) under class distribution mismatch aims to tackle a challenging problem wherein unlabeled data contain lots of unknown categories unseen in the labeled ones. In such mismatch scenarios, traditional SSL suffers severe performance damage due to the harmful invasion of the instances with unknown categories into the target classifier. In this study, by strict mathematical reasoning, we reveal that the SSL error under class distribution mismatch is composed of pseudo-labeling error and invasion error, both of which jointly bound the SSL population risk. To alleviate the SSL error, we propose a robust SSL framework called Weight-Aware Distillation (WAD) that, by weights, selectively transfers knowledge beneficial to the target task from unsupervised contrastive representation to the target classifier. Specifically, WAD captures adaptive weights and high-quality pseudo-labels to target instances by exploring point mutual information (PMI) in representation space to maximize the role of unlabeled data and filter unknown categories. Theoretically, we prove that WAD has a tight upper bound of population risk under class distribution mismatch. Experimentally, extensive results demonstrate that WAD outperforms five state-of-the-art SSL approaches and one standard baseline on two benchmark datasets, CIFAR10 and CIFAR100, and an artificial cross-dataset. The code is available at https://github.com/RUC-DWBI-ML/research/tree/main/WAD-master.

Active learning(AL) has been successful based on the premise that labeled and unlabeled data come from the same class distribution. However, its performance undergoes a severe deterioration under class distribution mismatch, wherein the unlabeled data contain numerous instances out of the class distribution of labeled data. In this article, we solve this practical yet rarely studied problem by minimizing the AL error, which is formally defined and decomposed as the valid query error and invalid query error. Specifically, the invalid query error is associated with the queries from unknown categories, and the valid query error is attributed to less informative queries from target categories. In light of this discovery, we propose a contrastive AL framework, named ConAL, to simultaneously learn the semantics and distinctiveness of the instances by contrastive techniques, thereby reducing the invalid query error and valid query error, respectively. Theoretically, we prove that the AL error of ConAL has a tight upper bound. Experimentally, ConAL achieves superior performance on two benchmark datasets, CIFAR10 and CIFAR100, and a cross-dataset with class distribution across multi-datasets. Furthermore, we validate that the ConAL technique performs admirably even on the realistic dataset. To the best of our knowledge, ConAL is the first AL work for class distribution mismatch.

Inaccurate-supervised learning (ISL) is a weakly supervised learning framework for imprecise annotation, which is derived from some specific popular learning frameworks, mainly including partial label learning (PLL), partial multilabel learning (PML), and multiview PML (MVPML). While PLL, PML, and MVPML are each solved as independent models through different methods and no general framework can currently be applied to these frameworks, most existing methods for solving them were designed based on traditional machine-learning techniques, such as logistic regression, KNN, SVM, decision tree. Prior to this study, there was no single general framework that used adversarial networks to solve ISL problems. To narrow this gap, this study proposed an adversarial network structure to solve ISL problems, called ISL with generative adversarial nets (ISL-GANs). In ISL-GAN, fake samples, which are quite similar to real samples, gradually promote the Discriminator to disambiguate the noise labels of real samples. We also provide theoretical analyses for ISL-GAN in effectively handling ISL data. In this article, we propose a general framework to solve PLL, PML, and MVPML, while in the published conference version, we adopt the specific framework, which is a special case of the general one, to solve the PLL problem. Finally, the effectiveness is demonstrated through extensive experiments on various imprecise annotation learning tasks, including PLL, PML, and MVPML.

As the location-based applications ourishing, we will witness soon the transferring of a prodigious amount of data from the local to a public cloud. The rising demand for outsourced data is moving toward a wider geographical area with arbitrary distribution (i.e., dense or sparse) and query scope (i.e., limited or vast). In terms of cloud risks, the outsourced individual data should be preserved when being queried, especially for location information. Geometric range queries are one of the most fundamental search functions. However, the existed works of secure geometric queries are far from practical usage on efciency and security simultaneously. In this paper, we propose a novel scheme, LuxGeo. Our scheme reaches a constant navigation and a linear sweep, which is tailored for secure and efcient location-lookup. Our experiments over three real-world spatial datasets have shown its practical efciency. For example, it only takes 10.01s with 728 tuples retrieved over 63, 369 ciphertext dataset for a single query. LuxGeo has better performance than the existed solutions for a GSE problem on efciency and security.

The accuracy of selectivity estimation is of vital importance to create good query plans. Traditional estimators such as histograms make several assumptions during estimation that can lead to huge errors. Recently the database community started exploring the usage of machine learning in selectivity estimation and won great achievements. However, due to the black box models they used, existing learning-based methods still face several new challenges, including high estimation latency, large training data demanding, and occurrence of illogical results. In this work, we propose a learning-based MOnotonic Selectivity Estimator (MOSE) to address these challenges. We first learn a multi-dimensional cumulative distribution function of the data in a supervised method and then compute selectivity for ad hoc query predicates at rum-time. We propose a novel regularizer and an effective attribute-aware calibration method to improve the estimation accuracy. To further improve the model efficiency, we design a mutual information based model ensemble method. With regard to the heavy cost of training data collection, we design a model-based active learning strategy to generate high-quality training data cost-effectively. We conduct extensive experiments on both real-world and synthetic datasets and the results show that MOSE outperforms the state-of-the-art methods in terms of accuracy and efficiency.

Phrase mining is an essential step when transforming unstructured text into structured information, in which the aim is to extract high-quality phrases from given corpora automatically. Existing statistics-based methods have achieved state-of-the-art performance on this task. However, such methods often rely heavily on statistical signals to extract quality phrases, ignoring the effect of contextual information. In this paper, we propose a novel context-aware method, called ConPhrase, for quality phrase mining under distantly supervised settings. Specifically, ConPhrase formulates phrase mining as a sequence labeling problem by considering local contextual information, and also incorporates distant supervision methods to automatically generate labeled data. It comprises two modules designed to tackle global information scarcity and noisy data filtration: 1) a topic-aware phrase recognition network that incorporates domain-related topic information into word representation learning to identify quality phrases effectively; 2) an instance selection network that focuses on choosing correct sentences with reinforcement learning for improving the prediction performance of the phrase recognition network. Moreover, we also propose an extended variant of ConPhrase, called ConPhrase+, that further enhances phrase recognition by utilizing document-level contextual information across sentences within the entire document. Experimental results show that contextual information is indispensable for phrase mining and our context-aware methods perform significantly better than state-of-the-art approaches on three publicly available datasets.

The cold-start issue is a fundamental challenge in Recommender Systems. The recent self-supervised learning (SSL) on Graph Neural Networks (GNNs) model, PT-GNN, pre-trains the GNN model to reconstruct the cold-start embeddings and has shown great potential for cold-start recommendation. However, due to the over-smoothing problem, PT-GNN can only capture up to 3-order relation, which cannot provide much useful auxiliary information to depict the target cold-start user or item. Besides, the embedding reconstruction task only considers the intra-correlations within the subgraph of users and items, while ignoring the inter-correlations across different subgraphs. To solve the above challenges, we propose a multi-strategy-based pre-training method for cold-start recommendation (MPT), which extends PT-GNN from the perspective of model architecture and pretext tasks to improve the cold-start recommendation performance. 1 Specifically, in terms of the model architecture, in addition to the short-range dependencies of users and items captured by the GNN encoder, we introduce a Transformer encoder to capture long-range dependencies. In terms of the pretext task, in addition to considering the intra-correlations of users and items by the embedding reconstruction task, we add an embedding contrastive learning task to capture inter-correlations of users and items. We train the GNN and Transformer encoders on these pretext tasks under the meta-learning setting to simulate the real cold-start scenario, making the model able to be easily and rapidly adapted to new cold-start users and items. Experiments on three public recommendation datasets show the superiority of the proposed MPT model against the vanilla GNN models, the pre-training GNN model on user/item embedding inference, and the recommendation task.

Expert finding, a popular service provided by many online websites such as Expertise Finder, LinkedIn, and AMiner, is beneficial to seeking candidate qualifications, consultants, and collaborators. However, its quality is suffered from lack of ample sources of expert information. This paper employs AMiner as the basis with an aim at linking any external experts to the counterparts on AMiner. As it is infeasible to acquire sufficient linkages from arbitrary external sources, we explore the problem of zero-shot expert linking. In this paper, we propose CODE, which first pre-trains an expert linking model by contrastive learning on AMiner such that it can capture the representation and matching patterns of experts without supervised signals, then it is fine-tuned between AMinerand external sources to enhance the model’s transferability in an adversarial manner. For evaluation, we first design two intrinsic tasks, author identification and paper clustering, to validate the representation and matching capability endowed by contrastive learning. Then the final external expert linking performance on two genres of external sources also implies the superiority of adversarial fine-tuning method. Additionally, we show the online deployment of CODE, and continuously improve its online performance via active learning.

Recent works on knowledge base question answering (KBQA) retrieve subgraphs for easier reasoning.The desired subgraph is crucial as a small one may exclude the answer but a large one might introduce more noises.However, the existing retrieval is either heuristic or interwoven with the reasoning, causing reasoning on the partial subgraphs, which increases the reasoning bias when the intermediate supervision is missing.This paper proposes a trainable subgraph retriever (SR) decoupled from the subsequent reasoning process, which enables a plug-and-play framework to enhance any subgraph-oriented KBQA model.Extensive experiments demonstrate SR achieves significantly better retrieval and QA performance than existing retrieval methods.Via weakly supervised pre-training as well as the end-to-end fine-tuning, SR achieves new state-of-the-art performance when combined with NSM (He et al., 2021), a subgraph-oriented reasoner, for embedding-based KBQA methods.Codes and datasets are available online 1 .

Existing methods on knowledge base question generation (KBQG) learn a one-size-fits-all model by training together all subgraphs without distinguishing the diverse semantics of subgraphs.In this work, we show that making use of the past experience on semantically similar subgraphs can reduce the learning difficulty and promote the performance of KBQG models.To achieve this, we propose a novel approach to model diverse subgraphs with metalearner (DSM).Specifically, we devise a graph contrastive learning-based retriever to identify semantically similar subgraphs, so that we can construct the semantics-aware learning tasks for the meta-learner to learn semanticsspecific and semantics-agnostic knowledge on and across these tasks.Extensive experiments on two widely-adopted benchmarks for KBQG show that DSM derives new state-of-the-art performance and benefits the question answering tasks as a means of data augmentation.Codes and datasets are available online 1 .

Local differential privacy (LDP), a technique applying unbiased statistical estimations instead of real data, is often adopted in data collection. In particular, this technique is used in frequency oracles (FO) because it can protect each user’s privacy and prevent leakage of sensitive information. However, the definition of LDP is so conservative that it requires all inputs to be indistinguishable after perturbation. Indeed, LDP protects each value; however, it is rarely used in practical scenarios owing to its cost in terms of accuracy. In this paper, we address the challenge of providing weakened but flexible protection where each value only needs to be indistinguishable from part of the domain after perturbation. First, we present this weakened but flexible LDP (FLDP) notion which splits the domain. We then prove the association with LDP. Second, we design a Flexible Hadamard Response (FHR) approach for the common FO issue while satisfying FLDP. The proposed approach balances communication cost, computational complexity, and estimation accuracy. Finally, experimental results using practical and synthetic datasets verify the effectiveness and efficiency of our approach.

Counting subgraphs in decentralized settings has drawn increasing attention for graph analysis, wherein triangle count is one of the fundamental statistics. However, triangle counts may breach edge privacy, such as sensitive relations of individuals. Protecting edge privacy in triangle counts collection is a challenging problem due to the strong correlations among data from different clients. Decentralized Differential Privacy (DDP), as a possible option, protects edge privacy on correlated data to some extent. However, DDP provides a weak privacy guarantee by only hiding one edge in global. Unlike DDP, Local Differential Privacy (LDP) is a widely adopted standard for data collection which hides multiple data points in global at a time. But the LDP notion does not consider data correlations. With the understanding of these limitations, we introduce Edge Relationship Local Differential Privacy (Edge-RLDP), which provides a strong privacy guarantee as LDP and considers data correlations simultaneously. Based on Edge-RLDP, a baseline framework for triangle counts collection is proposed, as well as an improved two-phase framework, which strikes a better balance between privacy and data utility. Our improved framework fully utilizes the privacy budget by asking each client to only report the count of randomly sampled triangles after measuring the global data correlation. Theoretically, we rigorously prove that our framework satisfies ($\varepsilon, \delta$) -Edge-RLDP. Experimentally, we demonstrate our framework outperforms the state-of-art methods in terms of triangle count accuracy under a stricter privacy definition.

The accuracy of selectivity estimation is of vital importance to create good query plans in database management systems. We propose MOSE, a learning-based MOnotonic Selectivity Estimator, to provide accurate, reliable, and efficient selectivity estimation for query optimization.

Partial label learning (PLL) is to learn a discriminative model under incomplete supervision, where each instance is annotated with a candidate label set. The basic principle of PLL is that the unknown correct label y of an instance x resides in its candidate label set s, i.e., P(y ∈ s | x) = 1. On which basis, current researches either directly model P(x | y) under different data generation assumptions or propose various surrogate multiclass losses, which all aim to encourage the model-based Pθ(y ∈ s | x)→1 implicitly. In this work, instead, we explicitly construct a binary classification task toward P(y ∈ s | x) based on the discriminative model, that is to predict whether the model-output label of x is one of its candidate labels. We formulate a novel risk estimator with estimation error bound for the proposed PLL binary classification risk. By applying logit adjustment based on disambiguation strategy, the practical approach directly maximizes Pθ(y ∈ s | x) while implicitly disambiguating the correct one from candidate labels simultaneously. Thorough experiments validate that the proposed approach achieves competitive performance against the state-of-the-art PLL methods.

Query optimization is crucial for the query performance of database systems. Despite decades of efforts from both research and industrial communities, query optimization remains one of the most challenging problems. Thanks to the advances in artificial intelligence, data-driven and learning-based techniques are seeing traction in database research recently. However, most former learning-based works perform less practical because they are evasive about the interaction between learning components and database systems.

We study the problem of supervised contrastive (SupCon) learning on graphs. The SupCon loss has been recently proposed for classification tasks by pulling data points in the same class closer than those of different classes. However, it could be difficult for SupCon to handle datasets with large intra-class variances and high inter-class similarities. This issue is also challenging when it couples with graph structures. To address this, we present the cluster-aware supervised contrastive learning loss (ClusterSCL1) for graph learning tasks. The main idea of ClusterSCL is to retain the structural and attribute properties of a graph in the form of nodes’ cluster distributions during supervised contrastive learning. Specifically, ClusterSCL introduces the strategy of cluster-aware data augmentation and integrates it with the SupCon loss. Extensive experiments on several widely adopted graph benchmarks demonstrate the superiority of ClusterSCL over the cross-entropy, SupCon, and other graph contrastive objectives.

With the increasing popularity of location-based services (LBS), data outsourcing toward clouds is an emerging paradigm for ease of data management by LBS providers. Geometric range queries are one of the fundamental search functions in LBS, which are to find points inside geometric areas (e.g., circles or polygons). To ensure data confidentiality, the service users tend to encrypt the data before outsourcing it. However, regarding encrypted data, only a few consider geometric range queries, where the rationale is the high-dimension calculations make these queries particularly harder. In this paper, we propose a novel scheme for geometric range queries, that can provide the privacy of data stored at a cloud server and queries. Our scheme supports querying encrypted spatial data with irregular-shaped areas, achieves fast searches and enables dynamic updates. Experimental results over real-world spatial datasets demonstrate that our scheme results in fewer communication rounds and can speed up the search time 4× compared to state-of-the-art schemes, without carrying any potentially visible leakage in the structure.

As an important branch in Recommender System, occasional group recommendation has received more and more attention. In this scenario, each occasional group (cold-start group) has no or few historical interacted items. As each occasional group has extremely sparse interactions with items, traditional group recommendation methods can not learn high-quality group representations. The recent proposed Graph Neural Networks (GNNs), which incorporate the high-order neighbors of the target occasional group, can alleviate the above problem in some extent. However, these GNNs still can not explicitly strengthen the embedding quality of the high-order neighbors with few interactions. Motivated by the self-supervised learning technique, which is able to find the correlations within the data itself, we propose a self-supervised graph learning framework, which takes the user/item/group embedding reconstruction as the pretext task to enhance the embeddings of the cold-start users/items/groups. To explicitly enhance the high-order cold-start neighbors' embedding quality, we further introduce an embedding enhancer, which leverages the self-attention mechanism to improve the embedding quality for them. Comprehensive experiments show the advantages of our proposed framework than the state-of-the-art methods.

Name disambiguation is a key and also a very tough problem in many online systems such as social search and academic search. Despite considerable research, a critical issue that has not been systematically studied isdisambiguation on the fly— to complete the disambiguation in the real-time. This is very challenging, as the disambiguation algorithm must be accurate, efficient, and error tolerance. In this paper, we propose a novel framework — CONNA — to train a matching component and a decision component jointly via reinforcement learning. The matching component is responsible for finding the top matched candidate for the given paper, and the decision component is responsible for deciding on assigning the top matched person or creating a new person. The two components are intertwined and can be bootstrapped via jointly training. Empirically, we evaluate CONNA on two name disambiguation datasets. Experimental results show that the proposed framework can achieve a 1.21-19.84 percent improvement on F1-score using joint training of the matching and the decision components. The proposed CONNA has been successfully deployed on AMiner — a large online academic search system.

Active learning (AL) is successful based on the assumption that labeled and unlabeled data are obtained from the same class distribution. However, its performance deteriorates under class distribution mismatch, wherein the un-labeled data contain many samples out of the class distribution of labeled data. To effectively handle the problems under class distribution mismatch, we propose a contrastive coding based AL framework named CCAL. Unlike the existing AL methods that focus on selecting the most informative samples for annotating, CCAL extracts both semantic and distinctive features by contrastive learning and combines them in a query strategy to choose the most informative un-labeled samples with matched categories. Theoretically, we prove that the AL error of CCAL has a tight upper bound. Experimentally, we evaluate its performance on CIFAR10, CIFAR100, and an artificial cross-dataset that consists of five datasets; consequently, CCAL achieves state-of-the-art performance by a large margin with remarkably lower annotation cost. To the best of our knowledge, CCAL is the first work related to AL for class distribution mismatch.

Deep Convolutional Neural Networks (CNNs) are increasingly used in multimedia retrieval, and accelerating Deep CNNs has recently received an ever-increasing research focus. Among various approaches proposed in the literature, filter pruning has been regarded as a promising solution, which is due to its advantage in significant speedup and memory reduction of both network model and intermediate feature maps. Many works have been proposed to find unimportant filters, and then prune it for accelerating Deep CNNs. However, they mainly focus on using heuristic methods to evaluate the importance of filters, such as the statistical information of filters (e.g., prune filter with small $\ell_2$-norm), which may be not perfect. In this paper, we propose a novel filter pruning method, namely A Unified-Model via Block Coordinate Descent for Learning the Importance of Filter (U-BCD). The importance of the filters in our U-BCD is learned by optimizing method. We can simultaneously learn the filter parameters and the importance of filters by block coordinate descent method. When applied to two image classification benchmarks, the effectiveness of our U-BCD is validated. Notably, on CIFAR-10, our U-BCD reduces more than 57% FLOPs on ResNet-110 with even 0.08% relative accuracy improvement, and also achieve state-of-the-art results on ILSVRC-2012.

GNN-based anomaly detection has recently attracted considerable attention. Existing attempts have thus far focused on jointly learning the node representations and the classifier for detecting the anomalies. Inspired by the recent advances of self-supervised learning (SSL) on graphs, we explore another possibility of decoupling the node representation learning and the classification for anomaly detection. We conduct a preliminary study to show that decoupled training using existing graph SSL schemes to represent nodes can obtain performance gains over joint training, but it may deteriorate when the behavior patterns and the label semantics become highly inconsistent. To be less biased by the inconsistency, we propose a simple yet effective graph SSL scheme, called Deep Cluster Infomax (DCI) for node representation learning, which captures the intrinsic graph properties in more concentrated feature spaces by clustering the entire graph into multiple parts. We conduct extensive experiments on four real-world datasets for anomaly detection. The results demonstrate that decoupled training equipped with a proper SSL scheme can outperform joint training in AUC. Compared with existing graph SSL schemes, DCI can help decoupled training gain more improvements.

Cold-start problem is a fundamental challenge for recommendation tasks. Despite the recent advances on Graph Neural Networks (GNNs) incorporate the high-order collaborative signal to alleviate the problem, the embeddings of the cold-start users and items aren't explicitly optimized, and the cold-start neighbors are not dealt with during the graph convolution in GNNs. This paper proposes to pre-train a GNN model before applying it for recommendation. Unlike the goal of recommendation, the pre-training GNN simulates the cold-start scenarios from the users/items with sufficient interactions and takes the embedding reconstruction as the pretext task, such that it can directly improve the embedding quality and can be easily adapted to the new cold-start users/items. To further reduce the impact from the cold-start neighbors, we incorporate a self-attention-based meta aggregator to enhance the aggregation ability of each graph convolution step, and an adaptive neighbor sampler to select the effective neighbors according to the feedbacks from the pre-training GNN model. Experiments on three public recommendation datasets show the superiority of our pre-training GNN model against the original GNN models on user/item embedding inference and the recommendation task.

Accelerating Deep Convolutional Neural Networks(CNNs) has recently received ever-increasing research focus. Among various approaches proposed in the literature, filter pruning has been regarded as a promising solution, which is due to its advantage in significant speedup and memory reduction of both network model and intermediate feature maps. Previous works utilized "smaller-norm-less-important" criterion to prune filters with smaller lp-norm values by pruning and retraining alternately. However, they ignore the effects of $feedback: most current approaches that prune filters only consider the statistics of the filters (e.g., prune filter with small lp-norm values), without considering the performance of the pruned model as an important feedback signal in the next iteration of filter pruning. To solve the problem of non-feedback, we propose a novel filter pruning method, namely Filter Pruning via Probabilistic Model-based Optimization (FPPMO). FPPMO solves the problem of non-feedback by pruning filters in a probabilistic manner. We introduce a pruning probability for each filter, and pruning is guided by sampling from the pruning probability distribution. An optimization method is proposed to update the pruning probability based on the performance of the pruned model in the pruning process. When applied to two image classification benchmarks, the effectiveness of our FPPMO is validated. Notably, on CIFAR-10, our FPPMO reduces more than 57% FLOPs on ResNet-110 with even 0.08% relative accuracy improvement. Moreover, on ILSVRC-2012, our FPPMO reduces more than 50% FLOPs on ResNet-101 without top-5 accuracy drop. Which proving that our FPPMO outperforms the state-of-the-art filter pruning method.

Rule-based classifier, that extract a subset of induced rules to efficiently learn/mine while preserving the discernibility information, plays a crucial role in human-explainable artificial intelligence. However, in this era of big data, rule induction on the whole datasets is computationally intensive. So far, to the best of our knowledge, no known method focusing on accelerating rule induction has been reported. This is the first study to consider the acceleration technique to reduce the scale of computation in rule induction. We propose an accelerator for rule induction based on fuzzy rough theory; the accelerator can avoid redundant computation and accelerate the building of a rule classifier. First, a rule induction method based on consistence degree, called consistence-based value reduction (CVR), is proposed and used as basis to accelerate. Second, we introduce a compacted search space termed key set, which only contains the key instances required to update the induced rule, to conduct value reduction. The monotonicity of key set ensures the feasibility of our accelerator. Third, a rule-induction accelerator is designed based on key set, and it is theoretically guaranteed to display the same results as the unaccelerated version. Specifically, the rank preservation property of key set ensures consistency between the rule induction achieved by the accelerator and the unaccelerated method. Finally, extensive experiments demonstrate that the proposed accelerator can perform remarkably faster than the unaccelerated rule-based classifier methods, especially on datasets with numerous instances.

Group k-nearest neighbor (kGNN) search allows a group of n mobile users to jointly retrieve k points from a location-based service provider (LSP) that minimizes the aggregate distance to them. We identify four protection objectives in the privacy preserving kGNN search: (i) every user's location should be protected from LSP; (ii) the group's query and the query answer should be protected from LSP; (iii) LSP's private database information should be protected from users; (iv) every user's location should be protected from other users in the group. We design two privacy preserving solutions under two types of threat model to the privacy preserving kGNN search in the full user collusion environment, where any n - 1 users in the group may collude to infer the location of the remaining user. Our solutions do not rely on heavy pre-computation on LSP like previous works. Though we consider kGNN, the proposed privacy preserving solutions can be easily adopted to any group query as it treats the query answering (i.e., kGNN) as a black box. Theoretical and experimental analysis suggest that our solutions are highly efficient in both communication cost and user computational cost while incurring some reasonable overhead on LSP.

Knowledge graph alignment aims to link equivalent entities across different knowledge graphs. To utilize both the graph structures and the side information such as name, description and attributes, most of the works propagate the side information especially names through linked entities by graph neural networks. However, due to the heterogeneity of different knowledge graphs, the alignment accuracy will be suffered from aggregating different neighbors. This work presents an interaction model to only leverage the side information. Instead of aggregating neighbors, we compute the interactions between neighbors which can capture fine-grained matches of neighbors. Similarly, the interactions of attributes are also modeled. Experimental results show that our model significantly outperforms the best state-of-the-art methods by 1.9-9.7% in terms of HitRatio@1 on the dataset DBP15K.

Accelerating Deep Convolutional Neural Networks (CNNs) has recently received ever-increasing research focus. Among various approaches proposed in the literature, filter pruning has been regarded as a promising solution, which is due to its advantage in significant speedup and memory reduction of both network model and intermediate feature maps. Previous works utilized "smaller-norm-less-important" criterion to prune filters with smaller ࡁp-norm values by pruning and retraining alternately. This trends to narrow the model capacity for the following reasons: (1) Violent pruning. Previous works adopt a violent strategy in which all filters are simultaneously pruned, which leaving the room to retain model accuracy limited. (2) Filter degradation. Previous works simply set the pruned filter to 0 and retrained it alterately, which easily led to the loss of learning ability of filters. To solve this problem, we propose a novel filter pruning method, namely Incremental Filter Pruning via Random Walk (IFPRW). IFPRW solves the problem of violent pruning by incremental method and Filter degradation by means of random walk. When applied to two image classification benchmarks, the usefulness and strength of IFPRW is validated. Notably, on CIFAR-10, IFPRW reduces more than 46% FLOPs on ResNet-110 with even 0.28% relative accuracy improvement. Moreover, on ILSVRC-2012, IFPRW reduces more than 54% FLOPs on ResNet-101 with only 0.7% top-5 accurcacy drop. which proving that IFPRW outperforms the state-of-the-art filter pruning methods.

We propose a ranking framework, called PatternRank+NN, for expanding a set of seed entities of a particular class (i.e., entity set expansion) from Web search queries. PatternRank+NN consists of two parts: PatternRank and NN. Unlike the traditional methods, PatternRank brings user behaviors into entity set expansion from Web search queries. PatternRank is a Markov chain which simulates the Web search query process of users on the graph model for Web search query log, and ranks the features of the class. The features in the front rank are used to generate candidate entities of the class. NN, a ranking strategy called Nearest Neighbor, ranks these candidate entities such that the set of seed entities can be expanded from the candidate entities in the front rank. Our experiments demonstrate the superior performance of PatternRank+NN in comparison with the state-of-the-art methods.

The proliferation of massive open online courses (MOOCs) demands an effective way of personalized course recommendation. The recent attention-based recommendation models can distinguish the effects of different historical courses when recommending different target courses. However, when a user has interests in many different courses, the attention mechanism will perform poorly as the effects of the contributing courses are diluted by diverse historical courses. To address such a challenge, we propose a hierarchical reinforcement learning algorithm to revise the user profiles and tune the course recommendation model on the revised profiles.Systematically, we evaluate the proposed model on a real dataset consisting of 1,302 courses, 82,535 users and 458,454 user enrolled behaviors, which were collected from XuetangX—one of the largest MOOCs in China. Experimental results show that the proposed model significantly outperforms the state-of-the-art recommendation models (improving 5.02% to 18.95% in terms of HR@10).

Data release, such as statistics of data distribution, in many data analysis and machine learning tasks is needed, which poses significant risks of user's privacy. Usually, to preserve privacy of every individual, frequency estimation based on LDP (Local Differential Privacy) is used to replace the real distribution of data. Unfortunately, when an individual sends values multiple times, privacy leakage, i.e., same value problems may occur, along with other performance problems such as memory usage problem. To narrow these gaps, SAnonLDP (Sample Anonymous Local Differential Privacy) is proposed in this paper. We build the SAnonLDP framework by integrating k-anonymous into LDP, which includes four blocks: random grouping; anonymous and Walsh-Fourier transforms; random response; singular value decomposition (SVD). Among them, the second block 'Anonymous and Walsh-Fourier transforms' significantly decreases the communication cost and the memory requirements. The left blocks make up for the loss of information to achieve an acceptable frequency estimation. More important, we verify that this estimation is unbiased by the strict mathematical reasoning. Finally, the numerical experiments demonstrate that SAnonLAP achieves better KL-divergence and estimation error compared to another known privacy model: RAPPOR.

In data management systems, query processing on GPUs or distributed clusters have proven to be an effective method for high efficiency. However, the high PCIe data transfer overhead between CPUs and GPUs, and the communication cost between nodes in distributed systems are usually bottleneck for improving system performance. Recently, GPUDirect RDMA has been developed and has received a lot of attention. It contains the features of the RDMA and GPUDirect technologies, which provides new opportunities for optimizing query processing.

As the location-based applications are flourishing, we will witness soon a prodigious amount of spatial data will be stored in the public cloud with the geometric range query as one of the most fundamental search functions. The rising demand of outsourced data is moving larger-scale datasets and wider-scope query size. To protect the confidentiality of the geographic information of individuals, the outsourced data stored at the cloud server should be preserved especially when they are queried. While the problem of secure range query on outsourced encrypted data has been extensively studied, the current schemes are far from the practice in terms of efficiency and scalability. In this paper, we propose a novel solution based on Geohash and predicate symmetric searchable encryption for secure range queries named as MixGeo. We present a multi-level indexes structure tailored for efficient and large-scale spatial data lookup in the cloud server while preserving data privacy.

Aligning users across multiple heterogeneous social networks is a fundamental issue in many data mining applications. Methods that incorporate user attributes and network structure have received much attention. However, most of them suffer from error propagation or the noise from diverse neighbors in the network. To effectively model the influence from neighbors, we propose a graph neural network to directly represent the ego networks of two users to be aligned into an embedding, based on which we predict the alignment label. Three major mechanisms in the model are designed to unitedly represent different attributes, distinguish different neighbors and capture the structure information of the ego networks respectively.

With the advancement of sensor electronic devices, wireless sensor networks have attracted more and more attention. Range query has become a significant part of sensor networks due to its availability and convenience. However, It is challenging to process range query while still protecting sensitive data from disclosure. Existing work mainly focuses on privacy- preserving range query, but neglects the damage of collusion attacks, probability attacks and differential attacks. In this paper, we propose a privacy- preserving, energy-efficient and multi-dimensional range query protocol called PERQ, which not only achieves data privacy, but also considers collusion attacks, probability attacks and differential attacks. Generalized distance-based and modular arithmetic range query mechanism are used. In addition, a novel cyclic modular verification scheme is proposed to verify the data integrity. Extensive theoretical analysis and experimental results confirm the high performance of PERQ in terms of energy efficiency, security and accountability requirements.

Mobile crowd sensing has the potential to acquire massive data from places and address large-scale societal problems. However, most currently existing crowd sensing systems suffer from insufficient participants. Therefore, incentive design for crowd sensing is essential and urgent. In this paper, different from the auction-based and server-dominant incentives, we design a personalized incentive, PIE, with partiality for neither the server nor the participants with budget constraint. The total payment for all the participants accords to their collective participation level, and the individual reward for each participant depends on individual contribution. We measure the individual contribution and participation level based on Voronoi diagram and Shannon entropy. Both offline and online incentives are proposed with budget constraint. Experimental study shows that our incentives are participation-aware and contribution-dependent, which encourages participants' active join, balanced distribution and flexible reward.

Crowdsourcing proves a viable approach to solve certain large-scale problems by posting tasks distributively to humans and harnessing their knowledge to get results effectively and efficiently. Unfortunately, crowdsourcing suffers from lack of available participants with domain knowledge or skills. In this paper, we propose potential wise crowd (i.e., a crowd with similarity and diversity in domain knowledge) find from million grassroots in social networks. We design and implement a distant-supervision framework to find potential crowdsourcers from existing social networks. A knowledge graph is used to assess the domain knowledge in terms of similarity and diversity. The wise crowd formation is a NP-hard problem and we propose greedy algorithms to approach it. Experimental results show the performance of our framework and algorithms in aspects of effectiveness and efficiency.

Context plays an important role in helping users to make decisions. There are hierarchical structure between contexts and aggregation characteristics within the context in real scenarios. Exist works mainly focus on exploring the explicit hierarchy between contexts, while ignoring the aggregation characteristics within the context. In this work, we explore both of them so as to improve accuracy of prediction in recommender systems. We propose a Random Partition Factorization Machines (RPFM) by adopting random decision trees to split the contexts hierarchically to better capture the local complex interplay. The intuition here is that local homogeneous contexts tend to generate similar ratings. During prediction, our method goes through from the root to the leaves and borrows from predictions at higher level when there is sparseness at lower level. Other than estimation accuracy of ratings, RPFM also reduces the over-fitting by building an ensemble model on multiple decision trees. We test RPFM over three different benchmark contextual datasets. Experimental results demonstrate that RPFM outperforms state-of-the-art context-aware recommendation methods.

Recently, listwise ranking-oriented collaborative filtering (CF) algorithms have gained great success in recommender systems. However, the ranked preference list may compromise the privacy of individuals. A notable paradigm for offering strong privacy guarantee is differential privacy. In this paper, we propose DPListCF, a differentially private algorithm based on ListCF (a state-of-art listwise CF algorithm). The main idea of DPListCF is to make both of the similarity calculation phase and rank prediction phase of ListCF satisfy differential privacy, by using input perturbation method and output perturbation method in the two phases respectively. Extensive experiments using two real datasets evaluate the performance of DPListCF, and demonstrate that the proposed algorithm outperforms state-of-art approaches.

Density estimation can construct an estimate of the probability density function from the observed data. However, such a function may compromise the privacy of individuals. A notable paradigm for offering strong privacy guarantees in data analysis is differential privacy. In this paper, we propose DPGMM, a parametric density estimation algorithm using Gaussian mixtures model (GMM) under differential privacy. GMM is a well-known model that could approximate any distribution and can be solved via Expectation-Maximization (EM) algorithm. The main idea of DPGMM is to add two extra steps after getting the estimated parameters in the M step of each iteration. The first step is the noise adding step, which injects calibrated noise to the estimated parameters according to their L1-sensitivities and privacy budgets. The second step is the post-processing step, which post-processes those noisy parameters that might break their intrinsic characteristics. Extensive experiments using both real and synthetic datasets evaluate the performance of DPGMM, and demonstrate that the proposed method outperforms a state-of-art approach.

Mobile devices have become more and more powerful with lots of embedded sensors providing sensibility of various data, which makes crowd sensing a compelling paradigm followed by emerging applications. In this paper, we design a crowd based incentive mechanism to stimulate participants joining sensing campaigns with consideration of location privacy. In our incentive, MagiCrowd, we creatively cluster the participants as several atomic crowds to bargain with the crowd sensing campaigner. We propose K-least to cluster the participants and achieve K-anonymity location privacy. Negotiated Bargain Theory is introduced to determine the incentive payoffs and Penalty Allocation is designed to allocate the gross crowd rewards. MagiCrowd can achieve high participation rate, rational reward and location privacy. We discuss the proposed incentive in depth and conduct thorough experiments to evaluate the desirable properties.

It is popular for most people to read news online since the web sites can provide access to news articles from millions of sources around the world. For these news web sites, the key challenge is to help users find related news articles to read. In this paper, we present a system called CROWN (Context-aware RecOmmender for Web News) to do Chinese news recommendation. By recommendation, the system can retrieve personalized fresh and relevant news articles to mobile users according to their particular context. Differing from existing mobile news applications which employ rather simple strategies for news recommendation, CROWN integrates the contextual information in prediction by modeling the data as a tensor. Such context information usually includes the time, the location, etc. This demo paper presents the implementation of the whole procedure of news recommendation in the system of CROWN. Experimental results on a large corpus of newly-published Chinese web news show its performance is satisfactory.

With the increasing proliferation of the Mobile Social Networks (MSN) and the Location Based Service (LBS), location privacy has attracted broad attention in recent years. Most researches have been done with the assumption that the server is untrusted and a trusted third party is introduced to protect the user location privacy when a user sends queries for the location service. In this paper, we reconsider this assumption and propose a Personalized and Flexible location privacy protection Model (PFM) based on user relationship strength. We conduct researches in the situation that the server is trusted while malicious users in the MSN can disguise as a friend to break location privacy. We present an entropic TF-IDF based approach to measure the bi-directional relationship strength and propose probability distribution based cloaking model to protect user location privacy. We thoroughly evaluate our methods based on Quality of Privacy (QoP) via real and synthetic data.

With high expansibility and efficient power usage, tiered wireless sensor networks are widely deployed in many fields as an important part of Internet of Things (IoTs). It is challenging to process range query while protecting sensitive data from adversaries. Moreover, most existing work focuses on privacy-preserving range query neglecting collusion attacks and probability attacks, which are more threatening to network security. In this paper, we first propose a secure range query protocol called secRQ, which not only protects data privacy, but also resists collusion attacks and probability attacks in tiered wireless sensor networks. Generalized inverse matrices and distance-based range query mechanism are used to guarantee security as well as high efficiency and accuracy. Besides, we propose the mutual verification scheme to verify the integrity of query results. Finally, both theoretical analysis and experimental results confirm the security, efficiency and accuracy of secRQ.

Currently, most robust classifiers with parameters focus on the determination of the optimal or suboptimal parameters. There are no research studies or even discussions about robust classifiers on all of the possible parameters. This paper considers the robust rough classifier and finds that the robust rough classifier satisfies a nested topological structure; then, the nested classifier, which reflects the classifier on all of the possible parameters, is proposed. First, some notions, such as the robust discernibility vector, the robust value reduct, and the robust covering vector, are proposed; these notions can reflect the classical corresponding notions on all of the possible parameters. It is more important that these notions share a common characteristic: the nested structure. The nested structure of these notions makes nested classifier theoretically possible. Furthermore, some novel algorithms are designed to compute the robust value reduct, the robust covering degree, and the robust classifier. These algorithms make the nested classifier technologically possible. Finally, numerical experiments demonstrate that the nested classifier is effective and efficient for classification and predication.

Wireless sensor network is an important part of the Internet of Things. Preservation of privacy and integrity in wireless sensor networks is extremely urgent and challenging. To address this problem, we propose in this paper an efficient and secure range query protocol in two-tiered wireless sensor networks introducing master nodes. Our proposal not only prevents adversaries from gaining sensitive information of both queries issued by users and data collected by sensor nodes but also allows the sink to verify whether results are valid. It offers confidentiality of queries and data by constructing a special code, provides integrity verification by the correlation among data and also enables efficient query processing. Finally, theoretical analysis and simulation results confirm the security and efficiency of our proposal.

Currently most robust fuzzy rough classifiers with parameters focus on the robustness and less-sensitiveness to noise. No work studies or even discusses about the topological structure of robust fuzzy rough classifiers. This paper finds that the robust rough classifier satisfies a nested topological structure, and then NESTED CLASSIFIER, which reflects the classifier on different parameters, is proposed. First some notions, such as robust discernibility vector, robust value reduct and robust covering vector, are proposed which share the common characteristic: the nested structure. The nested structure of these notions makes the nested classifier theoretically possible. Furthermore, some novel algorithms are designed to compute robust value reduct, robust covering degree and robust classifier. These algorithms make the nested classifier technologically possible. Finally numerical experiments demonstrate that the nested classifier is more efficient than the existing ones.

This paper proposes a robust method of dimension reduction using fuzzy rough sets, in which the reduction results can reflect the reducts obtained on all of the possible parameters. Here, the reducts being obtained on all of the possible parameters mean that all of the reducts are obtained on different degrees of robustness to handle noise. This method is completely different from the existing methods of fuzzy rough reduction. The differences are shown in three aspects: the concept, the tool, and the algorithm. First, the key concept of attribute reduction is redefined in a new way. That is, the robust fuzzy rough reduct, which is shortened to a robust reduct, is proposed to reflect the classical reducts obtained on all of the possible parameters. The new “robust reduct” is not a crisp subset of condition attributes; rather, it is a fuzzy subset, whose most interesting property is that any cut set of the robust reduct is a classical reduct on a certain parameter. Second, the tool used to measure the discernibility power is different from the existing discernibility measures. In this paper, the robustness of each attribute to handle misclassification and perturbation is considered. By considering both the robustness and the discernibility, a robust fuzzy discernibility matrix is designed. Finally, the algorithms used to find the robust reducts are designed based upon the robust fuzzy discernibility matrix, which is completely different from the existing algorithms used to find the classical reducts.

Recently there has been a lot of interest in graph-based analysis. One of the most important aspects of graph-based analysis is to measure similarity between nodes and to do similarity search in a graph. For example, in social networks such as Facebook, system may want to recommend potential friends to a particular user based on connections between users. In custom-product networks such as eBay, one may wish to recommend products to others based on purchases history. In this talk, I will introduce some methods on vertex similarities computations and their applications on similarity search in real world networks.

We study the problem of question topic classification using a very large real‐worldCommunityQuestionAnswering (CQA) dataset fromYahoo!Answers. The dataset comprises 3.9 million questions and these questions are organized into more than 1,000 categories in a hierarchy. To the best knowledge, this is the first systematic evaluation of the performance of different classification methods on question topic classification as well as short texts. Specifically, we empirically evaluate the following in classifying questions intoCQAcategories: (a) the usefulness of n‐gram features and bag‐of‐word features; (b) the performance of three standard classification algorithms (naive Bayes, maximum entropy, and support vector machines); (c) the performance of the state‐of‐the‐art hierarchical classification algorithms; (d) the effect of training data size on performance; and (e) the effectiveness of the different components ofCQAdata, including subject, content, asker, and the best answer. The experimental results show what aspects are important for question topic classification in terms of both effectiveness and efficiency. We believe that the experimental findings from this study will be useful in real‐world classification problems.

Recently there has been a lot of interest in graph-based analysis. One of the most important aspects of graph-based analysis is to measure similarity between nodes in a graph. SimRank is a simple and influential measure of this kind, based on a solid graph theoretical model. However, existing methods on SimRank computation suffer from two limitations: 1) the computing cost can be very high in practice; and 2) they can only be applied on static graphs. In this paper, we exploit the inherent parallelism and high memory bandwidth of graphics processing units (GPU) to accelerate the computation of SimRank on large graphs. Furthermore, based on the observation that SimRank is essentially a first-order Markov Chain, we propose to utilize the iterative aggregation techniques for uncoupling Markov chains to compute SimRank scores in parallel for large graphs. The iterative aggregation method can be applied on dynamic graphs. Moreover, it can handle not only the link-updating problem but also the node-updating problem. We give the corresponding theoretical justification and analysis, propose three optimization strategies to further improve the computation efficiency, and extend the proposed algorithm to dynamic graphs. Extensive experiments on synthetic and real data sets verify that the proposed methods are efficient and effective.

Information networks are ubiquitous in many applications and analysis on such networks has attracted significant attention in the academic communities. One of the most important aspects of information network analysis is to measure similarity between nodes in a network. SimRank is a simple and influential measure of this kind, based on a solid theoretical "random surfer" model. Existing work computes SimRank similarity scores in an iterative mode. We argue that the iterative method can be infeasible and inefficient when, as in many real-world scenarios, the networks change dynamically and frequently. We envision non-iterative method to bridge the gap. It allows users not only to update the similarity scores incrementally, but also to derive similarity scores for an arbitrary subset of nodes. To enable the non-iterative computation, we propose to rewrite the SimRank equation into a non-iterative form by using the Kronecker product and vectorization operators. Based on this, we develop a family of novel approximate SimRank computation algorithms for static and dynamic information networks, and give their corresponding theoretical justification and analysis. The non-iterative method supports efficient processing of various node analysis including similarity tracking and centrality tracking on evolving information networks. The effectiveness and efficiency of our proposed methods are evaluated on synthetic and real data sets.

This paper addresses a fundamental and challenging problem with broad applications: efficient processing of region-based promotion queries, i.e., to discover the top-k most interesting regions for effective promotion of an object (e.g., a product or a person) given by user, where a region is defined over continuous ranged dimensions. In our problem context, the object can be promoted in a region when it is top-ranked in it. Such type of promotion queries involves an exponentially large search space and expensive aggregation operations. For efficient query processing, we study a fresh, principled framework called region-based promotion cube (RepCube). Grounded on a solid cost analysis, we first develop a partial materialization strategy to yield the provably maximum online pruning power given a storage budget. Then, cell relaxation is performed to further reduce the storage space while ensuring the effectiveness of pruning using a given bound. Extensive experiments conducted on large data sets show that our proposed method is highly practical, and its efficiency is one to two orders of magnitude higher than baseline solutions.

Recently there has been a lot of interest in graph-based analysis. One of the most important aspects of graph-based analysis is to measure similarity between nodes in a graph. SimRank is a simple and influential measure of this kind, based on a solid graph theoretical model. However, existing methods on SimRank computation suffer from two limitations: 1) the computing cost can be very high in practice; and 2) they can only be applied on static graphs. In this paper, we exploit the inherent parallelism and high memory bandwidth of graphics processing units (GPU) to accelerate the computation of SimRank on large graphs. Furthermore, based on the observation that SimRank is essentially a first-order Markov Chain, we propose to utilize the iterative aggregation techniques for uncoupling Markov chains to compute SimRank scores in parallel for large graphs. The iterative aggregation method can be applied on dynamic graphs. Moreover, it can handle not only the link-updating problem but also the node-updating problem. Extensive experiments on synthetic and real data sets verify that the proposed methods are efficient and effective.

Recently there have been growing interests in the applications of wireless sensor networks. Given a query point, which is a value, find a set of K nodes whose values are nearest to this point. We call this query the value-based KNN (v-KNN) query. v-KNN is a challenging query in wireless sensor networks because the network is highly distributed and global knowledge of the values are needed before the result set could be constructed. In this paper, we propose a new algorithm called KVC (v-KNN queries based on value clustering ) to process the v-KNN queries in wireless sensor networks in an energy efficient way. KVC takes advantage of the rich resources in the base station to do some optimizations to filter the irrelevant nodes and push down the v-KNN query into the network. The aim of KVC is to reduce the total communication cost as much as possible while processing the v-KNN queries correctly and efficiently. Simulation results on both realistic and synthetical data sets show that KVC outperforms the central processing in both average and hotspot energy consumption in wireless sensor networks.

The concept of dominance has recently attracted much interest in the context of skyline computation. Given an N-dimensional data set S, a point p is said to dominate q if p is better than q in at least one dimension and equal to or better than it in the remaining dimensions. In this paper, we propose extending the concept of dominance for business analysis from a microeconomic perspective. More specifically, we propose a new form of analysis, called Dominant Relationship Analysis (DRA), which aims to provide insight into the dominant relationships between products and potential buyers. By analyzing such relationships, companies can position their products more effectively while remaining profitable.To support DRA, we propose a novel data cube called DADA (Data Cube for Dominant Relationship Analysis), which captures the dominant relationships between products and customers. Three types of queries called Dominant Relationship Queries (DRQs) are consequently proposed for analysis purposes: 1)Linear Optimization Queries (LOQ), 2)Subspace Analysis Queries (SAQ), and 3)Comparative Dominant Queries (CDQ). Algorithms are designed for efficient computation of DADA and answering the DRQs using DADA. Results of our comprehensive experiments show the effectiveness and efficiency of DADA and its associated query processing strategies.

Data cube pre-computation is an important concept for supporting OLAP(Online Analytical Processing) and has been studied extensively. It is often not feasible to compute a complete data cube due to the huge storage requirement. Recently proposed quotient cube addressed this issue through a partitioning method that groups cube cells into equivalence partitions. Such an approach is not only useful for distributive aggregate functions such as SUM but can also be applied to the holistic aggregate functions like MEDIAN.Maintaining a data cube for holistic aggregation is a hard problem since its difficulty lies in the fact that history tuple values must be kept in order to compute the new aggregate when tuples are inserted or deleted. The quotient cube makes the problem harder since we also need to maintain the equivalence classes. In this paper, we introduce two techniques called addset data structure and sliding window to deal with this problem. We develop efficient algorithms for maintaining a quotient cube with holistic aggregation functions that takes up reasonably small storage space. Performance study shows that our algorithms are effective, efficient and scalable over large databases.