text:
145/3372407},
doi = {10.1145/3372407},
abstract = {Social Internet of Things has recently become a promising paradigm for augmenting the capability of humans and devices connected in the networks to provide services. In social Internet of Things network, crowdsourcing that collects the intelligence of the human crowd has served as a powerful tool for data acquisition and distributed computing. To support critical applications (e.g., a recommendation system and assessing the inequality of urban perception), in this article, we shall focus on the collaborative ranking problems for user preference prediction from crowdsourced pairwise comparisons. Based on the Bradley--Terry--Luce (BTL) model, a maximum likelihood estimation (MLE) is proposed via low-rank approach in order to estimate the underlying weight/score matrix, thereby predicting the ranking list for each user. A novel regularized formulation with the smoothed surrogate of elementwise infinity norm is proposed in order to address the unique challenge of the coupled the non-smooth elementwise infinity norm constraint and non-convex low-rank constraint in the MLE problem. We solve the resulting smoothed rank-constrained optimization problem via developing the Riemannian trust-region algorithm on quotient manifolds of fixed-rank matrices, which enjoys the superlinear convergence rate. The admirable performance and algorithmic advantages of the proposed method over the state-of-the-art algorithms are demonstrated via numerical results. Moreover, the proposed method outperforms state-of-the-art algorithms on large collaborative filtering datasets in both success rate of inferring preference and normalized discounted cumulative gain.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {19},
numpages = {26},
keywords = {smoothed matrix manifold optimization, crowdsourced data, low-rank optimization, Ranking, social Internet of Things, pairwise comparison}
}

@article{10.1145/3372406,
author = {Xu, Yanan and Shen, Yanyan and Zhu, Yanmin and Yu, Jiadi},
title = {AR2Net: An Attentive Neural Approach for Business Location Selection with Satellite Data and Urban Data},
year = {2020},
issue_date = {March 2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {14},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3372406},
doi = {10.1145/3372406},
abstract = {Business location selection is crucial to the success of businesses. Traditional approaches like manual survey investigate multiple factors, such as foot traffic, neighborhood structure, and available workforce, which are typically hard to measure. In this article, we propose to explore both satellite data (e.g., satellite images and nighttime light data) and urban data for business location selection tasks of various businesses. We extract discriminative features from the two kinds of data and perform empirical analysis to evaluate the correlation between extracted features and the business popularity of locations. A novel neural network approach named R2Net is proposed to learn deep interactions among features and predict the business popularity of locations. The proposed approach is trained with a regression-and-ranking combined loss function to preserve accurate popularity estimation and the ranking order of locations simultaneously. To support the location selection for multiple businesses, we propose an approach named AR2Net with three attention modules, which enable the approach to focus on different latent features according to business types. Comprehensive experiments on a real-world dataset demonstrate that the satellite features are effective and our models outperform the state-of-the-art methods in terms of four metrics.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {20},
numpages = {28},
keywords = {satellite images, Satellite data, nighttime light, business location selection}
}

@article{10.1145/3369870,
author = {Nie, Feiping and Wang, Zheng and Wang, Rong and Wang, Zhen and Li, Xuelong},
title = {Adaptive Local Linear Discriminant Analysis},
year = {2020},
issue_date = {February 2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {14},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3369870},
doi = {10.1145/3369870},
abstract = {Dimensionality reduction plays a significant role in high-dimensional data processing, and Linear Discriminant Analysis (LDA) is a widely used supervised dimensionality reduction approach. However, a major drawback of LDA is that it is incapable of extracting the local structure information, which is crucial for handling multimodal data. In this article, we propose a novel supervised dimensionality reduction method named Adaptive Local Linear Discriminant Analysis (ALLDA), which adaptively learns a k-nearest neighbors graph from data themselves to extract the local connectivity of data. Furthermore, the original high-dimensional data usually contains noisy and redundant features, which has a negative impact on the evaluation of neighborships and degrades the subsequent classification performance. To address this issue, our method learns the similarity matrix and updates the subspace simultaneously so that the neighborships can be evaluated in the optimal subspaces where the noises have been removed. Through the optimal graph embedding, the underlying sub-manifolds of data in intra-class can be extracted precisely. Meanwhile, an efficient iterative optimization algorithm is proposed to solve the minimization problem. Promising experimental results on synthetic and real-world datasets are provided to evaluate the effectiveness of proposed method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {9},
numpages = {19},
keywords = {linear discriminant analysis, Supervised dimensionality reduction, local connectivity, optimal graph embedding}
}

@article{10.1145/3362158,
author = {Angiulli, Fabrizio},
title = {CFOF: A Concentration Free Measure for Anomaly Detection},
year = {2020},
issue_date = {February 2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {14},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3362158},
doi = {10.1145/3362158},
abstract = {We present a novel notion of outlier, called the Concentration Free Outlier Factor, or CFOF. As a main contribution, we formalize the notion of concentration of outlier scores and theoretically prove that CFOF does not concentrate in the Euclidean space for any arbitrary large dimensionality. To the best of our knowledge, there are no other proposals of data analysis measures related to the Euclidean distance for which it has been provided theoretical evidence that they are immune to the concentration effect. We determine the closed form of the distribution of CFOF scores in arbitrarily large dimensionalities and show that the CFOF score of a point depends on its squared norm standard score and on the kurtosis of the data distribution, thus providing a clear and statistically founded characterization of this notion. Moreover, we leverage this closed form to provide evidence that the definition does not suffer of the hubness problem affecting other measures in high dimensions. We prove that the number of CFOF outliers coming from each cluster is proportional to cluster size and kurtosis, a property that we call semi-locality. We leverage theoretical findings to shed lights on properties of well-known outlier scores. Indeed, we determine that semi-locality characterizes existing reverse nearest neighbor-based outlier definitions, thus clarifying the exact nature of their observed local behavior. We also formally prove that classical distance-based and density-based outliers concentrate both for bounded and unbounded sample sizes and for fixed and variable values of the neighborhood parameter. We introduce the fast-CFOF algorithm for detecting outliers in large high-dimensional dataset. The algorithm has linear cost, supports multi-resolution analysis, and is embarrassingly parallel. Experiments highlight that the technique is able to efficiently process huge datasets and to deal even with large values of the neighborhood parameter, to avoid concentration, and to obtain excellent accuracy.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {4},
numpages = {53},
keywords = {huge datasets, high-dimensional data, Outlier detection, curse of dimensionality, kurtosis, hubness, concentration of distances}
}

@article{10.1145/3369799,
author = {Lu, Xinjiang and Yu, Zhiwen and Liu, Chuanren and Liu, Yanchi and Xiong, Hui and Guo, Bin},
title = {Inferring Lifetime Status of Point-of-Interest: A Multitask Multiclass Approach},
year = {2020},
issue_date = {February 2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {14},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3369799},
doi = {10.1145/3369799},
abstract = {A Point-of-Interest (POI) refers to a specific location that people may find useful or interesting. In modern cities, a large number of POIs emerge, grow, stabilize for a period, then finally disappear. The stages (e.g., emerge and grow) in this process are called lifetime statuses of a POI. While a large body of research has been devoted to identifying and recommending POIs, there are few studies on inferring the lifetime status of POIs. Indeed, the predictive analytics of POI lifetime status can be valuable for various tasks, such as urban planning, business site selection, and real estate appraisal. In this article, we propose a multitask learning approach, named inferring POI lifetime status, to inferring the POI lifetime status with multifaceted data sources. Specifically, we first define three types of POI lifetime status, i.e., booming, decaying, and stable. Then, we formulate a serial classification problem to predict the sequential/successive lifetime statuses of POIs over time. Leveraging geographical data and human mobility data, we examine and integrate three aspects of features related to the prosperity of POIs, i.e., region popularity, region demands, and peer competitiveness. Next, as the booming/decaying POIs are relatively rare in our data, we perform stable class decomposition to alleviate the imbalance between stable POIs and booming/decaying POIs. Finally, we develop a POI lifetime status classifier by exploiting the multitask learning framework as well as the multiclass kernel-based vector machines. We perform extensive experiments using large-scale and real-world datasets of New York City. The experimental results validate the effectiveness of our approach to automatically inferring POI lifetime status.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {10},
numpages = {27},
keywords = {lifetime status, urban computing, Point-of-Interest, multitask learning, multiclass classification}
}

@article{10.1145/3365673,
author = {Mitra, Sayantan and Hasanuzzaman, Mohammed and Saha, Sriparna},
title = {A Unified Multi-View Clustering Algorithm Using Multi-Objective Optimization Coupled with Generative Model},
year = {2020},
issue_date = {February 2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {14},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3365673},
doi = {10.1145/3365673},
abstract = {There is a large body of works on multi-view clustering that exploit multiple representations (or views) of the same input data for better convergence. These multiple views can come from multiple modalities (image, audio, text) or different feature subsets. Obtaining one consensus partitioning after considering different views is usually a non-trivial task. Recently, multi-objective based multi-view clustering methods have suppressed the performance of single objective based multi-view clustering techniques. One key problem is that it is difficult to select a single solution from a set of alternative partitionings generated by multi-objective techniques on the final Pareto optimal front. In this article, we propose a novel multi-objective based multi-view clustering framework that overcomes the problem of selecting a single solution in multi-objective based techniques. In particular, our proposed framework has three major components as follows: (i) multi-view based multi-objective algorithm, Multiview-AMOSA, for initial clustering of data points; (ii) a generative model for generating a combined solution having probabilistic labels; and (iii) K-means algorithm for obtaining the final labels. As the first component, we have adopted a recently developed multi-view based multi-objective clustering algorithm to generate different possible consensus partitionings of a given dataset taking into account different views. A generative model is coupled with the first component to generate a single consensus partitioning after considering multiple solutions. It exploits the latent subsets of the non-dominated solutions obtained from the multi-objective clustering algorithm and combines them to produce a single probabilistic labeled solution. Finally, a simple clustering algorithm, namely K-means, is applied on the generated probabilistic labels to obtain the final cluster labels. Experimental validation of our proposed framework is carried out over several benchmark datasets belonging to three different domains; UCI datasets, multi-view datasets, search result clustering datasets, and patient stratification datasets. Experimental results show that our proposed framework achieves an improvement of around 2%--4% over different evaluation metrics in all the four domains in comparison to state-of-the art methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {2},
numpages = {31},
keywords = {multi-view clustering, generative model, Multi-objective clustering, search result clustering}
}

@article{10.1145/3369872,
author = {Galimberti, Edoardo and Bonchi, Francesco and Gullo, Francesco and Lanciano, Tommaso},
title = {Core Decomposition in Multilayer Networks: Theory, Algorithms, and Applications},
year = {2020},
issue_date = {February 2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {14},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3369872},
doi = {10.1145/3369872},
abstract = {Multilayer networks are a powerful paradigm to model complex systems, where multiple relations occur between the same entities. Despite the keen interest in a variety of tasks, algorithms, and analyses in this type of network, the problem of extracting dense subgraphs has remained largely unexplored so far.As a first step in this direction, in this work, we study the problem of core decomposition of a multilayer network. Unlike the single-layer counterpart in which cores are all nested into one another and can be computed in linear time, the multilayer context is much more challenging as no total order exists among multilayer cores; rather, they form a lattice whose size is exponential in the number of layers. In this setting, we devise three algorithms, which differ in the way they visit the core lattice and in their pruning techniques. We assess time and space efficiency of the three algorithms on a large variety of real-world multilayer networks.We then move a step forward and study the problem of extracting the inner-most (also known as maximal) cores, i.e., the cores that are not dominated by any other core in terms of their core index in all the layers. inner-most cores are typically orders of magnitude less than all the cores. Motivated by this, we devise an algorithm that effectively exploits the maximality property and extracts inner-most cores directly, without first computing a complete decomposition. This allows for a consistent speed up over a na\"{\i}ve method that simply filters out non-inner-most ones from all the cores.Finally, we showcase the multilayer core-decomposition tool in a variety of scenarios and problems. We start by considering the problem of densest-subgraph extraction in multilayer networks. We introduce a definition of multilayer densest subgraph that tradesoff between high density and number of layers in which the high density holds, and exploit multilayer core decomposition to approximate this problem with quality guarantees. As further applications, we show how to utilize multilayer core decomposition to speed-up the extraction of frequent cross-graph quasi-cliques and to generalize the community-search problem to the multilayer setting.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {11},
numpages = {40},
keywords = {cliques and quasi-cliques, dense-subgraph extraction, core decomposition, Graph mining, multilayer networks, community search}
}

@article{10.1145/3365677,
author = {Kuang, Kun and Cui, Peng and Li, Bo and Jiang, Meng and Wang, Yashen and Wu, Fei and Yang, Shiqiang},
title = {Treatment Effect Estimation via Differentiated Confounder Balancing and Regression},
year = {2019},
issue_date = {February 2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {14},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3365677},
doi = {10.1145/3365677},
abstract = {Treatment effect plays an important role on decision making in many fields, such as social marketing, healthcare, and public policy. The key challenge on estimating treatment effect in the wild observational studies is to handle confounding bias induced by imbalance of the confounder distributions between treated and control units. Traditional methods remove confounding bias by re-weighting units with supposedly accurate propensity score estimation under the unconfoundedness assumption. Controlling high-dimensional variables may make the unconfoundedness assumption more plausible, but poses new challenge on accurate propensity score estimation. One strand of recent literature seeks to directly optimize weights to balance confounder distributions, bypassing propensity score estimation. But existing balancing methods fail to do selection and differentiation among the pool of a large number of potential confounders, leading to possible underperformance in many high-dimensional settings. In this article, we propose a data-driven Differentiated Confounder Balancing (DCB) algorithm to jointly select confounders, differentiate weights of confounders and balance confounder distributions for treatment effect estimation in the wild high-dimensional settings. Besides, under some settings with heavy confounding bias, in order to further reduce the bias and variance of estimated treatment effect, we propose a Regression Adjusted Differentiated Confounder Balancing (RA-DCB) algorithm based on our DCB algorithm by incorporating outcome regression adjustment. The synergistic learning algorithms we proposed are more capable of reducing the confounding bias in many observational studies. To validate the effectiveness of our DCB and RA-DCB algorithms, we conduct extensive experiments on both synthetic and real-world datasets. The experimental results clearly demonstrate that our algorithms outperform the state-of-the-art methods. By incorporating regression adjustment, our RA-DCB algorithm achieves more precise estimation on treatment effect than DCB algorithm, especially under the settings with heavy confounding bias. Moreover, we show that the top features ranked by our algorithm generate accurate prediction of online advertising effect.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {6},
numpages = {25},
keywords = {confounding bias, regression adjustment, Treatment effect estimation, differentiated confounder balancing}
}

@article{10.1145/3361739,
author = {Ni, Li and Luo, Wenjian and Zhu, Wenjie and Hua, Bei},
title = {Local Overlapping Community Detection},
year = {2019},
issue_date = {February 2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {14},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3361739},
doi = {10.1145/3361739},
abstract = {Local community detection refers to finding the community that contains the given node based on local information, which becomes very meaningful when global information about the network is unavailable or expensive to acquire. Most studies on local community detection focus on finding non-overlapping communities. However, many real-world networks contain overlapping communities like social networks. Given an overlapping node that belongs to multiple communities, the problem is to find communities to which it belongs according to local information. We propose a framework for local overlapping community detection. The framework has three steps. First, find nodes in multiple communities to which the given node belongs. Second, select representative nodes from nodes obtained above, which tends to be in different communities. Third, discover the communities to which these representative nodes belong. In addition, to demonstrate the effectiveness of the framework, we implement six versions of this framework. Experimental results demonstrate that the six implementation versions outperform the other algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {3},
numpages = {25},
keywords = {Social network, local overlapping community detection, local community detection, community detection}
}

@article{10.1145/3370912,
author = {Queiroz-Sousa, Paulo Orlando and Salgado, Ana Carolina},
title = {A Review on OLAP Technologies Applied to Information Networks},
year = {2019},
issue_date = {February 2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {14},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3370912},
doi = {10.1145/3370912},
abstract = {Many real systems produce network data or highly interconnected data, which can be called information networks. These information networks form a critical component in modern information infrastructure, constituting a large graph data volume. The analysis of information network data covers several technological areas, among them OLAP technologies. OLAP is a technology that enables multi-dimensional and multi-level analysis on a large volume of data, providing aggregated data visualizations with different perspectives. This article presents a literature review on the main applications of OLAP technology in the analysis of information network data. To achieve such goal, it shows a systematic review to list the works that apply OLAP technologies in graph data. It defines seven comparison criteria (Materialization, Network, Selection, Aggregation, Model, OLAP Operations, Analytics) to qualify the works found based on their functionalities. The works are analyzed according to each criterion and discussed to identify trends and challenges in the application of OLAP in the information network.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {8},
numpages = {25},
keywords = {OLAP, data warehousing, cube, Graph-database, information network, graph analytics}
}

@article{10.1145/3365676,
author = {Arifuzzaman, Shaikh and Khan, Maleq and Marathe, Madhav},
title = {Fast Parallel Algorithms for Counting and Listing Triangles in Big Graphs},
year = {2019},
issue_date = {February 2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {14},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3365676},
doi = {10.1145/3365676},
abstract = {Big graphs (networks) arising in numerous application areas pose significant challengesfor graph analysts as these graphs grow to billions of nodes and edges and are prohibitively large to fit in the main memory. Finding the number of triangles in a graph is an important problem in the mining and analysis of graphs. In this article, we present two efficient MPI-based distributed memory parallel algorithms for counting triangles in big graphs. The first algorithm employs overlapping partitioning and efficient load balancing schemes to provide a very fast parallel algorithm. The algorithm scales well to networks with billions of nodes and can compute the exact number of triangles in a network with 10 billion edges in 16 minutes. The second algorithm divides the network into non-overlapping partitions leading to a space-efficient algorithm. Our results on both artificial and real-world networks demonstrate a significant space saving with this algorithm. We also present a novel approach that reduces communication cost drastically leading the algorithm to both a space- and runtime-efficient algorithm. Further, we demonstrate how our algorithms can be used to list all triangles in a graph and compute clustering coefficients of nodes. Our algorithm can also be adapted to a parallel approximation algorithm using an edge sparsification method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {5},
numpages = {34},
keywords = {clustering-coefficient, graph mining, social networks, Triangle-counting, massive networks, parallel algorithms}
}

@article{10.1145/3366633,
author = {Md. Jan, Zohaib and Verma, Brijesh},
title = {Evolutionary Classifier and Cluster Selection Approach for Ensemble Classification},
year = {2019},
issue_date = {February 2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {14},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3366633},
doi = {10.1145/3366633},
abstract = {Ensemble classifiers improve the classification performance by combining several classifiers using a suitable fusion methodology. Many ensemble classifier generation methods have been developed that allowed the training of multiple classifiers on a single dataset. As such random subspace is a common methodology utilized by many state-of-the-art ensemble classifiers that generate random subsamples from the input data and train classifiers on different subsamples. Real-world datasets have randomness and noise in them, therefore not all randomly generated samples are suitable for training. In this article, we propose a novel particle swarm optimization-based approach to optimize the random subspace to generate an ensemble classifier. We first generate a random subspace by incrementally clustering input data and then optimize all generated data clusters. On all optimized data clusters, a set of classifiers is trained and added to the pool. The pool of classifiers is then optimized and an optimized ensemble classifier is generated. The proposed approach is tested on 12 benchmark datasets from the UCI repository and results are compared with current state-of-the-art ensemble classifier approaches. A statistical significance test is also conducted and an analysis is presented.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {7},
numpages = {18},
keywords = {clustering, particle swarm optimization, Multiple classifier systems}
}

@article{10.1145/3365672,
author = {Hasan, Md Kamrul and Pal, Christopher},
title = {A New Smooth Approximation to the Zero One Loss with a Probabilistic Interpretation},
year = {2019},
issue_date = {February 2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {14},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3365672},
doi = {10.1145/3365672},
abstract = {We examine a new form of smooth approximation to the zero one loss in which learning is performed using a reformulation of the widely used logistic function. Our approach is based on using the posterior mean of a novel generalized Beta-Bernoulli formulation. This leads to a generalized logistic function that approximates the zero one loss, but retains a probabilistic formulation conferring a number of useful properties. The approach is easily generalized to kernel logistic regression and easily integrated into methods for structured prediction. We present experiments in which we learn such models using an optimization method consisting of a combination of gradient descent and coordinate descent using localized grid search so as to escape from local minima. Our experiments indicate that optimization quality is improved when learning metaparameters are themselves optimized using a validation set. Our experiments show improved performance relative to widely used logistic and hinge loss methods on a wide variety of problems ranging from standard UC Irvine and libSVM evaluation datasets to product review predictions and a visual information extraction task. We observe that the approach is as follows: (1) more robust to outliers compared to the logistic and hinge losses; (2) outperforms comparable logistic and max margin models on larger scale benchmark problems; (3) when combined with Gaussian–Laplacian mixture prior on parameters the kernelized version of our formulation yields sparser solutions than Support Vector Machine classifiers; and (4) when integrated into a probabilistic structured prediction technique our approach provides more accurate probabilities yielding improved inference and increasing information extraction performance.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {1},
numpages = {28},
keywords = {classification, probabilistic models, Machine learning, logistic regression, supervised learning}
}

@article{10.1145/3364226,
author = {Zhou, Yu and Huang, Jianbin and Sun, Heli and Sun, Yizhou and Qiao, Shaojie and Wambura, Stephen},
title = {Recurrent Meta-Structure for Robust Similarity Measure in Heterogeneous Information Networks},
year = {2019},
issue_date = {December 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {6},
issn = {1556-4681},
url = {https://doi.org/10.1145/3364226},
doi = {10.1145/3364226},
abstract = {Similarity measure is one of the fundamental task in heterogeneous information network (HIN) analysis. It has been applied to many areas, such as product recommendation, clustering, and Web search. Most of the existing metrics can provide personalized services for users by taking a meta-path or meta-structure as input. However, these metrics may highly depend on the user-specified meta-path or meta-structure. In addition, users must know how to select an appropriate meta-path or meta-structure. In this article, we propose a novel similarity measure in HINs, called Recurrent Meta-Structure (RecurMS)-based Similarity (RMSS). The RecurMS as a schematic structure in HINs provides a unified framework for integrating all of the meta-paths and meta-structures, and can be constructed automatically by means of repetitively traversing the network schema. In order to formalize the semantics, the RecurMS is decomposed into several recurrent meta-paths and recurrent meta-trees, and we then define the commuting matrices of the recurrent meta-paths and meta-trees. All of these commuting matrices are combined together according to different weights. We propose two kinds of weighting strategies to determine the weights. The first is called the local weighting strategy that depends on the sparsity of the commuting matrices, and the second is called the global weighting strategy that depends on the strength of the commuting matrices. As a result, RMSS is defined by means of the weighted summation of the commuting matrices. Note that RMSS can also provide personalized services for users by means of the weights of the recurrent meta-paths and meta-trees. Experimental evaluations show that the proposed RMSS is robust and outperforms the existing metrics in terms of ranking and clustering task.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {64},
numpages = {33},
keywords = {Heterogeneous information network, meta-path, meta-structure, similarity}
}

@article{10.1145/3362695,
author = {Veloso, Br\'{a}ulio M. and Assun\c{c}\~{a}o, Renato M. and Ferreira, Anderson A. and Ziviani, Nivio},
title = {In Search of a Stochastic Model for the E-News Reader},
year = {2019},
issue_date = {December 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {6},
issn = {1556-4681},
url = {https://doi.org/10.1145/3362695},
doi = {10.1145/3362695},
abstract = {E-news readers have increasingly at their disposal a broad set of news articles to read. Online newspaper sites use recommender systems to predict and to offer relevant articles to their users. Typically, these recommender systems do not leverage users’ reading behavior. If we know how the topics-reads change in a reading session, we may lead to fine-tuned recommendations, for example, after reading a certain number of sports items, it may be counter-productive to keep recommending other sports news. The motivation for this article is the assumption that understanding user behavior when reading successive online news articles can help in developing better recommender systems. We propose five categories of stochastic models to describe this behavior depending on how the previous reading history affects the future choices of topics. We instantiated these five classes with many different stochastic processes covering short-term memory, revealed-preference, cumulative advantage, and geometric sojourn models. Our empirical study is based on large datasets of E-news from two online newspapers. We collected data from more than 13 million users who generated more than 23 million reading sessions, each one composed by the successive clicks of the users on the posted news. We reduce each user session to the sequence of reading news topics. The models were fitted and compared using the Akaike Information Criterion and the Brier Score. We found that the best models are those in which the user moves through topics influenced only by their most recent readings. Our models were also better to predict the next reading than the recommender systems currently used in these journals showing that our models can improve user satisfaction.},
journal = {ACM Trans. Knowl. Discov. Data},
month = nov,
articleno = {65},
numpages = {27},
keywords = {online newspapers, stochastic models, Modeling user behavior}
}

@article{10.1145/3363571,
author = {Wu, Jimmy Ming-Tai and Lin, Jerry Chun-Wei and Tamrakar, Ashish},
title = {High-Utility Itemset Mining with Effective Pruning Strategies},
year = {2019},
issue_date = {December 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {6},
issn = {1556-4681},
url = {https://doi.org/10.1145/3363571},
doi = {10.1145/3363571},
abstract = {High-utility itemset mining is a popular data mining problem that considers utility factors, such as quantity and unit profit of items besides frequency measure from the transactional database. It helps to find the most valuable and profitable products/items that are difficult to track by using only the frequent itemsets. An item might have a high-profit value which is rare in the transactional database and has a tremendous importance. While there are many existing algorithms to find high-utility itemsets (HUIs) that generate comparatively large candidate sets, our main focus is on significantly reducing the computation time with the introduction of new pruning strategies. The designed pruning strategies help to reduce the visitation of unnecessary nodes in the search space, which reduces the time required by the algorithm. In this article, two new stricter upper bounds are designed to reduce the computation time by refraining from visiting unnecessary nodes of an itemset. Thus, the search space of the potential HUIs can be greatly reduced, and the mining procedure of the execution time can be improved. The proposed strategies can also significantly minimize the transaction database generated on each node. Experimental results showed that the designed algorithm with two pruning strategies outperform the state-of-the-art algorithms for mining the required HUIs in terms of runtime and number of revised candidates. The memory usage of the designed algorithm also outperforms the state-of-the-art approach. Moreover, a multi-thread concept is also discussed to further handle the problem of big datasets.},
journal = {ACM Trans. Knowl. Discov. Data},
month = nov,
articleno = {58},
numpages = {22},
keywords = {pruning strategy, high-utility itemset, multiple threads, HUIM}
}

@article{10.1145/3363574,
author = {Lee, John Boaz and Rossi, Ryan A. and Kim, Sungchul and Ahmed, Nesreen K. and Koh, Eunyee},
title = {Attention Models in Graphs: A Survey},
year = {2019},
issue_date = {December 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {6},
issn = {1556-4681},
url = {https://doi.org/10.1145/3363574},
doi = {10.1145/3363574},
abstract = {Graph-structured data arise naturally in many different application domains. By representing data as graphs, we can capture entities (i.e., nodes) as well as their relationships (i.e., edges) with each other. Many useful insights can be derived from graph-structured data as demonstrated by an ever-growing body of work focused on graph mining. However, in the real-world, graphs can be both large—with many complex patterns—and noisy, which can pose a problem for effective graph mining. An effective way to deal with this issue is to incorporate “attention” into graph mining solutions. An attention mechanism allows a method to focus on task-relevant parts of the graph, helping it to make better decisions. In this work, we conduct a comprehensive and focused survey of the literature on the emerging field of graph attention models. We introduce three intuitive taxonomies to group existing work. These are based on problem setting (type of input and output), the type of attention mechanism used, and the task (e.g., graph classification, link prediction). We motivate our taxonomies through detailed examples and use each to survey competing approaches from a unique standpoint. Finally, we highlight several challenges in the area and discuss promising directions for future work.},
journal = {ACM Trans. Knowl. Discov. Data},
month = nov,
articleno = {62},
numpages = {25},
keywords = {deep learning, graph attention survey, Attention mechanism, graph attention}
}

@article{10.1145/3363570,
author = {Liu, Shenghua and Shen, Huawei and Zheng, Houdong and Cheng, Xueqi and Liao, Xiangwen},
title = {CT LIS: Learning Influences and Susceptibilities through Temporal Behaviors},
year = {2019},
issue_date = {December 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {6},
issn = {1556-4681},
url = {https://doi.org/10.1145/3363570},
doi = {10.1145/3363570},
abstract = {How to quantify influences between users, seeing that social network users influence each other in their temporal behaviors? Previous work has directly defined an independent model parameter to capture the interpersonal influence between each pair of users. To do so, these models need a parameter for each pair of users, which results in high-dimensional models becoming easily trapped into the overfitting problem. However, such models do not consider how influences depend on each other if influences are sent from the same user or if influences are received by the same user. Therefore, we propose a model that defines parameters for every user with a latent influence vector and a susceptibility vector, opposite to define influences on user pairs. Such low-dimensional representations naturally cause the interpersonal influences involving the same user to be coupled with each other, thus reducing the model’s complexity. Additionally, the model can easily consider the temporal information and sentimental polarities of users’ messages. Finally, we conduct extensive experiments on two real-world Microblog datasets, showing that our model with such representations achieves best performance on three prediction tasks, compared to the state-of-the-art and pair-wise baselines.},
journal = {ACM Trans. Knowl. Discov. Data},
month = nov,
articleno = {57},
numpages = {21},
keywords = {User behaviors, susceptibility, influence, time series}
}

@article{10.1145/3363573,
author = {Roseberry, Martha and Krawczyk, Bartosz and Cano, Alberto},
title = {Multi-Label Punitive KNN with Self-Adjusting Memory for Drifting Data Streams},
year = {2019},
issue_date = {December 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {6},
issn = {1556-4681},
url = {https://doi.org/10.1145/3363573},
doi = {10.1145/3363573},
abstract = {In multi-label learning, data may simultaneously belong to more than one class. When multi-label data arrives as a stream, the challenges associated with multi-label learning are joined by those of data stream mining, including the need for algorithms that are fast and flexible, able to match both the speed and evolving nature of the stream. This article presents a punitive k nearest neighbors algorithm with a self-adjusting memory (MLSAMPkNN) for multi-label, drifting data streams. The memory adjusts in size to contain only the current concept and a novel punitive system identifies and penalizes errant data examples early, removing them from the window. By retaining and using only data that are both current and beneficial, MLSAMPkNN is able to adapt quickly and efficiently to changes within the data stream while still maintaining a low computational complexity. Additionally, the punitive removal mechanism offers increased robustness to various data-level difficulties present in data streams, such as class imbalance and noise. The experimental study compares the proposal to 24 algorithms using 30 real-world and 15 artificial multi-label data streams on six multi-label metrics, evaluation time, and memory consumption. The superior performance of the proposed method is validated through non-parametric statistical analysis, proving both high accuracy and low time complexity. MLSAMPkNN is a versatile classifier, capable of returning excellent performance in diverse stream scenarios.},
journal = {ACM Trans. Knowl. Discov. Data},
month = nov,
articleno = {60},
numpages = {31},
keywords = {nearest neighbor, concept drift, data stream, Multi-label classification}
}

@article{10.1145/3363572,
author = {Henzgen, Sascha and H\"{u}llermeier, Eyke},
title = {Mining Rank Data},
year = {2019},
issue_date = {December 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {6},
issn = {1556-4681},
url = {https://doi.org/10.1145/3363572},
doi = {10.1145/3363572},
abstract = {The problem of frequent pattern mining has been studied quite extensively for various types of data, including sets, sequences, and graphs. Somewhat surprisingly, another important type of data, namely rank data, has received very little attention in data mining so far. In this article, we therefore address the problem of mining rank data, that is, data in the form of rankings (total orders) of an underlying set of items. More specifically, two types of patterns are considered, namely frequent rankings and dependencies between such rankings in the form of association rules. Algorithms for mining frequent rankings and frequent closed rankings are proposed and tested experimentally, using both synthetic and real data.},
journal = {ACM Trans. Knowl. Discov. Data},
month = nov,
articleno = {59},
numpages = {36},
keywords = {rank data, association rules, Data mining, frequent pattern mining}
}

@article{10.1145/3363575,
author = {Yang, Wangdong and Li, Kenli and Li, Keqin},
title = {A Pipeline Computing Method of SpTV for Three-Order Tensors on CPU and GPU},
year = {2019},
issue_date = {December 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {6},
issn = {1556-4681},
url = {https://doi.org/10.1145/3363575},
doi = {10.1145/3363575},
abstract = {Tensors have drawn a growing attention in many applications, such as physics, engineering science, social networks, recommended systems. Tensor decomposition is the key to explore the inherent intrinsic data relationship of tensor. There are many sparse tensor and vector multiplications (SpTV) in tensor decomposition. We analyze a variety of storage formats of sparse tensors and develop a piecewise compression strategy to improve the storage efficiency of large sparse tensors. This compression strategy can avoid storing a large number of empty slices and empty fibers in sparse tensors, and thus the storage space is significantly reduced. A parallel algorithm for the SpTV based on the high-order compressed format based on slices is designed to greatly improve its computing performance on graphics processing unit. Each tensor is cut into multiple slices to form a series of sparse matrix and vector multiplications, which form the pipelined parallelism. The transmission time of the slices can be hidden through pipelined parallel to further optimize the performance of the SpTV.},
journal = {ACM Trans. Knowl. Discov. Data},
month = nov,
articleno = {63},
numpages = {27},
keywords = {Pipeline, tensor and vector multiplication, tensor, slices}
}

@article{10.1145/3350487,
author = {Zhu, Peisong and Chen, Zhuang and Zheng, Haojie and Qian, Tieyun},
title = {Aspect Aware Learning for Aspect Category Sentiment Analysis},
year = {2019},
issue_date = {December 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {6},
issn = {1556-4681},
url = {https://doi.org/10.1145/3350487},
doi = {10.1145/3350487},
abstract = {Aspect category sentiment analysis (ACSA) is an underexploited subtask in aspect level sentiment analysis. It aims to identify the sentiment of predefined aspect categories. The main challenge in ACSA comes from the fact that the aspect category may not occur in the sentence in most of the cases. For example, the review “they have delicious sandwiches” positively talks about the aspect category “food” in an implicit manner.In this article, we propose a novel aspect aware learning (AAL) framework for ACSA tasks. Our key idea is to exploit the interaction between the aspect category and the contents under the guidance of both sentiment polarity and predefined categories. To this end, we design a two-way memory network for integrating AAL into the framework of sentiment classification. We further present two algorithms to incorporate the potential impacts of aspect categories. One is to capture the correlations between aspect terms and the aspect category like “sandwiches” and “food.” The other is to recognize the aspect category for sentiment representations like “food” for “delicious.” We conduct extensive experiments on four SemEval datasets. The results reveal the essential role of AAL in ACSA by achieving the state-of-the-art performance.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {55},
numpages = {21},
keywords = {Aspect category sentiment analysis, aspect aware learning, memory network}
}

@article{10.1145/3359554,
author = {Lei, Yu and Li, Wenjie},
title = {Interactive Recommendation with User-Specific Deep Reinforcement Learning},
year = {2019},
issue_date = {December 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {6},
issn = {1556-4681},
url = {https://doi.org/10.1145/3359554},
doi = {10.1145/3359554},
abstract = {In this article, we study a multi-step interactive recommendation problem for explicit-feedback recommender systems. Different from the existing works, we propose a novel user-specific deep reinforcement learning approach to the problem. Specifically, we first formulate the problem of interactive recommendation for each target user as a Markov decision process (MDP). We then derive a multi-MDP reinforcement learning task for all involved users. To model the possible relationships (including similarities and differences) between different users’ MDPs, we construct user-specific latent states by using matrix factorization. After that, we propose a user-specific deep Q-learning (UDQN) method to estimate optimal policies based on the constructed user-specific latent states. Furthermore, we propose Biased UDQN (BUDQN) to explicitly model user-specific information by employing an additional bias parameter when estimating the Q-values for different users. Finally, we validate the effectiveness of our approach by comprehensive experimental results and analysis.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {61},
numpages = {15},
keywords = {deep Q-learning, Interactive recommendation, deep reinforcement learning}
}

@article{10.1145/3355563,
author = {Wang, Yuandong and Lin, Xuelian and Wei, Hua and Wo, Tianyu and Huang, Zhou and Zhang, Yong and Xu, Jie},
title = {A Unified Framework with Multi-Source Data for Predicting Passenger Demands of Ride Services},
year = {2019},
issue_date = {December 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {6},
issn = {1556-4681},
url = {https://doi.org/10.1145/3355563},
doi = {10.1145/3355563},
abstract = {Ride-hailing applications have been offering convenient ride services for people in need. However, such applications still suffer from the issue of supply-demand disequilibrium, which is a typical problem for traditional taxi services. With effective predictions on passenger demands, we can alleviate the disequilibrium by pre-dispatching, dynamic pricing or avoiding dispatching cars to zero-demand areas. Existing studies of demand predictions mainly utilize limited data sources, trajectory data, or orders of ride services or both of them, which also lacks a multi-perspective consideration. In this article, we present a unified framework with a new combined model and a road-network-based spatial partition to leverage multi-source data and model the passenger demands from temporal, spatial, and zero-demand-area perspectives. In addition, our framework realizes offline training and online predicting, which can satisfy the real-time requirement more easily. We analyze and evaluate the performance of our combined model using the actual operational data from UCAR. The experimental results indicate that our model outperforms baselines on both Mean Absolute Error and Root Mean Square Error on average.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {56},
numpages = {24},
keywords = {demand prediction, Spatio-temporal data, ride service, ride-hailing application}
}

@article{10.1145/3344721,
author = {Zhou, Xiren and Chen, Huanhuan and Li, Jinlong},
title = {Probabilistic Mixture Model for Mapping the Underground Pipes},
year = {2019},
issue_date = {October 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {5},
issn = {1556-4681},
url = {https://doi.org/10.1145/3344721},
doi = {10.1145/3344721},
abstract = {Buried pipes beneath our city are blood vessels that feed human civilization through the supply of water, gas, electricity, and so on, and mapping the buried pipes has long been addressed as an issue. In this article, a suitable coordinate of the detected area is established, the noisy Ground Penetrating Radar (GPR) and Global Positioning System (GPS) data are analyzed and normalized, and the pipeline is described mathematically. Based on these, the Probabilistic Mixture Model is proposed to map the buried pipes, which takes discrete noisy GPR and GPS data as the input and the accurate pipe locations and directions as the output. The proposed model consists of the Preprocessing, the Pipe Fitting algorithm, the Classification Fitting Expectation Maximization (CFEM) algorithm, and the Angle-limited Hough (Al-Hough) transform. The direction information of the detecting point is added into the measuring of the distance from the point to nearby pipelines, to handle some areas where the pipes are intersected or difficult to classify. The Expectation Maximization (EM) algorithm is upgraded to CFEM algorithm that is able to classify detecting points into different classes, and connect and fit multiple points in each class to get accurate pipeline locations and directions, and the Al-Hough transform provides reliable initializations for CFEM, to some extent, ensuring the convergence of the proposed model. The experimental results on the simulated and real-world datasets demonstrate the effectiveness of the proposed model.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {47},
numpages = {26},
keywords = {pipeline mapping, buried utility location, Data mining, probabilistic model}
}

@article{10.1145/3340847,
author = {Xu, Yanan and Zhu, Yanmin and Shen, Yanyan and Yu, Jiadi},
title = {Fine-Grained Air Quality Inference with Remote Sensing Data and Ubiquitous Urban Data},
year = {2019},
issue_date = {October 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {5},
issn = {1556-4681},
url = {https://doi.org/10.1145/3340847},
doi = {10.1145/3340847},
abstract = {Air quality has gained much attention in recent years and is of great importance to protecting people’s health. Due to the influence of multiple factors, the limited air quality monitoring stations deployed in cities are unable to provide fine-grained air quality information. One cost-effective way is to infer air quality with records from existing monitoring stations. However, the severe data sparsity problem (e.g., only 0.2% data are known) leads to the failure of most inference methods. We observe that remote sensing data are of high quality and have a strong correlation with the air quality. Therefore, we propose to integrate remote sensing data and ubiquitous urban data for the air quality inference. But there are two main challenges, i.e., data heterogeneity and incompleteness of the remote sensing data. To address the challenges, we propose a two-stage approach. In the first stage, we infer and predict air quality conditions of some places leveraging the remote sensing data and meteorological data with two proposed ANN-based methods, respectively. This stage significantly alleviates the data sparsity problem. In the second stage, the records and estimated air quality data are put in a tensor. A tensor decomposition method is applied to complete the tensor. The features extracted from urban data are classified into the spatial features (i.e., road features and POI features) and the temporal features (i.e., meteorological features) as the constraints to further address the data sparsity problem. In addition, an iterative training framework is proposed to improve the inference performance. Experiments on a real-world dataset show that our approach outperforms state-of-the-art methods, such as U-Air.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {46},
numpages = {27},
keywords = {air quality inference, neural network, AOT, Remote sensing, tensor decomposition}
}

@article{10.1145/3340848,
author = {Xue, Yu and Xue, Bing and Zhang, Mengjie},
title = {Self-Adaptive Particle Swarm Optimization for Large-Scale Feature Selection in Classification},
year = {2019},
issue_date = {October 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {5},
issn = {1556-4681},
url = {https://doi.org/10.1145/3340848},
doi = {10.1145/3340848},
abstract = {Many evolutionary computation (EC) methods have been used to solve feature selection problems and they perform well on most small-scale feature selection problems. However, as the dimensionality of feature selection problems increases, the solution space increases exponentially. Meanwhile, there are more irrelevant features than relevant features in datasets, which leads to many local optima in the huge solution space. Therefore, the existing EC methods still suffer from the problem of stagnation in local optima on large-scale feature selection problems. Furthermore, large-scale feature selection problems with different datasets may have different properties. Thus, it may be of low performance to solve different large-scale feature selection problems with an existing EC method that has only one candidate solution generation strategy (CSGS). In addition, it is time-consuming to find a suitable EC method and corresponding suitable parameter values for a given large-scale feature selection problem if we want to solve it effectively and efficiently. In this article, we propose a self-adaptive particle swarm optimization (SaPSO) algorithm for feature selection, particularly for large-scale feature selection. First, an encoding scheme for the feature selection problem is employed in the SaPSO. Second, three important issues related to self-adaptive algorithms are investigated. After that, the SaPSO algorithm with a typical self-adaptive mechanism is proposed. The experimental results on 12 datasets show that the solution size obtained by the SaPSO algorithm is smaller than its EC counterparts on all datasets. The SaPSO algorithm performs better than its non-EC and EC counterparts in terms of classification accuracy not only on most training sets but also on most test sets. Furthermore, as the dimensionality of the feature selection problem increases, the advantages of SaPSO become more prominent. This highlights that the SaPSO algorithm is suitable for solving feature selection problems, particularly large-scale feature selection problems.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {50},
numpages = {27},
keywords = {classification, large-scale, particle swarm optimization, self-adaptive, Feature selection}
}

@article{10.1145/3340804,
author = {Jiang, Fei and Yin, Guosheng and Dominici, Francesca},
title = {Bayesian Model Selection Approach to Multiple Change-Points Detection with Non-Local Prior Distributions},
year = {2019},
issue_date = {October 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {5},
issn = {1556-4681},
url = {https://doi.org/10.1145/3340804},
doi = {10.1145/3340804},
abstract = {We propose a Bayesian model selection (BMS) boundary detection procedure using non-local prior distributions for a sequence of data with multiple systematic mean changes. By using the non-local priors in the BMS framework, the BMS method can effectively suppress the non-boundary spike points with large instantaneous changes. Further, we speedup the algorithm by reducing the multiple change points to a series of single change point detection problems. We establish the consistency of the estimated number and locations of the change points under various prior distributions. From both theoretical and numerical perspectives, we show that the non-local inverse moment prior leads to the fastest convergence rate in identifying the true change points on the boundaries. Extensive simulation studies are conducted to compare the BMS with existing methods, and our method is illustrated with application to the magnetic resonance imaging guided radiation therapy data.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {48},
numpages = {17},
keywords = {moment prior, marginal likelihood, parallel computing, inverse moment prior, Bayes factor, bayesian model selection, local prior}
}

@article{10.1145/3356584,
author = {Wang, Yun and Song, Guojie and Du, Lun and Lu, Zhicong},
title = {Real-Time Estimation of the Urban Air Quality with Mobile Sensor System},
year = {2019},
issue_date = {October 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {5},
issn = {1556-4681},
url = {https://doi.org/10.1145/3356584},
doi = {10.1145/3356584},
abstract = {Recently, real-time air quality estimation has attracted more and more attention from all over the world, which is close to our daily life. With the prevalence of mobile sensors, there is an emerging way to monitor the air quality with mobile sensors on vehicles. Compared with traditional expensive monitor stations, mobile sensors are cheaper and more abundant, but observations from these sensors have unstable spatial and temporal distributions, which results in the existing model could not work very well on this type of data. In this article, taking advantage of air quality data from mobile sensors, we propose an real-time urban air quality estimation method based on the Gaussian Process Regression for air pollution of the unmonitored areas, pivoting on the diffusion effect and the accumulation effect of air pollution. In order to meet the real-time demands, we propose a two-layer ensemble learning framework and a self-adaptivity mechanism to improve computational efficiency and adaptivity. We evaluate our model with real data from mobile sensor system located in Beijing, China. And the experiments show that our proposed model is superior to the state-of-the-art spatial regression methods in both precision and time performances.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {49},
numpages = {9},
keywords = {Air quality real-time estimation, ensemble learning, mobile sensors, gaussian process regression}
}

@article{10.1145/3344719,
author = {Bergamini, Elisabetta and Borassi, Michele and Crescenzi, Pierluigi and Marino, Andrea and Meyerhenke, Henning},
title = {Computing Top-k Closeness Centrality Faster in Unweighted Graphs},
year = {2019},
issue_date = {October 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {5},
issn = {1556-4681},
url = {https://doi.org/10.1145/3344719},
doi = {10.1145/3344719},
abstract = {Given a connected graph G=(V,E), where V denotes the set of nodes and E the set of edges of the graph, the length (that is, the number of edges) of the shortest path between two nodes v and w is denoted by d(v,w). The closeness centrality of a vertex v is then defined as n=1/Σw ∈ V d(v,w), where n=|V|. This measure is widely used in the analysis of real-world complex networks, and the problem of selecting the k most central vertices has been deeply analyzed in the last decade. However, this problem is computationally not easy, especially for large networks: in the first part of the article, we prove that it is not solvable in time O(|E|2=ϵ) on directed graphs, for any constant ϵ > 0, under reasonable complexity assumptions. Furthermore, we propose a new algorithm for selecting the k most central nodes in a graph: we experimentally show that this algorithm improves significantly both the textbook algorithm, which is based on computing the distance between all pairs of vertices, and the state of the art. For example, we are able to compute the top k nodes in few dozens of seconds in real-world networks with millions of nodes and edges. Finally, as a case study, we compute the 10 most central actors in the Internet Movie Database (IMDB) collaboration network, where two actors are linked if they played together in a movie, and in the Wikipedia citation network, which contains a directed edge from a page p to a page q if p contains a link to q.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {53},
numpages = {40},
keywords = {complex networks, Centrality, closeness}
}

@article{10.1145/3340708,
author = {He, Kun and Shi, Pan and Bindel, David and Hopcroft, John E.},
title = {Krylov Subspace Approximation for Local Community Detection in Large Networks},
year = {2019},
issue_date = {October 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {5},
issn = {1556-4681},
url = {https://doi.org/10.1145/3340708},
doi = {10.1145/3340708},
abstract = {Community detection is an important information mining task to uncover modular structures in large networks. For increasingly common large network datasets, global community detection is prohibitively expensive, and attention has shifted to methods that mine local communities,  i.e., identifying all latent members of a particular community from a few labeled seed members. To address such semi-supervised mining task, we systematically develop a local spectral (LOSP) subspace-based community detection method, called LOSP. We define a family of LOSP subspaces based on Krylov subspaces, and seek a sparse indicator for the target community via an ℓ1 norm minimization over the Krylov subspace. Variants of LOSP depend on type of random walks with different diffusion speeds, type of random walks, dimension of the LOSP subspace, and step of diffusions. The effectiveness of the proposed LOSP approach is theoretically analyzed based on Rayleigh quotients, and it is experimentally verified on a wide variety of real-world networks across social, production, and biological domains, as well as on an extensive set of synthetic LFR benchmark datasets.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {52},
numpages = {30},
keywords = {Krylov subspace, spectral clustering, Rayleigh quotient, sparse linear coding, Local community detection}
}

@article{10.1145/3344720,
author = {Crescenzi, Valter and Merialdo, Paolo and Qiu, Disheng},
title = {Hybrid Crowd-Machine Wrapper Inference},
year = {2019},
issue_date = {October 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {5},
issn = {1556-4681},
url = {https://doi.org/10.1145/3344720},
doi = {10.1145/3344720},
abstract = {Wrapper inference deals in generating programs to extract data from Web pages. Several supervised and unsupervised wrapper inference approaches have been proposed in the literature. On one hand, unsupervised approaches produce erratic wrappers: whenever the sources do not satisfy underlying assumptions of the inference algorithm, their accuracy is compromised. On the other hand, supervised approaches produce accurate wrappers, but since they need training data, their scalability is limited. The recent advent of crowdsourcing platforms has opened new opportunities for supervised approaches, as they make possible the production of large amounts of training data with the support of workers recruited online. Nevertheless, involving human workers has monetary costs. We present an original hybrid crowd-machine wrapper inference system that offers the benefits of both approaches exploiting the cooperation of crowd workers and unsupervised algorithms. Based on a principled probabilistic model that estimates the quality of wrappers, humans workers are recruited only when unsupervised wrapper induction algorithms are not able to produce sufficiently accurate solutions.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {51},
numpages = {43},
keywords = {data extraction, wrapper inference, Crowdsourcing}
}

@article{10.1145/3344210,
author = {Tatti, Nikolaj},
title = {Density-Friendly Graph Decomposition},
year = {2019},
issue_date = {October 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {5},
issn = {1556-4681},
url = {https://doi.org/10.1145/3344210},
doi = {10.1145/3344210},
abstract = {Decomposing a graph into a hierarchical structure via k-core analysis is a standard operation in any modern graph-mining toolkit. k-core decomposition is a simple and efficient method that allows to analyze a graph beyond its mere degree distribution. More specifically, it is used to identify areas in the graph of increasing centrality and connectedness, and it allows to reveal the structural organization of the graph.Despite the fact that k-core analysis relies on vertex degrees, k-cores do not satisfy a certain, rather natural, density property. Simply put, the most central k-core is not necessarily the densest subgraph. This inconsistency between k-cores and graph density provides the basis of our study.We start by defining what it means for a subgraph to be locally dense, and we show that our definition entails a nested chain decomposition of the graph, similar to the one given by k-cores, but in this case the components are arranged in order of increasing density. We show that such a locally dense decomposition for a graph G=(V,E) can be computed in polynomial time. The running time of the exact decomposition algorithm is O(|V|2|E|) but is significantly faster in practice. In addition, we develop a linear-time algorithm that provides a factor-2 approximation to the optimal locally dense decomposition. Furthermore, we show that the k-core decomposition is also a factor-2 approximation, however, as demonstrated by our experimental evaluation, in practice k-cores have different structure than locally dense subgraphs, and as predicted by the theory, k-cores are not always well-aligned with graph density.},
journal = {ACM Trans. Knowl. Discov. Data},
month = sep,
articleno = {54},
numpages = {29},
keywords = {max-flow, fractional programming, Locally-dense graph decomposition}
}

@article{10.1145/3322126,
author = {Ben-Gal, Irad and Weinstock, Shahar and Singer, Gonen and Bambos, Nicholas},
title = {Clustering Users by Their Mobility Behavioral Patterns},
year = {2019},
issue_date = {August 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3322126},
doi = {10.1145/3322126},
abstract = {The immense stream of data from mobile devices during recent years enables one to learn more about human behavior and provide mobile phone users with personalized services. In this work, we identify clusters of users who share similar mobility behavioral patterns. We analyze trajectories of semantic locations to find users who have similar mobility “lifestyle,” even when they live in different areas. For this task, we propose a new grouping scheme that is called Lifestyle-Based Clustering (LBC). We represent the mobility movement of each user by a Markov model and calculate the Jensen–Shannon distances among pairs of users. The pairwise distances are represented by a similarity matrix, which is used for the clustering. To validate the unsupervised clustering task, we develop an entropy-based clustering measure, namely, an index that measures the homogeneity of mobility patterns within clusters of users. The analysis is validated on a real-world dataset that contains location-movements of 50,000 cellular phone users that were analyzed over a two-month period.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {45},
numpages = {28},
keywords = {clustering evaluation, Clustering trajectories}
}

@article{10.1145/3333030,
author = {Qiang, Jipeng and Chen, Ping and Ding, Wei and Wang, Tong and Xie, Fei and Wu, Xindong},
title = {Heterogeneous-Length Text Topic Modeling for Reader-Aware Multi-Document Summarization},
year = {2019},
issue_date = {August 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3333030},
doi = {10.1145/3333030},
abstract = {More and more user comments like Tweets are available, which often contain user concerns. In order to meet the demands of users, a good summary generating from multiple documents should consider reader interests as reflected in reader comments. In this article, we focus on how to generate a summary from multi-document documents by considering reader comments, named as reader-aware multi-document summarization (RA-MDS). We present an innovative topic-based method for RA-MDA, which exploits latent topics to obtain the most salient and lessen redundancy summary from multiple documents. Since finding latent topics for RA-MDS is a crucial step, we also present a Heterogeneous-length Text Topic Modeling (HTTM) to extract topics from the corpus that includes both news reports and user comments, denoted as heterogeneous-length texts. In this case, the latent topics extract by HTTM cover not only important aspects of the event, but also aspects that attract reader interests. Comparisons on summary benchmark datasets also confirm that the proposed RA-MDS method is effective in improving the quality of extracted summaries. In addition, experimental results demonstrate that the proposed topic modeling method outperforms existing topic modeling algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {42},
numpages = {21},
keywords = {LDA, multi-document summarization, Topic modeling, heterogeneous-length text}
}

@article{10.1145/3332168,
author = {Amelkin, Victor and Bogdanov, Petko and Singh, Ambuj K.},
title = {A Distance Measure for the Analysis of Polar Opinion Dynamics in Social Networks},
year = {2019},
issue_date = {August 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3332168},
doi = {10.1145/3332168},
abstract = {Analysis of opinion dynamics in social networks plays an important role in today’s life. For predicting users’ political preference, it is particularly important to be able to analyze the dynamics of competing polar opinions, such as pro-Democrat vs. pro-Republican. While observing the evolution of polar opinions in a social network over time, can we tell when the network evolved abnormally? Furthermore, can we predict how the opinions of the users will change in the future? To answer such questions, it is insufficient to study individual user behavior, since opinions can spread beyond users’ ego-networks. Instead, we need to consider the opinion dynamics of all users simultaneously and capture the connection between the individuals’ behavior and the global evolution pattern of the social network.In this work, we introduce the Social Network Distance (SND)—a distance measure that quantifies the likelihood of evolution of one snapshot of a social network into another snapshot under a chosen model of polar opinion dynamics. SND has a rich semantics of a transportation problem, yet, is computable in time linear in the number of users and, as such, is applicable to large-scale online social networks. In our experiments with synthetic and Twitter data, we demonstrate the utility of our distance measure for anomalous event detection. It achieves a true positive rate of 0.83, twice as high as that of alternatives. The same predictions presented in precision-recall space show that SND retains perfect precision for recall up to 0.2. Its precision then decreases while maintaining more than 2-fold improvement over alternatives for recall up to 0.95. When used for opinion prediction in Twitter data, SND’s accuracy is 75.6%, which is 7.5% higher than that of the next best method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {38},
numpages = {34},
keywords = {Social network, model-driven analysis, competing opinions, time-series, transportation problem, opinion prediction, minimum-cost network flow, polarization, anomaly detection, opinion dynamics, earth mover’s distance, distance measure, wasserstein metric, polar opinions}
}

@article{10.1145/3332185,
author = {Comito, Carmela and Forestiero, Agostino and Pizzuti, Clara},
title = {Bursty Event Detection in Twitter Streams},
year = {2019},
issue_date = {August 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3332185},
doi = {10.1145/3332185},
abstract = {Social media, in recent years, have become an invaluable source of information for both public and private organizations to enhance the comprehension of people interests and the onset of new events. Twitter, especially, allows a fast spread of news and events happening real time that can contribute to situation awareness during emergency situations, but also to understand trending topics of a period. The article proposes an online algorithm that incrementally groups tweet streams into clusters. The approach summarizes the examined tweets into the cluster centroid by maintaining a number of textual and temporal features that allow the method to effectively discover groups of interest on particular themes. Experiments on messages posted by users addressing different issues, and a comparison with state-of-the-art approaches show that the method is capable to detect discussions regarding topics of interest, but also to distinguish bursty events revealed by a sudden spreading of attention on messages published by users.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {41},
numpages = {28},
keywords = {online clustering, bursty event, Twitter, event detection}
}

@article{10.1145/3332183,
author = {Chen, Haoran and Li, Jinghua and Gao, Junbin and Sun, Yanfeng and Hu, Yongli and Yin, Baocai},
title = {Maximally Correlated Principal Component Analysis Based on Deep Parameterization Learning},
year = {2019},
issue_date = {August 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3332183},
doi = {10.1145/3332183},
abstract = {Dimensionality reduction is widely used to deal with high-dimensional data. As a famous dimensionality reduction method, principal component analysis (PCA) aiming at finding the low dimension feature of original data has made great successes, and many improved PCA algorithms have been proposed. However, most algorithms based on PCA only consider the linear correlation of data features. In this article, we propose a novel dimensionality reduction model called maximally correlated PCA based on deep parameterization learning (MCPCADP), which takes nonlinear correlation into account in the deep parameterization framework for the purpose of dimensionality reduction. The new model explores nonlinear correlation by maximizing Ky-Fan norm of the covariance matrix of nonlinearly mapped data features. A new BP algorithm for model optimization is derived. In order to assess the proposed method, we conduct experiments on both a synthetic database and several real-world databases. The experimental results demonstrate that the proposed algorithm is comparable to several widely used algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {39},
numpages = {17},
keywords = {deep parameterization learning, classification, back propagation, Maximally correlated principal component analysis}
}

@article{10.1145/3333028,
author = {Sajadmanesh, Sina and Bazargani, Sogol and Zhang, Jiawei and Rabiee, Hamid R.},
title = {Continuous-Time Relationship Prediction in Dynamic Heterogeneous Information Networks},
year = {2019},
issue_date = {August 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3333028},
doi = {10.1145/3333028},
abstract = {Online social networks, World Wide Web, media, and technological networks, and other types of so-called information networks are ubiquitous nowadays. These information networks are inherently heterogeneous and dynamic. They are heterogeneous as they consist of multi-typed objects and relations, and they are dynamic as they are constantly evolving over time. One of the challenging issues in such heterogeneous and dynamic environments is to forecast those relationships in the network that will appear in the future. In this article, we try to solve the problem of continuous-time relationship prediction in dynamic and heterogeneous information networks. This implies predicting the time it takes for a relationship to appear in the future, given its features that have been extracted by considering both heterogeneity and temporal dynamics of the underlying network. To this end, we first introduce a feature extraction framework that combines the power of meta-path-based modeling and recurrent neural networks to effectively extract features suitable for relationship prediction regarding heterogeneity and dynamicity of the networks. Next, we propose a supervised non-parametric approach, called Non-Parametric Generalized Linear Model (Np-Glm), which infers the hidden underlying probability distribution of the relationship building time given its features. We then present a learning algorithm to train Np-Glm and an inference method to answer time-related queries. Extensive experiments conducted on synthetic data and three real-world datasets, namely Delicious, MovieLens, and DBLP, demonstrate the effectiveness of Np-Glm in solving continuous-time relationship prediction problem vis-\`{a}-vis competitive baselines.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {44},
numpages = {31},
keywords = {recurrent neural network, social network analysis, non-parametric modeling, Link prediction, heterogeneous network, autoencoder}
}

@article{10.1145/3332522,
author = {Li, Qingyang and Yu, Zhiwen and Guo, Bin and Xu, Huang and Lu, Xinjiang},
title = {Housing Demand Estimation Based on Express Delivery Data},
year = {2019},
issue_date = {August 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3332522},
doi = {10.1145/3332522},
abstract = {Housing demand estimation is an important topic in the field of economic research. It is beneficial and helpful for various applications including real estate market regulation and urban planning, and therefore is crucial for both real estate investors and government administrators. Meanwhile, given the rapid development of the express industry, abundant useful information is embedded in express delivery records, which is helpful for researchers in profiling urban life patterns. The express delivery behaviors of the residents in a residential community can reflect the housing demand to some extent. Although housing demand has been analyzed in previous studies, its estimation has not been very good, and the subject remains under explored. To this end, in this article, we propose a systematic housing demand estimation method based on express delivery data. First, the express delivery records are aggregated on the community scale with the use of clustering methods, and the missing values in the records are completed. Then, various features are extracted from a less sparse dataset considering both the probability of residential mobility and the attractiveness of residential communities. In addition, given that the correlations between different districts can influence the performances of the inference model, the commonalities and differences of different districts are considered. After obtaining the features and correlations between different districts being obtained, the housing demand is estimated by using a multi-task learning method based on neural networks. The experimental results for real-world data show that the proposed model is effective at estimating the housing demand at the residential community level.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {43},
numpages = {25},
keywords = {Housing demand, express delivery data, multi-task learning}
}

@article{10.1145/3332146,
author = {Gallardo, Laura Fern\'{a}ndez and Sanchez-Iborra, Ramon},
title = {On the Impact of Voice Encoding and Transmission on the Predictions of Speaker Warmth and Attractiveness},
year = {2019},
issue_date = {August 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3332146},
doi = {10.1145/3332146},
abstract = {Modern human-computer interaction systems may not only be based on interpreting natural language but also on detecting speaker interpersonal characteristics in order to determine dialog strategies. This may be of high interest in different fields such as telephone marketing or automatic voice-based interactive services. However, when such systems encounter signals transmitted over a communication network instead of clean speech, e.g., in call centers, the speaker characterization accuracy might be impaired by the degradations caused in the speech signal by the encoding and communication processes. This article addresses a binary classification of high versus low warm--attractive speakers over different channel and encoding conditions. The ground truth is derived from ratings given to clean speech extracted from an extensive subjective test. Our results show that, under the considered conditions, the AMR-WB+ codec permits good levels of classification accuracy, comparable to the classification with clean, non-degraded speech. This is especially notable for the case of a Random Forest-based classifier, which presents the best performance among the set of evaluated algorithms. The impact of different packet loss rates has been examined, whereas jitter effects have been found to be negligible.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {40},
numpages = {17},
keywords = {predictive modeling, transmission channels, Speaker characteristics, speech processing}
}

@article{10.1145/3326919,
author = {Dornaika, Fadi},
title = {Active Two Phase Collaborative Representation Classifier},
year = {2019},
issue_date = {August 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3326919},
doi = {10.1145/3326919},
abstract = {The Sparse Representation Classifier, the Collaborative Representation Classifier (CRC), and the Two Phase Test Sample Sparse Representation (TPTSSR) classifier were introduced in recent times. All these frameworks are supervised and passive in the sense that they cannot benefit from unlabeled data samples. In this paper, inspired by active learning paradigms, we introduce an active CRC that can be used by these frameworks. More precisely, we are interested in the TPTSSR framework due to its good performance and its reasonable computational cost. Our proposed Active Two Phase Collaborative Representation Classifier (ATPCRC) starts by predicting the label of the available unlabeled samples. At testing stage, two coding processes are carried out separately on the set of originally labeled samples and the whole set (original and predicted label). The two types of class-wise reconstruction errors are blended in order to decide the class of any test image. Experiments conducted on four public image datasets show that the proposed ATPCRC can outperform the classic TPTSSR as well as many state-of-the-art methods that exploit label and unlabeled data samples.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {36},
numpages = {10},
keywords = {active learning, Two phase collaborative representation classifier, semi-supervised learning, image categorization}
}

@article{10.1145/3332932,
author = {Yang, Wenmain and Wang, Kun and Ruan, Na and Gao, Wenyuan and Jia, Weijia and Zhao, Wei and Liu, Nan and Zhang, Yunyong},
title = {Time-Sync Video Tag Extraction Using Semantic Association Graph},
year = {2019},
issue_date = {August 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/3332932},
doi = {10.1145/3332932},
abstract = {Time-sync comments (TSCs) reveal a new way of extracting the online video tags. However, such TSCs have lots of noises due to users’ diverse comments, introducing great challenges for accurate and fast video tag extractions. In this article, we propose an unsupervised video tag extraction algorithm named Semantic Weight-Inverse Document Frequency (SW-IDF). Specifically, we first generate corresponding semantic association graph (SAG) using semantic similarities and timestamps of the TSCs. Second, we propose two graph cluster algorithms, i.e., dialogue-based algorithm and topic center-based algorithm, to deal with the videos with different density of comments. Third, we design a graph iteration algorithm to assign the weight to each comment based on the degrees of the clustered subgraphs, which can differentiate the meaningful comments from the noises. Finally, we gain the weight of each word by combining Semantic Weight (SW) and Inverse Document Frequency (IDF). In this way, the video tags are extracted automatically in an unsupervised way. Extensive experiments have shown that SW-IDF (dialogue-based algorithm) achieves 0.4210 F1-score and 0.4932 MAP (Mean Average Precision) in high-density comments, 0.4267 F1-score and 0.3623 MAP in low-density comments; while SW-IDF (topic center-based algorithm) achieves 0.4444 F1-score and 0.5122 MAP in high-density comments, 0.4207 F1-score and 0.3522 MAP in low-density comments. It has a better performance than the state-of-the-art unsupervised algorithms in both F1-score and MAP.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {37},
numpages = {24},
keywords = {semantic association graph, crowdsourced time-sync comments, video tagging, keywords extraction, Multimedia retrieval}
}

@article{10.1145/3326060,
author = {Huang, Yourong and Xiao, Zhu and Yu, Xiaoyou and Wang, Dong and Havyarimana, Vincent and Bai, Jing},
title = {Road Network Construction with Complex Intersections Based on Sparsely Sampled Private Car Trajectory Data},
year = {2019},
issue_date = {July 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3326060},
doi = {10.1145/3326060},
abstract = {A road network is a critical aspect of both urban planning and route recommendation. This article proposes an efficient approach to build a fine-grained road network based on sparsely sampled private car trajectory data under complex urban environment. In order to resolve difficulties introduced by low sampling rate trajectory data, we concentrate sample points around intersections by utilizing the turning characteristics from the large-scale trajectory data to ensure the accuracy of the detection of intersections and road segments. In front of complex road networks including many complex intersections, such as the overpasses and underpasses, we first layer intersections into major and minor one, and then propose a simplified representation of intersections and corresponding computable model based on the features of roads, which can significantly improve the accuracy of detected road networks, especially for the complex intersections. In order to construct fine-grained road networks, we distinguish various types of intersections using direction information and detected turning limit. To the best of our knowledge, our road network building method is the first time to give fine-grained road networks based on low-sampling rate private car trajectory data, especially able to infer the location of complex intersections and its connections to other intersections. Last but not the least, we propose an effective parameter selection process for the Density-Based Spatial Clustering of Applications with Noise based clustering algorithm, which is used to implement the reliable intersection detection. Extensive evaluations are conducted based on a real-world trajectory dataset from 1,345 private cars in Futian district, Shenzhen city of China. The results demonstrate the effectiveness of the proposed method. The constructed road network matches close to the one from a public editing map OpenStreetMap, especially the location of the road intersections and road segments, which achieves 92.2% intersections within 20m and 91.6% road segments within 8m.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {35},
numpages = {28},
keywords = {road networks, private cars, Trajectory data}
}

@article{10.1145/3320277,
author = {Zhang, Mingyue and Wei, Xuan and Guo, Xunhua and Chen, Guoqing and Wei, Qiang},
title = {Identifying Complements and Substitutes of Products: A Neural Network Framework Based on Product Embedding},
year = {2019},
issue_date = {July 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3320277},
doi = {10.1145/3320277},
abstract = {Complements and substitutes are two typical product relationships that deserve consideration in online product recommendation. One of the key objectives of recommender systems is to promote cross-selling, which heavily relies on recommending the appropriate type of products in specific scenarios. Research on consumer behavior has shown that consumers usually prefer substitutes in the browsing stage whereas complements in the purchasing stage. Thus, it is of great importance to identify the complementary and substitutable relationships between products. In this article, we design a neural network based framework that integrates the textual content and non-textual information of online reviews to mine product relationships. For the textual content, we utilize methods such as LDA topic modeling to represent products in a succinct form called “embedding.” To capture the semantics of complementary and substitutable relationships, we design a modeling process that transfers the product embeddings into semantic features and incorporates additional non-textual factors of product reviews. Extensive experiments are conducted to verify the effectiveness of the proposed product relationship mining model. The advantages and robustness of our model are discussed from various perspectives.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {34},
numpages = {29},
keywords = {product embedding, substitutes, online reviews, product recommendation, product relationship, Complements}
}

@article{10.1145/3328795,
author = {Iqbal, Mohsin and Karim, Asim and Kamiran, Faisal},
title = {Balancing Prediction Errors for Robust Sentiment Classification},
year = {2019},
issue_date = {July 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3328795},
doi = {10.1145/3328795},
abstract = {Sentiment classification is a popular text mining task in which textual content (e.g., a message) is assigned a polarity label (typically positive or negative) reflecting the sentiment expressed in it. Sentiment classification is used widely in applications like customer feedback analysis where robustness and correctness of results are critical. In this article, we highlight that prediction accuracy alone is not sufficient for assessing the performance of a sentiment classifier; it is also important that the classifier is not biased toward positive or negative polarity, thus distorting the distribution of positive and negative messages in the predictions. We propose a measure, called Polarity Bias Rate, for quantifying this bias in a sentiment classifier. Second, we present two methods for removing this bias in the predictions of unsupervised and supervised sentiment classifiers. Our first method, called Bias-Aware Thresholding (BAT), shifts the decision boundary to control the bias in the predictions. Motivated from cost-sensitive learning, BAT is easily applicable to both lexicon-based unsupervised and supervised classifiers. Our second method, called Balanced Logistic Regression (BLR) introduces a bias-remover constraint into the standard logistic regression model. BLR is an automatic bias-free supervised sentiment classifier.We evaluate our methods extensively on seven real-world datasets. The experiments involve two lexicon-based and two supervised sentiment classifiers and include evaluation on multiple train-test data sizes. The results show that bias is controlled effectively in predictions. Furthermore, prediction accuracy is also increased in many cases, thus enhancing the robustness of sentiment classification.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {33},
numpages = {21},
keywords = {Sentiment analysis, fairness in learning, lexicon-based methods, bias-aware sentiment analysis, supervised methods}
}

@article{10.1145/3321517,
author = {Ju, Fujiao and Sun, Yanfeng and Gao, Junbin and Antolovich, Michael and Dong, Junliang and Yin, Baocai},
title = {Tensorizing Restricted Boltzmann Machine},
year = {2019},
issue_date = {July 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3321517},
doi = {10.1145/3321517},
abstract = {Restricted Boltzmann machine (RBM) is a famous model for feature extraction and can be used as an initializer for neural networks. When applying the classic RBM to multidimensional data such as 2D/3D tensors, one needs to vectorize such as high-order data. Vectorizing will result in dimensional disaster and valuable spatial information loss. As RBM is a model with fully connected layers, it requires a large amount of memory. Therefore, it is difficult to use RBM with high-order data on low-end devices. In this article, to utilize classic RBM on tensorial data directly, we propose a new tensorial RBM model parameterized by the tensor train format (TTRBM). In this model, both visible and hidden variables are in tensorial form, which are connected by a parameter matrix in tensor train format. The biggest advantage of the proposed model is that TTRBM can obtain comparable performance compared with the classic RBM with much fewer model parameters and faster training process. To demonstrate the advantages of TTRBM, we conduct three real-world applications, face reconstruction, handwritten digit recognition, and image super-resolution in the experiments.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {30},
numpages = {16},
keywords = {Tensor, tensor train format, restricted Boltzmann machine}
}

@article{10.1145/3314105,
author = {Zhang, Xuchao and Lei, Shuo and Zhao, Liang and Boedihardjo, Arnold P. and Lu, Chang-Tien},
title = {Robust Regression via Heuristic Corruption Thresholding and Its Adaptive Estimation Variation},
year = {2019},
issue_date = {July 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3314105},
doi = {10.1145/3314105},
abstract = {The presence of data noise and corruptions has recently invoked increasing attention on robust least-squares regression (RLSR), which addresses this fundamental problem that learns reliable regression coefficients when response variables can be arbitrarily corrupted. Until now, the following important challenges could not be handled concurrently: (1) rigorous recovery guarantee of regression coefficients, (2) difficulty in estimating the corruption ratio parameter, and (3) scaling to massive datasets. This article proposes a novel Robust regression algorithm via Heuristic Corruption Thresholding (RHCT) that concurrently addresses all the above challenges. Specifically, the algorithm alternately optimizes the regression coefficients and estimates the optimal uncorrupted set via heuristic thresholding without a pre-defined corruption ratio parameter until its convergence. Moreover, to improve the efficiency of corruption estimation in large-scale data, a Robust regression algorithm via Adaptive Corruption Thresholding (RACT) is proposed to determine the size of the uncorrupted set in a novel adaptive search method without iterating data samples exhaustively. In addition, we prove that our algorithms benefit from strong guarantees analogous to those of state-of-the-art methods in terms of convergence rates and recovery guarantees. Extensive experiments demonstrate that the effectiveness of our new methods is superior to that of existing methods in the recovery of both regression coefficients and uncorrupted sets, with very competitive efficiency.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {28},
numpages = {22},
keywords = {adaptive search, adversarial data corruption, discrete optimization, hard thresholding, Robust regression}
}

@article{10.1145/3314107,
author = {Gan, Wensheng and Lin, Jerry Chun-Wei and Fournier-Viger, Philippe and Chao, Han-Chieh and Yu, Philip S.},
title = {A Survey of Parallel Sequential Pattern Mining},
year = {2019},
issue_date = {July 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3314107},
doi = {10.1145/3314107},
abstract = {With the growing popularity of shared resources, large volumes of complex data of different types are collected automatically. Traditional data mining algorithms generally have problems and challenges including huge memory cost, low processing speed, and inadequate hard disk space. As a fundamental task of data mining, sequential pattern mining (SPM) is used in a wide variety of real-life applications. However, it is more complex and challenging than other pattern mining tasks, i.e., frequent itemset mining and association rule mining, and also suffers from the above challenges when handling the large-scale data. To solve these problems, mining sequential patterns in a parallel or distributed computing environment has emerged as an important issue with many applications. In this article, an in-depth survey of the current status of parallel SPM (PSPM) is investigated and provided, including detailed categorization of traditional serial SPM approaches, and state-of-the art PSPM. We review the related work of PSPM in details including partition-based algorithms for PSPM, apriori-based PSPM, pattern-growth-based PSPM, and hybrid algorithms for PSPM, and provide deep description (i.e., characteristics, advantages, disadvantages, and summarization) of these parallel approaches of PSPM. Some advanced topics for PSPM, including parallel quantitative/weighted/utility SPM, PSPM from uncertain data and stream data, hardware acceleration for PSPM, are further reviewed in details. Besides, we review and provide some well-known open-source software of PSPM. Finally, we summarize some challenges and opportunities of PSPM in the big data era.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {25},
numpages = {34},
keywords = {data mining, Data science, parallelism, sequential pattern, big data}
}

@article{10.1145/3314202,
author = {Wang, Zheng and Ye, Xiaojun and Wang, Chaokun and Yu, Philip S.},
title = {Feature Selection via Transferring Knowledge Across Different Classes},
year = {2019},
issue_date = {June 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3314202},
doi = {10.1145/3314202},
abstract = {The problem of feature selection has attracted considerable research interest in recent years. Supervised information is capable of significantly improving the quality of selected features. However, existing supervised feature selection methods all require that classes in the labeled data (source domain) and unlabeled data (target domain) to be identical, which may be too restrictive in many cases. In this article, we consider a more challenging cross-class setting where the classes in these two domains are related but different, which has rarely been studied before. We propose a cross-class knowledge transfer feature selection framework which transfers the cross-class knowledge from the source domain to guide target domain feature selection. Specifically, high-level descriptions, i.e., attributes, are used as the bridge for knowledge transfer. To further improve the quality of the selected features, our framework jointly considers the tasks of cross-class knowledge transfer and feature selection. Experimental results on four benchmark datasets demonstrate the superiority of the proposed method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {22},
numpages = {29},
keywords = {dimension reduction, Feature selection, supervision transfer}
}

@article{10.1145/3310227,
author = {Zhou, Yao and Ying, Lei and He, Jingrui},
title = {Multi-Task Crowdsourcing via an Optimization Framework},
year = {2019},
issue_date = {July 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3310227},
doi = {10.1145/3310227},
abstract = {The unprecedented amounts of data have catalyzed the trend of combining human insights with machine learning techniques, which facilitate the use of crowdsourcing to enlist label information both effectively and efficiently. One crucial challenge in crowdsourcing is the diverse worker quality, which determines the accuracy of the label information provided by such workers. Motivated by the observations that same set of tasks are typically labeled by the same set of workers, we studied their behaviors across multiple related tasks and proposed an optimization framework for learning from task and worker dual heterogeneity. The proposed method uses a weight tensor to represent the workers’ behaviors across multiple tasks, and seeks to find the optimal solution of the tensor by exploiting its structured information. Then, we propose an iterative algorithm to solve the optimization problem and analyze its computational complexity. To infer the true label of an example, we construct a worker ensemble based on the estimated tensor, whose decisions will be weighted using a set of entropy weight. We also prove that the gradient of the most time-consuming updating block is separable with respect to the workers, which leads to a randomized algorithm with faster speed. Moreover, we extend the learning framework to accommodate to the multi-class setting. Finally, we test the performance of our framework on several datasets, and demonstrate its superiority over state-of-the-art techniques.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {27},
numpages = {26},
keywords = {entropy ensemble, tensor representation, crowdsourcing, optimization, Multi-task learning}
}

@article{10.1145/3320482,
author = {Liu, Chenyang and Cao, Jian and Feng, Shanshan},
title = {Leveraging Kernel-Incorporated Matrix Factorization for App Recommendation},
year = {2019},
issue_date = {July 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3320482},
doi = {10.1145/3320482},
abstract = {The ever-increasing number of smartphone applications (apps) available on different app markets poses a challenge for personalized app recommendation. Conventional collaborative filtering-based recommendation methods suffer from sparse and binary user-app implicit feedback, which results in poor performance in discriminating user-app preferences. In this article, we first propose two kernel incorporated probabilistic matrix factorization models, which introduce app-categorical information to constrain the user and app latent features to be similar to their neighbors in the latent space. The two models are solved by Stochastic Gradient Descent with a user-oriented negative sampling scheme. To further improve the recommendation performance, we construct pseudo user-app ratings based on user-app usage information, and propose a novel kernelized non-negative matrix factorization by incorporating non-negative constraints on latent factors to predict user-app preferences. This model also leverages user--user and app--app similarities with regard to app-categorical information to mine the latent geometric structure in the pseudo-rating space. Adopting the Karush--Kuhn--Tucker conditions, a Multiplicative Updating Rules based optimization is proposed for model learning, and the convergence is proved by introducing an auxiliary function. The experimental results on a real user-app installation usage dataset show the comparable performance of our models with the state-of-the-art baselines in terms of two ranking-oriented evaluation metrics.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {31},
numpages = {27},
keywords = {App recommendation, kernel function, non-negative matrix factorization, probabilistic matrix factorization}
}

@article{10.1145/3320489,
author = {Dehghan, Mahdi and Abin, Ahmad Ali},
title = {Translations Diversification for Expert Finding: A Novel Clustering-Based Approach},
year = {2019},
issue_date = {July 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3320489},
doi = {10.1145/3320489},
abstract = {Expert finding is the task of retrieving and ranking knowledgeable people in the subject of user’s query. It is a well-studied problem that has attracted the attention of many researchers. The most important challenge in expert finding is to determine the similarity between query words and documents authored by candidate experts. One of the most important challenges in Information Retrieval (IR) community is the issue of vocabulary gap between queries and documents. In this study, a translation model based on words clustering in two query and co-occurrence spaces is proposed to overcome this problem. First, the words that are semantically close, are clustered in a query space and then each cluster in this space are clustered again in a co-occurrence space. Representatives of each cluster in the co-occurrence space are considered as a diverse subset of the parent cluster. By this method, the query translations are expected to be diversified in the query space. Next, a probabilistic model, that is based on the belonging degree of word to cluster and similarity of cluster to query in the query space, is used to consider the problem of vocabulary gap. Finally, the corresponding translations to each query are used in conjunction with a combination model for expert finding. Experiments on Stack Overflow dataset show the effectiveness of the proposed method for expert finding.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {32},
numpages = {20},
keywords = {translation diversification, Expert finding, data clustering, translation model, Stack Overflow}
}

@article{10.1145/3314204,
author = {Mahmoudi, Amin and Yaakub, Mohd Ridzwan and Bakar, Azuraliza Abu},
title = {The Relationship between Online Social Network Ties and User Attributes},
year = {2019},
issue_date = {July 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3314204},
doi = {10.1145/3314204},
abstract = {The distance between users has an effect on the formation of social network ties, but it is not the only or even the main factor. Knowing all the features that influence such ties is very important for many related domains such as location-based recommender systems and community and event detection systems for online social networks (OSNs). In recent years, researchers have analyzed the role of user geo-location in OSNs. Researchers have also attempted to determine the probability of friendships being established based on distance, where friendship is not only a function of distance. However, some important features of OSNs remain unknown. In order to comprehensively understand the OSN phenomenon, we also need to analyze users’ attributes. Basically, an OSN functions according to four main user properties: user geo-location, user weight, number of user interactions, and user lifespan. The research presented here sought to determine whether the user mobility pattern can be used to predict users’ interaction behavior. It also investigated whether, in addition to distance, the number of friends (known as user weight) interferes in social network tie formation. To this end, we analyzed the above-stated features in three large-scale OSNs. We found that regardless of a high degree freedom in user mobility, the fraction of the number of outside activities over the inside activity is a significant fraction that helps us to address the user interaction behavior. To the best of our knowledge, research has not been conducted elsewhere on this issue. We also present a high-resolution formula in order to improve the friendship probability function.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {26},
numpages = {15},
keywords = {tie formation, Distance, online social network, IO-fraction, user weight}
}

@article{10.1145/3314106,
author = {Wang, Zhitao and Chen, Chengyao and Li, Wenjie},
title = {Information Diffusion Prediction with Network Regularized Role-Based User Representation Learning},
year = {2019},
issue_date = {July 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/3314106},
doi = {10.1145/3314106},
abstract = {In this article, we aim at developing a user representation learning model to solve the information diffusion prediction problem in social media. The main idea is to project the diffusion users into a continuous latent space as the role-based (sender and receiver) representations, which capture unique diffusion characteristics of users. The model learns the role-based representations based on a cascade modeling objective that aims at maximizing the likelihood of observed cascades, and employs the matrix factorization objective of reconstructing structural proximities as a regularization on representations. By jointly embedding the information of cascades and network, the learned representations are robust on different diffusion data. We evaluate the proposed model on three real-world datasets. The experimental results demonstrate the better performance of the proposed model than state-of-the-art diffusion embedding and network embedding models and other popular graph-based methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {29},
numpages = {23},
keywords = {diffusion role, network regularization, representation learning, Information diffusion}
}

@article{10.1145/3314203,
author = {Hong, Junyuan and Li, Yang and Chen, Huanhuan},
title = {Variant Grassmann Manifolds: A Representation Augmentation Method for Action Recognition},
year = {2019},
issue_date = {June 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3314203},
doi = {10.1145/3314203},
abstract = {In classification tasks, classifiers trained with finite examples might generalize poorly to new data with unknown variance. For this issue, data augmentation is a successful solution where numerous artificial examples are added to training sets. In this article, we focus on the data augmentation for improving the accuracy of action recognition, where action videos are modeled by linear dynamical systems and approximately represented as linear subspaces. These subspace representations lie in a non-Euclidean space, named Grassmann manifold, containing points as orthonormal matrixes. It is our concern that poor generalization may result from the variance of manifolds when data come from different sources or classes. Thus, we introduce infinitely many variant Grassmann manifolds (VGM) subject to a known distribution, then represent each action video as different Grassmann points leading to augmented representations. Furthermore, a prior based on the stability of subspace bases is introduced, so the manifold distribution can be adaptively determined, balancing discrimination and representation. Experimental results of multi-class and multi-source classification show that VGM softmax classifiers achieve lower test error rates compared to methods with a single manifold.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {23},
numpages = {23},
keywords = {data augmentation, action recognition, Representation learning, Grassmann manifold}
}

@article{10.1145/3319911,
author = {Guo, Yumeng and Chung, Fulai and Li, Guozheng and Wang, Jiancong and Gee, James C.},
title = {Leveraging Label-Specific Discriminant Mapping Features for Multi-Label Learning},
year = {2019},
issue_date = {June 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3319911},
doi = {10.1145/3319911},
abstract = {As an important machine learning task, multi-label learning deals with the problem where each sample instance (feature vector) is associated with multiple labels simultaneously. Most existing approaches focus on manipulating the label space, such as exploiting correlations between labels and reducing label space dimension, with identical feature space in the process of classification. One potential drawback of this traditional strategy is that each label might have its own specific characteristics and using identical features for all label cannot lead to optimized performance. In this article, we propose an effective algorithm named LSDM, i.e., leveraging label-specific discriminant mapping features for multi-label learning, to overcome the drawback. LSDM sets diverse ratio parameter values to conduct cluster analysis on the positive and negative instances of identical label. It reconstructs label-specific feature space which includes distance information and spatial topology information. Our experimental results show that combining these two parts of information in the new feature representation can better exploit the clustering results in the learning process. Due to the problem of diverse combinations for identical label, we employ simplified linear discriminant analysis to efficiently excavate optimal one for each label and perform classification by querying the corresponding results. Comparison with the state-of-the-art algorithms on a total of 20 benchmark datasets clearly manifests the competitiveness of LSDM.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {24},
numpages = {23},
keywords = {multi-label learning, Machine learning, label specific features}
}

@article{10.1145/3309712,
author = {Cadena, Jose and Chen, Feng and Vullikanti, Anil},
title = {Near-Optimal and Practical Algorithms for Graph Scan Statistics with Connectivity Constraints},
year = {2019},
issue_date = {June 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3309712},
doi = {10.1145/3309712},
abstract = {One fundamental task in network analysis is detecting “hotspots” or “anomalies” in the network; that is, detecting subgraphs where there is significantly more activity than one would expect given historical data or some baseline process. Scan statistics is one popular approach used for anomalous subgraph detection. This methodology involves maximizing a score function over all connected subgraphs, which is a challenging computational problem. A number of heuristics have been proposed for these problems, but they do not provide any quality guarantees. Here, we propose a framework for designing algorithms for optimizing a large class of scan statistics for networks, subject to connectivity constraints. Our algorithms run in time that scales linearly on the size of the graph and depends on a parameter we call the “effective solution size,” while providing rigorous approximation guarantees. In contrast, most prior methods have super-linear running times in terms of graph size. Extensive empirical evidence demonstrates the effectiveness and efficiency of our proposed algorithms in comparison with state-of-the-art methods. Our approach improves on the performance relative to all prior methods, giving up to over 25% increase in the score. Further, our algorithms scale to networks with up to a million nodes, which is 1--2 orders of magnitude larger than all prior applications.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {20},
numpages = {33},
keywords = {parameterized complexity, anomalous subgraph detection, Scan statistics, graph anomaly detection}
}

@article{10.1145/3309541,
author = {Jiang, Bingbing and Li, Chang and Rijke, Maarten De and Yao, Xin and Chen, Huanhuan},
title = {Probabilistic Feature Selection and Classification Vector Machine},
year = {2019},
issue_date = {June 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3309541},
doi = {10.1145/3309541},
abstract = {Sparse Bayesian learning is a state-of-the-art supervised learning algorithm that can choose a subset of relevant samples from the input data and make reliable probabilistic predictions. However, in the presence of high-dimensional data with irrelevant features, traditional sparse Bayesian classifiers suffer from performance degradation and low efficiency due to the incapability of eliminating irrelevant features. To tackle this problem, we propose a novel sparse Bayesian embedded feature selection algorithm that adopts truncated Gaussian distributions as both sample and feature priors. The proposed algorithm, called probabilistic feature selection and classification vector machine (PFCVMLP) is able to simultaneously select relevant features and samples for classification tasks. In order to derive the analytical solutions, Laplace approximation is applied to compute approximate posteriors and marginal likelihoods. Finally, parameters and hyperparameters are optimized by the type-II maximum likelihood method. Experiments on three datasets validate the performance of PFCVMLP along two dimensions: classification performance and effectiveness for feature selection. Finally, we analyze the generalization performance and derive a generalization error bound for PFCVMLP. By tightening the bound, the importance of feature selection is demonstrated.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {21},
numpages = {27},
keywords = {EEG emotion recognition, Feature selection, probabilistic classification model, sparse Bayesian learning, supervised learning}
}

@article{10.1145/3301304,
author = {Katib, Anas and Rao, Praveen and Barnard, Kobus and Kamhoua, Charles},
title = {Fast Approximate Score Computation on Large-Scale Distributed Data for Learning Multinomial Bayesian Networks},
year = {2019},
issue_date = {June 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3301304},
doi = {10.1145/3301304},
abstract = {In this article, we focus on the problem of learning a Bayesian network over distributed data stored in a commodity cluster. Specifically, we address the challenge of computing the scoring function over distributed data in an efficient and scalable manner, which is a fundamental task during learning. While exact score computation can be done using the MapReduce-style computation, our goal is to compute approximate scores much faster with probabilistic error bounds and in a scalable manner. We propose a novel approach, which is designed to achieve the following: (a) decentralized score computation using the principle of gossiping; (b) lower resource consumption via a probabilistic approach for maintaining scores using the properties of a Markov chain; and (c) effective distribution of tasks during score computation (on large datasets) by synergistically combining well-known hashing techniques. We conduct theoretical analysis of our approach in terms of convergence speed of the statistics required for score computation, and memory and network bandwidth consumption. We also discuss how our approach is capable of efficiently recomputing scores when new data are available. We conducted a comprehensive evaluation of our approach and compared with the MapReduce-style computation using datasets of different characteristics on a 16-node cluster. When the MapReduce-style computation provided exact statistics for score computation, it was nearly 10 times slower than our approach. Although it ran faster on randomly sampled datasets than on the entire datasets, it performed worse than our approach in terms of accuracy. Our approach achieved high accuracy (below 6% average relative error) in estimating the statistics for approximate score computation on all the tested datasets. In conclusion, it provides a feasible tradeoff between computation time and accuracy for fast approximate score computation on large-scale distributed data.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {14},
numpages = {40},
keywords = {gossip algorithms, bayesian networks, structure learning, distributed data, Approximate score computation}
}

@article{10.1145/3300230,
author = {Ma, Liang and Srivatsa, Mudhakar and Cansever, Derya and Yan, Xifeng and Kase, Sue and Vanni, Michelle},
title = {Performance Bounds of Decentralized Search in Expert Networks for Query Answering},
year = {2019},
issue_date = {June 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3300230},
doi = {10.1145/3300230},
abstract = {Expert networks are formed by a group of expert-professionals with different specialties to collaboratively resolve specific queries posted to the network. In such networks, when a query reaches an expert who does not have sufficient expertise, this query needs to be routed to other experts for further processing until it is completely solved; therefore, query answering efficiency is sensitive to the underlying query routing mechanism being used. Among all possible query routing mechanisms, decentralized search, operating purely on each expert’s local information without any knowledge of network global structure, represents the most basic and scalable routing mechanism, which is applicable to any network scenarios even in dynamic networks. However, there is still a lack of fundamental understanding of the efficiency of decentralized search in expert networks. In this regard, we investigate decentralized search by quantifying its performance under a variety of network settings. Our key findings reveal the existence of network conditions, under which decentralized search can achieve significantly short query routing paths (i.e., between O(log n) and O(log2 n) hops, n: total number of experts in the network). Based on such theoretical foundation, we further study how the unique properties of decentralized search in expert networks are related to the anecdotal small-world phenomenon. In addition, we demonstrate that decentralized search is robust against estimation errors introduced by misinterpreting the required expertise levels. The developed performance bounds, confirmed by real datasets, are able to assist in predicting network performance and designing complex expert networks.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {18},
numpages = {23},
keywords = {Expert networks, decentralized search, query answering, theory, performance bounds}
}

@article{10.1145/3310254,
author = {Jha, Kishlay and Xun, Guangxu and Gopalakrishnan, Vishrawas and Zhang, Aidong},
title = {DWE-Med: Dynamic Word Embeddings for Medical Domain},
year = {2019},
issue_date = {June 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3310254},
doi = {10.1145/3310254},
abstract = {Recent advances in unsupervised language processing methods have created an opportunity to exploit massive text corpora for developing high-quality vector space representation (also known as word embeddings) of words. Towards this direction, practitioners have developed and applied several data driven embedding models with quite good rate of success. However, a drawback of these models lies in their premise of static context; wherein, the meaning of a word is assumed to remain the same over the period of time. This is limiting because it is known that the semantic meaning of a concept evolves over time. While such semantic drifts are routinely observed in almost all the domains; their effect is acute in domain such as biomedicine, where the semantic meaning of a concept changes relatively fast. To address this, in this study, we aim to learn temporally aware vector representation of medical concepts from the timestamped text data, and in doing so provide a systematic approach to formalize the problem. More specifically, a dynamic word embedding based model that jointly learns the temporal characteristics of medical concepts and performs across time-alignment is proposed. Apart from capturing the evolutionary characteristics in an optimal manner, the model also factors in the implicit medical properties useful for a variety of bio-medical applications. Empirical studies conducted on two important bio-medical use cases validates the effectiveness of the proposed approach and suggests that the model not only learns quality embeddings but also facilitates intuitive trajectory visualizations.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {19},
numpages = {21},
keywords = {word embeddings, temporal dynamics, Biomedical domain}
}

@article{10.1145/3301303,
author = {Gao, Xiaofeng and Cao, Zhenhao and Li, Sha and Yao, Bin and Chen, Guihai and Tang, Shaojie},
title = {Taxonomy and Evaluation for Microblog Popularity Prediction},
year = {2019},
issue_date = {June 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3301303},
doi = {10.1145/3301303},
abstract = {As social networks become a major source of information, predicting the outcome of information diffusion has appeared intriguing to both researchers and practitioners. By organizing and categorizing the joint efforts of numerous studies on popularity prediction, this article presents a hierarchical taxonomy and helps to establish a systematic overview of popularity prediction methods for microblog. Specifically, we uncover three lines of thoughts: the feature-based approach, time-series modelling, and the collaborative filtering approach and analyse them, respectively. Furthermore, we also categorize prediction methods based on their underlying rationale: whether they attempt to model the motivation of users or monitor the early responses. Finally, we put these prediction methods to test by performing experiments on real-life data collected from popular social networks Twitter and Weibo. We compare the methods in terms of accuracy, efficiency, timeliness, robustness, and bias.As far as we are concerned, there is no precedented survey aimed at microblog popularity prediction at the time of submission. By establishing a taxonomy and evaluation for the first time, we hope to provide an in-depth review of state-of-the-art prediction methods and point out directions for further research. Our evaluations show that time-series modelling has the advantage of high accuracy and the ability to improve over time. The feature-based methods using only temporal features performs nearly as well as using all possible features, producing average results. This suggests that temporal features do have strong predictive power and that power is better exploited with time-series models. On the other hand, this implies that we know little about the future popularity of an item before it is posted, which may be the focus of further research.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {15},
numpages = {40},
keywords = {evaluation, Social network, popularity prediction, taxonomy}
}

@article{10.1145/3301300,
author = {Teinemaa, Irene and Dumas, Marlon and Rosa, Marcello La and Maggi, Fabrizio Maria},
title = {Outcome-Oriented Predictive Process Monitoring: Review and Benchmark},
year = {2019},
issue_date = {June 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3301300},
doi = {10.1145/3301300},
abstract = {Predictive business process monitoring refers to the act of making predictions about the future state of ongoing cases of a business process, based on their incomplete execution traces and logs of historical (completed) traces. Motivated by the increasingly pervasive availability of fine-grained event data about business process executions, the problem of predictive process monitoring has received substantial attention in the past years. In particular, a considerable number of methods have been put forward to address the problem of outcome-oriented predictive process monitoring, which refers to classifying each ongoing case of a process according to a given set of possible categorical outcomes—e.g., Will the customer complain or not? Will an order be delivered, canceled, or withdrawn? Unfortunately, different authors have used different datasets, experimental settings, evaluation measures, and baselines to assess their proposals, resulting in poor comparability and an unclear picture of the relative merits and applicability of different methods. To address this gap, this article presents a systematic review and taxonomy of outcome-oriented predictive process monitoring methods, and a comparative experimental evaluation of eleven representative methods using a benchmark covering 24 predictive process monitoring tasks based on nine real-life event logs.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {17},
numpages = {57},
keywords = {Business process, predictive monitoring, sequence classification}
}

@article{10.1145/3301302,
author = {Yan, Ruidong and Li, Yi and Wu, Weili and Li, Deying and Wang, Yongcai},
title = {Rumor Blocking through Online Link Deletion on Social Networks},
year = {2019},
issue_date = {June 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {13},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/3301302},
doi = {10.1145/3301302},
abstract = {In recent years, social networks have become important platforms for people to disseminate information. However, we need to take effective measures such as blocking a set of links to control the negative rumors spreading over the network. In this article, we propose a Rumor Spread Minimization (RSM) problem, i.e., we remove an edge set from network such that the rumor spread is minimized.

license_type: permissive

extension: bib