text:
4},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098072},
doi = {10.1145/3097983.3098072},
abstract = {Given a graph G, a source node s and a target node t, the personalized PageRank (PPR) of t with respect to s is the probability that a random walk starting from s terminates at t. A single-source PPR (SSPPR) query enumerates all nodes in G, and returns the top-k nodes with the highest PPR values with respect to a given source node s. SSPPR has important applications in web search and social networks, e.g., in Twitter's Who-To-Follow recommendation service. However, SSPPR computation is immensely expensive, and at the same time resistant to indexing and materialization. So far, existing solutions either use heuristics, which do not guarantee result quality, or rely on the strong computing power of modern data centers, which is costly.Motivated by this, we propose FORA, a simple and effective index-based solution for approximate SSPPR processing, with rigorous guarantees on result quality. The basic idea of FORA is to combine two existing methods Forward Push (which is fast but does not guarantee quality) and Monte Carlo Random Walk (accurate but slow) in a simple and yet non-trivial way, leading to an algorithm that is both fast and accurate. Further, FORA includes a simple and effective indexing scheme, as well as a module for top-k selection with high pruning power. Extensive experiments demonstrate that FORA is orders of magnitude more efficient than its main competitors. Notably, on a billion-edge Twitter dataset, FORA answers a top-500 approximate SSPPR query within 5 seconds, using a single commodity server.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {505–514},
numpages = {10},
keywords = {personalized pagerank, forward push, random walk},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098071,
author = {Wu, Liwei and Hsieh, Cho-Jui and Sharpnack, James},
title = {Large-Scale Collaborative Ranking in Near-Linear Time},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098071},
doi = {10.1145/3097983.3098071},
abstract = {In this paper, we consider the Collaborative Ranking (CR) problem for recommendation systems. Given a set of pairwise preferences between items for each user, collaborative ranking can be used to rank un-rated items for each user, and this ranking can be naturally used for recommendation. It is observed that collaborative ranking algorithms usually achieve better performance since they directly minimize the ranking loss; however, they are rarely used in practice due to the poor scalability. All the existing CR algorithms have time complexity at least O(|Ω|r) per iteration, where r is the target rank and |Ω| is number of pairs which grows quadratically with number of ratings per user. For example, the Netflix data contains totally 20 billion rating pairs, and at this scale all the current algorithms have to work with significant subsampling, resulting in poor prediction on testing data.In this paper, we propose a new collaborative ranking algorithm called Primal-CR that reduces the time complexity to O(|Ω|+d1 |d2 r), where d1 is number of users and |d2 is the averaged number of items rated by a user. Note that d1 |d2 is strictly smaller and often much smaller than |Ω|.Furthermore, by exploiting the fact that most data is in the form of numerical ratings instead of pairwise comparisons, we propose Primal-CR++ with O(d1|d2 (r+ log |d2)) time complexity. Both algorithms have better theoretical time complexity than existing approaches and also outperform existing approaches in terms of NDCG and pairwise error on real data sets. To the best of our knowledge, this is the first collaborative ranking algorithm capable of working on the full Netflix dataset using all the 20 billion rating pairs, and this leads to a model with much better recommendation compared with previous models trained on subsamples. Finally, compared with classical matrix factorization algorithm which also requires O(d1d2r) time, our algorithm has almost the same efficiency while making much better recommendations since we consider the ranking loss.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {515–524},
numpages = {10},
keywords = {large-scale, recommendation systems, collaborative ranking},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098019,
author = {Xu, Jingwei and Yao, Yuan and Tong, Hanghang and Tao, Xianping and Lu, Jian},
title = {HoORaYs: High-Order Optimization of Rating Distance for Recommender Systems},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098019},
doi = {10.1145/3097983.3098019},
abstract = {Latent factor models have become a prevalent method in recommender systems, to predict users' preference on items based on the historical user feedback. Most of the existing methods, explicitly or implicitly, are built upon the first-order rating distance principle, which aims to minimize the difference between the estimated and real ratings. In this paper, we generalize such first-order rating distance principle and propose a new latent factor model (HoORaYs) for recommender systems. The core idea of the proposed method is to explore high-order rating distance, which aims to minimize not only (i) the difference between the estimated and real ratings of the same (user, item) pair (i.e., the first-order rating distance), but also (ii) the difference between the estimated and real rating difference of the same user across different items (i.e., the second-order rating distance). We formulate it as a regularized optimization problem, and propose an effective and scalable algorithm to solve it. Our analysis from the geometry and Bayesian perspectives indicate that by exploring the high-order rating distance, it helps to reduce the variance of the estimator, which in turns leads to better generalization performance (e.g., smaller prediction error). We evaluate the proposed method on four real-world data sets, two with explicit user feedback and the other two with implicit user feedback. Experimental results show that the proposed method consistently outperforms the state-of-the-art methods in terms of the prediction accuracy.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {525–534},
numpages = {10},
keywords = {high-order distance, recommender systems, latent factor model, collaborative filtering},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098009,
author = {Xun, Guangxu and Li, Yaliang and Gao, Jing and Zhang, Aidong},
title = {Collaboratively Improving Topic Discovery and Word Embeddings by Coordinating Global and Local Contexts},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098009},
doi = {10.1145/3097983.3098009},
abstract = {A text corpus typically contains two types of context information -- global context and local context. Global context carries topical information which can be utilized by topic models to discover topic structures from the text corpus, while local context can train word embeddings to capture semantic regularities reflected in the text corpus. This encourages us to exploit the useful information in both the global and the local context information. In this paper, we propose a unified language model based on matrix factorization techniques which 1) takes the complementary global and local context information into consideration simultaneously, and 2) models topics and learns word embeddings collaboratively. We empirically show that by incorporating both global and local context, this collaborative model can not only significantly improve the performance of topic discovery over the baseline topic models, but also learn better word embeddings than the baseline word embedding models. We also provide qualitative analysis that explains how the cooperation of global and local context information can result in better topic structures and word embeddings.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {535–543},
numpages = {9},
keywords = {unified language model, word embeddings, topic modeling, local context, global context},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098083,
author = {Yen, Ian E.H. and Huang, Xiangru and Dai, Wei and Ravikumar, Pradeep and Dhillon, Inderjit and Xing, Eric},
title = {PPDsparse: A Parallel Primal-Dual Sparse Method for Extreme Classification},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098083},
doi = {10.1145/3097983.3098083},
abstract = {Extreme Classification comprises multi-class or multi-label prediction where there is a large number of classes, and is increasingly relevant to many real-world applications such as text and image tagging. In this setting, standard classification methods, with complexity linear in the number of classes, become intractable, while enforcing structural constraints among classes (such as low-rank or tree-structure) to reduce complexity often sacrifices accuracy for efficiency. The recent PD-Sparse method addresses this via an algorithm that is sub-linear in the number of variables, by exploiting primal-dual sparsity inherent in a specific loss function, namely the max-margin loss. In this work, we extend PD-Sparse to be efficiently parallelized in large-scale distributed settings. By introducing separable loss functions, we can scale out the training, with network communication and space efficiency comparable to those in one-versus-all approaches while maintaining an overall complexity sub-linear in the number of classes. On several large-scale benchmarks our proposed method achieves accuracy competitive to the state-of-the-art while reducing the training time from days to tens of minutes compared with existing parallel or sparse methods on a cluster of 100 cores.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {545–553},
numpages = {9},
keywords = {sparse optimization, primal dual method, extreme classification},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098069,
author = {Yin, Hao and Benson, Austin R. and Leskovec, Jure and Gleich, David F.},
title = {Local Higher-Order Graph Clustering},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098069},
doi = {10.1145/3097983.3098069},
abstract = {Local graph clustering methods aim to find a cluster of nodes by exploring a small region of the graph. These methods are attractive because they enable targeted clustering around a given seed node and are faster than traditional global graph clustering methods because their runtime does not depend on the size of the input graph. However, current local graph partitioning methods are not designed to account for the higher-order structures crucial to the network, nor can they effectively handle directed networks. Here we introduce a new class of local graph clustering methods that address these issues by incorporating higher-order network information captured by small subgraphs, also called network motifs. We develop the Motif-based Approximate Personalized PageRank (MAPPR) algorithm that finds clusters containing a seed node with minimal emph{motif conductance}, a generalization of the conductance metric for network motifs. We generalize existing theory to prove the fast running time (independent of the size of the graph) and obtain theoretical guarantees on the cluster quality (in terms of motif conductance). We also develop a theory of node neighborhoods for finding sets that have small motif conductance, and apply these results to the case of finding good seed nodes to use as input to the MAPPR algorithm. Experimental validation on community detection tasks in both synthetic and real-world networks, shows that our new framework MAPPR outperforms the current edge-based personalized PageRank methodology.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {555–564},
numpages = {10},
keywords = {community detection, motifs, higher-order structure, clustering},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098055,
author = {Zang, Chengxi and Cui, Peng and Faloutsos, Christos and Zhu, Wenwu},
title = {Long Short Memory Process: Modeling Growth Dynamics of Microscopic Social Connectivity},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098055},
doi = {10.1145/3097983.3098055},
abstract = {How do people make friends dynamically in social networks? What are the temporal patterns for an individual increasing its social connectivity? What are the basic mechanisms governing the formation of these temporal patterns? No matter cyber or physical social systems, their structure and dynamics are mainly driven by the connectivity dynamics of each individual. However, due to the lack of empirical data, little is known about the empirical dynamic patterns of social connectivity at microscopic level, let alone the regularities or models governing these microscopic dynamics.We examine the detailed growth process of "WeChat", the largest online social network in China, with 300 million users and 4.75 billion links spanning two years. We uncover a wide range of long-term power law growth and short-term bursty growth for the social connectivity of different users. We propose three key ingredients, namely average-effect, multiscale-effect and correlation-effect, which govern the observed growth patterns at microscopic level. As a result, we propose the long short memory process incorporating these ingredients, demonstrating that it successfully reproduces the complex growth patterns observed in the empirical data. By analyzing modeling parameters, we discover statistical regularities underlying the empirical growth dynamics. Our model and discoveries provide a foundation for the microscopic mechanisms of network growth dynamics, potentially leading to implications for prediction, clustering and outlier detection on human dynamics.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {565–574},
numpages = {10},
keywords = {social network, social dynamics, burst, human dynamics, power law growth},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3097996,
author = {Zhang, Muhan and Chen, Yixin},
title = {Weisfeiler-Lehman Neural Machine for Link Prediction},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3097996},
doi = {10.1145/3097983.3097996},
abstract = {In this paper, we propose a next-generation link prediction method, Weisfeiler-Lehman Neural Machine (WLNM), which learns topological features in the form of graph patterns that promote the formation of links. WLNM has unmatched advantages including higher performance than state-of-the-art methods and universal applicability over various kinds of networks. WLNM extracts an enclosing subgraph of each target link and encodes the subgraph as an adjacency matrix. The key novelty of the encoding comes from a fast hashing-based Weisfeiler-Lehman (WL) algorithm that labels the vertices according to their structural roles in the subgraph while preserving the subgraph's intrinsic directionality. After that, a neural network is trained on these adjacency matrices to learn a predictive model. Compared with traditional link prediction methods, WLNM does not assume a particular link formation mechanism (such as common neighbors), but learns this mechanism from the graph itself. We conduct comprehensive experiments to show that WLNM not only outperforms a great number of state-of-the-art link prediction methods, but also consistently performs well across networks with different characteristics.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {575–583},
numpages = {9},
keywords = {color refinement, graph labeling, neural network, link prediction},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098003,
author = {Zhang, Haoyu and Zhang, Qin},
title = {EmbedJoin: Efficient Edit Similarity Joins via Embeddings},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098003},
doi = {10.1145/3097983.3098003},
abstract = {We study the problem of edit similarity joins, where given a set of strings and a threshold value K, we want to output all pairs of strings whose edit distances are at most K. Edit similarity join is a fundamental problem in data cleaning/integration, bioinformatics, collaborative filtering and natural language processing, and has been identified as a primitive operator for database systems. This problem has been studied extensively in the literature. However, we have observed that all the existing algorithms fall short on long strings and large distance thresholds.In this paper we propose an algorithm named EmbedJoin which scales very well with string length and distance threshold. Our algorithm is built on the recent advance of metric embeddings for edit distance, and is very different from all of the previous approaches. We demonstrate via an extensive set of experiments that EmbedJoin significantly outperforms the previous best algorithms on long strings and large distance thresholds.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {585–594},
numpages = {10},
keywords = {edit distance, similarity joins},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098027,
author = {Zhang, Chao and Liu, Liyuan and Lei, Dongming and Yuan, Quan and Zhuang, Honglei and Hanratty, Tim and Han, Jiawei},
title = {TrioVecEvent: Embedding-Based Online Local Event Detection in Geo-Tagged Tweet Streams},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098027},
doi = {10.1145/3097983.3098027},
abstract = {Detecting local events (e.g., protest, disaster) at their onsets is an important task for a wide spectrum of applications, ranging from disaster control to crime monitoring and place recommendation. Recent years have witnessed growing interest in leveraging geo-tagged tweet streams for online local event detection. Nevertheless, the accuracies of existing methods still remain unsatisfactory for building reliable local event detection systems. We propose TrioVecEvent, a method that leverages multimodal embeddings to achieve accurate online local event detection. The effectiveness of TrioVecEvent is underpinned by its two-step detection scheme. First, it ensures a high coverage of the underlying local events by dividing the tweets in the query window into coherent geo-topic clusters. To generate quality geo-topic clusters, we capture short-text semantics by learning multimodal embeddings of the location, time, and text, and then perform online clustering with a novel Bayesian mixture model. Second, TrioVecEvent considers the geo-topic clusters as candidate events and extracts a set of features for classifying the candidates. Leveraging the multimodal embeddings as background knowledge, we introduce discriminative features that can well characterize local events, which enables pinpointing true local events from the candidate pool with a small amount of training data. We have used crowdsourcing to evaluate TrioVecEvent, and found that it improves the performance of the state-of-the-art method by a large margin.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {595–604},
numpages = {10},
keywords = {social media, topic modeling, multimodal embedding, representation learning, spatiotemporal data mining, event detection},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098033,
author = {Zhang, Chenzi and Wei, Fan and Liu, Qin and Tang, Zhihao Gavin and Li, Zhenguo},
title = {Graph Edge Partitioning via Neighborhood Heuristic},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098033},
doi = {10.1145/3097983.3098033},
abstract = {We consider the edge partitioning problem that partitions the edges of an input graph into multiple balanced components, while minimizing the total number of vertices replicated (one vertex might appear in more than one partition). This problem is critical in minimizing communication costs and running time for several large-scale distributed graph computation platforms (e.g., PowerGraph, Spark GraphX). We first prove that this problem is NP-hard, and then present a new partitioning heuristic with polynomial running time. We provide a worst-case upper bound of replication factor for our heuristic on general graphs. To our knowledge, we are the first to provide such bound for edge partitioning algorithms on general graphs. Applying this bound to random power-law graphs greatly improves the previous bounds of expected replication factor. Extensive experiments demonstrated that our partitioning algorithm consistently produces much smaller replication factors on various benchmark data sets than the state-of-the-art. When deployed in the production graph engine, PowerGraph, in average it reduces replication factor, communication, and running time by 54%, 66%, and 21%, respectively.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {605–614},
numpages = {10},
keywords = {graph edge partitioning, distributed graph mining},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098050,
author = {Zhang, Kai and Liu, Chuanren and Zhang, Jie and Xiong, Hui and Xing, Eric and Ye, Jieping},
title = {Randomization or Condensation? Linear-Cost Matrix Sketching Via Cascaded Compression Sampling},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098050},
doi = {10.1145/3097983.3098050},
abstract = {Matrix sketching is aimed at finding compact representations of a matrix while simultaneously preserving most of its properties, which is a fundamental building block in modern scientific computing. Randomized algorithms represent state-of-the-art and have attracted huge interest from the fields of machine learning, data mining, and theoretic computer science. However, it still requires the use of the entire input matrix in producing desired factorizations, which can be a major computational and memory bottleneck in truly large problems. In this paper, we uncover an interesting theoretic connection between matrix low-rank decomposition and lossy signal compression, based on which a cascaded compression sampling framework is devised to approximate an m-by-n matrix in only O(m+n) time and space. Indeed, the proposed method accesses only a small number of matrix rows and columns, which significantly improves the memory footprint. Meanwhile, by sequentially teaming two rounds of approximation procedures and upgrading the sampling strategy from a uniform probability to more sophisticated, encoding-orientated sampling, significant algorithmic boosting is achieved to uncover more granular structures in the data. Empirical results on a wide spectrum of real-world, large-scale matrices show that by taking only linear time and space, the accuracy of our method rivals those state-of-the-art randomized algorithms consuming a quadratic, O(mn), amount of resources.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {615–623},
numpages = {9},
keywords = {cascaded compression sampling, matrix sketching, random projection, low-rank decomposition, nystrom method, randomized algorithms},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098030,
author = {Zhao, Hongke and Zhang, Hefu and Ge, Yong and Liu, Qi and Chen, Enhong and Li, Huayu and Wu, Le},
title = {Tracking the Dynamics in Crowdfunding},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098030},
doi = {10.1145/3097983.3098030},
abstract = {Crowdfunding is an emerging Internet fundraising mechanism by raising monetary contributions from the crowd for projects or ventures. In these platforms, the dynamics, i.e., daily funding amount on campaigns and perks (backing options with rewards), are the most concerned issue for creators, backers and platforms. However, tracking the dynamics in crowdfunding is very challenging and still under-explored. To that end, in this paper, we present a focused study on this important problem. A special goal is to forecast the funding amount for a given campaign and its perks in the future days. Specifically, we formalize the dynamics in crowdfunding as a hierarchical time series, i.e., campaign level and perk level. Specific to each level, we develop a special regression by modeling the decision making process of the crowd (visitors and backing probability) and exploring various factors that impact the decision; on this basis, an enhanced switching regression is proposed at each level to address the heterogeneity of funding sequences. Further, we employ a revision matrix to combine the two-level base forecasts for the final forecasting. We conduct extensive experiments on a real-world crowdfunding data collected from Indiegogo.com. The experimental results clearly demonstrate the effectiveness of our approaches on tracking the dynamics in crowdfunding.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {625–634},
numpages = {10},
keywords = {hierarchical time series, dynamics, crowdfunding},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098063,
author = {Zhao, Huan and Yao, Quanming and Li, Jianda and Song, Yangqiu and Lee, Dik Lun},
title = {Meta-Graph Based Recommendation Fusion over Heterogeneous Information Networks},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098063},
doi = {10.1145/3097983.3098063},
abstract = {Heterogeneous Information Network (HIN) is a natural and general representation of data in modern large commercial recommender systems which involve heterogeneous types of data. HIN based recommenders face two problems: how to represent the high-level semantics of recommendations and how to fuse the heterogeneous information to make recommendations. In this paper, we solve the two problems by first introducing the concept of meta-graph to HIN-based recommendation, and then solving the information fusion problem with a "matrix factorization (MF) + factorization machine (FM)" approach. For the similarities generated by each meta-graph, we perform standard MF to generate latent features for both users and items. With different meta-graph based features, we propose to use FM with Group lasso (FMG) to automatically learn from the observed ratings to effectively select useful meta-graph based features. Experimental results on two real-world datasets, Amazon and Yelp, show the effectiveness of our approach compared to state-of-the-art FM and other HIN-based recommendation algorithms.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {635–644},
numpages = {10},
keywords = {recommendation system, heterogeneous information networks, factorization machine, collaborative filtering},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098000,
author = {Zheng, Yan and Phillips, Jeff M.},
title = {Coresets for Kernel Regression},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098000},
doi = {10.1145/3097983.3098000},
abstract = {Kernel regression is an essential and ubiquitous tool for non-parametric data analysis, particularly popular among time series and spatial data. However, the central operation which is performed many times, evaluating a kernel on the data set, takes linear time. This is impractical for modern large data sets.In this paper we describe coresets for kernel regression: compressed data sets which can be used as proxy for the original data and have provably bounded worst case error. The size of the coresets are independent of the raw number of data points; rather they only depend on the error guarantee, and in some cases the size of domain and amount of smoothing. We evaluate our methods on very large time series and spatial data, and demonstrate that they incur negligible error, can be constructed extremely efficiently, and allow for great computational gains.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {645–654},
numpages = {10},
keywords = {coreset, sample complexity, kernel regression},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098015,
author = {Zhou, Dawei and Zhang, Si and Yildirim, Mehmet Yigit and Alcorn, Scott and Tong, Hanghang and Davulcu, Hasan and He, Jingrui},
title = {A Local Algorithm for Structure-Preserving Graph Cut},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098015},
doi = {10.1145/3097983.3098015},
abstract = {Nowadays, large-scale graph data is being generated in a variety of real-world applications, from social networks to co-authorship networks, from protein-protein interaction networks to road traffic networks. Many existing works on graph mining focus on the vertices and edges, with the first-order Markov chain as the underlying model. They fail to explore the high-order network structures, which are of key importance in many high impact domains. For example, in bank customer personally identifiable information (PII) networks, the star structures often correspond to a set of synthetic identities; in financial transaction networks, the loop structures may indicate the existence of money laundering. In this paper, we focus on mining user-specified high-order network structures and aim to find a structure-rich subgraph which does not break many such structures by separating the subgraph from the rest.A key challenge associated with finding a structure-rich subgraph is the prohibitive computational cost. To address this problem, inspired by the family of local graph clustering algorithms for efficiently identifying a low-conductance cut without exploring the entire graph, we propose to generalize the key idea to model high-order network structures. In particular, we start with a generic definition of high-order conductance, and define the high-order diffusion core, which is based on a high-order random walk induced by user-specified high-order network structure. Then we propose a novel High-Order Structure-Preserving LOcal Cut (HOSPLOC) algorithm, which runs in polylogarithmic time with respect to the number of edges in the graph. It starts with a seed vertex and iteratively explores its neighborhood until a subgraph with a small high-order conductance is found. Furthermore, we analyze its performance in terms of both effectiveness and efficiency. The experimental results on both synthetic graphs and real graphs demonstrate the effectiveness and efficiency of our proposed HOSPLOC algorithm.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {655–664},
numpages = {10},
keywords = {high-order network structure, local clustering algorithm},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098052,
author = {Zhou, Chong and Paffenroth, Randy C.},
title = {Anomaly Detection with Robust Deep Autoencoders},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098052},
doi = {10.1145/3097983.3098052},
abstract = {Deep autoencoders, and other deep neural networks, have demonstrated their effectiveness in discovering non-linear features across many problem domains. However, in many real-world problems, large outliers and pervasive noise are commonplace, and one may not have access to clean training data as required by standard deep denoising autoencoders. Herein, we demonstrate novel extensions to deep autoencoders which not only maintain a deep autoencoders' ability to discover high quality, non-linear features but can also eliminate outliers and noise without access to any clean training data. Our model is inspired by Robust Principal Component Analysis, and we split the input data X into two parts, $X = L_{D} + S$, where $L_{D}$ can be effectively reconstructed by a deep autoencoder and $S$ contains the outliers and noise in the original data X. Since such splitting increases the robustness of standard deep autoencoders, we name our model a "Robust Deep Autoencoder (RDA)". Further, we present generalizations of our results to grouped sparsity norms which allow one to distinguish random anomalies from other types of structured corruptions, such as a collection of features being corrupted across many instances or a collection of instances having more corruptions than their fellows. Such "Group Robust Deep Autoencoders (GRDA)" give rise to novel anomaly detection approaches whose superior performance we demonstrate on a selection of benchmark problems.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {665–674},
numpages = {10},
keywords = {anomaly detection, group robust deep autoencoder, robust deep autoencoders, autoencoders, denoising},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098155,
author = {Agarwal, Aman and Basu, Soumya and Schnabel, Tobias and Joachims, Thorsten},
title = {Effective Evaluation Using Logged Bandit Feedback from Multiple Loggers},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098155},
doi = {10.1145/3097983.3098155},
abstract = {Accurately evaluating new policies (e.g. ad-placement models, ranking functions, recommendation functions) is one of the key prerequisites for improving interactive systems. While the conventional approach to evaluation relies on online A/B tests, recent work has shown that counterfactual estimators can provide an inexpensive and fast alternative, since they can be applied offline using log data that was collected from a different policy fielded in the past. In this paper, we address the question of how to estimate the performance of a new target policy when we have log data from multiple historic policies. This question is of great relevance in practice, since policies get updated frequently in most online systems. We show that naively combining data from multiple logging policies can be highly suboptimal. In particular, we find that the standard Inverse Propensity Score (IPS) estimator suffers especially when logging and target policies diverge -- to a point where throwing away data improves the variance of the estimator. We therefore propose two alternative estimators which we characterize theoretically and compare experimentally. We find that the new estimators can provide substantially improved estimation accuracy.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {687–696},
numpages = {10},
keywords = {implicit feedback, off-policy evaluation, log data, counterfactual estimators},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098099,
author = {Agrawal, Saurabh and Atluri, Gowtham and Karpatne, Anuj and Haltom, William and Liess, Stefan and Chatterjee, Snigdhansu and Kumar, Vipin},
title = {Tripoles: A New Class of Relationships in Time Series Data},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098099},
doi = {10.1145/3097983.3098099},
abstract = {Mining relationships in time series data is of immense interest to several disciplines such as neuroscience, climate science, and transportation. Traditional approaches for mining relationships focus on discovering pair-wise relationships in the data. In this work, we define a novel relationship pattern involving three interacting time series, which we refer to as a tripole. We show that tripoles capture interesting relationship patterns in the data that are not possible to be captured using traditionally studied pair-wise relationships. We demonstrate the utility of tripoles in multiple real-world datasets from various domains including climate science and neuroscience. In particular, our approach is able to discover tripoles that are statistically significant, reproducible across multiple independent data sets, and lead to novel domain insights.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {697–706},
numpages = {10},
keywords = {fmri, climate teleconnections, multivariate linear patterns, spatio-temporal, correlation mining},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098173,
author = {Antikacioglu, Arda and Ravi, R.},
title = {Post Processing Recommender Systems for Diversity},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098173},
doi = {10.1145/3097983.3098173},
abstract = {Collaborative filtering is a broad and powerful framework for building recommendation systems that has seen widespread adoption. Over the past decade, the propensity of such systems for favoring popular products and thus creating echo chambers have been observed. This has given rise to an active area of research that seeks to diversify recommendations generated by such algorithms. We address the problem of increasing diversity in recom- mendation systems that are based on collaborative filtering that use past ratings to predict a rating quality for potential recommendations. Following our earlier work, we formulate recommendation system design as a subgraph selection problem from a candidate super-graph of potential recommendations where both diversity and rating quality are explicitly optimized: (1) On the modeling side, we define a new flexible notion of diversity that allows a system designer to prescribe the number of recommendations each item should receive, and smoothly penalizes deviations from this distribution. (2) On the algorithmic side, we show that minimum-cost network flow methods yield fast algorithms in theory and practice for designing recommendation subgraphs that optimize this notion of diversity. (3) On the empirical side, we show the effectiveness of our new model and method to increase diversity while maintaining high rating quality in standard rating data sets from Netflix and MovieLens.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {707–716},
numpages = {10},
keywords = {subgraph selection, network flow, diversity, discrepancy, recommender systems},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098170,
author = {Bauman, Konstantin and Liu, Bing and Tuzhilin, Alexander},
title = {Aspect Based Recommendations: Recommending Items with the Most Valuable Aspects Based on User Reviews},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098170},
doi = {10.1145/3097983.3098170},
abstract = {In this paper, we propose a recommendation technique that not only can recommend items of interest to the user as traditional recommendation systems do but also specific aspects of consumption of the items to further enhance the user experience with those items. For example, it can recommend the user to go to a specific restaurant (item) and also order some specific foods there, e.g., seafood (an aspect of consumption). Our method is called Sentiment Utility Logistic Model (SULM). As its name suggests, SULM uses sentiment analysis of user reviews. It first predicts the sentiment that the user may have about the item based on what he/she might express about the aspects of the item and then identifies the most valuable aspects of the user's potential experience with that item. Furthermore, the method can recommend items together with those most important aspects over which the user has control and can potentially select them, such as the time to go to a restaurant, e.g. lunch vs. dinner, and what to order there, e.g., seafood. We tested the proposed method on three applications (restaurant, hotel, and beauty & spa) and experimentally showed that those users who followed our recommendations of the most valuable aspects while consuming the items, had better experiences, as defined by the overall rating.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {717–725},
numpages = {9},
keywords = {user reviews, recommender systems, user-controlled aspects, sentiment analysis, user experience, aspects of user experience},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098195,
author = {Blalock, Davis W. and Guttag, John V.},
title = {Bolt: Accelerated Data Mining with Fast Vector Compression},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098195},
doi = {10.1145/3097983.3098195},
abstract = {Vectors of data are at the heart of machine learning and data mining. Recently, vector quantization methods have shown great promise in reducing both the time and space costs of operating on vectors. We introduce a vector quantization algorithm that can compress vectors over 12x faster than existing techniques while also accelerating approximate vector operations such as distance and dot product computations by up to 10x. Because it can encode over 2GB of vectors per second, it makes vector quantization cheap enough to employ in many more circumstances. For example, using our technique to compute approximate dot products in a nested loop can multiply matrices faster than a state-of-the-art BLAS implementation, even when our algorithm must first compress the matrices. In addition to showing the above speedups, we demonstrate that our approach can accelerate nearest neighbor search and maximum inner product search by over 100x compared to floating point operations and 10x compared to other vector quantization methods. Our approximate Euclidean distance and dot product computations are not only faster than those of related algorithms with slower encodings, but also faster than Hamming distance computations, which have direct hardware support on the tested platforms. We also assess the errors of our algorithm's approximate distances and dot products, and find that it is competitive with existing, slower vector quantization algorithms.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {727–735},
numpages = {9},
keywords = {scalability, vector quantization, nearest neighbor search, compression},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098156,
author = {Bojchevski, Aleksandar and Matkovic, Yves and G\"{u}nnemann, Stephan},
title = {Robust Spectral Clustering for Noisy Data: Modeling Sparse Corruptions Improves Latent Embeddings},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098156},
doi = {10.1145/3097983.3098156},
abstract = {Spectral clustering is one of the most prominent clustering approaches. However, it is highly sensitive to noisy input data. In this work, we propose a robust spectral clustering technique able to handle such scenarios. To achieve this goal, we propose a sparse and latent decomposition of the similarity graph used in spectral clustering. In our model, we jointly learn the spectral embedding as well as the corrupted data - thus, enhancing the clustering performance overall. We propose algorithmic solutions to all three established variants of spectral clustering, each showing linear complexity in the number of edges. Our experimental analysis confirms the significant potential of our approach for robust spectral clustering. Supplementary material is available at www.kdd.in.tum.de/RSC.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {737–746},
numpages = {10},
keywords = {spectral clustering, noise, embedding, spectral learning, robustness, noisy data, graph embedding, sparsity, robust learning, latent decomposition},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098086,
author = {Cao, Bokai and Zheng, Lei and Zhang, Chenwei and Yu, Philip S. and Piscitello, Andrea and Zulueta, John and Ajilore, Olu and Ryan, Kelly and Leow, Alex D.},
title = {DeepMood: Modeling Mobile Phone Typing Dynamics for Mood Detection},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098086},
doi = {10.1145/3097983.3098086},
abstract = {The increasing use of electronic forms of communication presents new opportunities in the study of mental health, including the ability to investigate the manifestations of psychiatric diseases unobtrusively and in the setting of patients' daily lives. A pilot study to explore the possible connections between bipolar affective disorder and mobile phone usage was conducted. In this study, participants were provided a mobile phone to use as their primary phone. This phone was loaded with a custom keyboard that collected metadata consisting of keypress entry time and accelerometer movement. Individual character data with the exceptions of the backspace key and space bar were not collected due to privacy concerns. We propose an end-to-end deep architecture based on late fusion, named DeepMood, to model the multi-view metadata for the prediction of mood scores. Experimental results show that 90.31% prediction accuracy on the depression score can be achieved based on session-level mobile phone typing dynamics which is typically less than one minute. It demonstrates the feasibility of using mobile phone metadata to infer mood disturbance and severity.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {747–755},
numpages = {9},
keywords = {sequence prediction, recurrent network, bipolar disorder, typing dynamics},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098165,
author = {Chen, Jinghui and Gu, Quanquan},
title = {Fast Newton Hard Thresholding Pursuit for Sparsity Constrained Nonconvex Optimization},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098165},
doi = {10.1145/3097983.3098165},
abstract = {We propose a fast Newton hard thresholding pursuit algorithm for sparsity constrained nonconvex optimization. Our proposed algorithm reduces the per-iteration time complexity to linear in the data dimension d compared with cubic time complexity in Newton's method, while preserving faster computational and statistical convergence rates. In particular, we prove that the proposed algorithm converges to the unknown sparse model parameter at a composite rate, namely quadratic at first and linear when it gets close to the true parameter, up to the minimax optimal statistical precision of the underlying model. Thorough experiments on both synthetic and real datasets demonstrate that our algorithm outperforms the state-of-the-art optimization algorithms for sparsity constrained optimization.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {757–766},
numpages = {10},
keywords = {sparse learning, sparsity constrained optimization, newton's method, nonconvex optimization},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098202,
author = {Chen, Ting and Sun, Yizhou and Shi, Yue and Hong, Liangjie},
title = {On Sampling Strategies for Neural Network-Based Collaborative Filtering},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098202},
doi = {10.1145/3097983.3098202},
abstract = {Recent advances in neural networks have inspired people to design hybrid recommendation algorithms that can incorporate both (1) user-item interaction information and (2) content information including image, audio, and text. Despite their promising results, neural network-based recommendation algorithms pose extensive computational costs, making it challenging to scale and improve upon. In this paper, we propose a general neural network-based recommendation framework, which subsumes several existing state-of-the-art recommendation algorithms, and address the efficiency issue by investigating sampling strategies in the stochastic gradient descent training for the framework. We tackle this issue by first establishing a connection between the loss functions and the user-item interaction bipartite graph, where the loss function terms are defined on links while major computation burdens are located at nodes. We call this type of loss functions "graph-based" loss functions, for which varied mini-batch sampling strategies can have different computational costs. Based on the insight, three novel sampling strategies are proposed, which can significantly improve the training efficiency of the proposed framework (up to $times 30$ times speedup in our experiments), as well as improving the recommendation performance. Theoretical analysis is also provided for both the computational cost and the convergence. We believe the study of sampling strategies have further implications on general graph-based loss functions, and would also enable more research under the neural network-based recommendation framework.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {767–776},
numpages = {10},
keywords = {neural networks, sampling strategies, collaborative filtering},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098106,
author = {Cheng, Kewei and Li, Jundong and Liu, Huan},
title = {Unsupervised Feature Selection in Signed Social Networks},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098106},
doi = {10.1145/3097983.3098106},
abstract = {The rapid growth of social media services brings a large amount of high-dimensional social media data at an unprecedented rate. Feature selection is powerful to prepare high-dimensional data by finding a subset of relevant features. A vast majority of existing feature selection algorithms for social media data exclusively focus on positive interactions among linked instances such as friendships and user following relations. However, in many real-world social networks, instances may also be negatively interconnected. Recent work shows that negative links have an added value over positive links in advancing many learning tasks. In this paper, we study a novel problem of unsupervised feature selection in signed social networks and propose a novel framework SignedFS. In particular, we provide a principled way to model positive and negative links for user latent representation learning. Then we embed the user latent representations into feature selection when label information is not available. Also, we revisit the principle of homophily and balance theory in signed social networks and incorporate the signed graph regularization into the feature selection framework to capture the first-order and the second-order proximity among users in signed social networks. Experiments on two real-world signed social networks demonstrate the effectiveness of our proposed framework. Further experiments are conducted to understand the impacts of different components of SignedFS.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {777–786},
numpages = {10},
keywords = {feature selection, signed social networks, unsupervised learning},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098126,
author = {Choi, Edward and Bahadori, Mohammad Taha and Song, Le and Stewart, Walter F. and Sun, Jimeng},
title = {GRAM: Graph-Based Attention Model for Healthcare Representation Learning},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098126},
doi = {10.1145/3097983.3098126},
abstract = {Deep learning methods exhibit promising performance for predictive modeling in healthcare, but two important challenges remain: - Data insufficiency: Often in healthcare predictive modeling, the sample size is insufficient for deep learning methods to achieve satisfactory results.Interpretation: The representations learned by deep learning methods should align with medical knowledge.To address these challenges, we propose GRaph-based Attention Model (GRAM) that supplements electronic health records (EHR) with hierarchical information inherent to medical ontologies. Based on the data volume and the ontology structure, GRAM represents a medical concept as a combination of its ancestors in the ontology via an attention mechanism.We compared predictive performance (i.e. accuracy, data needs, interpretability) of GRAM to various methods including the recurrent neural network (RNN) in two sequential diagnoses prediction tasks and one heart failure prediction task. Compared to the basic RNN, GRAM achieved 10% higher accuracy for predicting diseases rarely observed in the training data and 3% improved area under the ROC curve for predicting heart failure using an order of magnitude less training data. Additionally, unlike other methods, the medical concept representations learned by GRAM are well aligned with the medical ontology. Finally, GRAM exhibits intuitive attention behaviors by adaptively generalizing to higher level concepts when facing data insufficiency at the lower level concepts.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {787–795},
numpages = {9},
keywords = {attention model, electronic health records, predictive healthcare, graph},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098095,
author = {Corbett-Davies, Sam and Pierson, Emma and Feller, Avi and Goel, Sharad and Huq, Aziz},
title = {Algorithmic Decision Making and the Cost of Fairness},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098095},
doi = {10.1145/3097983.3098095},
abstract = {Algorithms are now regularly used to decide whether defendants awaiting trial are too dangerous to be released back into the community. In some cases, black defendants are substantially more likely than white defendants to be incorrectly classified as high risk. To mitigate such disparities, several techniques have recently been proposed to achieve algorithmic fairness. Here we reformulate algorithmic fairness as constrained optimization: the objective is to maximize public safety while satisfying formal fairness constraints designed to reduce racial disparities. We show that for several past definitions of fairness, the optimal algorithms that result require detaining defendants above race-specific risk thresholds. We further show that the optimal unconstrained algorithm requires applying a single, uniform threshold to all defendants. The unconstrained algorithm thus maximizes public safety while also satisfying one important understanding of equality: that all individuals are held to the same standard, irrespective of race. Because the optimal constrained and unconstrained algorithms generally differ, there is tension between improving public safety and satisfying prevailing notions of algorithmic fairness. By examining data from Broward County, Florida, we show that this trade-off can be large in practice. We focus on algorithms for pretrial release decisions, but the principles we discuss apply to other domains, and also to human decision makers carrying out structured decision rules.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {797–806},
numpages = {10},
keywords = {algorithmic fairness, risk assessment, discrimination, pretrial detention, disparate impact},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098116,
author = {Dong, Yuxiao and Johnson, Reid A. and Xu, Jian and Chawla, Nitesh V.},
title = {Structural Diversity and Homophily: A Study Across More Than One Hundred Big Networks},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098116},
doi = {10.1145/3097983.3098116},
abstract = {A widely recognized organizing principle of networks is structural homophily, which suggests that people with more common neighbors are more likely to connect with each other. However, what influence the diverse structures embedded in common neighbors have on link formation is much less well-understood. To explore this problem, we begin by characterizing the structural diversity of common neighborhoods. Using a collection of 120 large-scale networks, we demonstrate that the impact of the common neighborhood diversity on link existence can vary substantially across networks. We find that its positive effect on Facebook and negative effect on LinkedIn suggest different underlying networking needs in these networks. We also discover striking cases where diversity violates the principle of homophily---that is, where fewer mutual connections may lead to a higher tendency to link with each other. We then leverage structural diversity to develop a common neighborhood signature (CNS), which we apply to a large set of networks to uncover unique network superfamilies not discoverable by conventional methods. Our findings shed light on the pursuit to understand the ways in which network structures are organized and formed, pointing to potential advancement in designing graph generation models and recommender systems.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {807–816},
numpages = {10},
keywords = {triadic closure, social networks, network diversity, network signature, link prediction, embeddedness, big data},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098128,
author = {Eikmeier, Nicole and Gleich, David F.},
title = {Revisiting Power-Law Distributions in Spectra of Real World Networks},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098128},
doi = {10.1145/3097983.3098128},
abstract = {By studying a large number of real world graphs, we find empirical evidence that most real world graphs have a statistically significant power-law distribution with a cutoff in the singular values of the adjacency matrix and eigenvalues of the Laplacian matrix in addition to the commonly conjectured power-law in the degrees. Among these results, power-laws in the singular values appear more consistently than in the degree distribution. The exponents of the power-law distributions are much larger than previously observed. We find a surprising direct relationship between the power-law in the degree distribution and the power-law in the eigenvalues of the Laplacian that was theorized in simple models but is extremely accurate in practice. We investigate these findings in large networks by studying the cutoff value itself, which shows a scaling law for the number of elements involved in these power-laws. Using the scaling law enables us to compute only a subset of eigenvalues of large networks, up to tens of millions of vertices and billions of edges, where we find that those too show evidence of statistically significant power-laws.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {817–826},
numpages = {10},
keywords = {power-law distributions, degree distributions, graph spectrum, real world networks},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098154,
author = {Fu, Yanjie and Aggarwal, Charu and Parthasarathy, Srinivasan and Turaga, Deepak S. and Xiong, Hui},
title = {REMIX: Automated Exploration for Interactive Outlier Detection},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098154},
doi = {10.1145/3097983.3098154},
abstract = {Outlier detection is the identification of points in a dataset that do not conform to the norm. Outlier detection is highly sensitive to the choice of the detection algorithm and the feature subspace used by the algorithm. Extracting domain-relevant insights from outliers needs systematic exploration of these choices since diverse outlier sets could lead to complementary insights. This challenge is especially acute in an interactive setting, where the choices must be explored in a time-constrained manner. In this work, we present REMIX, the first system to address the problem of outlier detection in an interactive setting. REMIX uses a novel mixed integer programming (MIP) formulation for automatically selecting and executing a diverse set of outlier detectors within a time limit. This formulation incorporates multiple aspects such as (i) an upper limit on the total execution time of detectors (ii) diversity in the space of algorithms and features, and (iii) meta-learning for evaluating the cost and utility of detectors. REMIX provides two distinct ways for the analyst to consume its results: (i) a partitioning of the detectors explored by REMIX into perspectives through low-rank non-negative matrix factorization; each perspective can be easily visualized as an intuitive heatmap of experiments versus outliers, and (ii) an ensembled set of outliers which combines outlier scores from all detectors. We demonstrate the benefits of REMIX through extensive empirical validation on real-world data.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {827–835},
numpages = {9},
keywords = {matrix factorization, outlier detection, visualization, ensemble, exploration, interactive},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098092,
author = {Gabel, Moshe and Keren, Daniel and Schuster, Assaf},
title = {Anarchists, Unite: Practical Entropy Approximation for Distributed Streams},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098092},
doi = {10.1145/3097983.3098092},
abstract = {Entropy is a fundamental property of data and a key metric in many scientific and engineering fields. Entropy estimation has been extensively studied, but almost always under the assumption that there is a single data stream, seen in its entirety by one node running the estimation algorithm. Multiple distributed data sources are becoming increasingly common, however, with applications in signal processing, computer science, medicine, physics, and more. Centralizing all data can be infeasible, for example in networks of battery or bandwidth limited sensors, so entropy estimation in distributed streams requires new, communication-efficient approaches.We propose a practical communication-efficient algorithm for continuously approximating the entropy of distributed streams, with deterministic, user-defined error bounds. Unlike previous streaming methods, it supports deletions and variable-sized time-based sliding windows, while still avoiding communication when possible. Moreover, it optionally incorporates a state-of-the-art entropy sketch, allowing for both bandwidth reduction and monitoring very high dimensional problems. Finally, it provides the approximation to all nodes, rather than to a centralized location, which is important in settings such as wireless sensor networks.Evaluation on several public datasets from real application domains shows that our adaptive algorithm can often reduce the number of messages by two orders of magnitude, compared to centralizing all data in one node.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {837–846},
numpages = {10},
keywords = {distributed streams, data mining, entropy estimation},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098197,
author = {Hosseini, Seyed Abbas and Alizadeh, Keivan and Khodadadi, Ali and Arabzadeh, Ali and Farajtabar, Mehrdad and Zha, Hongyuan and Rabiee, Hamid R.},
title = {Recurrent Poisson Factorization for Temporal Recommendation},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098197},
doi = {10.1145/3097983.3098197},
abstract = {Poisson factorization is a probabilistic model of users and items for recommendation systems, where the so-called implicit consumer data is modeled by a factorized Poisson distribution. There are many variants of Poisson factorization methods who show state-of-the-art performance on real-world recommendation tasks. However, most of them do not explicitly take into account the temporal behavior and the recurrent activities of users which is essential to recommend the right item to the right user at the right time. In this paper, we introduce Recurrent Poisson Factorization (RPF) framework that generalizes the classical PF methods by utilizing a Poisson process for modeling the implicit feedback. RPF treats time as a natural constituent of the model and brings to the table a rich family of time-sensitive factorization models. To elaborate, we instantiate several variants of RPF who are capable of handling dynamic user preferences and item specification (DRPF), modeling the social-aspect of product adoption (SRPF), and capturing the consumption heterogeneity among users and items (HRPF). We also develop a variational algorithm for approximate posterior inference that scales up to massive data sets. Furthermore, we demonstrate RPF's superior performance over many state-of-the-art methods on synthetic dataset, and large scale real-world datasets on music streaming logs, and user-item interactions in M-Commerce platforms.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {847–855},
numpages = {9},
keywords = {temporal recommender system, poisson process, poisson factorization},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098091,
author = {Huang, Qiming and Zhu, Michael},
title = {SPOT: Sparse Optimal Transformations for High Dimensional Variable Selection and Exploratory Regression Analysis},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098091},
doi = {10.1145/3097983.3098091},
abstract = {We develop a novel method called SParse Optimal Transformations (SPOT) to simultaneously select important variables and explore relationships between the response and predictor variables in high dimensional nonparametric regression analysis. Not only are the optimal transformations identified by SPOT interpretable, they can also be used for response prediction. We further show that SPOT achieves consistency in both variable selection and parameter estimation. Numerical experiments and real data applications demonstrate that SPOT outperforms other existing methods and can serve as an effective tool in practice.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {857–865},
numpages = {9},
keywords = {optimal transformation, variable selection, regression analysis, spline, monotone transformation},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098112,
author = {Jia, Xiaowei and Khandelwal, Ankush and Nayak, Guruprasad and Gerber, James and Carlson, Kimberly and West, Paul and Kumar, Vipin},
title = {Incremental Dual-Memory LSTM in Land Cover Prediction},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098112},
doi = {10.1145/3097983.3098112},
abstract = {Land cover prediction is essential for monitoring global environmental change. Unfortunately, traditional classification models are plagued by temporal variation and emergence of novel/unseen land cover classes in the prediction process. In this paper, we propose an LSTM-based spatio-temporal learning framework with a dual-memory structure. The dual-memory structure captures both long-term and short-term temporal variation patterns, and is updated incrementally to adapt the model to the ever-changing environment. Moreover, we integrate zero-shot learning to identify unseen classes even without labelled samples. Experiments on both synthetic and real-world datasets demonstrate the superiority of the proposed framework over multiple baselines in land cover prediction.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {867–876},
numpages = {10},
keywords = {lstm, zero-short learning, land cover},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098105,
author = {Jiang, Meng and Shang, Jingbo and Cassidy, Taylor and Ren, Xiang and Kaplan, Lance M. and Hanratty, Timothy P. and Han, Jiawei},
title = {MetaPAD: Meta Pattern Discovery from Massive Text Corpora},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098105},
doi = {10.1145/3097983.3098105},
abstract = {Mining textual patterns in news, tweets, papers, and many other kinds of text corpora has been an active theme in text mining and NLP research. Previous studies adopt a dependency parsing-based pattern discovery approach. However, the parsing results lose rich context around entities in the patterns, and the process is costly for a corpus of large scale. In this study, we propose a novel typed textual pattern structure, called meta pattern, which is extended to a frequent, informative, and precise subsequence pattern in certain context. We propose an efficient framework, called MetaPAD, which discovers meta patterns from massive corpora with three techniques: (1) it develops a context-aware segmentation method to carefully determine the boundaries of patterns with a learnt pattern quality assessment function, which avoids costly dependency parsing and generates high-quality patterns; (2) it identifies and groups synonymous meta patterns from multiple facets---their types, contexts, and extractions; and (3) it examines type distributions of entities in the instances extracted by each group of patterns, and looks for appropriate type levels to make discovered patterns precise. Experiments demonstrate that our proposed framework discovers high-quality typed textual patterns efficiently from different genres of massive corpora and facilitates information extraction.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {877–886},
numpages = {10},
keywords = {natural language processing, text mining, meta pattern, text corpora, context-aware segmentation, pattern discovery, information extraction, textual pattern, attribute discovery, synonymous meta pattern},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098118,
author = {Kim, Yejin and Sun, Jimeng and Yu, Hwanjo and Jiang, Xiaoqian},
title = {Federated Tensor Factorization for Computational Phenotyping},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098118},
doi = {10.1145/3097983.3098118},
abstract = {Tensor factorization models offer an effective approach to convert massive electronic health records into meaningful clinical concepts (phenotypes) for data analysis. These models need a large amount of diverse samples to avoid population bias. An open challenge is how to derive phenotypes jointly across multiple hospitals, in which direct patient-level data sharing is not possible (e.g., due to institutional policies). In this paper, we developed a novel solution to enable federated tensor factorization for computational phenotyping without sharing patient-level data. We developed secure data harmonization and federated computation procedures based on alternating direction method of multipliers (ADMM). Using this method, the multiple hospitals iteratively update tensors and transfer secure summarized information to a central server, and the server aggregates the information to generate phenotypes. We demonstrated with real medical datasets that our method resembles the centralized training model (based on combined datasets) in terms of accuracy and phenotypes discovery while respecting privacy.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {887–895},
numpages = {9},
keywords = {phenotype, admm, federated approach},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098137,
author = {Komiyama, Junpei and Ishihata, Masakazu and Arimura, Hiroki and Nishibayashi, Takashi and Minato, Shin-ichi},
title = {Statistical Emerging Pattern Mining with Multiple Testing Correction},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098137},
doi = {10.1145/3097983.3098137},
abstract = {Emerging patterns are patterns whose support significantly differs between two databases. We study the problem of listing emerging patterns with a multiple testing guarantee. Recently, Terada et al., proposed the Limitless Arity Multiple-testing Procedure (LAMP) that controls the family-wise error rate (FWER) in statistical association mining. LAMP reduces the number of "untestable" hypotheses without compromising its statistical power. Still, FWER is restrictive, and as a result, its statistical power is inherently unsatisfying when the number of patterns is large. On the other hand, the false discovery rate (FDR) is less restrictive than FWER, and thus controlling FDR yields a larger number of significant patterns. We propose two emerging pattern mining methods: the first one controls FWER, and the second one controls FDR. The effectiveness of the methods is verified in computer simulations with real-world datasets.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {897–906},
numpages = {10},
keywords = {statistical pattern mining, multiple testing, emerging pattern mining},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098187,
author = {Labutov, Igor and Huang, Yun and Brusilovsky, Peter and He, Daqing},
title = {Semi-Supervised Techniques for Mining Learning Outcomes and Prerequisites},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098187},
doi = {10.1145/3097983.3098187},
abstract = {Educational content of today no longer only resides in textbooks and classrooms; more and more learning material is found in a free, accessible form on the Internet. Our long-standing vision is to transform this web of educational content into an adaptive, web-scale "textbook", that can guide its readers to most relevant "pages" according to their learning goal and current knowledge. In this paper, we address one core, long-standing problem towards this goal: identifying outcome and prerequisite concepts within a piece of educational content (e.g., a tutorial). Specifically, we propose a novel approach that leverages textbooks as a source of distant supervision, but learns a model that can generalize to arbitrary documents (such as those on the web). As such, our model can take advantage of any existing textbook, without requiring expert annotation. At the task of predicting outcome and prerequisite concepts, we demonstrate improvements over a number of baselines on six textbooks, especially in the regime of little to no ground-truth labels available. Finally, we demonstrate the utility of a model learned using our approach at the task of identifying prerequisite documents for adaptive content recommendation --- an important step towards our vision of the "web as a textbook".},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {907–915},
numpages = {9},
keywords = {adaptive hypermedia, educational data mining, open corpus adaptive hypermedia, graphical models, semi-supervised machine learning},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098107,
author = {Li, Huayu and Ge, Yong and Zhu, Hengshu and Xiong, Hui and Zhao, Hongke},
title = {Prospecting the Career Development of Talents: A Survival Analysis Perspective},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098107},
doi = {10.1145/3097983.3098107},
abstract = {The study of career development has become more important during a time of rising competition. Even with the help of newly available big data in the field of human resources, it is challenging to prospect the career development of talents in an effective manner, since the nature and structure of talent careers can change quickly. To this end, in this paper, we propose a novel survival analysis approach to model the talent career paths, with a focus on two critical issues in talent management, namely turnover and career progression. Specifically, for modeling the talent turnover behaviors, we formulate the prediction of survival status at a sequence of time intervals as a multi-task learning problem by considering the prediction at each time interval as a task. Also, we impose the ranking constraints to model both censored and uncensored data, and capture the intrinsic properties exhibited in general lifetime modeling with non-recurrent and recurrent events. Similarly, for modeling the talent career progression, each task concerns the prediction of a relative occupational level at each time interval. The ranking constraints imposed on different occupational levels can help to reduce the prediction error. Finally, we evaluate our approach with several state-of-the-art baseline methods on real-world talent data. The experimental results clearly demonstrate the effectiveness of the proposed models for predicting the turnover and career progression of talents.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {917–925},
numpages = {9},
keywords = {ranking, multi-task learning, survival analysis, career path modeling, career development},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098115,
author = {Li, Huayu and Min, Martin Renqiang and Ge, Yong and Kadav, Asim},
title = {A Context-Aware Attention Network for Interactive Question Answering},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098115},
doi = {10.1145/3097983.3098115},
abstract = {Neural network based sequence-to-sequence models in an encoder-decoder framework have been successfully applied to solve Question Answering (QA) problems, predicting answers from statements and questions. However, almost all previous models have failed to consider detailed context information and unknown states under which systems do not have enough information to answer given questions. These scenarios with incomplete or ambiguous information are very common in the setting of Interactive Question Answering (IQA). To address this challenge, we develop a novel model, employing context-dependent word-level attention for more accurate statement representations and question-guided sentence-level attention for better context modeling. We also generate unique IQA datasets to test our model, which will be made publicly available. Employing these attention mechanisms, our model accurately understands when it can output an answer or when it requires generating a supplementary question for additional input depending on different contexts. When available, user's feedback is encoded and directly applied to update sentence-level attention to infer an answer. Extensive experiments on QA and IQA datasets quantitatively demonstrate the effectiveness of our model with significant improvement over state-of-the-art conventional QA models.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {927–935},
numpages = {9},
keywords = {attention, recurrent neural network, question answering, interactive question answering},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098136,
author = {Liu, Sulin and Pan, Sinno Jialin and Ho, Qirong},
title = {Distributed Multi-Task Relationship Learning},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098136},
doi = {10.1145/3097983.3098136},
abstract = {Multi-task learning aims to learn multiple tasks jointly by exploiting their relatedness to improve the generalization performance for each task. Traditionally, to perform multi-task learning, one needs to centralize data from all the tasks to a single machine. However, in many real-world applications, data of different tasks may be geo-distributed over different local machines. Due to heavy communication caused by transmitting the data and the issue of data privacy and security, it is impossible to send data of different task to a master machine to perform multi-task learning. Therefore, in this paper, we propose a distributed multi-task learning framework that simultaneously learns predictive models for each task as well as task relationships between tasks alternatingly in the parameter server paradigm. In our framework, we first offer a general dual form for a family of regularized multi-task relationship learning methods. Subsequently, we propose a communication-efficient primal-dual distributed optimization algorithm to solve the dual problem by carefully designing local subproblems to make the dual problem decomposable. Moreover, we provide a theoretical convergence analysis for the proposed algorithm, which is specific for distributed multi-task relationship learning. We conduct extensive experiments on both synthetic and real-world datasets to evaluate our proposed framework in terms of effectiveness and convergence.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {937–946},
numpages = {10},
keywords = {distributed multi-task learning, transfer learning},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098168,
author = {Liu, Yanchi and Liu, Chuanren and Lu, Xinjiang and Teng, Mingfei and Zhu, Hengshu and Xiong, Hui},
title = {Point-of-Interest Demand Modeling with Human Mobility Patterns},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098168},
doi = {10.1145/3097983.3098168},
abstract = {Point-of-Interest (POI) demand modeling in urban regions is critical for many applications such as business site selection and real estate investment. While some efforts have been made for the demand analysis of some specific POI categories, such as restaurants, it lacks systematic means to support POI demand modeling. To this end, in this paper, we develop a systematic POI demand modeling framework, named Region POI Demand Identification (RPDI), to model POI demands by exploiting the daily needs of people identified from their large-scale mobility data. Specifically, we first partition the urban space into spatially differentiated neighborhood regions formed by many small local communities. Then, the daily activity patterns of people traveling in the city will be extracted from human mobility data. Since the trip activities, even aggregated, are sparse and insufficient to directly identify the POI demands, especially for underdeveloped regions, we develop a latent factor model that integrates human mobility data, POI profiles, and demographic data to robustly model the POI demand of urban regions in a holistic way. In this model, POI preferences and supplies are used together with demographic features to estimate the POI demands simultaneously for all the urban regions interconnected in the city. Moreover, we also design efficient algorithms to optimize the latent model for large-scale data. Finally, experimental results on real-world data in New York City (NYC) show that our method is effective for identifying POI demands for different regions.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {947–955},
numpages = {9},
keywords = {human mobility, region demand, point-of-interest},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098180,
author = {Liu, Junming and Sun, Leilei and Li, Qiao and Ming, Jingci and Liu, Yanchi and Xiong, Hui},
title = {Functional Zone Based Hierarchical Demand Prediction For Bike System Expansion},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098180},
doi = {10.1145/3097983.3098180},
abstract = {Bike sharing systems, aiming at providing the missing links in public transportation systems, are becoming popular in urban cities. Many providers of bike sharing systems are ready to expand their bike stations from the existing service area to surrounding regions. A key to success for a bike sharing systems expansion is the bike demand prediction for expansion areas. There are two major challenges in this demand prediction problem: First. the bike transition records are not available for the expansion area and second. station level bike demand have big variances across the urban city. Previous research efforts mainly focus on discovering global features, assuming the station bike demands react equally to the global features, which brings large prediction error when the urban area is large and highly diversified. To address these challenges, in this paper, we develop a hierarchical station bike demand predictor which analyzes bike demands from functional zone level to station level. Specifically, we first divide the studied bike stations into functional zones by a novel Bi-clustering algorithm which is designed to cluster bike stations with similar POI characteristics and close geographical distances together. Then, the hourly bike check-ins and check-outs of functional zones are predicted by integrating three influential factors: distance preference, zone-to-zone preference, and zone characteristics. The station demand is estimated by studying the demand distributions among the stations within the same functional zone. Finally, the extensive experimental results on the NYC Citi Bike system with two expansion stages show the advantages of our approach on station demand and balance prediction for bike sharing system expansions.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {957–966},
numpages = {10},
keywords = {bike sharing system, clustering, demand prediction},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098129,
author = {Ma, Fenglong and Meng, Chuishi and Xiao, Houping and Li, Qi and Gao, Jing and Su, Lu and Zhang, Aidong},
title = {Unsupervised Discovery of Drug Side-Effects from Heterogeneous Data Sources},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098129},
doi = {10.1145/3097983.3098129},
abstract = {Drug side-effects become a worldwide public health concern, which are the fourth leading cause of death in the United States. Pharmaceutical industry has paid tremendous effort to identify drug side-effects during the drug development. However, it is impossible and impractical to identify all of them. Fortunately, drug side-effects can also be reported on heterogeneous platforms (i.e., data sources), such as FDA Adverse Event Reporting System and various online communities. However, existing supervised and semi-supervised approaches are not practical as annotating labels are expensive in the medical field. In this paper, we propose a novel and effective unsupervised model Sifter to automatically discover drug side-effects. Sifter enhances the estimation on drug side-effects by learning from various online platforms and measuring platform-level and user-level quality simultaneously. In this way, Sifter demonstrates better performance compared with existing approaches in terms of correctly identifying drug side-effects. Experimental results on five real-world datasets show that Sifter can significantly improve the performance of identifying side-effects compared with the state-of-the-art approaches.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {967–976},
numpages = {10},
keywords = {healthcare informatics, truth discovery, probabilistic graphical model, drug side-effects},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098101,
author = {Maurus, Samuel and Plant, Claudia},
title = {Let's See Your Digits: Anomalous-State Detection Using Benford's Law},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098101},
doi = {10.1145/3097983.3098101},
abstract = {Benford's Law explains a curious phenomenon in which the leading digits of "naturally-occurring" numerical data are distributed in a precise fashion. In this paper we begin by showing that system metrics generated by many modern information systems like Twitter, Wikipedia, YouTube and GitHub obey this law. We then propose a novel unsupervised approach called BenFound that exploits this property to detect anomalous system events. BenFound tracks the "Benfordness" of key system metrics, like the follower counts of tweeting Twitter users or the change deltas in Wikipedia page edits. It then applies a novel Benford-conformity test in real-time to identify "non-Benford events". We investigate a variety of such events, showing that they correspond to unnatural and often undesirable system interactions like spamming, hashtag-hijacking and denial-of-service attacks. The result is a technically-uncomplicated and effective "red flagging" technique that can be used to complement existing anomaly-detection approaches. Although not without its limitations, it is highly efficient and requires neither obscure parameters, nor text streams, nor natural-language processing.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {977–986},
numpages = {10},
keywords = {nonparametric statistical tests, data streams, anomaly detection, time series data, benford's law},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098113,
author = {Qi, Guo-Jun and Tang, Jiliang and Wang, Jingdong and Luo, Jiebo},
title = {Mixture Factorized Ornstein-Uhlenbeck Processes for Time-Series Forecasting},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098113},
doi = {10.1145/3097983.3098113},
abstract = {Forecasting the future observations of time-series data can be performed by modeling the trend and fluctuations from the observed data. Many classical time-series analysis models like Autoregressive model (AR) and its variants have been developed to achieve such forecasting ability. While they are often based on the white noise assumption to model the data fluctuations, a more general Brownian motion has been adopted that results in Ornstein-Uhlenbeck (OU) process. The OU process has gained huge successes in predicting the future observations over many genres of time series, however, it is still limited in modeling simple diffusion dynamics driven by a single persistent factor that never evolves over time. However, in many real problems, a mixture of hidden factors are usually present, and when and how frequently they appear or disappear are unknown ahead of time. This imposes a challenge that inspires us to develop a Mixture Factorized OU process (MFOUP) to model evolving factors. The new model is able to capture the changing states of multiple mixed hidden factors, from which we can infer their roles in driving the movements of time series. We conduct experiments on three forecasting problems, covering sensor and market data streams. The results show its competitive performance on predicting future observations and capturing evolution patterns of hidden factors as compared with the other algorithms.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {987–995},
numpages = {9},
keywords = {mixture factorized ornstein-uhlenbeck process (mfoup)},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098185,
author = {Qu, Meng and Ren, Xiang and Han, Jiawei},
title = {Automatic Synonym Discovery with Knowledge Bases},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098185},
doi = {10.1145/3097983.3098185},
abstract = {Recognizing entity synonyms from text has become a crucial task in many entity-leveraging applications. However, discovering entity synonyms from domain-specific text corpora (e.g., news articles, scientific papers) is rather challenging. Current systems take an entity name string as input to find out other names that are synonymous, ignoring the fact that often times a name string can refer to multiple entities (e.g., "apple" could refer to both Apple Inc. and the fruit apple). Moreover, most existing methods require training data manually created by domain experts to construct supervised-learning systems. In this paper, we study the problem of automatic synonym discovery with knowledge bases, that is, identifying synonyms for knowledge base entities in a given domain-specific corpus. The manually-curated synonyms for each entity stored in a knowledge base not only form a set of name strings to disambiguate the meaning for each other, but also can serve as "distant" supervision to help determine important features for the task. We propose a novel framework, called DPE, to integrate two kinds of mutually-complementing signals for synonym discovery, i.e., distributional features based on corpus-level statistics and textual patterns based on local contexts. In particular, DPE jointly optimizes the two kinds of signals in conjunction with distant supervision, so that they can mutually enhance each other in the training stage. At the inference stage, both signals will be utilized to discover synonyms for the given entities. Experimental results prove the effectiveness of the proposed framework.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {997–1005},
numpages = {9},
keywords = {distributional based approach, knowledge base, synonym discovery, distant supervision, pattern based approach},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098111,
author = {Raff, Edward and Nicholas, Charles},
title = {An Alternative to NCD for Large Sequences, Lempel-Ziv Jaccard Distance},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098111},
doi = {10.1145/3097983.3098111},
abstract = {The Normalized Compression Distance (NCD) has been used in a number of domains to compare objects with varying feature types. This flexibility comes from the use of general purpose compression algorithms as the means of computing distances between byte sequences. Such flexibility makes NCD particularly attractive for cases where the right features to use are not obvious, such as malware classification. However, NCD can be computationally demanding, thereby restricting the scale at which it can be applied. We introduce an alternative metric also inspired by compression, the Lempel-Ziv Jaccard Distance (LZJD). We show that this new distance has desirable theoretical properties, as well as comparable or superior performance for malware classification, while being easy to implement and orders of magnitude faster in practice.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1007–1015},
numpages = {9},
keywords = {lempel-ziv, malware classification, jaccard similarity, cyber security, normalized compression distance},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098199,
author = {Rozenshtein, Polina and Tatti, Nikolaj and Gionis, Aristides},
title = {Inferring the Strength of Social Ties: A Community-Driven Approach},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098199},
doi = {10.1145/3097983.3098199},
abstract = {Online social networks are growing and becoming denser.The social connections of a given person may have very high variability: from close friends and relatives to acquaintances to people who hardly know. Inferring the strength of social ties is an important ingredient for modeling the interaction of users in a network and understanding their behavior. Furthermore, the problem has applications in computational social science, viral marketing, and people recommendation. In this paper we study the problem of inferring the strength of social ties in a given network. Our work is motivated by a recent approach by Sintos et. al [24], which leverages the Strong Triadic Closure STC principle, a hypothesis rooted in social psychology. To guide our inference process, in addition to the network structure, we also consider as input a collection of tight communities. Those are sets of vertices that we expect to be connected via strong ties. Such communities appear in different situations, e.g., when being part of a community implies a strong connection to one of the existing members. We consider two related problem formalizations that reflect the assumptions of our setting: small number of STC violations and strong-tie connectivity in the input communities. We show that both problem formulations are NP-hard. We also show that one problem formulation is hard to approximate, while for the second we develop an algorithm with approximation guarantee. We validate the proposed method on real-world datasets by comparing with baselines that optimize STC violations and community connectivity separately.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1017–1025},
numpages = {9},
keywords = {approximation algorithms, strong triadic closure, social network analysis, network inference},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098192,
author = {Saveski, Martin and Pouget-Abadie, Jean and Saint-Jacques, Guillaume and Duan, Weitao and Ghosh, Souvik and Xu, Ya and Airoldi, Edoardo M.},
title = {Detecting Network Effects: Randomizing Over Randomized Experiments},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098192},
doi = {10.1145/3097983.3098192},
abstract = {Randomized experiments, or A/B tests, are the standard approach for evaluating the causal effects of new product features, i.e., treatments. The validity of these tests rests on the "stable unit treatment value assumption" (SUTVA), which implies that the treatment only affects the behavior of treated users, and does not affect the behavior of their connections. Violations of SUTVA, common in features that exhibit network effects, result in inaccurate estimates of the causal effect of treatment. In this paper, we leverage a new experimental design for testing whether SUTVA holds, without making any assumptions on how treatment effects may spill over between the treatment and the control group. To achieve this, we simultaneously run both a completely randomized and a cluster-based randomized experiment, and then we compare the difference of the resulting estimates. We present a statistical test for measuring the significance of this difference and offer theoretical bounds on the Type I error rate. We provide practical guidelines for implementing our methodology on large-scale experimentation platforms. Importantly, the proposed methodology can be applied to settings in which a network is not necessarily observed but, if available, can be used in the analysis. Finally, we deploy this design to LinkedIn's experimentation platform and apply it to two online experiments, highlighting the presence of network effects and bias in standard A/B testing approaches in a real-world setting.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1027–1035},
numpages = {9},
keywords = {spillovers, sutva, randomized experiment, network interference, experimental design, network effects, a/b testing},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098145,
author = {Scholtes, Ingo},
title = {When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098145},
doi = {10.1145/3097983.3098145},
abstract = {We introduce a framework for the modeling of sequential data capturing pathways of varying lengths observed in a network. Such data are important, e.g., when studying click streams in the Web, travel patterns in transportation systems, information cascades in social networks, biological pathways, or time-stamped social interactions. While it is common to apply graph analytics and network analysis to such data, recent works have shown that temporal correlations can invalidate the results of such methods. This raises a fundamental question: When is a network abstraction of sequential data justified?Addressing this open question, we propose a framework that combines Markov chains of multiple, higher orders into a multi-layer graphical model that captures temporal correlations in pathways at multiple length scales simultaneously. We develop a model selection technique to infer the optimal number of layers of such a model and show that it outperforms baseline Markov order detection techniques. An application to eight real-world data sets on pathways and temporal networks shows that it allows to infer graphical models that capture both topological and temporal characteristics of such data. Our work highlights fallacies of network abstractions and provides a principled answer to the open question when they are justified. Generalizing network representations to multi-order graphical models, it opens perspectives for new data mining and knowledge discovery algorithms.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1037–1046},
numpages = {10},
keywords = {graph theory, knowledge discovery, pagerank, graphical model, graph analytics, time series data, time series analysis, dynamic graph, information systems, dynamic network analysis, graph mining, temporal networks, temporal data, sequential data, click stream analysis, data mining, network science, social network analysis, sequence mining, higher-order model, network analysis, relational data, higher-order network, click paths, markov chain, pathway data},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098177,
author = {Shen, Yelong and Huang, Po-Sen and Gao, Jianfeng and Chen, Weizhu},
title = {ReasoNet: Learning to Stop Reading in Machine Comprehension},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098177},
doi = {10.1145/3097983.3098177},
abstract = {Teaching a computer to read and answer general questions pertaining to a document is a challenging yet unsolved problem. In this paper, we describe a novel neural network architecture called the Reasoning Network (ReasoNet) for machine comprehension tasks. ReasoNets make use of multiple turns to effectively exploit and then reason over the relation among queries, documents, and answers. Different from previous approaches using a fixed number of turns during inference, ReasoNets introduce a termination state to relax this constraint on the reasoning depth. With the use of reinforcement learning, ReasoNets can dynamically determine whether to continue the comprehension process after digesting intermediate results, or to terminate reading when it concludes that existing information is adequate to produce an answer. ReasoNets achieve superior performance in machine comprehension datasets, including unstructured CNN and Daily Mail datasets, the Stanford SQuAD dataset, and a structured Graph Reachability dataset.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1047–1055},
numpages = {9},
keywords = {deep reinforcement learning, reasonet, machine reading comprehension},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098087,
author = {Shin, Kijung and Hooi, Bryan and Kim, Jisu and Faloutsos, Christos},
title = {DenseAlert: Incremental Dense-Subtensor Detection in Tensor Streams},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098087},
doi = {10.1145/3097983.3098087},
abstract = {Consider a stream of retweet events - how can we spot fraudulent lock-step behavior in such multi-aspect data (i.e., tensors) evolving over time? Can we detect it in real time, with an accuracy guarantee? Past studies have shown that dense subtensors tend to indicate anomalous or even fraudulent behavior in many tensor data, including social media, Wikipedia, and TCP dumps. Thus, several algorithms have been proposed for detecting dense subtensors rapidly and accurately. However, existing algorithms assume that tensors are static, while many real-world tensors, including those mentioned above, evolve over time.We propose DENSESTREAM, an incremental algorithm that maintains and updates a dense subtensor in a tensor stream (i.e., a sequence of changes in a tensor), and DENSESALERT, an incremental algorithm spotting the sudden appearances of dense subtensors. Our algorithms are: (1) Fast and "any time": updates by our algorithms are up to a million times faster than the fastest batch algorithms, (2) Provably accurate: our algorithms guarantee a lower bound on the density of the subtensor they maintain, and (3) Effective: our DENSESALERT successfully spots anomalies in real-world tensors, especially those overlooked by existing algorithms.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1057–1066},
numpages = {10},
keywords = {incremental algorithm, fraud detection, dense-subtensor detection, anomaly detection, tensor stream},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098144,
author = {Siffer, Alban and Fouque, Pierre-Alain and Termier, Alexandre and Largouet, Christine},
title = {Anomaly Detection in Streams with Extreme Value Theory},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098144},
doi = {10.1145/3097983.3098144},
abstract = {Anomaly detection in time series has attracted considerable attention due to its importance in many real-world applications including intrusion detection, energy management and finance. Most approaches for detecting outliers rely on either manually set thresholds or assumptions on the distribution of data according to Chandola, Banerjee and Kumar.Here, we propose a new approach to detect outliers in streaming univariate time series based on Extreme Value Theory that does not require to hand-set thresholds and makes no assumption on the distribution: the main parameter is only the risk, controlling the number of false positives. Our approach can be used for outlier detection, but more generally for automatically setting thresholds, making it useful in wide number of situations. We also experiment our algorithms on various real-world datasets which confirm its soundness and efficiency.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1067–1075},
numpages = {9},
keywords = {extreme value theory, outliers in time series, streaming},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098146,
author = {Singh, Mayank and Sarkar, Rajdeep and Goyal, Pawan and Mukherjee, Animesh and Chakrabarti, Soumen},
title = {Relay-Linking Models for Prominence and Obsolescence in Evolving Networks},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098146},
doi = {10.1145/3097983.3098146},
abstract = {The rate at which nodes in evolving social networks acquire links (friends, citations) shows complex temporal dynamics. Preferential attachment and link copying models, while enabling elegant analysis, only capture rich-gets-richer effects, not aging and decline. Recent aging models are complex and heavily parameterized; most involve estimating 1-3 parameters per node. These parameters are intrinsic: they explain decline in terms of events in the past of the same node, and do not explain, using the network, where the linking attention might go instead. We argue that traditional characterization of linking dynamics are insufficient to judge the faithfulness of models. We propose a new temporal sketch of an evolving graph, and introduce several new characterizations of a network's temporal dynamics. Then we propose a new family of frugal aging models with no per-node parameters and only two global parameters. Our model is based on a surprising inversion or undoing of triangle completion, where an old node relays a citation to a younger follower in its immediate vicinity. Despite very few parameters, the new family of models shows remarkably better fit with real data. Before concluding, we analyze temporal signatures for various research communities yielding further insights into their comparative dynamics. To facilitate reproducible research, we shall soon make all the codes and the processed dataset available in the public domain.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1077–1086},
numpages = {10},
keywords = {aging models, relay-link, network growth models},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098098,
author = {Song, Hwanjun and Lee, Jae-Gil and Han, Wook-Shin},
title = {PAMAE: Parallel <i>k</i>-Medoids Clustering with High Accuracy and Efficiency},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098098},
doi = {10.1145/3097983.3098098},
abstract = {The k-medoids algorithm is one of the best-known clustering algorithms. Despite this, however, it is not as widely used for big data analytics as the k-means algorithm, mainly because of its high computational complexity. Many studies have attempted to solve the efficiency problem of the k-medoids algorithm, but all such studies have improved efficiency at the expense of accuracy. In this paper, we propose a novel parallel k-medoids algorithm, which we call PAMAE, that achieves both high accuracy and high efficiency. We identify two factors---"global search" and "entire data"---that are essential to achieving high accuracy, but are also very time-consuming if considered simultaneously. Thus, our key idea is to apply them individually through two phases: parallel seeding and parallel refinement, neither of which is costly. The first phase performs global search over sampled data, and the second phase performs local search over entire data. Our theoretical analysis proves that this serial execution of the two phases leads to an accurate solution that would be achieved by global search over entire data. In order to validate the merit of our approach, we implement PAMAE on Spark as well as Hadoop and conduct extensive experiments using various real-world data sets on 12 Microsoft Azure machines (48 cores). The results show that PAMAE significantly outperforms most of recent parallel algorithms and, at the same time, produces a clustering quality as comparable as the previous most-accurate algorithm. The source code and data are available at https://github.com/jaegil/k-Medoid.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1087–1096},
numpages = {10},
keywords = {parallelization, hadoop, k-medoids, sampling, spark, pam},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098153,
author = {St.Amand, Joseph and Huan, Jun},
title = {Sparse Compositional Local Metric Learning},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098153},
doi = {10.1145/3097983.3098153},
abstract = {Mahalanobis distance metric learning becomes an especially challenging problem as the dimension of the feature space p is scaled upwards. The number of parameters to optimize grows with space complexity of order O (p 2), making storage infeasible, interpretability poor, and causing the model to have a high tendency to overfit. Additionally, optimization while maintaining feasibility of the solution becomes prohibitively expensive, requiring a projection onto the positive semi-definite cone after every iteration. In addition to the obvious space and computational challenges, vanilla distance metric learning is unable to model complex and multi-modal trends in the data. Inspired by the recent resurgence of Frank-Wolfe style optimization, we propose a new method for sparse compositional local Mahalanobis distance metric learning. Our proposed technique learns a set of distance metrics which are composed of local and global components. We capture local interactions in the feature space, while ensuring that all metrics share a global component, which may act as a regularizer. We optimize our model using an alternating pairwise Frank-Wolfe style algorithm. This serves a dual purpose, we can control the sparsity of our solution, and altogether avoid any expensive projection operations. Finally, we conduct an empirical evaluation of our method with the current state of the art and present the results on five datasets from varying domains.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1097–1104},
numpages = {8},
keywords = {frank-wolfe optimization, sparse metric learning, mahalanobis distance},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098166,
author = {Tang, Jian and Wang, Yue and Zheng, Kai and Mei, Qiaozhu},
title = {End-to-End Learning for Short Text Expansion},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098166},
doi = {10.1145/3097983.3098166},
abstract = {Effectively making sense of short texts is a critical task for many real world applications such as search engines, social media services, and recommender systems. The task is particularly challenging as a short text contains very sparse information, often too sparse for a machine learning algorithm to pick up useful signals. A common practice for analyzing short text is to first expand it with external information, which is usually harvested from a large collection of longer texts. In literature, short text expansion has been done with all kinds of heuristics. We propose an end-to-end solution that automatically learns how to expand short text to optimize a given learning task. A novel deep memory network is proposed to automatically find relevant information from a collection of longer documents and reformulate the short text through a gating mechanism. Using short text classification as a demonstrating task, we show that the deep memory network significantly outperforms classical text expansion methods with comprehensive experiments on real world data sets.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1105–1113},
numpages = {9},
keywords = {query expansion, memory networks, short text classification},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098119,
author = {Tillman, B\'{a}lint and Markopoulou, Athina and Butts, Carter T. and Gjoka, Minas},
title = {Construction of Directed 2K Graphs},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098119},
doi = {10.1145/3097983.3098119},
abstract = {We study the problem of generating synthetic graphs that resemble real-world directed graphs in terms of their degree correlations. In order to capture degree correlation specifically for directed graphs, we define directed 2K (D2K) as those graphs with a given directed degree sequence (DDS) and a given target joint degree and attribute matrix (JDAM). We provide necessary and sufficient conditions for a target D2K to be realizable and we design an efficient algorithm that generates graph realizations with exactly the target D2K. We apply our algorithm to generate synthetic graphs that target real-world directed graphs (such as Twitter), and we demonstrate its benefits compared to state-of-the-art construction algorithms.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1115–1124},
numpages = {10},
keywords = {construction algorithms, directed graphs, graph realizations},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098161,
author = {Ustun, Berk and Rudin, Cynthia},
title = {Optimized Risk Scores},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098161},
doi = {10.1145/3097983.3098161},
abstract = {Risk scores are simple classification models that let users quickly assess risk by adding, subtracting, and multiplying a few small numbers. Such models are widely used in healthcare and criminal justice, but are often built ad hoc. In this paper, we present a principled approach to learn risk scores that are fully optimized for feature selection, integer coefficients, and operational constraints. We formulate the risk score problem as a mixed integer nonlinear program, and present a new cutting plane algorithm to efficiently recover its optimal solution. Our approach can fit optimized risk scores in a way that scales linearly with the sample size of a dataset, provides a proof of optimality, and obeys complex constraints without parameter tuning. We illustrate these benefits through an extensive set of numerical experiments, and an application where we build a customized risk score for ICU seizure prediction.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1125–1134},
numpages = {10},
keywords = {interpretable models, classification, seizure prediction, mixed integer non-linear programming, risk scores, cutting plane methods},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098122,
author = {Wang, Hao and Fu, Yanmei and Wang, Qinyong and Yin, Hongzhi and Du, Changying and Xiong, Hui},
title = {A Location-Sentiment-Aware Recommender System for Both Home-Town and Out-of-Town Users},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098122},
doi = {10.1145/3097983.3098122},
abstract = {Spatial item recommendation has become an important means to help people discover interesting locations, especially when people pay a visit to unfamiliar regions. Some current researches are focusing on modelling individual and collective geographical preferences for spatial item recommendation based on users' check-in records, but they fail to explore the phenomenon of user interest drift across geographical regions, i.e., users would show different interests when they travel to different regions. Besides, they ignore the influence of public comments for subsequent users' check-in behaviors. Specifically, it is intuitive that users would refuse to check in to a spatial item whose historical reviews seem negative overall, even though it might fit their interests. Therefore, it is necessary to recommend the right item to the right user at the right location. In this paper, we propose a latent probabilistic generative model called LSARS to mimic the decision-making process of users' check-in activities both in home-town and out-of-town scenarios by adapting to user interest drift and crowd sentiments, which can learn location-aware and sentiment-aware individual interests from the contents of spatial items and user reviews. Due to the sparsity of user activities in out-of-town regions, LSARS is further designed to incorporate the public preferences learned from local users' check-in behaviors. Finally, we deploy LSARS into two practical application scenes: spatial item recommendation and target user discovery. Extensive experiments on two large-scale location-based social networks (LBSNs) datasets show that LSARS achieves better performance than existing state-of-the-art methods.},
booktitle = {Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1135–1143},
numpages = {9},
keywords = {user interest drift, check-in behavior, crowd sentiment, recommendation},
location = {Halifax, NS, Canada},
series = {KDD '17}
}

@inproceedings{10.1145/3097983.3098158,
author = {Wang, Qinglong and Guo, Wenbo and Zhang, Kaixuan and Ororbia, Alexander G. and Xing, Xinyu and Liu, Xue and Giles, C. Lee},
title = {Adversary Resistant Deep Neural Networks with an Application to Malware Detection},
year = {2017},
isbn = {9781450348874},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3097983.3098158},
doi = {10.1145/3097983.3098158},
abstract = {Outside the highly publicized victories in the game of Go, there have been numerous successful applications of deep learning in the fields of information retrieval, computer vision, and speech recognition. In cybersecurity, an increasing number of companies have begun exploring the use of deep learning (DL) in a variety of security tasks with malware detection among the more popular. These companies claim that deep neural networks (DNNs) could help turn the tide in the war against malware infection. However, DNNs are vulnerable to adversarial samples, a shortcoming that plagues most, if not all, statistical and machine learning models. Recent research has demonstrated that those with malicious intent can easily circumvent deep learning-powered malware detection by exploiting this weakness.To address this problem, previous work developed defense mechanisms that are based on augmenting training data

license_type: permissive

branch_name: refs/heads/main

extension: bib