text:
, Kai and Zhou, Xiaofang},
title = {Exploiting Viral Marketing for Location Promotion in Location-Based Social Networks},
year = {2016},
issue_date = {December 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3001938},
doi = {10.1145/3001938},
abstract = {With the explosion of smartphones and social network services, location-based social networks (LBSNs) are increasingly seen as tools for businesses (e.g., restaurants and hotels) to promote their products and services. In this article, we investigate the key techniques that can help businesses promote their locations by advertising wisely through the underlying LBSNs. In order to maximize the benefit of location promotion, we formalize it as an influence maximization problem in an LBSN, i.e., given a target location and an LBSN, a set of k users (called seeds) should be advertised initially such that they can successfully propagate and attract many other users to visit the target location. Existing studies have proposed different ways to calculate the information propagation probability, that is, how likely it is that a user may influence another, in the setting of a static social network. However, it is more challenging to derive the propagation probability in an LBSN since it is heavily affected by the target location and the user mobility, both of which are dynamic and query dependent. This article proposes two user mobility models, namely the Gaussian-based and distance-based mobility models, to capture the check-in behavior of individual LBSN users, based on which location-aware propagation probabilities can be derived. Extensive experiments based on two real LBSN datasets have demonstrated the superior effectiveness of our proposals compared with existing static models of propagation probabilities to truly reflect the information propagation in LBSNs.},
journal = {ACM Trans. Knowl. Discov. Data},
month = nov,
articleno = {25},
numpages = {28},
keywords = {Propagation probability, check-in behavior, location-based social network, influence maximization}
}

@article{10.1145/2934692,
author = {Fu, Yanjie and Xiong, Hui and Ge, Yong and Zheng, Yu and Yao, Zijun and Zhou, Zhi-Hua},
title = {Modeling of Geographic Dependencies for Real Estate Ranking},
year = {2016},
issue_date = {August 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2934692},
doi = {10.1145/2934692},
abstract = {It is traditionally a challenge for home buyers to understand, compare, and contrast the investment value of real estate. Although a number of appraisal methods have been developed to value real properties, the performances of these methods have been limited by traditional data sources for real estate appraisal. With the development of new ways of collecting estate-related mobile data, there is a potential to leverage geographic dependencies of real estate for enhancing real estate appraisal. Indeed, the geographic dependencies of the investment value of an estate can be from the characteristics of its own neighborhood (individual), the values of its nearby estates (peer), and the prosperity of the affiliated latent business area (zone). To this end, in this paper, we propose a geographic method, named ClusRanking, for real estate appraisal by leveraging the mutual enforcement of ranking and clustering power. ClusRanking is able to exploit geographic individual, peer, and zone dependencies in a probabilistic ranking model. Specifically, we first extract the geographic utility of estates from geography data, estimate the neighborhood popularity of estates by mining taxicab trajectory data, and model the influence of latent business areas. Also, we fuse these three influential factors and predict real estate investment value. Moreover, we simultaneously consider individual, peer and zone dependencies, and derive an estate-specific ranking likelihood as the objective function. Furthermore, we propose an improved method named CR-ClusRanking by incorporating checkin information as a regularization term which reduces the performance volatility of real estate ranking system. Finally, we conduct a comprehensive evaluation with the real estate-related data of Beijing, and the experimental results demonstrate the effectiveness of our proposed methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {11},
numpages = {27},
keywords = {Real estate, ranking, clustering, geographic dependencies}
}

@article{10.1145/2936718,
author = {Wang, Wei and Leskovec, Jure},
title = {Introduction to the Special Issue of Best Papers in ACM SIGKDD 2014},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2936718},
doi = {10.1145/2936718},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {33},
numpages = {2}
}

@article{10.1145/2744204,
author = {Wei, Ying and Song, Yangqiu and Zhen, Yi and Liu, Bo and Yang, Qiang},
title = {Heterogeneous Translated Hashing: A Scalable Solution Towards Multi-Modal Similarity Search},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2744204},
doi = {10.1145/2744204},
abstract = {Multi-modal similarity search has attracted considerable attention to meet the need of information retrieval across different types of media. To enable efficient multi-modal similarity search in large-scale databases recently, researchers start to study multi-modal hashing. Most of the existing methods are applied to search across multi-views among which explicit correspondence is provided. Given a multi-modal similarity search task, we observe that abundant multi-view data can be found on the Web which can serve as an auxiliary bridge. In this paper, we propose a Heterogeneous Translated Hashing (HTH) method with such auxiliary bridge incorporated not only to improve current multi-view search but also to enable similarity search across heterogeneous media which have no direct correspondence. HTH provides more flexible and discriminative ability by embedding heterogeneous media into different Hamming spaces, compared to almost all existing methods that map heterogeneous data in a common Hamming space. We formulate a joint optimization model to learn hash functions embedding heterogeneous media into different Hamming spaces, and a translator aligning different Hamming spaces. The extensive experiments on two real-world datasets, one publicly available dataset of Flickr, and the other MIRFLICKR-Yahoo Answers dataset, highlight the effectiveness and efficiency of our algorithm.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {36},
numpages = {28},
keywords = {heterogeneous translated hashing, similarity search, Hash function learning, scalability}
}

@article{10.1145/2943785,
author = {Qiao, Maoying and Xu, Richard Yi Da and Bian, Wei and Tao, Dacheng},
title = {Fast Sampling for Time-Varying Determinantal Point Processes},
year = {2016},
issue_date = {August 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2943785},
doi = {10.1145/2943785},
abstract = {Determinantal Point Processes (DPPs) are stochastic models which assign each subset of a base dataset with a probability proportional to the subset’s degree of diversity. It has been shown that DPPs are particularly appropriate in data subset selection and summarization (e.g., news display, video summarizations). DPPs prefer diverse subsets while other conventional models cannot offer. However, DPPs inference algorithms have a polynomial time complexity which makes it difficult to handle large and time-varying datasets, especially when real-time processing is required. To address this limitation, we developed a fast sampling algorithm for DPPs which takes advantage of the nature of some time-varying data (e.g., news corpora updating, communication network evolving), where the data changes between time stamps are relatively small. The proposed algorithm is built upon the simplification of marginal density functions over successive time stamps and the sequential Monte Carlo (SMC) sampling technique. Evaluations on both a real-world news dataset and the Enron Corpus confirm the efficiency of the proposed algorithm.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {8},
numpages = {24},
keywords = {fast sampling, Time-varying determinantal point processes (TV-DPPs), sequential Monte Carlo}
}

@article{10.1145/2953882,
author = {Crescenzi, Pierluigi and D'angelo, Gianlorenzo and Severini, Lorenzo and Velaj, Yllka},
title = {Greedily Improving Our Own Closeness Centrality in a Network},
year = {2016},
issue_date = {August 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2953882},
doi = {10.1145/2953882},
abstract = {The closeness centrality is a well-known measure of importance of a vertex within a given complex network. Having high closeness centrality can have positive impact on the vertex itself: hence, in this paper we consider the optimization problem of determining how much a vertex can increase its centrality by creating a limited amount of new edges incident to it. We will consider both the undirected and the directed graph cases. In both cases, we first prove that the optimization problem does not admit a polynomial-time approximation scheme (unless P = NP), and then propose a greedy approximation algorithm (with an almost tight approximation ratio), whose performance is then tested on synthetic graphs and real-world networks.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {9},
numpages = {32},
keywords = {Approximation algorithms, graph augmentation, greedy algorithm, large networks}
}

@article{10.1145/2934688,
author = {Shao, Junming and Yang, Qinli and Dang, Hoang-Vu and Schmidt, Bertil and Kramer, Stefan},
title = {Scalable Clustering by Iterative Partitioning and Point Attractor Representation},
year = {2016},
issue_date = {August 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2934688},
doi = {10.1145/2934688},
abstract = {Clustering very large datasets while preserving cluster quality remains a challenging data-mining task to date. In this paper, we propose an effective scalable clustering algorithm for large datasets that builds upon the concept of synchronization. Inherited from the powerful concept of synchronization, the proposed algorithm, CIPA (Clustering by Iterative Partitioning and Point Attractor Representations), is capable of handling very large datasets by iteratively partitioning them into thousands of subsets and clustering each subset separately. Using dynamic clustering by synchronization, each subset is then represented by a set of point attractors and outliers. Finally, CIPA identifies the cluster structure of the original dataset by clustering the newly generated dataset consisting of points attractors and outliers from all subsets. We demonstrate that our new scalable clustering approach has several attractive benefits: (a) CIPA faithfully captures the cluster structure of the original data by performing clustering on each separate data iteratively instead of using any sampling or statistical summarization technique. (b) It allows clustering very large datasets efficiently with high cluster quality. (c) CIPA is parallelizable and also suitable for distributed data. Extensive experiments demonstrate the effectiveness and efficiency of our approach.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {5},
numpages = {23},
keywords = {High-performance algorithm, synchronization, scalable clustering}
}

@article{10.1145/2910586,
author = {Wu, Ou and You, Qiang and Xia, Fen and Ma, Lei and Hu, Weiming},
title = {Listwise Learning to Rank from Crowds},
year = {2016},
issue_date = {August 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2910586},
doi = {10.1145/2910586},
abstract = {Learning to rank has received great attention in recent years as it plays a crucial role in many applications such as information retrieval and data mining. The existing concept of learning to rank assumes that each training instance is associated with a reliable label. However, in practice, this assumption does not necessarily hold true as it may be infeasible or remarkably expensive to obtain reliable labels for many learning to rank applications. Therefore, a feasible approach is to collect labels from crowds and then learn a ranking function from crowdsourcing labels. This study explores the listwise learning to rank with crowdsourcing labels obtained from multiple annotators, who may be unreliable. A new probabilistic ranking model is first proposed by combining two existing models. Subsequently, a ranking function is trained by proposing a maximum likelihood learning approach, which estimates ground-truth labels and annotator expertise, and trains the ranking function iteratively. In practical crowdsourcing machine learning, valuable side information (e.g., professional grades) about involved annotators is normally attainable. Therefore, this study also investigates learning to rank from crowd labels when side information on the expertise of involved annotators is available. In particular, three basic types of side information are investigated, and corresponding learning algorithms are consequently introduced. Further, the top-k learning to rank from crowdsourcing labels are explored to deal with long training ranking lists. The proposed algorithms are tested on both synthetic and real-world data. Results reveal that the maximum likelihood estimation approach significantly outperforms the average approach and existing crowdsourcing regression methods. The performances of the proposed algorithms are comparable to those of the learning model in consideration reliable labels. The results of the investigation further indicate that side information is helpful in inferring both ranking functions and expertise degrees of annotators.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {4},
numpages = {39},
keywords = {multiple annotators, crowdsourcing, Listwise learning to rank, side information, probabilistic ranking model}
}

@article{10.1145/2948068,
author = {Li, Xiang and Ling, Charles X. and Wang, Huaimin},
title = {The Convergence Behavior of Naive Bayes on Large Sparse Datasets},
year = {2016},
issue_date = {August 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2948068},
doi = {10.1145/2948068},
abstract = {Large and sparse datasets with a lot of missing values are common in the big data era, such as user behaviors over a large number of items. Classification in such datasets is an important topic for machine learning and data mining. Practically, naive Bayes is still a popular classification algorithm for large sparse datasets, as its time and space complexity scales linearly with the size of non-missing values. However, several important questions about the behavior of naive Bayes are yet to be answered. For example, how different mechanisms of data missing, data sparsity, and the number of attributes systematically affect the learning curves and convergence? In this paper, we address several common data missing mechanisms and propose novel data generation methods based on these mechanisms. We generate large and sparse data systematically, and study the entire AUC (Area Under ROC Curve) learning curve and convergence behavior of naive Bayes. We not only have several important experiment observations, but also provide detailed theoretic studies. Finally, we summarize our empirical and theoretic results as an intuitive decision flowchart and a useful guideline for classifying large sparse datasets in practice.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {10},
numpages = {24},
keywords = {large sparse data, Convergence behavior}
}

@article{10.1145/2934693,
author = {Zhang, Xianchao and Zong, Linlin and You, Quanzeng and Yong, Xing},
title = {Sampling for Nystr\"{o}m Extension-Based Spectral Clustering: Incremental Perspective and Novel Analysis},
year = {2016},
issue_date = {August 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2934693},
doi = {10.1145/2934693},
abstract = {Sampling is the key aspect for Nystr\"{o}m extension based spectral clustering. Traditional sampling schemes select the set of landmark points on a whole and focus on how to lower the matrix approximation error. However, the matrix approximation error does not have direct impact on the clustering performance. In this article, we propose a sampling framework from an incremental perspective, i.e., the landmark points are selected one by one, and each next point to be sampled is determined by previously selected landmark points. Incremental sampling builds explicit relationships among landmark points; thus, they work together well and provide a theoretical guarantee on the clustering performance. We provide two novel analysis methods and propose two schemes for selecting-the-next-one of the framework. The first scheme is based on clusterability analysis, which provides a better guarantee on clustering performance than schemes based on matrix approximation error analysis. The second scheme is based on loss analysis, which provides maximized predictive ability of the landmark points on the (implicit) labels of the unsampled points. Experimental results on a wide range of benchmark datasets demonstrate the superiorities of our proposed incremental sampling schemes over existing sampling schemes.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {7},
numpages = {25},
keywords = {Nystr\"{o}m extension, clusterability analysis, Spectral clustering, incremental sampling, loss analysis}
}

@article{10.1145/2930671,
author = {Yu, Zhiwen and Tian, Miao and Wang, Zhu and Guo, Bin and Mei, Tao},
title = {Shop-Type Recommendation Leveraging the Data from Social Media and Location-Based Services},
year = {2016},
issue_date = {August 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2930671},
doi = {10.1145/2930671},
abstract = {It is an important yet challenging task for investors to determine the most suitable type of shop (e.g., restaurant, fashion) for a newly opened store. Traditional ways are predominantly field surveys and empirical estimation, which are not effective as they lack shop-related data. As social media and location-based services (LBS) are becoming more and more pervasive, user-generated data from these platforms are providing rich information not only about individual consumption experiences, but also about shop attributes. In this paper, we investigate the recommendation of shop types for a given location, by leveraging heterogeneous data that are mainly historical user preferences and location context from social media and LBS. Our goal is to select the most suitable shop type, seeking to maximize the number of customers served from a candidate set of types. We propose a novel bias learning matrix factorization method with feature fusion for shop popularity prediction. Features are defined and extracted from two perspectives: location, where features are closely related to location characteristics, and commercial, where features are about the relationships between shops in the neighborhood. Experimental results show that the proposed method outperforms state-of-the-art solutions.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {1},
numpages = {21},
keywords = {Social media, shop-type recommendation, location-based services, matrix factorization}
}

@article{10.1145/2898358,
author = {McDowell, Luke K. and Aha, David W.},
title = {Leveraging Neighbor Attributes for Classification in Sparsely Labeled Networks},
year = {2016},
issue_date = {August 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2898358},
doi = {10.1145/2898358},
abstract = {Many analysis tasks involve linked nodes, such as people connected by friendship links. Research on link-based classification (LBC) has studied how to leverage these connections to improve classification accuracy. Most such prior research has assumed the provision of a densely labeled training network. Instead, this article studies the common and challenging case when LBC must use a single sparsely labeled network for both learning and inference, a case where existing methods often yield poor accuracy. To address this challenge, we introduce a novel method that enables prediction via “neighbor attributes,” which were briefly considered by early LBC work but then abandoned due to perceived problems. We then explain, using both extensive experiments and loss decomposition analysis, how using neighbor attributes often significantly improves accuracy. We further show that using appropriate semi-supervised learning (SSL) is essential to obtaining the best accuracy in this domain and that the gains of neighbor attributes remain across a range of SSL choices and data conditions. Finally, given the challenges of label sparsity for LBC and the impact of neighbor attributes, we show that multiple previous studies must be re-considered, including studies regarding the best model features, the impact of noisy attributes, and strategies for active learning.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {2},
numpages = {37},
keywords = {link-based classification, collective inference, statistical relational learning, Collective classification}
}

@article{10.1145/2940329,
author = {Grabocka, Josif and Schilling, Nicolas and Schmidt-Thieme, Lars},
title = {Latent Time-Series Motifs},
year = {2016},
issue_date = {August 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2940329},
doi = {10.1145/2940329},
abstract = {Motifs are the most repetitive/frequent patterns of a time-series. The discovery of motifs is crucial for practitioners in order to understand and interpret the phenomena occurring in sequential data. Currently, motifs are searched among series sub-sequences, aiming at selecting the most frequently occurring ones. Search-based methods, which try out series sub-sequence as motif candidates, are currently believed to be the best methods in finding the most frequent patterns.However, this paper proposes an entirely new perspective in finding motifs. We demonstrate that searching is non-optimal since the domain of motifs is restricted, and instead we propose a principled optimization approach able to find optimal motifs. We treat the occurrence frequency as a function and time-series motifs as its parameters, therefore we learn the optimal motifs that maximize the frequency function. In contrast to searching, our method is able to discover the most repetitive patterns (hence optimal), even in cases where they do not explicitly occur as sub-sequences. Experiments on several real-life time-series datasets show that the motifs found by our method are highly more frequent than the ones found through searching, for exactly the same distance threshold.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {6},
numpages = {20},
keywords = {Time series, motifs, repeated patterns}
}

@article{10.1145/2910585,
author = {Chang, Xiaojun and Nie, Feiping and Yang, Yi and Zhang, Chengqi and Huang, Heng},
title = {Convex Sparse PCA for Unsupervised Feature Learning},
year = {2016},
issue_date = {August 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2910585},
doi = {10.1145/2910585},
abstract = {Principal component analysis (PCA) has been widely applied to dimensionality reduction and data pre-processing for different applications in engineering, biology, social science, and the like. Classical PCA and its variants seek for linear projections of the original variables to obtain the low-dimensional feature representations with maximal variance. One limitation is that it is difficult to interpret the results of PCA. Besides, the classical PCA is vulnerable to certain noisy data. In this paper, we propose a Convex Sparse Principal Component Analysis (CSPCA) algorithm and apply it to feature learning. First, we show that PCA can be formulated as a low-rank regression optimization problem. Based on the discussion, the l2, 1-normminimization is incorporated into the objective function to make the regression coefficients sparse, thereby robust to the outliers. Also, based on the sparse model used in CSPCA, an optimal weight is assigned to each of the original feature, which in turn provides the output with good interpretability. With the output of our CSPCA, we can effectively analyze the importance of each feature under the PCA criteria. Our new objective function is convex, and we propose an iterative algorithm to optimize it. We apply the CSPCA algorithm to feature selection and conduct extensive experiments on seven benchmark datasets. Experimental results demonstrate that the proposed algorithm outperforms state-of-the-art unsupervised feature selection algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {3},
numpages = {16},
keywords = {Principal component analysis (PCA), feature analysis, convex PCA, sparse PCA}
}

@article{10.1145/2753764,
author = {Xu, Silei and Lui, John C. S.},
title = {Product Selection Problem: Improve Market Share by Learning Consumer Behavior},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2753764},
doi = {10.1145/2753764},
abstract = {It is often crucial for manufacturers to decide what products to produce so that they can increase their market share in an increasingly fierce market. To decide which products to produce, manufacturers need to analyze the consumers’ requirements and how consumers make their purchase decisions so that the new products will be competitive in the market. In this paper, we first present a general distance-based product adoption model to capture consumers’ purchase behavior. Using this model, various distance metrics can be used to describe different real life purchase behavior. We then provide a learning algorithm to decide which set of distance metrics one should use when we are given some accessible historical purchase data. Based on the product adoption model, we formalize the k most marketable products (or k-MMP) selection problem and formally prove that the problem is NP-hard. To tackle this problem, we propose an efficient greedy-based approximation algorithm with a provable solution guarantee. Using submodularity analysis, we prove that our approximation algorithm can achieve at least 63% of the optimal solution. We apply our algorithm on both synthetic datasets and real-world datasets (TripAdvisor.com), and show that our algorithm can easily achieve five or more orders of speedup over the exhaustive search and achieve about 96% of the optimal solution on average. Our experiments also demonstrate the robustness of our distance metric learning method, and illustrate how one can adopt it to improve the accuracy of product selection.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {34},
numpages = {25},
keywords = {submodular set function, approximation algorithm, Product selection, model learning, consumer behavior}
}

@article{10.1145/2746403,
author = {Jiang, Meng and Cui, Peng and Beutel, Alex and Faloutsos, Christos and Yang, Shiqiang},
title = {Catching Synchronized Behaviors in Large Networks: A Graph Mining Approach},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2746403},
doi = {10.1145/2746403},
abstract = {Given a directed graph of millions of nodes, how can we automatically spot anomalous, suspicious nodes judging only from their connectivity patterns? Suspicious graph patterns show up in many applications, from Twitter users who buy fake followers, manipulating the social network, to botnet members performing distributed denial of service attacks, disturbing the network traffic graph. We propose a fast and effective method, CatchSync, which exploits two of the tell-tale signs left in graphs by fraudsters: (a) synchronized behavior: suspicious nodes have extremely similar behavior patterns because they are often required to perform some task together (such as follow the same user); and (b) rare behavior: their connectivity patterns are very different from the majority. We introduce novel measures to quantify both concepts (“synchronicity” and “normality”) and we propose a parameter-free algorithm that works on the resulting synchronicity-normality plots. Thanks to careful design, CatchSync has the following desirable properties: (a) it is scalable to large datasets, being linear in the graph size; (b) it is parameter free; and (c) it is side-information-oblivious: it can operate using only the topology, without needing labeled data, nor timing information, and the like., while still capable of using side information if available. We applied CatchSync on three large, real datasets, 1-billion-edge Twitter social graph, 3-billion-edge, and 12-billion-edge Tencent Weibo social graphs, and several synthetic ones; CatchSync consistently outperforms existing competitors, both in detection accuracy by 36% on Twitter and 20% on Tencent Weibo, as well as in speed.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {35},
numpages = {27},
keywords = {Anomaly detection, suspicious behavior, graph mining, connectivity pattern}
}

@article{10.1145/2818714,
author = {Shen, Chih-Ya and Yang, De-Nian and Lee, Wang-Chien and Chen, Ming-Syan},
title = {Spatial-Proximity Optimization for Rapid Task Group Deployment},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2818714},
doi = {10.1145/2818714},
abstract = {Spatial proximity is one of the most important factors for the quick deployment of the task groups in various time-sensitive missions. This article proposes a new spatial query, Spatio-Social Team Query (SSTQ), that forms a strong task group by considering (1) the group’s spatial distance (i.e., transportation time), (2) skills of the candidate group members, and (3) social rapport among the candidates. Efficient processing of SSTQ is very challenging, because the aforementioned spatial, skill, and social factors need to be carefully examined. In this article, therefore, we first formulate two subproblems of SSTQ, namely Hop-Constrained Team Problem (HCTP) and Connection-Oriented Team Query (COTQ). HCTP is a decision problem that considers only social and skill dimensions. We prove that HCTP is NP-Complete. Moreover, based on the hardness of HCTP, we prove that SSTQ is NP-Hard and inapproximable within any factor. On the other hand, COTQ is a special case of SSTQ that relaxes the social constraint. We prove that COTQ is NP-Hard and propose an approximation algorithm for COTQ, namely COTprox. Furthermore, based on the observations on COTprox, we devise an approximation algorithm, SSTprox, with a guaranteed error bound for SSTQ. Finally, to efficiently obtain the optimal solution to SSTQ for small instances, we design two efficient algorithms, SpatialFirst and SkillFirst, with different scenarios in mind. These two algorithms incorporate various effective ordering and pruning techniques to reduce the search space for answering SSTQ. Experimental results on real datasets indicate that the proposed algorithms can efficiently answer SSTQ under various parameter settings.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {47},
numpages = {36},
keywords = {Spatial database, query processing, social network}
}

@article{10.1145/2903148,
author = {Chen, Chen and Tong, Hanghang and Prakash, B. Aditya and Eliassi-Rad, Tina and Faloutsos, Michalis and Faloutsos, Christos},
title = {Eigen-Optimization on Large Graphs by Edge Manipulation},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2903148},
doi = {10.1145/2903148},
abstract = {Large graphs are prevalent in many applications and enable a variety of information dissemination processes, e.g., meme, virus, and influence propagation. How can we optimize the underlying graph structure to affect the outcome of such dissemination processes in a desired way (e.g., stop a virus propagation, facilitate the propagation of a piece of good idea, etc)? Existing research suggests that the leading eigenvalue of the underlying graph is the key metric in determining the so-called epidemic threshold for a variety of dissemination models. In this paper, we study the problem of how to optimally place a set of edges (e.g., edge deletion and edge addition) to optimize the leading eigenvalue of the underlying graph, so that we can guide the dissemination process in a desired way. We propose effective, scalable algorithms for edge deletion and edge addition, respectively. In addition, we reveal the intrinsic relationship between edge deletion and node deletion problems. Experimental results validate the effectiveness and efficiency of the proposed algorithms. },
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {49},
numpages = {30},
keywords = {scalability, Edge manipulation, graph mining, immunization}
}

@article{10.1145/2882968,
author = {Tahani, Maryam and Hemmatyar, Ali M. A. and Rabiee, Hamid R. and Ramezani, Maryam},
title = {Inferring Dynamic Diffusion Networks in Online Media},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2882968},
doi = {10.1145/2882968},
abstract = {Online media play an important role in information societies by providing a convenient infrastructure for different processes. Information diffusion that is a fundamental process taking place on social and information networks has been investigated in many studies. Research on information diffusion in these networks faces two main challenges: (1) In most cases, diffusion takes place on an underlying network, which is latent and its structure is unknown. (2) This latent network is not fixed and changes over time. In this article, we investigate the diffusion network extraction (DNE) problem when the underlying network is dynamic and latent. We model the diffusion behavior (existence probability) of each edge as a stochastic process and utilize the Hidden Markov Model (HMM) to discover the most probable diffusion links according to the current observation of the diffusion process, which is the infection time of nodes and the past diffusion behavior of links. We evaluate the performance of our Dynamic Diffusion Network Extraction (DDNE) method, on both synthetic and real datasets. Experimental results show that the performance of the proposed method is independent of the cascade transmission model and outperforms the state of art method in terms of F-measure.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {44},
numpages = {22},
keywords = {Online media, information diffusion, hidden markov model, dynamic network}
}

@article{10.1145/2912122,
author = {Tong, Hanghang and Wang, Fei and Choudhury, Munmun De and Obradovic, Zoran},
title = {Guest Editorial: Special Issue on Connected Health at Big Data Era (BigChat): A TKDD Special Issue},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2912122},
doi = {10.1145/2912122},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {37},
numpages = {4}
}

@article{10.1145/2898359,
author = {Koh, Yun Sing and Ravana, Sri Devi},
title = {Unsupervised Rare Pattern Mining: A Survey},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2898359},
doi = {10.1145/2898359},
abstract = {Association rule mining was first introduced to examine patterns among frequent items. The original motivation for seeking these rules arose from need to examine customer purchasing behaviour in supermarket transaction data. It seeks to identify combinations of items or itemsets, whose presence in a transaction affects the likelihood of the presence of another specific item or itemsets. In recent years, there has been an increasing demand for rare association rule mining. Detecting rare patterns in data is a vital task, with numerous high-impact applications including medical, finance, and security. This survey aims to provide a general, comprehensive, and structured overview of the state-of-the-art methods for rare pattern mining. We investigate the problems in finding rare rules using traditional association rule mining. As rare association rule mining has not been well explored, there is still specific groundwork that needs to be established. We will discuss some of the major issues in rare association rule mining and also look at current algorithms. As a contribution, we give a general framework for categorizing algorithms: Apriori and Tree based. We highlight the differences between these methods. Finally, we present several real-world application using rare pattern mining in diverse domains. We conclude our survey with a discussion on open and practical challenges in the field.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {45},
numpages = {29},
keywords = {Association rule mining, rare rules, infrequent patterns}
}

@article{10.1145/2903147,
author = {Cheng, Wei and Guo, Zhishan and Zhang, Xiang and Wang, Wei},
title = {CGC: A Flexible and Robust Approach to Integrating Co-Regularized Multi-Domain Graph for Clustering},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2903147},
doi = {10.1145/2903147},
abstract = {Multi-view graph clustering aims to enhance clustering performance by integrating heterogeneous information collected in different domains. Each domain provides a different view of the data instances. Leveraging cross-domain information has been demonstrated an effective way to achieve better clustering results. Despite the previous success, existing multi-view graph clustering methods usually assume that different views are available for the same set of instances. Thus, instances in different domains can be treated as having strict one-to-one relationship. In many real-life applications, however, data instances in one domain may correspond to multiple instances in another domain. Moreover, relationships between instances in different domains may be associated with weights based on prior (partial) knowledge. In this article, we propose a flexible and robust framework, Co-regularized Graph Clustering (CGC), based on non-negative matrix factorization (NMF), to tackle these challenges. CGC has several advantages over the existing methods. First, it supports many-to-many cross-domain instance relationship. Second, it incorporates weight on cross-domain relationship. Third, it allows partial cross-domain mapping so that graphs in different domains may have different sizes. Finally, it provides users with the extent to which the cross-domain instance relationship violates the in-domain clustering structure, and thus enables users to re-evaluate the consistency of the relationship. We develop an efficient optimization method that guarantees to find the global optimal solution with a given confidence requirement. The proposed method can automatically identify noisy domains and assign smaller weights to them. This helps to obtain optimal graph partition for the focused domain. Extensive experimental results on UCI benchmark datasets, newsgroup datasets, and biological interaction networks demonstrate the effectiveness of our approach.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {46},
numpages = {27},
keywords = {co-regularization, Graph clustering, nonnegative matrix factorization}
}

@article{10.1145/2821513,
author = {Yu, Zhiwen and Wang, Zhitao and Chen, Liming and Guo, Bin and Li, Wenjie},
title = {Featuring, Detecting, and Visualizing Human Sentiment in Chinese Micro-Blog},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2821513},
doi = {10.1145/2821513},
abstract = {Micro-blog has been increasingly used for the public to express their opinions, and for organizations to detect public sentiment about social events or public policies. In this article, we examine and identify the key problems of this field, focusing particularly on the characteristics of innovative words, multi-media elements, and hierarchical structure of Chinese “Weibo.” Based on the analysis, we propose a novel approach and develop associated theoretical and technological methods to address these problems. These include a new sentiment word mining method based on three wording metrics and point-wise information, a rule set model for analyzing sentiment features of different linguistic components, and the corresponding methodology for calculating sentiment on multi-granularity considering emoticon elements as auxiliary affective factors. We evaluate our new word discovery and sentiment detection methods on a real-life Chinese micro-blog dataset. Initial results show that our new diction can improve sentiment detection, and they demonstrate that our multi-level rule set method is more effective, with the average accuracy being 10.2% and 1.5% higher than two existing methods for Chinese micro-blog sentiment analysis. In addition, we exploit visualization techniques to study the relationships between online sentiment and real life. The visualization of detected sentiment can help depict temporal patterns and spatial discrepancy.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {48},
numpages = {23},
keywords = {rule set--based model, Sentiment detection, sentiment lexicon expansion, visualization}
}

@article{10.1145/2875427,
author = {Zhu, Yada and He, Jingrui},
title = {Co-Clustering Structural Temporal Data with Applications to Semiconductor Manufacturing},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2875427},
doi = {10.1145/2875427},
abstract = {Recent years have witnessed data explosion in semiconductor manufacturing due to advances in instrumentation and storage techniques. The large amount of data associated with process variables monitored over time form a rich reservoir of information, which can be used for a variety of purposes, such as anomaly detection, quality control, and fault diagnostics. In particular, following the same recipe for a certain Integrated Circuit device, multiple tools and chambers can be deployed for the production of this device, during which multiple time series can be collected, such as temperature, impedance, gas flow, electric bias, etc. These time series naturally fit into a two-dimensional array (matrix), i.e., each element in this array corresponds to a time series for one process variable from one chamber. To leverage the rich structural information in such temporal data, in this article, we propose a novel framework named C-Struts to simultaneously cluster on the two dimensions of this array. In this framework, we interpret the structural information as a set of constraints on the cluster membership, introduce an auxiliary probability distribution accordingly, and design an iterative algorithm to assign each time series to a certain cluster on each dimension. Furthermore, we establish the equivalence between C-Struts and a generic optimization problem, which is able to accommodate various distance functions. Extensive experiments on synthetic, benchmark, as well as manufacturing datasets demonstrate the effectiveness of the proposed method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {43},
numpages = {18},
keywords = {temporal, semiconductor, structural, Co-clustering}
}

@article{10.1145/2768830,
author = {Cui, Licong and Tao, Shiqiang and Zhang, Guo-Qiang},
title = {Biomedical Ontology Quality Assurance Using a Big Data Approach},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2768830},
doi = {10.1145/2768830},
abstract = {This article presents recent progresses made in using scalable cloud computing environment, Hadoop and MapReduce, to perform ontology quality assurance (OQA), and points to areas of future opportunity. The standard sequential approach used for implementing OQA methods can take weeks if not months for exhaustive analyses for large biomedical ontological systems. With OQA methods newly implemented using massively parallel algorithms in the MapReduce framework, several orders of magnitude in speed-up can be achieved (e.g., from three months to three hours). Such dramatically reduced time makes it feasible not only to perform exhaustive structural analysis of large ontological hierarchies, but also to systematically track structural changes between versions for evolutional analysis. As an exemplar, progress is reported in using MapReduce to perform evolutional analysis and visualization on the Systemized Nomenclature of Medicine—Clinical Terms (SNOMED CT), a prominent clinical terminology system. Future opportunities in three areas are described: one is to extend the scope of MapReduce-based approach to existing OQA methods, especially for automated exhaustive structural analysis. The second is to apply our proposed MapReduce Pipeline for Lattice-based Evaluation (MaPLE) approach, demonstrated as an exemplar method for SNOMED CT, to other biomedical ontologies. The third area is to develop interfaces for reviewing results obtained by OQA methods and for visualizing ontological alignment and evolution, which can also take advantage of cloud computing technology to systematically pre-compute computationally intensive jobs in order to increase performance during user interactions with the visualization interface. Advances in these directions are expected to better support the ontological engineering lifecycle.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {41},
numpages = {28},
keywords = {lattice, SNOMED CT, terminology quality assurance, Hadoop}
}

@article{10.1145/2890508,
author = {Rayana, Shebuti and Akoglu, Leman},
title = {Less is More: Building Selective Anomaly Ensembles},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2890508},
doi = {10.1145/2890508},
abstract = {Ensemble learning for anomaly detection has been barely studied, due to difficulty in acquiring ground truth and the lack of inherent objective functions. In contrast, ensemble approaches for classification and clustering have been studied and effectively used for long. Our work taps into this gap and builds a new ensemble approach for anomaly detection, with application to event detection in temporal graphs as well as outlier detection in no-graph settings. It handles and combines multiple heterogeneous detectors to yield improved and robust performance. Importantly, trusting results from all the constituent detectors may deteriorate the overall performance of the ensemble, as some detectors could provide inaccurate results depending on the type of data in hand and the underlying assumptions of a detector. This suggests that combining the detectors selectively is key to building effective anomaly ensembles—hence “less is more”.In this paper we propose a novel ensemble approach called SELECT for anomaly detection, which automatically and systematically selects the results from constituent detectors to combine in a fully unsupervised fashion. We apply our method to event detection in temporal graphs and outlier detection in multi-dimensional point data (no-graph), where SELECT successfully utilizes five base detectors and seven consensus methods under a unified ensemble framework. We provide extensive quantitative evaluation of our approach for event detection on five real-world datasets (four with ground truth events), including Enron email communications, RealityMining SMS and phone call records, New York Times news corpus, and World Cup 2014 Twitter news feed. We also provide results for outlier detection on seven real-world multi-dimensional point datasets from UCI Machine Learning Repository. Thanks to its selection mechanism, SELECT yields superior performance compared to the individual detectors alone, the full ensemble (naively combining all results), an existing diversity-based ensemble, and an existing weighted ensemble approach.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {42},
numpages = {33},
keywords = {anomaly mining, rank aggregation, Ensemble methods, anomaly ensembles, event detection, unsupervised learning, dynamic graphs}
}

@article{10.1145/2785970,
author = {WU, Yubao and Zhu, Xiaofeng and Li, Li and Fan, Wei and Jin, Ruoming and Zhang, Xiang},
title = {Mining Dual Networks: Models, Algorithms, and Applications},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2785970},
doi = {10.1145/2785970},
abstract = {Finding the densest subgraph in a single graph is a fundamental problem that has been extensively studied. In many emerging applications, there exist dual networks. For example, in genetics, it is important to use protein interactions to interpret genetic interactions. In this application, one network represents physical interactions among nodes, for example, protein--protein interactions, and another network represents conceptual interactions, for example, genetic interactions. Edges in the conceptual network are usually derived based on certain correlation measure or statistical test measuring the strength of the interaction. Two nodes with strong conceptual interaction may not have direct physical interaction.In this article, we propose the novel dual-network model and investigate the problem of finding the densest connected subgraph (DCS), which has the largest density in the conceptual network and is also connected in the physical network. Density in the conceptual network represents the average strength of the measured interacting signals among the set of nodes. Connectivity in the physical network shows how they interact physically. Such pattern cannot be identified using the existing algorithms for a single network. We show that even though finding the densest subgraph in a single network is polynomial time solvable, the DCS problem is NP-hard. We develop a two-step approach to solve the DCS problem. In the first step, we effectively prune the dual networks, while guarantee that the optimal solution is contained in the remaining networks. For the second step, we develop two efficient greedy methods based on different search strategies to find the DCS. Different variations of the DCS problem are also studied. We perform extensive experiments on a variety of real and synthetic dual networks to evaluate the effectiveness and efficiency of the developed methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {40},
numpages = {37},
keywords = {Dual networks, densest connected subgraphs (DCSs)}
}

@article{10.1145/2768831,
author = {Yang, Pei and Yang, Hongxia and Fu, Haoda and Zhou, Dawei and Ye, Jieping and Lappas, Theodoros and He, Jingrui},
title = {Jointly Modeling Label and Feature Heterogeneity in Medical Informatics},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2768831},
doi = {10.1145/2768831},
abstract = {Multiple types of heterogeneity including label heterogeneity and feature heterogeneity often co-exist in many real-world data mining applications, such as diabetes treatment classification, gene functionality prediction, and brain image analysis. To effectively leverage such heterogeneity, in this article, we propose a novel graph-based model for Learning with both Label and Feature heterogeneity, namely L2F. It models the label correlation by requiring that any two label-specific classifiers behave similarly on the same views if the associated labels are similar, and imposes the view consistency by requiring that view-based classifiers generate similar predictions on the same examples. The objective function for L2F is jointly convex. To solve the optimization problem, we propose an iterative algorithm, which is guaranteed to converge to the global optimum. One appealing feature of L2F is that it is capable of handling data with missing views and labels. Furthermore, we analyze its generalization performance based on Rademacher complexity, which sheds light on the benefits of jointly modeling the label and feature heterogeneity. Experimental results on various biomedical datasets show the effectiveness of the proposed approach.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {39},
numpages = {25},
keywords = {medical informatics, Heterogeneous learning, multi-label learning, multi-view learning}
}

@article{10.1145/2789212,
author = {Xiong, Feiyu and Kam, Moshe and Hrebien, Leonid and Wang, Beilun and Qi, Yanjun},
title = {Kernelized Information-Theoretic Metric Learning for Cancer Diagnosis Using High-Dimensional Molecular Profiling Data},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2789212},
doi = {10.1145/2789212},
abstract = {With the advancement of genome-wide monitoring technologies, molecular expression data have become widely used for diagnosing cancer through tumor or blood samples. When mining molecular signature data, the process of comparing samples through an adaptive distance function is fundamental but difficult, as such datasets are normally heterogeneous and high dimensional. In this article, we present kernelized information-theoretic metric learning (KITML) algorithms that optimize a distance function to tackle the cancer diagnosis problem and scale to high dimensionality. By learning a nonlinear transformation in the input space implicitly through kernelization, KITML permits efficient optimization, low storage, and improved learning of distance metric. We propose two novel applications of KITML for diagnosing cancer using high-dimensional molecular profiling data: (1) for sample-level cancer diagnosis, the learned metric is used to improve the performance of k-nearest neighbor classification; and (2) for estimating the severity level or stage of a group of samples, we propose a novel set-based ranking approach to extend KITML. For the sample-level cancer classification task, we have evaluated on 14 cancer gene microarray datasets and compared with eight other state-of-the-art approaches. The results show that our approach achieves the best overall performance for the task of molecular-expression-driven cancer sample diagnosis. For the group-level cancer stage estimation, we test the proposed set-KITML approach using three multi-stage cancer microarray datasets, and correctly estimated the stages of sample groups for all three studies.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {38},
numpages = {23},
keywords = {high-dimensional data, cancer diagnosis, Metric learning}
}

@article{10.1145/2824443,
author = {Koutra, Danai and Shah, Neil and Vogelstein, Joshua T. and Gallagher, Brian and Faloutsos, Christos},
title = {D<span class="smallcaps SmallerCapital">elta</span>C<span class="smallcaps SmallerCapital">on</span>: Principled Massive-Graph Similarity Function with Attribution},
year = {2016},
issue_date = {February 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2824443},
doi = {10.1145/2824443},
abstract = {How much has a network changed since yesterday? How different is the wiring of Bob’s brain (a left-handed male) and Alice’s brain (a right-handed female), and how is it different? Graph similarity with given node correspondence, i.e., the detection of changes in the connectivity of graphs, arises in numerous settings. In this work, we formally state the axioms and desired properties of the graph similarity functions, and evaluate when state-of-the-art methods fail to detect crucial connectivity changes in graphs. We propose DeltaCon, a principled, intuitive, and scalable algorithm that assesses the similarity between two graphs on the same nodes (e.g., employees of a company, customers of a mobile carrier). In conjunction, we propose DeltaCon-Attr, a related approach that enables attribution of change or dissimilarity to responsible nodes and edges. Experiments on various synthetic and real graphs showcase the advantages of our method over existing similarity measures. Finally, we employ DeltaCon and DeltaCon-Attr on real applications: (a) we classify people to groups of high and low creativity based on their brain connectivity graphs, (b) do temporal anomaly detection in the who-emails-whom Enron graph and find the top culprits for the changes in the temporal corporate email graph, and (c) recover pairs of test-retest large brain scans ( ∼17M edges, up to 90M edges) for 21 subjects.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {28},
numpages = {43},
keywords = {network monitoring, anomaly detection, edge attribution, graph comparison, node attribution, Graph similarity, culprit nodes and edges, graph classification}
}

@article{10.1145/2845086,
author = {Lu, Faming and Zeng, Qingtian and Duan, Hua},
title = {Synchronization-Core-Based Discovery of Processes with Decomposable Cyclic Dependencies},
year = {2016},
issue_date = {February 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2845086},
doi = {10.1145/2845086},
abstract = {Traditional process discovery techniques mine process models based upon event traces giving little consideration to workflow relevant data recorded in event logs. The neglect of such information usually leads to incorrect discovered models, especially when activities have decomposable cyclic dependencies. To address this problem, the recorded workflow relevant data and decision tree learning technique are utilized to classify cases into case clusters. Each case cluster contains causality and concurrency activity dependencies only. Then, a set of activity ordering relations are derived based on case clusters. And a synchronization-core-based process model is discovered from the ordering relations and composite cases. Finally, the discovered model is transformed to a BPMN model. The proposed approach is validated with a medical treatment process and an open event log. Meanwhile, a prototype system is presented.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {31},
numpages = {29},
keywords = {process discovery, decision tree, Process mining, BPMN}
}

@article{10.1145/2742549,
author = {Guo, Zhen and Zhang, Zhongfei (Mark) and Xing, Eric P. and Faloutsos, Christos},
title = {Multimodal Data Mining in a Multimedia Database Based on Structured Max Margin Learning},
year = {2016},
issue_date = {February 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2742549},
doi = {10.1145/2742549},
abstract = {Mining knowledge from a multimedia database has received increasing attentions recently since huge repositories are made available by the development of the Internet. In this article, we exploit the relations among different modalities in a multimedia database and present a framework for general multimodal data mining problem where image annotation and image retrieval are considered as the special cases. Specifically, the multimodal data mining problem can be formulated as a structured prediction problem where we learn the mapping from an input to the structured and interdependent output variables. In addition, in order to reduce the demanding computation, we propose a new max margin structure learning approach called Enhanced Max Margin Learning (EMML) framework, which is much more efficient with a much faster convergence rate than the existing max margin learning methods, as verified through empirical evaluations. Furthermore, we apply EMML framework to develop an effective and efficient solution to the multimodal data mining problem that is highly scalable in the sense that the query response time is independent of the database scale. The EMML framework allows an efficient multimodal data mining query in a very large scale multimedia database, and excels many existing multimodal data mining methods in the literature that do not scale up at all. The performance comparison with a state-of-the-art multimodal data mining method is reported for the real-world image databases.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {23},
numpages = {30},
keywords = {Multimodal data mining, max margin, image retrieval, image annotation}
}

@article{10.1145/2822897,
author = {Myers, Risa B. and Frenzel MD, John C. and Ruiz Md, Joseph R. and Jermaine, Christopher M.},
title = {Do Anesthesiologists Know What They Are Doing? Mining a Surgical Time-Series Database to Correlate Expert Assessment with Outcomes},
year = {2016},
issue_date = {February 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2822897},
doi = {10.1145/2822897},
abstract = {Anesthesiologists are taught to carefully manage patient vital signs during surgery. Unfortunately, there is little empirical evidence that vital sign management, as currently practiced, is correlated with patient outcomes. We seek to validate or repudiate current clinical practice and determine whether or not clinician evaluation of surgical vital signs correlate with outcomes. Using a database of over 90,000 cases, we attempt to determine whether those cases that anesthesiologists would subjectively decide are “low quality” are more likely to result in negative outcomes. The problem reduces to one of multi-dimensional time-series classification. Our approach is to have a set of expert anesthesiologists independently label a small number of training cases, from which we build classifiers and label all 90,000 cases. We then use the labeling to search for correlation with outcomes and compare the prevalence of important 30-day outcomes between providers.To mimic the providers’ quality labels, we consider several standard classification methods, such as dynamic time warping in conjunction with a kNN classifier, as well as complexity invariant distance, and a regression based upon the feature extraction methods outlined by Mao et al. 2012 (using features such as time-series mean, standard deviation, skew, etc.). We also propose a new feature selection mechanism that learns a hidden Markov model to segment the time series; the fraction of time that each series spends in each state is used to label the series using a regression-based classifier. In the end, we obtain strong, empirical evidence that current best practice is correlated with reduced negative patient outcomes. We also learn that all of the experts were able to significantly separate cases by outcome, with higher prevalence of negative 30-day outcomes in the cases labeled as “low quality” for almost all of the outcomes investigated.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {24},
numpages = {27},
keywords = {ordinal regression, hidden Markov model (HMM), Vital signs}
}

@article{10.1145/2842629,
author = {Zhao, Wayne Xin and Wang, Jinpeng and He, Yulan and Wen, Ji-Rong and Chang, Edward Y. and Li, Xiaoming},
title = {Mining Product Adopter Information from Online Reviews for Improving Product Recommendation},
year = {2016},
issue_date = {February 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2842629},
doi = {10.1145/2842629},
abstract = {We present in this article an automated framework that extracts product adopter information from online reviews and incorporates the extracted information into feature-based matrix factorization for more effective product recommendation. In specific, we propose a bootstrapping approach for the extraction of product adopters from review text and categorize them into a number of different demographic categories. The aggregated demographic information of many product adopters can be used to characterize both products and users in the form of distributions over different demographic categories. We further propose a graph-based method to iteratively update user- and product-related distributions more reliably in a heterogeneous user--product graph and incorporate them as features into the matrix factorization approach for product recommendation. Our experimental results on a large dataset crawled from JingDong, the largest B2C e-commerce website in China, show that our proposed framework outperforms a number of competitive baselines for product recommendation.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {29},
numpages = {23},
keywords = {Online review, product adopter, product recommendation, matrix factorisation}
}

@article{10.1145/2775108,
author = {Prat-P\'{e}rez, Arnau and Dominguez-Sal, David and Brunat, Josep-M. and Larriba-Pey, Josep-Lluis},
title = {Put Three and Three Together: Triangle-Driven Community Detection},
year = {2016},
issue_date = {February 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2775108},
doi = {10.1145/2775108},
abstract = {Community detection has arisen as one of the most relevant topics in the field of graph data mining due to its applications in many fields such as biology, social networks, or network traffic analysis. Although the existing metrics used to quantify the quality of a community work well in general, under some circumstances, they fail at correctly capturing such notion. The main reason is that these metrics consider the internal community edges as a set, but ignore how these actually connect the vertices of the community. We propose the Weighted Community Clustering (WCC), which is a new community metric that takes the triangle instead of the edge as the minimal structural motif indicating the presence of a strong relation in a graph. We theoretically analyse WCC in depth and formally prove, by means of a set of properties, that the maximization of WCC guarantees communities with cohesion and structure. In addition, we propose Scalable Community Detection (SCD), a community detection algorithm based on WCC, which is designed to be fast and scalable on SMP machines, showing experimentally that WCC correctly captures the concept of community in social networks using real datasets. Finally, using ground-truth data, we show that SCD provides better quality than the best disjoint community detection algorithms of the state of the art while performing faster.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {22},
numpages = {42},
keywords = {triangles, Community detection, social networks, scalable algorithm, parallel algorithm}
}

@article{10.1145/2829955,
author = {Duarte, Jo\~{a}o and Gama, Jo\~{a}o and Bifet, Albert},
title = {Adaptive Model Rules From High-Speed Data Streams},
year = {2016},
issue_date = {February 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2829955},
doi = {10.1145/2829955},
abstract = {Decision rules are one of the most expressive and interpretable models for machine learning. In this article, we present Adaptive Model Rules (AMRules), the first stream rule learning algorithm for regression problems. In AMRules, the antecedent of a rule is a conjunction of conditions on the attribute values, and the consequent is a linear combination of the attributes. In order to maintain a regression model compatible with the most recent state of the process generating data, each rule uses a Page-Hinkley test to detect changes in this process and react to changes by pruning the rule set. Online learning might be strongly affected by outliers. AMRules is also equipped with outliers detection mechanisms to avoid model adaption using anomalous examples. In the experimental section, we report the results of AMRules on benchmark regression problems, and compare the performance of our system with other streaming regression algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {30},
numpages = {22},
keywords = {Data streams, rule learning, regression}
}

@article{10.1145/2815625,
author = {Subbian, Karthik and Aggarwal, Charu and Srivastava, Jaideep},
title = {Mining Influencers Using Information Flows in Social Streams},
year = {2016},
issue_date = {February 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2815625},
doi = {10.1145/2815625},
abstract = {The problem of discovering information flow trends in social networks has become increasingly relevant due to the increasing amount of content in online social networks, and its relevance as a tool for research into the content trends analysis in the network. An important part of this analysis is to determine the key patterns of flow in the underlying network. Almost all the work in this area has focused on fixed models of the network structure, and edge-based transmission between nodes. In this article, we propose a fully content-centered model of flow analysis in networks, in which the analysis is based on actual content transmissions in the underlying social stream, rather than a static model of transmission on the edges. First, we introduce the problem of influence analysis in the context of information flow in networks. We then propose a novel algorithm InFlowMine to discover the information flow patterns in the network and demonstrate the effectiveness of the discovered information flows using an influence mining application. This application illustrates the flexibility and effectiveness of our information flow model to find topic- or network-specific influencers, or their combinations. We empirically show that our information flow mining approach is effective and efficient than the existing methods on a number of different measures.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {26},
numpages = {28},
keywords = {influencer analysis, information flows, Network analysis}
}

@article{10.1145/2818378,
author = {Namata, Galileo Mark and London, Ben and Getoor, Lise},
title = {Collective Graph Identification},
year = {2016},
issue_date = {February 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2818378},
doi = {10.1145/2818378},
abstract = {Data describing networks—such as communication networks, transaction networks, disease transmission networks, collaboration networks, etc.—are becoming increasingly available. While observational data can be useful, it often only hints at the actual underlying process that governs interactions and attributes. For example, an email communication network provides insight into its users and their relationships, but is not the same as the “real” underlying social network. In this article, we introduce the problem of graph identification, i.e., discovering the latent graph structure underlying an observed network. We cast the problem as a probabilistic inference task, in which we must infer the nodes, edges, and node labels of a hidden graph, based on evidence. This entails solving several canonical problems in network analysis: entity resolution (determining when two observations correspond to the same entity), link prediction (inferring the existence of links), and node labeling (inferring hidden attributes). While each of these subproblems has been well studied in isolation, here we consider them as a single, collective task. We present a simple, yet novel, approach to address all three subproblems simultaneously. Our approach, which we refer to as C3, consists of a collection of Coupled Collective Classifiers that are applied iteratively to propagate inferred information among the subproblems. We consider variants of C3 using different learning and inference techniques and empirically demonstrate that C3 is superior, both in terms of predictive accuracy and running time, to state-of-the-art probabilistic approaches on four real problems.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {25},
numpages = {36},
keywords = {link prediction, collective classification, Entity resolution, semi-supervised learning}
}

@article{10.1145/2829956,
author = {Angiulli, Fabrizio and Fassetti, Fabio},
title = {Toward Generalizing the Unification with Statistical Outliers: The Gradient Outlier Factor Measure},
year = {2016},
issue_date = {February 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2829956},
doi = {10.1145/2829956},
abstract = {In this work, we introduce a novel definition of outlier, namely the Gradient Outlier Factor (or GOF), with the aim to provide a definition that unifies with the statistical one on some standard distributions but has a different behavior in the presence of mixture distributions. Intuitively, the GOF score measures the probability to stay in the neighborhood of a certain object. It is directly proportional to the density and inversely proportional to the variation of the density. We derive formal properties under which the GOF definition unifies the statistical outlier definition and show that the unification holds for some standard distributions, while the GOF is able to capture tails in the presence of different distributions even if their densities sensibly differ. Moreover, we provide a probabilistic interpretation of the GOF score, by means of the notion of density of the data density. Experimental results confirm that there are scenarios in which the novel definition can be profitably employed. To the best of our knowledge, except for distance-based outlier, no other data mining outlier definition has a so clearly established relationship with statistical outliers.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {27},
numpages = {26},
keywords = {unification between outlier definitions, Outlier detection, statistical outliers}
}

@article{10.1145/2798730,
author = {Rowe, Matthew},
title = {Mining User Development Signals for Online Community Churner Detection},
year = {2016},
issue_date = {February 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2798730},
doi = {10.1145/2798730},
abstract = {Churners are users who stop using a given service after previously signing up. In the domain of telecommunications and video games, churners represent a loss of revenue as a user leaving indicates that they will no longer pay for the service. In the context of online community platforms (e.g., community message boards, social networking sites, question--answering systems, etc.), the churning of a user can represent different kinds of loss: of social capital, of expertise, or of a vibrant individual who is a mediator for interaction and communication. Detecting which users are likely to churn from online communities, therefore, enables community managers to offer incentives to entice those users back; as retention is less expensive than re-signing users up. In this article, we tackle the task of detecting churners on four online community platforms by mining user development signals. These signals explain how users have evolved along different dimensions (i.e., social and lexical) relative to their prior behaviour and the community in which they have interacted. We present a linear model, based upon elastic-net regularisation, that uses extracted features from the signals to detect churners. Our evaluation of this model against several state of the art baselines, including our own prior work, empirically demonstrates the superior performance that this approach achieves for several experimental settings. This article presents a novel approach to churn prediction that takes a different route from existing approaches that are based on measuring static social network properties of users (e.g., centrality, in-degree, etc.).},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {21},
numpages = {28},
keywords = {social dynamics, Churn prediction, lifecycle mining, lexical terms, online communities}
}

@article{10.1145/2791295,
author = {Liu, Yashu and Wang, Jie and Ye, Jieping},
title = {An Efficient Algorithm For Weak Hierarchical Lasso},
year = {2016},
issue_date = {February 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2791295},
doi = {10.1145/2791295},
abstract = {Linear regression is a widely used tool in data mining and machine learning. In many applications, fitting a regression model with only linear effects may not be sufficient for predictive or explanatory purposes. One strategy that has recently received increasing attention in statistics is to include feature interactions to capture the nonlinearity in the regression model. Such model has been applied successfully in many biomedical applications. One major challenge in the use of such model is that the data dimensionality is significantly higher than the original data, resulting in the small sample size large dimension problem. Recently, weak hierarchical Lasso, a sparse interaction regression model, is proposed that produces a sparse and hierarchical structured estimator by exploiting the Lasso penalty and a set of hierarchical constraints. However, the hierarchical constraints make it a non-convex problem and the existing method finds the solution to its convex relaxation, which needs additional conditions to guarantee the hierarchical structure. In this article, we propose to directly solve the non-convex weak hierarchical Lasso by making use of the General Iterative Shrinkage and Thresholding (GIST) optimization framework, which has been shown to be efficient for solving non-convex sparse formulations. The key step in GIST is to compute a sequence of proximal operators. One of our key technical contributions is to show that the proximal operator associated with the non-convex weak hierarchical Lasso admits a closed-form solution. However, a naive approach for solving each subproblem of the proximal operator leads to a quadratic time complexity, which is not desirable for large-size problems. We have conducted extensive experiments on both synthetic and real datasets. Results show that our proposed algorithm is much more efficient and effective than its convex relaxation. To this end, we further develop an efficient algorithm for computing the subproblems with a linearithmic time complexity. In addition, we extend the technique to perform the optimization-based hierarchical testing of pairwise interactions for binary classification problems, which is essentially the proximal operator associated with weak hierarchical Lasso. Simulation studies show that the non-convex hierarchical testing framework outperforms the convex relaxation when a hierarchical structure exists between main effects and interactions.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {32},
numpages = {24},
keywords = {proximal operator, weak hierarchical Lasso, Sparse learning, non-convex}
}

@article{10.1145/2811268,
author = {Yu, Rose and He, Xinran and Liu, Yan},
title = {GLAD: Group Anomaly Detection in Social Media Analysis},
year = {2015},
issue_date = {October 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2811268},
doi = {10.1145/2811268},
abstract = {Traditional anomaly detection on social media mostly focuses on individual point anomalies while anomalous phenomena usually occur in groups. Therefore, it is valuable to study the collective behavior of individuals and detect group anomalies. Existing group anomaly detection approaches rely on the assumption that the groups are known, which can hardly be true in real world social media applications. In this article, we take a generative approach by proposing a hierarchical Bayes model: Group Latent Anomaly Detection (GLAD) model. GLAD takes both pairwise and point-wise data as input, automatically infers the groups and detects group anomalies simultaneously. To account for the dynamic properties of the social media data, we further generalize GLAD to its dynamic extension d-GLAD. We conduct extensive experiments to evaluate our models on both synthetic and real world datasets. The empirical results demonstrate that our approach is effective and robust in discovering latent groups and detecting group anomalies.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {18},
numpages = {22},
keywords = {topic modeling, Group anomaly, community detection}
}

@article{10.1145/2757282,
author = {Li, Lei and Peng, Wei and Kataria, Saurabh and Sun, Tong and Li, Tao},
title = {Recommending Users and Communities in Social Media},
year = {2015},
issue_date = {October 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2757282},
doi = {10.1145/2757282},
abstract = {Social media has become increasingly prevalent in the last few years, not only enabling people to connect with each other by social links, but also providing platforms for people to share information and interact over diverse topics. Rich user-generated information, for example, users’ relationships and daily posts, are often available in most social media service websites. Given such information, a challenging problem is to provide reasonable user and community recommendation for a target user, and consequently, help the target user engage in the daily discussions and activities with his/her friends or like-minded people. In this article, we propose a unified framework of recommending users and communities that utilizes the information in social media. Given a user’s profile or a set of keywords as input, our framework is capable of recommending influential users and topic-cohesive interactive communities that are most relevant to the given user or keywords. With the proposed framework, users can find other individuals or communities sharing similar interests, and then have more interaction with these users or within the communities. We present a generative topic model to discover user-oriented and community-oriented topics simultaneously, which enables us to capture the exact topical interests of users, as well as the focuses of communities. Extensive experimental evaluation and case studies on a dataset collected from Twitter demonstrate the effectiveness of our proposed framework compared with other probabilistic-topic-model-based recommendation methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {17},
numpages = {27},
keywords = {User recommendation, community recommendation, social media, user-community-topic model}
}

@article{10.1145/2803176,
author = {Zhang, Yao and Prakash, B. Aditya},
title = {Data-Aware Vaccine Allocation Over Large Networks},
year = {2015},
issue_date = {October 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2803176},
doi = {10.1145/2803176},
abstract = {Given a graph, like a social/computer network or the blogosphere, in which an infection (or meme or virus) has been spreading for some time, how to select the k best nodes for immunization/quarantining immediately? Most previous works for controlling propagation (say via immunization) have concentrated on developing strategies for vaccination preemptively before the start of the epidemic. While very useful to provide insights in to which baseline policies can best control an infection, they may not be ideal to make real-time decisions as the infection is progressing.In this paper, we study how to immunize healthy nodes, in the presence of already infected nodes. Efficient algorithms for such a problem can help public-health experts make more informed choices, tailoring their decisions to the actual distribution of the epidemic on the ground. First we formulate the Data-Aware Vaccination problem, and prove it is NP-hard and also that it is hard to approximate. Secondly, we propose three effective polynomial-time heuristics DAVA, DAVA-prune and DAVA-fast, of varying degrees of efficiency and performance. Finally, we also demonstrate the scalability and effectiveness of our algorithms through extensive experiments on multiple real networks including large epidemiology datasets (containing millions of interactions). Our algorithms show substantial gains of up to ten times more healthy nodes at the end against many other intuitive and nontrivial competitors.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {20},
numpages = {32},
keywords = {social networks, Graph mining, diffusion, immunization}
}

@article{10.1145/2757281,
author = {Papagelis, Manos},
title = {Refining Social Graph Connectivity via Shortcut Edge Addition},
year = {2015},
issue_date = {October 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2757281},
doi = {10.1145/2757281},
abstract = {Small changes on the structure of a graph can have a dramatic effect on its connectivity. While in the traditional graph theory, the focus is on well-defined properties of graph connectivity, such as biconnectivity, in the context of a social graph, connectivity is typically manifested by its ability to carry on social processes. In this paper, we consider the problem of adding a small set of nonexisting edges (shortcuts) in a social graph with the main objective of minimizing its characteristic path length. This property determines the average distance between pairs of vertices and essentially controls how broadly information can propagate through a network. We formally define the problem of interest, characterize its hardness and propose a novel method, path screening, which quickly identifies important shortcuts to guide the augmentation of the graph. We devise a sampling-based variant of our method that can scale up the computation in larger graphs. The claims of our methods are formally validated. Through experiments on real and synthetic data, we demonstrate that our methods are a multitude of times faster than standard approaches, their accuracy outperforms sensible baselines and they can ease the spread of information in a network, for a varying range of conditions.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {12},
numpages = {35},
keywords = {network engineering, propagation, mixing time, Graph augmentation, conductance, shortcuts, social networks}
}

@article{10.1145/2778990,
author = {Chakrabarti, Aniket and Satuluri, Venu and Srivathsan, Atreya and Parthasarathy, Srinivasan},
title = {A Bayesian Perspective on Locality Sensitive Hashing with Extensions for Kernel Methods},
year = {2015},
issue_date = {October 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2778990},
doi = {10.1145/2778990},
abstract = {Given a collection of objects and an associated similarity measure, the all-pairs similarity search problem asks us to find all pairs of objects with similarity greater than a certain user-specified threshold. In order to reduce the number of candidates to search, locality-sensitive hashing (LSH) based indexing methods are very effective. However, most such methods only use LSH for the first phase of similarity search—that is, efficient indexing for candidate generation. In this article, we present BayesLSH, a principled Bayesian algorithm for the subsequent phase of similarity search—performing candidate pruning and similarity estimation using LSH. A simpler variant, BayesLSH-Lite, which calculates similarities exactly, is also presented. Our algorithms are able to quickly prune away a large majority of the false positive candidate pairs, leading to significant speedups over baseline approaches. For BayesLSH, we also provide probabilistic guarantees on the quality of the output, both in terms of accuracy and recall. Finally, the quality of BayesLSH’s output can be easily tuned and does not require any manual setting of the number of hashes to use for similarity estimation, unlike standard approaches. For two state-of-the-art candidate generation algorithms, AllPairs and LSH, BayesLSH enables significant speedups, typically in the range 2 \texttimes{} --20 \texttimes{} for a wide variety of datasets.We also extend the BayesLSH algorithm for kernel methods—in which the similarity between two data objects is defined by a kernel function. Since the embedding of data points in the transformed kernel space is unknown, algorithms such as AllPairs which rely on building inverted index structure for fast similarity search do not work with kernel functions. Exhaustive search across all possible pairs is also not an option since the dataset can be huge and computing the kernel values for each pair can be prohibitive. We propose K-BayesLSH an all-pairs similarity search problem for kernel functions. K-BayesLSH leverages a recently proposed idea—kernelized locality sensitive hashing (KLSH)—for hash bit computation and candidate generation, and uses the aforementioned BayesLSH idea for candidate pruning and similarity estimation. We ran a broad spectrum of experiments on a variety of datasets drawn from different domains and with distinct kernels and find a speedup of 2 \texttimes{} --7 \texttimes{} over vanilla KLSH.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {19},
numpages = {32},
keywords = {all-pairs similarity search, kernel similarity measure, Locality-sensitive hashing, bayesian inference}
}

@article{10.1145/2736698,
author = {Jia, Adele Lu and Shen, Siqi and Bovenkamp, Ruud Van De and Iosup, Alexandru and Kuipers, Fernando and Epema, Dick H. J.},
title = {Socializing by Gaming: Revealing Social Relationships in Multiplayer Online Games},
year = {2015},
issue_date = {October 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2736698},
doi = {10.1145/2736698},
abstract = {Multiplayer Online Games (MOGs) like Defense of the Ancients and StarCraft II have attracted hundreds of millions of users who communicate, interact, and socialize with each other through gaming. In MOGs, rich social relationships emerge and can be used to improve gaming services such as match recommendation and game population retention, which are important for the user experience and the commercial value of the companies who run these MOGs. In this work, we focus on understanding social relationships in MOGs. We propose a graph model that is able to capture social relationships of a variety of types and strengths. We apply our model to real-world data collected from three MOGs that contain in total over ten years of behavioral history for millions of players and matches. We compare social relationships in MOGs across different game genres and with regular online social networks like Facebook. Taking match recommendation as an example application of our model, we propose SAMRA, a Socially Aware Match Recommendation Algorithm that takes social relationships into account. We show that our model not only improves the precision of traditional link prediction approaches, but also potentially helps players enjoy games to a higher extent.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {11},
numpages = {29},
keywords = {graph model, user interaction, Multiplayer Online Games (MOGs), social relationship}
}

@article{10.1145/2753765,
author = {Zhang, Lei and Luo, Ping and Tang, Linpeng and Chen, Enhong and Liu, Qi and Wang, Min and Xiong, Hui},
title = {Occupancy-Based Frequent Pattern Mining<sup>*</sup>},
year = {2015},
issue_date = {October 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2753765},
doi = {10.1145/2753765},
abstract = {Frequent pattern mining is an important data mining problem with many broad applications. Most studies in this field use support (frequency) to measure the popularity of a pattern, namely the fraction of transactions or sequences that include the pattern in a data set. In this study, we introduce a new interesting measure, namely occupancy, to measure the completeness of a pattern in its supporting transactions or sequences. This is motivated by some real-world pattern recommendation applications in which an interesting pattern should not only be frequent, but also occupies a large portion of its supporting transactions or sequences. With the definition of occupancy we call a pattern dominant if its occupancy value is above a user-specified threshold. Then, our task is to identify the qualified patterns which are both dominant and frequent. Also, we formulate the problem of mining top-k qualified patterns, that is, finding k qualified patterns with maximum values on a user-defined function of support and occupancy, for example, weighted sum of support and occupancy. The challenge to these tasks is that the value of occupancy does not change monotonically when more items are appended to a given pattern. Therefore, we propose a general algorithm called DOFRA (DOminant and FRequent pattern mining Algorithm) for mining these qualified patterns, which explores the upper bound properties on occupancy to drastically reduce the search process. Finally, we show the effectiveness of DOFRA in two real-world applications and also demonstrate the efficiency of DOFRA on several real and large synthetic datasets.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {14},
numpages = {33},
keywords = {dominant pattern, bound estimation, Occupancy}
}

@article{10.1145/2776894,
author = {Chen, Hung-Hsuan and Giles, C. Lee},
title = {ASCOS++: An Asymmetric Similarity Measure for Weighted Networks to Address the Problem of SimRank},
year = {2015},
issue_date = {October 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2776894},
doi = {10.1145/2776894},
abstract = {In this article, we explore the relationships among digital objects in terms of their similarity based on vertex similarity measures. We argue that SimRank—a famous similarity measure—and its families, such as P-Rank and SimRank++, fail to capture similar node pairs in certain conditions, especially when two nodes can only reach each other through paths of odd lengths. We present new similarity measures ASCOS and ASCOS++ to address the problem. ASCOS outputs a more complete similarity score than SimRank and SimRank’s families. ASCOS++ enriches ASCOS to include edge weight into the measure, giving all edges and network weights an opportunity to make their contribution. We show that both ASCOS++ and ASCOS can be reformulated and applied on a distributed environment for parallel contribution. Experimental results show that ASCOS++ reports a better score than SimRank and several famous similarity measures. Finally, we re-examine previous use cases of SimRank, and explain appropriate and inappropriate use cases. We suggest future SimRank users following the rules proposed here before na\"{\i}vely applying it. We also discuss the relationship between ASCOS++ and PageRank.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {15},
numpages = {26},
keywords = {Vertex similarity, link prediction, link analysis, SimRank, coauthor network, ASCOS++}
}

@article{10.1145/2751562,
author = {Hong, Liang and Zou, Lei and Zeng, Cheng and Zhang, Luming and Wang, Jian and Tian, Jilei},
title = {Context-Aware Recommendation Using Role-Based Trust Network},
year = {2015},
issue_date = {October 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2751562},
doi = {10.1145/2751562},
abstract = {Recommender systems have been studied comprehensively in both academic and industrial fields over the past decade. As user interests can be affected by context at any time and any place in mobile scenarios, rich context information becomes more and more important for personalized context-aware recommendations. Although existing context-aware recommender systems can make context-aware recommendations to some extent, they suffer several inherent weaknesses: (1) Users’ context-aware interests are not modeled realistically, which reduces the recommendation quality; (2) Current context-aware recommender systems ignore trust relations among users. Trust relations are actually context-aware and associated with certain aspects (i.e., categories of items) in mobile scenarios. In this article, we define a term role to model common context-aware interests among a group of users. We propose an efficient role mining algorithm to mine roles from a “user-context-behavior” matrix, and a role-based trust model to calculate context-aware trust value between two users. During online recommendation, given a user u in a context c, an efficient weighted set similarity query (WSSQ) algorithm is designed to build u’s role-based trust network in context c. Finally, we make recommendations to u based on u’s role-based trust network by considering both context-aware roles and trust relations. Extensive experiments demonstrate that our recommendation approach outperforms the state-of-the-art methods in both effectiveness and efficiency.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {13},
numpages = {25},
keywords = {context-aware, Recommendation, role, trust network}
}

@article{10.1145/2747880,
author = {Zafarani, Reza and Tang, Lei and Liu, Huan},
title = {User Identification Across Social Media},
year = {2015},
issue_date = {October 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2747880},
doi = {10.1145/2747880},
abstract = {People use various social media sites for different purposes. The information on each site is often partial. When sources of complementary information are integrated, a better profile of a user can be built. This profile can help improve online services such as advertising across sites. To integrate these sources of information, it is necessary to identify individuals across social media sites. This paper aims to address the cross-media user identification problem. We provide evidence on the existence of a mapping among identities of individuals across social media sites, study the feasibility of finding this mapping, and illustrate and develop means for finding this mapping. Our studies show that effective approaches that exploit information redundancies due to users’ unique behavioral patterns can be utilized to find such a mapping. This study paves the way for analysis and mining across social networking sites, and facilitates the creation of novel online services across sites. In particular, recommending friends and advertising across networks, analyzing information diffusion across sites, and studying specific user behavior such as user migration across sites in social media are one of the many areas that can benefit from the results of this study.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {16},
numpages = {30},
keywords = {cross-media analysis, behavioral modeling, Social network analysis, user identification}
}

@article{10.1145/2710021,
author = {Wang, Hua and Nie, Feiping and Huang, Heng},
title = {Large-Scale Cross-Language Web Page Classification via Dual Knowledge Transfer Using Fast Nonnegative Matrix Trifactorization},
year = {2015},
issue_date = {July 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2710021},
doi = {10.1145/2710021},
abstract = {With the rapid growth of modern technologies, Internet has reached almost every corner of the world. As a result, it becomes more and more important to manage and mine information contained in Web pages in different languages. Traditional supervised learning methods usually require a large amount of training data to obtain accurate and robust classification models. However, labeled Web pages did not increase as fast as the growth of Internet. The lack of sufficient training Web pages in many languages, especially for those in uncommonly used languages, makes it a challenge for traditional classification algorithms to achieve satisfactory performance. To address this, we observe that Web pages for a same topic from different languages usually share some common semantic patterns, though in different representation forms. In addition, we also observe that the associations between word clusters and Web page classes are another type of reliable carriers to transfer knowledge across languages. With these recognitions, in this article we propose a novel joint nonnegative matrix trifactorization (NMTF) based Dual Knowledge Transfer (DKT) approach for cross-language Web page classification. Our approach transfers knowledge from the auxiliary language, in which abundant labeled Web pages are available, to the target languages, in which we want to classify Web pages, through two different paths: word cluster approximation and the associations between word clusters and Web page classes. With the reinforcement between these two different knowledge transfer paths, our approach can achieve better classification accuracy. In order to deal with the large-scale real world data, we further develop the proposed DKT approach by constraining the factor matrices of NMTF to be cluster indicator matrices. Due to the nature of cluster indicator matrices, we can decouple the proposed optimization objective and the resulted subproblems are of much smaller sizes involving much less matrix multiplications, which make our new approach much more computationally efficient. We evaluate the proposed approach in extensive experiments using a real world cross-language Web page data set. Promising results have demonstrated the effectiveness of our approach that are consistent with our theoretical analyses.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {1},
numpages = {29},
keywords = {nonnegative matrix trifactorization, Cross-language classification, large-scale data, cluster indicator matrix, knowledge transfer}
}

@article{10.1145/2733381,
author = {Campello, Ricardo J. G. B. and Moulavi, Davoud and Zimek, Arthur and Sander, J\"{o}rg},
title = {Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection},
year = {2015},
issue_date = {July 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2733381},
doi = {10.1145/2733381},
abstract = {An integrated framework for density-based cluster analysis, outlier detection, and data visualization is introduced in this article. The main module consists of an algorithm to compute hierarchical estimates of the level sets of a density, following Hartigan’s classic model of density-contour clusters and trees. Such an algorithm generalizes and improves existing density-based clustering techniques with respect to different aspects. It provides as a result a complete clustering hierarchy composed of all possible density-based clusters following the nonparametric model adopted, for an infinite range of density thresholds. The resulting hierarchy can be easily processed so as to provide multiple ways for data visualization and exploration. It can also be further postprocessed so that: (i) a normalized score of “outlierness” can be assigned to each data object, which unifies both the global and local perspectives of outliers into a single definition; and (ii) a “flat” (i.e., nonhierarchical) clustering solution composed of clusters extracted from local cuts through the cluster tree (possibly corresponding to different density thresholds) can be obtained, either in an unsupervised or in a semisupervised way. In the unsupervised scenario, the algorithm corresponding to this postprocessing module provides a global, optimal solution to the formal problem of maximizing the overall stability of the extracted clusters. If partially labeled objects or instance-level constraints are provided by the user, the algorithm can solve the problem by considering both constraints violations/satisfactions and cluster stability criteria. An asymptotic complexity analysis, both in terms of running time and memory space, is described. Experiments are reported that involve a variety of synthetic and real datasets, including comparisons with state-of-the-art, density-based clustering and (global and local) outlier detection methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {5},
numpages = {51},
keywords = {hierarchical and nonhierarchical clustering, data visualization, outlier detection, Density-based clustering, unsupervised and semisupervised clustering, global/local outliers}
}

@article{10.1145/2717314,
author = {Zhou, Yang and Liu, Ling},
title = {Social Influence Based Clustering and Optimization over Heterogeneous Information Networks},
year = {2015},
issue_date = {July 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2717314},
doi = {10.1145/2717314},
abstract = {Social influence analysis has shown great potential for strategic marketing decision. It is well known that people influence one another based on both their social connections and the social activities that they have engaged in the past. In this article, we develop an innovative and high-performance social influence based graph clustering framework with four unique features. First, we explicitly distinguish social connection based influence (self-influence) and social activity based influence (co-influence). We compute the self-influence similarity between two members based on their social connections within a single collaboration network, and compute the co-influence similarity by taking into account not only the set of activities that people participate but also the semantic association between these activities. Second, we define the concept of influence-based similarity by introducing a unified influence-based similarity matrix that employs an iterative weight update method to integrate self-influence and co-influence similarities. Third, we design a dynamic learning algorithm, called SI-Cluster, for social influence based graph clustering. It iteratively partitions a large social collaboration network into K clusters based on both the social network itself and the multiple associated activity information networks, each representing a category of activities that people have engaged. To make the SI-Cluster algorithm converge fast, we transform sophisticated nonlinear fractional programming problem with respect to multiple weights into a straightforward nonlinear parametric programming problem of single variable. Finally, we develop an optimization technique of diagonalizable-matrix approximation to speed up the computation of self-influence similarity and co-influence similarities. Our SI-Cluster-Opt significantly improves the efficiency of SI-Cluster on large graphs while maintaining high quality of clustering results. Extensive experimental evaluation on three real-world graphs shows that, compared to existing representative graph clustering algorithms, our SI-Cluster-Opt approach not only achieves a very good balance between self-influence and co-influence similarities but also scales extremely well for clustering large graphs in terms of time complexity while meeting the guarantee of high density, low entropy and low Davies--Bouldin Index.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {2},
numpages = {53},
keywords = {heterogeneous information network, Graph clustering, social influence}
}

@article{10.1145/2733380,
author = {Ahmed, Rezwan and Karypis, George},
title = {Algorithms for Mining the Coevolving Relational Motifs in Dynamic Networks},
year = {2015},
issue_date = {July 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2733380},
doi = {10.1145/2733380},
abstract = {Computational methods and tools that can efficiently and effectively analyze the temporal changes in dynamic complex relational networks enable us to gain significant insights regarding the entity relations and their evolution. This article introduces a new class of dynamic graph patterns, referred to as coevolving relational motifs (CRMs), which are designed to identify recurring sets of entities whose relations change in a consistent way over time. CRMs can provide evidence to the existence of, possibly unknown, coordination mechanisms by identifying the relational motifs that evolve in a similar and highly conserved fashion. We developed an algorithm to efficiently analyze the frequent relational changes between the entities of the dynamic networks and capture all frequent coevolutions as CRMs. Our algorithm follows a depth-first exploration of the frequent CRM lattice and incorporates canonical labeling for redundancy elimination. Experimental results based on multiple real world dynamic networks show that the method is able to efficiently identify CRMs. In addition, a qualitative analysis of the results shows that the discovered patterns can be used as features to characterize the dynamic network.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {4},
numpages = {31},
keywords = {evolving pattern mining, Dynamic networks, network evolution}
}

@article{10.1145/2729980,
author = {Papalexakis, Evangelos E. and Faloutsos, Christos and Sidiropoulos, Nicholas D.},
title = {P<span class="smallcaps SmallerCapital">ar</span>C<span class="smallcaps SmallerCapital">ube</span>: Sparse Parallelizable CANDECOMP-PARAFAC Tensor Decomposition},
year = {2015},
issue_date = {July 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2729980},
doi = {10.1145/2729980},
abstract = {How can we efficiently decompose a tensor into sparse factors, when the data do not fit in memory? Tensor decompositions have gained a steadily increasing popularity in data-mining applications; however, the current state-of-art decomposition algorithms operate on main memory and do not scale to truly large datasets. In this work, we propose ParCube, a new and highly parallelizable method for speeding up tensor decompositions that is well suited to produce sparse approximations. Experiments with even moderately large data indicate over 90% sparser outputs and 14 times faster execution, with approximation error close to the current state of the art irrespective of computation and memory requirements. We provide theoretical guarantees for the algorithm’s correctness and we experimentally validate our claims through extensive experiments, including four different real world datasets (Enron, Lbnl, Facebook and Nell), demonstrating its effectiveness for data-mining practitioners. In particular, we are the first to analyze the very large Nell dataset using a sparse tensor decomposition, demonstrating that ParCube enables us to handle effectively and efficiently very large datasets. Finally, we make our highly scalable parallel implementation publicly available, enabling reproducibility of our work.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {3},
numpages = {25},
keywords = {parallel algorithms, sparsity, sampling, Tensors, PARAFAC decomposition, randomized algorithms}
}

@article{10.1145/2747879,
author = {Zhang, Xianchao and Zhang, Xiaotong and Liu, Han},
title = {Smart Multitask Bregman Clustering and Multitask Kernel Clustering},
year = {2015},
issue_date = {July 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2747879},
doi = {10.1145/2747879},
abstract = {Traditional clustering algorithms deal with a single clustering task on a single dataset. However, there are many related tasks in the real world, which motivates multitask clustering. Recently some multitask clustering algorithms have been proposed, and among them multitask Bregman clustering (MBC) is a very applicable method. MBC alternatively updates clusters and learns relationships between clusters of different tasks, and the two phases boost each other. However, the boosting does not always have positive effects on improving the clustering performance, it may also cause negative effects. Another issue of MBC is that it cannot deal with nonlinear separable data. In this article, we show that in MBC, the process of using cluster relationship to boost the cluster updating phase may cause negative effects, that is, cluster centroids may be skewed under some conditions. We propose a smart multitask Bregman clustering (S-MBC) algorithm which can identify the negative effects of the boosting and avoid the negative effects if they occur. We then propose a multitask kernel clustering (MKC) framework for nonlinear separable data by using a similar framework like MBC in the kernel space. We also propose a specific optimization method, which is quite different from that of MBC, to implement the MKC framework. Since MKC can also cause negative effects like MBC, we further extend the framework of MKC to a smart multitask kernel clustering (S-MKC) framework in a similar way that S-MBC is extended from MBC. We conduct experiments on 10 real world multitask clustering datasets to evaluate the performance of S-MBC and S-MKC. The results on clustering accuracy show that: (1) compared with the original MBC algorithm MBC, S-MBC and S-MKC perform much better; (2) compared with the convex discriminative multitask relationship clustering (DMTRC) algorithms DMTRC-L and DMTRC-R which also avoid negative transfer, S-MBC and S-MKC perform worse in the (ideal) case in which different tasks have the same cluster number and the empirical label marginal distribution in each task distributes evenly, but better or comparable in other (more general) cases. Moreover, S-MBC and S-MKC can work on the datasets in which different tasks have different number of clusters, violating the assumptions of DMTRC-L and DMTRC-R. The results on efficiency show that S-MBC and S-MKC consume more computational time than MBC and less computational time than DMTRC-L and DMTRC-R. Overall S-MBC and S-MKC are competitive compared with the state-of-the-art multitask clustering algorithms in synthetical terms of accuracy, efficiency and applicability.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {8},
numpages = {29},
keywords = {negative transfer, Multitask clustering, Mercer kernel, Bregman divergence}
}

@article{10.1145/2742801,
author = {Yu, Zhiwen and Wang, Zhu and He, Huilei and Tian, Jilei and Lu, Xinjiang and Guo, Bin},
title = {Discovering Information Propagation Patterns in Microblogging Services},
year = {2015},
issue_date = {July 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2742801},
doi = {10.1145/2742801},
abstract = {During the last decade, microblog has become an important social networking service with billions of users all over the world, acting as a novel and efficient platform for the creation and dissemination of real-time information. Modeling and revealing the information propagation patterns in microblogging services cannot only lead to more accurate understanding of user behaviors and provide insights into the underlying sociology, but also enable useful applications such as trending prediction, recommendation and filtering, spam detection and viral marketing. In this article, we aim to reveal the information propagation patterns in Sina Weibo, the biggest microblogging service in China. First, the cascade of each message is represented as a tree based on its retweeting process. Afterwards, we divide the information propagation pattern into two levels, that is, the macro level and the micro level. On one hand, the macro propagation patterns refer to general propagation modes that are extracted by grouping propagation trees based on hierarchical clustering. On the other hand, the micro propagation patterns are frequent information flow patterns that are discovered using tree-based mining techniques. Experimental results show that several interesting patterns are extracted, such as popular message propagation, artificial propagation, and typical information flows between different types of users.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {7},
numpages = {22},
keywords = {propagation tree, microblogging services, message cascade, Information propagation pattern}
}

@article{10.1145/2735634,
author = {Liu, Siyuan and Qu, Qiang and Wang, Shuhui},
title = {Rationality Analytics from Trajectories},
year = {2015},
issue_date = {July 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2735634},
doi = {10.1145/2735634},
abstract = {The availability of trajectories tracking the geographical locations of people as a function of time offers an opportunity to study human behaviors. In this article, we study rationality from the perspective of user decision on visiting a point of interest (POI) which is represented as a trajectory. However, the analysis of rationality is challenged by a number of issues, for example, how to model a trajectory in terms of complex user decision processes? and how to detect hidden factors that have significant impact on the rational decision making? In this study, we propose Rationality Analysis Model (RAM) to analyze rationality from trajectories in terms of a set of impact factors. In order to automatically identify hidden factors, we propose a method, Collective Hidden Factor Retrieval (CHFR), which can also be generalized to parse multiple trajectories at the same time or parse individual trajectories of different time periods. Extensive experimental study is conducted on three large-scale real-life datasets (i.e., taxi trajectories, user shopping trajectories, and visiting trajectories in a theme park). The results show that the proposed methods are efficient, effective, and scalable. We also deploy a system in a large theme park to conduct a field study. Interesting findings and user feedback of the field study are provided to support other applications in user behavior mining and analysis, such as business intelligence and user management for marketing purposes.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {10},
numpages = {22},
keywords = {Rationality analytics, decision model, trajectory}
}

@article{10.1145/2749465,
author = {Wei, Wei and Carley, Kathleen M.},
title = {Measuring Temporal Patterns in Dynamic Social Networks},
year = {2015},
issue_date = {July 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2749465},
doi = {10.1145/2749465},
abstract = {Given social networks over time, how can we measure network activities across different timesteps with a limited number of metrics? We propose two classes of dynamic metrics for assessing temporal evolution patterns of agents in terms of persistency and emergence. For each class of dynamic metrics, we implement it using three different temporal aggregation models ranging from the most commonly used Average Aggregation Model to more the complex models such as the Exponential Aggregation Model. We argue that the problem of measuring temporal patterns can be formulated using Recency and Primacy effect, which is a concept used to characterize human cognitive processes. Experimental results show that the way metrics model Recency--Primacy effect is closely related to their abilities to measure temporal patterns. Furthermore, our results indicate that future network agent activities can be predicted based on history information using dynamic metrics. By conducting multiple experiments, we are also able to find an optimal length of history information that is most relevant to future activities. This optimal length is highly consistent within a dataset and can be used as an intrinsic metric to evaluate a dynamic social network.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {9},
numpages = {27},
keywords = {aggregating method, temporal analysis, Primacy and Recency effects, Social network analysis}
}

@article{10.1145/2742548,
author = {Berardi, Giacomo and Esuli, Andrea and Sebastiani, Fabrizio},
title = {Utility-Theoretic Ranking for Semiautomated Text Classification},
year = {2015},
issue_date = {July 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2742548},
doi = {10.1145/2742548},
abstract = {Semiautomated Text Classification (SATC) may be defined as the task of ranking a set D of automatically labelled textual documents in such a way that, if a human annotator validates (i.e., inspects and corrects where appropriate) the documents in a top-ranked portion of D with the goal of increasing the overall labelling accuracy of D, the expected increase is maximized. An obvious SATC strategy is to rank D so that the documents that the classifier has labelled with the lowest confidence are top ranked. In this work, we show that this strategy is suboptimal. We develop new utility-theoretic ranking methods based on the notion of validation gain, defined as the improvement in classification effectiveness that would derive by validating a given automatically labelled document. We also propose a new effectiveness measure for SATC-oriented ranking methods, based on the expected reduction in classification error brought about by partially validating a list generated by a given ranking method. We report the results of experiments showing that, with respect to the baseline method mentioned earlier, and according to the proposed measure, our utility-theoretic ranking methods can achieve substantially higher expected reductions in classification error.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {6},
numpages = {32},
keywords = {Text classification, supervised learning, semiautomated text classification, ranking, cost-sensitive learning}
}

@article{10.1145/2724720,
author = {Mirbakhsh, Nima and Ling, Charles X.},
title = {Improving Top-N Recommendation for Cold-Start Users via Cross-Domain Information},
year = {2015},
issue_date = {June 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2724720},
doi = {10.1145/2724720},
abstract = {Making accurate recommendations for cold-start users is a challenging yet important problem in recommendation systems. Including more information from other domains is a natural solution to improve the recommendations. However, most previous work in cross-domain recommendations has focused on improving prediction accuracy with several severe limitations. In this article, we extend our previous work on clustering-based matrix factorization in single domains into cross domains. In addition, we utilize recent results on unobserved ratings. Our new method can more effectively utilize data from auxiliary domains to achieve better recommendations, especially for cold-start users. For example, our method improves the recall to 21% on average for cold-start users, whereas previous methods result in only 15% recall in the cross-domain Amazon dataset. We also observe almost the same improvements in the Epinions dataset. Considering that it is often difficult to make even a small improvement in recommendations, for cold- start users in particular, our result is quite significant.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {33},
numpages = {19},
keywords = {recommendation system, cold start, matrix factorization, Collaborative filtering}
}

@article{10.1145/2728170,
author = {Bonchi, Francesco and Gionis, Aristides and Gullo, Francesco and Tsourakakis, Charalampos E. and Ukkonen, Antti},
title = {Chromatic Correlation Clustering},
year = {2015},
issue_date = {June 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2728170},
doi = {10.1145/2728170},
abstract = {We study a novel clustering problem in which the pairwise relations between objects are categorical. This problem can be viewed as clustering the vertices of a graph whose edges are of different types (colors). We introduce an objective function that ensures the edges within each cluster have, as much as possible, the same color. We show that the problem is NP-hard and propose a randomized algorithm with approximation guarantee proportional to the maximum degree of the input graph. The algorithm iteratively picks a random edge as a pivot, builds a cluster around it, and removes the cluster from the graph. Although being fast, easy to implement, and parameter-free, this algorithm tends to produce a relatively large number of clusters. To overcome this issue we introduce a variant algorithm, which modifies how the pivot is chosen and how the cluster is built around the pivot. Finally, to address the case where a fixed number of output clusters is required, we devise a third algorithm that directly optimizes the objective function based on the alternating-minimization paradigm.We also extend our objective function to handle cases where object’s relations are described by multiple labels. We modify our randomized approximation algorithm to optimize such an extended objective function and show that its approximation guarantee remains proportional to the maximum degree of the graph.We test our algorithms on synthetic and real data from the domains of social media, protein-interaction networks, and bibliometrics. Results reveal that our algorithms outperform a baseline algorithm both in the task of reconstructing a ground-truth clustering and in terms of objective-function value.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {34},
numpages = {24},
keywords = {edge-labeled graphs, Clustering, correlation clustering}
}

@article{10.1145/2700407,
author = {Lin, Bing-Rong and Kifer, Daniel},
title = {Information Measures in Statistical Privacy and Data Processing Applications},
year = {2015},
issue_date = {June 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2700407},
doi = {10.1145/2700407},
abstract = {In statistical privacy, utility refers to two concepts: information preservation, how much statistical information is retained by a sanitizing algorithm, and usability, how (and with how much difficulty) one extracts this information to build statistical models, answer queries, and so forth. Some scenarios incentivize a separation between information preservation and usability, so that the data owner first chooses a sanitizing algorithm to maximize a measure of information preservation, and, afterward, the data consumers process the sanitized output according to their various individual needs [Ghosh et al. 2009; Williams and McSherry 2010].We analyze the information-preserving properties of utility measures with a combination of two new and three existing utility axioms and study how violations of an axiom can be fixed. We show that the average (over possible outputs of the sanitizer) error of Bayesian decision makers forms the unique class of utility measures that satisfy all of the axioms. The axioms are agnostic to Bayesian concepts such as subjective probabilities and hence strengthen support for Bayesian views in privacy research. In particular, this result connects information preservation to aspects of usability—if the information preservation of a sanitizing algorithm should be measured as the average error of a Bayesian decision maker, shouldn’t Bayesian decision theory be a good choice when it comes to using the sanitized outputs for various purposes? We put this idea to the test in the unattributed histogram problem where our decision-theoretic postprocessing algorithm empirically outperforms previously proposed approaches.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {28},
numpages = {29},
keywords = {differential privacy, decision theory, information measures, utility, Privacy, minimax}
}

@article{10.1145/2700386,
author = {Xie, Hong and Lui, John C. S.},
title = {Mathematical Modeling and Analysis of Product Rating with Partial Information},
year = {2015},
issue_date = {June 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2700386},
doi = {10.1145/2700386},
abstract = {Many Web services like Amazon, Epinions, and TripAdvisor provide historical product ratings so that users can evaluate the quality of products. Product ratings are important because they affect how well a product will be adopted by the market. The challenge is that we only have partial information on these ratings: each user assigns ratings to only a small subset of products. Under this partial information setting, we explore a number of fundamental questions. What is the minimum number of ratings a product needs so that one can make a reliable evaluation of its quality? How may users’ misbehavior, such as cheating in product rating, affect the evaluation result? To answer these questions, we present a probabilistic model to capture various important factors (e.g., rating aggregation rules, rating behavior) that may influence the product quality assessment under the partial information setting. We derive the minimum number of ratings needed to produce a reliable indicator on the quality of a product. We extend our model to accommodate users’ misbehavior in product rating. We derive the maximum fraction of misbehaving users that a rating aggregation rule can tolerate and the minimum number of ratings needed to compensate. We carry out experiments using both synthetic and real-world

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr

branch_name: refs/heads/main