text:
tackle this problem. This work proposes a relaxing function as part of the prior and updates the parameters with the likelihood function in terms of the consistency between the true label information and predicted result. This work presents two Gibbs sampling algorithms to perform posterior inference. In the experiments, the online CRP is applied to three massive data sets, and compared with several online learning and batch learning algorithms. One of the data sets is obtained from Wikipedia, which comprises approximately two million documents. The experimental results reveal that the proposed online CRP performs well and efficiently on massive data sets. Finally, this work proposes two methods to update the hyperparameter $alpha$ of the online CRP. The first method is based on the posterior distribution of $alpha$, and the second exploits the property of online learning, namely adapting to change, to adjust $alpha$ dynamically.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {591–600},
numpages = {10},
keywords = {chinese restaurant process, nonparametric, adaptive learning, online learning},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623623,
author = {Dong, Xin and Gabrilovich, Evgeniy and Heitz, Geremy and Horn, Wilko and Lao, Ni and Murphy, Kevin and Strohmann, Thomas and Sun, Shaohua and Zhang, Wei},
title = {Knowledge Vault: A Web-Scale Approach to Probabilistic Knowledge Fusion},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623623},
doi = {10.1145/2623330.2623623},
abstract = {Recent years have witnessed a proliferation of large-scale knowledge bases, including Wikipedia, Freebase, YAGO, Microsoft's Satori, and Google's Knowledge Graph. To increase the scale even further, we need to explore automatic methods for constructing knowledge bases. Previous approaches have primarily focused on text-based extraction, which can be very noisy. Here we introduce Knowledge Vault, a Web-scale probabilistic knowledge base that combines extractions from Web content (obtained via analysis of text, tabular data, page structure, and human annotations) with prior knowledge derived from existing knowledge repositories. We employ supervised machine learning methods for fusing these distinct information sources. The Knowledge Vault is substantially bigger than any previously published structured knowledge repository, and features a probabilistic inference system that computes calibrated probabilities of fact correctness. We report the results of multiple studies that explore the relative utility of the different information sources and extraction methods.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {601–610},
numpages = {10},
keywords = {information extraction, probabilistic models, machine learning, knowledge bases},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623614,
author = {Wang, Shusen and Zhang, Chao and Qian, Hui and Zhang, Zhihua},
title = {Improving the Modified Nystr\"{o}m Method Using Spectral Shifting},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623614},
doi = {10.1145/2623330.2623614},
abstract = {The Nystrom method is an efficient approach to enabling large-scale kernel methods. The Nystrom method generates a fast approximation to any large-scale symmetric positive semidefinete (SPSD) matrix using only a few columns of the SPSD matrix. However, since the Nystrom approximation is low-rank, when the spectrum of the SPSD matrix decays slowly, the Nystrom approximation is of low accuracy. In this paper, we propose a variant of the Nystrom method called the modified Nystrom by spectral shifting (SS-Nystrom). The SS-Nystrom method works well no matter whether the spectrum of SPSD matrix decays fast or slow. We prove that our SS-Nystrom has a much stronger error bound than the standard and modified Nystrom methods, and that SS-Nystrom can be even more accurate than the truncated SVD of the same scale in some cases. We also devise an algorithm such that the SS-Nystrom approximation can be computed nearly as efficient as the modified Nystrom approximation. Finally, our SS-Nystrom method demonstrates significant improvements over the standard and modified Nystrom methods on several real-world datasets.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {611–620},
numpages = {10},
keywords = {kernel approximation, the nystr\"{o}m method, large-scale machine learning},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623627,
author = {Chen, Wenlin and Chen, Yixin and Weinberger, Kilian Q.},
title = {Fast Flux Discriminant for Large-Scale Sparse Nonlinear Classification},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623627},
doi = {10.1145/2623330.2623627},
abstract = {In this paper, we propose a novel supervised learning method, Fast Flux Discriminant (FFD), for large-scale nonlinear classification. Compared with other existing methods, FFD has unmatched advantages, as it attains the efficiency and interpretability of linear models as well as the accuracy of nonlinear models. It is also sparse and naturally handles mixed data types. It works by decomposing the kernel density estimation in the entire feature space into selected low-dimensional subspaces. Since there are many possible subspaces, we propose a submodular optimization framework for subspace selection. The selected subspace predictions are then transformed to new features on which a linear model can be learned. Besides, since the transformed features naturally expect non-negative weights, we only require smooth optimization even with the L1 regularization. Unlike other nonlinear models such as kernel methods, the FFD model is interpretable as it gives importance weights on the original features. Its training and testing are also much faster than traditional kernel models. We carry out extensive empirical studies on real-world datasets and show that the proposed model achieves state-of-the-art classification results with sparsity, interpretability, and exceptional scalability. Our model can be learned in minutes on datasets with millions of samples, for which most existing nonlinear methods will be prohibitively expensive in space and time.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {621–630},
numpages = {10},
keywords = {submodularity, classification, interpretability, sparsity},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623640,
author = {Tang, Mingwang and Li, Feifei},
title = {Scalable Histograms on Large Probabilistic Data},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623640},
doi = {10.1145/2623330.2623640},
abstract = {Histogram construction is a fundamental problem in data management, and a good histogram supports numerous mining operations. Recent work has extended histograms to probabilistic data. However, constructing histograms for probabilistic data can be extremely expensive, and existing studies suffer from limited scalability. This work designs novel approximation methods to construct scalable histograms on probabilistic data. We show that our methods provide constant approximations compared to the optimal histograms produced by the state-of-the-art in the worst case. We also extend our methods to parallel and distributed settings so that they can run gracefully in a cluster of commodity machines. We introduced novel synopses to reduce communication cost when running our methods in such settings. Extensive experiments on large real data sets have demonstrated the superb scalability and efficiency achieved by our methods, when compared to the state-of-the-art methods. They also achieved excellent approximation quality in practice.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {631–640},
numpages = {10},
keywords = {scalable method, probabilistic database, histogram},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623743,
author = {Chierichetti, Flavio and Dalvi, Nilesh and Kumar, Ravi},
title = {Correlation Clustering in MapReduce},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623743},
doi = {10.1145/2623330.2623743},
abstract = {Correlation clustering is a basic primitive in data miner's toolkit with applications ranging from entity matching to social network analysis. The goal in correlation clustering is, given a graph with signed edges, partition the nodes into clusters to minimize the number of disagreements. In this paper we obtain a new algorithm for correlation clustering. Our algorithm is easily implementable in computational models such as MapReduce and streaming, and runs in a small number of rounds. In addition, we show that our algorithm obtains an almost 3-approximation to the optimal correlation clustering. Experiments on huge graphs demonstrate the scalability of our algorithm and its applicability to data mining problems.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {641–650},
numpages = {10},
keywords = {scalable clustering, signed networks.},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623615,
author = {Anagnostopoulos, Christos and Triantafillou, Peter},
title = {Scaling out Big Data Missing Value Imputations: Pythia vs. Godzilla},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623615},
doi = {10.1145/2623330.2623615},
abstract = {Solving the missing-value (MV) problem with small estimation errors in big data environments is a notoriously resource-demanding task. As datasets and their user community continuously grow, the problem can only be exacerbated. Assume that it is possible to have a single machine (`Godzilla'), which can store the massive dataset and support an ever-growing community submitting MV imputation requests. Is it possible to replace Godzilla by employing a large number of cohort machines so that imputations can be performed much faster, engaging cohorts in parallel, each of which accesses much smaller partitions of the original dataset? If so, it would be preferable for obvious performance reasons to access only a subset of all cohorts per imputation. In this case, can we decide swiftly which is the desired subset of cohorts to engage per imputation? But efficiency and scalability is just one key concern! Is it possible to do the above while ensuring comparable or even better than Godzilla's imputation estimation errors? In this paper we derive answers to these fundamentals questions and develop principled methods and a framework which offer large performance speed-ups and better, or comparable, errors to that of Godzilla, independently of which missing-value imputation algorithm is used. Our contributions involve Pythia, a framework and algorithms for providing the answers to the above questions and for engaging the appropriate subset of cohorts per MV imputation request. Pythia functionality rests on two pillars: (i) dataset (partition) signatures, one per cohort, and (ii) similarity notions and algorithms, which can identify the appropriate subset of cohorts to engage. Comprehensive experimentation with real and synthetic datasets showcase our efficiency, scalability, and accuracy claims.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {651–660},
numpages = {10},
keywords = {missing value, clustering, big data},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623612,
author = {Li, Mu and Zhang, Tong and Chen, Yuqiang and Smola, Alexander J.},
title = {Efficient Mini-Batch Training for Stochastic Optimization},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623612},
doi = {10.1145/2623330.2623612},
abstract = {Stochastic gradient descent (SGD) is a popular technique for large-scale optimization problems in machine learning. In order to parallelize SGD, minibatch training needs to be employed to reduce the communication cost. However, an increase in minibatch size typically decreases the rate of convergence. This paper introduces a technique based on approximate optimization of a conservatively regularized objective function within each minibatch. We prove that the convergence rate does not decrease with increasing minibatch size. Experiments demonstrate that with suitable implementations of approximate optimization, the resulting algorithm can outperform standard SGD in many scenarios.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {661–670},
numpages = {10},
keywords = {minibatch, machine learning, stochastic gradient descent, big data, distributed computing},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623637,
author = {Badanidiyuru, Ashwinkumar and Mirzasoleiman, Baharan and Karbasi, Amin and Krause, Andreas},
title = {Streaming Submodular Maximization: Massive Data Summarization on the Fly},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623637},
doi = {10.1145/2623330.2623637},
abstract = {How can one summarize a massive data set "on the fly", i.e., without even having seen it in its entirety? In this paper, we address the problem of extracting representative elements from a large stream of data. I.e., we would like to select a subset of say k data points from the stream that are most representative according to some objective function. Many natural notions of "representativeness" satisfy submodularity, an intuitive notion of diminishing returns. Thus, such problems can be reduced to maximizing a submodular set function subject to a cardinality constraint. Classical approaches to submodular maximization require full access to the data set. We develop the first efficient streaming algorithm with constant factor 1/2-ε approximation guarantee to the optimum solution, requiring only a single pass through the data, and memory independent of data size. In our experiments, we extensively evaluate the effectiveness of our approach on several applications, including training large-scale kernel methods and exemplar-based clustering, on millions of data points. We observe that our streaming method, while achieving practically the same utility value, runs about 100 times faster than previous work.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {671–680},
numpages = {10},
keywords = {streaming algorithms, submodular functions},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623680,
author = {Cohen, Edith},
title = {Distance Queries from Sampled Data: Accurate and Efficient},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623680},
doi = {10.1145/2623330.2623680},
abstract = {Distance queries are a basic tool in data analysis. They are used for detection and localization of change for the purpose of anomaly detection, monitoring, or planning. Distance queries are particularly useful when data sets such as measurements, snapshots of a system, content, traffic matrices, and activity logs are collected repeatedly. Random sampling, which can be efficiently performed over streamed or distributed data, is an important tool for scalable data analysis. The sample constitutes an extremely flexible summary, which naturally supports domain queries and scalable estimation of statistics, which can be specified after the sample is generated. The effectiveness of a sample as a summary, however, hinges on the estimators we have.We derive novel estimators for estimating $L_p$ distance from sampled data. Our estimators apply with the most common weighted sampling schemes: Poisson Probability Proportional to Size (PPS) and its fixed sample size variants. They also apply when the samples of different data sets are independent or coordinated. Our estimators are admissible (Pareto optimal in terms of variance) and have compelling properties.We study the performance of our Manhattan and Euclidean distance (p=1,2) estimators on diverse datasets, demonstrating scalability and accuracy even when a small fraction of the data is sampled. Our work, for the first time, facilitates effective distance estimation over sampled data.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {681–690},
numpages = {10},
keywords = {poisson sampling, manhattan distance, bottom-k sampling, euclidean distance, distance queries},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623736,
author = {Li, Yi and Wang, Zhengyu and Woodruff, David P.},
title = {Improved Testing of Low Rank Matrices},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623736},
doi = {10.1145/2623330.2623736},
abstract = {We study the problem of determining if an input matrix A εRm x n can be well-approximated by a low rank matrix. Specifically, we study the problem of quickly estimating the rank or stable rank of A, the latter often providing a more robust measure of the rank. Since we seek significantly sublinear time algorithms, we cast these problems in the property testing framework. In this framework, A either has low rank or stable rank, or is far from having this property. The algorithm should read only a small number of entries or rows of A and decide which case A is in with high probability. If neither case occurs, the output is allowed to be arbitrary. We consider two notions of being far: (1) A requires changing at least an ε-fraction of its entries, or (2) A requires changing at least an ε-fraction of its rows. We call the former the "entry model" and the latter the "row model". We show: For testing if a matrix has rank at most d in the entry model, we improve the previous number of entries of A that need to be read from O(d2/ε2) (Krauthgamer and Sasson, SODA 2003) to O(d2/ε). Our algorithm is the first to adaptively query the entries of A, which for constant d we show is necessary to achieve O(1/ε) queries. For the important case of d = 1 we also give a new non-adaptive algorithm, improving the previous O(1/ε2) queries to O(log2(1/ε) / ε).For testing if a matrix has rank at most d in the row model, we prove an Ω(d/ε) lower bound on the number of rows that need to be read, even for adaptive algorithms. Our lower bound matches a non-adaptive upper bound of Krauthgamer and Sasson.For testing if a matrix has stable rank at most d in the row model or requires changing an ε/d-fraction of its rows in order to have stable rank at most d, we prove that reading θ(d/ε2) rows is necessary and sufficient. We also give an empirical evaluation of our rank and stable rank algorithms on real and synthetic datasets.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {691–700},
numpages = {10},
keywords = {principal component analysis, stable rank, property testing, robustness, dimensionality reduction},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623732,
author = {Perozzi, Bryan and Al-Rfou, Rami and Skiena, Steven},
title = {DeepWalk: Online Learning of Social Representations},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623732},
doi = {10.1145/2623330.2623732},
abstract = {We present DeepWalk, a novel approach for learning latent representations of vertices in a network. These latent representations encode social relations in a continuous vector space, which is easily exploited by statistical models. DeepWalk generalizes recent advancements in language modeling and unsupervised feature learning (or deep learning) from sequences of words to graphs.DeepWalk uses local information obtained from truncated random walks to learn latent representations by treating walks as the equivalent of sentences. We demonstrate DeepWalk's latent representations on several multi-label network classification tasks for social networks such as BlogCatalog, Flickr, and YouTube. Our results show that DeepWalk outperforms challenging baselines which are allowed a global view of the network, especially in the presence of missing information. DeepWalk's representations can provide F1 scores up to 10% higher than competing methods when labeled data is sparse. In some experiments, DeepWalk's representations are able to outperform all baseline methods while using 60% less training data.DeepWalk is also scalable. It is an online learning algorithm which builds useful incremental results, and is trivially parallelizable. These qualities make it suitable for a broad class of real world applications such as network classification, and anomaly detection.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {701–710},
numpages = {10},
keywords = {latent representations, deep learning, learning with partial labels, online learning, social networks, network classification},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623749,
author = {Sarawagi, Sunita and Chakrabarti, Soumen},
title = {Open-Domain Quantity Queries on Web Tables: Annotation, Response, and Consensus Models},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623749},
doi = {10.1145/2623330.2623749},
abstract = {Over 40% of columns in hundreds of millions of Web tables contain numeric quantities. Tables are a richer source of structured knowledge than free text. We harness Web tables to answer queries whose target is a quantity with natural variation, such as net worth of zuckerburg, battery life of ipad, half life of plutonium, and calories in pizza. Our goal is to respond to such queries with a ranked list of quantity distributions, suitably represented. Apart from the challenges of informal schema and noisy extractions, which have been known since tables were used for non-quantity information extraction, we face additional problems of noisy number formats, as well as unit specifications that are often contextual and ambiguous.Early "hardening" of extraction decisions at a table level leads to poor accuracy. Instead, we use a probabilistic context free grammar (PCFG) based unit extractor on the tables, and retain several top-scoring extractions of quantity and numerals. Then we inject these into a new collective inference framework that makes global decisions about the relevance of candidate table snippets, the interpretation of the query's target quantity type, the value distributions to be ranked and presented, and the degree of consensus that can be built to support the proposed quantity distributions. Experiments with over 25 million Web tables and 350 diverse queries show robust, large benefits from our quantity catalog, unit extractor, and collective inference.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {711–720},
numpages = {10},
keywords = {collective inference, number and unit extraction, web tables},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623625,
author = {Wu, Bin and Zhong, Erheng and Tan, Ben and Horner, Andrew and Yang, Qiang},
title = {Crowdsourced Time-Sync Video Tagging Using Temporal and Personalized Topic Modeling},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623625},
doi = {10.1145/2623330.2623625},
abstract = {Time-sync video tagging aims to automatically generate tags for each video shot. It can improve the user's experience in previewing a video's timeline structure compared to traditional schemes that tag an entire video clip. In this paper, we propose a new application which extracts time-sync video tags by automatically exploiting crowdsourced comments from video websites such as Nico Nico Douga, where videos are commented on by online crowd users in a time-sync manner. The challenge of the proposed application is that users with bias interact with one another frequently and bring noise into the data, while the comments are too sparse to compensate for the noise. Previous techniques are unable to handle this task well as they consider video semantics independently, which may overfit the sparse comments in each shot and thus fail to provide accurate modeling. To resolve these issues, we propose a novel temporal and personalized topic model that jointly considers temporal dependencies between video semantics, users' interaction in commenting, and users' preferences as prior knowledge. Our proposed model shares knowledge across video shots via users to enrich the short comments, and peels off user interaction and user bias to solve the noisy-comment problem. Log-likelihood analyses and user studies on large datasets show that the proposed model outperforms several state-of-the-art baselines in video tagging quality. Case studies also demonstrate our model's capability of extracting tags from the crowdsourced short and noisy comments.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {721–730},
numpages = {10},
keywords = {temporal and personalized model, video tagging, crowdsourcing, topic modeling},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623679,
author = {Li, Liangda and Deng, Hongbo and Dong, Anlei and Chang, Yi and Zha, Hongyuan},
title = {Identifying and Labeling Search Tasks via Query-Based Hawkes Processes},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623679},
doi = {10.1145/2623330.2623679},
abstract = {We consider a search task as a set of queries that serve the same user information need. Analyzing search tasks from user query streams plays an important role in building a set of modern tools to improve search engine performance. In this paper, we propose a probabilistic method for identifying and labeling search tasks based on the following intuitive observations: queries that are issued temporally close by users in many sequences of queries are likely to belong to the same search task, meanwhile, different users having the same information needs tend to submit topically coherent search queries. To capture the above intuitions, we directly model query temporal patterns using a special class of point processes called Hawkes processes, and combine topic models with Hawkes processes for simultaneously identifying and labeling search tasks. Essentially, Hawkes processes utilize their self-exciting properties to identify search tasks if influence exists among a sequence of queries for individual users, while the topic model exploits query co-occurrence across different users to discover the latent information needed for labeling search tasks. More importantly, there is mutual reinforcement between Hawkes processes and the topic model in the unified model that enhances the performance of both. We evaluate our method based on both synthetic data and real-world query log data. In addition, we also apply our model to query clustering and search task identification. By comparing with state-of-the-art methods, the results demonstrate that the improvement in our proposed approach is consistent and promising.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {731–740},
numpages = {10},
keywords = {search task, variational inference, hawkes process, latent dirichlet allocation},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623761,
author = {Polozov, Oleksandr and Gulwani, Sumit},
title = {LaSEWeb: Automating Search Strategies over Semi-Structured Web Data},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623761},
doi = {10.1145/2623330.2623761},
abstract = {We show how to programmatically model processes that humans use when extracting answers to queries (e.g., "Who invented typewriter?", "List of Washington national parks") from semi-structured Web pages returned by a search engine. This modeling enables various applications including automating repetitive search tasks, and helping search engine developers design micro-segments of factoid questions.We describe the design and implementation of a domain-specific language that enables extracting data from a webpage based on its structure, visual layout, and linguistic patterns. We also describe an algorithm to rank multiple answers extracted from multiple webpages.On 100,000+ queries (across 7 micro-segments) obtained from Bing logs, our system LaSEWeb answered queries with an average recall of 71%. Also, the desired answer(s) were present in top-3 suggestions for 95%+ cases.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {741–750},
numpages = {10},
keywords = {question answering., structure extraction, domain-specific languages, semi-structured data, web programming},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623650,
author = {Liang, Shangsong and Ren, Zhaochun and de Rijke, Maarten},
title = {Personalized Search Result Diversification via Structured Learning},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623650},
doi = {10.1145/2623330.2623650},
abstract = {This paper is concerned with the problem of personalized diversification of search results, with the goal of enhancing the performance of both plain diversification and plain personalization algorithms. In previous work, the problem has mainly been tackled by means of unsupervised learning. To further enhance the performance, we propose a supervised learning strategy. Specifically, we set up a structured learning framework for conducting supervised personalized diversification, in which we add features extracted directly from the tokens of documents and those utilized by unsupervised personalized diversification algorithms, and, importantly, those generated from our proposed user-interest latent Dirichlet topic model. Based on our proposed topic model whether a document can cater to a user's interest can be estimated in our learning strategy. We also define two constraints in our structured learning framework to ensure that search results are both diversified and consistent with a user's interest. We conduct experiments on an open personalized diversification dataset and find that our supervised learning strategy outperforms unsupervised personalized diversification methods as well as other plain personalization and plain diversification methods.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {751–760},
numpages = {10},
keywords = {ad hoc retrieval, structured svms, personalization, diversity},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623641,
author = {Gong, Pinghua and Zhou, Jiayu and Fan, Wei and Ye, Jieping},
title = {Efficient Multi-Task Feature Learning with Calibration},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623641},
doi = {10.1145/2623330.2623641},
abstract = {Multi-task feature learning has been proposed to improve the generalization performance by learning the shared features among multiple related tasks and it has been successfully applied to many real-world problems in machine learning, data mining, computer vision and bioinformatics. Most existing multi-task feature learning models simply assume a common noise level for all tasks, which may not be the case in real applications. Recently, a Calibrated Multivariate Regression (CMR) model has been proposed, which calibrates different tasks with respect to their noise levels and achieves superior prediction performance over the non-calibrated one. A major challenge is how to solve the CMR model efficiently as it is formulated as a composite optimization problem consisting of two non-smooth terms. In this paper, we propose a variant of the calibrated multi-task feature learning formulation by including a squared norm regularizer. We show that the dual problem of the proposed formulation is a smooth optimization problem with a piecewise sphere constraint. The simplicity of the dual problem enables us to develop fast dual optimization algorithms with low per-iteration cost. We also provide a detailed convergence analysis for the proposed dual optimization algorithm. Empirical studies demonstrate that, the dual optimization algorithm quickly converges and it is much more efficient than the primal optimization algorithm. Moreover, the calibrated multi-task feature learning algorithms with and without the squared norm regularizer achieve similar prediction performance and both outperform the non-calibrated ones. Thus, the proposed variant not only enables us to develop fast optimization algorithms, but also keeps the superior prediction performance of the calibrated multi-task feature learning over the non-calibrated one.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {761–770},
numpages = {10},
keywords = {calibration, dual problem, accelerated gradient descent, feature selection, multi-task learning},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623697,
author = {Zhou, Tianyi and Tao, Dacheng},
title = {Multi-Task Copula by Sparse Graph Regression},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623697},
doi = {10.1145/2623330.2623697},
abstract = {This paper proposes multi-task copula (MTC) that can handle a much wider class of tasks than mean regression with Gaussian noise in most former multi-task learning (MTL). While former MTL emphasizes shared structure among models, MTC aims at joint prediction to exploit inter-output correlation. Given input, the outputs of MTC are allowed to follow arbitrary joint continuous distribution. MTC captures the joint likelihood of multi-output by learning the marginal of each output firstly and then a sparse and smooth output dependency graph function. While the former can be achieved by classical MTL, learning graphs dynamically varying with input is quite a challenge. We address this issue by developing sparse graph regression (SpaGraphR), a non-parametric estimator incorporating kernel smoothing, maximum likelihood, and sparse graph structure to gain fast learning algorithm. It starts from a few seed graphs on a few input points, and then updates the graphs on other input points by a fast operator via coarse-to-fine propagation. Due to the power of copula in modeling semi-parametric distributions, SpaGraphR can model a rich class of dynamic non-Gaussian correlations. We show that MTC can address more flexible and difficult tasks that do not fit the assumptions of former MTL nicely, and can fully exploit their relatedness. Experiments on robotic control and stock price prediction justify its appealing performance in challenging MTL problems.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {771–780},
numpages = {10},
keywords = {semi-parametric model, copula, sparse structured learning, covariance regression, multi-task learning},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623739,
author = {Zhou, Mianwei and Chang, Kevin C.},
title = {Unifying Learning to Rank and Domain Adaptation: Enabling Cross-Task Document Scoring},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623739},
doi = {10.1145/2623330.2623739},
abstract = {For document scoring, although learning to rank and domain adaptation are treated as two different problems in previous works, we discover that they actually share the same challenge of adapting keyword contribution across different queries or domains. In this paper, we propose to study the cross-task document scoring problem, where a task refers to a query to rank or a domain to adapt to, as the first attempt to unify these two problems. Existing solutions for learning to rank and domain adaptation either leave the heavy burden of adapting keyword contribution to feature designers, or are difficult to be generalized. To resolve such limitations, we abstract the keyword scoring principle, pointing out that the contribution of a keyword essentially depends on, first, its importance to a task and, second, its importance to the document. For determining these two aspects of keyword importance, we further propose the concept of feature decoupling, suggesting using two types of easy-to-design features: meta-features and intra-features. Towards learning a scorer based on the decoupled features, we require that our framework fulfill inferred sparsity to eliminate the interference of noisy keywords, and employ distant supervision to tackle the lack of keyword labels. We propose the Tree-structured Boltzmann Machine (T-RBM), a novel two-stage Markov Network, as our solution. Experiments on three different applications confirm the effectiveness of T-RBM, which achieves significant improvement compared with four state-of-the-art baseline methods.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {781–790},
numpages = {10},
keywords = {domain adaptation, feature decoupling, learning to rank, tree-structured restricted boltzmann machine},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623688,
author = {Wei, Ying and Song, Yangqiu and Zhen, Yi and Liu, Bo and Yang, Qiang},
title = {Scalable Heterogeneous Translated Hashing},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623688},
doi = {10.1145/2623330.2623688},
abstract = {Hashing has enjoyed a great success in large-scale similarity search. Recently, researchers have studied the multi-modal hashing to meet the need of similarity search across different types of media. However, most of the existing methods are applied to search across multi-views among which explicit bridge information is provided. Given a heterogeneous media search task, we observe that abundant multi-view data can be found on the Web which can serve as an auxiliary bridge. In this paper, we propose a Heterogeneous Translated Hashing (HTH) method with such auxiliary bridge incorporated not only to improve current multi-view search but also to enable similarity search across heterogeneous media which have no direct correspondence. HTH simultaneously learns hash functions embedding heterogeneous media into different Hamming spaces, and translators aligning these spaces. Unlike almost all existing methods that map heterogeneous data in a common Hamming space, mapping to different spaces provides more flexible and discriminative ability. We empirically verify the effectiveness and efficiency of our algorithm on two real world large datasets, one publicly available dataset of Flickr and the other MIRFLICKR-Yahoo Answers dataset.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {791–800},
numpages = {10},
keywords = {scalability, heterogeneous translated hashing, hash function learning},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623657,
author = {Li, Chung-Yi and Lin, Shou-De},
title = {Matching Users and Items across Domains to Improve the Recommendation Quality},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623657},
doi = {10.1145/2623330.2623657},
abstract = {Given two homogeneous rating matrices with some overlapped users/items whose mappings are unknown, this paper aims at answering two questions. First, can we identify the unknown mapping between the users and/or items? Second, can we further utilize the identified mappings to improve the quality of recommendation in either domain? Our solution integrates a latent space matching procedure and a refining process based on the optimization of prediction to identify the matching. Then, we further design a transfer-based method to improve the recommendation performance. Using both synthetic and real data, we have done extensive experiments given different real life scenarios to verify the effectiveness of our models. The code and other materials are available at http://www.csie.ntu.edu.tw/~r00922051/matching/},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {801–810},
numpages = {10},
keywords = {matrix factorization, transfer learning, collaborative filtering},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623744,
author = {Lu, Wei and Ioannidis, Stratis and Bhagat, Smriti and Lakshmanan, Laks V.S.},
title = {Optimal Recommendations under Attraction, Aversion, and Social Influence},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623744},
doi = {10.1145/2623330.2623744},
abstract = {People's interests are dynamically evolving, often affected by external factors such as trends promoted by the media or adopted by their friends. In this work, we model interest evolution through dynamic interest cascades: we consider a scenario where a user's interests may be affected by (a) the interests of other users in her social circle, as well as (b) suggestions she receives from a recommender system. In the latter case, we model user reactions through either attraction or aversion towards past suggestions. We study this interest evolution process, and the utility accrued by recommendations, as a function of the system's recommendation strategy. We show that, in steady state, the optimal strategy can be computed as the solution of a semi-definite program (SDP). Using datasets of user ratings, we provide evidence for the existence of aversion and attraction in real-life data, and show that our optimal strategy can lead to significantly improved recommendations over systems that ignore aversion and attraction.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {811–820},
numpages = {10},
keywords = {aversion, interest evolution, attraction, recommender systems},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623630,
author = {Ren, Xiang and Liu, Jialu and Yu, Xiao and Khandelwal, Urvashi and Gu, Quanquan and Wang, Lidan and Han, Jiawei},
title = {ClusCite: Effective Citation Recommendation by Information Network-Based Clustering},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623630},
doi = {10.1145/2623330.2623630},
abstract = {Citation recommendation is an interesting but challenging research problem. Most existing studies assume that all papers adopt the same criterion and follow the same behavioral pattern in deciding relevance and authority of a paper. However, in reality, papers have distinct citation behavioral patterns when looking for different references, depending on paper content, authors and target venues. In this study, we investigate the problem in the context of heterogeneous bibliographic networks and propose a novel cluster-based citation recommendation framework, called ClusCite, which explores the principle that citations tend to be softly clustered into interest groups based on multiple types of relationships in the network. Therefore, we predict each query's citations based on related interest groups, each having its own model for paper authority and relevance. Specifically, we learn group memberships for objects and the significance of relevance features for each interest group, while also propagating relative authority between objects, by solving a joint optimization problem. Experiments on both DBLP and PubMed datasets demonstrate the power of the proposed approach, with 17.68% improvement in Recall@50 and 9.57% growth in MRR over the best performing baseline.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {821–830},
numpages = {10},
keywords = {heterogeneous information network, citation behavioral pattern, clustering, citation recommendation},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623638,
author = {Lian, Defu and Zhao, Cong and Xie, Xing and Sun, Guangzhong and Chen, Enhong and Rui, Yong},
title = {GeoMF: Joint Geographical Modeling and Matrix Factorization for Point-of-Interest Recommendation},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623638},
doi = {10.1145/2623330.2623638},
abstract = {Point-of-Interest (POI) recommendation has become an important means to help people discover attractive locations. However, extreme sparsity of user-POI matrices creates a severe challenge. To cope with this challenge, viewing mobility records on location-based social networks (LBSNs) as implicit feedback for POI recommendation, we first propose to exploit weighted matrix factorization for this task since it usually serves collaborative filtering with implicit feedback better. Besides, researchers have recently discovered a spatial clustering phenomenon in human mobility behavior on the LBSNs, i.e., individual visiting locations tend to cluster together, and also demonstrated its effectiveness in POI recommendation, thus we incorporate it into the factorization model. Particularly, we augment users' and POIs' latent factors in the factorization model with activity area vectors of users and influence area vectors of POIs, respectively. Based on such an augmented model, we not only capture the spatial clustering phenomenon in terms of two-dimensional kernel density estimation, but we also explain why the introduction of such a phenomenon into matrix factorization helps to deal with the challenge from matrix sparsity. We then evaluate the proposed algorithm on a large-scale LBSN dataset. The results indicate that weighted matrix factorization is superior to other forms of factorization models and that incorporating the spatial clustering phenomenon into matrix factorization improves recommendation performance.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {831–840},
numpages = {10},
keywords = {weighted matrix factorization, location-based social network, kernel density estimation, location recommendation},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623721,
author = {G\"{u}nnemann, Stephan and G\"{u}nnemann, Nikou and Faloutsos, Christos},
title = {Detecting Anomalies in Dynamic Rating Data: A Robust Probabilistic Model for Rating Evolution},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623721},
doi = {10.1145/2623330.2623721},
abstract = {Rating data is ubiquitous on websites such as Amazon, TripAdvisor, or Yelp. Since ratings are not static but given at various points in time, a temporal analysis of rating data provides deeper insights into the evolution of a product's quality. In this work, we tackle the following question: Given the time stamped rating data for a product or service, how can we detect the general rating behavior of users as well as time intervals where the ratings behave anomalous? We propose a Bayesian model that represents the rating data as sequence of categorical mixture models. In contrast to existing methods, our method does not require any aggregation of the input but it operates on the original time stamped data. To capture the dynamic effects of the ratings, the categorical mixtures are temporally constrained: Anomalies can occur in specific time intervals only and the general rating behavior should evolve smoothly over time. Our method automatically determines the intervals where anomalies occur, and it captures the temporal effects of the general behavior by using a state space model on the natural parameters of the categorical distributions. For learning our model, we propose an efficient algorithm combining principles from variational inference and dynamic programming. In our experimental study we show the effectiveness of our method and we present interesting discoveries on multiple real world datasets.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {841–850},
numpages = {10},
keywords = {robust mining, categorical mixtures, anomaly detection},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623692,
author = {Xu, Silei and Lui, John Chi-Shing},
title = {Product Selection Problem: Improve Market Share by Learning Consumer Behavior},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623692},
doi = {10.1145/2623330.2623692},
abstract = {It is often crucial for manufacturers to decide what products to produce so that they can increase their market share in an increasingly fierce market. To decide which products to produce, manufacturers need to analyze the consumers' requirements and how consumers make their purchase decisions so that the new products will be competitive in the market. In this paper, we first present a general distance-based product adoption model to capture consumers' purchase behavior. Using this model, various distance metrics can be used to describe different real life purchase behavior. We then provide a learning algorithm to decide which set of distance metrics one should use when we are given some historical purchase data. Based on the product adoption model, we formalize the k most marketable products (or k-MMP) selection problem and formally prove that the problem is NP-hard. To tackle this problem, we propose an efficient greedy-based approximation algorithm with a provable solution guarantee. Using submodularity analysis, we prove that our approximation algorithm can achieve at least 63% of the optimal solution. We apply our algorithm on both synthetic datasets and real-world datasets (TripAdvisor.com), and show that our algorithm can easily achieve five or more orders of speedup over the exhaustive search and achieve about 96% of the optimal solution on average. Our experiments also show the significant impact of different distance metrics on the results, and how proper distance metrics can improve the accuracy of product selection.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {851–860},
numpages = {10},
keywords = {consumer behavior, model learning, product selection, submodular set function, approximation algorithm},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623647,
author = {Tong, Yongxin and Cao, Caleb Chen and Chen, Lei},
title = {TCS: Efficient Topic Discovery over Crowd-Oriented Service Data},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623647},
doi = {10.1145/2623330.2623647},
abstract = {In recent years, with the widespread usage of Web 2.0 techniques, crowdsourcing plays an important role in offering human intelligence in various service websites, such as Yahoo! Answer and Quora. With the increasing amount of crowd-oriented service data, an important task is to analyze latest hot topics and track topic evolution over time. However, the existing techniques in text mining cannot effectively work due to the unique structure of crowd-oriented service data, task-response pairs, which consists of the task and its corresponding responses. In particular, existing approaches become ineffective with the ever-increasing crowd-oriented service data that accumulate along the time. In this paper, we first study the problem of discovering topics over crowd-oriented service data. Then we propose a new probabilistic topic model, the Topic Crowd Service Model (TCS model), to effectively discover latent topics from massive crowd-oriented service data. In particular, in order to train TCS efficiently, we design a novel parameter inference algorithm, the Bucket Parameter Estimation (BPE), which utilizes belief propagation and a new sketching technique, called Pairwise Sketch (pSketch). Finally, we conduct extensive experiments to verify the effectiveness and efficiency of the TCS model and the BPE algorithm.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {861–870},
numpages = {10},
keywords = {crowd-oriented service, crowdsourcing, probabilistic topic model},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623740,
author = {Schubert, Erich and Weiler, Michael and Kriegel, Hans-Peter},
title = {SigniTrend: Scalable Detection of Emerging Topics in Textual Streams by Hashed Significance Thresholds},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623740},
doi = {10.1145/2623330.2623740},
abstract = {Social media such as Twitter or weblogs are a popular source for live textual data. Much of this popularity is due to the fast rate at which this data arrives, and there are a number of global events - such as the Arab Spring - where Twitter is reported to have had a major influence. However, existing methods for emerging topic detection are often only able to detect events of a global magnitude such as natural disasters or celebrity deaths, and can monitor user-selected keywords or operate on a curated set of hashtags only. Interesting emerging topics may, however, be of much smaller magnitude and may involve the combination of two or more words that themselves are not unusually hot at that time. Our contributions to the detection of emerging trends are three-fold first of all, we propose a significance measure that can be used to detect emerging topics early, long before they become "hot tags", by drawing upon experience from outlier detection. Secondly, by using hash tables in a heavy-hitters type algorithm for establishing a noise baseline, we show how to track even all keyword pairs using only a fixed amount of memory. Finally, we aggregate the detected co-trends into larger topics using clustering approaches, as often as a single event will cause multiple word combinations to trend at the same time.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {871–880},
numpages = {10},
keywords = {hashing, trend detection, text-mining, outlier detection},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623691,
author = {Buntine, Wray L. and Mishra, Swapnil},
title = {Experiments with Non-Parametric Topic Models},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623691},
doi = {10.1145/2623330.2623691},
abstract = {In topic modelling, various alternative priors have been developed, for instance asymmetric and symmetric priors for the document-topic and topic-word matrices respectively, the hierarchical Dirichlet process prior for the document-topic matrix and the hierarchical Pitman-Yor process prior for the topic-word matrix. For information retrieval, language models exhibiting word burstiness are important. Indeed, this burstiness effect has been show to help topic models as well, and this requires additional word probability vectors for each document. Here we show how to combine these ideas to develop high-performing non-parametric topic models exhibiting burstiness based on standard Gibbs sampling. Experiments are done to explore the behavior of the models under different conditions and to compare the algorithms with previously published. The full non-parametric topic models with burstiness are only a small factor slower than standard Gibbs sampling for LDA and require double the memory, making them very competitive. We look at the comparative behaviour of different models and present some experimental insights.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {881–890},
numpages = {10},
keywords = {text, topic modelling, non-parametric prior, experimental results},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623756,
author = {Li, Aaron Q. and Ahmed, Amr and Ravi, Sujith and Smola, Alexander J.},
title = {Reducing the Sampling Complexity of Topic Models},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623756},
doi = {10.1145/2623330.2623756},
abstract = {Inference in topic models typically involves a sampling step to associate latent variables with observations. Unfortunately the generative model loses sparsity as the amount of data increases, requiring O(k) operations per word for k topics. In this paper we propose an algorithm which scales linearly with the number of actually instantiated topics kd in the document. For large document collections and in structured hierarchical models kd ll k. This yields an order of magnitude speedup. Our method applies to a wide variety of statistical models such as PDP [16,4] and HDP [19].At its core is the idea that dense, slowly changing distributions can be approximated efficiently by the combination of a Metropolis-Hastings step, use of sparsity, and amortized constant time sampling via Walker's alias method.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {891–900},
numpages = {10},
keywords = {alias method, topic models, scalability, sampling},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623670,
author = {Tsytsarau, Mikalai and Palpanas, Themis and Castellanos, Malu},
title = {Dynamics of News Events and Social Media Reaction},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623670},
doi = {10.1145/2623330.2623670},
abstract = {The analysis of social sentiment expressed on the Web is becoming increasingly relevant to a variety of applications, and it is important to understand the underlying mechanisms which drive the evolution of sentiments in one way or another, in order to be able to predict these changes in the future. In this paper, we study the dynamics of news events and their relation to changes of sentiment expressed on relevant topics. We propose a novel framework, which models the behavior of news and social media in response to events as a convolution between event's importance and media response function, specific to media and event type. This framework is suitable for detecting time and duration of events, as well as their impact and dynamics, from time series of publication volume. These data can greatly enhance events analysis; for instance, they can help distinguish important events from unimportant, or predict sentiment and stock market shifts. As an example of such application, we extracted news events for a variety of topics and then correlated this data with the corresponding sentiment time series, revealing the connection between sentiment shifts and event dynamics.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {901–910},
numpages = {10},
keywords = {sentiment analysis, social media, news dynamics, information spread},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623642,
author = {Xiao, Qian and Chen, Rui and Tan, Kian-Lee},
title = {Differentially Private Network Data Release via Structural Inference},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623642},
doi = {10.1145/2623330.2623642},
abstract = {Information networks, such as social media and email networks, often contain sensitive information. Releasing such network data could seriously jeopardize individual privacy. Therefore, we need to sanitize network data before the release. In this paper, we present a novel data sanitization solution that infers a network's structure in a differentially private manner. We observe that, by estimating the connection probabilities between vertices instead of considering the observed edges directly, the noise scale enforced by differential privacy can be greatly reduced. Our proposed method infers the network structure by using a statistical hierarchical random graph (HRG) model. The guarantee of differential privacy is achieved by sampling possible HRG structures in the model space via Markov chain Monte Carlo (MCMC). We theoretically prove that the sensitivity of such inference is only O(log n), where n is the number of vertices in a network. This bound implies less noise to be injected than those of existing works. We experimentally evaluate our approach on four real-life network datasets and show that our solution effectively preserves essential network structural properties like degree distribution, shortest path length distribution and influential nodes.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {911–920},
numpages = {10},
keywords = {differential privacy, network data, structural inference},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623683,
author = {Lu, Wentian and Miklau, Gerome},
title = {Exponential Random Graph Estimation under Differential Privacy},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623683},
doi = {10.1145/2623330.2623683},
abstract = {The effective analysis of social networks and graph-structured data is often limited by the privacy concerns of individuals whose data make up these networks. Differential privacy offers individuals a rigorous and appealing guarantee of privacy. But while differentially private algorithms for computing basic graph properties have been proposed, most graph modeling tasks common in the data mining community cannot yet be carried out privately. In this work we propose algorithms for privately estimating the parameters of exponential random graph models (ERGMs). We break the estimation problem into two steps: computing private sufficient statistics, then using them to estimate the model parameters. We consider specific alternating statistics that are in common use for ERGM models and describe a method for estimating them privately by adding noise proportional to a high-confidence bound on their local sensitivity. In addition, we propose an estimation algorithm that considers the noise distribution of the private statistics and offers better accuracy than performing standard parameter estimation using the private statistics.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {921–930},
numpages = {10},
keywords = {differential privacy, exponential random graph model},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623723,
author = {Lee, Jaewoo and Clifton, Christopher W.},
title = {Top-k Frequent Itemsets via Differentially Private FP-Trees},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623723},
doi = {10.1145/2623330.2623723},
abstract = {Frequent itemset mining is a core data mining task and has been studied extensively. Although by their nature, frequent itemsets are aggregates over many individuals and would not seem to pose a privacy threat, an attacker with strong background information can learn private individual information from frequent itemsets. This has lead to differentially private frequent itemset mining, which protects privacy by giving inexact answers. We give an approach that first identifies top-k frequent itemsets, then uses them to construct a compact, differentially private FP-tree. Once the noisy FP-tree is built, the (privatized) support of all frequent itemsets can be derived from it without access to the original data. Experimental results show that the proposed algorithm gives substantially better results than prior approaches, especially for high levels of privacy.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {931–940},
numpages = {10},
keywords = {frequent itemset, fp-tree, differential privacy},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623632,
author = {Jiang, Meng and Cui, Peng and Beutel, Alex and Faloutsos, Christos and Yang, Shiqiang},
title = {CatchSync: Catching Synchronized Behavior in Large Directed Graphs},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623632},
doi = {10.1145/2623330.2623632},
abstract = {Given a directed graph of millions of nodes, how can we automatically spot anomalous, suspicious nodes, judging only from their connectivity patterns? Suspicious graph patterns show up in many applications, from Twitter users who buy fake followers, manipulating the social network, to botnet members performing distributed denial of service attacks, disturbing the network traffic graph. We propose a fast and effective method, CatchSync, which exploits two of the tell-tale signs left in graphs by fraudsters: (a) synchronized behavior: suspicious nodes have extremely similar behavior pattern, because they are often required to perform some task together (such as follow the same user); and (b) rare behavior: their connectivity patterns are very different from the majority. We introduce novel measures to quantify both concepts ("synchronicity" and "normality") and we propose a parameter-free algorithm that works on the resulting synchronicity-normality plots. Thanks to careful design, CatchSync has the following desirable properties: (a) it is scalable to large datasets, being linear on the graph size; (b) it is parameter free; and (c) it is side-information-oblivious: it can operate using only the topology, without needing labeled data, nor timing information, etc., while still capable of using side information, if available. We applied CatchSync on two large, real datasets 1-billion-edge Twitter social graph and 3-billion-edge Tencent Weibo social graph, and several synthetic ones; CatchSync consistently outperforms existing competitors, both in detection accuracy by 36% on Twitter and 20% on Tencent Weibo, as well as in speed.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {941–950},
numpages = {10},
keywords = {anomalous behavior, outlier detection, zombie follower},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623705,
author = {Zhu, Hengshu and Xiong, Hui and Ge, Yong and Chen, Enhong},
title = {Mobile App Recommendations with Security and Privacy Awareness},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623705},
doi = {10.1145/2623330.2623705},
abstract = {With the rapid prevalence of smart mobile devices, the number of mobile Apps available has exploded over the past few years. To facilitate the choice of mobile Apps, existing mobile App recommender systems typically recommend popular mobile Apps to mobile users. However, mobile Apps are highly varied and often poorly understood, particularly for their activities and functions related to privacy and security. Therefore, more and more mobile users are reluctant to adopt mobile Apps due to the risk of privacy invasion and other security concerns. To fill this crucial void, in this paper, we propose to develop a mobile App recommender system with privacy and security awareness. The design goal is to equip the recommender system with the functionality which allows to automatically detect and evaluate the security risk of mobile Apps. Then, the recommender system can provide App recommendations by considering both the Apps' popularity and the users' security preferences. Specifically, a mobile App can lead to security risk because insecure data access permissions have been implemented in this App. Therefore, we first develop the techniques to automatically detect the potential security risk for each mobile App by exploiting the requested permissions. Then, we propose a flexible approach based on modern portfolio theory for recommending Apps by striking a balance between the Apps' popularity and the users' security concerns, and build an App hash tree to efficiently recommend Apps. Finally, we evaluate our approach with extensive experiments on a large-scale data set collected from Google Play. The experimental results clearly validate the effectiveness of our approach.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {951–960},
numpages = {10},
keywords = {security and privacy, mobile apps, recommender systems},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623713,
author = {Fang, Xiaomin and Pan, Rong},
title = {Fast DTT: A near Linear Algorithm for Decomposing a Tensor into Factor Tensors},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623713},
doi = {10.1145/2623330.2623713},
abstract = {As tensors provide a natural representation for the higher-order relations, tensor factorization techniques such as Tucker decomposition and CANDECOMP/PARAFAC decomposition have been applied to many fields. Tucker decomposition has strong capacity of expression, but the time complexity is unpractical for the large-scale real problems. On the other hand, CANDECOMP/PARAFAC decomposition is linear in the feature dimensionality, but the assumption is so strong that it abandons some important information. Besides, both of TD and CP decompose a tensor into several factor matrices. However, the factor matrices are not natural for the representation of the higher-order relations. To overcome these problems, we propose a near linear tensor factorization approach, which decompose a tensor into factor tensors in order to model the higher-order relations, without loss of important information. In addition, to reduce the time complexity and the number of the parameters, we decompose each slice of the factor tensors into two smaller matrices. We conduct experiments on both synthetic datasets and real datasets. The experimental results on the synthetic datasets validate that our model has strong capacity of expression. The results on the real datasets show that our approach outperforms the state-of-the-art tensor factorization methods.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {967–976},
numpages = {10},
keywords = {DTT, tensor decomposition},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623726,
author = {Nie, Feiping and Wang, Xiaoqian and Huang, Heng},
title = {Clustering and Projected Clustering with Adaptive Neighbors},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623726},
doi = {10.1145/2623330.2623726},
abstract = {Many clustering methods partition the data groups based on the input data similarity matrix. Thus, the clustering results highly depend on the data similarity learning. Because the similarity measurement and data clustering are often conducted in two separated steps, the learned data similarity may not be the optimal one for data clustering and lead to the suboptimal results. In this paper, we propose a novel clustering model to learn the data similarity matrix and clustering structure simultaneously. Our new model learns the data similarity matrix by assigning the adaptive and optimal neighbors for each data point based on the local distances. Meanwhile, the new rank constraint is imposed to the Laplacian matrix of the data similarity matrix, such that the connected components in the resulted similarity matrix are exactly equal to the cluster number. We derive an efficient algorithm to optimize the proposed challenging problem, and show the theoretical analysis on the connections between our method and the K-means clustering, and spectral clustering. We also further extend the new clustering model for the projected clustering to handle the high-dimensional data. Extensive empirical results on both synthetic data and real-world benchmark data sets show that our new clustering methods consistently outperforms the related clustering approaches.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {977–986},
numpages = {10},
keywords = {clustering, adaptive neighbors, clustering with dimensionality reduction, block diagonal similarity matrix},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623671,
author = {Chen, Xilun and Candan, K. Selcuk},
title = {LWI-SVD: Low-Rank, Windowed, Incremental Singular Value Decompositions on Time-Evolving Data Sets},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623671},
doi = {10.1145/2623330.2623671},
abstract = {Singular Value Decomposition (SVD) is computationally costly and therefore a naive implementation does not scale to the needs of scenarios where data evolves continuously. While there are various on-line analysis and incremental decomposition techniques, these may not accurately represent the data or may be slow for the needs of many applications. To address these challenges, in this paper, we propose a Low-rank, Windowed, Incremental SVD (LWI-SVD) algorithm, which (a) leverages efficient and accurate low-rank approximations to speed up incremental SVD updates and (b) uses a window-based approach to aggregate multiple incoming updates (insertions or deletions of rows and columns) and, thus, reduces on- line processing costs. We also present an LWI-SVD with restarts (LWI2-SVD) algorithm which leverages a novel highly efficient partial reconstruction based change detection scheme to support timely refreshing of the decomposition with significant changes in the data and prevent accumulation of errors over time. Experiment results, including comparisons to other state of the art techniques on different data sets and under different parameter settings, confirm that LWI-SVD and LWI2-SVD are both efficient and accurate in maintaining decompositions.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {987–996},
numpages = {10},
keywords = {data streams, incremental singular value decomposition},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623698,
author = {Papailiopoulos, Dimitris and Kyrillidis, Anastasios and Boutsidis, Christos},
title = {Provable Deterministic Leverage Score Sampling},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623698},
doi = {10.1145/2623330.2623698},
abstract = {We explain theoretically a curious empirical phenomenon: "Approximating a matrix by deterministically selecting a subset of its columns with the corresponding largest leverage scores results in a good low-rank matrix surrogate". In this work, we provide a novel theoretical analysis of deterministic leverage score sampling. We show that such sampling can be provably as accurate as its randomized counterparts, if the leverage scores follow a moderately steep power-law decay. We support this power-law assumption by providing empirical evidence that such decay laws are abundant in real-world data sets. We then demonstrate empirically the performance of deterministic leverage score sampling, which many times matches or outperforms the state-of-the-art techniques.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {997–1006},
numpages = {10},
keywords = {deterministic sampling, low-rank matrix approximation, subset selection, leverage scores, power law distributions},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623620,
author = {Le, Tuan M.V. and Lauw, Hady W.},
title = {Semantic Visualization for Spherical Representation},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623620},
doi = {10.1145/2623330.2623620},
abstract = {Visualization of high-dimensional data such as text documents is widely applicable. The traditional means is to find an appropriate embedding of the high-dimensional representation in a low-dimensional visualizable space. As topic modeling is a useful form of dimensionality reduction that preserves the semantics in documents, recent approaches aim for a visualization that is consistent with both the original word space, as well as the semantic topic space. In this paper, we address the semantic visualization problem. Given a corpus of documents, the objective is to simultaneously learn the topic distributions as well as the visualization coordinates of documents. We propose to develop a semantic visualization model that approximates L2-normalized data directly. The key is to associate each document with three representations: a coordinate in the visualization space, a multinomial distribution in the topic space, and a directional vector in a high-dimensional unit hypersphere in the word space. We join these representations in a unified generative model, and describe its parameter estimation through variational inference. Comprehensive experiments on real-life text datasets show that the proposed method outperforms the existing baselines on objective evaluation metrics for visualization quality and topic interpretability.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1007–1016},
numpages = {10},
keywords = {generative model, semantic visualization, topic model, L2-normalized vector, dimensionality reduction, spherical semantic embedding, spherical space},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623748,
author = {Agrawal, Rakesh and Golshan, Behzad and Terzi, Evimaria},
title = {Grouping Students in Educational Settings},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623748},
doi = {10.1145/2623330.2623748},
abstract = {Given a class of large number of students, each exhibiting a different ability level, how can we group them into sections so that the overall gain for students is maximized? This question has been a topic of central concern and debate amongst social scientists and policy makers for a long time. We propose a framework for rigorously studying this question, taking a computational perspective. We present a formal definition of the grouping problem and investigate some of its variants. Such variants are determined by the desired number of groups as well as the definition of the gain for each student in the group. We focus on two natural instantiations of the gain function and we show that for both of them the problem of identifying a single group of students that maximizes the gain among its members can be solved in polynomial time. The corresponding partitioning problem, where the goal is to partition the students into non-overlapping groups appear to be much harder. However, the algorithms for the single-group version can be leveraged for solving the more complex partitioning problem. Our experiments with generated data coming from different distributions demonstrate that our algorithm is significantly better than the current strategies in vogue for dividing students in a class into sections.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1017–1026},
numpages = {10},
keywords = {large classes, teams, massive courses, clustering, MOOC, groups, partitioning},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623653,
author = {Shang, Jingbo and Zheng, Yu and Tong, Wenzhu and Chang, Eric and Yu, Yong},
title = {Inferring Gas Consumption and Pollution Emission of Vehicles throughout a City},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623653},
doi = {10.1145/2623330.2623653},
abstract = {This paper instantly infers the gas consumption and pollution emission of vehicles traveling on a city's road network in a current time slot, using GPS trajectories from a sample of vehicles (e.g., taxicabs). The knowledge can be used to suggest cost-efficient driving routes as well as identifying road segments where gas has been wasted significantly. The instant estimation of the emissions from vehicles can enable pollution alerts and help diagnose the root cause of air pollution in the long run. In our method, we first compute the travel speed of each road segment using the GPS trajectories received recently. As many road segments are not traversed by trajectories (i.e., data sparsity), we propose a Travel Speed Estimation (TSE) model based on a context-aware matrix factorization approach. TSE leverages features learned from other data sources, e.g., map data and historical trajectories, to deal with the data sparsity problem. We then propose a Traffic Volume Inference (TVI) model to infer the number of vehicles passing each road segment per minute. TVI is an unsupervised Bayesian Network that incorporates multiple factors, such as travel speed, weather conditions and geographical features of a road. Given the travel speed and traffic volume of a road segment, gas consumption and emissions can be calculated based on existing environmental theories. We evaluate our method based on extensive experiments using GPS trajectories generated by over 32,000 taxis in Beijing over a period of two months. The results demonstrate the advantages of our method over baselines, validating the contribution of its components and finding interesting discoveries for the benefit of society.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1027–1036},
numpages = {10},
keywords = {traffic pollution, gas consumption, urban computing, spatial trajectories.},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623654,
author = {Raman, Karthik and Joachims, Thorsten},
title = {Methods for Ordinal Peer Grading},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623654},
doi = {10.1145/2623330.2623654},
abstract = {Massive Online Open Courses have the potential to revolutionize higher education with their wide outreach and accessibility, but they require instructors to come up with scalable alternates to traditional student evaluation. Peer grading -- having students assess each other -- is a promising approach to tackling the problem of evaluation at scale, since the number of "graders" naturally scales with the number of students. However, students are not trained in grading, which means that one cannot expect the same level of grading skills as in traditional settings. Drawing on broad evidence that ordinal feedback is easier to provide and more reliable than cardinal feedback [5, 38, 29, 9], it is therefore desirable to allow peer graders to make ordinal statements (e.g. "project X is better than project Y") and not require them to make cardinal statements (e.g. "project X is a B-"). Thus, in this paper we study the problem of automatically inferring student grades from ordinal peer feedback, as opposed to existing methods that require cardinal peer feedback. We formulate the ordinal peer grading problem as a type of rank aggregation problem, and explore several probabilistic models under which to estimate student grades and grader reliability. We study the applicability of these methods using peer grading data collected from a real class --- with instructor and TA grades as a baseline --- and demonstrate the efficacy of ordinal feedback techniques in comparison to existing cardinal peer grading methods. Finally, we compare these peer-grading techniques to traditional evaluation techniques.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1037–1046},
numpages = {10},
keywords = {ordinal feedback, rank aggregation, peer grading},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623675,
author = {Fu, Yanjie and Xiong, Hui and Ge, Yong and Yao, Zijun and Zheng, Yu and Zhou, Zhi-Hua},
title = {Exploiting Geographic Dependencies for Real Estate Appraisal: A Mutual Perspective of Ranking and Clustering},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623675},
doi = {10.1145/2623330.2623675},
abstract = {It is traditionally a challenge for home buyers to understand, compare and contrast the investment values of real estates. While a number of estate appraisal methods have been developed to value real property, the performances of these methods have been limited by the traditional data sources for estate appraisal. However, with the development of new ways of collecting estate-related mobile data, there is a potential to leverage geographic dependencies of estates for enhancing estate appraisal. Indeed, the geographic dependencies of the value of an estate can be from the characteristics of its own neighborhood (individual), the values of its nearby estates (peer), and the prosperity of the affiliated latent business area (zone). To this end, in this paper, we propose a geographic method, named ClusRanking, for estate appraisal by leveraging the mutual enforcement of ranking and clustering power. ClusRanking is able to exploit geographic individual, peer, and zone dependencies in a probabilistic ranking model. Specifically, we first extract the geographic utility of estates from geography data, estimate the neighborhood popularity of estates by mining taxicab trajectory data, and model the influence of latent business areas via ClusRanking. Also, we use a linear model to fuse these three influential factors and predict estate investment values. Moreover, we simultaneously consider individual, peer and zone dependencies, and derive an estate-specific ranking likelihood as the objective function. Finally, we conduct a comprehensive evaluation with real-world estate related data, and the experimental results demonstrate the effectiveness of our method.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1047–1056},
numpages = {10},
keywords = {clusranking, geographic dependencies, real estate appraisal},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623729,
author = {Zong, Bo and Wu, Yinghui and Song, Jie and Singh, Ambuj K. and Cam, Hasan and Han, Jiawei and Yan, Xifeng},
title = {Towards Scalable Critical Alert Mining},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623729},
doi = {10.1145/2623330.2623729},
abstract = {Performance monitor software for data centers typically generates a great number of alert sequences. These alert sequences indicate abnormal network events. Given a set of observed alert sequences, it is important to identify the most critical alerts that are potentially the causes of others. While the need for mining critical alerts over large scale alert sequences is evident, most alert analysis techniques stop at modeling and mining the causal relations among the alerts.This paper studies the critical alert mining problem: Given a set of alert sequences, we aim to find a set of k critical alerts such that the number of alerts potentially triggered by them is maximized. We show that the problem is intractable; therefore, we resort to approximation and heuristic algorithms. First, we develop an approximation algorithm that obtains a near-optimal alert set in quadratic time, and propose pruning techniques to improve its runtime performance. Moreover, we show a faster approximation exists, when the alerts follow certain causal structure. Second, we propose two fast heuristic algorithms based on tree sampling techniques. On real-life data, these algorithms identify a critical alert from up to 270,000 mined causal relations in 5 seconds; meanwhile, they preserve more than 80% of solution quality, and are up to 5,000 times faster than their approximation counterparts.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1057–1066},
numpages = {10},
keywords = {graph mining, critical alert mining, root cause analysis, data center troubleshooting, data mining},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623717,
author = {Cao, Caleb Chen and Chen, Lei and Jagadish, Hosagrahar Visvesvaraya},
title = {From Labor to Trader: Opinion Elicitation via Online Crowds as a Market},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623717},
doi = {10.1145/2623330.2623717},
abstract = {We often care about people's degrees of belief about certain events: e.g. causality between an action and the outcomes, odds distribution among the outcome of a horse race and so on. It is well recognized that the best form to elicit opinion from human is probability distribution instead of simple voting, because the form of distribution retains the delicate information that an opinion expresses. In the past, opinion elicitation has relied on experts, who are expensive and not always available. More recently, crowdsourcing has gained prominence as an inexpensive way to get a great deal of human input. However, traditional crowdsourcing has primarily focused on issuing very simple (e.g. binary decision) tasks to the crowd. In this paper, we study how to use crowds for Opinion Elicitation. There are three major challenges to eliciting opinion information in the form of probability distributions: how to measure the quality of distribution; how to aggregate the distributions; and, how to strategically implement such a system.To address these challenges, we design and implement COPE Crowd-powered OPinion Elicitation market. COPE models crowdsourced work as a trading market, where the "workers" behave like "traders" to maximize their profit by presenting their opinion. Among the innovative features in this system, we design COPE updating to combine the multiple elicited distributions following a Bayesian scheme. Also to provide more flexibility while running COPE, we propose a series of efficient algorithms and a slope based strategy to manage the ending condition of COPE. We then demonstrate the implementation of COPE and report experimental results running on real commercial platform to demonstrate the practical value of this system.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1067–1076},
numpages = {10},
keywords = {human computation, market, social media, crowdsourcing},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623633,
author = {Zhang, Weinan and Yuan, Shuai and Wang, Jun},
title = {Optimal Real-Time Bidding for Display Advertising},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623633},
doi = {10.1145/2623330.2623633},
abstract = {In this paper we study bid optimisation for real-time bidding (RTB) based display advertising. RTB allows advertisers to bid on a display ad impression in real time when it is being generated. It goes beyond contextual advertising by motivating the bidding focused on user data and it is different from the sponsored search auction where the bid price is associated with keywords. For the demand side, a fundamental technical challenge is to automate the bidding process based on the budget, the campaign objective and various information gathered in runtime and in history. In this paper, the programmatic bidding is cast as a functional optimisation problem. Under certain dependency assumptions, we derive simple bidding functions that can be calculated in real time; our finding shows that the optimal bid has a non-linear relationship with the impression level evaluation such as the click-through rate and the conversion rate, which are estimated in real time from the impression level features. This is different from previous work that is mainly focused on a linear bidding function. Our mathematical derivation suggests that optimal bidding strategies should try to bid more impressions rather than focus on a small set of high valued impressions because according to the current RTB market data, compared to the higher evaluated impressions, the lower evaluated ones are more cost effective and the chances of winning them are relatively higher. Aside from the theoretical insights, offline experiments on a real dataset and online experiments on a production RTB system verify the effectiveness of our proposed optimal bidding strategies and the functional optimisation framework.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1077–1086},
numpages = {10},
keywords = {bid optimisation, display advertising, demand-side platform, real-time bidding},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623720,
author = {Wang, Ting and Wang, Dashun and Wang, Fei},
title = {Quantifying Herding Effects in Crowd Wisdom},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623720},
doi = {10.1145/2623330.2623720},
abstract = {In many diverse settings, aggregated opinions of others play an increasingly dominant role in shaping individual decision making. One key prerequisite of harnessing the "crowd wisdom" is the independency of individuals' opinions, yet in real settings collective opinions are rarely simple aggregations of independent minds. Recent experimental studies document that disclosing prior collective opinions distorts individuals' decision making as well as their perceptions of quality and value, highlighting a fundamental disconnect from current modeling efforts: How to model social influence and its impact on systems that are constantly evolving? In this paper, we develop a mechanistic framework to model social influence of prior collective opinions (e.g., online product ratings) on subsequent individual decision making. We find our method successfully captures the dynamics of rating growth, helping us separate social influence bias from inherent values. Using large-scale longitudinal customer rating datasets, we demonstrate that our model not only effectively assesses social influence bias, but also accurately predicts long-term cumulative growth of ratings solely based on early rating trajectories. We believe our framework will play an increasingly important role as our understanding of social processes deepens. It promotes strategies to untangle manipulations and social biases and provides insights towards a more reliable and effective design of social platforms.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1087–1096},
numpages = {10},
keywords = {crowd wisdom, social influence, herding effect},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623634,
author = {Chapelle, Olivier},
title = {Modeling Delayed Feedback in Display Advertising},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623634},
doi = {10.1145/2623330.2623634},
abstract = {In performance display advertising a key metric of a campaign effectiveness is its conversion rate -- the proportion of users who take a predefined action on the advertiser website, such as a purchase. Predicting this conversion rate is thus essential for estimating the value of an impression and can be achieved via machine learning. One difficulty however is that the conversions can take place long after the impression -- up to a month -- and this delayed feedback hinders the conversion modeling. We tackle this issue by introducing an additional model that captures the conversion delay. Intuitively, this probabilistic model helps determining whether a user that has not converted should be treated as a negative sample -- when the elapsed time is larger than the predicted delay -- or should be discarded from the training set -- when it is too early to tell. We provide experimental results on real traffic logs that demonstrate the effectiveness of the proposed model.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1097–1105},
numpages = {9},
keywords = {display advertising, conversion prediction, machine learning},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623672,
author = {Fang, Meng and Tao, Dacheng},
title = {Networked Bandits with Disjoint Linear Payoffs},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623672},
doi = {10.1145/2623330.2623672},
abstract = {In this paper, we study `networked bandits', a new bandit problem where a set of interrelated arms varies over time and, given the contextual information that selects one arm, invokes other correlated arms. This problem remains under-investigated, in spite of its applicability to many practical problems. For instance, in social networks, an arm can obtain payoffs from both the selected user and its relations since they often share the content through the network. We examine whether it is possible to obtain multiple payoffs from several correlated arms based on the relationships. In particular, we formalize the networked bandit problem and propose an algorithm that considers not only the selected arm, but also the relationships between arms. Our algorithm is `optimism in face of uncertainty' style, in that it decides an arm depending on integrated confidence sets constructed from historical data. We analyze the performance in simulation experiments and on two real-world offline datasets. The experimental results demonstrate our algorithm's effectiveness in the networked bandit setting.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1106–1115},
numpages = {10},
keywords = {social network, networked bandits, exploration/exploitation dilemma},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623622,
author = {Chen, Zhiyuan and Liu, Bing},
title = {Mining Topics in Documents: Standing on the Shoulders of Big Data},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623622},
doi = {10.1145/2623330.2623622},
abstract = {Topic modeling has been widely used to mine topics from documents. However, a key weakness of topic modeling is that it needs a large amount of data (e.g., thousands of documents) to provide reliable statistics to generate coherent topics. However, in practice, many document collections do not have so many documents. Given a small number of documents, the classic topic model LDA generates very poor topics. Even with a large volume of data, unsupervised learning of topic models can still produce unsatisfactory results. In recently years, knowledge-based topic models have been proposed, which ask human users to provide some prior domain knowledge to guide the model to produce better topics. Our research takes a radically different approach. We propose to learn as humans do, i.e., retaining the results learned in the past and using them to help future learning. When faced with a new task, we first mine some reliable (prior) knowledge from the past learning/modeling results and then use it to guide the model inference to generate more coherent topics. This approach is possible because of the big data readily available on the Web. The proposed algorithm mines two forms of knowledge: must-link (meaning that two words should be in the same topic) and cannot-link (meaning that two words should not be in the same topic). It also deals with two problems of the automatically mined knowledge, i.e., wrong knowledge and knowledge transitivity. Experimental results using review documents from 100 product domains show that the proposed approach makes dramatic improvements over state-of-the-art baselines.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1116–1125},
numpages = {10},
keywords = {topic model, opinion aspect extraction, lifelong learning},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623617,
author = {Chen, Zhe and Cafarella, Michael},
title = {Integrating Spreadsheet Data via Accurate and Low-Effort Extraction},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623617},
doi = {10.1145/2623330.2623617},
abstract = {Spreadsheets contain valuable data on many topics. However, spreadsheets are difficult to integrate with other data sources. Converting spreadsheet data to the relational model would allow data analysts to use relational integration tools. We propose a two-phase semiautomatic system that extracts accurate relational metadata while minimizing user effort. Based on an undirected graphical model, our system enables downstream spreadsheet integration applications. First, the automatic extractor uses hints from spreadsheets' graphical style and recovered metadata to extract the spreadsheet data as accurately as possible. Second, the interactive repair identifies similar regions in distinct spreadsheets scattered across large spreadsheet corpora, allowing a user's single manual repair to be amortized over many possible extraction errors. Our experiments show that a human can obtain the accurate extraction with just 31% of the manual operations required by a standard classification based technique on two real-world datasets.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1126–1135},
numpages = {10},
keywords = {graphical model, spreadsheets, information extraction},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623687,
author = {Sudhof, Moritz and Gom\'{e}z Emilsson, Andr\'{e}s and Maas, Andrew L. and Potts, Christopher},
title = {Sentiment Expression Conditioned by Affective Transitions and Social Forces},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623687},
doi = {10.1145/2623330.2623687},
abstract = {Human emotional states are not independent but rather proceed along systematic paths governed by both internal, cognitive factors and external, social ones. For example, anxiety often transitions to disappointment, which is likely to sink to depression before rising to happiness and relaxation, and these states are conditioned by the states of others in our communities. Modeling these complex dependencies can yield insights into human emotion and support more powerful sentiment technologies.We develop a theory of conditional dependencies between emotional states in which emotions are characterized not only by valence (polarity) and arousal (intensity) but also by the role they play in state transitions and social relationships. We implement this theory using conditional random fields (CRFs) that synthesize textual information with information about previous emotional states and the emotional states of others. To assess the power of affective transitions, we evaluate our model in a collection of 'mood' updates from the Experience Project. To assess the power of social factors, we use a corpus of product reviews from a website in which the community dynamics encourage reviewers to be influenced by each other. In both settings, our models yield improvements of statistical and practical significance over ones that classify each text independently of its emotional or social context.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1136–1145},
numpages = {10},
keywords = {sentiment as social, sentiment transitions, multidimensional sentiment analysis},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623685,
author = {Li, Furong and Lee, Mong Li and Hsu, Wynne},
title = {Entity Profiling with Varying Source Reliabilities},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623685},
doi = {10.1145/2623330.2623685},
abstract = {The rapid growth of information sources on the Web has intensified the problem of data quality. In particular, the same real world entity may be described by different sources in various ways with overlapping information, and possibly conflicting or even erroneous values. In order to obtain a more complete and accurate picture for a real world entity, we need to collate the data records that refer to the entity, as well as correct any erroneous values. We observe that these two tasks are often tightly coupled: rectifying erroneous values will facilitate data collation, while linking similar records provides us with a clearer view of the data and additional evidence for error correction. In this paper, we present a framework called Comet that interleaves record linkage with error correction, taking into consideration the source reliabilities on various attributes. The proposed framework first utilizes confidence based matching to discriminate records in terms of ambiguity and source reliability. Then it performs adaptive matching to reduce the impact of erroneous values. Experiment results demonstrate that Comet outperforms the state-of-the-art techniques and is able to build complete and accurate profiles for real world entities.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1146–1155},
numpages = {10},
keywords = {record linkage, entity profiling, truth discovery, source reliability},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623677,
author = {Fader, Anthony and Zettlemoyer, Luke and Etzioni, Oren},
title = {Open Question Answering over Curated and Extracted Knowledge Bases},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623677},
doi = {10.1145/2623330.2623677},
abstract = {We consider the problem of open-domain question answering (Open QA) over massive knowledge bases (KBs). Existing approaches use either manually curated KBs like Freebase or KBs automatically extracted from unstructured text. In this paper, we present OQA, the first approach to leverage both curated and extracted KBs.A key technical challenge is designing systems that are robust to the high variability in both natural language questions and massive KBs. OQA achieves robustness by decomposing the full Open QA problem into smaller sub-problems including question paraphrasing and query reformulation. OQA solves these sub-problems by mining millions of rules from an unlabeled question corpus and across multiple KBs. OQA then learns to integrate these rules by performing discriminative training on question-answer pairs using a latent-variable structured perceptron algorithm. We evaluate OQA on three benchmark question sets and demonstrate that it achieves up to twice the precision and recall of a state-of-the-art Open QA system.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1156–1165},
numpages = {10},
keywords = {algorithms, experimentation},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623619,
author = {Chen, Feng and Neill, Daniel B.},
title = {Non-Parametric Scan Statistics for Event Detection and Forecasting in Heterogeneous Social Media Graphs},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623619},
doi = {10.1145/2623330.2623619},
abstract = {Event detection in social media is an important but challenging problem. Most existing approaches are based on burst detection, topic modeling, or clustering techniques, which cannot naturally model the implicit heterogeneous network structure in social media. As a result, only limited information, such as terms and geographic locations, can be used. This paper presents Non-Parametric Heterogeneous Graph Scan (NPHGS), a new approach that considers the entire heterogeneous network for event detection: we first model the network as a "sensor" network, in which each node senses its "neighborhood environment" and reports an empirical p-value measuring its current level of anomalousness for each time interval (e.g., hour or day). Then, we efficiently maximize a nonparametric scan statistic over connected subgraphs to identify the most anomalous network clusters. Finally, the event represented by each cluster is summarized with information such as type of event, geographical locations, time, and participants. As a case study, we consider two applications using Twitter data, civil unrest event detection and rare disease outbreak detection, and present empirical evaluations illustrating the effectiveness and efficiency of our proposed approach.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1166–1175},
numpages = {10},
keywords = {social media, non-parametric scan statistics, event detection and forecasting, heterogeneous graphs},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623674,
author = {Rozenshtein, Polina and Anagnostopoulos, Aris and Gionis, Aristides and Tatti, Nikolaj},
title = {Event Detection in Activity Networks},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623674},
doi = {10.1145/2623330.2623674},
abstract = {With the fast growth of smart devices and social networks, a lot of computing systems collect data that record different types of activities. An important computational challenge is to analyze these data, extract patterns, and understand activity trends. We consider the problem of mining activity networks to identify interesting events, such as a big concert or a demonstration in a city, or a trending keyword in a user community in a social network.We define an event to be a subset of nodes in the network that are close to each other and have high activity levels. We formalize the problem of event detection using two graph-theoretic formulations. The first one captures the compactness of an event using the sum of distances among all pairs of the event nodes. We show that this formulation can be mapped to the maxcut problem, and thus, it can be solved by applying standard semidefinite programming techniques. The second formulation captures compactness using a minimum-distance tree. This formulation leads to the prize-collecting Steiner-tree problem, which we solve by adapting existing approximation algorithms. For the two problems we introduce, we also propose efficient and effective greedy approaches and we prove performance guarantees for one of them. We experiment with the proposed algorithms on real datasets from a public bicycling system and a geolocation-enabled social network dataset collected from twitter. The results show that our methods are able to detect meaningful events.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1176–1185},
numpages = {10},
keywords = {maximum cut, prize-collecting steiner tree, submodular function maximization, event detection},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623644,
author = {Jiang, Meng and Cui, Peng and Wang, Fei and Xu, Xinran and Zhu, Wenwu and Yang, Shiqiang},
title = {FEMA: Flexible Evolutionary Multi-Faceted Analysis for Dynamic Behavioral Pattern Discovery},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623644},
doi = {10.1145/2623330.2623644},
abstract = {Behavioral pattern discovery is increasingly being studied to understand human behavior and the discovered patterns can be used in many real world applications such as web search, recommender system and advertisement targeting. Traditional methods usually consider the behaviors as simple user and item connections, or represent them with a static model. In real world, however, human behaviors are actually complex and dynamic: they include correlations between user and multiple types of objects and also continuously evolve along time. These characteristics cause severe data sparsity and computational complexity problem, which pose great challenge to human behavioral analysis and prediction. In this paper, we propose a Flexible Evolutionary Multi-faceted Analysis (FEMA) framework for both behavior prediction and pattern mining. FEMA utilizes a flexible and dynamic factorization scheme for analyzing human behavioral data sequences, which can incorporate various knowledge embedded in different object domains to alleviate the sparsity problem. We give approximation algorithms for efficiency, where the bound of approximation loss is theoretically proved. We extensively evaluate the proposed method in two real datasets. For the prediction of human behaviors, the proposed FEMA significantly outperforms other state-of-the-art baseline methods by 17.4%. Moreover, FEMA is able to discover quite a number of interesting multi-faceted temporal patterns on human behaviors with good interpretability. More importantly, it can reduce the run time from hours to minutes, which is significant for industry to serve real-time applications.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1186–1195},
numpages = {10},
keywords = {behavioral pattern, flexible regularizers, tensor factorization, evolutionary analysis, behavior modeling},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623690,
author = {Golshan, Behzad and Lappas, Theodoros and Terzi, Evimaria},
title = {Profit-Maximizing Cluster Hires},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623690},
doi = {10.1145/2623330.2623690},
abstract = {Team formation has been long recognized as a natural way to acquire a diverse pool of useful skills, by combining experts with complementary talents. This allows organizations to effectively complete beneficial projects from different domains, while also helping individual experts position themselves and succeed in highly competitive job markets. Here, we assume a collection of projects ensuremath{P}, where each project requires a certain set of skills, and yields a different benefit upon completion. We are further presented with a pool of experts ensuremath{X}, where each expert has his own skillset and compensation demands. Then, we study the problem of hiring a cluster of experts T ⊆ X, so that the overall compensation (cost) does not exceed a given budget B, and the total benefit of the projects that this team can collectively cover is maximized. We refer to this as the ClusterHire problem. Our work presents a detailed analysis of the computational complexity and hardness of approximation of the problem, as well as heuristic, yet effective, algorithms for solving it in practice. We demonstrate the efficacy of our approaches through experiments on real datasets of experts, and demonstrate their advantage over intuitive baselines. We also explore additional variants of the fundamental problem formulation, in order to account for constraints and considerations that emerge in realistic cluster-hiring scenarios. All variants considered in this paper have immediate applications in the cluster hiring process, as it emerges in the context of different organizational settings.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1196–1205},
numpages = {10},
keywords = {team formation, online marketplaces},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623724,
author = {Li, Keqian and Lu, Wei and Bhagat, Smriti and Lakshmanan, Laks V.S. and Yu, Cong},
title = {On Social Event Organization},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623724},
doi = {10.1145/2623330.2623724},
abstract = {Online platforms, such as Meetup and Plancast, have recently become popular for planning gatherings and event organization. However, there is a surprising lack of studies on how to effectively and efficiently organize social events for a large group of people through such platforms. In this paper, we study the key computational problem involved in organization of social events, to our best knowledge, for the first time.We propose the Social Event Organization (SEO) problem as one of assigning a set of events for a group of users to attend, where the users are socially connected with each other and have innate levels of interest in those events. As a first step toward Social Event Organization, we introduce a formal definition of a restricted version of the problem and show that it is NP-hard and is hard to approximate. We propose efficient heuristic algorithms that improve upon simple greedy algorithms by incorporating the notion of phantom events and by using look-ahead estimation. Using synthetic datasets and three real datasets including those from the platforms Meetup and Plancast, we experimentally demonstrate that our greedy heuristics are scalable and furthermore outperform the baseline algorithms significantly in terms of achieving superior social welfare.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1206–1215},
numpages = {10},
keywords = {assignment problems, social networks, event organization},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623693,
author = {Embar, Varun R. and Pasumarthi, Rama Kumar and Bhattacharya, Indrajit},
title = {A Bayesian Framework for Estimating Properties of Network Diffusions},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623693},
doi = {10.1145/2623330.2623693},
abstract = {The analysis of network connections, diffusion processes and cascades requires evaluating properties of the diffusion network. Properties of interest often involve variables that are not explicitly observed in real world diffusions. Connection strengths in the network and diffusion paths of infections over the network are examples of such hidden variables. These hidden variables therefore need to be estimated for these properties to be evaluated. In this paper, we propose and study this novel problem in a Bayesian framework by capturing the posterior distribution of these hidden variables given the observed cascades, and computing the expectation of these properties under this posterior distribution. We identify and characterize interesting network diffusion properties whose expectations can be computed exactly and efficiently, either wholly or in part. For properties that are not `nice' in this sense, we propose a Gibbs Sampling framework for Monte Carlo integration. In detailed experiments using various network diffusion properties over multiple synthetic and real datasets, we demonstrate that the proposed approach is significantly more accurate than a frequentist plug-in baseline. We also propose a map-reduce implementation of our framework and demonstrate that this can analyze cascades with millions of infections in minutes.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1216–1225},
numpages = {10},
keywords = {networks of diffusion, information cascades, social influence analysis, bayesian analysis, gibbs sampling},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623704,
author = {Khalil, Elias Boutros and Dilkina, Bistra and Song, Le},
title = {Scalable Diffusion-Aware Optimization of Network Topology},
year = {2014},
isbn = {9781450329569},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2623330.2623704},
doi = {10.1145/2623330.2623704},
abstract = {How can we optimize the topology of a networked system to bring a flu under control, propel a video to popularity, or stifle a network malware in its infancy? Previous work on information diffusion has focused on modeling the diffusion dynamics and selecting nodes to maximize/minimize influence. Only a paucity of recent studies have attempted to address the network modification problems, where the goal is to either facilitate desirable spreads or curtail undesirable ones by adding or deleting a small subset of network nodes or edges. In this paper, we focus on the widely studied linear threshold diffusion model, and prove, for the first time, that the network modification problems under this model have supermodular objective functions. This surprising property allows us to design efficient data structures and scalable algorithms with provable approximation guarantees, despite the hardness of the problems in question. Both the time and space complexities of our algorithms are linear in the size of the network, which allows us to experiment with millions of nodes and edges. We show that our algorithms outperform an array of heuristics in terms of their effectiveness in controlling diffusion processes, often beating the next best by a significant margin.},
booktitle = {Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1226–1235},
numpages = {10},
keywords = {diffusion networks, approximation, network optimization, supermodularity},
location = {New York, New York, USA},
series = {KDD '14}
}

@inproceedings{10.1145/2623330.2623646,
author = {Kurashima, Takeshi and Iwata, Tomoharu and Takaya, Noriko and Sawada, Hiroshi},
title = {Probabilistic Latent Network Visualization:

license_type: permissive

branch_name: refs/heads/main

extension: bib