OpenRaiser/Intern-Atlas huggingface dataset:
Learning word sense disambiguation in biomedical text with difference between training and test distributions
Authors: Jeong Woo Son, Seong-Bae Park
Venue: CIKM
Year: 2009

Word sense disambiguation (WSD) is a crucial issue in bio-medical text mining since the performance of diverse biomedical text mining techniques strongly depends on the senses of lexicons. Thus, it is natural to consider lexicons as the most crucial features in WSD. However, due to the diversity of lexical space, WSD methods based on machine learning techniques with lexical features suffer from the difference between distributions of training and test documents. To tackle this problem, this paper proposes support vector machines with example-wise weights. In this method, the training distribution is made coincide with the test distribution by weighting training examples according to their similarity to all test data. The experimental results show that the distribution change between training and test data is actually recognized and the proposed method which considers this change in its training phase outperforms ordinary support vector machines.
Discovering matching dependencies
Authors: Shaoxu Song, Lei Chen
Venue: CIKM
Year: 2009

Matching dependencies (MDs) are recently proposed for various data quality applications such as detecting the violation of integrity constraints and duplicate object identification. In this paper, we study the problem of discovering matching dependencies for a given database instance. First, we formally define the measures, support and confidence, for evaluating the utility of MDs in the given database instance. Then, we study the discovery of MDs with certain utility requirements of support and confidence. Exact algorithms are developed, together with pruning strategies to improve the time performance. Finally, our experimental evaluation demonstrates the efficiency of the proposed methods.
Topic and keyword re-ranking for LDA-based topic modeling
Authors: Yangqiu Song, Shimei Pan, Shixia Liu, Michelle X. Zhou, Weihong Qian
Venue: CIKM
Year: 2009

Topic-based text summaries promise to help average users quickly understand a text collection and derive insights. Recent research has shown that the Latent Dirichlet Allocation (LDA) model is one of the most effective approaches to topic analysis. However, the LDA-based results may not be ideal for human understanding and consumption. In this paper, we present several topic and keyword re-ranking approaches that can help users better understand and consume the LDA-derived topics in their text analysis. Our methods process the LDA output based on a set of criteria that model a user's information needs. Our evaluation demonstrates the usefulness of the methods in summarizing several large-scale, real world data sets.
Hydra: a hybrid recommender system [cross-linked rating and content information]
Authors: Stephan Spiegel, Jérôme Kunegis, Fang Li
Venue: CIKM
Year: 2009

This paper discusses the combination of collaborative and content-based filtering in the context of web-based recommender systems. In particular, we link the well-known MovieLens rating data with supplementary IMDB content information. The resulting network of user-item relations and associated content features is converted into a unified mathematical model, which is applicable to our underlying neighbor-based prediction algorithm. By means of various experiments, we demonstrate the influence of supplementary user as well as item features on the prediction accuracy of Hydra, our proposed hybrid recommender. In order to decrease system runtime and to reveal latent user and item relations, we factorize our hybrid model via singular value decomposition (SVD).
Rank-aware clustering of structured datasets
Authors: Julia Stoyanovich, Sihem Amer-Yahia
Venue: CIKM
Year: 2009

In online applications such as Yahoo! Personals and Yahoo! Real Estate users define structured profiles in order to find potentially interesting matches. Typically, profiles are evaluated against large datasets and produce thousands of matches. In addition to filtering, users also specify ranking in their profile, and matches are returned in a ranked list. Top results in a list are typically homogeneous, which hinders data exploration. For example, a user looking for 1- or 2-bedroom apartments sorted by price will see a large number of cheap 1-bedrooms in undesirable neighborhoods before seeing a different apartment. An alternative to ranking is to group matches on common attribute values, e.g., cheap 1-bedrooms in good neighborhoods, 2-bedrooms with 2 baths, and choose groups in relationship with ranking. In this paper, we present a novel paradigm of rank-aware clustering, and demonstrate its effectiveness on a large dataset from Yahoo! Personals, a leading online dating site.
Learning to recommend questions based on user ratings
Authors: Ke Sun, Yunbo Cao, Xinying Song, Young-In Song, Xiaolong Wang, Chin-Yew Lin
Venue: CIKM
Year: 2009

At community question answering services, users are usually encouraged to rate questions by votes. The questions with the most votes are then recommended and ranked on the top when users browse questions by category. As users are not obligated to rate questions, usually only a small proportion of questions eventually gets rating. Thus, in this paper, we are concerned with learning to recommend questions from user ratings of a limited size. To overcome the data sparsity, we propose to utilize questions without users rating as well. Further, as there exist certain noises within user ratings (the preference of some users expressed in their ratings diverges from that of the majority of users), we design a new algorithm called 'majority-based perceptron algorithm' which can avoid the influence of noisy instances by emphasizing its learning over data instances from the majority users. Experimental results from a large collection of real questions confirm the effectiveness of our proposals.
Matching stream patterns of various lengths and tolerances
Authors: Huanliang Sun, Ke Deng, Fanyu Meng, Junling Liu
Venue: CIKM
Year: 2009

Continuously identifying pre-defined patterns in a streaming time series has strong demand in various applications. While most existing works assume the patterns are in equal length and tolerance, this work focuses on the problem where the patterns have various lengths and tolerances, a common situation in the real world. The challenge of this problem roots on the strict space and time requirements of processing the arriving and expiring data in high-speed stream, combined with difficulty of coping with a large number of patterns with various lengths and tolerances. We introduce a novel concept of converging envelope which bounds the tolerance of a group of patterns in various tolerances and equal length and thus dramatically reduces the number of patterns for similarity computation. The basic idea of converging envelope has potential to more general index problems. To index patterns in various lengths and tolerances, we partition patterns into sub-patterns in equal length and an multi-tree index is developed in this paper.
What makes categories difficult to classify?: a study on predicting classification performance for categories
Authors: Aixin Sun, Ee-Peng Lim, Ying Liu
Venue: CIKM
Year: 2009

In this paper, we try to predict which category will be less accurately classified compared with other categories in a classification task that involves multiple categories. The categories with poor predicted performance will be identified before any classifiers are trained and additional steps can be taken to address the predicted poor accuracies of these categories. Inspired by the work on query performance prediction in ad-hoc retrieval, we propose to predict classification performance using two measures, namely, category size and category coherence. Our experiments on 20-Newsgroup and Reuters-21578 datasets show that the Spearman rank correlation coefficient between the predicted rank of classification performance and the expected classification accuracy is as high as 0.9.
Independent informative subgraph mining for graph information retrieval
Authors: Bingjun Sun, Prasenjit Mitra, C. Lee Giles
Venue: CIKM
Year: 2009

In order to enable scalable querying of graph databases, intelligent selection of subgraphs to index is essential. An improved index can reduce response times for graph queries significantly. For a given subgraph query, graph candidates that may contain the subgraph are retrieved using the graph index and subgraph isomorphism tests are performed to prune out unsatisfied graphs. However, since the space of all possible subgraphs of the whole set of graphs is prohibitively large, feature selection is required to identify a good subset of subgraph features for indexing. Thus, one of the key issues is: given the set of all possible subgraphs of the graph set, which subset of features is the optimal such that the algorithm retrieves the smallest set of candidate graphs and reduces the number of subgraph isomorphism tests? We introduce a graph search method for subgraph queries based on subgraph frequencies. Then, we propose several novel feature selection criteria, Max-Precision, Max-Irredundant-Information, and Max-Information-Min-Redundancy, based on mutual information. Finally we show theoretically and empirically that our proposed methods retrieve a smaller candidate set than previous methods. For example, using the same number of features, our method improve the precision for the query candidate set by 4%-13% in comparison to previous methods. As a result the response time of subgraph queries also is improved correspondingly.
Learning to rank graphs for online similar graph search
Authors: Bingjun Sun, Prasenjit Mitra, C. Lee Giles
Venue: CIKM
Year: 2009

Many applications in structure matching require the ability to search for graphs that are similar to a query graph, i.e., similarity graph queries. Prior works, especially in chemoinformatics, have used the maximum common edge subgraph (MCEG) to compute the graph similarity. This approach is prohibitively slow for real-time queries. In this work, we propose an algorithm that extracts and indexes subgraph features from a graph dataset. It computes the similarity of graphs using a linear graph kernel based on feature weights learned offline from a training set generated using MCEG. We show empirically that our proposed algorithm of learning to rank graphs can achieve higher normalized discounted cumulative gain compared with existing optimal methods based on MCEG. The running time of our algorithm is orders of magnitude faster than these existing methods.
Injecting purpose and trust into data anonymisation
Authors: Xiaoxun Sun, Hua Wang, Jiuyong Li
Venue: CIKM
Year: 2009

Most existing works of data anonymisation target at the optimization of the anonymisation metrics to balance the data utility and privacy, whereas they ignore the effects of a requester's trust level and application purposes during the data anonymisation. Our aim of this paper is to propose a much finer level anonymisation scheme with regard to the data requester's trust value and specific application purpose. We prioritize the attributes for anonymisation based on how important and critical they are related to the specified application purposes and propose a trust evaluation strategy to quantify the data requester's reliability, and further build the projection between the trust value and the degree of data anonymiztion, which intends to determine to what extent the data should be anonymized. The decomposition algorithm is developed to find the desired anonymous solution, which guarantees the uniqueness and correctness.
A graph-based approach for biomedical thesaurus expansion
Authors: Ikumi Suzuki, Kazuo Hara, Masashi Shimbo, Yuji Matsumoto
Venue: CIKM
Year: 2009

The addition of new terms to biomedical thesauri is important for keeping pace with new research. In the context of a thesaurus expansion task, we investigate the property of Laplacian diffusion kernel matrices that depreciate pivotal vertices having many links to surrounding vertices. We confirm that this property can be seen on the Laplacian matrix of a graph that we construct from the GENIA corpus (a subset of MEDLINE abstracts) and simulate thesaurus expansion by employing either the Laplacian diffusion kernel matrix, or the adjacency matrix (i.e., cosine similarity), to determine the correct position for new biomedical terms being added to the MeSH thesaurus. Whilst results do not show the desired precision, our approach is shown to be complementary to calculation of cosine similarity between thesaurus terms and we recognize directions for future work.
Annotating wikipedia articles with semantic tags for structured retrieval
Authors: Saravadee Sae Tan, Tang Enya Kong, Gian Chand Sodhy
Venue: CIKM
Year: 2009

Structured retrieval aims at exploiting the structural information of documents when searching for documents. Structured retrieval makes use of both content and structure of documents to improve information retrieval. Therefore, the availability of semantic structure in the documents is an important factor for the success of structured retrieval. However, the majority of documents in the Web still lack semantically-rich structure. This motivates us to automatically identify the semantic information in web documents and explicitly annotate the information with semantic tags.
Scalable learning of collective behavior based on sparse social dimensions
Authors: Lei Tang, Huan Liu
Venue: CIKM
Year: 2009

The study of collective behavior is to understand how individuals behave in a social network environment. Oceans of data generated by social media like Facebook, Twitter, Flickr and YouTube present opportunities and challenges to studying collective behavior in a large scale. In this work, we aim to learn to predict collective behavior in social media. In particular, given information about some individuals, how can we infer the behavior of unobserved individuals in the same network? A social-dimension based approach is adopted to address the heterogeneity of connections presented in social media. However, the networks in social media are normally of colossal size, involving hundreds of thousands or even millions of actors. The scale of networks entails scalable learning of models for collective behavior prediction. To address the scalability issue, we propose an edge-centric clustering scheme to extract sparse social dimensions. With sparse social dimensions, the socialdimension based approach can efficiently handle networks of millions of actors while demonstrating comparable prediction performance as other non-scalable methods.
Self-organizing peer-to-peer networks for collaborative document tracking
Authors: Hathai Tanta-ngai, Evangelos E. Milios, Vlado Keselj
Venue: CIKM
Year: 2009

Given a set of peers with overlapping interests where each peer wishes to keep track of new documents that are relevant to their interests, we propose a self-organizing peer-to-peer document-tracking network based on common interest profiles. The goal of a document-tracking network is to disseminate new documents as they are published. Peers collaboratively share new documents of interest with other peers. There is no explicit profile exchange between peers and no global information available. We describe a strategy for peers to discover the existence of other peers and learn about their interests locally, based on information carried in the document metadata that propagates through the network. Peers are connected based on their observed common interests. We compare our proposed common interest strategy with a randomly connected network. The experimental results, based on simulated environment using the ACM digital library metadata, demonstrate that the proposed strategy gives the best dissemination performance. We also demonstrate that our self-organizing networks follow the characteristics of social networks.
Mining data streams with periodically changing distributions
Authors: Yingying Tao, M. Tamer Özsu
Venue: CIKM
Year: 2009

Dynamic data streams are those whose underlying distribution changes over time. They occur in a number of application domains, and mining them is important for these applications. Coupled with the unboundedness and high arrival rates of data streams, the dynamism of the underlying distribution makes data mining challenging. In this paper, we focus on a large class of dynamic streams that exhibit periodicity in distribution changes. We propose a framework, called DMM, for mining this class of streams that includes a new change detection technique and a novel match-and-reuse approach. Once a distribution change is detected, we compare the new distribution with a set of historically observed distribution patterns and use the mining results from the past if a match is detected. Since, for two highly similar distributions, their mining results should also present high similarity, by matching and reusing existing mining results, the overall stream mining efficiency is improved while the accuracy is maintained. Our experimental results confirm this conjecture.
Effective, design-independent XML keyword search
Authors: Arash Termehchy, Marianne Winslett
Venue: CIKM
Year: 2009

Keyword search techniques that take advantage of XML structure make it very easy for ordinary users to query XML databases, but current approaches to processing these queries rely on intuitively appealing heuristics that are ultimately ad hoc. These approaches often retrieve irrelevant answers, overlook relevant answers, and cannot rank answers appropriately. To address these problems for data-centric XML, we propose coherency ranking (CR), a domain- and database design-independent ranking method for XML keyword queries that is based on an extension of the concept of mutual information. With CR, the results of a keyword query are invariant under schema reorganization. We analyze how previous approaches to XML keyword search approximate CR, and present efficient algorithms to perform CR. Our empirical evaluation with 65 user-supplied queries over two real-world XML data sets shows that CR has better precision and recall and provides better ranking than all previous approaches.
iPoG: fast interactive proximity querying on graphs
Authors: Hanghang Tong, Huiming Qu, Hani Jamjoom, Christos Faloutsos
Venue: CIKM
Year: 2009

Given an author-conference graph, how do we answer proximity queries (e.g., what are the most related conferences for John Smith?); how can we tailor the search result if the user provides additional yes/no type of feedback (e.g., what are the most related conferences for John Smith given that he does not like ICML?)? Given the potential computational complexity, we mainly devote ourselves to addressing the computational issues in this paper by proposing an efficient solution (referred to as iPoG-B) for bipartite graphs. Our experimental results show that the proposed fast solution (iPoGB) achieves significant speedup, while leading to the same ranking result.
SAX: a privacy preserving general pupose methodapplied to detection of intrusions
Authors: François Trousset, Pascal Poncelet, Florent Masseglia
Venue: CIKM
Year: 2009

To overcome the problem of attacks on networks, new Intrusion Detection System (IDS) approaches have been proposed in recent years. They consist in identifying signatures of known attacks to compare them to each request and determine whether it is an attack or not. However, these methods are set to default when the attack is unknown from the database of signatures. Usually this problem is solved by calling human expertise to update the database of signatures. However, it is frequent that an attack has already been detected by another organization and it would be useful to be able to benefit from this knowledge to enrich the database of signatures. Unfortunately this information is not so easy to obtain. In fact organizations do not necessarily want to spread the information that they have already faced this type of attack. In this paper we propose a new approach to intrusion detection in a collaborative environment but by preserving the privacy of the collaborative organizations. Our approach works for any signature even if it needs a complex program to be detected and insure that no information is disclosed on the content of any of the sites. For this pupose, we have developped a general method (SAX) that allows to compute any algorithm while preserving privacy of data and also of the program code which is computed.
Predicting the volume of comments on online news stories
Authors: Manos Tsagkias, Wouter Weerkamp, Maarten de Rijke
Venue: CIKM
Year: 2009

On-line news agents provide commenting facilities for readers to express their views with regard to news stories. The number of user supplied comments on a news article may be indicative of its importance or impact. We report on exploratory work that predicts the comment volume of news articles prior to publication using five feature sets. We address the prediction task as a two stage classification task: a binary classification identifies articles with the potential to receive comments, and a second binary classification receives the output from the first step to label articles "low" or "high" comment volume. The results show solid performance for the former task, while performance degrades for the latter.
VRIFA: a nonlinear SVM visualization tool using nomogram and localized radial basis function (LRBF) kernels
Authors: Ngo Anh Vien, Nguyen Hoang Viet, TaeChoong Chung, Hwanjo Yu, Sungchul Kim, Baek Hwan Cho
Venue: CIKM
Year: 2009

Prediction problems are prevalent in medical domains. For example, computer-aided diagnosis or prognosis is a key component in a CDSS (Clinical Decision Support System). SVMs, especially SVMs with nonlinear kernels such RBF kernels, have shown superior accuracy in prediction problems. However, they are not favorably used by physicians for medical prediction problems because nonlinear SVMs are difficult to visualize, thus it is hard to provide intuitive interpretation of prediction results to physicians. Nomogram was proposed to visualize SVM classification models. However, it cannot visualize nonlinear SVM models. Localized RBF (LRBF) kernel was proposed which shows comparable accuracy as the RBF kernel while the LRBF kernel is easier to interpret since it can be linearly decomposed. This paper presents a new tool named VRIFA, which integrates the nomogram and LRBF kernel to provide users with an interactive visualization of nonlinear SVM models. VRIFA graphically exposes the internal structure of nonlinear SVM models showing the effect of each feature, the magnitude of the effect, and the change at the prediction output. VRIFA also performs nomogram-based feature selection while training a model in order to remove noise or redundant features and improve the prediction accuracy. The tool has been used by biomedical researchers for computer-aided diagnosis and risk factor analysis for diseases. VRIFA is accessible at http://dm.postech.ac.kr/vrifa .