text:
data (from Amazon and TripAdvisor). We not only validate our model but also show that the “average rating rule” produces more reliable and robust product quality assessments than the “majority rating rule” and the “median rating rule” in aggregating product ratings. Last, we perform experiments on two movie rating datasets (from Flixster and Netflix) to demonstrate how to apply our framework to improve the applications of recommender systems.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {26},
numpages = {33},
keywords = {bias, rating aggregation rule, misbehavior, true quality, minimum number of ratings, Product rating}
}

@article{10.1145/2700406,
author = {Esuli, Andrea and Sebastiani, Fabrizio},
title = {Optimizing Text Quantifiers for Multivariate Loss Functions},
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/2700406},
doi = {10.1145/2700406},
abstract = {We address the problem of quantification, a supervised learning task whose goal is, given a class, to estimate the relative frequency (or prevalence) of the class in a dataset of unlabeled items. Quantification has several applications in data and text mining, such as estimating the prevalence of positive reviews in a set of reviews of a given product or estimating the prevalence of a given support issue in a dataset of transcripts of phone calls to tech support. So far, quantification has been addressed by learning a general-purpose classifier, counting the unlabeled items that have been assigned the class, and tuning the obtained counts according to some heuristics. In this article, we depart from the tradition of using general-purpose classifiers and use instead a supervised learning model for structured prediction, capable of generating classifiers directly optimized for the (multivariate and nonlinear) function used for evaluating quantification accuracy. The experiments that we have run on 5,500 binary high-dimensional datasets (averaging more than 14,000 documents each) show that this method is more accurate, more stable, and more efficient than existing state-of-the-art quantification methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {27},
numpages = {27},
keywords = {supervised learning, prior estimation, Kullback-Leibler divergence, prevalence estimation, text classification, loss functions, Quantification}
}

@article{10.1145/2700385,
author = {Huang, Hao and Yoo, Shinjae and Yu, Dantong and Qin, Hong},
title = {Density-Aware Clustering Based on Aggregated Heat Kernel and Its Transformation},
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/2700385},
doi = {10.1145/2700385},
abstract = {Current spectral clustering algorithms suffer from the sensitivity to existing noise and parameter scaling and may not be aware of different density distributions across clusters. If these problems are left untreated, the consequent clustering results cannot accurately represent true data patterns, in particular, for complex real-world datasets with heterogeneous densities. This article aims to solve these problems by proposing a diffusion-based Aggregated Heat Kernel (AHK) to improve the clustering stability, and a Local Density Affinity Transformation (LDAT) to correct the bias originating from different cluster densities. AHK statistically models the heat diffusion traces along the entire time scale, so it ensures robustness during the clustering process, while LDAT probabilistically reveals the local density of each instance and suppresses the local density bias in the affinity matrix. Our proposed framework integrates these two techniques systematically. As a result, it not only provides an advanced noise-resisting and density-aware spectral mapping to the original dataset but also demonstrates the stability during the processing of tuning the scaling parameter (which usually controls the range of neighborhood). Furthermore, our framework works well with the majority of similarity kernels, which ensures its applicability to many types of data and problem domains. The systematic experiments on different applications show that our proposed algorithm outperforms state-of-the-art clustering algorithms for the data with heterogeneous density distributions and achieves robust clustering performance with respect to tuning the scaling parameter and handling various levels and types of noise.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {29},
numpages = {35},
keywords = {Aggregated Heat Kernel, Local Density Affinity Transformation}
}

@article{10.1145/2701430,
author = {Liu, Guimei and Zhang, Haojun and Feng, Mengling and Wong, Limsoon and Ng, See-Kiong},
title = {Supporting Exploratory Hypothesis Testing and Analysis},
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/2701430},
doi = {10.1145/2701430},
abstract = {Conventional hypothesis testing is carried out in a hypothesis-driven manner. A scientist must first formulate a hypothesis based on what he or she sees and then devise a variety of experiments to test it. Given the rapid growth of data, it has become virtually impossible for a person to manually inspect all data to find all of the interesting hypotheses for testing. In this article, we propose and develop a data-driven framework for automatic hypothesis testing and analysis. We define a hypothesis as a comparison between two or more subpopulations. We find subpopulations for comparison using frequent pattern mining techniques and then pair them up for statistical hypothesis testing. We also generate additional information for further analysis of the hypotheses that are deemed significant. The number of hypotheses generated can be very large, and many of them are very similar. We develop algorithms to remove redundant hypotheses and present a succinct set of significant hypotheses to users. We conducted a set of experiments to show the efficiency and effectiveness of the proposed algorithms. The results show that our system can help users (1) identify significant hypotheses efficiently, (2) isolate the reasons behind significant hypotheses efficiently, and (3) find confounding factors that form Simpson’s paradoxes with discovered significant hypotheses.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {31},
numpages = {24},
keywords = {comparative data analysis, exploratory data mining, Exploratory hypothesis testing, actionable knowledge}
}

@article{10.1145/2710020,
author = {Greco, Gianluigi and Guzzo, Antonella and Lupia, Francesco and Pontieri, Luigi},
title = {Process Discovery under Precedence Constraints},
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/2710020},
doi = {10.1145/2710020},
abstract = {Process discovery has emerged as a powerful approach to support the analysis and the design of complex processes. It consists of analyzing a set of traces registering the sequence of tasks performed along several enactments of a transactional system, in order to build a process model that can explain all the episodes recorded over them. An approach to accomplish this task is presented that can benefit from the background knowledge that, in many cases, is available to the analysts taking care of the process (re-)design. The approach is based on encoding the information gathered from the log and the (possibly) given background knowledge in terms of precedence constraints, that is, of constraints over the topology of the resulting process models. Mining algorithms are eventually formulated in terms of reasoning problems over precedence constraints, and the computational complexity of such problems is thoroughly analyzed by tracing their tractability frontier. Solution algorithms are proposed and their properties analyzed. These algorithms have been implemented in a prototype system, and results of a thorough experimental activity are discussed.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {32},
numpages = {39},
keywords = {computational complexity, Process mining, graph analysis}
}

@article{10.1145/2700409,
author = {Yu, Kui and Ding, Wei and Simovici, Dan A. and Wang, Hao and Pei, Jian and Wu, Xindong},
title = {Classification with Streaming Features: An Emerging-Pattern Mining Approach},
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/2700409},
doi = {10.1145/2700409},
abstract = {Many datasets from real-world applications have very high-dimensional or increasing feature space. It is a new research problem to learn and maintain a classifier to deal with very high dimensionality or streaming features. In this article, we adapt the well-known emerging-pattern--based classification models and propose a semi-streaming approach. For streaming features, it is computationally expensive or even prohibitive to mine long-emerging patterns, and it is nontrivial to integrate emerging-pattern mining with feature selection. We present an online feature selection step, which is capable of selecting and maintaining a pool of effective features from a feature stream. Then, in our offline step, separated from the online step, we periodically compute and update emerging patterns from the pool of selected features from the online step. We evaluate the effectiveness and efficiency of the proposed method using a series of benchmark datasets and a real-world case study on Mars crater detection. Our proposed method yields classification performance comparable to the state-of-art static classification methods. Most important, the proposed method is significantly faster and can efficiently handle datasets with streaming features.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {30},
numpages = {31},
keywords = {streaming features, Emerging patterns, classification, feature selection}
}

@article{10.1145/2629585,
author = {Gopal, Siddharth and Yang, Yiming},
title = {Hierarchical Bayesian Inference and Recursive Regularization for Large-Scale Classification},
year = {2015},
issue_date = {April 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2629585},
doi = {10.1145/2629585},
abstract = {In this article, we address open challenges in large-scale classification, focusing on how to effectively leverage the dependency structures (hierarchical or graphical) among class labels, and how to make the inference scalable in jointly optimizing all model parameters. We propose two main approaches, namely the hierarchical Bayesian inference framework and the recursive regularization scheme. The key idea in both approaches is to reinforce the similarity among parameter across the nodes in a hierarchy or network based on the proximity and connectivity of the nodes. For scalability, we develop hierarchical variational inference algorithms and fast dual coordinate descent training procedures with parallelization. In our experiments for classification problems with hundreds of thousands of classes and millions of training instances with terabytes of parameters, the proposed methods show consistent and statistically significant improvements over other competing approaches, and the best results on multiple benchmark datasets for large-scale classification.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {18},
numpages = {23},
keywords = {Bayesian methods, hierarchical classification, Large-scale optimization}
}

@article{10.1145/2700403,
author = {Vlachos, Michail and Schneider, Johannes and Vassiliadis, Vassilios G.},
title = {On Data Publishing with Clustering Preservation},
year = {2015},
issue_date = {April 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2700403},
doi = {10.1145/2700403},
abstract = {The emergence of cloud-based storage services is opening up new avenues in data exchange and data dissemination. This has amplified the interest in right-protection mechanisms to establish ownership in the event of data leakage. Current right-protection technologies, however, rarely provide strong guarantees on dataset utility after the protection process. This work presents techniques that explicitly address this topic and provably preserve the outcome of certain mining operations. In particular, we take special care to guarantee that the outcome of hierarchical clustering operations remains the same before and after right protection. Our approach considers all prevalent hierarchical clustering variants: single-, complete-, and average-linkage. We imprint the ownership in a dataset using watermarking principles, and we derive tight bounds on the expansion/contraction of distances incurred by the process. We leverage our analysis to design fast algorithms for right protection without exhaustively searching the vast design space. Finally, because the right-protection process introduces a user-tunable distortion on the dataset, we explore the possibility of using this mechanism for data obfuscation. We quantify the tradeoff between obfuscation and utility for spatiotemporal datasets and discover very favorable characteristics of the process. An additional advantage is that when one is interested in both right-protecting and obfuscating the original data values, the proposed mechanism can accomplish both tasks simultaneously.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {23},
numpages = {30},
keywords = {Distance-Based Mining, Restricted Isometry Property, Distortion Estimation, Watermarking}
}

@article{10.1145/2700405,
author = {Hu, Juhua and Zhan, De-Chuan and Wu, Xintao and Jiang, Yuan and Zhou, Zhi-Hua},
title = {Pairwised Specific Distance Learning from Physical Linkages},
year = {2015},
issue_date = {April 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2700405},
doi = {10.1145/2700405},
abstract = {In real tasks, usually a good classification performance can only be obtained when a good distance metric is obtained; therefore, distance metric learning has attracted significant attention in the past few years. Typical studies of distance metric learning evaluate how to construct an appropriate distance metric that is able to separate training data points from different classes or satisfy a set of constraints (e.g., must-links and/or cannot-links). It is noteworthy that this task becomes challenging when there are only limited labeled training data points and no constraints are given explicitly. Moreover, most existing approaches aim to construct a global distance metric that is applicable to all data points. However, different data points may have different properties and may require different distance metrics. We notice that data points in real tasks are often connected by physical links (e.g., people are linked with each other in social networks; personal webpages are often connected to other webpages, including nonpersonal webpages), but the linkage information has not been exploited in distance metric learning. In this article, we develop a pairwised specific distance (PSD) approach that exploits the structures of physical linkages and in particular captures the key observations that nonmetric and clique linkages imply the appearance of different or unique semantics, respectively. It is noteworthy that, rather than generating a global distance, PSD generates different distances for different pairs of data points; this property is desired in applications involving complicated data semantics. We mainly present PSD for multi-class learning and further extend it to multi-label learning. Experimental results validate the effectiveness of PSD, especially in the scenarios in which there are very limited labeled training data points and no explicit constraints are given.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {20},
numpages = {27},
keywords = {unlabeled data, multi-label learning, nonmetric linkage, Distance metric learning, multi-class learning, physical linkages}
}

@article{10.1145/2700404,
author = {Soundarajan, Sucheta and Hopcroft, John E.},
title = {Use of Local Group Information to Identify Communities in Networks},
year = {2015},
issue_date = {April 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2700404},
doi = {10.1145/2700404},
abstract = {The recent interest in networks has inspired a broad range of work on algorithms and techniques to characterize, identify, and extract communities from networks. Such efforts are complicated by a lack of consensus on what a “community” truly is, and these disagreements have led to a wide variety of mathematical formulations for describing communities. Often, these mathematical formulations, such as modularity and conductance, have been founded in the general principle that communities, like a G(n, p) graph, are “round,” with connections throughout the entire community, and so algorithms were developed to optimize such mathematical measures. More recently, a variety of algorithms have been developed that, rather than expecting connectivity through the entire community, seek out very small groups of well-connected nodes and then connect these groups into larger communities. In this article, we examine seven real networks, each containing external annotation that allows us to identify “annotated communities.” A study of these annotated communities gives insight into why the second category of community detection algorithms may be more successful than the first category. We then present a flexible algorithm template that is based on the idea of joining together small sets of nodes. In this template, we first identify very small, tightly connected “subcommunities” of nodes, each corresponding to a single node’s “perception” of the network around it. We then create a new network in which each node represents such a subcommunity, and then identify communities in this new network. Because each node can appear in multiple subcommunities, this method allows us to detect overlapping communities. When evaluated on real data, we show that our template outperforms many other state-of-the-art algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {21},
numpages = {27},
keywords = {communities, Social networks}
}

@article{10.1145/2700398,
author = {Zhang, Jing and Tang, Jie and Li, Juanzi and Liu, Yang and Xing, Chunxiao},
title = {Who Influenced You? Predicting Retweet via Social Influence Locality},
year = {2015},
issue_date = {April 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2700398},
doi = {10.1145/2700398},
abstract = {Social influence occurs when one’s opinions, emotions, or behaviors are affected by others in a social network. However, social influence takes many forms, and its underlying mechanism is still unclear. For example, how is one’s behavior influenced by a group of friends who know each other and by the friends from different ego friend circles? In this article, we study the social influence problem in a large microblogging network. Particularly, we consider users’ (re)tweet behaviors and focus on investigating how friends in one’s ego network influence retweet behaviors. We propose a novel notion of social influence locality and develop two instantiation functions based on pairwise influence and structural diversity. The defined influence locality functions have strong predictive power. Without any additional features, we can obtain an F1-score of 71.65% for predicting users’ retweet behaviors by training a logistic regression classifier based on the defined influence locality functions. We incorporate social influence locality into a factor graph model, which can further leverage the network-based correlation. Our experiments on the large microblogging network show that the model significantly improves the precision of retweet prediction. Our analysis also reveals several intriguing discoveries. For example, if you have six friends retweeting a microblog, the average likelihood that you will also retweet it strongly depends on the structure among the six friends: The likelihood will significantly drop (only ⅙) when the six friends do not know each other, compared with the case when the six friends know each other.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {25},
numpages = {26},
keywords = {retweet prediction, Social network, microblog network, social influence}
}

@article{10.1145/2700393,
author = {Wang, Pinghui and Zhao, Junzhou and Lui, John C. S. and Towsley, Don and Guan, Xiaohong},
title = {Unbiased Characterization of Node Pairs over Large Graphs},
year = {2015},
issue_date = {April 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2700393},
doi = {10.1145/2700393},
abstract = {Characterizing user pair relationships is important for applications such as friend recommendation and interest targeting in online social networks (OSNs). Due to the large-scale nature of such networks, it is infeasible to enumerate all user pairs and thus sampling is used. In this article, we show that it is a great challenge for OSN service providers to characterize user pair relationships, even when they possess the complete graph topology. The reason is that when sampling techniques (i.e., uniform vertex sampling (UVS) and random walk (RW)) are naively applied, they can introduce large biases, particularly for estimating similarity distribution of user pairs with constraints like existence of mutual neighbors, which is important for applications such as identifying network homophily. Estimating statistics of user pairs is more challenging in the absence of the complete topology information, as an unbiased sampling technique like UVS is usually not allowed and exploring the OSN graph topology is expensive. To address these challenges, we present unbiased sampling methods to characterize user pair properties based on UVS and RW techniques. We carry out an evaluation of our methods to show their accuracy and efficiency. Finally, we apply our methods to three OSNs—Foursquare, Douban, and Xiami—and discover that significant homophily is present in these networks.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {22},
numpages = {27},
keywords = {random walks, graph sampling, homophily, Social network}
}

@article{10.1145/2700399,
author = {Melo, Pedro O. S. Vaz De and Faloutsos, Christos and Assun\c{c}\~{a}o, Renato and Alves, Rodrigo and Loureiro, Antonio A. F.},
title = {Universal and Distinct Properties of Communication Dynamics: How to Generate Realistic Inter-Event Times},
year = {2015},
issue_date = {April 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2700399},
doi = {10.1145/2700399},
abstract = {With the advancement of information systems, means of communications are becoming cheaper, faster, and more available. Today, millions of people carrying smartphones or tablets are able to communicate practically any time and anywhere they want. They can access their e-mails, comment on weblogs, watch and post videos and photos (as well as comment on them), and make phone calls or text messages almost ubiquitously. Given this scenario, in this article, we tackle a fundamental aspect of this new era of communication: How the time intervals between communication events behave for different technologies and means of communications. Are there universal patterns for the Inter-Event Time Distribution (IED)? How do inter-event times behave differently among particular technologies? To answer these questions, we analyzed eight different datasets from real and modern communication data and found four well-defined patterns seen in all the eight datasets. Moreover, we propose the use of the Self-Feeding Process (SFP) to generate inter-event times between communications. The SFP is an extremely parsimonious point process that requires at most two parameters and is able to generate inter-event times with all the universal properties we observed in the data. We also show three potential applications of the SFP: as a framework to generate a synthetic dataset containing realistic communication events of any one of the analyzed means of communications, as a technique to detect anomalies, and as a building block for more specific models that aim to encompass the particularities seen in each of the analyzed systems.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {24},
numpages = {31},
keywords = {inter-event times, generative model, Communication dynamics}
}

@article{10.1145/2663356,
author = {Yin, Hongzhi and Cui, Bin and Chen, Ling and Hu, Zhiting and Zhang, Chengqi},
title = {Modeling Location-Based User Rating Profiles for Personalized Recommendation},
year = {2015},
issue_date = {April 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2663356},
doi = {10.1145/2663356},
abstract = {This article proposes LA-LDA, a location-aware probabilistic generative model that exploits location-based ratings to model user profiles and produce recommendations. Most of the existing recommendation models do not consider the spatial information of users or items; however, LA-LDA supports three classes of location-based ratings, namely spatial user ratings for nonspatial items, nonspatial user ratings for spatial items, and spatial user ratings for spatial items. LA-LDA consists of two components, ULA-LDA and ILA-LDA, which are designed to take into account user and item location information, respectively. The component ULA-LDA explicitly incorporates and quantifies the influence from local public preferences to produce recommendations by considering user home locations, whereas the component ILA-LDA recommends items that are closer in both taste and travel distance to the querying users by capturing item co-occurrence patterns, as well as item location co-occurrence patterns. The two components of LA-LDA can be applied either separately or collectively, depending on the available types of location-based ratings. To demonstrate the applicability and flexibility of the LA-LDA model, we deploy it to both top-k recommendation and cold start recommendation scenarios. Experimental evidence on large-scale real-world data, including the data from Gowalla (a location-based social network), DoubanEvent (an event-based social network), and MovieLens (a movie recommendation system), reveal that LA-LDA models user profiles more accurately by outperforming existing recommendation models for top-k recommendation and the cold start problem.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {19},
numpages = {41},
keywords = {recommender system, probabilistic generative model, User profile, cold start, location-based services}
}

@article{10.1145/2700993,
author = {Gionis, Aristides and Li, Hang},
title = {Introduction to the Special Issue ACM SIGKDD 2013},
year = {2015},
issue_date = {April 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2700993},
doi = {10.1145/2700993},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {15e},
numpages = {2}
}

@article{10.1145/2700395,
author = {Jha, Madhav and Seshadhri, C. and Pinar, Ali},
title = {A Space-Efficient Streaming Algorithm for Estimating Transitivity and Triangle Counts Using the Birthday Paradox},
year = {2015},
issue_date = {April 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2700395},
doi = {10.1145/2700395},
abstract = {We design a space-efficient algorithm that approximates the transitivity (global clustering coefficient) and total triangle count with only a single pass through a graph given as a stream of edges. Our procedure is based on the classic probabilistic result, the birthday paradox. When the transitivity is constant and there are more edges than wedges (common properties for social networks), we can prove that our algorithm requires O(√n) space (n is the number of vertices) to provide accurate estimates. We run a detailed set of experiments on a variety of real graphs and demonstrate that the memory requirement of the algorithm is a tiny fraction of the graph. For example, even for a graph with 200 million edges, our algorithm stores just 40,000 edges to give accurate results. Being a single pass streaming algorithm, our procedure also maintains a real-time estimate of the transitivity/number of triangles of a graph by storing a minuscule fraction of edges.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {15},
numpages = {21},
keywords = {Triangle counting, transitivity, streaming graphs, streaming algorithms, birthday paradox, clustering coefficient}
}

@article{10.1145/2700408,
author = {Wang, Zheng and Ye, Jieping},
title = {Querying Discriminative and Representative Samples for Batch Mode Active Learning},
year = {2015},
issue_date = {April 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2700408},
doi = {10.1145/2700408},
abstract = {Empirical risk minimization (ERM) provides a principled guideline for many machine learning and data mining algorithms. Under the ERM principle, one minimizes an upper bound of the true risk, which is approximated by the summation of empirical risk and the complexity of the candidate classifier class. To guarantee a satisfactory learning performance, ERM requires that the training data are i.i.d. sampled from the unknown source distribution. However, this may not be the case in active learning, where one selects the most informative samples to label, and these data may not follow the source distribution. In this article, we generalize the ERM principle to the active learning setting. We derive a novel form of upper bound for the true risk in the active learning setting; by minimizing this upper bound, we develop a practical batch mode active learning method. The proposed formulation involves a nonconvex integer programming optimization problem. We solve it efficiently by an alternating optimization method. Our method is shown to query the most informative samples while preserving the source distribution as much as possible, thus identifying the most uncertain and representative queries. We further extend our method to multiclass active learning by introducing novel pseudolabels in the multiclass case and developing an efficient algorithm. Experiments on benchmark datasets and real-world applications demonstrate the superior performance of our proposed method compared to state-of-the-art methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {17},
numpages = {23},
keywords = {empirical risk minimization, representative and discriminative, Active learning, maximum mean discrepancy}
}

@article{10.1145/2700394,
author = {Tang, Lu-An and Yu, Xiao and Gu, Quanquan and Han, Jiawei and Jiang, Guofei and Leung, Alice and Porta, Thomas La},
title = {A Framework of Mining Trajectories from Untrustworthy Data in Cyber-Physical System},
year = {2015},
issue_date = {April 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2700394},
doi = {10.1145/2700394},
abstract = {A cyber-physical system (CPS) integrates physical (i.e., sensor) devices with cyber (i.e., informational) components to form a context-sensitive system that responds intelligently to dynamic changes in real-world situations. The CPS has wide applications in scenarios such as environment monitoring, battlefield surveillance, and traffic control. One key research problem of CPS is called mining lines in the sand. With a large number of sensors (sand) deployed in a designated area, the CPS is required to discover all trajectories (lines) of passing intruders in real time. There are two crucial challenges that need to be addressed: (1) the collected sensor data are not trustworthy, and (2) the intruders do not send out any identification information. The system needs to distinguish multiple intruders and track their movements. This study proposes a method called LiSM (Line-in-the-Sand Miner) to discover trajectories from untrustworthy sensor data. LiSM constructs a watching network from sensor data and computes the locations of intruder appearances based on the link information of the network. The system retrieves a cone model from the historical trajectories to track multiple intruders. Finally, the system validates the mining results and updates sensors’ reliability scores in a feedback process. In addition, LoRM (Line-on-the-Road Miner) is proposed for trajectory discovery on road networks—mining lines on the roads. LoRM employs a filtering-and-refinement framework to reduce the distance computational overhead on road networks and uses a shortest-path-measure to track intruders. The proposed methods are evaluated with extensive experiments on big datasets. The experimental results show that the proposed methods achieve higher accuracy and efficiency in trajectory mining tasks.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {16},
numpages = {35},
keywords = {trajectory, sensor network, Cyber-physical system}
}

@article{10.1145/2629474,
author = {Wang, Guangtao and Song, Qinbao and Zhang, Xueying and Zhang, Kaiyuan},
title = {A Generic Multilabel Learning-Based Classification Algorithm Recommendation Method},
year = {2014},
issue_date = {October 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2629474},
doi = {10.1145/2629474},
abstract = {As more and more classification algorithms continue to be developed, recommending appropriate algorithms to a given classification problem is increasingly important. This article first distinguishes the algorithm recommendation methods by two dimensions: (1) meta-features, which are a set of measures used to characterize the learning problems, and (2) meta-target, which represents the relative performance of the classification algorithms on the learning problem. In contrast to the existing algorithm recommendation methods whose meta-target is usually in the form of either the ranking of candidate algorithms or a single algorithm, this article proposes a new and natural multilabel form to describe the meta-target. This is due to the fact that there would be multiple algorithms being appropriate for a given problem in practice. Furthermore, a novel multilabel learning-based generic algorithm recommendation method is proposed, which views the algorithm recommendation as a multilabel learning problem and solves the problem by the mature multilabel learning algorithms. To evaluate the proposed multilabel learning-based recommendation method, extensive experiments with 13 well-known classification algorithms, two kinds of meta-targets such as algorithm ranking and single algorithm, and five different kinds of meta-features are conducted on 1,090 benchmark learning problems. The results show the effectiveness of our proposed multilabel learning-based recommendation method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {7},
numpages = {30},
keywords = {multilabel k nearest neighbors, multiple comparison procedure, Algorithm automatic recommendation, multilabel classification}
}

@article{10.1145/2629587,
author = {Tang, Jiliang and Liu, Huan},
title = {Feature Selection for Social Media Data},
year = {2014},
issue_date = {October 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2629587},
doi = {10.1145/2629587},
abstract = {Feature selection is widely used in preparing high-dimensional data for effective data mining. The explosive popularity of social media produces massive and high-dimensional data at an unprecedented rate, presenting new challenges to feature selection. Social media data consists of (1) traditional high-dimensional, attribute-value data such as posts, tweets, comments, and images, and (2) linked data that provides social context for posts and describes the relationships between social media users as well as who generates the posts, and so on. The nature of social media also determines that its data is massive, noisy, and incomplete, which exacerbates the already challenging problem of feature selection. In this article, we study a novel feature selection problem of selecting features for social media data with its social context. In detail, we illustrate the differences between attribute-value data and social media data, investigate if linked data can be exploited in a new feature selection framework by taking advantage of social science theories. We design and conduct experiments on datasets from real-world social media Web sites, and the empirical results demonstrate that the proposed framework can significantly improve the performance of feature selection. Further experiments are conducted to evaluate the effects of user--user and user--post relationships manifested in linked data on feature selection, and research issues for future work will be discussed.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {19},
numpages = {27},
keywords = {social context, social media data, Feature selection}
}

@article{10.1145/2601437,
author = {Miettinen, Pauli and Vreeken, Jilles},
title = {MDL4BMF: Minimum Description Length for Boolean Matrix Factorization},
year = {2014},
issue_date = {October 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2601437},
doi = {10.1145/2601437},
abstract = {Matrix factorizations—where a given data matrix is approximated by a product of two or more factor matrices—are powerful data mining tools. Among other tasks, matrix factorizations are often used to separate global structure from noise. This, however, requires solving the “model order selection problem” of determining the proper rank of the factorization, that is, to answer where fine-grained structure stops, and where noise starts.Boolean Matrix Factorization (BMF)—where data, factors, and matrix product are Boolean—has in recent years received increased attention from the data mining community. The technique has desirable properties, such as high interpretability and natural sparsity. Yet, so far no method for selecting the correct model order for BMF has been available. In this article, we propose the use of the Minimum Description Length (MDL) principle for this task. Besides solving the problem, this well-founded approach has numerous benefits; for example, it is automatic, does not require a likelihood function, is fast, and, as experiments show, is highly accurate.We formulate the description length function for BMF in general—making it applicable for any BMF algorithm. We discuss how to construct an appropriate encoding: starting from a simple and intuitive approach, we arrive at a highly efficient data-to-model--based encoding for BMF. We extend an existing algorithm for BMF to use MDL to identify the best Boolean matrix factorization, analyze the complexity of the problem, and perform an extensive experimental evaluation to study its behavior.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {18},
numpages = {31},
keywords = {model selection, Boolean rank, minimum description length principle, parameter free, model order selection, Boolean matrix factorization, pattern sets, MDL, summarization}
}

@article{10.1145/2629504,
author = {Huai, Baoxing and Chen, Enhong and Zhu, Hengshu and Xiong, Hui and Bao, Tengfei and Liu, Qi and Tian, Jilei},
title = {Toward Personalized Context Recognition for Mobile Users: A Semisupervised Bayesian HMM Approach},
year = {2014},
issue_date = {November 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2629504},
doi = {10.1145/2629504},
abstract = {The problem of mobile context recognition targets the identification of semantic meaning of context in a mobile environment. This plays an important role in understanding mobile user behaviors and thus provides the opportunity for the development of better intelligent context-aware services. A key step of context recognition is to model the personalized contextual information of mobile users. Although many studies have been devoted to mobile context modeling, limited efforts have been made on the exploitation of the sequential and dependency characteristics of mobile contextual information. Also, the latent semantics behind mobile context are often ambiguous and poorly understood. Indeed, a promising direction is to incorporate some domain knowledge of common contexts, such as “waiting for a bus” or “having dinner,” by modeling both labeled and unlabeled context data from mobile users because there are often few labeled contexts available in practice. To this end, in this article, we propose a sequence-based semisupervised approach to modeling personalized context for mobile users. Specifically, we first exploit the Bayesian Hidden Markov Model (B-HMM) for modeling context in the form of probabilistic distributions and transitions of raw context data. Also, we propose a sequential model by extending B-HMM with the prior knowledge of contextual features to model context more accurately. Then, to efficiently learn the parameters and initial values of the proposed models, we develop a novel approach for parameter estimation by integrating the Dirichlet Process Mixture (DPM) model and the Mixture Unigram (MU) model. Furthermore, by incorporating both user-labeled and unlabeled data, we propose a semisupervised learning-based algorithm to identify and model the latent semantics of context. Finally, experimental results on real-world data clearly validate both the efficiency and effectiveness of the proposed approaches for recognizing personalized context of mobile users.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {10},
numpages = {29},
keywords = {Context recognition, hidden Markov model}
}

@article{10.1145/2630421,
author = {Gundecha, Pritam and Barbier, Geoffrey and Tang, Jiliang and Liu, Huan},
title = {User Vulnerability and Its Reduction on a Social Networking Site},
year = {2014},
issue_date = {November 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2630421},
doi = {10.1145/2630421},
abstract = {Privacy and security are major concerns for many users of social media. When users share information (e.g., data and photos) with friends, they can make their friends vulnerable to security and privacy breaches with dire consequences. With the continuous expansion of a user’s social network, privacy settings alone are often inadequate to protect a user’s profile. In this research, we aim to address some critical issues related to privacy protection: (1) How can we measure and assess individual users’ vulnerability? (2) With the diversity of one’s social network friends, how can one figure out an effective approach to maintaining balance between vulnerability and social utility? In this work, first we present a novel way to define vulnerable friends from an individual user’s perspective. User vulnerability is dependent on whether or not the user’s friends’ privacy settings protect the friend and the individual’s network of friends (which includes the user). We show that it is feasible to measure and assess user vulnerability and reduce one’s vulnerability without changing the structure of a social networking site. The approach is to unfriend one’s most vulnerable friends. However, when such a vulnerable friend is also socially important, unfriending him or her would significantly reduce one’s own social status. We formulate this novel problem as vulnerability minimization with social utility constraints. We formally define the optimization problem and provide an approximation algorithm with a proven bound. Finally, we conduct a large-scale evaluation of a new framework using a Facebook dataset. We resort to experiments and observe how much vulnerability an individual user can be decreased by unfriending a vulnerable friend. We compare performance of different unfriending strategies and discuss the security risk of new friend requests. Additionally, by employing different forms of social utility, we confirm that the balance between user vulnerability and social utility can be practically achieved.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {12},
numpages = {25},
keywords = {social network, Vulnerability, privacy}
}

@article{10.1145/2629564,
author = {Wang, Pinghui and Lui, John C. S. and Ribeiro, Bruno and Towsley, Don and Zhao, Junzhou and Guan, Xiaohong},
title = {Efficiently Estimating Motif Statistics of Large Networks},
year = {2014},
issue_date = {November 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2629564},
doi = {10.1145/2629564},
abstract = {Exploring statistics of locally connected subgraph patterns (also known as network motifs) has helped researchers better understand the structure and function of biological and Online Social Networks (OSNs). Nowadays, the massive size of some critical networks—often stored in already overloaded relational databases—effectively limits the rate at which nodes and edges can be explored, making it a challenge to accurately discover subgraph statistics. In this work, we propose sampling methods to accurately estimate subgraph statistics from as few queried nodes as possible. We present sampling algorithms that efficiently and accurately estimate subgraph properties of massive networks. Our algorithms require no precomputation or complete network topology information. At the same time, we provide theoretical guarantees of convergence. We perform experiments using widely known datasets and show that, for the same accuracy, our algorithms require an order of magnitude less queries (samples) than the current state-of-the-art algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {8},
numpages = {27},
keywords = {subgraph patterns, network motifs, Social network, random walks, graph sampling}
}

@article{10.1145/2641574,
author = {Huang, Hao and Qin, Hong and Yoo, Shinjae and Yu, Dantong},
title = {Physics-Based Anomaly Detection Defined on Manifold Space},
year = {2014},
issue_date = {November 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2641574},
doi = {10.1145/2641574},
abstract = {Current popular anomaly detection algorithms are capable of detecting global anomalies but often fail to distinguish local anomalies from normal instances. Inspired by contemporary physics theory (i.e., heat diffusion and quantum mechanics), we propose two unsupervised anomaly detection algorithms. Building on the embedding manifold derived from heat diffusion, we devise Local Anomaly Descriptor (LAD), which faithfully reveals the intrinsic neighborhood density. It uses a scale-dependent umbrella operator to bridge global and local properties, which makes LAD more informative within an adaptive scope of neighborhood. To offer more stability of local density measurement on scaling parameter tuning, we formulate Fermi Density Descriptor (FDD), which measures the probability of a fermion particle being at a specific location. By choosing the stable energy distribution function, FDD steadily distinguishes anomalies from normal instances with any scaling parameter setting. To further enhance the efficacy of our proposed algorithms, we explore the utility of anisotropic Gaussian kernel (AGK), which offers better manifold-aware affinity information. We also quantify and examine the effect of different Laplacian normalizations for anomaly detection. Comprehensive experiments on both synthetic and benchmark datasets verify that our proposed algorithms outperform the existing anomaly detection algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {14},
numpages = {39},
keywords = {heat diffusion, Laplace operator, quantum mechanics, Anomaly detection}
}

@article{10.1145/2637484,
author = {Duan, Lian and Street, W. Nick and Liu, Yanchi and Xu, Songhua and Wu, Brook},
title = {Selecting the Right Correlation Measure for Binary Data},
year = {2014},
issue_date = {November 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2637484},
doi = {10.1145/2637484},
abstract = {Finding the most interesting correlations among items is essential for problems in many commercial, medical, and scientific domains. Although there are numerous measures available for evaluating correlations, different correlation measures provide drastically different results. Piatetsky-Shapiro provided three mandatory properties for any reasonable correlation measure, and Tan et al. proposed several properties to categorize correlation measures; however, it is still hard for users to choose the desirable correlation measures according to their needs. In order to solve this problem, we explore the effectiveness problem in three ways. First, we propose two desirable properties and two optional properties for correlation measure selection and study the property satisfaction for different correlation measures. Second, we study different techniques to adjust correlation measures and propose two new correlation measures: the Simplified χ2 with Continuity Correction and the Simplified χ2 with Support. Third, we analyze the upper and lower bounds of different measures and categorize them by the bound differences. Combining these three directions, we provide guidelines for users to choose the proper measure according to their needs.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {13},
numpages = {28},
keywords = {association rules, correlation, Knowledge discovery}
}

@article{10.1145/2629668,
author = {Liu, Siyuan and Chen, Lei and Ni, Lionel M.},
title = {Anomaly Detection from Incomplete Data},
year = {2014},
issue_date = {November 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2629668},
doi = {10.1145/2629668},
abstract = {Anomaly detection (a.k.a., outlier or burst detection) is a well-motivated problem and a major data mining and knowledge discovery task. In this article, we study the problem of population anomaly detection, one of the key issues related to event monitoring and population management within a city. Through studying detected population anomalies, we can trace and analyze these anomalies, which could help to model city traffic design and event impact analysis and prediction. Although a significant and interesting issue, it is very hard to detect population anomalies and retrieve anomaly trajectories, especially given that it is difficult to get actual and sufficient population data. To address the difficulties of a lack of real population data, we take advantage of mobile phone networks, which offer enormous spatial and temporal communication data on persons. More importantly, we claim that we can utilize these mobile phone data to infer and approximate population data. Thus, we can study the population anomaly detection problem by taking advantages of unique features hidden in mobile phone data. In this article, we present a system to conduct Population Anomaly Detection (PAD). First, we propose an effective clustering method, correlation-based clustering, to cluster the incomplete location information from mobile phone data (i.e., from mobile call volume distribution to population density distribution). Then, we design an adaptive parameter-free detection method, R-scan, to capture the distributed dynamic anomalies. Finally, we devise an efficient algorithm, BT-miner, to retrieve anomaly trajectories. The experimental results from real-life mobile phone data confirm the effectiveness and efficiency of the proposed algorithms. Finally, the proposed methods are realized as a pilot system in a city in China.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {11},
numpages = {22},
keywords = {anomaly trajectory, correlation-based clustering, mobile phone, Anomaly detection}
}

@article{10.1145/2611380,
author = {Zheng, Li and Li, Tao and Ding, Chris},
title = {A Framework for Hierarchical Ensemble Clustering},
year = {2014},
issue_date = {November 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2611380},
doi = {10.1145/2611380},
abstract = {Ensemble clustering, as an important extension of the clustering problem, refers to the problem of combining different (input) clusterings of a given dataset to generate a final (consensus) clustering that is a better fit in some sense than existing clusterings. Over the past few years, many ensemble clustering approaches have been developed. However, most of them are designed for partitional clustering methods, and few research efforts have been reported for ensemble hierarchical clustering methods. In this article, a hierarchical ensemble clustering framework that can naturally combine both partitional clustering and hierarchical clustering results is proposed. In addition, a novel method for learning the ultra-metric distance from the aggregated distance matrices and generating final hierarchical clustering with enhanced cluster separation is developed based on the ultra-metric distance for hierarchical clustering. We study three important problems: dendrogram description, dendrogram combination, and dendrogram selection. We develop two approaches for dendrogram selection based on tree distances, and we investigate various dendrogram distances for representing dendrograms. We provide a systematic empirical study of the ensemble hierarchical clustering problem. Experimental results demonstrate the effectiveness of our proposed approaches.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {9},
numpages = {23},
keywords = {ensemble selection, Hierarchical ensemble clustering, ultra-metric}
}

@article{10.1145/2641760,
author = {Paul, Saurabh and Boutsidis, Christos and Magdon-Ismail, Malik and Drineas, Petros},
title = {Random Projections for Linear Support Vector Machines},
year = {2014},
issue_date = {October 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2641760},
doi = {10.1145/2641760},
abstract = {Let X be a data matrix of rank ρ, whose rows represent n points in d-dimensional space. The linear support vector machine constructs a hyperplane separator that maximizes the 1-norm soft margin. We develop a new oblivious dimension reduction technique that is precomputed and can be applied to any input matrix X. We prove that, with high probability, the margin and minimum enclosing ball in the feature space are preserved to within ϵ-relative error, ensuring comparable generalization as in the original space in the case of classification. For regression, we show that the margin is preserved to ϵ-relative error with high probability. We present extensive experiments with real and synthetic data to support our theory.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {22},
numpages = {25},
keywords = {Classification, support vector machines, dimensionality reduction}
}

@article{10.1145/2629586,
author = {Riondato, Matteo and Upfal, Eli},
title = {Efficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees},
year = {2014},
issue_date = {October 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2629586},
doi = {10.1145/2629586},
abstract = {The tasks of extracting (top-K) Frequent Itemsets (FIs) and Association Rules (ARs) are fundamental primitives in data mining and database applications. Exact algorithms for these problems exist and are widely used, but their running time is hindered by the need of scanning the entire dataset, possibly multiple times. High-quality approximations of FIs and ARs are sufficient for most practical uses. Sampling techniques can be used for fast discovery of approximate solutions, but works exploring this technique did not provide satisfactory performance guarantees on the quality of the approximation due to the difficulty of bounding the probability of under- or oversampling any one of an unknown number of frequent itemsets. We circumvent this issue by applying the statistical concept of Vapnik-Chervonenkis (VC) dimension to develop a novel technique for providing tight bounds on the sample size that guarantees approximation of the (top-K) FIs and ARs within user-specified parameters. The resulting sample size is linearly dependent on the VC-dimension of a range space associated with the dataset. We analyze the VC-dimension of this range space and show that it is upper bounded by an easy-to-compute characteristic quantity of the dataset, the d-index, namely, the maximum integer d such that the dataset contains at least d transactions of length at least d such that no one of them is a superset of or equal to another. We show that this bound is tight for a large class of datasets. The resulting sample size is a significant improvement over previous known results. We present an extensive experimental evaluation of our technique on real and artificial datasets, demonstrating the practicality of our methods, and showing that they achieve even higher quality approximations than what is guaranteed by the analysis.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {20},
numpages = {32},
keywords = {frequent itemsets, sampling, data mining, VC-dimension, Association rules}
}

@article{10.1145/2629617,
author = {Ordonez, Carlos and Garcia-Alvarado, Carlos and Baladandayuthapani, Veerabhadaran},
title = {Bayesian Variable Selection in Linear Regression in One Pass for Large Datasets},
year = {2014},
issue_date = {October 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2629617},
doi = {10.1145/2629617},
abstract = {Bayesian models are generally computed with Markov Chain Monte Carlo (MCMC) methods. The main disadvantage of MCMC methods is the large number of iterations they need to sample the posterior distributions of model parameters, especially for large datasets. On the other hand, variable selection remains a challenging problem due to its combinatorial search space, where Bayesian models are a promising solution. In this work, we study how to accelerate Bayesian model computation for variable selection in linear regression. We propose a fast Gibbs sampler algorithm, a widely used MCMC method that incorporates several optimizations. We use a Zellner prior for the regression coefficients, an improper prior on variance, and a conjugate prior Gaussian distribution, which enable dataset summarization in one pass, thus exploiting an augmented set of sufficient statistics. Thereafter, the algorithm iterates in main memory. Sufficient statistics are indexed with a sparse binary vector to efficiently compute matrix projections based on selected variables. Discovered variable subsets probabilities, selecting and discarding each variable, are stored on a hash table for fast retrieval in future iterations. We study how to integrate our algorithm into a Database Management System (DBMS), exploiting aggregate User-Defined Functions for parallel data summarization and stored procedures to manipulate matrices with arrays. An experimental evaluation with real datasets evaluates accuracy and time performance, comparing our DBMS-based algorithm with the R package. Our algorithm is shown to produce accurate results, scale linearly on dataset size, and run orders of magnitude faster than the R package.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {3},
numpages = {14},
keywords = {MCMC, Gibbs sampler, on-line algorithm, Sufficient statistics, variable selection}
}

@article{10.1145/2641758,
author = {Hern´ndez-Orallo, Jos\'{e}},
title = {Probabilistic Reframing for Cost-Sensitive Regression},
year = {2014},
issue_date = {October 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2641758},
doi = {10.1145/2641758},
abstract = {Common-day applications of predictive models usually involve the full use of the available contextual information. When the operating context changes, one may fine-tune the by-default (incontextual) prediction or may even abstain from predicting a value (a reject). Global reframing solutions, where the same function is applied to adapt the estimated outputs to a new cost context, are possible solutions here. An alternative approach, which has not been studied in a comprehensive way for regression in the knowledge discovery and data mining literature, is the use of a local (e.g., probabilistic) reframing approach, where decisions are made according to the estimated output and a reliability, confidence, or probability estimation. In this article, we advocate for a simple two-parameter (mean and variance) approach, working with a normal conditional probability density. Given the conditional mean produced by any regression technique, we develop lightweight “enrichment” methods that produce good estimates of the conditional variance, which are used by the probabilistic (local) reframing methods. We apply these methods to some very common families of cost-sensitive problems, such as optimal predictions in (auction) bids, asymmetric loss scenarios, and rejection rules.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {17},
numpages = {55},
keywords = {reliability estimation in regression, asymmetric loss, calibration, conditional density estimation, reframing, Cost-sensitive regression}
}

@article{10.1145/2641761,
author = {Erd\H{o}s, D\'{o}ra and Gemulla, Rainer and Terzi, Evimaria},
title = {Reconstructing Graphs from Neighborhood Data},
year = {2014},
issue_date = {October 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2641761},
doi = {10.1145/2641761},
abstract = {Consider a social network and suppose that we are only given the number of common friends between each pair of users. Can we reconstruct the underlying network? Similarly, consider a set of documents and the words that appear in them. If we only know the number of common words for every pair of documents, as well as the number of common documents for every pair of words, can we infer which words appear in which documents? In this article, we develop a general methodology for answering questions like these.We formalize these questions in what we call the Reconstruct problem: given information about the common neighbors of nodes in a network, our goal is to reconstruct the hidden binary matrix that indicates the presence or absence of relationships between individual nodes. In fact, we propose two different variants of this problem: one where the number of connections of every node (i.e., the degree of every node) is known and a second one where it is unknown. We call these variants the degree-aware and the degree-oblivious versions of the Reconstruct problem, respectively.Our algorithms for both variants exploit the properties of the singular value decomposition of the hidden binary matrix. More specifically, we show that using the available neighborhood information, we can reconstruct the hidden matrix by finding the components of its singular value decomposition and then combining them appropriately. Our extensive experimental study suggests that our methods are able to reconstruct binary matrices of different characteristics with up to 100% accuracy.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {23},
numpages = {22},
keywords = {singular value decomposition, Bipartite graph reconstruction, adjacency matrix}
}

@article{10.1145/2629618,
author = {Boedihardjo, Arnold P. and Lu, Chang-Tien and Wang, Bingsheng},
title = {A Framework for Exploiting Local Information to Enhance Density Estimation of Data Streams},
year = {2014},
issue_date = {October 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2629618},
doi = {10.1145/2629618},
abstract = {The Probability Density Function (PDF) is the fundamental data model for a variety of stream mining algorithms. Existing works apply the standard nonparametric Kernel Density Estimator (KDE) to approximate the PDF of data streams. As a result, the stream-based KDEs cannot accurately capture complex local density features. In this article, we propose the use of Local Region (LRs) to model local density information in univariate data streams. In-depth theoretical analyses are presented to justify the effectiveness of the LR-based KDE. Based on the analyses, we develop the General Local rEgion AlgorithM (GLEAM) to enhance the estimation quality of structurally complex univariate distributions for existing stream-based KDEs. A set of algorithmic optimizations is designed to improve the query throughput of GLEAM and to achieve its linear order computation. Additionally, a comprehensive suite of experiments was conducted to test the effectiveness and efficiency of GLEAM.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {2},
numpages = {38},
keywords = {General Local rEgion AlgorithM (GLEAM), Local region information}
}

@article{10.1145/2601435,
author = {Acharya, Ayan and Hruschka, Eduardo R. and Ghosh, Joydeep and Acharyya, Sreangsu},
title = {An Optimization Framework for Combining Ensembles of Classifiers and Clusterers with Applications to Nontransductive Semisupervised Learning and Transfer Learning},
year = {2014},
issue_date = {October 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2601435},
doi = {10.1145/2601435},
abstract = {Unsupervised models can provide supplementary soft constraints to help classify new “target” data because similar instances in the target set are more likely to share the same class label. Such models can also help detect possible differences between training and target distributions, which is useful in applications where concept drift may take place, as in transfer learning settings. This article describes a general optimization framework that takes as input class membership estimates from existing classifiers learned on previously encountered “source” (or training) data, as well as a similarity matrix from a cluster ensemble operating solely on the target (or test) data to be classified, and yields a consensus labeling of the target data. More precisely, the application settings considered are nontransductive semisupervised and transfer learning scenarios where the training data are used only to build an ensemble of classifiers and are subsequently discarded before classifying the target data. The framework admits a wide range of loss functions and classification/clustering methods. It exploits properties of Bregman divergences in conjunction with Legendre duality to yield a principled and scalable approach. A variety of experiments show that the proposed framework can yield results substantially superior to those provided by na\"{\i}vely applying classifiers learned on the original task to the target data. In addition, we show that the proposed approach, even not being conceptually transductive, can provide better results compared to some popular transductive learning techniques.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {1},
numpages = {35},
keywords = {Classification, semisupervised learning, transductive learning, transfer learning, clustering, ensembles}
}

@article{10.1145/2629616,
author = {Xu, Zhiqiang and Ke, Yiping and Wang, Yi and Cheng, Hong and Cheng, James},
title = {GBAGC: A General Bayesian Framework for Attributed Graph Clustering},
year = {2014},
issue_date = {October 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2629616},
doi = {10.1145/2629616},
abstract = {Graph clustering, also known as community detection, is a long-standing problem in data mining. In recent years, with the proliferation of rich attribute information available for objects in real-world graphs, how to leverage not only structural but also attribute information for clustering attributed graphs becomes a new challenge. Most existing works took a distance-based approach. They proposed various distance measures to fuse structural and attribute information and then applied standard techniques for graph clustering based on these distance measures. In this article, we take an alternative view and propose a novel Bayesian framework for attributed graph clustering. Our framework provides a general and principled solution to modeling both the structural and the attribute aspects of a graph. It avoids the artificial design of a distance measure in existing methods and, furthermore, can seamlessly handle graphs with different types of edges and vertex attributes. We develop an efficient variational method for graph clustering under this framework and derive two concrete algorithms for clustering unweighted and weighted attributed graphs. Experimental results on large real-world datasets show that our algorithms significantly outperform the state-of-the-art distance-based method, in terms of both effectiveness and efficiency.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {5},
numpages = {43},
keywords = {Bayesian method, Attributed graph clustering, model-based clustering}
}

@article{10.1145/2629511,
author = {Coscia, Michele and Rossetti, Giulio and Giannotti, Fosca and Pedreschi, Dino},
title = {Uncovering Hierarchical and Overlapping Communities with a Local-First Approach},
year = {2014},
issue_date = {October 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2629511},
doi = {10.1145/2629511},
abstract = {Community discovery in complex networks is the task of organizing a network’s structure by grouping together nodes related to each other. Traditional approaches are based on the assumption that there is a global-level organization in the network. However, in many scenarios, each node is the bearer of complex information and cannot be classified in disjoint clusters. The top-down global view of the partition approach is not designed for this. Here, we represent this complex information as multiple latent labels, and we postulate that edges in the networks are created among nodes carrying similar labels. The latent labels are the communities a node belongs to and we discover them with a simple local-first approach to community discovery. This is achieved by democratically letting each node vote for the communities it sees surrounding it in its limited view of the global system, its ego neighborhood, using a label propagation algorithm, assuming that each node is aware of the label it shares with each of its connections. The local communities are merged hierarchically, unveiling the modular organization of the network at the global level and identifying overlapping groups and groups of groups. We tested this intuition against the state-of-the-art overlapping community discovery and found that our new method advances in the chosen scenarios in the quality of the obtained communities. We perform a test on benchmark and on real-world networks, evaluating the quality of the community coverage by using the extracted communities to predict the metadata attached to the nodes, which we consider external information about the latent labels. We also provide an explanation about why real-world networks contain overlapping communities and how our logic is able to capture them. Finally, we show how our method is deterministic, is incremental, and has a limited time complexity, so that it can be used on real-world scale networks.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {6},
numpages = {27},
keywords = {community discovery, Complex networks, data mining}
}

@article{10.1145/2629328,
author = {Fei, Hongliang and Huan, Jun},
title = {Structured Sparse Boosting for Graph Classification},
year = {2014},
issue_date = {October 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {9},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2629328},
doi = {10.1145/2629328},
abstract = {Boosting is a highly effective algorithm that produces a linear combination of weak classifiers (a.k.a. base learners) to obtain high-quality classification models. In this article, we propose a generalized logit boost algorithm in which base learners have structural relationships in the functional space. Although such relationships are generic, our work is particularly motivated by the emerging topic of pattern-based classification for semistructured data including graphs. Toward an efficient incorporation of the structure information, we have designed a general model in which we use an undirected graph to capture the relationship of subgraph-based base learners. In our method, we employ both L1 and Laplacian-based L2 regularization to logit boosting to achieve model sparsity and smoothness in the functional space spanned by the base learners. We have derived efficient optimization algorithms based on coordinate descent for the new boosting formulation and theoretically prove that it exhibits a natural grouping effect for nearby spatial or overlapping base learners and that the resulting estimator is consistent. Additionally, motivated by the connection between logit boosting and logistic regression, we extend our structured sparse regularization framework to logistic regression for vectorial data in which features are structured. Using comprehensive experimental study and comparing our work with the state-of-the-art, we have demonstrated the effectiveness of the proposed learning method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {4},
numpages = {22},
keywords = {semistructured data, graph classification, boosting, structural sparsity, Regularization, feature selection, logistic regression}
}

@article{10.1145/2641759,
author = {Burton, Scott H. and Giraud-Carrier, Christophe G.},
title = {Discovering Social Circles in Directed Graphs},
year = {2014},
issue_date = {October 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2641759},
doi = {10.1145/2641759},
abstract = {We examine the problem of identifying social circles, or sets of cohesive and mutually aware nodes surrounding an initial query set, in directed graphs where the complete graph is not known beforehand. This problem differs from local community mining, in that the query set defines the circle of interest. We explicitly handle edge direction, as in many cases relationships are not symmetric, and focus on the local context because many real-world graphs cannot be feasibly known. We outline several issues that are unique to this context, introduce a quality function to measure the value of including a particular node in an emerging social circle, and describe a greedy social circle discovery algorithm. We demonstrate the effectiveness of this approach on artificial benchmarks, large networks with topical community labels, and several real-world case studies.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {21},
numpages = {27},
keywords = {Social circles, local community search, directed graphs}
}

@article{10.1145/2601436,
author = {Ge, Yong and Jiang, Guofei and Ding, Min and Xiong, Hui},
title = {Ranking Metric Anomaly in Invariant Networks},
year = {2014},
issue_date = {June 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2601436},
doi = {10.1145/2601436},
abstract = {The management of large-scale distributed information systems relies on the effective use and modeling of monitoring data collected at various points in the distributed information systems. A traditional approach to model monitoring data is to discover invariant relationships among the monitoring data. Indeed, we can discover all invariant relationships among all pairs of monitoring data and generate invariant networks, where a node is a monitoring data source (metric) and a link indicates an invariant relationship between two monitoring data. Such an invariant network representation can help system experts to localize and diagnose the system faults by examining those broken invariant relationships and their related metrics, since system faults usually propagate among the monitoring data and eventually lead to some broken invariant relationships. However, at one time, there are usually a lot of broken links (invariant relationships) within an invariant network. Without proper guidance, it is difficult for system experts to manually inspect this large number of broken links. To this end, in this article, we propose the problem of ranking metrics according to the anomaly levels for a given invariant network, while this is a nontrivial task due to the uncertainties and the complex nature of invariant networks. Specifically, we propose two types of algorithms for ranking metric anomaly by link analysis in invariant networks. Along this line, we first define two measurements to quantify the anomaly level of each metric, and introduce the mRank algorithm. Also, we provide a weighted score mechanism and develop the gRank algorithm, which involves an iterative process to obtain a score to measure the anomaly levels. In addition, some extended algorithms based on mRank and gRank algorithms are developed by taking into account the probability of being broken as well as noisy links. Finally, we validate all the proposed algorithms on a large number of real-world and synthetic data sets to illustrate the effectiveness and efficiency of different algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {8},
numpages = {30},
keywords = {link analysis, invariant networks, Metric anomaly ranking}
}

@article{10.1145/2611520,
author = {Shabtai, Asaf and Bercovitch, Maya and Rokach, Lior and Elovici, Yuval},
title = {Optimizing Data Misuse Detection},
year = {2014},
issue_date = {June 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2611520},
doi = {10.1145/2611520},
abstract = {Data misuse may be performed by entities such as an organization's employees and business partners who are granted access to sensitive information and misuse their privileges. We assume that users can be either trusted or untrusted. The access of untrusted parties to data objects (e.g., client and patient records) should be monitored in an attempt to detect misuse. However, monitoring data objects is resource intensive and time-consuming and may also cause disturbance or inconvenience to the involved employees. Therefore, the monitored data objects should be carefully selected. In this article, we present two optimization problems carefully designed for selecting specific data objects for monitoring, such that the detection rate is maximized and the monitoring effort is minimized. In the first optimization problem, the goal is to select data objects for monitoring that are accessed by at most c trusted agents while ensuring access to at least k monitored objects by each untrusted agent (both c and k are integer variable). As opposed to the first optimization problem, the goal of the second optimization problem is to select monitored data objects that maximize the number of monitored data objects accessed by untrusted agents while ensuring that each trusted agent does not access more than d monitored data objects (d is an integer variable as well). Two efficient heuristic algorithms for solving these optimization problems are proposed, and experiments were conducted simulating different scenarios to evaluate the algorithms’ performance. Moreover, we compared the heuristic algorithms’ performance to the optimal solution and conducted sensitivity analysis on the three parameters (c, k, and d) and on the ratio between the trusted and untrusted agents.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {16},
numpages = {23},
keywords = {Data misuse, honeytokens, data monitoring, information security}
}

@article{10.1145/2611378,
author = {Lin, Ming and Weng, Shifeng and Zhang, Changshui},
title = {On the Sample Complexity of Random Fourier Features for Online Learning: How Many Random Fourier Features Do We Need?},
year = {2014},
issue_date = {June 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2611378},
doi = {10.1145/2611378},
abstract = {We study the sample complexity of random Fourier features for online kernel learning—that is, the number of random Fourier features required to achieve good generalization performance. We show that when the loss function is strongly convex and smooth, online kernel learning with random Fourier features can achieve an O(log T /T) bound for the excess risk with only O(1/λ2) random Fourier features, where T is the number of training examples and λ is the modulus of strong convexity. This is a significant improvement compared to the existing result for batch kernel learning that requires O(T) random Fourier features to achieve a generalization bound O(1/√T). Our empirical study verifies that online kernel learning with a limited number of random Fourier features can achieve similar generalization performance as online learning using full kernel matrix. We also present an enhanced online learning algorithm with random Fourier features that improves the classification performance by multiple passes of training examples and a partial average.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {13},
numpages = {19},
keywords = {Nystr\"{o}m, kernel learning, sampling complexity}
}

@article{10.1145/2538028,
author = {Zhang, Yu and Yeung, Dit-Yan},
title = {A Regularization Approach to Learning Task Relationships in Multitask Learning},
year = {2014},
issue_date = {June 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2538028},
doi = {10.1145/2538028},
abstract = {Multitask learning is a learning paradigm that seeks to improve the generalization performance of a learning task with the help of some other related tasks. In this article, we propose a regularization approach to learning the relationships between tasks in multitask learning. This approach can be viewed as a novel generalization of the regularized formulation for single-task learning. Besides modeling positive task correlation, our approach—multitask relationship learning (MTRL)—can also describe negative task correlation and identify outlier tasks based on the same underlying principle. By utilizing a matrix-variate normal distribution as a prior on the model parameters of all tasks, our MTRL method has a jointly convex objective function. For efficiency, we use an alternating method to learn the optimal model parameters for each task as well as the relationships between tasks. We study MTRL in the symmetric multitask learning setting and then generalize it to the asymmetric setting as well. We also discuss some variants of the regularization approach to demonstrate the use of other matrix-variate priors for learning task relationships. Moreover, to gain more insight into our model, we also study the relationships between MTRL and some existing multitask learning methods. Experiments conducted on a toy problem as well as several benchmark datasets demonstrate the effectiveness of MTRL as well as its high interpretability revealed by the task covariance matrix.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {12},
numpages = {31},
keywords = {Multitask learning, task relationship, regularization framework}
}

@article{10.1145/2601434,
author = {Huang, Jin and Nie, Feiping and Huang, Heng and Ding, Chris},
title = {Robust Manifold Nonnegative Matrix Factorization},
year = {2014},
issue_date = {June 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2601434},
doi = {10.1145/2601434},
abstract = {Nonnegative Matrix Factorization (NMF) has been one of the most widely used clustering techniques for exploratory data analysis. However, since each data point enters the objective function with squared residue error, a few outliers with large errors easily dominate the objective function. In this article, we propose a Robust Manifold Nonnegative Matrix Factorization (RMNMF) method using ℓ2,1-norm and integrating NMF and spectral clustering under the same clustering framework. We also point out the solution uniqueness issue for the existing NMF methods and propose an additional orthonormal constraint to address this problem. With the new constraint, the conventional auxiliary function approach no longer works. We tackle this difficult optimization problem via a novel Augmented Lagrangian Method (ALM)--based algorithm and convert the original constrained optimization problem on one variable into a multivariate constrained problem. The new objective function then can be decomposed into several subproblems that each has a closed-form solution. More importantly, we reveal the connection of our method with robust K-means and spectral clustering, and we demonstrate its theoretical significance. Extensive experiments have been conducted on nine benchmark datasets, and all empirical results show the effectiveness of our method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {11},
numpages = {21},
keywords = {robust NMF, nonnegative matrix factorization (NMF), manifold, Clustering}
}

@article{10.1145/2532169,
author = {Schifanella, Claudio and Candan, K. Sel\c{c}uk and Sapino, Maria Luisa},
title = {Multiresolution Tensor Decompositions with Mode Hierarchies},
year = {2014},
issue_date = {June 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2532169},
doi = {10.1145/2532169},
abstract = {Tensors (multidimensional arrays) are widely used for representing high-order dimensional data, in applications ranging from social networks, sensor data, and Internet traffic. Multiway data analysis techniques, in particular tensor decompositions, allow extraction of hidden correlations among multiway data and thus are key components of many data analysis frameworks. Intuitively, these algorithms can be thought of as multiway clustering schemes, which consider multiple facets of the data in identifying clusters, their weights, and contributions of each data element. Unfortunately, algorithms for fitting multiway models are, in general, iterative and very time consuming. In this article, we observe that, in many applications, there is a priori background knowledge (or metadata) about one or more domain dimensions. This metadata is often in the form of a hierarchy that clusters the elements of a given data facet (or mode). We investigate whether such single-mode data hierarchies can be used to boost the efficiency of tensor decomposition process, without significant impact on the final decomposition quality. We consider each domain hierarchy as a guide to help provide higher- or lower-resolution views of the data in the tensor on demand and we rely on these metadata-induced multiresolution tensor representations to develop a multiresolution approach to tensor decomposition. In this article, we focus on an alternating least squares (ALS)--based implementation of the two most important decomposition models such as the PARAllel FACtors (PARAFAC, which decomposes a tensor into a diagonal tensor and a set of factor matrices) and the Tucker (which produces as result a core tensor and a set of dimension-subspaces matrices). Experiment results show that, when the available metadata is used as a rough guide, the proposed multiresolution method helps fit both PARAFAC and Tucker models with consistent (under different parameters settings) savings in execution time and memory consumption, while preserving the quality of the decomposition.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {10},
numpages = {38},
keywords = {Tucker, multiresolution, PARAFAC, Tensor decomposition}
}

@article{10.1145/2601439,
author = {Zhang, Gensheng and Jiang, Xiao and Luo, Ping and Wang, Min and Li, Chengkai},
title = {Discovering General Prominent Streaks in Sequence Data},
year = {2014},
issue_date = {June 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2601439},
doi = {10.1145/2601439},
abstract = {This article studies the problem of prominent streak discovery in sequence data. Given a sequence of values, a prominent streak is a long consecutive subsequence consisting of only large (small) values, such as consecutive games of outstanding performance in sports, consecutive hours of heavy network traffic, and consecutive days of frequent mentioning of a person in social media. Prominent streak discovery provides insightful data patterns for data analysis in many real-world applications and is an enabling technique for computational journalism. Given its real-world usefulness and complexity, the research on prominent streaks in sequence data opens a spectrum of challenging problems.A baseline approach to finding prominent streaks is a quadratic algorithm that exhaustively enumerates all possible streaks and performs pairwise streak dominance comparison. For more efficient methods, we make the observation that prominent streaks are in fact skyline points in two dimensions—streak interval length and minimum value in the interval. Our solution thus hinges on the idea to separate the two steps in prominent streak discovery: candidate streak generation and skyline operation over candidate streaks. For candidate generation, we propose the concept of local prominent streak (LPS). We prove that prominent streaks are a subset of LPSs and the number of LPSs is less than the length of a data sequence, in comparison with the quadratic number of candidates produced by the brute-force baseline method. We develop efficient algorithms based on the concept of LPS. The nonlinear local prominent streak (NLPS)-based method considers a superset of LPSs as candidates, and the linear local prominent streak (LLPS)-based method further guarantees to consider only LPSs. The proposed properties and algorithms are also extended for discovering general top-k, multisequence, and multidimensional prominent streaks. The results of experiments using multiple real datasets verified the effectiveness of the proposed methods and showed orders of magnitude performance improvement against the baseline method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {9},
numpages = {37},
keywords = {time series database, Computational journalism, skyline query, sequence database}
}

@article{10.1145/2556608,
author = {Chen, Wei and Tang, Jie},
title = {Introduction to Special Issue on Computational Aspects of Social and Information Networks: Theory, Methodologies, and Applications (TKDD-CASIN)},
year = {2014},
issue_date = {February 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2556608},
doi = {10.1145/2556608},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {1},
numpages = {2}
}

@article{10.1145/2556612,
author = {Mcauley, Julian and Leskovec, Jure},
title = {Discovering Social Circles in Ego Networks},
year = {2014},
issue_date = {February 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2556612},
doi = {10.1145/2556612},
abstract = {People's personal social networks are big and cluttered, and currently there is no good way to automatically organize them. Social networking sites allow users to manually categorize their friends into social circles (e.g., “circles” on Google+, and “lists” on Facebook and Twitter). However, circles are laborious to construct and must be manually updated whenever a user's network grows. In this article, we study the novel task of automatically identifying users' social circles. We pose this task as a multimembership node clustering problem on a user's ego network, a network of connections between her friends. We develop a model for detecting circles that combines network structure as well as user profile information. For each circle, we learn its members and the circle-specific user profile similarity metric. Modeling node membership to multiple circles allows us to detect overlapping as well as hierarchically nested circles. Experiments show that our model accurately identifies circles on a diverse set of data from Facebook, Google+, and Twitter, for all of which we obtain hand-labeled ground truth.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {4},
numpages = {28},
keywords = {machine learning, Community detection, social circles, ego networks}
}

@article{10.1145/2518176,
author = {Jin, Ruoming and Lee, Victor E. and Li, Longjie},
title = {Scalable and Axiomatic Ranking of Network Role Similarity},
year = {2014},
issue_date = {February 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2518176},
doi = {10.1145/2518176},
abstract = {A key task in analyzing social networks and other complex networks is role analysis: describing and categorizing nodes according to how they interact with other nodes. Two nodes have the same role if they interact with equivalent sets of neighbors. The most fundamental role equivalence is automorphic equivalence. Unfortunately, the fastest algorithms known for graph automorphism are nonpolynomial. Moreover, since exact equivalence is rare, a more meaningful task is measuring the role similarity between any two nodes. This task is closely related to the structural or link-based similarity problem that SimRank addresses. However, SimRank and other existing similarity measures are not sufficient because they do not guarantee to recognize automorphically or structurally equivalent nodes. This article makes two contributions. First, we present and justify several axiomatic properties necessary for a role similarity measure or metric. Second, we present RoleSim, a new similarity metric that satisfies these axioms and can be computed with a simple iterative algorithm. We rigorously prove that RoleSim satisfies all of these axiomatic properties. We also introduce Iceberg RoleSim, a scalable algorithm that discovers all pairs with RoleSim scores above a user-defined threshold θ. We demonstrate the interpretative power of RoleSim on both both synthetic and real datasets.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {3},
numpages = {37},
keywords = {vertex similarity, Complex network, ranking, social network, automorphic equivalence, role similarity}
}

@article{10.1145/2556613,
author = {Zhong, Erheng and Fan, Wei and Yang, Qiang},
title = {User Behavior Learning and Transfer in Composite Social Networks},
year = {2014},
issue_date = {February 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2556613},
doi = {10.1145/2556613},
abstract = {Accurate prediction of user behaviors is important for many social media applications, including social marketing, personalization, and recommendation. A major challenge lies in that although many previous works model user behavior from only historical behavior logs, the available user behavior data or interactions between users and items in a given social network are usually very limited and sparse (e.g., ⩾ 99.9% empty), which makes models overfit the rare observations and fail to provide accurate predictions. We observe that many people are members of several social networks in the same time, such as Facebook, Twitter, and Tencent’s QQ. Importantly, users’ behaviors and interests in different networks influence one another. This provides an opportunity to leverage the knowledge of user behaviors in different networks by considering the overlapping users in different networks as bridges, in order to alleviate the data sparsity problem, and enhance the predictive performance of user behavior modeling. Combining different networks “simply and naively” does not work well. In this article, we formulate the problem to model multiple networks as “adaptive composite transfer” and propose a framework called ComSoc. ComSoc first selects the most suitable networks inside a composite social network via a hierarchical Bayesian model, parameterized for individual users. It then builds topic models for user behavior prediction using both the relationships in the selected networks and related behavior data. With different relational regularization, we introduce different implementations, corresponding to different ways to transfer knowledge from composite social relations. To handle big data, we have implemented the algorithm using Map/Reduce. We demonstrate that the proposed composite network-based user behavior models significantly improve the predictive accuracy over a number of existing approaches on several real-world applications, including a very large social networking dataset from Tencent Inc.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {6},
numpages = {32},
keywords = {social network analysis, transfer learning, Composite social network}
}

@article{10.1145/2556609,
author = {Yang, Zhi and Wilson, Christo and Wang, Xiao and Gao, Tingting and Zhao, Ben Y. and Dai, Yafei},
title = {Uncovering Social Network Sybils in the Wild},
year = {2014},
issue_date = {February 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2556609},
doi = {10.1145/2556609},
abstract = {Sybil accounts are fake identities created to unfairly increase the power or resources of a single malicious user. Researchers have long known about the existence of Sybil accounts in online communities such as file-sharing systems, but they have not been able to perform large-scale measurements to detect them or measure their activities. In this article, we describe our efforts to detect, characterize, and understand Sybil account activity in the Renren Online Social Network (OSN). We use ground truth provided by Renren Inc. to build measurement-based Sybil detectors and deploy them on Renren to detect more than 100,000 Sybil accounts. Using our full dataset of 650,000 Sybils, we examine several aspects of Sybil behavior. First, we study their link creation behavior and find that contrary to prior conjecture, Sybils in OSNs do not form tight-knit communities. Next, we examine the fine-grained behaviors of Sybils on Renren using clickstream data. Third, we investigate behind-the-scenes collusion between large groups of Sybils. Our results reveal that Sybils with no explicit social ties still act in concert to launch attacks. Finally, we investigate enhanced techniques to identify stealthy Sybils. In summary, our study advances the understanding of Sybil behavior on OSNs and shows that Sybils can effectively avoid existing community-based Sybil detectors. We hope that our results will foster new research on Sybil detection that is based on novel types of Sybil features.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {2},
numpages = {29},
keywords = {spam, Online social networks, measurement, Sybil attacks, user behavior}
}

@article{10.1145/2527231,
author = {Abrahao, Bruno and Soundarajan, Sucheta and Hopcroft, John and Kleinberg, Robert},
title = {A Separability Framework for Analyzing Community Structure},
year = {2014},
issue_date = {February 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2527231},
doi = {10.1145/2527231},
abstract = {Four major factors govern the intricacies of community extraction in networks: (1) the literature offers a multitude of disparate community detection algorithms whose output exhibits high structural variability across the collection, (2) communities identified by algorithms may differ structurally from real communities that arise in practice, (3) there is no consensus characterizing how to discriminate communities from noncommunities, and (4) the application domain includes a wide variety of networks of fundamentally different natures. In this article, we present a class separability framework to tackle these challenges through a comprehensive analysis of community properties. Our approach enables the assessment of the structural dissimilarity among the output of multiple community detection algorithms and between the output of algorithms and communities that arise in practice. In addition, our method provides us with a way to organize the vast collection of community detection algorithms by grouping those that behave similarly. Finally, we identify the most discriminative graph-theoretical properties of community signature and the small subset of properties that account for most of the biases of the different community detection algorithms. We illustrate our approach with an experimental analysis, which reveals nuances of the structure of real and extracted communities. In our experiments, we furnish our framework with the output of 10 different community detection procedures, representative of categories of popular algorithms available in the literature, applied to a diverse collection of large-scale real network datasets whose domains span biology, online shopping, and social systems. We also analyze communities identified by annotations that accompany the data, which reflect exemplar communities in various domain. We characterize these communities using a broad spectrum of community properties to produce the different structural classes. As our experiments show that community structure is not a universal concept, our framework enables an informed choice of the most suitable community detection method for identifying communities of a specific type in a given network and allows for a comparison of existing community detection algorithms while guiding the design of new ones.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {5},
numpages = {29},
keywords = {detection algorithms, Class separability, community structure, networks}
}

@article{10.1145/2541268.2541270,
author = {Huang, Jin and Nie, Feiping and Huang, Heng and Tu, Yi-Cheng and Lei, Yu},
title = {Social Trust Prediction Using Heterogeneous Networks},
year = {2013},
issue_date = {November 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2541268.2541270},
doi = {10.1145/2541268.2541270},
abstract = {Along with increasing popularity of social websites, online users rely more on the trustworthiness information to make decisions, extract and filter information, and tag and build connections with other users. However, such social network data often suffer from severe data sparsity and are not able to provide users with enough information. Therefore, trust prediction has emerged as an important topic in social network research. Traditional approaches are primarily based on exploring trust graph topology itself. However, research in sociology and our life experience suggest that people who are in the same social circle often exhibit similar behaviors and tastes. To take advantage of the ancillary information for trust prediction, the challenge then becomes what to transfer and how to transfer. In this article, we address this problem by aggregating heterogeneous social networks and propose a novel joint social networks mining (JSNM) method. Our new joint learning model explores the user-group-level similarity between correlated graphs and simultaneously learns the individual graph structure; therefore, the shared structures and patterns from multiple social networks can be utilized to enhance the prediction tasks. As a result, we not only improve the trust prediction in the target graph but also facilitate other information retrieval tasks in the auxiliary graphs. To optimize the proposed objective function, we use the alternative technique to break down the objective function into several manageable subproblems. We further introduce the auxiliary function to solve the optimization problems with rigorously proved convergence. The extensive experiments have been conducted on both synthetic and real- world data. All empirical results demonstrate the effectiveness of our method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {17},
numpages = {21},
keywords = {nonnegative matrix factorization, social network, Trust prediction, transfer learning}
}

@article{10.1145/2541268.2541273,
author = {Ang, Hock Hee and Gopalkrishnan, Vivekanand and Hoi, Steven C. H. and Ng, Wee Keong},
title = {Classification in P2P Networks with Cascade Support Vector Machines},
year = {2013},
issue_date = {November 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2541268.2541273},
doi = {10.1145/2541268.2541273},
abstract = {Classification in Peer-to-Peer (P2P) networks is important to many real applications, such as distributed intrusion detection, distributed recommendation systems, and distributed antispam detection. However, it is very challenging to perform classification in P2P networks due to many practical issues, such as scalability, peer dynamism, and asynchronism. This article investigates the practical techniques of constructing Support Vector Machine (SVM) classifiers in the P2P networks. In particular, we demonstrate how to efficiently cascade SVM in a P2P network with the use of reduced SVM. In addition, we propose to fuse the concept of cascade SVM with bootstrap aggregation to effectively balance the trade-off between classification accuracy, model construction, and prediction cost. We provide theoretical insights for the proposed solutions and conduct an extensive set of empirical studies on a number of large-scale datasets. Encouraging results validate the efficacy of the proposed approach.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {20},
numpages = {29},
keywords = {distributed classification, cascade SVM, bootstrap aggregation, P2P networks}
}

@article{10.1145/2541268.2541272,
author = {Balc\'{a}zar, Jos\'{e} L.},
title = {Formal and Computational Properties of the Confidence Boost of Association Rules},
year = {2013},
issue_date = {November 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2541268.2541272},
doi = {10.1145/2541268.2541272},
abstract = {Some existing notions of redundancy among association rules allow for a logical-style characterization and lead to irredundant bases of absolutely minimum size. We push the intuition of redundancy further to find an intuitive notion of novelty of an association rule, with respect to other rules. Namely, an irredundant rule is so because its confidence is higher than what the rest of the rules would suggest; then, one can ask: how much higher?We propose to measure such a sort of novelty through the confidence boost of a rule. Acting as a complement to confidence and support, the confidence boost helps to obtain small and crisp sets of mined association rules and solves the well-known problem that, in certain cases, rules of negative correlation may pass the confidence bound. We analyze the properties of two versions of the notion of confidence boost, one of them a natural generalization of the other. We develop algorithms to filter rules according to their confidence boost, compare the concept to some similar notions in the literature, and describe the results of some experimentation employing the new notions on standard benchmark datasets. We describe an open source association mining tool that embodies one of our variants of confidence boost in such a way that the data mining process does not require the user to select any value for any parameter.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {19},
numpages = {41},
keywords = {Association rule mining, confidence, association rule quality}
}

@article{10.1145/2541268.2541271,
author = {Guzzo, Antonella and Moccia, Luigi and Sacc\`{a}, Domenico and Serra, Edoardo},
title = {Solving Inverse Frequent Itemset Mining with Infrequency Constraints via Large-Scale Linear Programs},
year = {2013},
issue_date = {November 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2541268.2541271},
doi = {10.1145/2541268.2541271},
abstract = {Inverse frequent set mining (IFM) is the problem of computing a transaction database D satisfying given support constraints for some itemsets, which are typically the frequent ones. This article proposes a new formulation of IFM, called IFMI (IFM with infrequency constraints), where the itemsets that are not listed as frequent are constrained to be infrequent; that is, they must have a support less than or equal to a specified unique threshold. An instance of IFMI can be seen as an instance of the original IFM by making explicit the infrequency constraints for the minimal infrequent itemsets, corresponding to the so-called negative generator border defined in the literature. The complexity increase from PSPACE (complexity of IFM) to NEXP (complexity of IFMI) is caused by the cardinality of the negative generator border, which can be exponential in the original input size. Therefore, the article introduces a specific problem parameter κ that computes an upper bound to this cardinality using a hypergraph interpretation for which minimal infrequent itemsets correspond to minimal transversals. By fixing a constant k, the article formulates a k-bounded definition of the problem, called k-IFMI, that collects all instances for which the value of the parameter κ is less than or equal to k—its complexity is in PSPACE as for IFM. The bounded problem is encoded as an integer linear program with a large number of variables (actually exponential w.r.t. the number of constraints), which is thereafter approximated by relaxing integer constraints—the decision problem of solving the linear program is proven to be in NP. In order to solve the linear program, a column generation technique is used that is a variation of the simplex method designed to solve large-scale linear programs, in particular with a huge number of variables. The method at each step requires the solution of an auxiliary integer linear program, which is proven to be NP hard in this case and for which a greedy heuristic is presented. The resulting overall column generation solution algorithm enjoys very good scaling as evidenced by the intensive experimentation, thereby paving the way for its application in real-life scenarios.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {18},
numpages = {39},
keywords = {inverse problem, column generation simplex, minimal hypergraph transversals, Frequent itemset mining}
}

@article{10.1145/2541268.2541269,
author = {Adali, Sibel and Magdon-Ismail, Malik and Lu, Xiaohui},
title = {IHypR: Prominence Ranking in Networks of Collaborations with Hyperedges<sup>1</sup>},
year = {2013},
issue_date = {November 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2541268.2541269},
doi = {10.1145/2541268.2541269},
abstract = {We present a new algorithm called iHypR for computing prominence of actors in social networks of collaborations. Our algorithm builds on the assumption that prominent actors collaborate on prominent objects, and prominent objects are naturally grouped into prominent clusters or groups (hyperedges in a graph). iHypR makes use of the relationships between actors, objects, and hyperedges to compute a global prominence score for the actors in the network. We do not assume the hyperedges are given in advance. Hyperedges computed by our method can perform as well or even better than “true” hyperedges. Our algorithm is customized for networks of collaborations, but it is generally applicable without further tuning. We show, through extensive experimentation with three real-life data sets and multiple external measures of prominence, that our algorithm outperforms existing well-known algorithms. Our work is the first to offer such an extensive evaluation. We show that unlike most existing algorithms, the performance is robust across multiple measures of performance. Further, we give a detailed study of the sensitivity of our algorithm to different data sets and the design choices within the algorithm that a user may wish to change. Our article illustrates the various trade-offs that must be considered in computing prominence in collaborative social networks.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {16},
numpages = {32},
keywords = {social networks, Prominence, collaboration}
}

@article{10.1145/2513092.2513093,
author = {Agarwal, Deepak and Caruana, Rich and Pei, Jian and Wang, Ke},
title = {Introduction to the Special Issue ACM SIGKDD 2012},
year = {2013},
issue_date = {September 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2513092.2513093},
doi = {10.1145/2513092.2513093},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {9},
numpages = {2}
}

@article{10.1145/2500492,
author = {Sun, Yizhou and Norick, Brandon and Han, Jiawei and Yan, Xifeng and Yu, Philip S. and Yu, Xiao},
title = {PathSelClus: Integrating Meta-Path Selection with User-Guided Object Clustering in Heterogeneous Information Networks},
year = {2013},
issue_date = {September 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2500492},
doi = {10.1145/2500492},
abstract = {Real-world, multiple-typed objects are often interconnected, forming heterogeneous information networks. A major challenge for link-based clustering in such networks is their potential to generate many different results, carrying rather diverse semantic meanings. In order to generate desired clustering, we propose to use meta-path, a path that connects object types via a sequence of relations, to control clustering with distinct semantics. Nevertheless, it is easier for a user to provide a few examples (seeds) than a weighted combination of sophisticated meta-paths to specify her clustering preference. Thus, we propose to integrate meta-path selection with user-guided clustering to cluster objects in networks, where a user first provides a small set of object seeds for each cluster as guidance. Then the system learns the weight for each meta-path that is consistent with the clustering result implied by the guidance, and generates clusters under the learned weights of meta-paths. A probabilistic approach is proposed to solve the problem, and an effective and efficient iterative algorithm, PathSelClus, is proposed to learn the model, where the clustering quality and the meta-path weights mutually enhance each other. Our experiments with several clustering tasks in two real networks and one synthetic network demonstrate the power of the algorithm in comparison with the baselines.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {11},
numpages = {23},
keywords = {Heterogeneous information networks, user-guided clustering, meta-path selection}
}

@article{10.1145/2513092.2513096,
author = {Ji, Ming and Lin, Binbin and He, Xiaofei and Cai, Deng and Han, Jiawei},
title = {Parallel Field Ranking},
year = {2013},
issue_date = {September 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2513092.2513096},
doi = {10.1145/2513092.2513096},
abstract = {Recently, ranking data with respect to the intrinsic geometric structure (manifold ranking) has received considerable attentions, with encouraging performance in many applications in pattern recognition, information retrieval and recommendation systems. Most of the existing manifold ranking methods focus on learning a ranking function that varies smoothly along the data manifold. However, beyond smoothness, a desirable ranking function should vary monotonically along the geodesics of the data manifold, such that the ranking order along the geodesics is preserved. In this article, we aim to learn a ranking function that varies linearly and therefore monotonically along the geodesics of the data manifold. Recent theoretical work shows that the gradient field of a linear function on the manifold has to be a parallel vector field. Therefore, we propose a novel ranking algorithm on the data manifolds, called Parallel Field Ranking. Specifically, we try to learn a ranking function and a vector field simultaneously. We require the vector field to be close to the gradient field of the ranking function, and the vector field to be as parallel as possible. Moreover, we require the value of the ranking function at the query point to be the highest, and then decrease linearly along the manifold. Experimental results on both synthetic data and real data demonstrate the effectiveness of our proposed algorithm.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {15},
numpages = {21},
keywords = {Manifold, vector field, ranking}
}

@article{10.1145/2500491,
author = {Briggs, Forrest and Fern, Xiaoli Z. and Raich, Raviv and Lou, Qi},
title = {Instance Annotation for Multi-Instance Multi-Label Learning},
year = {2013},
issue_date = {September 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2500491},
doi = {10.1145/2500491},
abstract = {Multi-instance multi-label learning (MIML) is a framework for supervised classification where the objects to be classified are bags of instances associated with multiple labels. For example, an image can be represented as a bag of segments and associated with a list of objects it contains. Prior work on MIML has focused on predicting label sets for previously unseen bags. We instead consider the problem of predicting instance labels while learning from data labeled only at the bag level. We propose a regularized rank-loss objective designed for instance annotation, which can be instantiated with different aggregation models connecting instance-level labels with bag-level label sets. The aggregation models that we consider can be factored as a linear function of a “support instance” for each class, which is a single feature vector representing a whole bag. Hence we name our proposed methods rank-loss Support Instance Machines (SIM). We propose two optimization methods for the rank-loss objective, which is nonconvex. One is a heuristic method that alternates between updating support instances, and solving a convex problem in which the support instances are treated as constant. The other is to apply the constrained concave-convex procedure (CCCP), which can also be interpreted as iteratively updating support instances and solving a convex problem. To solve the convex problem, we employ the Pegasos framework of primal subgradient descent, and prove that it finds an ϵ-suboptimal solution in runtime that is linear in the number of bags, instances, and 1/ϵ. Additionally, we suggest a method of extending the linear learning algorithm to nonlinear classification, without increasing the runtime asymptotically. Experiments on artificial and real-world datasets including images and audio show that the proposed methods achieve higher accuracy than other loss functions used in prior work, e.g., Hamming loss, and recent work in ambiguous label classification.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {14},
numpages = {30},
keywords = {subgradient, image annotation, Instance annotation, multi-label, support vector machine, multi-instance, bioacoustics}
}

@article{10.1145/2513092.2513094,
author = {Chattopadhyay, Rita and Wang, Zheng and Fan, Wei and Davidson, Ian and Panchanathan, Sethuraman and Ye, Jieping},
title = {Batch Mode Active Sampling Based on Marginal Probability Distribution Matching},
year = {2013},
issue_date = {September 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2513092.2513094},
doi = {10.1145/2513092.2513094},
abstract = {Active Learning is a machine learning and data mining technique that selects the most informative samples for labeling and uses them as training data; it is especially useful when there are large amount of unlabeled data and labeling them is expensive. Recently, batch-mode active learning, where a set of samples are selected concurrently for labeling, based on their collective merit, has attracted a lot of attention. The objective of batch-mode active learning is to select a set of informative samples so that a classifier learned on these samples has good generalization performance on the unlabeled data. Most of the existing batch-mode active learning methodologies try to achieve this by selecting samples based on certain criteria. In this article we propose a novel criterion which achieves good generalization performance of a classifier by specifically selecting a set of query samples that minimize the difference in distribution between the labeled and the unlabeled data, after annotation. We explicitly measure this difference based on all candidate subsets of the unlabeled data and select the best subset. The proposed objective is an NP-hard integer programming optimization problem. We provide two optimization techniques to solve this problem. In the first one, the problem is transformed into a convex quadratic programming problem and in the second method the problem is transformed into a linear programming problem. Our empirical studies using publicly available UCI datasets and two biomedical image databases demonstrate the effectiveness of the proposed approach in comparison with the state-of-the-art batch-mode active learning methods. We also present two extensions of the proposed approach, which incorporate uncertainty of the predicted labels of the unlabeled data and transfer learning in the proposed formulation. In addition, we present a joint optimization framework for performing both transfer and active learning simultaneously unlike the existing approaches of learning in two separate stages, that is, typically, transfer learning followed by active learning. We specifically minimize a common objective of reducing distribution difference between the domain adapted source, the queried and labeled samples and the rest of the unlabeled target domain data. Our empirical studies on two biomedical image databases and on a publicly available 20 Newsgroups dataset show that incorporation of uncertainty information and transfer learning further improves the performance of the proposed active learning based classifier. Our empirical studies also show that the proposed transfer-active method based on the joint optimization framework performs significantly better than a framework which implements transfer and active learning in two separate stages.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {13},
numpages = {25},
keywords = {marginal probability distribution, maximum mean discrepancy, Active learning, transfer learning}
}

@article{10.1145/2500490,
author = {Bellare, Kedar and Iyengar, Suresh and Parameswaran, Aditya and Rastogi, Vibhor},
title = {Active Sampling for Entity Matching with Guarantees},
year = {2013},
issue_date = {September 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2500490},
doi = {10.1145/2500490},
abstract = {In entity matching, a fundamental issue while training a classifier to label pairs of entities as either duplicates or nonduplicates is the one of selecting informative training examples. Although active learning presents an attractive solution to this problem, previous approaches minimize the misclassification rate (0--1 loss) of the classifier, which is an unsuitable metric for entity matching due to class imbalance (i.e., many more nonduplicate pairs than duplicate pairs). To address this, a recent paper [Arasu et al. 2010] proposes to maximize recall of the classifier under the constraint that its precision should be greater than a specified threshold. However, the proposed technique requires the labels of all n input pairs in the worst case.Our main result is an active learning algorithm that approximately maximizes recall of the classifier while respecting a precision constraint with provably sublinear label complexity (under certain distributional assumptions). Our algorithm uses as a black box any active learning module that minimizes 0--1 loss. We show that label complexity of our algorithm is at most log n times the label complexity of the black box, and also bound the difference in the recall of classifier learnt by our algorithm and the recall of the optimal classifier satisfying the precision constraint. We provide an empirical evaluation of our algorithm on several real-world matching data sets that demonstrates the effectiveness of our approach.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {12},
numpages = {24},
keywords = {deduplication, Entity matching, active learning, imbalanced data}
}

@article{10.1145/2500489,
author = {Rakthanmanon, Thanawin and Campana, Bilson and Mueen, Abdullah and Batista, Gustavo and Westover, Brandon and Zhu, Qiang and Zakaria, Jesin and Keogh, Eamonn},
title = {Addressing Big Data Time Series: Mining Trillions of Time Series Subsequences Under Dynamic Time Warping},
year = {2013},
issue_date = {September 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2500489},
doi = {10.1145/2500489},
abstract = {Most time series data mining algorithms use similarity search as a core subroutine, and thus the time taken for similarity search is the bottleneck for virtually all time series data mining algorithms, including classification, clustering, motif discovery, anomaly detection, and so on. The difficulty of scaling a search to large datasets explains to a great extent why most academic work on time series data mining has plateaued at considering a few millions of time series objects, while much of industry and science sits on billions of time series objects waiting to be explored. In this work we show that by using a combination of four novel ideas we can search and mine massive time series for the first time. We demonstrate the following unintuitive fact: in large datasets we can exactly search under Dynamic Time Warping (DTW) much more quickly than the current state-of-the-art Euclidean distance search algorithms. We demonstrate our work on the largest set of time series experiments ever attempted. In particular, the largest dataset we consider is larger than the combined size of all of the time series datasets considered in all data mining papers ever published. We explain how our ideas allow us to solve higher-level time series data mining problems such as motif discovery and clustering at scales that would otherwise be untenable. Moreover, we show how our ideas allow us to efficiently support the uniform scaling distance measure, a measure whose utility seems to be underappreciated, but which we demonstrate here. In addition to mining massive datasets with up to one trillion datapoints, we will show that our ideas also have implications for real-time monitoring of data streams, allowing us to handle much faster arrival rates and/or use cheaper and lower powered devices than are currently possible.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {10},
numpages = {31},
keywords = {similarity search, lower bounds, Time series}
}

@article{10.1145/2499907.2499911,
author = {Peng, Jing and Seetharaman, Guna and Fan, Wei and Varde, Aparna},
title = {Exploiting Fisher and Fukunaga-Koontz Transforms in Chernoff Dimensionality Reduction},
year = {2013},
issue_date = {July 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2499907.2499911},
doi = {10.1145/2499907.2499911},
abstract = {Knowledge discovery from big data demands effective representation of data. However, big data are often characterized by high dimensionality, which makes knowledge discovery more difficult. Many techniques for dimensionality reudction have been proposed, including well-known Fisher's Linear Discriminant Analysis (LDA). However, the Fisher criterion is incapable of dealing with heteroscedasticity in the data. A technique based on the Chernoff criterion for linear dimensionality reduction has been proposed that is capable of exploiting heteroscedastic information in the data. While the Chernoff criterion has been shown to outperform the Fisher's, a clear understanding of its exact behavior is lacking. In this article, we show precisely what can be expected from the Chernoff criterion. In particular, we show that the Chernoff criterion exploits the Fisher and Fukunaga-Koontz transforms in computing its linear discriminants. Furthermore, we show that a recently proposed decomposition of the data space into four subspaces is incomplete. We provide arguments on how to best enrich the decomposition of the data space in order to account for heteroscedasticity in the data. Finally, we provide experimental results validating our theoretical analysis.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {8},
numpages = {25},
keywords = {dimensionality reduction, Chernoff distance, LDA, FKT, Feature evaluation and selection}
}

@article{10.1145/2499907.2499909,
author = {Yang, Haiqin and Lyu, Michael R. and King, Irwin},
title = {Efficient Online Learning for Multitask Feature Selection},
year = {2013},
issue_date = {July 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {2},
issn = {1556-46

license_type: permissive

extension: bib