OpenRaiser/Intern-Atlas huggingface dataset:
Domain Cartridge: Unsupervised Framework for Shallow Domain Ontology Construction from Corpus
Authors: Subhabrata Mukherjee, Jitendra Ajmera, Sachindra Joshi
Venue: CIKM
Year: 2014

In this work we propose an unsupervised framework to construct a shallow domain ontology from corpus. It is essential for Information Retrieval systems, Question-Answering systems, Dialogue etc. to identify important concepts in the domain and the relationship between them. We identify important domain terms of which multi-words form an important component. We show that the incorporation of multi-words improves parser performance, resulting in better parser output, which improves the performance of an existing Question-Answering system by upto 7%. On manually annotated smartphone dataset, the proposed system identifies 40:87% of the domain terms, compared to 22% recall obtained using WordNet, 43:77% by Yago and 53:74% by BabelNet respectively. However, it does not use any manually annotated resource like the compared systems. Thereafter, we propose a framework to construct a shallow ontology from the discovered domain terms by identifying four domain relations namely, Synonyms ('similar-to'), Type-Of ('is-a'), Action-On ('methods') and Feature-Of ('attributes'), where we achieve significant performance improvement over WordNet, BabelNet and Yago without using any mode of supervision or manual annotation.
Dynamic Clustering of Contextual Multi-Armed Bandits
Authors: Trong T. Nguyen, Hady Wirawan Lauw
Venue: CIKM
Year: 2014

With the prevalence of the Web and social media, users increasingly express their preferences online. In learning these preferences, recommender systems need to balance the trade-off between exploitation, by providing users with more of the "same", and exploration, by providing users with something "new" so as to expand the systems' knowledge. Multi-armed bandit (MAB) is a framework to balance this trade-off. Most of the previous work in MAB either models a single bandit for the whole population, or one bandit for each user. We propose an algorithm to divide the population of users into multiple clusters, and to customize the bandits to each cluster. This clustering is dynamic, i.e., users can switch from one cluster to another, as their preferences change. We evaluate the proposed algorithm on two real-life datasets.
Towards Named-Entity-based Similarity Measures: Challenges and Opportunities
Authors: Tom De Nies, Christian Beecks, Wesley De Neve, Thomas Seidl, Erik Mannens, Rik Van de Walle
Venue: CIKM
Year: 2014

In this paper, we investigate challenges related to the adaptation of similarity measures used in the field of Information Retrieval to work with semantic features, i.e. Named Entities. The challenges to consider are numerous, including the accuracy of the annotation process, the adapted similarity measures, the quality of the Linked Data referred to, and the efficient access to the Semantic Web. We discuss each challenge in detail, as well as possible ways to tackle them.
"Strength Lies in Differences": Diversifying Friends for Recommendations through Subspace Clustering
Authors: Eirini Ntoutsi, Kostas Stefanidis, Katharina Rausch, Hans-Peter Kriegel
Venue: CIKM
Year: 2014

Nowadays, WWW brings overwhelming variety of choices to consumers. Recommendation systems facilitate the selection by issuing recommendations to them. Recommendations for users, or groups, are determined by considering users similar to the users in question. Scanning the whole database for locating similar users, though, is expensive. Existing approaches build cluster models by employing full-dimensional clustering to find sets of similar users. As the datasets we deal with are high-dimensional and incomplete, full-dimensional clustering is not the best option. To this end, we explore the fault-tolerant subspace clustering approach. We extend the concept of fault tolerance to density-based subspace clustering, and to speed up our algorithms, we introduce the significance threshold for considering only promising dimensions for subspace extension. Moreover, as we potentially receive a multitude of users from subspace clustering, we propose a weighted ranking approach to refine the set of like-minded users. Our experiments on real movie datasets show that the diversification of the similar users that the subspace clustering approaches offer results in better recommendations compared to traditional collaborative filtering and full-dimensional clustering approaches.
Re-call and Re-cognition in Episode Re-retrieval: A User Study on News Re-finding a Fortnight Later
Authors: Shuya Ochiai, Makoto P. Kato, Katsumi Tanaka
Venue: CIKM
Year: 2014

This study investigates recall and recognition in a news refinding task where participants were asked to read news articles and then to search for the same articles a fortnight later. Recall, which is a task to express what a person remembers, corresponds to query formulations, while recognition, which is a task to judge whether a presented item has been shown before, corresponds to a user's relevance judgment on search results in a refinding task. Our four main contributions can be summarized as follows: (i) we developed a method to investigate the effects of memory loss on episode refinding tasks on a large scale; (ii) our user study revealed a big drop on search performances in the refinding task after a fortnight and several differences between search queries input immediately after news browsing and ones at a later time; (iii) we found that asking questions and expanding input queries on the basis of the answers significantly improved the search performance in the news refinding task; and (iv) the users' recognition abilities were different than their recall abilities, e.g. object names in a news story could be correctly recognized even though they were rarely recalled. Our findings support several findings in cognitive psychology from the viewpoint of information refinding and also have several implications for search algorithms for assisting user refinding.
Truth Discovery in Crowdsourced Detection of Spatial Events
Authors: Wentao Robin Ouyang, Mani B. Srivastava, Alice Toniolo, Timothy J. Norman
Venue: CIKM
Year: 2014

<p>The ubiquity of smartphones has led to the emergence of mobile crowdsourcing tasks such as the detection of spatial events when smartphone users move around in their daily lives. However, the credibility of those detected events can be negatively impacted by unreliable participants with low-quality data. Consequently, a major challenge in quality control is to discover true events from diverse and noisy participants' reports. This truth discovery problem is uniquely distinct from its online counterpart in that it involves uncertainties in both participants' mobility and reliability. Decoupling these two types of uncertainties through location tracking will raise severe privacy and energy issues, whereas simply ignoring missing reports or treating them as negative reports will significantly degrade the accuracy of the discovered truth. In this paper, we propose a new method to tackle this truth discovery problem through principled probabilistic modeling. In particular, we integrate the modeling of location popularity, location visit indicators, truth of events and three-way participant reliability in a unified framework. The proposed model is thus capable of efficiently handling various types of uncertainties and automatically discovering truth without any supervision or the need of location tracking. Experimental results demonstrate that our proposed method outperforms existing state-of-the-art truth discovery approaches in the mobile crowdsourcing environment.</p>
Query Performance Prediction for Aspect Weighting in Search Result Diversification
Authors: Ahmet Murat Ozdemiray, Ismail Sengor Altingovde
Venue: CIKM
Year: 2014

Accurate estimation of query aspect weights is an important issue to improve the performance of explicit search result diversification algorithms. For the first time in the literature, we propose using post-retrieval query performance predictors (QPPs) to estimate, for each aspect, the retrieval effectiveness on the candidate document set, and leverage these estimations to set the aspect weights. In addition to utilizing well-known QPPs from the literature, we also introduce three new QPPs that are based on score distributions and hence, can be employed for online query processing in real-life search engines. Our exhaustive experiments reveal that using QPPs for aspect weighting improves almost all state-of-the-art diversification algorithms in comparison to using a uniform weight estimator. Furthermore, the proposed QPPs are comparable or superior to the existing predictors in the context of aspect weighting.
A Fixed-Point Method for Weighting Terms in Verbose Informational Queries
Authors: Jiaul H. Paik, Douglas W. Oard
Venue: CIKM
Year: 2014

The term weighting and document ranking functions used with informational queries are typically optimized for cases in which queries are short and documents are long. It is reasonable to assume that the presence of a term in a short query reflects some aspect of the topic that is important to the user, and thus rewarding documents that contain the greatest number of distinct query terms is a useful heuristic. Verbose informational queries, such as those that result from cut-and-paste of example text, or that might result from informal spoken interaction, pose a different challenge in which many extraneous (and thus potentially misleading) terms may be present in the query. Modest improvements have been reported from applying supervised methods to learn which terms in a verbose query deserve the greatest emphasis. This paper proposes a novel unsupervised method for weighting terms in verbose informational queries that relies instead on iteratively estimating which terms are most central to the query. The key idea is to use an initial set of retrieval results to define a recursion on the term weight vector that converges to a fixed point representing the vector that optimally describes the initial result set. Experiments with several TREC news and Web test collections indicate that the proposed method often statistically significantly outperforms state of the art supervised methods.
MapReduce Triangle Enumeration With Guarantees
Authors: Ha-Myung Park, Francesco Silvestri, U Kang, Rasmus Pagh
Venue: CIKM
Year: 2014

We describe an optimal randomized MapReduce algorithm for the problem of triangle enumeration that requires O(E3/2/(M√m) rounds, where m denotes the expected memory size of a reducer and M the total available space. This generalizes the well-known vertex partitioning approach proposed in (Suri and Vassilvitskii, 2011) to multiple rounds, significantly increasing the size of the graphs that can be handled on a given system. We also give new theoretical (high probability) bounds on the work needed in each reducer, addressing the "curse of the last reducer". Indeed, our work is the first to give guarantees on the maximum load of each reducer for an arbitrary input graph. Our experimental evaluation shows the scalability of our approach, that it is competitive with existing methods improving the performance by a factor up to 2X, and that it can significantly increase the size of datasets that can be processed.
Active Exploration in Networks: Using Probabilistic Relationships for Learning and Inference
Authors: Joseph John Pfeiffer III, Jennifer Neville, Paul N. Bennett
Venue: CIKM
Year: 2014

Many interesting domains in machine learning can be viewed as networks, with relationships (e.g., friendships) connecting items (e.g., individuals). The Active Exploration (AE) task is to identify all items in a network with a desired trait (i.e., positive labels) given only partial information about the network. The AE process iteratively queries for labels or network structure within a limited budget; thus, accurate predictions prior to making each query is critical to maximizing the number of positives gathered. However, the targeted AE query process produces partially observed networks that can create difficulties for predictive modeling. In particular, we demonstrate that these partial networks can exhibit extreme label correlation bias, which makes it difficult for conventional relational learning methods to accurately estimate relational parameters. To overcome this issue, we model the joint distribution of possible edges and labels to improve learning and inference. Our proposed method, Probabilistic Relational Expectation Maximization (PR-EM), is the first AE approach to accurately learn the complex dependencies between attributes, labels, and structure to improve predictions. PR-EM utilizes collective inference over the missing relationships in the partial network to jointly infer unknown item traits. Further, we develop a linear inference algorithm to facilitate efficient use of PR-EM in large networks. We test our approach on four real world networks, showing that AE with PR-EM gathers significantly more positive items compared to state-of-the-art methods.
Analysis of Physical Activity Propagation in a Health Social Network
Authors: NhatHai Phan, Dejing Dou, Xiao Xiao, Brigitte Piniewski, David Kil
Venue: CIKM
Year: 2014

Modeling physical activity propagation, such as the activity level and intensity, is the key to prevent the cascades of obesity, and help spread wellness and healthy behavior in a social network. However, there has been lacking of scientific and quantitative study to elucidate how social communication may deliver physical activity interventions. In this work we introduce a Community-level Physical Activity Propagation (CPP) model to analyze physical activity propagation and social influence at different granularities (i.e., individual level and community level). CPP is a novel model which is inspired by the well-known Independent Cascade and Community-level Social Influence models. Given a social network, we utilize a hierarchical approach to detect a set of communities and their reciprocal influence strength of physical activities. CPP provides a powerful tool to discover, summarize, and investigate influence patterns of physical activities in a health social network. The detail experimental evaluation shows not only the effectiveness of our approach but also the correlation of the detected communities with various health outcome measures (i.e., both existing ones and our novel measure, named Wellness score, which is a combination of lifestyle parameters, biometrics, and biomarkers). Our promising results potentially pave a way for knowledge discovery in health social networks.
Learning to Propagate Rare Labels
Authors: Rakesh Pimplikar, Dinesh Garg, Deepesh Bharani, Gyana R. Parija
Venue: CIKM
Year: 2014

Label propagation is a well-explored family of methods for training a semi-supervised classifier where input data points (both labeled and unlabeled) are connected in the form of a weighted graph. For binary classification, the performance of these methods starts degrading considerably whenever input dataset exhibits following characteristics - (i) one of the class label is rare label or equivalently, class imbalance (CI) is very high, and (ii) degree of supervision (DoS) is very low -- defined as fraction of labeled points. These characteristics are common in many real-world datasets relating to network fraud detection. Moreover, in such applications, the amount of class imbalance is not known a priori. In this paper, we have proposed and justified the use of an alternative formulation for graph label propagation under such extreme behavior of the datasets. In our formulation, objective function is the difference of two convex quadratic functions and the constraints are box constraints. We solve this program using Concave-Convex Procedure (CCCP). Whenever the problem size becomes too large, we suggest to work with a k-NN subgraph of the given graph which can be sampled by using Locality Sensitive Hashing (LSH) technique. We have also discussed various issues that one typically faces while sampling such a k-NN subgraph in practice. Further, we have proposed a novel label flipping method on top of the CCCP solution, which improves the result of CCCP further whenever class imbalance information is made available a priori. Our method can be easily adopted for a MapReduce platform, such as Hadoop. We have conducted experiments on 11 datasets comprising a graph size of up to 20K nodes, CI as high as 99:6%, and DoS as low as 0:5%. Our method has resulted up to 19:5-times improvement in F-measure and up to 17:5-times improvement in AUC-PR measure against baseline methods.
Correct Me If I'm Wrong: Fixing Grammatical Errors by Preposition Ranking
Authors: Roman Prokofyev, Ruslan Mavlyutov, Martin Grund, Gianluca Demartini, Philippe Cudré-Mauroux
Venue: CIKM
Year: 2014

The detection and correction of grammatical errors still represent very hard problems for modern error-correction systems. As an example, the top-performing systems at the preposition correction challenge CoNLL-2013 only achieved a F1 score of 17%. In this paper, we propose and extensively evaluate a series of approaches for correcting prepositions, analyzing a large body of high-quality textual content to capture language usage. Leveraging n-gram statistics, association measures, and machine learning techniques, our system is able to learn which words or phrases govern the usage of a specific preposition. Our approach makes heavy use of n-gram statistics generated from very large textual corpora. In particular, one of our key features is the use of n-gram association measures (e.g., Pointwise Mutual Information) between words and prepositions to generate better aggregated preposition rankings for the individual n-grams. We evaluate the effectiveness of our approach using cross-validation with different feature combinations and on two test collections created from a set of English language exams and StackExchange forums. We also compare against state-of-the-art supervised methods. Experimental results from the CoNLL-2013 test collection show that our approach to preposition correction achieves ∼30% in F1 score which results in 13% absolute improvement over the best performing approach at that challenge.
Computing Multi-Relational Sufficient Statistics for Large Databases
Authors: Zhensong Qian, Oliver Schulte, Yan Sun
Venue: CIKM
Year: 2014

Databases contain information about which relationships do and do not hold among entities. To make this information accessible for statistical analysis requires computing sufficient statistics that combine information from different database tables. Such statistics may involve any number of positive and negative relationships. With a naive enumeration approach, computing sufficient statistics for negative relationships is feasible only for small databases. We solve this problem with a new dynamic programming algorithm that performs a virtual join, where the requisite counts are computed without materializing join tables. Contingency table algebra is a new extension of relational algebra, that facilitates the efficient implementation of this Möobius virtual join operation. The Möbius Join scales to large datasets (over 1M tuples) with complex schemas. Empirical evaluation with seven benchmark datasets showed that information about the presence and absence of links can be exploited in feature selection, association rule mining, and Bayesian network learning.
Unsupervised Feature Selection for Multi-View Clustering on Text-Image Web News Data
Authors: Mingjie Qian, ChengXiang Zhai
Venue: CIKM
Year: 2014

Unlabeled high-dimensional text-image web news data are produced every day, presenting new challenges to unsupervised feature selection on multi-view data. State-of-the-art multi-view unsupervised feature selection methods learn pseudo class labels by spectral analysis, which is sensitive to the choice of similarity metric for each view. For text-image data, the raw text itself contains more discriminative information than similarity graph which loses information during construction, and thus the text feature can be directly used for label learning, avoiding information loss as in spectral analysis. We propose a new multi-view unsupervised feature selection method in which image local learning regularized orthogonal nonnegative matrix factorization is used to learn pseudo labels and simultaneously robust joint $l_{2,1}$-norm minimization is performed to select discriminative features. Cross-view consensus on pseudo labels can be obtained as much as possible. We systematically evaluate the proposed method in multi-view text-image web news datasets. Our extensive experiments on web news datasets crawled from two major US media channels: CNN and FOXNews demonstrate the efficacy of the new method over state-of-the-art multi-view and single-view unsupervised feature selection methods.
Towards Efficient Dissemination of Linked Data in the Internet of Things
Authors: Yongrui Qin, Quan Z. Sheng, Nickolas J. G. Falkner, Ali Shemshadi, Edward Curry
Venue: CIKM
Year: 2014

The Internet of Things (IoT) envisions smart objects collecting and sharing data at a global scale via the Internet. One challenging issue is how to disseminate data to relevant data consumers efficiently. In this paper, we leverage semantic technologies which can facilitate machine-to-machine communications, such as Linked Data, to build an efficient information dissemination system for semantic IoT. The system integrates Linked Data streams generated from various data collectors and disseminates matched data to relevant data consumers based on Basic Graph Patterns (BGPs) registered in the system by those consumers. To efficiently match BGPs against Linked Data streams, we introduce two types of matching, namely semantic matching and pattern matching, by considering whether the matching process supports semantic relatedness computation. Two new data structures, namely MVR-tree and TP-automata, are introduced to suit these types of matching respectively. Experiments show that an MVR-tree designed for semantic matching can achieve a twofold increase in throughput compared with the naive R-tree based method. TP-automata, as the first approach designed for pattern matching over Linked Data streams, also provides two to three orders of magnitude improvements on throughput compared with semantic matching approaches.
Indexing Linked Data in a Wireless Broadcast System with 3D Hilbert Space-Filling Curves
Authors: Yongrui Qin, Quan Z. Sheng, Nickolas J. G. Falkner, Wei Emma Zhang, Hua Wang
Venue: CIKM
Year: 2014

Semantic technologies aim to facilitate machine-to-machine communication and are attracting more and more interest from both academia and industry, especially in the emerging Internet of Things (IoT). In this paper, we consider large-scale information sharing scenarios among mobile objects in IoT by leveraging semantic techniques. We propose to broadcast Linked Data on-air using RDF format to allow simultaneous access to the information and to achieve better scalability. We introduce a novel air indexing method to reduce the information access latency and energy consumption. To build air indexes, we firstly map RDF triples in the Linked Data into points in a 3D space and build B+-trees based on 3D Hilbert curve mappings for all of the 3D points. We then convert these trees into linear sequences so that they can be broadcast over a wireless channel. A novel search algorithm is also designed to efficiently evaluate queries against the air indexes. Experiments show that our indexing method outperforms the air indexing method based on traditional 3D R-trees.