OpenRaiser/Intern-Atlas huggingface dataset:
DELTA: indexing and querying multi-labeled graphs
Authors: Jiong Yang, Shijie Zhang, Wei Jin
Venue: CIKM
Year: 2011

With the emergence of social networks and computational biology, more data are in the forms of multi-labeled graphs, where a vertex has multiple labels. Since most algorithms focus only on single labeled graphs, these algorithms perform inefficiently when applied to multi-labeled graphs. In this paper, we investigate the problem of subgraph indexing and matching in the multi-labeled graphs. The label set on a vertex is transformed into a high dimensional box. The R-tree is employed to store and index these boxes. The vertex matching problem can be transformed into spatial range queries on the high dimensional space. In addition, we study two types of queries: location and existence queries. In this paper, detailed algorithms are provided to process these two types of queries. Real and synthetic data sets are employed to demonstrate the efficiency and effectiveness of our subgraph indexing and query processing methods.
Can irrelevant data help semi-supervised learning, why and how?
Authors: Haiqin Yang, Shenghuo Zhu, Irwin King, Michael R. Lyu
Venue: CIKM
Year: 2011

Previous semi-supervised learning (SSL) techniques usually assume unlabeled data are relevant to the target task. That is, they follow the same distribution as the targeted labeled data. In this paper, we address a different and very difficult scenario in SSL, where the unlabeled data may be a mixture of data relevant or irrelevant to the target binary classification task. In our framework, we do not require explicitly prior knowledge on the relatedness of the unlabeled data to the target data. In order to alleviate the effect of the irrelevant unlabeled data and utilize the implicit knowledge among all available data, we develop a novel maximum margin classifier, named the tri-class support vector machine (3C-SVM), to seek an inductive rule to separate the target binary classification task well while finding out the irrelevant data by-product. To attain this goal, we introduce a new min loss function, which can relieve the impact of the irrelevant data while relying more on the labeled data and the relevant unlabeled data. This loss function can therefore achieve the maximum entropy principle. The 3C-SVM can then generalize standard SVMs, Semi-supervised SVMs, and SVMs learned from the universum as its special cases. We further analyze the property of 3C-SVM on why the irrelevant data can help to improve the model performance. For implementation, we make relaxation and approximate the objective by the convex-concave procedure, which turns the original optimization from integral programming problem to a problem by just solving a finite number of quadratic programming problems. Empirical results are reported to demonstrate the advantages of our 3C-SVM model.
Extracting multi-dimensional relations: a generative model of groups of entities in a corpus
Authors: Ching-man Au Yeung, Tomoharu Iwata
Venue: CIKM
Year: 2011

Extracting relations among different entities from various data sources has been an important topic in data mining. While many methods focus only on a single type of relations, real world entities maintain relations that contain much richer information. We propose a hierarchical Bayesian model for extracting multi-dimensional relations among entities from a text corpus. Using data from Wikipedia, we show that our model can accurately predict the relevance of an entity given the topic of the document as well as the set of entities that are already mentioned in that document.
Modeling personalized email prioritization: classification-based and regression-based approaches
Authors: Shinjae Yoo, Yiming Yang, Jaime G. Carbonell
Venue: CIKM
Year: 2011

Email overload, even after spam filtering, presents a serious productivity challenge for busy professionals and executives. One solution is automated prioritization of incoming emails to ensure the most important are read and processed quickly, while others are processed later as/if time permits in declining priority levels. This paper presents a study of machine learning approaches to email prioritization into discrete levels, comparing ordinal regression versus classifier cascades. Given the ordinal nature of discrete email priority levels, SVM ordinal regression would be expected to perform well, but surprisingly a cascade of SVM classifiers significantly outperforms ordinal regression for email prioritization. In contrast, SVM regression performs well -- better than classifiers -- on selected UCI data sets. This unexpected performance inversion is analyzed and results are presented, providing core functionality for email prioritization systems.
Towards a top-down and bottom-up bidirectional approach to joint information extraction
Authors: Xiaofeng Yu, Irwin King, Michael R. Lyu
Venue: CIKM
Year: 2011

Most high-level information extraction (IE) consists of compound and aggregated subtasks. Such IE problems are generally challenging and they have generated increasing interest recently. We investigate two representative IE tasks: (1) entity identification and relation extraction from Wikipedia, and (2) citation matching, and we formally define joint optimization of information extraction. We propose a joint paradigm integrating three factors -- segmentation, relation, and segmentation-relation joint factors, to solve all relevant subtasks simultaneously. This modeling offers a natural formalism for exploiting bidirectional rich dependencies and interactions between relevant subtasks to capture mutual benefits. Since exact parameter estimation is prohibitively intractable, we present a general, highly-coupled learning algorithm based on variational expectation maximization (VEM) to perform parameter estimation approximately in a top-down and bottom-up manner, such that information can flow bidirectionally and mutual benefits from different subtasks can be well exploited. In this algorithm, both segmentation and relation are optimized iteratively and collaboratively using hypotheses from each other. We conducted extensive experiments using two real-world datasets to demonstrate the promise of our approach.
Promotional subspace mining with EProbe framework
Authors: Yan Zhang, Yiyu Jia, Wei Jin
Venue: CIKM
Year: 2011

In multidimensional data, Promotional Subspace Mining (PSM) aims to find out outstanding subspaces for a given object, and to discover meaningful rules from them. In PSM, one major research issue is to produce top subspaces efficiently given a predefined subspace ranking measure. A common approach is to achieve an exact solution, which searches through the entire subspace search space and evaluate the target object's rank in every subspace, assisted with possible pruning strategies. In this paper, we propose EProbe, an Efficient Subspace Probing framework. This novel framework strives to initialize the idea of "early stop" of the top subspace search process. The essential goal is to provide a scalable, cost-effective, and flexible solution where its accuracy can be traded with the efficiency using adjustable parameters. This framework is especially useful when the computation resources are insufficient and only a limited number of candidate subspaces can be evaluated. As a first attempt to seek solutions under EProbe framework, we propose two novel algorithms SRatio and SlidingCluster. In our experiments, we illustrate that these two algorithms could produce a more effective subspace traversal order. Being effective, the top-k subspaces included in the final results are shown to be evaluated in the early stage of the subspace traversal process.
A machine-learned proactive moderation system for auction fraud detection
Authors: Liang Zhang, Jie Yang, Wei Chu, Belle L. Tseng
Venue: CIKM
Year: 2011

Online auction and shopping are gaining popularity with the growth of web-based eCommerce. Criminals are also taking advantage of these opportunities to conduct fraudulent activities against honest parties with the purpose of deception and illegal profit. In practice, proactive moderation systems are deployed to detect suspicious events for further inspection by human experts. Motivated by real-world applications in commercial auction sites in Asia, we develop various advanced machine learning techniques in the proactive moderation system. Our proposed system is formulated as optimizing bounded generalized linear models in multi-instance learning problems, with intrinsic bias in selective labeling and massive unlabeled samples. In both offline evaluations and online bucket tests, the proposed system significantly outperforms the rule-based system on various metrics, including area under ROC (AUC), loss rate of labeled frauds and customer complaints. We also show that the metrics of loss rates are more effective than AUC in our cases.
TEXplorer: keyword-based object search and exploration in multidimensional text databases
Authors: Bo Zhao, Cindy Xide Lin, Bolin Ding, Jiawei Han
Venue: CIKM
Year: 2011

We propose a novel system TEXplorer that integrates keyword-based object ranking with the aggregation and exploration power of OLAP in a text database with rich structured attributes available, e.g., a product review database. TEXplorer can be implemented within a multi-dimensional text database, where each row is associated with structural dimensions (attributes) and text data (e.g., a document). The system utilizes the text cube data model, where a cell aggregates a set of documents with matching values in a subset of dimensions. Cells in a text cube capture different levels of summarization of the documents, and can represent objects at different conceptual levels.
Max margin learning on domain-independent web information extraction
Authors: Bin Zhao, Xiaoxin Yin, Eric P. Xing
Venue: CIKM
Year: 2011

Domain-independent web information extraction can be addressed as a structured prediction problem where we learn a mapping function from an input web page to the structured and interdependent output variables, labeling each block on the page. In this paper, built upon an HTML parser of Internet Explorer that parses and renders a web page based on HTML tags and visual appearance, we propose a max margin learning approach for web information extraction. Specifically, the output of the parser is a vision tree, which is similar to a DOM tree but with visual information, i.e., how each node is displayed. Based on this hierarchical structure, we develop a max margin learning method for labeling each of its nodes. Due to the rich connections between blocks on the web page, we further introduce edges that connect spatially adjacent nodes on the vision tree, complicating the problem into a cyclic graph labeling task. A max margin learning method on cyclic graphs is developed for this problem, where loopy belief propagation is used for approximate inference. Experimental results on web data extraction show the feasibility and promise of our approach.
Search result diversification for enterprise data
Authors: Wei Zheng, Hui Fang, Conglei Yao, Min Wang
Venue: CIKM
Year: 2011

Search result diversification aims to return a list of diversified relevant documents in order to satisfy different user information needs. Most of the efforts focused on Web Search, and few studies have considered another important search domain, i.e., enterprise search. Unlike Web search, enterprise search deals with both unstructured and structured data. In this paper, we propose to integrate the structured and unstructured data to discover meaningful query subtopics in search result diversification. Experimental results show that integrating structured and unstructured information allows us to discover high quality query, which are effective in diversifying the retrieval results.
A novel framework of training hidden markov support vector machines from lightly-annotated data
Authors: Deyu Zhou, Yulan He
Venue: CIKM
Year: 2011

Natural language understanding (NLU) aims to map sentences to their semantic mean representations. Statistical approaches to NLU normally require fully-annotated training data where each sentence is paired with its word-level semantic annotations. In this paper, we propose a novel learning framework which trains the Hidden Markov Support Vector Machines (HM-SVMs) without the use of expensive fully-annotated data. In particular, our learning approach takes as input a training set of sentences labeled with abstract semantic annotations encoding underlying embedded structural relations and automatically induces derivation rules that map sentences to their semantic meaning representations. The proposed approach has been tested on the DARPA Communicator Data and achieved 93.18% in F-measure, which outperforms the previously proposed approaches of training the hidden vector state model or conditional random fields from unaligned data, with a relative error reduction rate of 43.3% and 10.6% being achieved.
Efficient association discovery with keyword-based constraints on large graph data
Authors: Mo Zhou, Yifan Pan, Yuqing Wu
Venue: CIKM
Year: 2011

In many domains, such as social networks and chem-informatics, data can be represented naturally in graph model, with nodes being data entries and edges the relationships between them. We study the application requirements in these domains and find that discovering Constrained Acyclic Paths (CAP) is highly in demand. In this paper, we define the CAP search problem and introduce a set of quantitative metrics for describing keyword-based constraints. We propose a series of algorithms to efficiently evaluate CAP queries on large-scale graph data. Extensive experiments illustrate that our algorithms are both efficient and scalable.
Conkar: constraint keyword-based association discovery
Authors: Mo Zhou, Yifan Pan, Yuqing Wu
Venue: CIKM
Year: 2011

In many domains, such as bioinformatics, cheminformatics, health informatics and social networks, data can be represented naturally as labeled graphs. To address the increasing needs in discovering interesting associations between entities in such data graphs, especially under complicated keyword-based and structural constraints, we introduce Conkar (Constrained Keyword-based Association DiscoveRy) System. Conkar is the first system for discovering constrained acyclic paths (CAP) in graph data under keyword-based constraints, with the highlight being the set of quantitative constraint metrics that we proposed, including coverage and relevance. We will demonstrate the key features of Conkar: powerful and userfriendly query specification, efficient query evaluation, flexible and on-demand result ranking, visual result display, as well as an insight tour on our novel CAP query evaluation algorithms.
Towards expert finding by leveraging relevant categories in authority ranking
Authors: Hengshu Zhu, Huanhuan Cao, Hui Xiong, Enhong Chen, Jilei Tian
Venue: CIKM
Year: 2011

How to improve authority ranking is a crucial research problem for expert finding. In this paper, we propose a novel framework for expert finding based on the authority information in the target category as well as the relevant categories. First, we develop a scalable method for measuring the relevancy between categories through topic models. Then, we provide a link analysis approach for ranking user authority by considering the information in both the target category and the relevant categories. Finally, the extensive experiments on two large-scale real-world Q&A data sets clearly show that the proposed method outperforms the baseline methods with a significant margin.
High efficiency and quality: large graphs matching
Authors: Yuanyuan Zhu, Lu Qin, Jeffrey Xu Yu, Yiping Ke, Xuemin Lin
Venue: CIKM
Year: 2011

Graph matching plays an essential role in many real applications. In this paper, we study how to match two large graphs by maximizing the number of matched edges, which is known as maximum common subgraph matching and is NP-hard. To find exact matching, it cannot handle a graph with more than 30 nodes. To find an approximate matching, the quality can be very poor. We propose a novel two-step approach which can efficiently match two large graphs over thousands of nodes with high matching quality. In the first step, we propose an anchor-selection/expansion approach to compute a good initial matching. In the second step, we propose a new approach to refine the initial matching. We give the optimality of our refinement and discuss how to randomly refine the matching with different combinations. We conducted extensive testing using real and synthetic datasets, and will report our findings.
Transfer active learning
Authors: Zhenfeng Zhu, Xingquan Zhu, Yangdong Ye, Yue-Fei Guo, Xiangyang Xue
Venue: CIKM
Year: 2011

Active learning traditionally assumes that labeled and unlabeled samples are subject to the same distributions and the goal of an active learner is to label the most informative unlabeled samples. In reality, situations may exist that we may not have unlabeled samples from the same domain as the labeled samples (i.e. target domain), whereas samples from auxiliary domains might be available. Under such situations, an interesting question is whether an active learner can actively label samples from auxiliary domains to benefit the target domain. In this paper, we propose a transfer active learning method, namely Transfer Active SVM (TrAcSVM), which uses a limited number of target instances to iteratively discover and label informative auxiliary instances. TrAcSVM employs an extended sigmoid function as instance weight updating approach to adjust the models for prediction of (newly arrived) target data. Experimental results on real-world data sets demonstrate that TrAcSVM obtains better efficiency and prediction accuracy than its peers.
Insert-friendly XML containment labeling scheme
Authors: Canwei Zhuang, Ziyu Lin, Shaorong Feng
Venue: CIKM
Year: 2011

The labeling scheme is designed to label the XML nodes so that both ordered and un-ordered queries can be processed without accessing the original XML file. When XML data become dynamic, it is important to design a labeling scheme that can facilitate updates and support query processing efficiently. In this paper, we propose a novel containment labeling scheme called DXCL (Dynamic XML Containment Labeling) to effectively process updating in dynamic XML data. Compared with the existing dynamic labeling schemes, a distinguishing feature of DXCL is that DXCL is compact and efficient regardless of whether the documents are updated or not. DXCL uses fixed length integer numbers to label initial XML documents and hence yields compact label size and high query performance. When updates take place, DXCL also has high performance on both label updates and query processing especially in the case of skewed insertions. Experimental results conform the benefits of our approach over the previous dynamic schemes.
Data, health, and algorithmics: computational challenges for biomedicine
Authors: Justin Zobel
Venue: CIKM
Year: 2011

In the decade following the completion of the Human Genome Project in 2000, the cost of sequencing DNA fell by a factor of around a million, and continues to fall. Applications of sequencing in health include precise diagnosis of infection and disease, lifestyle management, and development of highly targeted treatments. However, the volume and complexity of the data produced by these technologies presents a severe computational challenge. Breakthroughs in methods for search, storage, and analysis are required to keep pace with the flow of data, and to make use of the changes in biomedical knowledge that these technologies are creating. This keynote is an overview of some of these technologies and the new computational obstacles they have engendered, and reviews examples of algorithmic innovations and approaches currently being explored. These illustrate both the kinds of solutions that are required and the challenges that must be addressed to allow this data to be fully exploited.
Object ranking
Authors: Roelof van Zwol, Srinivas Vadrevu
Venue: CIKM
Year: 2011

Object ranking is an emerging discipline within information retrieval that is concerned with the ranking of objects, e.g. named entities and their attributes, in context of given a user query, or application. In this tutorial we will address the different aspects involved when building an object ranking system. We will present the state-of-the-art research in object ranking, as well as going into detail about our hands-on experiences when designing and developing the system for object ranking as it is in production at Yahoo! today. This allows for a unique mixture of research and development that will give the participants in-depth insights into the problem of object ranking.
Clinical clarity versus terminological order: the readiness of SNOMED CT concept descriptors for primary care
Authors: Zhe He, Michael Halper, Yehoshua Perl, Gai Elhanan
Venue: CIKM
Year: 2012

As SNOMED usage becomes more ingrained within applications, its range of concept descriptors, and particularly its synonym adequacy, becomes more important. A simulated clinical scenario involving various term-based concept searches is used to assess whether SNOMED's concept descriptors provide sufficient differentiation to enable possible concept selection between similar terms. Four random samples from different SNOMED concept populations are utilized. Of particular interest are concepts mapped duplicately into UMLS concepts due to shared term patterns. While overall synonym problems are rare (1%), some concept populations exhibited a high rate of potential problems for clinical use (17-62%). The vast majority of issues are due to SNOMED's inherent structure and fine granularity. Many findings hint at a lack of clear delineation between reference and interface terminological qualities. Closer attention should be given to practical clinical use-case scenarios. Reducing SNOMED's structural complexity may alleviate many of the described findings and encourage clinical adoption.
Identifying and characterizing user communities on Twitter during crisis events
Authors: Aditi Gupta, Anupam Joshi, Ponnurangam Kumaraguru
Venue: CIKM
Year: 2012

Twitter is a prominent online social media which is used to share information and opinions. Previous research has shown that current real world news topics and events dominate the discussions on Twitter. In this paper, we present a preliminary study to identify and characterize communities from a set of users who post messages on Twitter during crisis events. We present our work in progress by analyzing three major crisis events of 2011 as case studies (Hurricane Irene, Riots in England, and Earthquake in Virginia). Hurricane Irene alone, caused a damage of about 7-10 billion USD and claimed 56 lives. The aim of this paper is to identify the different user communities, and characterize them by the top central users. First, we defined a similarity metric between users based on their links, content posted and meta-data. Second, we applied spectral clustering to obtain communities of users formed during three different crisis events. Third, we evaluated the mechanism to identify top central users using degree centrality; we showed that the top users represent the topics and opinions of all the users in the community with 81% accuracy on an average. The top central people identified represent what the entire community shares. Therefore to understand a community, we need to monitor and analyze only these top users rather than all the users in a community.