text:
145/3022186,
author = {Lim, Yongsub and Jung, Minsoo and Kang, U.},
title = {Memory-Efficient and Accurate Sampling for Counting Local Triangles in Graph Streams: From Simple to Multigraphs},
year = {2018},
issue_date = {February 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3022186},
doi = {10.1145/3022186},
abstract = {How can we estimate local triangle counts accurately in a graph stream without storing the whole graph? How to handle duplicated edges in local triangle counting for graph stream? Local triangle counting, which computes the number of triangles attached to each node in a graph, is a very important problem with wide applications in social network analysis, anomaly detection, web mining, and the like.In this article, we propose algorithms for local triangle counting in a graph stream based on edge sampling: Mascot for a simple graph, and MultiBMascot and MultiWMascot for a multigraph. To develop Mascot, we first present two naive local triangle counting algorithms in a graph stream, called Mascot-C and Mascot-A. Mascot-C is based on constant edge sampling, and Mascot-A improves its accuracy by utilizing more memory spaces. Mascot achieves both accuracy and memory-efficiency of the two algorithms by unconditional triangle counting for a new edge, regardless of whether it is sampled or not. Extending the idea to a multigraph, we develop two algorithms MultiBMascot and MultiWMascot. MultiBMascot enables local triangle counting on the corresponding simple graph of a streamed multigraph without explicit graph conversion; MultiWMascot considers repeated occurrences of an edge as its weight and counts each triangle as the product of its three edge weights. In contrast to the existing algorithm that requires prior knowledge on the target graph and appropriately set parameters, our proposed algorithms require only one parameter of edge sampling probability.Through extensive experiments, we show that for the same number of edges sampled, Mascot provides the best accuracy compared to the existing algorithm as well as Mascot-C and Mascot-A. We also demonstrate that MultiBMascot on a multigraph is comparable to Mascot-C on the counterpart simple graph, and MultiWMascot becomes more accurate for higher degree nodes. Thanks to Mascot, we also discover interesting anomalous patterns in real graphs, including core-peripheries in the web, a bimodal call pattern in a phone call history, and intensive collaboration in DBLP.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {4},
numpages = {28},
keywords = {anomaly detection, Local triangle counting, graph stream mining, edge sampling}
}

@article{10.1145/3070616,
author = {Choo, Jaegul and Kim, Hannah and Clarkson, Edward and Liu, Zhicheng and Lee, Changhyun and Li, Fuxin and Lee, Hanseung and Kannan, Ramakrishnan and Stolper, Charles D. and Stasko, John and Park, Haesun},
title = {VisIRR: A Visual Analytics System for Information Retrieval and Recommendation for Large-Scale Document Data},
year = {2018},
issue_date = {February 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3070616},
doi = {10.1145/3070616},
abstract = {In this article, we present an interactive visual information retrieval and recommendation system, called VisIRR, for large-scale document discovery. VisIRR effectively combines the paradigms of (1) a passive pull through query processes for retrieval and (2) an active push that recommends items of potential interest to users based on their preferences. Equipped with an efficient dynamic query interface against a large-scale corpus, VisIRR organizes the retrieved documents into high-level topics and visualizes them in a 2D space, representing the relationships among the topics along with their keyword summary. In addition, based on interactive personalized preference feedback with regard to documents, VisIRR provides document recommendations from the entire corpus, which are beyond the retrieved sets. Such recommended documents are visualized in the same space as the retrieved documents, so that users can seamlessly analyze both existing and newly recommended ones. This article presents novel computational methods, which make these integrated representations and fast interactions possible for a large-scale document corpus. We illustrate how the system works by providing detailed usage scenarios. Additionally, we present preliminary user study results for evaluating the effectiveness of the system.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {8},
numpages = {20},
keywords = {clustering, topic modeling, dimension reduction, information retrieval, Recommendation}
}

@article{10.1145/3106369,
author = {Trevi\~{n}o, Edgar S. Garc\'{\i}a and Hameed, Muhammad Zaid and Barria, Javier A},
title = {Data Stream Evolution Diagnosis Using Recursive Wavelet Density Estimators},
year = {2018},
issue_date = {February 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3106369},
doi = {10.1145/3106369},
abstract = {Data streams are a new class of data that is becoming pervasively important in a wide range of applications, ranging from sensor networks, environmental monitoring to finance. In this article, we propose a novel framework for the online diagnosis of evolution of multidimensional streaming data that incorporates Recursive Wavelet Density Estimators into the context of Velocity Density Estimation. In the proposed framework changes in streaming data are characterized by the use of local and global evolution coefficients. In addition, we propose for the analysis of changes in the correlation structure of the data a recursive implementation of the Pearson correlation coefficient using exponential discounting. Two visualization tools, namely temporal and spatial velocity profiles, are extended in the context of the proposed framework. These are the three main advantages of the proposed method over previous approaches: (1) the memory storage required is minimal and independent of any window size; (2) it has a significantly lower computational complexity; and (3) it makes possible the fast diagnosis of data evolution at all dimensions and at relevant combinations of dimensions with only one pass of the data. With the help of the four examples, we show the framework’s relevance in a change detection context and its potential capability for real world applications.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {14},
numpages = {28},
keywords = {data stream evolution diagnosis, Data streams mining, velocity density estimation, incremental statistics}
}

@article{10.1145/3127876,
author = {Chiasserini, Carla-Fabiana and Garetto, Michel and Leonardi, Emili},
title = {De-Anonymizing Clustered Social Networks by Percolation Graph Matching},
year = {2018},
issue_date = {March 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3127876},
doi = {10.1145/3127876},
abstract = {Online social networks offer the opportunity to collect a huge amount of valuable information about billions of users. The analysis of this data by service providers and unintended third parties are posing serious treats to user privacy. In particular, recent work has shown that users participating in more than one online social network can be identified based only on the structure of their links to other users. An effective tool to de-anonymize social network users is represented by graph matching algorithms. Indeed, by exploiting a sufficiently large set of seed nodes, a percolation process can correctly match almost all nodes across the different social networks. In this article, we show the crucial role of clustering, which is a relevant feature of social network graphs (and many other systems). Clustering has both the effect of making matching algorithms more prone to errors, and the potential to greatly reduce the number of seeds needed to trigger percolation. We show these facts by considering a fairly general class of random geometric graphs with variable clustering level. We assume that seeds can be identified in particular sub-regions of the network graph, while no a priori knowledge about the location of the other nodes is required. Under these conditions, we show how clever algorithms can achieve surprisingly good performance while limiting the number of matching errors.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {21},
numpages = {39},
keywords = {Graph matching, de-anonymization, bootstrap percolation}
}

@article{10.1145/3154414,
author = {Shin, Kijung and Hooi, Bryan and Faloutsos, Christos},
title = {Fast, Accurate, and Flexible Algorithms for Dense Subtensor Mining},
year = {2018},
issue_date = {April 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3154414},
doi = {10.1145/3154414},
abstract = {Given a large-scale and high-order tensor, how can we detect dense subtensors in it? Can we spot them in near-linear time but with quality guarantees? Extensive previous work has shown that dense subtensors, as well as dense subgraphs, indicate anomalous or fraudulent behavior (e.g., lockstep behavior in social networks). However, available algorithms for detecting dense subtensors are not satisfactory in terms of speed, accuracy, and flexibility. In this work, we propose two algorithms, called M-Zoom and M-Biz, for fast and accurate dense-subtensor detection with various density measures. M-Zoom gives a lower bound on the density of detected subtensors, while M-Biz guarantees the local optimality of detected subtensors. M-Zoom and M-Biz can be combined, giving the following advantages: (1) Scalable: scale near-linearly with all aspects of tensors and are up to 114\texttimes{} faster than state-of-the-art methods with similar accuracy, (2) Provably accurate: provide a guarantee on the lowest density and local optimality of the subtensors they find, (3) Flexible: support multi-subtensor detection and size bounds as well as diverse density measures, and (4) Effective: successfully detected edit wars and bot activities in Wikipedia, and spotted network attacks from a TCP dump with near-perfect accuracy (AUC = 0.98).},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {28},
numpages = {30},
keywords = {anomaly detection, fraud detection, Tensor, dense subtensor}
}

@article{10.1145/3127875,
author = {Zhao, Wayne Xin and Fan, Feifan and Wen, Ji-Rong and Chang, Edward Y.},
title = {Joint Representation Learning for Location-Based Social Networks with Multi-Grained Sequential Contexts},
year = {2018},
issue_date = {March 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3127875},
doi = {10.1145/3127875},
abstract = {This article studies the problem of learning effective representations for Location-Based Social Networks (LBSN), which is useful in many tasks such as location recommendation and link prediction. Existing network embedding methods mainly focus on capturing topology patterns reflected in social connections, while check-in sequences, the most important data type in LBSNs, are not directly modeled by these models. In this article, we propose a representation learning method for LBSNs called as JRLM++, which models check-in sequences together with social connections. To capture sequential relatedness, JRLM++ characterizes two levels of sequential contexts, namely fine-grained and coarse-grained contexts. We present a learning algorithm tailored to the hierarchical architecture of the proposed model. We conduct extensive experiments on two important applications using real-world datasets. The experimental results demonstrate the superiority of our model. The proposed model can generate effective representations for both users and locations in the same embedding space, which can be further utilized to improve multiple LBSN tasks.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {22},
numpages = {21},
keywords = {contextual information, distributed representation, location recommendation, Check-in sequences, social link prediction}
}

@article{10.1145/3127873,
author = {HU, Guang-Neng and Dai, Xin-Yu and Qiu, Feng-Yu and Xia, Rui and Li, Tao and Huang, Shu-Jian and Chen, Jia-Jun},
title = {Collaborative Filtering with Topic and Social Latent Factors Incorporating Implicit Feedback},
year = {2018},
issue_date = {March 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3127873},
doi = {10.1145/3127873},
abstract = {Recommender systems (RSs) provide an effective way of alleviating the information overload problem by selecting personalized items for different users. Latent factors-based collaborative filtering (CF) has become the popular approaches for RSs due to its accuracy and scalability. Recently, online social networks and user-generated content provide diverse sources for recommendation beyond ratings. Although social matrix factorization (Social MF) and topic matrix factorization (Topic MF) successfully exploit social relations and item reviews, respectively; both of them ignore some useful information. In this article, we investigate the effective data fusion by combining the aforementioned approaches. First, we propose a novel model MR3 to jointly model three sources of information (i.e., ratings, item reviews, and social relations) effectively for rating prediction by aligning the latent factors and hidden topics. Second, we incorporate the implicit feedback from ratings into the proposed model to enhance its capability and to demonstrate its flexibility. We achieve more accurate rating prediction on real-life datasets over various state-of-the-art methods. Furthermore, we measure the contribution from each of the three data sources and the impact of implicit feedback from ratings, followed by the sensitivity analysis of hyperparameters. Empirical studies demonstrate the effectiveness and efficacy of our proposed model and its extension.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {23},
numpages = {30},
keywords = {implicit feedback, collaborative filtering, hidden topics, latent social factors, Recommendation systems}
}

@article{10.1145/3092690,
author = {Wang, Boyue and Hu, Yongli and Gao, Junbin and Sun, Yanfeng and Yin, Baocai},
title = {Partial Sum Minimization of Singular Values Representation on Grassmann Manifolds},
year = {2018},
issue_date = {February 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3092690},
doi = {10.1145/3092690},
abstract = {Clustering is one of the fundamental topics in data mining and pattern recognition. As a prospective clustering method, the subspace clustering has made considerable progress in recent researches, e.g., sparse subspace clustering (SSC) and low rank representation (LRR). However, most existing subspace clustering algorithms are designed for vectorial data from linear spaces, thus not suitable for high-dimensional data with intrinsic non-linear manifold structure. For high-dimensional or manifold data, few research pays attention to clustering problems. The purpose of clustering on manifolds tends to cluster manifold-valued data into several groups according to the mainfold-based similarity metric. This article proposes an extended LRR model for manifold-valued Grassmann data that incorporates prior knowledge by minimizing partial sum of singular values instead of the nuclear norm, namely Partial Sum minimization of Singular Values Representation (GPSSVR). The new model not only enforces the global structure of data in low rank, but also retains important information by minimizing only smaller singular values. To further maintain the local structures among Grassmann points, we also integrate the Laplacian penalty with GPSSVR. The proposed model and algorithms are assessed on a public human face dataset, some widely used human action video datasets and a real scenery dataset. The experimental results show that the proposed methods obviously outperform other state-of-the-art methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {13},
numpages = {22},
keywords = {Grassmann manifolds, subspace clustering, Low rank representation, Laplacian matrix, partial sum minimization of singular values}
}

@article{10.1145/3154411,
author = {Belcastro, Loris and Marozzo, Fabrizio and Talia, Domenico and Trunfio, Paolo},
title = {G-RoI: Automatic Region-of-Interest Detection Driven by Geotagged Social Media Data},
year = {2018},
issue_date = {April 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3154411},
doi = {10.1145/3154411},
abstract = {Geotagged data gathered from social media can be used to discover interesting locations visited by users called Places-of-Interest (PoIs). Since a PoI is generally identified by the geographical coordinates of a single point, it is hard to match it with user trajectories. Therefore, it is useful to define an area, called Region-of-Interest (RoI), to represent the boundaries of the PoI’s area. RoI mining techniques are aimed at discovering ROIs from PoIs and other data. Existing RoI mining techniques are based on three main approaches: predefined shapes, density-based clustering, and grid-based aggregation. This article proposes G-RoI, a novel RoI mining technique that exploits the indications contained in geotagged social media items to discover RoIs with a high accuracy. Experiments performed over a set of PoIs in Rome and Paris using social media geotagged data, demonstrate that G-RoI in most cases achieves better results than existing techniques. In particular, the mean F1 score is 0.34 higher than that obtained with the well-known DBSCAN algorithm in Rome RoIs and 0.23 higher in Paris RoIs.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {27},
numpages = {22},
keywords = {Social network analysis, Geotagged social media, Regions-of-interest, RoI mining, Places-of-Interest}
}

@article{10.1145/3132088,
author = {Pandove, Divya and Goel, Shivan and Rani, Rinkl},
title = {Systematic Review of Clustering High-Dimensional and Large Datasets},
year = {2018},
issue_date = {March 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3132088},
doi = {10.1145/3132088},
abstract = {Technological advancement has enabled us to store and process huge amount of data in relatively short spans of time. The nature of data is rapidly changing, particularly its dimensionality is more commonly multi- and high-dimensional. There is an immediate need to expand our focus to include analysis of high-dimensional and large datasets. Data analysis is becoming a mammoth task, due to incremental increase in data volume and complexity in terms of heterogony of data. It is due to this dynamic computing environment that the existing techniques either need to be modified or discarded to handle new data in multiple high-dimensions. Data clustering is a tool that is used in many disciplines, including data mining, so that meaningful knowledge can be extracted from seemingly unstructured data. The aim of this article is to understand the problem of clustering and various approaches addressing this problem. This article discusses the process of clustering from both microviews (data treating) and macroviews (overall clustering process). Different distance and similarity measures, which form the cornerstone of effective data clustering, are also identified. Further, an in-depth analysis of different clustering approaches focused on data mining, dealing with large-scale datasets is given. These approaches are comprehensively compared to bring out a clear differentiation among them. This article also surveys the problem of high-dimensional data and the existing approaches, that makes it more relevant. It also explores the latest trends in cluster analysis, and the real-life applications of this concept. This survey is exhaustive as it tries to cover all the aspects of clustering in the field of data mining.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {16},
numpages = {68},
keywords = {data clustering applications, data clustering process, large scale data mining, Cluster analysis, clustering tendency, dimensionality reduction}
}

@article{10.1145/3161886,
author = {Chen, Guangyong and Zhu, Fengyuan and Heng, Pheng Ann},
title = {Large-Scale Bayesian Probabilistic Matrix Factorization with Memo-Free Distributed Variational Inference},
year = {2018},
issue_date = {April 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3161886},
doi = {10.1145/3161886},
abstract = {Bayesian Probabilistic Matrix Factorization (BPMF) is a powerful model in many dyadic data prediction problems, especially the applications of Recommender system. However, its poor scalability has limited its wide applications on massive data. Based on the conditional independence property of observed entries in BPMF model, we propose a novel distributed memo-free variational inference method for large-scale matrix factorization problems. Compared with the state-of-the-art methods, the proposed method is favored for several attractive properties. Specifically, it does not require tuning of learning rate carefully, shuffling the training set at each iteration, or storing massive redundant variables, and can introduce new agents into the computations on the fly. We conduct extensive experiments on both synthetic and real-world datasets. The experimental results show that our method can converge significantly faster with better prediction performance than alternative algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {31},
numpages = {24},
keywords = {memo-free variational inference, Recommender system, large-scale, BPMF, distributed computation}
}

@article{10.1145/3154401,
author = {Liang, Jiongqian and Ajwani, Deepak and Nicholson, Patrick K. and Sala, Alessandra and Parthasarathy, Srinivasan},
title = {Prioritized Relationship Analysis in Heterogeneous Information Networks},
year = {2018},
issue_date = {April 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3154401},
doi = {10.1145/3154401},
abstract = {An increasing number of applications are modeled and analyzed in network form, where nodes represent entities of interest and edges represent interactions or relationships between entities. Commonly, such relationship analysis tools assume homogeneity in both node type and edge type. Recent research has sought to redress the assumption of homogeneity and focused on mining heterogeneous information networks (HINs) where both nodes and edges can be of different types. Building on such efforts, in this work, we articulate a novel approach for mining relationships across entities in such networks while accounting for user preference over relationship type and interestingness metric. We formalize the problem as a top-k lightest paths problem, contextualized in a real-world communication network, and seek to find the k most interesting path instances matching the preferred relationship type. Our solution, PROphetic HEuristic Algorithm for Path Searching (PRO-HEAPS), leverages a combination of novel graph preprocessing techniques, well-designed heuristics and the venerable A* search algorithm. We run our algorithm on real-world large-scale graphs and show that our algorithm significantly outperforms a wide variety of baseline approaches with speedups as large as 100X.To widen the range of applications, we also extend PRO-HEAPS to (i) support relationship analysis between two groups of entities and (ii) allow pattern path in the query to contain logical statements with operators AND, OR, NOT, and wild-card “.”. We run experiments using this generalized version of PRO-HEAPS and demonstrate that the advantage of PRO-HEAPS becomes even more pronounced for these general cases. Furthermore, we conduct a comprehensive analysis to study how the performance of PRO-HEAPS varies with respect to various attributes of the input HIN. We finally conduct a case study to demonstrate valuable applications of our algorithm.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {29},
numpages = {27},
keywords = {semantic relationship queries, Heterogeneous information networks, graph algorithms}
}

@article{10.1145/3110215,
author = {Ramezani, Maryam and Khodadadi, Ali and Rabiee, Hamid R.},
title = {Community Detection Using Diffusion Information},
year = {2018},
issue_date = {March 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3110215},
doi = {10.1145/3110215},
abstract = {Community detection in social networks has become a popular topic of research during the last decade. There exist a variety of algorithms for modularizing the network graph into different communities. However, they mostly assume that partial or complete information of the network graphs are available that is not feasible in many cases. In this article, we focus on detecting communities by exploiting their diffusion information. To this end, we utilize the Conditional Random Fields (CRF) to discover the community structures. The proposed method, community diffusion (CoDi), does not require any prior knowledge about the network structure or specific properties of communities. Furthermore, in contrast to the structure-based community detection methods, this method is able to identify the hidden communities. The experimental results indicate considerable improvements in detecting communities based on accuracy, scalability, and real cascade information measures.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {20},
numpages = {22},
keywords = {Social networks, community detection, conditional random field, information diffusion, social influence}
}

@article{10.1145/3154399,
author = {Huang, Hong and Dong, Yuxiao and Tang, Jie and Yang, Hongxia and Chawla, Nitesh V. and Fu, Xiaoming},
title = {Will Triadic Closure Strengthen Ties in Social Networks?},
year = {2018},
issue_date = {April 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3154399},
doi = {10.1145/3154399},
abstract = {The social triad—a group of three people—is one of the simplest and most fundamental social groups. Extensive network and social theories have been developed to understand its structure, such as triadic closure and social balance. Over the course of a triadic closure—the transition from two ties to three among three users, the strength dynamics of its social ties, however, are much less well understood. Using two dynamic networks from social media and mobile communication, we examine how the formation of the third tie in a triad affects the strength of the existing two ties. Surprisingly, we find that in about 80% social triads, the strength of the first two ties is weakened although averagely the tie strength in the two networks maintains an increasing or stable trend. We discover that (1) the decrease in tie strength among three males is more sharply than that among females, and (2) the tie strength between celebrities is more likely to be weakened as the closure of a triad than those between ordinary people. Furthermore, we formalize a triadic tie strength dynamics prediction problem to infer whether social ties of a triad will become weakened after its closure. We propose a TRIST method—a kernel density estimation (KDE)-based graphical model—to solve the problem by incorporating user demographics, temporal effects, and structural information. Extensive experiments demonstrate that TRIST offers a greater than 82% potential predictability for inferring triadic tie strength dynamics in both networks. The leveraging of the KDE and structural correlations enables TRIST to outperform baselines by up to 30% in terms of F1-score.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {30},
numpages = {25},
keywords = {dynamics, Social triad, predictive model, tie strength}
}

@article{10.1145/3139240,
author = {Bonab, Hamed R. and Can, Fazli},
title = {GOOWE: Geometrically Optimum and Online-Weighted Ensemble Classifier for Evolving Data Streams},
year = {2018},
issue_date = {March 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3139240},
doi = {10.1145/3139240},
abstract = {Designing adaptive classifiers for an evolving data stream is a challenging task due to the data size and its dynamically changing nature. Combining individual classifiers in an online setting, the ensemble approach, is a well-known solution. It is possible that a subset of classifiers in the ensemble outperforms others in a time-varying fashion. However, optimum weight assignment for component classifiers is a problem, which is not yet fully addressed in online evolving environments. We propose a novel data stream ensemble classifier, called Geometrically Optimum and Online-Weighted Ensemble (GOOWE), which assigns optimum weights to the component classifiers using a sliding window containing the most recent data instances. We map vote scores of individual classifiers and true class labels into a spatial environment. Based on the Euclidean distance between vote scores and ideal-points, and using the linear least squares (LSQ) solution, we present a novel, dynamic, and online weighting approach. While LSQ is used for batch mode ensemble classifiers, it is the first time that we adapt and use it for online environments by providing a spatial modeling of online ensembles. In order to show the robustness of the proposed algorithm, we use real-world datasets and synthetic data generators using the Massive Online Analysis (MOA) libraries. First, we analyze the impact of our weighting system on prediction accuracy through two scenarios. Second, we compare GOOWE with eight state-of-the-art ensemble classifiers in a comprehensive experimental environment. Our experiments show that GOOWE provides improved reactions to different types of concept drift compared to our baselines. The statistical tests indicate a significant improvement in accuracy, with conservative time and memory requirements.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {25},
numpages = {33},
keywords = {geometry of voting, concept drift, spatial modeling for online ensembles, Ensemble classifier, evolving data stream, least squares, dynamic weighting}
}

@article{10.1145/3070645,
author = {Kaushal, Vishal and Patwardhan, Manasi},
title = {Emerging Trends in Personality Identification Using Online Social Networks—A Literature Survey},
year = {2018},
issue_date = {March 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3070645},
doi = {10.1145/3070645},
abstract = {Personality is a combination of all the attributes—behavioral, temperamental, emotional, and mental—that characterizes a unique individual. Ability to identify personalities of people has always been of great interest to the researchers due to its importance. It continues to find highly useful applications in many domains. Owing to the increasing popularity of online social networks, researchers have started looking into the possibility of predicting a user's personality from his online social networking profile, which serves as a rich source of textual as well as non-textual content published by users. In the process of creating social networking profiles, users reveal a lot about themselves both in what they share and how they say it. Studies suggest that the online social networking websites are, in fact, a relevant and valid means of communicating personality. In this article, we review these various studies reported in literature toward identification of personality using online social networks. To the best of our knowledge, this is the first reported survey of its kind at the time of submission. We hope that our contribution, especially in summarizing the previous findings and in identifying the directions for future research in this area, would encourage researchers to do more work in this budding area.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {15},
numpages = {30},
keywords = {personality prediction, mining social network, online social network, Facebook, Personality, Twitter}
}

@article{10.1145/3154417,
author = {Xie, Hong and Ma, Richard T. B. and Lui, John C. S.},
title = {Enhancing Reputation via Price Discounts in E-Commerce Systems: A Data-Driven Approach},
year = {2018},
issue_date = {April 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3154417},
doi = {10.1145/3154417},
abstract = {Reputation systems have become an indispensable component of modern E-commerce systems, as they help buyers make informed decisions in choosing trustworthy sellers. To attract buyers and increase the transaction volume, sellers need to earn reasonably high reputation scores. This process usually takes a substantial amount of time. To accelerate this process, sellers can provide price discounts to attract users, but the underlying difficulty is that sellers have no prior knowledge on buyers’ preferences over price discounts. In this article, we develop an online algorithm to infer the optimal discount rate from data. We first formulate an optimization framework to select the optimal discount rate given buyers’ discount preferences, which is a tradeoff between the short-term profit and the ramp-up time (for reputation). We then derive the closed-form optimal discount rate, which gives us key insights in applying a stochastic bandits framework to infer the optimal discount rate from the transaction data with regret upper bounds. We show that the computational complexity of evaluating the performance metrics is infeasibly high, and therefore, we develop efficient randomized algorithms with guaranteed performance to approximate them. Finally, we conduct experiments on a dataset crawled from eBay. Experimental results show that our framework can trade 60% of the short-term profit for reducing the ramp-up time by 40%. This reduction in the ramp-up time can increase the long-term profit of a seller by at least 20%.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {26},
numpages = {29},
keywords = {stochastic bandits, reputation systems, randomized algorithms, price discounts, E-commerce}
}

@article{10.1145/3110216,
author = {Long, Cheng and Wong, Raymond Chi-Wing and Wei, Victor Junqiu},
title = {Profit Maximization with Sufficient Customer Satisfactions},
year = {2018},
issue_date = {March 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3110216},
doi = {10.1145/3110216},
abstract = {In many commercial campaigns, we observe that there exists a tradeoff between the number of customers satisfied by the company and the profit gained. Merely satisfying as many customers as possible or maximizing the profit is not desirable. To this end, in this article, we propose a new problem called k-<underline>S</underline>atisfiability <underline>A</underline>ssignment for <underline>M</underline>aximizing the <underline>P</underline>rofit (k-SAMP), where k is a user parameter and a non-negative integer. Given a set P of products and a set O of customers, k-SAMP is to find an assignment between P and O such that at least k customers are satisfied in the assignment and the profit incurred by this assignment is maximized. Although we find that this problem is closely related to two classic computer science problems, namely maximum weight matching and maximum matching, the techniques developed for these classic problems cannot be adapted to our k-SAMP problem. In this work, we design a novel algorithm called Adjust for the k-SAMP problem. Given an assignment A, Adjust iteratively increases the profit of A by adjusting some appropriate matches in A while keeping at least k customers satisfied in A. We prove that Adjust returns a global optimum. Extensive experiments were conducted that verified the efficiency of Adjust.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {19},
numpages = {34},
keywords = {Assignment, users’ satisfactions, profit maximization}
}

@article{10.1145/3106370,
author = {Li, Yixuan and He, Kun and Kloster, Kyle and Bindel, David and Hopcroft, John},
title = {Local Spectral Clustering for Overlapping Community Detection},
year = {2018},
issue_date = {March 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3106370},
doi = {10.1145/3106370},
abstract = {Large graphs arise in a number of contexts and understanding their structure and extracting information from them is an important research area. Early algorithms for mining communities have focused on global graph structure, and often run in time proportional to the size of the entire graph. As we explore networks with millions of vertices and find communities of size in the hundreds, it becomes important to shift our attention from macroscopic structure to microscopic structure in large networks. A growing body of work has been adopting local expansion methods in order to identify communities from a few exemplary seed members.In this article, we propose a novel approach for finding overlapping communities called Lemon (Local Expansion via Minimum One Norm). Provided with a few known seeds, the algorithm finds the community by performing a local spectral diffusion. The core idea of Lemon is to use short random walks to approximate an invariant subspace near a seed set, which we refer to as local spectra. Local spectra can be viewed as the low-dimensional embedding that captures the nodes’ closeness in the local network structure. We show that Lemon’s performance in detecting communities is competitive with state-of-the-art methods. Moreover, the running time scales with the size of the community rather than that of the entire graph. The algorithm is easy to implement and is highly parallelizable. We further provide theoretical analysis of the local spectral properties, bounding the measure of tightness of extracted community using the eigenvalues of graph Laplacian.We thoroughly evaluate our approach using both synthetic and real-world datasets across different domains, and analyze the empirical variations when applying our method to inherently different networks in practice. In addition, the heuristics on how the seed set quality and quantity would affect the performance are provided.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {17},
numpages = {27},
keywords = {Community detection, local spectral clustering, graph diffusion, random walk, seed set expansion}
}

@article{10.1145/3139241,
author = {Perozzi, Bryan and Akoglu, Leman},
title = {Discovering Communities and Anomalies in Attributed Graphs: Interactive Visual Exploration and Summarization},
year = {2018},
issue_date = {March 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3139241},
doi = {10.1145/3139241},
abstract = {Given a network with node attributes, how can we identify communities and spot anomalies? How can we characterize, describe, or summarize the network in a succinct way? Community extraction requires a measure of quality for connected subgraphs (e.g., social circles). Existing subgraph measures, however, either consider only the connectedness of nodes inside the community and ignore the cross-edges at the boundary (e.g., density) or only quantify the structure of the community and ignore the node attributes (e.g., conductance). In this work, we focus on node-attributed networks and introduce: (1) a new measure of subgraph quality for attributed communities called normality, (2) a community extraction algorithm that uses normality to extract communities and a few characterizing attributes per community, and (3) a summarization and interactive visualization approach for attributed graph exploration. More specifically, (1) we first introduce a new measure to quantify the normality of an attributed subgraph. Our normality measure carefully utilizes structure and attributes together to quantify both the internal consistency and external separability. We then formulate an objective function to automatically infer a few attributes (called the “focus”) and respective attribute weights, so as to maximize the normality  score of a given subgraph. Most notably, unlike many other approaches, our measure allows for many cross-edges as long as they can be “exonerated;” i.e., either (i) are expected under a null graph model, and/or (ii) their boundary nodes do not exhibit the focus attributes. Next, (2) we propose AMEN (for Attributed Mining of Entity Networks), an algorithm that simultaneously discovers the communities and their respective focus in a given graph, with a goal to maximize the total normality. Communities for which a focus that yields high normality  cannot be found are considered low quality or anomalous. Last, (3) we formulate a summarization task with a multi-criteria objective, which selects a subset of the communities that (i) cover the entire graph well, are (ii) high quality and (iii) diverse in their focus attributes. We further design an interactive visualization interface that presents the communities to a user in an interpretable, user-friendly fashion. The user can explore all the communities, analyze various algorithm-generated summaries, as well as devise their own summaries interactively to characterize the network in a succinct way. As the experiments on real-world attributed graphs show, our proposed approaches effectively find anomalous communities and outperform several existing measures and methods, such as conductance, density, OddBall, and SODA. We also conduct extensive user studies to measure the capability and efficiency that our approach provides to the users toward network summarization, exploration, and sensemaking.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {24},
numpages = {40},
keywords = {summarization, social circles, Attributed graphs, human-in-the-loop, visual analytics, community extraction, network measures, anomaly mining, interaction design, ego networks}
}

@article{10.1145/3106368,
author = {Costa, Gianni and Ortale, Riccardo},
title = {Mining Overlapping Communities and Inner Role Assignments through Bayesian Mixed-Membership Models of Networks with Context-Dependent Interactions},
year = {2018},
issue_date = {March 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3106368},
doi = {10.1145/3106368},
abstract = {Community discovery and role assignment have been recently integrated into an unsupervised approach for the exploratory analysis of overlapping communities and inner roles in networks. However, the formation of ties in these prototypical research efforts is not truly realistic, since it does not account for a fundamental aspect of link establishment in real-world networks, i.e., the explicative reasons that cause interactions among nodes. Such reasons can be interpreted as generic requirements of nodes, that are met by other nodes and essentially pertain both to the nodes themselves and to their interaction contexts (i.e., the respective communities and roles).In this article, we present two new model-based machine-learning approaches, wherein community discovery and role assignment are seamlessly integrated and simultaneously performed through approximate posterior inference in Bayesian mixed-membership models of directed networks. The devised models account for the explicative reasons governing link establishment in terms of node-specific and contextual latent interaction factors. The former are inherently characteristic of nodes, while the latter are characterizations of nodes in the context of the individual communities and roles. The generative process of both models assigns nodes to communities with respective roles and connects them through directed links, which are probabilistically governed by their node-specific and contextual interaction factors. The difference between the proposed models lies in the exploitation of the contextual interaction factors. More precisely, in one model, the contextual interaction factors have the same impact on link generation. In the other model, the contextual interaction factors are weighted by the extent of involvement of the linked nodes in the respective communities and roles.We develop MCMC algorithms implementing approximate posterior inference and parameter estimation within our models.Finally, we conduct an intensive comparative experimentation, which demonstrates their superiority in community compactness and link prediction on various real-world and synthetic networks.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {18},
numpages = {32},
keywords = {Bayesian probabilistic network analysis, Overlapping community detection, role assignment, link prediction}
}

@article{10.1145/3047009,
author = {Datta, Srayan and Adar, Eytan},
title = {C<span class="smallcaps SmallerCapital">ommunity</span>D<span class="smallcaps SmallerCapital">iff</span>: Visualizing Community Clustering Algorithms},
year = {2018},
issue_date = {February 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {12},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3047009},
doi = {10.1145/3047009},
abstract = {Community detection is an oft-used analytical function of network analysis but can be a black art to apply in practice. Grouping of related nodes is important for identifying patterns in network datasets but also notoriously sensitive to input data and algorithm selection. This is further complicated by the fact that, depending on domain and use case, the ground truth knowledge of the end-user can vary from none to complete. In this work, we present CommunityDiff, an interactive visualization system that combines visualization and active learning (AL) to support the end-user’s analytical process. As the end-user interacts with the system, a continuous refinement process updates both the community labels and visualizations. CommunityDiff features a mechanism for visualizing ensemble spaces, weighted combinations of algorithm output, that can identify patterns, commonalities, and differences among multiple community detection algorithms. Among other features, CommunityDiff introduces an AL mechanism that visually indicates uncertainty about community labels to focus end-user attention and supporting end-user control that ranges from explicitly indicating the number of expected communities to merging and splitting communities. Based on this end-user input, CommunityDiff dynamically recalculates communities. We demonstrate the viability of our through a study of speed of end-user convergence on satisfactory community labels. As part of building CommunityDiff, we describe a design process that can be adapted to other Interactive Machine Learning applications.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {11},
numpages = {34},
keywords = {Community detection, visualization, interactive machine learning}
}

@article{10.1145/3059214,
author = {Zhang, Tianyang and Cui, Peng and Faloutsos, Christos and Lu, Yunfei and Ye, Hao and Zhu, Wenwu and Yang, Shiqiang},
title = {<span class="smallcaps SmallerCapital">come</span>N<span class="smallcaps SmallerCapital">go</span>: A Dynamic Model for Social Group Evolution},
year = {2017},
issue_date = {August 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3059214},
doi = {10.1145/3059214},
abstract = {How do social groups, such as Facebook groups and Wechat groups, dynamically evolve over time? How do people join the social groups, uniformly or with burst? What is the pattern of people quitting from groups? Is there a simple universal model to depict the come-and-go patterns of various groups?In this article, we examine temporal evolution patterns of more than 100 thousands social groups with more than 10 million users. We surprisingly find that the evolution patterns of real social groups goes far beyond the classic dynamic models like SI and SIR. For example, we observe both diffusion and non-diffusion mechanism in the group joining process, and power-law decay in group quitting process, rather than exponential decay as expected in SIR model. Therefore, we propose a new model comeNgo, a concise yet flexible dynamic model for group evolution. Our model has the following advantages: (a) Unification power: it generalizes earlier theoretical models and different joining and quitting mechanisms we find from observation. (b) Succinctness and interpretability: it contains only six parameters with clear physical meanings. (c) Accuracy: it can capture various kinds of group evolution patterns preciously, and the goodness of fit increases by 58% over baseline. (d) Usefulness: it can be used in multiple application scenarios, such as forecasting and pattern discovery. Furthermore, our model can provide insights about different evolution patterns of social groups, and we also find that group structure and its evolution has notable relations with temporal patterns of group evolution.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {41},
numpages = {22},
keywords = {dynamic model, temporal patterns, Group evolution}
}

@article{10.1145/3046947,
author = {Anderson, Ashton and Kleinberg, Jon and Mullainathan, Sendhil},
title = {Assessing Human Error Against a Benchmark of Perfection},
year = {2017},
issue_date = {August 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3046947},
doi = {10.1145/3046947},
abstract = {An increasing number of domains are providing us with detailed trace data on human decisions in settings where we can evaluate the quality of these decisions via an algorithm. Motivated by this development, an emerging line of work has begun to consider whether we can characterize and predict the kinds of decisions where people are likely to make errors.To investigate what a general framework for human error prediction might look like, we focus on a model system with a rich history in the behavioral sciences: the decisions made by chess players as they select moves in a game. We carry out our analysis at a large scale, employing datasets with several million recorded games, and using chess tablebases to acquire a form of ground truth for a subset of chess positions that have been completely solved by computers but remain challenging for even the best players in the world.We organize our analysis around three categories of features that we argue are present in most settings where the analysis of human error is applicable: the skill of the decision-maker, the time available to make the decision, and the inherent difficulty of the decision. We identify rich structure in all three of these categories of features, and find strong evidence that in our domain, features describing the inherent difficulty of an instance are significantly more powerful than features based on skill or time.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {45},
numpages = {25},
keywords = {Blunder prediction, human decision-making}
}

@article{10.1145/3046945,
author = {Algizawy, Essam and Ogawa, Tetsuji and El-Mahdy, Ahmed},
title = {Real-Time Large-Scale Map Matching Using Mobile Phone Data},
year = {2017},
issue_date = {August 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3046945},
doi = {10.1145/3046945},
abstract = {With the wide spread use of mobile phones, cellular mobile big data is becoming an important resource that provides a wealth of information with almost no cost. However, the data generally suffers from relatively high spatial granularity, limiting the scope of its application. In this article, we consider, for the first time, the utility of actual mobile big data for map matching allowing for “microscopic” level traffic analysis. The state-of-the-art in map matching generally targets GPS data, which provides far denser sampling and higher location resolution than the mobile data. Our approach extends the typical Hidden-Markov model used in map matching to accommodate for highly sparse location trajectories, exploit the large mobile data volume to learn the model parameters, and exploit the sparsity of the data to provide for real-time Viterbi processing. We study an actual, anonymised mobile trajectories data set of the city of Dakar, Senegal, spanning a year, and generate a corresponding road-level traffic density, at an hourly granularity, for each mobile trajectory. We observed a relatively high correlation between the generated traffic intensities and corresponding values obtained by the gravity and equilibrium models typically used in mobility analysis, indicating the utility of the approach as an alternative means for traffic analysis.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {52},
numpages = {38},
keywords = {low cost, fine-grained spatial tracking, cellular duration records, Mobile big data, adaptive HMM}
}

@article{10.1145/3070644,
author = {Vosoughi, Soroush and Mohsenvand, Mostafa ‘Neo’ and Roy, Deb},
title = {Rumor Gauge: Predicting the Veracity of Rumors on Twitter},
year = {2017},
issue_date = {August 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3070644},
doi = {10.1145/3070644},
abstract = {The spread of malicious or accidental misinformation in social media, especially in time-sensitive situations, such as real-world emergencies, can have harmful effects on individuals and society. In this work, we developed models for automated verification of rumors (unverified information) that propagate through Twitter. To predict the veracity of rumors, we identified salient features of rumors by examining three aspects of information spread: linguistic style used to express rumors, characteristics of people involved in propagating information, and network propagation dynamics. The predicted veracity of a time series of these features extracted from a rumor (a collection of tweets) is generated using Hidden Markov Models. The verification algorithm was trained and tested on 209 rumors representing 938,806 tweets collected from real-world events, including the 2013 Boston Marathon bombings, the 2014 Ferguson unrest, and the 2014 Ebola epidemic, and many other rumors about various real-world events reported on popular websites that document public rumors. The algorithm was able to correctly predict the veracity of 75% of the rumors faster than any other public source, including journalists and law enforcement officials. The ability to track rumors and predict their outcomes may have practical applications for news consumers, financial markets, journalists, and emergency services, and more generally to help minimize the impact of false information on Twitter.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {50},
numpages = {36},
keywords = {propagation, Twitter, rumor, veracity prediction, fake news}
}

@article{10.1145/3064884,
author = {Costa, Alceu Ferraz and Yamaguchi, Yuto and Traina, Agma Juci Machado and Jr., Caetano Traina and Faloutsos, Christos},
title = {Modeling Temporal Activity to Detect Anomalous Behavior in Social Media},
year = {2017},
issue_date = {August 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3064884},
doi = {10.1145/3064884},
abstract = {Social media has become a popular and important tool for human communication. However, due to this popularity, spam and the distribution of malicious content by computer-controlled users, known as bots, has become a widespread problem. At the same time, when users use social media, they generate valuable data that can be used to understand the patterns of human communication. In this article, we focus on the following important question: Can we identify and use patterns of human communication to decide whether a human or a bot controls a user? The first contribution of this article is showing that the distribution of inter-arrival times (IATs) between postings is characterized by following four patterns: (i) heavy-tails, (ii) periodic-spikes, (iii) correlation between consecutive values, and (iv) bimodallity. As our second contribution, we propose a mathematical model named Act-M (Activity Model). We show that Act-M can accurately fit the distribution of IATs from social media users. Finally, we use Act-M to develop a method that detects if users are bots based only on the timing of their postings. We validate Act-M using data from over 55 million postings from four social media services: Reddit, Twitter, Stack-Overflow, and Hacker-News. Our experiments show that Act-M provides a more accurate fit to the data than existing models for human dynamics. Additionally, when detecting bots, Act-M provided a precision higher than 93% and 77% with a sensitivity of 70% for the Twitter and Reddit datasets, respectively.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {49},
numpages = {23},
keywords = {inter-arrival times, communication dynamics, Social media, anomaly detection}
}

@article{10.1145/3059177,
author = {Anagnostopoulos, Christos and Triantafillou, Peter},
title = {Query-Driven Learning for Predictive Analytics of Data Subspace Cardinality},
year = {2017},
issue_date = {August 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3059177},
doi = {10.1145/3059177},
abstract = {Fundamental to many predictive analytics tasks is the ability to estimate the cardinality (number of data items) of multi-dimensional data subspaces, defined by query selections over datasets. This is crucial for data analysts dealing with, e.g., interactive data subspace explorations, data subspace visualizations, and in query processing optimization. However, in many modern data systems, predictive analytics may be (i) too costly money-wise, e.g., in clouds, (ii) unreliable, e.g., in modern Big Data query engines, where accurate statistics are difficult to obtain/maintain, or (iii) infeasible, e.g., for privacy issues. We contribute a novel, query-driven, function estimation model of analyst-defined data subspace cardinality. The proposed estimation model is highly accurate in terms of prediction and accommodating the well-known selection queries: multi-dimensional range and distance-nearest neighbors (radius) queries. Our function estimation model: (i) quantizes the vectorial query space, by learning the analysts’ access patterns over a data space, (ii) associates query vectors with their corresponding cardinalities of the analyst-defined data subspaces, (iii) abstracts and employs query vectorial similarity to predict the cardinality of an unseen/unexplored data subspace, and (iv) identifies and adapts to possible changes of the query subspaces based on the theory of optimal stopping. The proposed model is decentralized, facilitating the scaling-out of such predictive analytics queries. The research significance of the model lies in that (i) it is an attractive solution when data-driven statistical techniques are undesirable or infeasible, (ii) it offers a scale-out, decentralized training solution, (iii) it is applicable to different selection query types, and (iv) it offers a performance that is superior to that of data-driven approaches.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {47},
numpages = {46},
keywords = {analytics selection queries, vector regression quantization, optimal stopping theory, Predictive analytics, predictive learning, data subspace exploration}
}

@article{10.1145/3070647,
author = {Wang, Yihan and Song, Shaoxu and Chen, Lei and Yu, Jeffrey Xu and Cheng, Hong},
title = {Discovering Conditional Matching Rules},
year = {2017},
issue_date = {August 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3070647},
doi = {10.1145/3070647},
abstract = {Matching dependencies (MDs) have recently been proposed to make data dependencies tolerant to various information representations, and found useful in data quality applications such as record matching. Instead of the strict equality function used in traditional dependency syntax (e.g., functional dependencies), MDs specify constraints based on similarity and identification. However, in practice, MDs may still be too strict and applicable only in a subset of tuples in a relation. Thereby, we study the conditional matching dependencies (CMDs), which bind matching dependencies only in a certain part of a table, i.e., MDs conditionally applicable in a subset of tuples. Compared to MDs, CMDs have more expressive power that enables them to satisfy wider application needs. In this article, we study several important theoretical and practical issues of CMDs, including irreducible CMDs with respect to the implication, discovery of CMDs from data, reliable CMDs agreed most by a relation, approximate CMDs almost satisfied in a relation, and finally applications of CMDs in record matching and missing value repairing. Through an extensive experimental evaluation in real data sets, we demonstrate the efficiency of proposed CMDs discovery algorithms and effectiveness of CMDs in real applications.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {46},
numpages = {38},
keywords = {data repair, record matching, Conditional matching dependency}
}

@article{10.1145/3092689,
author = {Aggarwal, Charu C.},
title = {Introduction to Special Issue on the Best Papers from KDD 2016},
year = {2017},
issue_date = {August 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3092689},
doi = {10.1145/3092689},
abstract = {This issue contains the best papers from the ACM KDD Conference 2016. As is customary at KDD, special issue papers are invited only from the research track. The top-ranked papers from the KDD 2016 conference are included in this issue. This issue contains a total of six articles, which are from different areas of data mining. A brief description of these articles is also provided in this article.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {39},
numpages = {3},
keywords = {Data mining}
}

@article{10.1145/3059194,
author = {Stefani, Lorenzo De and Epasto, Alessandro and Riondato, Matteo and Upfal, Eli},
title = {TRI\`{E}ST: Counting Local and Global Triangles in Fully Dynamic Streams with Fixed Memory Size},
year = {2017},
issue_date = {August 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3059194},
doi = {10.1145/3059194},
abstract = {“Ogni lassada xe persa.”1-- Proverb from Trieste, Italy.We present tri\`{e}st, a suite of one-pass streaming algorithms to compute unbiased, low-variance, high-quality approximations of the global and local (i.e., incident to each vertex) number of triangles in a fully dynamic graph represented as an adversarial stream of edge insertions and deletions.Our algorithms use reservoir sampling and its variants to exploit the user-specified memory space at all times. This is in contrast with previous approaches, which require hard-to-choose parameters (e.g., a fixed sampling probability) and offer no guarantees on the amount of memory they use. We analyze the variance of the estimations and show novel concentration bounds for these quantities.Our experimental results on very large graphs demonstrate that tri\`{e}st outperforms state-of-the-art approaches in accuracy and exhibits a small update time.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {43},
numpages = {50},
keywords = {reservoir sampling, subgraph counting, Cycle counting}
}

@article{10.1145/3056562,
author = {Chen, Chen and Tong, Hanghang and Xie, Lei and Ying, Lei and He, Qing},
title = {Cross-Dependency Inference in Multi-Layered Networks: A Collaborative Filtering Perspective},
year = {2017},
issue_date = {August 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3056562},
doi = {10.1145/3056562},
abstract = {The increasingly connected world has catalyzed the fusion of networks from different domains, which facilitates the emergence of a new network model—multi-layered networks. Examples of such kind of network systems include critical infrastructure networks, biological systems, organization-level collaborations, cross-platform e-commerce, and so forth. One crucial structure that distances multi-layered network from other network models is its cross-layer dependency, which describes the associations between the nodes from different layers. Needless to say, the cross-layer dependency in the network plays an essential role in many data mining applications like system robustness analysis and complex network control. However, it remains a daunting task to know the exact dependency relationships due to noise, limited accessibility, and so forth. In this article, we tackle the cross-layer dependency inference problem by modeling it as a collective collaborative filtering problem. Based on this idea, we propose an effective algorithm F<scp;>ascinate</scp;> that can reveal unobserved dependencies with linear complexity. Moreover, we derive F<scp;>ascinate</scp;>-ZERO, an online variant of F<scp;>ascinate</scp;> that can respond to a newly added node timely by checking its neighborhood dependencies. We perform extensive evaluations on real datasets to substantiate the superiority of our proposed approaches.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {42},
numpages = {26},
keywords = {Multi-layered network, graph mining, cross-layer dependency}
}

@article{10.1145/3046946,
author = {Cheng, Wei and Ni, Jingchao and Zhang, Kai and Chen, Haifeng and Jiang, Guofei and Shi, Yu and Zhang, Xiang and Wang, Wei},
title = {Ranking Causal Anomalies for System Fault Diagnosis via Temporal and Dynamical Analysis on Vanishing Correlations},
year = {2017},
issue_date = {August 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3046946},
doi = {10.1145/3046946},
abstract = {Detecting system anomalies is an important problem in many fields such as security, fault management, and industrial optimization. Recently, invariant network has shown to be powerful in characterizing complex system behaviours. In the invariant network, a node represents a system component and an edge indicates a stable, significant interaction between two components. Structures and evolutions of the invariance network, in particular the vanishing correlations, can shed important light on locating causal anomalies and performing diagnosis. However, existing approaches to detect causal anomalies with the invariant network often use the percentage of vanishing correlations to rank possible casual components, which have several limitations: (1) fault propagation in the network is ignored, (2) the root casual anomalies may not always be the nodes with a high percentage of vanishing correlations, (3) temporal patterns of vanishing correlations are not exploited for robust detection, and (4) prior knowledge on anomalous nodes are not exploited for (semi-)supervised detection. To address these limitations, in this article we propose a network diffusion based framework to identify significant causal anomalies and rank them. Our approach can effectively model fault propagation over the entire invariant network and can perform joint inference on both the structural and the time-evolving broken invariance patterns. As a result, it can locate high-confidence anomalies that are truly responsible for the vanishing correlations and can compensate for unstructured measurement noise in the system. Moreover, when the prior knowledge on the anomalous status of some nodes are available at certain time points, our approach is able to leverage them to further enhance the anomaly inference accuracy. When the prior knowledge is noisy, our approach also automatically learns reliable information and reduces impacts from noises. By performing extensive experiments on synthetic datasets, bank information system datasets, and coal plant cyber-physical system datasets, we demonstrate the effectiveness of our approach.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {40},
numpages = {28},
keywords = {nonnegative matrix factorization, label propagation, Causal anomalies ranking}
}

@article{10.1145/3080574,
author = {Boutemine, Oualid and Bouguessa, Mohamed},
title = {Mining Community Structures in Multidimensional Networks},
year = {2017},
issue_date = {August 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3080574},
doi = {10.1145/3080574},
abstract = {We investigate the problem of community detection in multidimensional networks, that is, networks where entities engage in various interaction types (dimensions) simultaneously. While some approaches have been proposed to identify community structures in multidimensional networks, there are a number of problems still to solve. In fact, the majority of the proposed approaches suffer from one or even more of the following limitations: (1) difficulty detecting communities in networks characterized by the presence of many irrelevant dimensions, (2) lack of systematic procedures to explicitly identify the relevant dimensions of each community, and (3) dependence on a set of user-supplied parameters, including the number of communities, that require a proper tuning. Most of the existing approaches are inadequate for dealing with these three issues in a unified framework. In this paper, we develop a novel approach that is capable of addressing the aforementioned limitations in a single framework. The proposed approach allows automated identification of communities and their sub-dimensional spaces using a novel objective function and a constrained label propagation-based optimization strategy. By leveraging the relevance of dimensions at the node level, the strategy aims to maximize the number of relevant within-community links while keeping track of the most relevant dimensions. A notable feature of the proposed approach is that it is able to automatically identify low dimensional community structures embedded in a high dimensional space. Experiments on synthetic and real multidimensional networks illustrate the suitability of the new method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {51},
numpages = {36},
keywords = {community detection, social networks, Data mining}
}

@article{10.1145/3056563,
author = {Hooi, Bryan and Shin, Kijung and Song, Hyun Ah and Beutel, Alex and Shah, Neil and Faloutsos, Christos},
title = {Graph-Based Fraud Detection in the Face of Camouflage},
year = {2017},
issue_date = {August 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3056563},
doi = {10.1145/3056563},
abstract = {Given a bipartite graph of users and the products that they review, or followers and followees, how can we detect fake reviews or follows? Existing fraud detection methods (spectral, etc.) try to identify dense subgraphs of nodes that are sparsely connected to the remaining graph. Fraudsters can evade these methods using camouflage, by adding reviews or follows with honest targets so that they look “normal.” Even worse, some fraudsters use hijacked accounts from honest users, and then the camouflage is indeed organic.Our focus is to spot fraudsters in the presence of camouflage or hijacked accounts. We propose FRAUDAR, an algorithm that (a) is camouflage resistant, (b) provides upper bounds on the effectiveness of fraudsters, and (c) is effective in real-world data. Experimental results under various attacks show that FRAUDAR outperforms the top competitor in accuracy of detecting both camouflaged and non-camouflaged fraud. Additionally, in real-world experiments with a Twitter follower--followee graph of 1.47 billion edges, FRAUDAR successfully detected a subgraph of more than 4, 000 detected accounts, of which a majority had tweets showing that they used follower-buying services.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {44},
numpages = {26},
keywords = {link analysis, Fraud detection, spam detection}
}

@article{10.1145/3070646,
author = {Wu, Yue and Hoi, Steven C. H. and Mei, Tao and Yu, Nenghai},
title = {Large-Scale Online Feature Selection for Ultra-High Dimensional Sparse Data},
year = {2017},
issue_date = {August 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3070646},
doi = {10.1145/3070646},
abstract = {Feature selection (FS) is an important technique in machine learning and data mining, especially for large-scale high-dimensional data. Most existing studies have been restricted to batch learning, which is often inefficient and poorly scalable when handling big data in real world. As real data may arrive sequentially and continuously, batch learning has to retrain the model for the new coming data, which is very computationally intensive. Online feature selection (OFS) is a promising new paradigm that is more efficient and scalable than batch learning algorithms. However, existing online algorithms usually fall short in their inferior efficacy. In this article, we present a novel second-order OFS algorithm that is simple yet effective, very fast and extremely scalable to deal with large-scale ultra-high dimensional sparse data streams. The basic idea is to exploit the second-order information to choose the subset of important features with high confidence weights. Unlike existing OFS methods that often suffer from extra high computational cost, we devise a novel algorithm with a MaxHeap-based approach, which is not only more effective than the existing first-order algorithms, but also significantly more efficient and scalable. Our extensive experiments validated that the proposed technique achieves highly competitive accuracy as compared with state-of-the-art batch FS methods, meanwhile it consumes significantly less computational cost that is orders of magnitude lower. Impressively, on a billion-scale synthetic dataset (1-billion dimensions, 1-billion non-zero features, and 1-million samples), the proposed algorithm takes less than 3 minutes to run on a single PC.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {48},
numpages = {22},
keywords = {second-order online learning, sparsity, ultra-high dimensionality, Feature selection}
}

@article{10.1145/3014060,
author = {Tang, Xun and Alabduljalil, Maha and Jin, Xin and Yang, Tao},
title = {Partitioned Similarity Search with Cache-Conscious Data Traversal},
year = {2017},
issue_date = {April 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3014060},
doi = {10.1145/3014060},
abstract = {All pairs similarity search (APSS) is used in many web search and data mining applications. Previous work has used techniques such as comparison filtering, inverted indexing, and parallel accumulation of partial results. However, shuffling intermediate results can incur significant communication overhead as data scales up. This paper studies a scalable two-phase approach called Partition-based Similarity Search (PSS). The first phase is to partition the data and group vectors that are potentially similar. The second phase is to run a set of tasks where each task compares a partition of vectors with other candidate partitions. Due to data sparsity and the presence of memory hierarchy, accessing feature vectors during the partition comparison phase incurs significant overhead. This paper introduces a cache-conscious design for data layout and traversal to reduce access time through size-controlled data splitting and vector coalescing, and it provides an analysis to guide the choice of optimization parameters. The evaluation results show that for the tested datasets, the proposed approach can lead to an early elimination of unnecessary I/O and data communication while sustaining parallel efficiency with one order of magnitude of performance improvement and it can also be integrated with LSH for approximated APSS.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {34},
numpages = {38},
keywords = {data traversal, All-pairs similarity search, partitioning, memory hierarchy}
}

@article{10.1145/3051128,
author = {Wang, Liang and Yu, Zhiwen and Guo, Bin and Ku, Tao and Yi, Fei},
title = {Moving Destination Prediction Using Sparse Dataset: A Mobility Gradient Descent Approach},
year = {2017},
issue_date = {April 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3051128},
doi = {10.1145/3051128},
abstract = {Moving destination prediction offers an important category of location-based applications and provides essential intelligence to business and governments. In existing studies, a common approach to destination prediction is to match the given query trajectory with massive recorded trajectories by similarity calculation. Unfortunately, due to privacy concerns, budget constraints, and many other factors, in most circumstances, we can only obtain a sparse trajectory dataset. In sparse dataset, the available moving trajectories are far from enough to cover all possible query trajectories; thus the predictability of the matching-based approach will decrease remarkably. Toward destination prediction with sparse dataset, instead of searching similar trajectories over the sparse records, we alternatively examine the changes of distances from sampling locations to final destination on query trajectory. The underlying idea is intuitive: It is directly motivated by travel purpose, people always get closer to the final destination during the movement. By borrowing the conception of gradient descent in optimization theory, we propose a novel moving destination prediction approach, namely MGDPre. Building upon the mobility gradient descent, MGDPre only investigates the behavior characteristics of query trajectory itself without matching historical trajectories, and thus is applicable for sparse dataset. We evaluate our approach based on extensive experiments, using GPS trajectories generated by a sample of taxis over a 10-day period in Shenzhen city, China. The results demonstrate that the effectiveness, efficiency, and scalability of our approach outperform state-of-the-art baseline methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {37},
numpages = {33},
keywords = {gradient descent, sparse dataset, Moving destination prediction, space division, Markov transition model}
}

@article{10.1145/3046948,
author = {Fountoulakis, Kimon and Kundu, Abhisek and Kontopoulou, Eugenia-Maria and Drineas, Petros},
title = {A Randomized Rounding Algorithm for Sparse PCA},
year = {2017},
issue_date = {April 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3046948},
doi = {10.1145/3046948},
abstract = {We present and analyze a simple, two-step algorithm to approximate the optimal solution of the sparse PCA problem. In the proposed approach, we first solve an ℓ1-penalized version of the NP-hard sparse PCA optimization problem and then we use a randomized rounding strategy to sparsify the resulting dense solution. Our main theoretical result guarantees an additive error approximation and provides a tradeoff between sparsity and accuracy. Extensive experimental evaluation indicates that the proposed approach is competitive in practice, even compared to state-of-the-art toolboxes such as Spasm.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {38},
numpages = {26},
keywords = {rounding randomized algorithm, Sparce pca}
}

@article{10.1145/3022669,
author = {Liu, Xutong and Chen, Feng and Lu, Yen-Cheng and Lu, Chang-Tien},
title = {Spatial Prediction for Multivariate Non-Gaussian Data},
year = {2017},
issue_date = {April 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3022669},
doi = {10.1145/3022669},
abstract = {With the ever increasing volume of geo-referenced datasets, there is a real need for better statistical estimation and prediction techniques for spatial analysis. Most existing approaches focus on predicting multivariate Gaussian spatial processes, but as the data may consist of non-Gaussian (or mixed type) variables, this creates two challenges: (1) how to accurately capture the dependencies among different data types, both Gaussian and non-Gaussian; and (2) how to efficiently predict multivariate non-Gaussian spatial processes. In this article, we propose a generic approach for predicting multiple response variables of mixed types. The proposed approach accurately captures cross-spatial dependencies among response variables and reduces the computational burden by projecting the spatial process to a lower dimensional space with knot-based techniques. Efficient approximations are provided to estimate posterior marginals of latent variables for the predictive process, and extensive experimental evaluations based on both simulation and real-life datasets are provided to demonstrate the effectiveness and efficiency of this new approach.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {36},
numpages = {27},
keywords = {Approximate bayesian inference, Gaussian and non-Gaussian processes, Laplace approximation, computational statistics, geostatistics, predictive process model}
}

@article{10.1145/3046941,
author = {Liu, Qi and Xiang, Biao and Yuan, Nicholas Jing and Chen, Enhong and Xiong, Hui and Zheng, Yi and Yang, Yu},
title = {An Influence Propagation View of PageRank},
year = {2017},
issue_date = {April 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3046941},
doi = {10.1145/3046941},
abstract = {For a long time, PageRank has been widely used for authority computation and has been adopted as a solid baseline for evaluating social influence related applications. However, when measuring the authority of network nodes, the traditional PageRank method does not take the nodes’ prior knowledge into consideration. Also, the connection between PageRank and social influence modeling methods is not clearly established. To that end, this article provides a focused study on understanding PageRank as well as the relationship between PageRank and social influence analysis. Along this line, we first propose a linear social influence model and reveal that this model generalizes the PageRank-based authority computation by introducing some constraints. Then, we show that the authority computation by PageRank can be enhanced if exploiting more reasonable constraints (e.g., from prior knowledge). Next, to deal with the computational challenge of linear model with general constraints, we provide an upper bound for identifying nodes with top authorities. Moreover, we extend the proposed linear model for better measuring the authority of the given node sets, and we also demonstrate the way to quickly identify the top authoritative node sets. Finally, extensive experimental evaluations on four real-world networks validate the effectiveness of the proposed linear model with respect to different constraint settings. The results show that the methods with more reasonable constraints can lead to better ranking and recommendation performance. Meanwhile, the upper bounds formed by PageRank values could be used to quickly locate the nodes and node sets with the highest authorities.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {30},
numpages = {30},
keywords = {priors, PageRank, upper bounds, authority, social influence propagation}
}

@article{10.1145/2996197,
author = {Guo, Ting and Wu, Jia and Zhu, Xingquan and Zhang, Chengqi},
title = {Combining Structured Node Content and Topology Information for Networked Graph Clustering},
year = {2017},
issue_date = {April 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2996197},
doi = {10.1145/2996197},
abstract = {Graphs are popularly used to represent objects with shared dependency relationships. To date, all existing graph clustering algorithms consider each node as a single attribute or a set of independent attributes, without realizing that content inside each node may also have complex structures. In this article, we formulate a new networked graph clustering task where a network contains a set of inter-connected (or networked) super-nodes, each of which is a single-attribute graph. The new super-node representation is applicable to many real-world applications, such as a citation network where each node denotes a paper whose content can be described as a graph, and citation relationships between papers form a networked graph (i.e., a super-graph). Networked graph clustering aims to find similar node groups, each of which contains nodes with similar content and structure information. The main challenge is to properly calculate the similarity between super-nodes for clustering. To solve the problem, we propose to characterize node similarity by integrating structure and content information of each super-node. To measure node content similarity, we use cosine distance by considering overlapped attributes between two super-nodes. To measure structure similarity, we propose an Attributed Random Walk Kernel (ARWK) to calculate the similarity between super-nodes. Detailed node content analysis is also included to build relationships between super-nodes with shared internal structure information, so the structure similarity can be calculated in a precise way. By integrating the structure similarity and content similarity as one matrix, the spectral clustering is used to achieve networked graph clustering. Our method enjoys sound theoretical properties, including bounded similarities and better structure similarity assessment than traditional graph clustering methods. Experiments on real-world applications demonstrate that our method significantly outperforms baseline approaches.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {29},
numpages = {29},
keywords = {Networked graphs, topology, super-nodes, clustering, kernel}
}

@article{10.1145/3046791,
author = {Rozenshtein, Polina and Tatti, Nikolaj and Gionis, Aristides},
title = {Finding Dynamic Dense Subgraphs},
year = {2017},
issue_date = {April 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3046791},
doi = {10.1145/3046791},
abstract = {Online social networks are often defined by considering interactions of entities at an aggregate level. For example, a call graph is formed among individuals who have called each other at least once; or at least k times. Similarly, in social-media platforms, we consider implicit social networks among users who have interacted in some way, e.g., have made a conversation, have commented to the content of each other, and so on. Such definitions have been used widely in the literature and they have offered significant insights regarding the structure of social networks. However, it is obvious that they suffer from a severe limitation: They neglect the precise time that interactions among the network entities occur.In this article, we consider interaction networks, where the data description contains not only information about the underlying topology of the social network, but also the exact time instances that network entities interact. In an interaction network, an edge is associated with a timestamp, and multiple edges may occur for the same pair of entities. Consequently, interaction networks offer a more fine-grained representation, which can be leveraged to reveal otherwise hidden dynamic phenomena.In the setting of interaction networks, we study the problem of discovering dynamic dense subgraphs whose edges occur in short time intervals. We view such subgraphs as fingerprints of dynamic activity occurring within network communities. Such communities represent groups of individuals who interact with each other in specific time instances, for example, a group of employees who work on a project and whose interaction intensifies before certain project milestones. We prove that the problem we define is NP-hard, and we provide efficient algorithms by adapting techniques for finding dense subgraphs. We also show how to speed-up the proposed methods by exploiting concavity properties of our objective function and by the means of fractional programming. We perform extensive evaluation of the proposed methods on synthetic and real datasets, which demonstrates the validity of our approach and shows that our algorithms can be used to obtain high-quality results.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {27},
numpages = {30},
keywords = {dynamic graphs, community discovery, interaction networks, time-evolving networks, Graph mining, social-network analysis, dense subgraphs}
}

@article{10.1145/3003728,
author = {Feng, Shanshan and Cao, Jian and Wang, Jie and Qian, Shiyou},
title = {Recommendations Based on Comprehensively Exploiting the Latent Factors Hidden in Items’ Ratings and Content},
year = {2017},
issue_date = {April 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3003728},
doi = {10.1145/3003728},
abstract = {To improve the performance of recommender systems in a practical manner, several hybrid approaches have been developed by considering item ratings and content information simultaneously. However, most of these hybrid approaches make recommendations based on aggregating different recommendation techniques using various strategies, rather than considering joint modeling of the item’s ratings and content, and thus fail to detect many latent factors that could potentially improve the performance of the recommender systems. For this reason, these approaches continue to suffer from data sparsity and do not work well for recommending items to individual users. A few studies try to describe a user’s preference by detecting items’ latent features from content-description texts as compensation for the sparse ratings. Unfortunately, most of these methods are still generally unable to accomplish recommendation tasks well for two reasons: (1) they learn latent factors from text descriptions or user--item ratings independently, rather than combining them together; and (2) influences of latent factors hidden in texts and ratings are not fully explored. In this study, we propose a probabilistic approach that we denote as latent random walk (LRW) based on the combination of an integrated latent topic model and random walk (RW) with the restart method, which can be used to rank items according to expected user preferences by detecting both their explicit and implicit correlative information, in order to recommend top-ranked items to potentially interested users. As presented in this article, the goal of this work is to comprehensively discover latent factors hidden in items’ ratings and content in order to alleviate the data sparsity problem and to improve the performance of recommender systems. The proposed topic model provides a generative probabilistic framework that discovers users’ implicit preferences and items’ latent features simultaneously by exploiting both ratings and item content information. On the basis of this probabilistic framework, RW can predict a user’s preference for unrated items by discovering global latent relations. In order to show the efficiency of the proposed approach, we test LRW and other state-of-the-art methods on three real-world datasets, namely, CAMRa2011, Yahoo!, and APP. The experiments indicate that our approach outperforms all comparative methods and, in addition, that it is less sensitive to the data sparsity problem, thus demonstrating the robustness of LRW for recommendation tasks.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {35},
numpages = {27},
keywords = {probabilistic topic model, correlative information discovering, random walk with restart, latent factors detection, Recommender system}
}

@article{10.1145/3022668,
author = {Sariy\"{u}ce, Ahmet Erdem and Kaya, Kamer and Saule, Erik and \c{C}ataly\"{u}rek, \"{U}mit V.},
title = {Graph Manipulations for Fast Centrality Computation},
year = {2017},
issue_date = {April 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3022668},
doi = {10.1145/3022668},
abstract = {The betweenness and closeness metrics are widely used metrics in many network analysis applications. Yet, they are expensive to compute. For that reason, making the betweenness and closeness centrality computations faster is an important and well-studied problem. In this work, we propose the framework BADIOS that manipulates the graph by compressing it and splitting into pieces so that the centrality computation can be handled independently for each piece. Experimental results show that the proposed techniques can be a great arsenal to reduce the centrality computation time for various types and sizes of networks. In particular, it reduces the betweenness centrality computation time of a 4.6 million edges graph from more than 5 days to less than 16 hours. For the same graph, the closeness computation time is decreased from more than 3 days to 6 hours (12.7x speedup).},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {26},
numpages = {25},
keywords = {shortest path, closeness centrality, Betweenness centrality}
}

@article{10.1145/3022185,
author = {Liu, Guannan and Fu, Yanjie and Chen, Guoqing and Xiong, Hui and Chen, Can},
title = {Modeling Buying Motives for Personalized Product Bundle Recommendation},
year = {2017},
issue_date = {April 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3022185},
doi = {10.1145/3022185},
abstract = {Product bundling is a marketing strategy that offers several products/items for sale as one bundle. While the bundling strategy has been widely used, less efforts have been made to understand how items should be bundled with respect to consumers’ preferences and buying motives for product bundles. This article investigates the relationships between the items that are bought together within a product bundle. To that end, each purchased product bundle is formulated as a bundle graph with items as nodes and the associations between pairs of items in the bundle as edges. The relationships between items can be analyzed by the formation of edges in bundle graphs, which can be attributed to the associations of feature aspects. Then, a probabilistic model BPM (Bundle Purchases with Motives) is proposed to capture the composition of each bundle graph, with two latent factors node-type and edge-type introduced to describe the feature aspects and relationships respectively. Furthermore, based on the preferences inferred from the model, an approach for recommending items to form product bundles is developed by estimating the probability that a consumer would buy an associative item together with the item already bought in the shopping cart. Finally, experimental results on real-world transaction data collected from well-known shopping sites show the effectiveness advantages of the proposed approach over other baseline methods. Moreover, the experiments also show that the proposed model can explain consumers’ buying motives for product bundles in terms of different node-types and edge-types.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {28},
numpages = {26},
keywords = {probabilistic graphical model, Product bundle, recommendation, buying motives}
}

@article{10.1145/3003730,
author = {Peng, Chong and Kang, Zhao and Hu, Yunhong and Cheng, Jie and Cheng, Qiang},
title = {Robust Graph Regularized Nonnegative Matrix Factorization for Clustering},
year = {2017},
issue_date = {April 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3003730},
doi = {10.1145/3003730},
abstract = {Matrix factorization is often used for data representation in many data mining and machine-learning problems. In particular, for a dataset without any negative entries, nonnegative matrix factorization (NMF) is often used to find a low-rank approximation by the product of two nonnegative matrices. With reduced dimensions, these matrices can be effectively used for many applications such as clustering. The existing methods of NMF are often afflicted with their sensitivity to outliers and noise in the data. To mitigate this drawback, in this paper, we consider integrating NMF into a robust principal component model, and design a robust formulation that effectively captures noise and outliers in the approximation while incorporating essential nonlinear structures. A set of comprehensive empirical evaluations in clustering applications demonstrates that the proposed method has strong robustness to gross errors and superior performance to current state-of-the-art methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {33},
numpages = {30},
keywords = {clustering, manifold, Nonnegative factorization, robust principal component analysis}
}

@article{10.1145/3003729,
author = {Wang, Sen and Li, Xue and Chang*, Xiaojun and Yao, Lina and Sheng, Quan Z. and Long, Guodong},
title = {Learning Multiple Diagnosis Codes for ICU Patients with Local Disease Correlation Mining},
year = {2017},
issue_date = {April 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3003729},
doi = {10.1145/3003729},
abstract = {In the era of big data, a mechanism that can automatically annotate disease codes to patients’ records in the medical information system is in demand. The purpose of this work is to propose a framework that automatically annotates the disease labels of multi-source patient data in Intensive Care Units (ICUs). We extract features from two main sources, medical charts and notes. The Bag-of-Words model is used to encode the features. Unlike most of the existing multi-label learning algorithms that globally consider correlations between diseases, our model learns disease correlation locally in the patient data. To achieve this, we derive a local disease correlation representation to enrich the discriminant power of each patient data. This representation is embedded into a unified multi-label learning framework. We develop an alternating algorithm to iteratively optimize the objective function. Extensive experiments have been conducted on a real-world ICU database. We have compared our algorithm with representative multi-label learning algorithms. Evaluation results have shown that our proposed method has state-of-the-art performance in the annotation of multiple diagnostic codes for ICU patients. This study suggests that problems in the automated diagnosis code annotation can be reliably addressed by using a multi-label learning model that exploits disease correlation. The findings of this study will greatly benefit health care and management in ICU considering that the automated diagnosis code annotation can significantly improve the quality and management of health care for both patients and caregivers.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {31},
numpages = {21},
keywords = {local correlation exploiting, Diagnosis code annotation, pattern discovery, MIMIC II database, ICU data mining, multi-label learning}
}

@article{10.1145/2992785,
author = {Bae, Seung-Hee and Halperin, Daniel and West, Jevin D. and Rosvall, Martin and Howe, Bill},
title = {Scalable and Efficient Flow-Based Community Detection for Large-Scale Graph Analysis},
year = {2017},
issue_date = {April 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2992785},
doi = {10.1145/2992785},
abstract = {Community detection is an increasingly popular approach to uncover important structures in large networks. Flow-based community detection methods rely on communication patterns of the network rather than structural properties to determine communities. The Infomap algorithm in particular optimizes a novel objective function called the map equation and has been shown to outperform other approaches in third-party benchmarks. However, Infomap and its variants are inherently sequential, limiting their use for large-scale graphs.In this article, we propose a novel algorithm to optimize the map equation called RelaxMap. RelaxMap provides two important improvements over Infomap: parallelization, so that the map equation can be optimized over much larger graphs, and prioritization, so that the most important work occurs first, iterations take less time, and the algorithm converges faster. We implement these techniques using OpenMP on shared-memory multicore systems, and evaluate our approach on a variety of graphs from standard graph clustering benchmarks as well as real graph datasets. Our evaluation shows that both techniques are effective: RelaxMap achieves 70% parallel efficiency on eight cores, and prioritization improves algorithm performance by an additional 20--50% on average, depending on the graph properties. Additionally, RelaxMap converges in the similar number of iterations and provides solutions of equivalent quality as the serial Infomap implementation.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {32},
numpages = {30},
keywords = {parallelization, graph analysis, prioritization, Community detection}
}

@article{10.1145/2953881,
author = {Wang, Chenguang and Song, Yangqiu and Roth, Dan and Zhang, Ming and Han, Jiawei},
title = {World Knowledge as Indirect Supervision for Document Clustering},
year = {2016},
issue_date = {December 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2953881},
doi = {10.1145/2953881},
abstract = {One of the key obstacles in making learning protocols realistic in applications is the need to supervise them, a costly process that often requires hiring domain experts. We consider the framework to use the world knowledge as indirect supervision. World knowledge is general-purpose knowledge, which is not designed for any specific domain. Then, the key challenges are how to adapt the world knowledge to domains and how to represent it for learning. In this article, we provide an example of using world knowledge for domain-dependent document clustering. We provide three ways to specify the world knowledge to domains by resolving the ambiguity of the entities and their types, and represent the data with world knowledge as a heterogeneous information network. Then, we propose a clustering algorithm that can cluster multiple types and incorporate the sub-type information as constraints. In the experiments, we use two existing knowledge bases as our sources of world knowledge. One is Freebase, which is collaboratively collected knowledge about entities and their organizations. The other is YAGO2, a knowledge base automatically extracted from Wikipedia and maps knowledge to the linguistic knowledge base, WordNet. Experimental results on two text benchmark datasets (20newsgroups and RCV1) show that incorporating world knowledge as indirect supervision can significantly outperform the state-of-the-art clustering algorithms as well as clustering algorithms enhanced with world knowledge features.A preliminary version of this work appeared in the proceedings of KDD 2015 [Wang et al. 2015a]. This journal version has made several major improvements. First, we have proposed a new and general learning framework for machine learning with world knowledge as indirect supervision, where document clustering is a special case in the original paper. Second, in order to make our unsupervised semantic parsing method more understandable, we add several real cases from the original sentences to the resulting logic forms with all the necessary information. Third, we add details of the three semantic filtering methods and conduct deep analysis of the three semantic filters, by using case studies to show why the conceptualization-based semantic filter can produce more accurate indirect supervision. Finally, in addition to the experiment on 20 newsgroup data and Freebase, we have extended the experiments on clustering results by using all the combinations of text (20 newsgroup, MCAT, CCAT, ECAT) and world knowledge sources (Freebase, YAGO2).},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {13},
numpages = {36},
keywords = {document clustering, heterogeneous information network, World knowledge, knowledge graph, knowledge base}
}

@article{10.1145/2988235,
author = {Wang, Zhongyuan and Wang, Fang and Wang, Haixun and Hu, Zhirui and Yan, Jun and Li, Fangtao and Wen, Ji-Rong and Li, Zhoujun},
title = {Unsupervised Head--Modifier Detection in Search Queries},
year = {2016},
issue_date = {December 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2988235},
doi = {10.1145/2988235},
abstract = {Interpreting the user intent in search queries is a key task in query understanding. Query intent classification has been widely studied. In this article, we go one step further to understand the query from the view of head--modifier analysis. For example, given the query “popular iphone 5 smart cover,” instead of using coarse-grained semantic classes (e.g., find electronic product), we interpret that “smart cover” is the head or the intent of the query and “iphone 5” is its modifier. Query head--modifier detection can help search engines to obtain particularly relevant content, which is also important for applications such as ads matching and query recommendation. We introduce an unsupervised semantic approach for query head--modifier detection. First, we mine a large number of instance level head--modifier pairs from search log. Then, we develop a conceptualization mechanism to generalize the instance level pairs to concept level. Finally, we derive weighted concept patterns that are concise, accurate, and have strong generalization power in head--modifier detection. The developed mechanism has been used in production for search relevance and ads matching. We use extensive experiment results to demonstrate the effectiveness of our approach.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {19},
numpages = {28},
keywords = {Query intent, concept pattern, head and modifier, knowledge modeling}
}

@article{10.1145/2994605,
author = {Chang, Yi and Yamada, Makoto and Ortega, Antonio and Liu, Yan},
title = {Lifecycle Modeling for Buzz Temporal Pattern Discovery},
year = {2016},
issue_date = {December 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2994605},
doi = {10.1145/2994605},
abstract = {In social media analysis, one critical task is detecting a burst of topics or buzz, which is reflected by extremely frequent mentions of certain keywords in a short-time interval. Detecting buzz not only provides useful insights into the information propagation mechanism, but also plays an essential role in preventing malicious rumors. However, buzz modeling is a challenging task because a buzz time-series often exhibits sudden spikes and heavy tails, wherein most existing time-series models fail. In this article, we propose novel buzz modeling approaches that capture the rise and fade temporal patterns via Product Lifecycle (PLC) model, a classical concept in economics. More specifically, we propose to model multiple peaks in buzz time-series with PLC mixture or PLC group mixture and develop a probabilistic graphical model (K-Mixture of Product Lifecycle (K-MPLC) to automatically discover inherent lifecycle patterns within a collection of buzzes. Furthermore, we effectively utilize the model parameters of PLC mixture or PLC group mixture for burst prediction. Our experimental results show that our proposed methods significantly outperform existing leading approaches on buzz clustering and buzz-type prediction.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {20},
numpages = {24},
keywords = {buzz type prediction, buzz clustering, Time-series modeling}
}

@article{10.1145/2996196,
author = {Wei, Qiang and Qiao, Dandan and Zhang, Jin and Chen, Guoqing and Guo, Xunhua},
title = {A Novel Bipartite Graph Based Competitiveness Degree Analysis from Query Logs},
year = {2016},
issue_date = {December 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2996196},
doi = {10.1145/2996196},
abstract = {Competitiveness degree analysis is a focal point of business strategy and competitive intelligence, aimed to help managers closely monitor to what extent their rivals are competing with them. This article proposes a novel method, namely BCQ, to measure the competitiveness degree between peers from query logs as an important form of user generated contents, which reflects the “wisdom of crowds” from the search engine users’ perspective. In doing so, a bipartite graph model is developed to capture the competitive relationships through conjoint attributes hidden in query logs, where the notion of competitiveness degree for entity pairs is introduced, and then used to identify the competitive paths mapped in the bipartite graph. Subsequently, extensive experiments are conducted to demonstrate the effectiveness of BCQ to quantify the competitiveness degrees. Experimental results reveal that BCQ can well support competitors ranking, which is helpful for devising competitive strategies and pursuing market performance. In addition, efficiency experiments on synthetic data show a good scalability of BCQ on large scale of query logs.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {21},
numpages = {25},
keywords = {competitiveness degree, query logs, Competitive intelligence, bipartite graph}
}

@article{10.1145/2997657,
author = {Lorenzetti, Carlos and Maguitman, Ana and Leake, David and Menczer, Filippo and Reichherzer, Thomas},
title = {Mining for Topics to Suggest Knowledge Model Extensions},
year = {2016},
issue_date = {December 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2997657},
doi = {10.1145/2997657},
abstract = {Electronic concept maps, interlinked with other concept maps and multimedia resources, can provide rich knowledge models to capture and share human knowledge. This article presents and evaluates methods to support experts as they extend existing knowledge models, by suggesting new context-relevant topics mined from Web search engines. The task of generating topics to support knowledge model extension raises two research questions: first, how to extract topic descriptors and discriminators from concept maps; and second, how to use these topic descriptors and discriminators to identify candidate topics on the Web with the right balance of novelty and relevance. To address these questions, this article first develops the theoretical framework required for a “topic suggester” to aid information search in the context of a knowledge model under construction. It then presents and evaluates algorithms based on this framework and applied in Extender, an implemented tool for topic suggestion. Extender has been developed and tested within CmapTools, a widely used system for supporting knowledge modeling using concept maps. However, the generality of the algorithms makes them applicable to a broad class of knowledge modeling systems, and to Web search in general.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {23},
numpages = {30},
keywords = {intelligent suggesters, web mining, knowledge discovery, knowledge construction, Concept mapping}
}

@article{10.1145/2987376,
author = {Afrati, Foto and Dolev, Shlomi and Korach, Ephraim and Sharma, Shantanu and Ullman, Jeffrey D.},
title = {Assignment Problems of Different-Sized Inputs in MapReduce},
year = {2016},
issue_date = {December 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2987376},
doi = {10.1145/2987376},
abstract = {A MapReduce algorithm can be described by a mapping schema, which assigns inputs to a set of reducers, such that for each required output there exists a reducer that receives all the inputs participating in the computation of this output. Reducers have a capacity that limits the sets of inputs they can be assigned. However, individual inputs may vary in terms of size. We consider, for the first time, mapping schemas where input sizes are part of the considerations and restrictions. One of the significant parameters to optimize in any MapReduce job is communication cost between the map and reduce phases. The communication cost can be optimized by minimizing the number of copies of inputs sent to the reducers. The communication cost is closely related to the number of reducers of constrained capacity that are used to accommodate appropriately the inputs, so that the requirement of how the inputs must meet in a reducer is satisfied. In this work, we consider a family of problems where it is required that each input meets with each other input in at least one reducer. We also consider a slightly different family of problems in which each input of a list, X, is required to meet each input of another list, Y, in at least one reducer. We prove that finding an optimal mapping schema for these families of problems is NP-hard, and present a bin-packing-based approximation algorithm for finding a near optimal mapping schema.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {18},
numpages = {35},
keywords = {Distributed computing, mapping schema, reducer capacity, MapReduce algorithms, and reducer capacity and communication cost trade-off}
}

@article{10.1145/2996467,
author = {Pei, Yuanli and Fern, Xiaoli Z. and Tjahja, Teresa Vania and Rosales, R\'{o}mer},
title = {Comparing Clustering with Pairwise and Relative Constraints: A Unified Framework},
year = {2016},
issue_date = {December 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2996467},
doi = {10.1145/2996467},
abstract = {Clustering can be improved with the help of side information about the similarity relationships among instances. Such information has been commonly represented by two types of constraints: pairwise constraints and relative constraints, regarding similarities about instance pairs and triplets, respectively. Prior work has mostly considered these two types of constraints separately and developed individual algorithms to learn from each type. In practice, however, it is critical to understand/compare the usefulness of the two types of constraints as well as the cost of acquiring them, which has not been studied before. This paper provides an extensive comparison of clustering with these two types of constraints. Specifically, we compare their impacts both on human users that provide such constraints and on the learning system that incorporates such constraints into clustering. In addition, to ensure that the comparison of clustering is performed on equal ground (without the potential bias introduced by different learning algorithms), we propose a probabilistic semi-supervised clustering framework that can learn from either type of constraints. Our experiments demonstrate that the proposed semi-supervised clustering framework is highly effective at utilizing both types of constraints to aid clustering. Our user study provides valuable insights regarding the impact of the constraints on human users, and our experiments on clustering with the human-labeled constraints reveal that relative constraint is often more efficient at improving clustering.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {22},
numpages = {26},
keywords = {Semi-supervised clustering, relative constraints, pairwise constraints}
}

@article{10.1145/2976744,
author = {Yu, Kui and Wu, Xindong and Ding, Wei and Pei, Jian},
title = {Scalable and Accurate Online Feature Selection for Big Data},
year = {2016},
issue_date = {December 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2976744},
doi = {10.1145/2976744},
abstract = {Feature selection is important in many big data applications. Two critical challenges closely associate with big data. First, in many big data applications, the dimensionality is extremely high, in millions, and keeps growing. Second, big data applications call for highly scalable feature selection algorithms in an online manner such that each feature can be processed in a sequential scan. We present SAOLA, a <underline>S</underline>calable and <underline>A</underline>ccurate <underline>O</underline>n<underline>L</underline>ine <underline>A</underline>pproach for feature selection in this paper. With a theoretical analysis on bounds of the pairwise correlations between features, SAOLA employs novel pairwise comparison techniques and maintains a parsimonious model over time in an online manner. Furthermore, to deal with upcoming features that arrive by groups, we extend the SAOLA algorithm, and then propose a new group-SAOLA algorithm for online group feature selection. The group-SAOLA algorithm can online maintain a set of feature groups that is sparse at the levels of both groups and individual features simultaneously. An empirical study using a series of benchmark real datasets shows that our two algorithms, SAOLA and group-SAOLA, are scalable on datasets of extremely high dimensionality and have superior performance over the state-of-the-art feature selection methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {16},
numpages = {39},
keywords = {Online feature selection, big data, extremely high dimensionality, group features}
}

@article{10.1145/2997656,
author = {Kumar, Dheeraj and Bezdek, James C. and Rajasegarar, Sutharshan and Palaniswami, Marimuthu and Leckie, Christopher and Chan, Jeffrey and Gubbi, Jayavardhana},
title = {Adaptive Cluster Tendency Visualization and Anomaly Detection for Streaming Data},
year = {2016},
issue_date = {December 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2997656},
doi = {10.1145/2997656},
abstract = {The growth in pervasive network infrastructure called the Internet of Things (IoT) enables a wide range of physical objects and environments to be monitored in fine spatial and temporal detail. The detailed, dynamic data that are collected in large quantities from sensor devices provide the basis for a variety of applications. Automatic interpretation of these evolving large data is required for timely detection of interesting events. This article develops and exemplifies two new relatives of the visual assessment of tendency (VAT) and improved visual assessment of tendency (iVAT) models, which uses cluster heat maps to visualize structure in static datasets. One new model is initialized with a static VAT/iVAT image, and then incrementally (hence inc-VAT/inc-iVAT) updates the current minimal spanning tree (MST) used by VAT with an efficient edge insertion scheme. Similarly, dec-VAT/dec-iVAT efficiently removes a node from the current VAT MST. A sequence of inc-iVAT/dec-iVAT images can be used for (visual) anomaly detection in evolving data streams and for sliding window based cluster assessment for time series data. The method is illustrated with four real datasets (three of them being smart city IoT data). The evaluation demonstrates the algorithms’ ability to successfully isolate anomalies and visualize changing cluster structure in the streaming data.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {24},
numpages = {40},
keywords = {cluster heat maps, sliding window based time series clustering, smart city streaming data analysis, internet of things (IoT), online anomaly detection, Visual assessment of clusters in streaming data}
}

@article{10.1145/2968451,
author = {Smith, Laura M. and Zhu, Linhong and Lerman, Kristina and Percus, Allon G.},
title = {Partitioning Networks with Node Attributes by Compressing Information Flow},
year = {2016},
issue_date = {December 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2968451},
doi = {10.1145/2968451},
abstract = {Real-world networks are often organized as modules or communities of similar nodes that serve as functional units. These networks are also rich in content, with nodes having distinguished features or attributes. In order to discover a network’s modular structure, it is necessary to take into account not only its links but also node attributes. We describe an information-theoretic method that identifies modules by compressing descriptions of information flow on a network. Our formulation introduces node content into the description of information flow, which we then minimize to discover groups of nodes with similar attributes that also tend to trap the flow of information. The method is conceptually simple and does not require ad-hoc parameters to specify the number of modules or to control the relative contribution of links and node attributes to network structure. We apply the proposed method to partition real-world networks with known community structure. We demonstrate that adding node attributes helps recover the underlying community structure in content-rich networks more effectively than using links alone. In addition, we show that our method is faster and more accurate than alternative state-of-the-art algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = nov,
articleno = {15},
numpages = {26},
keywords = {community detection, rich networks, Graph partitioning, information theory}
}

@article{10.1145/2935750,
author = {Gao, Zekai J. and Jermaine, Chris},
title = {Distributed Algorithms for Computing Very Large Thresholded Covariance Matrices},
year = {2016},
issue_date = {December 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2935750},
doi = {10.1145/2935750},
abstract = {Computation of covariance matrices from observed data is an important problem, as such matrices are used in applications such as principal component analysis (PCA), linear discriminant analysis (LDA), and increasingly in the learning and application of probabilistic graphical models. However, computing an empirical covariance matrix is not always an easy problem. There are two key difficulties associated with computing such a matrix from a very high-dimensional dataset. The first problem is over-fitting. For a p-dimensional covariance matrix, there are p(p − 1)/2 unique, off-diagonal entries in the empirical covariance matrix undefined for large p (say, p > 105), the size n of the dataset is often much smaller than the number of covariances to compute. Over-fitting is a concern in any situation in which the number of parameters learned can greatly exceed the size of the dataset. Thus, there are strong theoretical reasons to expect that for high-dimensional data—even Gaussian data—the empirical covariance matrix is not a good estimate for the true covariance matrix underlying the generative process. The second problem is computational. Computing a covariance matrix takes O(np2) time. For large p (greater than 10,000) and n much greater than p, this is debilitating. In this article, we consider how both of these difficulties can be handled simultaneously. Specifically, a key regularization technique for high-dimensional covariance estimation is thresholding, in which the smallest or least significant entries in the covariance matrix are simply dropped and replaced with the value 0. This suggests an obvious way to address the computational difficulty as well: First, compute the identities of the K entries in the covariance matrix that are actually important in the sense that they will not be removed during thresholding, and then in a second step, compute the values of those entries. This can be done in O(Kn) time. If K ≪ p2 and the identities of the important entries can be computed in reasonable time, then this is a big win. The key technical contribution of this article is the design and implementation of two different distributed algorithms for approximating the identities of the important entries quickly, using sampling. We have implemented these methods and tested them using an 800-core compute cluster. Experiments have been run using real datasets having millions of data points and up to 40, 000 dimensions. These experiments show that the proposed methods are both accurate and efficient.},
journal = {ACM Trans. Knowl. Discov. Data},
month = nov,
articleno = {12},
numpages = {25},
keywords = {thresholding, text processing, distributed algorithm, Covariance matrices, sampling}
}

@article{10.1145/2983533,
author = {Liu, Bin and Wu, Yao and Gong, Neil Zhenqiang and Wu, Junjie and Xiong, Hui and Ester, Martin},
title = {Structural Analysis of User Choices for Mobile App Recommendation},
year = {2016},
issue_date = {December 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2983533},
doi = {10.1145/2983533},
abstract = {Advances in smartphone technology have promoted the rapid development of mobile apps. However, the availability of a huge number of mobile apps in application stores has imposed the challenge of finding the right apps to meet the user needs. Indeed, there is a critical demand for personalized app recommendations. Along this line, there are opportunities and challenges posed by two unique characteristics of mobile apps. First, app markets have organized apps in a hierarchical taxonomy. Second, apps with similar functionalities are competing with each other. Although there are a variety of approaches for mobile app recommendations, these approaches do not have a focus on dealing with these opportunities and challenges. To this end, in this article, we provide a systematic study for addressing these challenges. Specifically, we develop a structural user choice model (SUCM) to learn fine-grained user preferences by exploiting the hierarchical taxonomy of apps as well as the competitive relationships among apps. Moreover, we design an efficient learning algorithm to estimate the parameters for the SUCM model. Finally, we perform extensive experiments on a large app adoption dataset collected from Google Play. The results show that SUCM consistently outperforms state-of-the-art Top-N recommendation methods by a significant margin.},
journal = {ACM Trans. Knowl. Discov. Data},
month = nov,
articleno = {17},
numpages = {23},
keywords = {structural choices, hierarchy structure, Recommender systems, mobile apps}
}

@article{10.1145/2953883,
author = {Chakraborty, Tanmoy and Srinivasan, Sriram and Ganguly, Niloy and Mukherjee, Animesh and Bhowmick, Sanjukta},
title = {Permanence and Community Structure in Complex Networks},
year = {2016},
issue_date = {December 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {11},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2953883},
doi = {10.1145/2953883},
abstract = {The goal of community detection algorithms is to identify densely connected units within large networks. An implicit assumption is that all the constituent nodes belong equally to their associated community. However, some nodes are more important in the community than others. To date, efforts have been primarily made to identify communities as a whole, rather than understanding to what extent an individual node belongs to its community. Therefore, most metrics for evaluating communities, for example modularity, are global. These metrics produce a score for each community, not for each individual node. In this article, we argue that the belongingness of nodes in a community is not uniform. We quantify the degree of belongingness of a vertex within a community by a new vertex-based metric called permanence.The central idea of permanence is based on the observation that the strength of membership of a vertex to a community depends upon two factors (i) the extent of connections of the vertex within its community versus outside its community, and (ii) how tightly the vertex is connected internally. We present the formulation of permanence based on these two quantities. We demonstrate that compared to other existing metrics (such as modularity, conductance, and cut-ratio), the change in permanence is more commensurate to the level of perturbation in ground-truth communities. We discuss how permanence can help us understand and utilize the structure and evolution of communities by demonstrating that it can be used to -- (i) measure the persistence of a vertex in a community, (ii) design strategies to strengthen the community structure, (iii) explore the core-periphery structure within a community, and (iv) select suitable initiators for message spreading.We further show that permanence is an excellent metric for identifying communities. We demonstrate that the process of maximizing permanence (abbreviated as MaxPerm) produces meaningful communities that concur with the ground-truth community structure of the networks more accurately than eight other popular community detection algorithms. Finally, we provide mathematical proofs to demonstrate the correctness of finding communities by maximizing permanence. In particular, we show that the communities obtained by this method are (i) less affected by the changes in vertex ordering, and (ii) more resilient to resolution limit, degeneracy of solutions, and asymptotic growth of values.},
journal = {ACM Trans. Knowl. Discov. Data},
month = nov,
articleno = {14},
numpages = {34},
keywords = {community evaluation metric, Permanence, modularity, community discovery}
}

@article{10.1145/3001938,
author = {Zhu, Wen-Yuan and Peng, Wen-Chih and Chen, Ling-Jyh and Zheng

license_type: permissive

extension: bib