Local differential privacy (LDP) techniques obviate the need for trust in the data collector, as they provide robust privacy guarantees against untrusted data managers while simultaneously preserving the accuracy of statistical information derived from the privatized data. As a result, these methods have garnered considerable interest and research efforts. In particular,$(\varepsilon,\delta)$-LDP schemes have been utilized across a range of statistical tasks. Nonetheless, existing$(\varepsilon,\delta)$-LDP mechanisms for mean estimation suffer from challenges such as elevated estimation errors and diminished data utility. To address this problem, we propose two novel$(\varepsilon,\delta)$-LDP algorithms for mean estimation. Specifically, we design a one-dimensional piecewise mean estimation algorithm, which perturbs the input data into intervals, thereby reducing noise addition and enhancing both accuracy and efficiency. Building on this foundation, we extend our approach to multi-dimensional data, resulting in a multi-dimensional piecewise mean estimation algorithm. Furthermore, we conduct a theoretical analysis to derive both the variance and error bounds for the proposed algorithms. Extensive experiments conducted on real datasets demonstrate the high practicality of our algorithms for data statistical tasks, showing significant improvements in data utility.

Taxonomies describe the definitions of entities, entities' attributes and the relations among the entities, and thus play an important role in building a knowledge graph. In this paper, we tackle the task of taxonomy entity translation, which is to translate the names of taxonomy entities in a source language to a target language. The translations then can be utilized to build a knowledge graph in the target language. Despite its importance, taxonomy entity translation remains a hard problem for AI models due to two major challenges. One challenge is understanding the semantic context in very short entity names. Another challenge is having deep understanding for the domain where the knowledge graph is built.

Recommender systems have to handle a highly non-stationary environment, due to users' fast changing interests over time. Traditional solutions have to periodically rebuild their models, despite high computational cost. But this still cannot empower them to automatically adjust to abrupt changes in trends caused by timely information. It is important to note that the changes of reward distributions caused by a non-stationary environment can also be context dependent. When the change is orthogonal to the given context, previously maintained models should be reused for better recommendation prediction.

There are various real-world applications such as video ads, airport screenings, courtroom trials, and job interviews where deception detection can play a crucial role. Hence, there are immense demands on deception detection in videos. However, videos are inherently complex; moreover, they lack detective labels in many real-world applications, which poses tremendous challenges to traditional deception detection methods. In this paper, we study the problem of deception detection in videos. In particular, we provide a principled way to capture rich information into a coherent model and propose an end-to-end framework DEV to detect DEceptive Videos automatically, which is robust to the small number of training data. Experimental results on real-world videos demonstrate the effectiveness of the proposed framework and further experiments are conducted to understand important factors of deception detection in videos.

The first International Workshop on Heterogeneous Networks Analysis and Mining is held in Los Angeles, California, USA on February 9th, 2018 and is co-located with the 11th ACM International Conference on Web Search and Data Mining. The goal of this workshop is to bring together computing researchers and practitioners to address challenges in the mining and analysis of real-world heterogeneous networks. This workshop has an exciting program that spans a number of subareas including: graph mining, learning from structured data, statistical relational learning, and network science in general. The program includes six invited speakers, lively discussion on emerging topics, and presentations of several original research papers.

Network embedding algorithms that map nodes in a network into a low-dimensional vector space are prevalent in recent years, due to their superior performance in many network-based tasks, such as clustering, classification, and link prediction. The main assumption of existing algorithms is that the learned latent representation for nodes should preserve the structure of the network, in terms of first-order or higher-order connectivity. In other words, nodes that are more similar will have higher probability to connect to each other. This phenomena is typically explained as homophily in network science. However, there is another factor usually neglected by the existing embedding algorithms, which is the popularity of a node. For example, celebrities in a social network usually receive numerous followers, which cannot be fully explained by the similarity of the two users. We denote this factor with the terminology "social rank»». We then propose a network embedding model that considers both of the two factors in link generation, and learn proximity-based embedding and social rank-based embedding separately. Rather than simply treating these two factors independent with each other, a carefully designed link generation model is proposed, which explicitly models the interdependency between these two types of embeddings. Experiments on several real-world datasets across different domains demonstrate the superiority of our novel network embedding model over the state-of-the-art methods.

There are users who generate significant amounts of domain knowledge in online forums or community question and answer (CQA) websites. Existing literature defines them as `experts.' These users attain such statuses by providing multiple relevant answers to the question askers. Past works have focused on recommending relevant posts to these users. With the rise of web forums where certified experts answer questions, strategies that are tailored towards addressing the new type of experts will be beneficial. In this paper, we identify a new type of user called `designated experts' (i.e., users designated as domain experts by the web administrators). These are the experts who are guaranteed by web administrators to be an expert in a given domain. Our focus is on how we can capture the unique behavior of designated experts in an online domain. We have noticed designated experts have different behaviors compared to CQA experts. In particular, unlike existing CQAs, only one designated expert responds to any given thread. To capture this intuition, we introduce a matrix factorization algorithm with regularization to capture the behavior. Our results show that the regularization method improves the performance significantly compared to the baseline approach.

Query auto-completion (QAC) facilitates faster user query input by predicting users' intended queries. Most QAC algorithms take a learning-based approach to incorporate various signals for query relevance prediction. However, such models are trained on simulat- ed user inputs from query log data. The lack of real user interaction data in the QAC process prevents them from further improving the QAC performance. In this work, for the first time we collect a high-resolution QAC query log that records every keystroke in a QAC session. Based on this data, we discover two user behaviors, namely the horizontal skipping bias and vertical position bias which are crucial for rele- vance prediction in QAC. In order to better explain them, we pro- pose a novel two-dimensional click model for modeling the QAC process with emphasis on these behaviors. Extensive experiments on our QAC data set from both PC and mobile devices demonstrate that our proposed model can accurate- ly explain the users' behaviors in interacting with a QAC system, and the resulting relevance model significant improves the QAC performance over existing click models. Furthermore, the learned knowledge about the skipping behavior can be effectively incorpo- rated into existing learning-based models to further improve their performance.

Among all web search queries there is an important subset of queries containing entity mentions. In these queries, it is observed that users are most interested in requesting some attribute of an entity, such as "Obama age" for the intent of age, which we refer to as the attribute intent. In this work we address the problem of identifying synonymous query intent templates for the attribute intent. For example, "how old is [Person]" and "[Person]'s age" are both synonymous templates for the age intent. Successful identification of the synonymous query intent templates not only can improve the performance of all existing query annotation approaches, but also could benefit applications such as instant answers and intent-based query suggestion. In this work we propose a clustering framework with multiple kernel functions to identify synonymous query intent templates for a set of canonical templates jointly. Furthermore, signals from multiple sources of information are integrated into a kernel function between templates, where the weights of these signals are tuned in an unsupervised manner. We have conducted extensive experiments across multiple domains in FreeBase, and results demonstrate the effectiveness of our clustering framework for finding synonymous query intent templates for attribute intents.

Entity attribute values, such as "lord of the rings" for movie.title or "infant" for shoe.gender, are atomic components of entity expressions. Discovering alternative surface forms of attribute values is important for improving entity recognition and retrieval. In this work, we propose a novel compact clustering framework to jointly identify synonyms for a set of attribute values. The framework can integrate signals from multiple information sources into a similarity function between attribute values. And the weights of these signals are optimized in an unsupervised manner. Extensive experiments across multiple domains demonstrate the effectiveness of our clustering framework for mining entity attribute synonyms.

This paper studies text summarization by extracting hierarchical topics from a given collection of documents. We propose a new approach of text modeling via network analysis. We convert documents into a word influence network, and find the words summarizing the major topics with an efficient influence maximization algorithm. Besides, the influence capability of the topic words on other words in the network reveal the relations among the topic words. Then we cluster the words and build hierarchies for the topics. Experiments on large collections of Web documents show that a simple method based on the influence analysis is effective, compared with existing generative topic modeling and random walk based ranking.

A large portion of real world data is either text or structured (e.g., relational) data. Moreover, such data objects are often linked together (e.g., structured specification of products linking with the corresponding product descriptions and customer comments). Even for text data such as news data, typed entities can be extracted with entity extraction tools. The EventCube project constructs TextCube and TopicCube from interconnected structured and text data (or from text data via entity extraction and dimension building), and performs multidimensional search and analysis on such datasets, in an informative, powerful, and user-friendly manner. This proposed EventCube demo will show the power of the system not only on the originally designed ASRS (Aviation Safety Report System) data sets, but also on news datasets collected from multiple news agencies, and academic datasets constructed from the DBLP and web data. The system has high potential to be extended in many powerful ways and serve as a general platform for search, OLAP (online analytical processing) and data mining on integrated text and structured data. After the system demo in the conference, the system will be put on the web for public access and evaluation.

MOTIVATION: Copy number abbreviation (CNA) is one type of genomic aberration that is often induced by genome instability and is associated with diseases such as cancer. Determination of the genome-wide CNA profile is an important step in identifying the underlying mutation mechanisms. Genomic data based on next-generation sequencing technology are particularly suitable for determination of high-quality CNA profile. Now is an important time to reevaluate the use of sequencing techniques for CNA analysis, especially with the rapid growth of the different targeted genome and whole-genome sequencing strategies. RESULTS: In this study, we provide a comparison of resequencing strategies, with regard to their utility, applied to the same hepatocellular carcinoma sample for copy number determination. These strategies include whole-genome, exome and restriction site-associated DNA (RAD) sequencing. The last of these strategies is a targeted sequencing technique that involves cutting the genome with a restriction enzyme and isolating the targeted sequences. Our data demonstrate that RAD sequencing is an efficient and comprehensive strategy that allows the cost-effective determination of CNAs. Further investigation of RAD sequencing data led to the finding that a precise measurement of the allele frequency would be a helpful complement to the read depth for CNA analysis for two reasons. First, knowledge of the allele frequency helps to resolve refined calculations of allele-specific copy numbers, which, in turn, identify the functionally important CNAs that are under natural selection on the parental alleles. Second, this knowledge enables deconvolution of CNA patterns in complex genomic regions.

Query spelling correction is a crucial component of modern search engines. Existing methods in the literature for search query spelling correction have two major drawbacks. First, they are unable to handle certain important types of spelling errors, such as concatenation and splitting. Second, they cannot efficiently evaluate all the candidate corrections due to the complex form of their scoring functions, and a heuristic filtering step must be applied to select a working set of top-K most promising candidates for final scoring, leading to non-optimal predictions. In this paper we address both limitations and propose a novel generalized Hidden Markov Model with discriminative training that can not only handle all the major types of spelling errors, including splitting and concatenation errors, in a single unified framework, but also efficiently evaluate all the candidate corrections to ensure the finding of a globally optimal correction. Experiments on two query spelling correction datasets demonstrate that the proposed generalized HMM is effective for correcting multiple types of spelling errors. The results also show that it significantly outperforms the current approach for generating top-K candidate corrections, making it a better first-stage filter to enable any other complex spelling correction algorithm to have access to a better working set of candidate corrections as well as to cover splitting and concatenation errors, which no existing method in academic literature can correct.

Query segmentation is an important task toward understanding queries accurately, which is essential for improving search results. Existing segmentation models either use labeled data to predict the segmentation boundaries, for which the training data is expensive to collect, or employ unsupervised strategy based on a large text corpus, which might be inaccurate because of the lack of relevant information. In this paper, we propose a probabilistic model to exploit clickthrough data for query segmentation, where the model parameters are estimated via an efficient EM algorithm. We further study how to properly interpret the segmentation results and utilize them to improve retrieval accuracy. Specifically, we propose an integrated language model based on the standard bigram language model to exploit the probabilistic structure obtained through query segmentation. Experiment results on two datasets show that our segmentation model outperforms existing segmentation models. Furthermore, extensive experiments on a large retrieval dataset reveals that the results of query segmentation can be leveraged to improve retrieval relevance by using the proposed integrated language model.

One-Class Collaborative Filtering (OCCF) is an emerging setup in collaborative filtering in which only positive examples or implicit feedback can be observed. Compared with the traditional collaborative filtering setting where the data has ratings, OCCF is more realistic in many scenarios when no ratings are available. In this paper, we propose to improve OCCF accuracy by exploiting the rich user information that is often naturally available in community-based interactive information systems, including a user's search query history, purchasing and browsing activities. We propose two ways to incorporate such user information into the OCCF models: one is to linearly combine scores from different sources and the other is to embed user information into collaborative filtering. Experimental results on a large-scale retail data set from a major e-commerce company show that the proposed methods are effective and can improve the performance of the One-Class Collaborative Filtering over baseline methods through leveraging rich user information.