Missing values often occur in multivariate time series, affecting data analysis and applications. Existing studies typically use complete data to train imputation models, which are then used to fill missing values. However, in practice, missing values could appear in various cells. Such varieties unfortunately prevent imputation models performing, even making fillings unavailable without the convergence guarantee, i.e., lacking the ensurance of obtaining the optimal solution when the iteration tends to infinite. The reasons are that (1) the imputed values of multiple cells could affect each other towards the conformance to models, and (2) dependencies obtained from complete data may not be accurate enough to impute many unobserved values, which poses a tougher challenge of the convergence. In this work, we study the collaborative imputation with the convergence guarantee. By “collaborative”, we mean (1) all the missing cells can be collaboratively imputed with the guaranteed conformance to models, and (2) the imputation models are collaboratively optimized according to fillings as well. Our major technical highlights include 1) introducing the statistically explainable collaborative imputation via likelihood maximization, 2) designing a collaborative imputation algorithm for multiple missing cells and extending it into a parallel version equivalently, 3) improving the algorithm by both imputation values and models collaboratively optimized with the convergence guarantee in parallel, 4) designing the streaming imputation and adaptive parameter determination strategies. Experiments on real incomplete datasets demonstrate the superiority of our methods against twelve baselines, in both imputation accuracy and downstream applications.

Multimodal knowledge graphs inevitably contain numerous errors due to the lack of human supervision in their automated construction and updating processes. These errors can significantly degrade the performance of downstream applications that rely on them. Existing researches on knowledge graph error detection primarily focus on leveraging graph structural and textual information to identify triplet errors in unimodal knowledge graphs. However, unlike unimodal knowledge graphs, multimodal knowledge graphs also suffer from mismatches between images and their corresponding entities, referred to as modality errors. These modality errors not only hinder the performance of downstream applications but also impede our effective utilization of the abundant complementary information provided by the visual modality for detecting triplet errors. To this end, we introduce a novel task of multimodal knowledge graph error detection (MKGED) in this paper, aiming at simultaneously identifying both modality errors and triplet errors. Given the lack of datasets for evaluating this task, we first establish two comprehensive MKGED datasets. Furthermore, we propose a novel framework, KGDMC, to address the MKGED task. Within KGDMC, we devise a disentanglement modality reconstruction (DMR) module for modality error detection. This module disentangles each original modality representation into two disjoint components: modality-specific representations and modality-invariant representations, leveraging the cross-modality reconstruction process to detect mismatched visual modalities. Additionally, for the triplet error detection, we propose a multi-grained triplet confidence (MTC) module, incorporating local triplet confidence, global structure confidence, and global path confidence, to collaboratively detect mismatched triplets. Extensive experiments on our constructed two datasets demonstrate the superiority of our proposed framework.

With the rapid development of the Internet and the widespread use of social media, the proliferation of multimodal misinformation combining images and text poses serious risks to societal trust, individual well-being, and the integrity of AI models trained on such data. Recently, the automatic detection multimodal misinformation has become an essential area of research. However, traditional methods often rely on hierarchical neural networks that compress and fuse modalities, potentially overlooking deeper interactions between modalities and reducing model interpretability. In this paper, we present a novel Multimodal Taylor Series (MTS) network for detecting multimodal misinformation. The MTS network leverages Taylor series expansion to explicitly capture both low-order and high-order interactions between modalities, which also enhances interpretability by decomposing the model's processing into distinct terms. Additionally, the proposed MTS network avoids exponential parameter growth and maintains linear scalability, allowing the model to effectively capture complex cross-modal correlations. Extensive experiments on three benchmark datasets demonstrate that the MTS network significantly outperforms state-of-the-art models. We have open-sourced the code and logs at: https://github.com/OneForAllSama/MTS.

Taxonomy completion aims to integrate new concepts into existing taxonomies by determining their appropriate hypernym and hyponym. While semantic and structural information are crucial for this task, existing approaches often struggle to balance these aspects effectively. In this paper, we propose COMI, an efficient taxonomy completion framework that leverages large language models (LLMs) to capture both semantic and structural information in a unified manner. COMI compresses node semantics into token representations, enabling LLMs to efficiently process the input structure composed of these tokens. To enhance the model's understanding of the structure, a further fine-tuning process using contrastive learning with mixup data augmentation is applied, where mixup generates diverse and challenging negative samples. Through these innovations, COMI improves the integration of semantic and structural information, leading to more accurate taxonomy completion. The experimental results on three real-world datasets demonstrate that COMI achieves state-of-the-art performance while showing up to 284x faster inference compared to the previous best method. Our code and compressed tokens are available at https://github.com/cyclexu/COMI.

Multimodal information extraction on social media is a series of fundamental tasks to construct the multimodal knowledge graph. The tasks aim to extract the structural information in free texts with the incorporate images, including: multimodal named entity typing and multimodal relation extraction. However, the growing number of multimodal data implies a growing category set and the newly emerged entity types or relations should be recognized without additional training. To address the aforementioned challenges, we focus on the zero-shot multimodal information extraction tasks which require using textual and visual modalities for recognizing unseen categories. Compared with text-based zero-shot information extraction models, the existing multimodal ones make the textual and visual modalities aligned directly and exploit various fusion strategies to improve their performances. But the existing methods ignore the fine-grained semantic correlation of text-image pairs and samples. Therefore, we propose the multimodal graph-based variational mixture of experts network (MG-VMoE) which takes the MoE network as the backbone and exploits it for aligning multimodal representations in a fine-grained way. Considering to learn informative representations of multimodal data, we design each expert network as a variational information bottleneck to process two modalities in a uni-backbone. Moreover, we also propose the multimodal graph-based virtual adversarial training to learn the semantic correlation between the samples. The experimental results on the two benchmark datasets demonstrate the superiority of MG-VMoE over the baselines.

Abstract In recent years, while algorithm-driven recommendation applications have seen widespread use, their negative impacts have also increasingly raised concerns. To gain a more comprehensive understanding of the impact of different recommendation algorithms, we explored the phenomenon of information cocoons, where users are enveloped by homogenized recommended content, in different algorithm-driven recommender systems. We simulated long-term interactions between users and various algorithm-driven recommender systems, trying to recreate multi-stage recommendation scenarios under the influence of complex factors, and explored whether and to what extent users would fall into information cocoons while analyzing the underlying reasons from the perspective of algorithms. We conducted simulation experiments on two real-world recommendation datasets from different fields. The results show that information cocoons is prevalent across different algorithm-driven recommender systems, and the extent of its occurrence varies. Diversity-oriented recommendations can help alleviate information cocoons but are limited in effectiveness. The ability of diversity-aware re-ranking frameworks to alleviate information cocoons is influenced by the basic recommendation models. Not only considering the diversity of the current recommendation list but also the similarity between items and users’ historical consumption content, we proposed a simple and lightweight re-ranking framework called ICMF. Compared to other re-ranking methods, ICMF avoids an average of 12.48% of users encountering homogenized recommended content.

Abstract Relational data play a crucial role in various fields, but they are often plagued by low-quality issues such as erroneous and missing values, which can terribly impact downstream applications. To tackle these issues, relational data cleaning with traditional signals, e.g., statistics, constraints, and clusters, have been extensively studied, with interpretability and efficiency. Recently, considering the strong capability of modeling complex relationships, artificial intelligence (AI) techniques have been introduced into the data cleaning field. These AI-based methods either consider multiple cleaning signals, integrate various techniques into the cleaning system, or incorporate neural networks. Among them, methods utilizing deep neural networks are classified as deep learning (DL) based, while those that do not are classified as machine learning (ML) based. In this study, we focus on three essential tasks (i.e., error detection, data repairing, and data imputation) for cleaning relational data, to comprehensively review the representative methods using traditional or AI techniques. By comparing and analyzing two types of methods across five dimensions (cost, generalization, interpretability, efficiency, and effectiveness), we provide insights into their strengths, weaknesses, and suitable application scenarios. Finally, we analyze the challenges and open issues currently faced in data cleaning and discuss possible directions for future studies.

Spatio-temporal data collected from geographically distributed sources often contain dirty values that affect downstream applications. Temporal data repairing methods, e.g., based on speed constraints, may mistakenly treat sudden changes as errors, although they represent real events and occur simultaneously at multiple locations. Spatial data repairing approaches emphasize value consistency across different locations but ignore temporal pattern similarity. Meanwhile, existing spatio-temporal repairing methods focus more on spatial error correction rather than temporal value repairing across locations. Therefore, we use both temporal and spatial dependencies to identify and repair spatio-temporal errors. Our main contributions are: (1) formalizing the optimal spatio-temporal data repairing problem under constraints and proving its NP-hardness; (2) designing an exact algorithm that decomposes global repair into local decisions with pruning methods; (3) developing two approximate algorithms with theoretical guarantees and probabilities of hitting the optimal solution, where the first explores a wider search space for higher accuracy, and the second uses a greedy sliding-window strategy to improve efficiency; and (4) conducting experiments on nine real-world datasets and downstream applications against eleven baselines, which demonstrate the superiority and practicability of our methods.

Dirty data are often observed in the multivariate time series, which not only degrades data quality but also adversely affects various downstream applications. Existing studies typically focus on repairing such errors appearing in either timestamps or attribute values alone, relying on the assumption that the other part is clean. However, in real scenarios, owing to various reasons, both timestamps and attribute values can be erroneous. It is intuitive to repair timestamps and attribute values respectively by calling different methods in turn. However, such a strategy may lead to over-repairing and introduce additional errors, by ignoring the mutual reference between timestamps and attribute values. Therefore, in this study, rather than repairing timestamps and attribute values respectively by calling different methods in turn, we consider the repairing for both attribute values and timestamps simultaneously. Our major contributions include (1) defining the multivariate speed constraints and formalizing the optimal repair problem with the NP-hardness analysis, (2) computing the exact solutions with pruning strategies and correctness ensurance, (3) designing the quadratic time approximation algorithm with the performance guarantee, (4) devising the linear time algorithm and ensuring its approximation performance bound. Empirical results over real-world dirty datasets demonstrate the superiority and practicality of our algorithms, against eleven competing methods, where our algorithm not only achieves the best accuracy but also spends the lowest time cost.

Group recommendation aims to suggest items to a group of users that are suitable for the group. Although some existing powerful deep learning models have achieved improved performance, various aspects remain unexplored: (1) Most existing models using contrastive learning tend to rely on high-quality data augmentation which requires precise contrastive view generation; (2) There is multifaceted natural noise in group recommendation, and additional noise is introduced during data augmentation; (3) Most existing hypergraph neural network-based models over-entangle the information of members and items, ignoring their unique characteristics. In light of this, we propose a highly effective Disentangled Hypergraph Masked Auto Encoder-enhanced method for group recommendation (DHMAE), combining a disentangled hypergraph neural network with a graph masked autoencoder. This approach creates self-supervised signals without data augmentation by masking the features of some nodes and hyperedges and then reconstructing them. For the noise problem, we design a masking strategy that relies on pre-computed degree-sensitive probabilities for the process of masking features. Furthermore, we propose a disentangled hypergraph neural network for group recommendation scenarios to extract common messages of members and items and disentangle them during the convolution process. Extensive experiments demonstrate that our method significantly outperforms state-of-the-art models and effectively addresses the noise issue.

Abstract Community search (CS) is a vital research area in network science that focuses on discovering personalized communities for query vertices from graphs. However, existing CS methods mainly concentrate on homogeneous or simple attributed graphs, often disregarding complex semantic information and rich contents carried by entities in heterogeneous graphs (HGs). In this paper, we propose a novel problem, namely the “Semantic Network Oriented Community Search with Meta-Structures in Heterogeneous Graphs (SNCS),” which aims to find dense communities that contain the query vertex, with vertices of the same type sharing similar topics. In response to this new problem, we present a novel approach, also named SNCS, representing the first solution employing meta-structures and topic constraints to tackle community search, leveraging both topological and latent features. To overcome the high-time complexity challenge posed by searching through meta-structures, we introduce a unique graph reconstruction technique. Our proposed method’s superiority is validated through extensive evaluations on real-world datasets. The results demonstrate a significant improvement in the quality of the obtained communities, with increases of 3.5–4.4% in clustering coefficient and 5–11% in density while requiring only 4–46% of the running time when compared with the state-of-the-art methods.

High-quality data are crucial for practical applications, but obtaining them through high-precision sensors comes at a high cost. To guarantee the trade-off between cost and precision, we may use multiple low-precision sensors to obtain the nearly accurate data fusion results at an affordable cost. The commonly used techniques, such as the Kalman filter and truth discovery methods, typically compute fusion values by combining all the observations according to predictions or sensor reliability. However, low-precision sensors can often cause outliers, and such methods combining all observations are susceptible to interference. To handle this problem, we select a single observation from multiple sensor readings as the fusion result for each timestamp. The selection strategy is guided by the maximum likelihood estimation, to determine the most probable changing trends of fusion results with adjacent timestamps. Our major contributions include (1) the problem formalization and NP-hardness analysis on finding the fusion result with the maximum likelihood w.r.t. local fusion models, (2) exact algorithms based on dynamic programming for tackling the problem, (3) efficient approximation methods with performance guarantees. Experiments on various real datasets and downstream applications demonstrate the superiority and practicality of our work in low-precision sensor data fusion.

Although clustering methods have shown promising performance in various applications, they cannot effectively handle incomplete data. Existing studies often impute missing values first before clustering analysis and conduct these two processes separately. However, inaccurate imputation does not necessarily contribute positively to the subsequent clustering. Intuitively, accurate imputation and clustering can serve and benefit from each other, where clustering-based imputation methods typically utilize cluster signals to impute incomplete data and accurate fillings are expected to bring more valuable data for clustering. Therefore, in this manuscript, rather than considering two tasks independently or conducting them respectively, we study simultaneous clustering and imputing over incomplete data. The immediate benefit is that such a strategy improves both clustering and imputation performance simultaneously, to get a win-win result. Our major technical highlights include (1) the problem formalization and NP-hardness analysis on computing simultaneous clustering and imputing results, (2) exact solutions by transforming the problem as the integer linear programming (ILP) formulation, and (3) efficient approximation algorithms based on the linear programming (LP) relaxation and local neighbors (LN) solution, with approximation guarantees. Experiments on various real-world datasets demonstrate the superiority of our work in clustering and imputing incomplete data.

User mobility behaviors frequently exhibit a spatial clustering phenomenon, wherein points of interest (POIs) visited by the same user tend to be in close proximity. Consequently, leveraging geographical influences for user preference modeling remains a prevalent approach in POI recommendation tasks. However, existing studies often overlook users’ hidden geographical habits for the following reasons: (1) Geographical features are commonly approximated by manually partitioned regions or fixed distributions, inadequately capturing the nuanced spatial proximity among POIs. (2) POIs with high geographical correlations are not explicitly incorporated as feedback signals during the training process, resulting in a lack of spatial clustering pattern learning within users’ preference representations. This paper introduces GeoCo, aGeographicalCorrelation enhanced network for POI recommendation. First, we model POIs’ geographical features using fine-grained hierarchical sequences to capture multilevel spatial relations. Subsequently, we propose a pre-training network that employs the sentence similarity assessment technique to comprehend the semantics of geographical correlations. Second, we introduce a novel multi-objective training process that intuitively learns spatial clustering patterns through user mobility behaviors. Extensive experiments conducted on two location-based social network (LBSN) datasets, Gowalla and Foursquare, demonstrate the superiority of our proposed model over fourteen state-of-the-art baseline models in POI recommendation tasks. Compared with the baselines, GeoCo has achieved a performance improvement of at least 5$\%$in Rec@5 and HR@5 on both datasets. Furthermore, we verify the effectiveness of pre-trained location vectors and the multi-objective training process in enhancing the model's understanding of geographical correlations for user preference construction.

Dirty data are commonly observed in real applications, making cleaning them a key step in data preparation. The widely adopted idea of cleaning dirty data is based on detecting conflicts w.r.t. integrity constraints. Typical S-repair methods remove a minimal set of tuples (to avoid excessive removal and information loss) such that integrity constraints are no longer violated in remaining tuples. Unfortunately, multiple candidates of minimal removal sets may exist and are difficult to determine which one is indeed proper. We intuitively notice that a clean tuple often has more close neighbors (i.e., higher density) than dirty tuples. Hence, in this paper, we study the problem of finding the optimal S-repair under integrity constraints with the highest density, among various minimal removal sets. Our major contributions include (1) thenp-hardness analysis on solving the problem, (2) a heuristic algorithm for efficiently tackling the problem and returning the optimal solution in certain cases, (3) an approximation performance bounded method with the same optimal solution guarantee. Experiments on real datasets collected from industry with real-world errors demonstrate the superiority of our work in cleaning dirty tuples.

Temporal link prediction on dynamic graphs has attracted considerable attention. Most methods focus on the graph at each timestamp and extract features for prediction. As graphs are directly compressed into feature matrices, the important latent information at each timestamp has not been well revealed. Eventually, the acquisition of dynamic evolution-related patterns is rendered inadequately. In this paper, inspired by the process of Super-Resolution (SR), a novel deep generative model SRG (Super Resolution Graph) is proposed. We innovatively introduce the concepts of the Low-Resolution (LR) graph, which is a single adjacent matrix at a timestamp, and the High-Resolution (HR) graph, which includes the link status of surrounding snapshots. Specifically, two major aspects are considered regarding the construction of the HR graph. For edges, we endeavor to obtain an extensive information transmission description that affects the current link status. For nodes, similar to the SR process, the neighbor relationship among nodes is maintained. In this form, we could predict the link status from a new perspective: Under the supervision of the graph moving average strategy, the conditional normalizing flow effectively realizes the transformation between LR and HR graphs. Extensive experiments on six real-world datasets from different applications demonstrate the effectiveness of our proposal.

Grammatical Error Correction (GEC) is usually considered as a translation task where an erroneous sentence is treated as the source language and the corrected sentence as the target language. The state-of-the-art GEC models often adopt transformer-based sequence-to-sequence architecture of machine translation. However, most of these approaches ignore the syntactic information because the syntax of an erroneous sentence is also full of errors and not beneficial to GEC. In this paper, we propose a novel Error-Correction Constituent Parsing (ECCP) task which uses the constituent parsing of corrected sentences to avoid the harmful effect of the erroneous sentence. We also propose an architecture that includes one encoder and two decoders. There are millions of parameters in transformer-based GEC models, and the labeled training data is substantially less than synthetic pre-training data. Therefore, adapter layers are added to the proposed architecture, and adapter tuning is used for fine-tuning our model to alleviate the low-resource issue. We conduct experiments on CoNLL-2014, BEA-2019, and JFLEG test datasets in unsupervised and supervised settings. Experimental results show that our method outperforms the-state-of-art baselines and achieves superior performance on all datasets.

Temporal link prediction, aiming to predict future edges between paired nodes in a dynamic graph, is of vital importance in diverse applications. However, existing methods are mainly built upon uniform Euclidean space, which has been found to be conflict with the power-law distributions of real-world graphs and unable to represent the hierarchical connections between nodes effectively. With respect to the special data characteristic, hyperbolic geometry offers an ideal alternative due to its exponential expansion property. In this paper, we propose HGWaveNet, a novel hyperbolic graph neural network that fully exploits the fitness between hyperbolic spaces and data distributions for temporal link prediction. Specifically, we design two key modules to learn the spatial topological structures and temporal evolutionary information separately. On the one hand, a hyperbolic diffusion graph convolution (HDGC) module effectively aggregates information from a wider range of neighbors. On the other hand, the internal order of causal correlation between historical states is captured by hyperbolic dilated causal convolution (HDCC) modules. The whole model is built upon the hyperbolic spaces to preserve the hierarchical structural information in the entire data flow. To prove the superiority of HGWaveNet, extensive experiments are conducted on six real-world graph datasets and the results show a relative improvement by up to 6.67% on AUC for temporal link prediction over SOTA methods.

Entity linking (EL) is the process of linking entity mentions appearing in web text with their corresponding entities in a knowledge base. EL plays an important role in the fields of knowledge engineering and data mining, underlying a variety of downstream applications such as knowledge base population, content analysis, relation extraction, and question answering. In recent years, deep learning (DL), which has achieved tremendous success in various domains, has also been leveraged in EL methods to surpass traditional machine learning based methods and yield the state-of-the-art performance. In this survey, we present a comprehensive review and analysis of existing DL based EL methods. First of all, we propose a new taxonomy, which organizes existing DL based EL methods using three axes: embedding, feature, and algorithm. Then we systematically survey the representative EL methods along the three axes of the taxonomy. Later, we introduce ten commonly used EL data sets and give a quantitative performance analysis of DL based EL methods over these data sets. Finally, we discuss the remaining limitations of existing methods and highlight some promising future directions.

Twitter, a microblogging platform, has developed into an increasingly invaluable information source, where millions of users post a great quantity of tweets with various topics per day. Heterogeneous information networks consisting of multi-type objects and relations are becoming more and more prevalent as an organization form of knowledge and information. The task of linking an entity mention in a tweet with its corresponding entity in a heterogeneous information network is of great importance, for the purpose of enriching heterogeneous information networks with the abundant and fresh knowledge embedded in tweets. However, the entity mention is ambiguous. Additionally, tweets are short and informal, making it difficult to mine enough information from a single tweet for entity linking. In this paper, we propose an unsupervised iterative clustering framework TELHIN to link multiple similar tweets with a heterogeneous information network jointly. Our framework takes three dimensions of tweet similarity into consideration: (1) content similarity, (2) temporal similarity, and (3) user similarity. The appropriate weights of different similarity dimensions for each entity mention are learned iteratively based on the metric learning algorithm by leveraging the pairwise constraints generated automatically. Experiments on real data demonstrate the effectiveness of our framework in comparison with the baselines.

Open Information Extraction (OIE) methods extract a large number of OIE triples (noun phrase, relation phrase, noun phrase) from text, which compose large Open Knowledge Bases (OKBs). However, noun phrases (NPs) and relation phrases (RPs) in OKBs are not canonicalized and often appear in different paraphrased textual variants, which leads to redundant and ambiguous facts. To address this problem, there are two related tasks: OKB canonicalization (i.e., convert NPs and RPs to canonicalized form) and OKB linking (i.e., link NPs and RPs with their corresponding entities and relations in a curated Knowledge Base (e.g., DBPedia). These two tasks are tightly coupled, and one task can benefit significantly from the other. However, they have been studied in isolation so far. In this paper, we explore the task of joint OKB canonicalization and linking for the first time, and propose a novel framework JOCL based on factor graph model to make them reinforce each other. JOCL is flexible enough to combine different signals from both tasks, and able to extend to fit any new signals. A thorough experimental study over two large scale OIE triple data sets shows that our framework outperforms all the baseline methods for the task of OKB canonicalization (OKB linking) in terms of average F1 (accuracy).

Knowledge bases are critical to many applications. However, they are greatly incomplete. Enriching knowledge bases with new entities and new location attributes becomes increasingly important. Given a named entity with tweets and Web documents where the entity appears, we aim to predict the entity city-level location combining the geographical location knowledge embedded in both Twitter and Web. This task is helpful for knowledge base enrichment and tweet location prediction. In this paper we propose NELPTW, the first unsupervised framework forNamedEntityLocationPrediction by leveraging the knowledge fromTwitter andWeb. Based on each data source, NELPTW utilizes a linear function ranking model to generate several rankings to the candidate location set for each entity. To combine the knowledge from two sources which have different reliability and importance for the location prediction, an unsupervised rank aggregation algorithm is developed to aggregate multiple rankings for each entity to obtain a better ranking. A learning algorithm based on the EM method is proposed to automatically learn the parameters of the ranking model without requiring any training labels. The experimental results over a real world Twitter and Web data set show that our framework significantly outperforms the baselines in terms of accuracy.

Heterogeneous information networks that consist of multi-type, interconnected objects are becoming increasingly popular, such as social media networks and bibliographic networks. The task of linking named entity mentions detected from unstructured Web text with their corresponding entities in a heterogeneous information network is of practical importance for the problem of information network population. This task is challenging due to name ambiguity and limited knowledge existing in the network. Most existing entity linking methods focus on linking entities with Wikipedia and cannot be applied to our task. In this paper, we present SHINE+, a general framework for linking named entitieS in Web free text with a Heterogeneous I nformation NEtwork. We propose a probabilistic linking model, which unifies an entity popularity model with an entity object model. As the entity knowledge contained in the information network is insufficient, we propose a knowledge population algorithm to iteratively enrich the network entity knowledge by leveraging the context information of mentions mapped by the linking model with high confidence, which subsequently boosts the linking performance. Experimental results over two real heterogeneous information networks (i.e., DBLP and IMDb) demonstrate the effectiveness and efficiency of our proposed framework in comparison with the baselines.

Similarity search is an essential operation in many applications. Given a collection of set records and a query, the exact set similarity search aims at finding all the records that are similar to the query from the collection. Existing methods adopt a filter-and-verify framework, which make use of inverted indexes. However, as the complexity of verification is rather low for setbased similarity metrics, they always fail to make a good tradeoff between filter power and filter cost. In this paper, we proposed an efficient framework for exact set similarity search based on tree index structure. We defined a hash-based ordering to effectively import data into the index structure and then make optimizations to reduce the filter cost. To further improve the filter power, we proposed a dynamic algorithm to partition the dataset into several parts and propose a multiple-index framework. Experimental results on real-world datasets show that our method significantly outperform the state-of-the-art algorithms.

With the increasing popularity of mobile Internet, it can bring great business value for Telecommunication (Telco) operators to provide users with better services in a timely manner. Understanding the change of mobile user's activity can be a great help for operators to increase user experience and avoid the user churn. In this paper, we predict short-term user activity with massive Mobile Broadband (MBB) data. We conduct experiments with a large scale and real-world dataset of Telco operators, which includes MBB data of more than three million users. The experimental results show that gradient boosting decision tree is the effective model for the prediction. In addition, we show that the user activity is highly correlated with individual features. Features, which are associated with personal daily habits, tend to make people active the next day. In contract, features, which happen for specific purpose and are less related to the individual habits, can make people inactive the next day.

This paper studies an emotion classification problem, which aims to classify online news comments to one of fine-grained emotion categories, e.g. happy, sad, and angry, etc. Neural networks have been widely used and achieved great success in sentiment classification. However, there must be sufficient labeled comments available for training neural networks, which usually requires labor-intensive and time-consuming manual labeling. One of the most effective solutions is to apply transfer learning, which uses abundant labeled comments from a source news domain to help the classification for another target domain with limited amount of labeled data. Still, the comments from different domains can have very different word distributions, which makes it difficult to transfer knowledge from one domain to another. In this paper, we accomplish cross-domain emotion tagging based on an advanced neural network BLSTM (bidirectional long short-term memory) with "domain translation'', which can overcome the difference between domains. A weighted linear transformation is utilized to "translate'' knowledge from source to target domain. An extensive set of experimental results on four datasets from popular online news services demonstrates the effectiveness of our proposed models.

In this paper, we present Deola, an Online system for Author Entity Linking with DBLP. Unlike most existing entity linking systems which focus on linking entities with Wikipedia and depend largely on the special features associated with Wikipedia (e.g., Wikipedia articles), Deola links author names appearing in the web document which belongs to the domain of computer science with their corresponding entities existing in the DBLP network. This task is helpful for the enrichment of the DBLP network and the understanding of the domain-specific document. This task is challenging due to name ambiguity and limited knowledge existing in DBLP. Given a fragment of domain-specific web document belonging to the domain of computer science, Deola can return the mapping entity in DBLP for each author name appearing in the input document.

This paper proposes a novel approach for efficiently evaluating regular path queries over provenance graphs of workflows that may include recursion. The approach assumes that an execution g of a workflow G is labeled with query-agnostic reachability labels using an existing technique. At query time, given g, G and a regular path query R, the approach decomposes R into a set of subqueries R1, …, Rkthat are safe for G. For each safe subquery Ri, G is rewritten so that, using the reachability labels of nodes in g, whether or not there is a path which matches Ribetween two nodes can be decided in constant time. The results of each safe subquery are then composed, possibly with some small unsafe remainder, to produce an answer to R. The approach results in an algorithm that significantly reduces the number of subqueries k over existing techniques by increasing their size and complexity, and that evaluates each subquery in time bounded by its input and output size. Experimental results demonstrate the benefit of this approach.

In many online news services, users often write comments towards news in subjective emotions such as sadness, happiness or anger. Knowing such emotions can help understand the preferences and perspectives of individual users, and therefore may facilitate online publishers to provide more relevant services to users. Although building emotion classifiers is a practical task, it highly depends on sufficient training data that is not easy to be collected directly and the manually labeling work of comments can be quite labor intensive. Also, online news has different domains, which makes the problem even harder as different word distributions of the domains require different classifiers with corresponding distinct training data.

We study the problem of searching a repository of complex hierarchical workflows whose component modules, both composite and atomic, have been annotated with keywords. Since keyword search does not use the graph structure of a workflow, we develop a model of workflows using context-free bag grammars. We then give efficient polynomial-time algorithms that, given a workflow and a keyword query, determine whether some execution of the workflow matches the query. Based on these algorithms we develop a search and ranking solution that efficiently retrieves the top-k grammars from a repository. Finally, we propose a novel result presentation method for grammars matching a keyword query, based on representative parse-trees. The effectiveness of our approach is validated through an extensive experimental evaluation.

With the rapid growing popularity of XML to represent data, how to make good use of XML data in relational databases is worthy of study. Storing XML data as text in relational databases is a traditional strategy which cannot reflect the feature of XML format. In this paper, a mechanism for XML data storage and query in relational databases is proposed. XML data can be stored in relational tables and XQuery expressions can be evaluated as a part of SQL for XML data query. XQuery grammar tree and Query tree model for XML data query in rela-tional databases is presented to gain more efficient performance while querying XML data. Appropriative algorithm for evaluating XPath is also presented in this paper by which XQuery can be evaluated rapidly and efficiency. Finally, experiments invalidate the strategy of XML storage and run the algorithm on real XML datasets to show the efficiency compared with other mechanisms.

This paper is concerned with the joint allocation of bid price and campaign budget in sponsored search. In this application, an advertiser can create a number of campaigns and set a budget for each of them. In a campaign, he/she can further create several ad groups with bid keywords and bid prices. Data analysis shows that many advertisers are dealing with a very large number of campaigns, bid keywords, and bid prices at the same time, which poses a great challenge to the optimality of their campaign management. As a result, the budgets of some campaigns might be too low to achieve the desired performance goals while those of some other campaigns might be wasted; the bid prices for some keywords may be too low to win competitive auctions while those of some other keywords may be unnecessarily high. In this paper, we propose a novel algorithm to automatically address this issue. In particular, we model the problem as a constrained optimization problem, which maximizes the expected advertiser revenue subject to the constraints of the total budget of the advertiser and the ranges of bid price change. By solving this optimization problem, we can obtain an optimal budget allocation plan as well as an optimal bid price setting. Our simulation results based on the sponsored search log of a commercial search engine have shown that by employing the proposed method, we can effectively improve the performances of the advertisers while at the same time we also see an increase in the revenue of the search engine. In addition, the results indicate that this method is robust to the second-order effects caused by the bid fluctuations from other advertisers.

With the rapid growth of online news services, users can actively respond to online news by making comments. Users often express subjective emotions in comments such as sadness, surprise and anger. Such emotions can help understand the preferences and perspectives of individual users, and therefore may facilitate online publishers to provide users with more relevant services. This paper tackles the task of predicting emotions for the comments of online news. To the best of our knowledge, this is the first research work for addressing the task. In particular, this paper proposes a novel Meta classification approach that exploits heterogeneous information sources such as the content of the comments and the emotion tags of news articles generated by users. The experiments on two datasets from online news services demonstrate the effectiveness of the proposed approach.

Although personalized search has been under way for many years and many personalization algorithms have been investigated, it is still unclear whether personalization is consistently effective on different queries for different users and under different search contexts. In this paper, we study this problem and provide some findings. We present a large-scale evaluation framework for personalized search based on query logs and then evaluate five personalized search algorithms (including two click-based ones and three topical-interest-based ones) using 12-day query logs of Windows Live Search. By analyzing the results, we reveal that personalized Web search does not work equally well under various situations. It represents a significant improvement over generic Web search for some queries, while it has little effect and even harms query performance under some situations. We propose click entropy as a simple measurement on whether a query should be personalized. We further propose several features to automatically predict when a query will benefit from a specific personalization algorithm. Experimental results show that using a personalization algorithm for queries selected by our prediction model is better than using it simply for all queries.

Learning-to-rank algorithms, which can automatically adapt ranking functions in web search, require a large volume of training data. A traditional way of generating training examples is to employ human experts to judge the relevance of documents. Unfortunately, it is difficult, time-consuming and costly. In this paper, we study the problem of exploiting click-through data for learning web search rankings that can be collected at much lower cost. We extract pairwise relevance preferences from a large-scale aggregated click-through dataset, compare these preferences with explicit human judgments, and use them as training examples to learn ranking functions. We find click-through data are useful and effective in learning ranking functions. A straightforward use of aggregated click-through data can outperform human judgments. We demonstrate that the strategies are only slightly affected by fraudulent clicks. We also reveal that the pairs which are very reliable, e.g., the pairs consisting of documents with large click frequency differences, are not sufficient for learning.