text:
81},
url = {https://doi.org/10.1145/2499907.2499909},
doi = {10.1145/2499907.2499909},
abstract = {Learning explanatory features across multiple related tasks, or MultiTask Feature Selection (MTFS), is an important problem in the applications of data mining, machine learning, and bioinformatics. Previous MTFS methods fulfill this task by batch-mode training. This makes them inefficient when data come sequentially or when the number of training data is so large that they cannot be loaded into the memory simultaneously. In order to tackle these problems, we propose a novel online learning framework to solve the MTFS problem. A main advantage of the online algorithm is its efficiency in both time complexity and memory cost. The weights of the MTFS models at each iteration can be updated by closed-form solutions based on the average of previous subgradients. This yields the worst-case bounds of the time complexity and memory cost at each iteration, both in the order of O(d \texttimes{} Q), where d is the number of feature dimensions and Q is the number of tasks. Moreover, we provide theoretical analysis for the average regret of the online learning algorithms, which also guarantees the convergence rate of the algorithms. Finally, we conduct detailed experiments to show the characteristics and merits of the online learning algorithms in solving several MTFS problems.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {6},
numpages = {27},
keywords = {Supervised learning, online learning, dual averaging method, multitask learning, feature selection}
}

@article{10.1145/2499907.2499910,
author = {Zhang, Yu and Yeung, Dit-Yan},
title = {Multilabel Relationship Learning},
year = {2013},
issue_date = {July 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2499907.2499910},
doi = {10.1145/2499907.2499910},
abstract = {Multilabel learning problems are commonly found in many applications. A characteristic shared by many multilabel learning problems is that some labels have significant correlations between them. In this article, we propose a novel multilabel learning method, called MultiLabel Relationship Learning (MLRL), which extends the conventional support vector machine by explicitly learning and utilizing the relationships between labels. Specifically, we model the label relationships using a label covariance matrix and use it to define a new regularization term for the optimization problem. MLRL learns the model parameters and the label covariance matrix simultaneously based on a unified convex formulation. To solve the convex optimization problem, we use an alternating method in which each subproblem can be solved efficiently. The relationship between MLRL and two widely used maximum margin methods for multilabel learning is investigated. Moreover, we also propose a semisupervised extension of MLRL, called SSMLRL, to demonstrate how to make use of unlabeled data to help learn the label covariance matrix. Through experiments conducted on some multilabel applications, we find that MLRL not only gives higher classification accuracy but also has better interpretability as revealed by the label covariance matrix.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {7},
numpages = {30},
keywords = {Multilabel learning, label relationship}
}

@article{10.1145/2499907.2499908,
author = {Lou, Tiancheng and Tang, Jie and Hopcroft, John and Fang, Zhanpeng and Ding, Xiaowen},
title = {Learning to Predict Reciprocity and Triadic Closure in Social Networks},
year = {2013},
issue_date = {July 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2499907.2499908},
doi = {10.1145/2499907.2499908},
abstract = {We study how links are formed in social networks. In particular, we focus on investigating how a reciprocal (two-way) link, the basic relationship in social networks, is developed from a parasocial (one-way) relationship and how the relationships further develop into triadic closure, one of the fundamental processes of link formation.We first investigate how geographic distance and interactions between users influence the formation of link structure among users. Then we study how social theories including homophily, social balance, and social status are satisfied over networks with parasocial and reciprocal relationships. The study unveils several interesting phenomena. For example, “friend's friend is a friend” indeed exists in the reciprocal relationship network, but does not hold in the parasocial relationship network.We propose a learning framework to formulate the problems of predicting reciprocity and triadic closure into a graphical model. We demonstrate that it is possible to accurately infer 90% of reciprocal relationships in a Twitter network. The proposed model also achieves better performance (+20--30% in terms of F1-measure) than several alternative methods for predicting the triadic closure formation.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {5},
numpages = {25},
keywords = {social influence, link prediction, Social network, predictive model, Twitter, reciprocal relationship}
}

@article{10.1145/2601433,
author = {Webb, Geoffrey I. and Vreeken, Jilles},
title = {Efficient Discovery of the Most Interesting Associations},
year = {2013},
issue_date = {June 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2601433},
doi = {10.1145/2601433},
abstract = {Self-sufficient itemsets have been proposed as an effective approach to summarizing the key associations in data. However, their computation appears highly demanding, as assessing whether an itemset is self-sufficient requires consideration of all pairwise partitions of the itemset into pairs of subsets as well as consideration of all supersets. This article presents the first published algorithm for efficiently discovering self-sufficient itemsets. This branch-and-bound algorithm deploys two powerful pruning mechanisms based on upper bounds on itemset value and statistical significance level. It demonstrates that finding top-k productive and nonredundant itemsets, with postprocessing to identify those that are not independently productive, can efficiently identify small sets of key associations. We present extensive evaluation of the strengths and limitations of the technique, including comparisons with alternative approaches to finding the most interesting associations.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {15},
numpages = {31},
keywords = {statistical association mining, itemset mining, interestingness, Association mining}
}

@article{10.1145/2601438,
author = {Ahmed, Nesreen K. and Neville, Jennifer and Kompella, Ramana},
title = {Network Sampling: From Static to Streaming Graphs},
year = {2013},
issue_date = {June 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2601438},
doi = {10.1145/2601438},
abstract = {Network sampling is integral to the analysis of social, information, and biological networks. Since many real-world networks are massive in size, continuously evolving, and/or distributed in nature, the network structure is often sampled in order to facilitate study. For these reasons, a more thorough and complete understanding of network sampling is critical to support the field of network science. In this paper, we outline a framework for the general problem of network sampling by highlighting the different objectives, population and units of interest, and classes of network sampling methods. In addition, we propose a spectrum of computational models for network sampling methods, ranging from the traditionally studied model based on the assumption of a static domain to a more challenging model that is appropriate for streaming domains. We design a family of sampling methods based on the concept of graph induction that generalize across the full spectrum of computational models (from static to streaming) while efficiently preserving many of the topological properties of the input graphs. Furthermore, we demonstrate how traditional static sampling algorithms can be modified for graph streams for each of the three main classes of sampling methods: node, edge, and topology-based sampling. Experimental results indicate that our proposed family of sampling methods more accurately preserve the underlying properties of the graph in both static and streaming domains. Finally, we study the impact of network sampling algorithms on the parameter estimation and performance evaluation of relational classification algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {7},
numpages = {56},
keywords = {graph streams, relational classification, social network analysis, Network sampling}
}

@article{10.1145/2536775,
author = {Eyal, Ron and Rosenfeld, Avi and Sina, Sigal and Kraus, Sarit},
title = {Predicting and Identifying Missing Node Information in Social Networks},
year = {2013},
issue_date = {June 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2536775},
doi = {10.1145/2536775},
abstract = {In recent years, social networks have surged in popularity. One key aspect of social network research is identifying important missing information that is not explicitly represented in the network, or is not visible to all. To date, this line of research typically focused on finding the connections that are missing between nodes, a challenge typically termed as the link prediction problem.This article introduces the missing node identification problem, where missing members in the social network structure must be identified. In this problem, indications of missing nodes are assumed to exist. Given these indications and a partial network, we must assess which indications originate from the same missing node and determine the full network structure.Toward solving this problem, we present the missing node identification by spectral clustering algorithm (MISC), an approach based on a spectral clustering algorithm, combined with nodes’ pairwise affinity measures that were adopted from link prediction research. We evaluate the performance of our approach in different problem settings and scenarios, using real-life data from Facebook. The results show that our approach has beneficial results and can be effective in solving the missing node identification problem. In addition, this article also presents R-MISC, which uses a sparse matrix representation, efficient algorithms for calculating the nodes’ pairwise affinity, and a proprietary dimension reduction technique to enable scaling the MISC algorithm to large networks of more than 100,000 nodes. Last, we consider problem settings where some of the indications are unknown. Two algorithms are suggested for this problem: speculative MISC, based on MISC, and missing link completion, based on classical link prediction literature. We show that speculative MISC outperforms missing link completion.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jun,
articleno = {14},
numpages = {35},
keywords = {missing nodes, spectral clustering, Social networks}
}

@article{10.1145/2435209.2435210,
author = {Angiulli, Fabrizio and Fassetti, Fabio},
title = {Nearest Neighbor-Based Classification of Uncertain Data},
year = {2013},
issue_date = {March 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2435209.2435210},
doi = {10.1145/2435209.2435210},
abstract = {This work deals with the problem of classifying uncertain data. With this aim we introduce the Uncertain Nearest Neighbor (UNN) rule, which represents the generalization of the deterministic nearest neighbor rule to the case in which uncertain objects are available. The UNN rule relies on the concept of nearest neighbor class, rather than on that of nearest neighbor object. The nearest neighbor class of a test object is the class that maximizes the probability of providing its nearest neighbor. The evidence is that the former concept is much more powerful than the latter in the presence of uncertainty, in that it correctly models the right semantics of the nearest neighbor decision rule when applied to the uncertain scenario. An effective and efficient algorithm to perform uncertain nearest neighbor classification of a generic (un)certain test object is designed, based on properties that greatly reduce the temporal cost associated with nearest neighbor class probability computation. Experimental results are presented, showing that the UNN rule is effective and efficient in classifying uncertain data.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {1},
numpages = {35},
keywords = {probability density functions, nearest neighbor, nearest neighbor rule, Classification, uncertain data}
}

@article{10.1145/2435209.2435212,
author = {Bayati, Mohsen and Gleich, David F. and Saberi, Amin and Wang, Ying},
title = {Message-Passing Algorithms for Sparse Network Alignment},
year = {2013},
issue_date = {March 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2435209.2435212},
doi = {10.1145/2435209.2435212},
abstract = {Network alignment generalizes and unifies several approaches for forming a matching or alignment between the vertices of two graphs. We study a mathematical programming framework for network alignment problem and a sparse variation of it where only a small number of matches between the vertices of the two graphs are possible. We propose a new message passing algorithm that allows us to compute, very efficiently, approximate solutions to the sparse network alignment problems with graph sizes as large as hundreds of thousands of vertices. We also provide extensive simulations comparing our algorithms with two of the best solvers for network alignment problems on two synthetic matching problems, two bioinformatics problems, and three large ontology alignment problems including a multilingual problem with a known labeled alignment.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {3},
numpages = {31},
keywords = {Network alignment, message-passing, belief propagation, graph matching}
}

@article{10.1145/2435209.2435213,
author = {Li, Bin and Hoi, Steven C. H. and Zhao, Peilin and Gopalkrishnan, Vivekanand},
title = {Confidence Weighted Mean Reversion Strategy for Online Portfolio Selection},
year = {2013},
issue_date = {March 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2435209.2435213},
doi = {10.1145/2435209.2435213},
abstract = {Online portfolio selection has been attracting increasing attention from the data mining and machine learning communities. All existing online portfolio selection strategies focus on the first order information of a portfolio vector, though the second order information may also be beneficial to a strategy. Moreover, empirical evidence shows that relative stock prices may follow the mean reversion property, which has not been fully exploited by existing strategies. This article proposes a novel online portfolio selection strategy named Confidence Weighted Mean Reversion (CWMR). Inspired by the mean reversion principle in finance and confidence weighted online learning technique in machine learning, CWMR models the portfolio vector as a Gaussian distribution, and sequentially updates the distribution by following the mean reversion trading principle. CWMR’s closed-form updates clearly reflect the mean reversion trading idea. We also present several variants of CWMR algorithms, including a CWMR mixture algorithm that is theoretical universal. Empirically, CWMR strategy is able to effectively exploit the power of mean reversion for online portfolio selection. Extensive experiments on various real markets show that the proposed strategy is superior to the state-of-the-art techniques. The experimental testbed including source codes and data sets is available online.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {4},
numpages = {38},
keywords = {mean reversion, online learning, Portfolio selection, confidence weighted learning}
}

@article{10.1145/2435209.2435211,
author = {Wang, Dingding and Zhu, Shenghuo and Li, Tao and Gong, Yihong},
title = {Comparative Document Summarization via Discriminative Sentence Selection},
year = {2013},
issue_date = {March 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {7},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2435209.2435211},
doi = {10.1145/2435209.2435211},
abstract = {Given a collection of document groups, a natural question is to identify the differences among these groups. Although traditional document summarization techniques can summarize the content of the document groups one by one, there exists a great necessity to generate a summary of the differences among the document groups. In this article, we study a novel problem of summarizing the differences between document groups. A discriminative sentence selection method is proposed to extract the most discriminative sentences that represent the specific characteristics of each document group. Experiments and case studies on real-world data sets demonstrate the effectiveness of our proposed method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {2},
numpages = {18},
keywords = {discriminative sentence selection, Comparative document summarization}
}

@article{10.1145/2382577.2382578,
author = {Ghosh, Joydeep and Smyth, Padhraic and Tomkins, Andrew and Caruana, Rich},
title = {Special Issue on Best of SIGKDD 2011},
year = {2012},
issue_date = {December 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2382577.2382578},
doi = {10.1145/2382577.2382578},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {14},
numpages = {2}
}

@article{10.1145/2382577.2382583,
author = {Wilkinson, Leland and Anand, Anushka and Dang, Tuan Nhon},
title = {Substantial Improvements in the Set-Covering Projection Classifier CHIRP (Composite Hypercubes on Iterated Random Projections)},
year = {2012},
issue_date = {December 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2382577.2382583},
doi = {10.1145/2382577.2382583},
abstract = {In Wilkinson et al. [2011] we introduced a new set-covering random projection classifier that achieved average error lower than that of other classifiers in the Weka platform. This classifier was based on an L∞ norm distance function and exploited an iterative sequence of three stages (projecting, binning, and covering) to deal with the curse of dimensionality, computational complexity, and nonlinear separability. We now present substantial changes that improve robustness and reduce training and testing time by almost an order of magnitude without jeopardizing CHIRP's outstanding error performance.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {19},
numpages = {18},
keywords = {random projections, Supervised classification}
}

@article{10.1145/2382577.2382582,
author = {Chattopadhyay, Rita and Sun, Qian and Fan, Wei and Davidson, Ian and Panchanathan, Sethuraman and Ye, Jieping},
title = {Multisource Domain Adaptation and Its Application to Early Detection of Fatigue},
year = {2012},
issue_date = {December 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2382577.2382582},
doi = {10.1145/2382577.2382582},
abstract = {We consider the characterization of muscle fatigue through a noninvasive sensing mechanism such as Surface ElectroMyoGraphy (SEMG). While changes in the properties of SEMG signals with respect to muscle fatigue have been reported in the literature, the large variation in these signals across different individuals makes the task of modeling and classification of SEMG signals challenging. Indeed, the variation in SEMG parameters from subject to subject creates differences in the data distribution. In this article, we propose two transfer learning frameworks based on the multisource domain adaptation methodology for detecting different stages of fatigue using SEMG signals, that addresses the distribution differences. In the proposed frameworks, the SEMG data of a subject represent a domain; data from multiple subjects in the training set form the multiple source domains and the test subject data form the target domain. SEMG signals are predominantly different in conditional probability distribution across subjects. The key feature of the first framework is a novel weighting scheme that addresses the conditional probability distribution differences across multiple domains (subjects) and the key feature of the second framework is a two-stage domain adaptation methodology which combines weighted data from multiple sources based on marginal probability differences (first stage) as well as conditional probability differences (second stage), with the target domain data. The weights for minimizing the marginal probability differences are estimated independently, while the weights for minimizing conditional probability differences are computed simultaneously by exploiting the potential interaction among multiple sources. We also provide a theoretical analysis on the generalization performance of the proposed multisource domain adaptation formulation using the weighted Rademacher complexity measure. We have validated the proposed frameworks on Surface ElectroMyoGram signals collected from 8 people during a fatigue-causing repetitive gripping activity. Comprehensive experiments on the SEMG dataset demonstrate that the proposed method improves the classification accuracy by 20% to 30% over the cases without any domain adaptation method and by 13% to 30% over existing state-of-the-art domain adaptation methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {18},
numpages = {26},
keywords = {transfer learning, surface electromyogram, subject-based variability, Multisource domain adaption}
}

@article{10.1145/2382577.2382580,
author = {Mampaey, Michael and Vreeken, Jilles and Tatti, Nikolaj},
title = {Summarizing Data Succinctly with the Most Informative Itemsets},
year = {2012},
issue_date = {December 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2382577.2382580},
doi = {10.1145/2382577.2382580},
abstract = {Knowledge discovery from data is an inherently iterative process. That is, what we know about the data greatly determines our expectations, and therefore, what results we would find interesting and/or surprising. Given new knowledge about the data, our expectations will change. Hence, in order to avoid redundant results, knowledge discovery algorithms ideally should follow such an iterative updating procedure.With this in mind, we introduce a well-founded approach for succinctly summarizing data with the most informative itemsets; using a probabilistic maximum entropy model, we iteratively find the itemset that provides us the most novel information—that is, for which the frequency in the data surprises us the most—and in turn we update our model accordingly. As we use the maximum entropy principle to obtain unbiased probabilistic models, and only include those itemsets that are most informative with regard to the current model, the summaries we construct are guaranteed to be both descriptive and nonredundant.The algorithm that we present, called mtv, can either discover the top-k most informative itemsets, or we can employ either the Bayesian Information Criterion (bic) or the Minimum Description Length (mdl) principle to automatically identify the set of itemsets that together summarize the data well. In other words, our method will “tell you what you need to know” about the data. Importantly, it is a one-phase algorithm: rather than picking itemsets from a user-provided candidate set, itemsets and their supports are mined on-the-fly. To further its applicability, we provide an efficient method to compute the maximum entropy distribution using Quick Inclusion-Exclusion.Experiments on our method, using synthetic, benchmark, and real data, show that the discovered summaries are succinct, and correctly identify the key patterns in the data. The models they form attain high likelihoods, and inspection shows that they summarize the data well with increasingly specific, yet nonredundant itemsets.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {16},
numpages = {42},
keywords = {summarization, minimum description length principle, maximum entropy, pattern sets, MDL, inclusion-exclusion, BIC, Frequent itemsets}
}

@article{10.1145/2382577.2382579,
author = {Kaufman, Shachar and Rosset, Saharon and Perlich, Claudia and Stitelman, Ori},
title = {Leakage in Data Mining: Formulation, Detection, and Avoidance},
year = {2012},
issue_date = {December 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2382577.2382579},
doi = {10.1145/2382577.2382579},
abstract = {Deemed “one of the top ten data mining mistakes”, leakage is the introduction of information about the data mining target that should not be legitimately available to mine from. In addition to our own industry experience with real-life projects, controversies around several major public data mining competitions held recently such as the INFORMS 2010 Data Mining Challenge and the IJCNN 2011 Social Network Challenge are evidence that this issue is as relevant today as it has ever been. While acknowledging the importance and prevalence of leakage in both synthetic competitions and real-life data mining projects, existing literature has largely left this idea unexplored. What little has been said turns out not to be broad enough to cover more complex cases of leakage, such as those where the classical independently and identically distributed (i.i.d.) assumption is violated, that have been recently documented. In our new approach, these cases and others are explained by explicitly defining modeling goals and analyzing the broader framework of the data mining problem. The resulting definition enables us to derive general methodology for dealing with the issue. We show that it is possible to avoid leakage with a simple specific approach to data management followed by what we call a learn-predict separation, and present several ways of detecting leakage when the modeler has no control over how the data have been collected. We also offer an alternative point of view on leakage that is based on causal graph modeling concepts.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {15},
numpages = {21},
keywords = {predictive modeling, leakage, Data mining}
}

@article{10.1145/2382577.2382581,
author = {Chu, Shumo and Cheng, James},
title = {Triangle Listing in Massive Networks},
year = {2012},
issue_date = {December 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2382577.2382581},
doi = {10.1145/2382577.2382581},
abstract = {Triangle listing is one of the fundamental algorithmic problems whose solution has numerous applications especially in the analysis of complex networks, such as the computation of clustering coefficients, transitivity, triangular connectivity, trusses, etc. Existing algorithms for triangle listing are mainly in-memory algorithms, whose performance cannot scale with the massive volume of today's fast growing networks. When the input graph cannot fit in main memory, triangle listing requires random disk accesses that can incur prohibitively huge I/O cost. Some streaming, semistreaming, and sampling algorithms have been proposed but these are approximation algorithms. We propose an I/O-efficient algorithm for triangle listing. Our algorithm is exact and avoids random disk access. Our results show that our algorithm is scalable and outperforms the state-of-the-art in-memory and local triangle estimation algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {17},
numpages = {32},
keywords = {massive networks, clustering coefficients, triangle counting, large graphs, Triangle listing}
}

@article{10.1145/2362383.2362387,
author = {Vaz de Melo, Pedro O. S. and Almeida, Virgilio A. F. and Loureiro, Antonio A. F. and Faloutsos, Christos},
title = {Forecasting in the NBA and Other Team Sports: Network Effects in Action},
year = {2012},
issue_date = {October 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2362383.2362387},
doi = {10.1145/2362383.2362387},
abstract = {The multi-million sports-betting market is based on the fact that the task of predicting the outcome of a sports event is very hard. Even with the aid of an uncountable number of descriptive statistics and background information, only a few can correctly guess the outcome of a game or a league. In this work, our approach is to move away from the traditional way of predicting sports events, and instead to model sports leagues as networks of players and teams where the only information available is the work relationships among them. We propose two network-based models to predict the behavior of teams in sports leagues. These models are parameter-free, that is, they do not have a single parameter, and moreover are sport-agnostic: they can be applied directly to any team sports league. First, we view a sports league as a network in evolution, and we infer the implicit feedback behind network changes and properties over the years. Then, we use this knowledge to construct the network-based prediction models, which can, with a significantly high probability, indicate how well a team will perform over a season. We compare our proposed models with other prediction models in two of the most popular sports leagues: the National Basketball Association (NBA) and the Major League Baseball (MLB). Our model shows consistently good results in comparison with the other models and, relying upon the network properties of the teams, we achieved a ≈ 14% rank prediction accuracy improvement over our best competitor.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {13},
numpages = {27},
keywords = {Complex networks, sports analytics, social networks}
}

@article{10.1145/2362383.2362386,
author = {Wang, Dingding and Zhu, Shenghuo and Li, Tao and Gong, Yihong},
title = {Comparative Document Summarization via Discriminative Sentence Selection},
year = {2012},
issue_date = {October 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2362383.2362386},
doi = {10.1145/2362383.2362386},
abstract = {Given a collection of document groups, a natural question is to identify the differences among them. Although traditional document summarization techniques can summarize the content of the document groups one by one, there exists a great necessity to generate a summary of the differences among the document groups. In this article, we study a novel problem, that of summarizing the differences between document groups. A discriminative sentence selection method is proposed to extract the most discriminative sentences which represent the specific characteristics of each document group. Experiments and case studies on real-world data sets demonstrate the effectiveness of our proposed method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {12},
numpages = {18},
keywords = {Comparative document summarization, discriminative sentence selection}
}

@article{10.1145/2362383.2362385,
author = {Chan, Jeffrey and Bailey, James and Leckie, Christopher and Houle, Michael},
title = {CiForager: Incrementally Discovering Regions of Correlated Change in Evolving Graphs},
year = {2012},
issue_date = {October 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2362383.2362385},
doi = {10.1145/2362383.2362385},
abstract = {Data mining techniques for understanding how graphs evolve over time have become increasingly important. Evolving graphs arise naturally in diverse applications such as computer network topologies, multiplayer games and medical imaging. A natural and interesting problem in evolving graph analysis is the discovery of compact subgraphs that change in a similar manner. Such subgraphs are known as regions of correlated change and they can both summarise change patterns in graphs and help identify the underlying events causing these changes. However, previous techniques for discovering regions of correlated change suffer from limited scalability, making them unsuitable for analysing the evolution of very large graphs. In this paper, we introduce a new algorithm called ciForager, that addresses this scalability challenge and offers considerable improvements. The efficiency of ciForager is based on the use of new incremental techniques for detecting change, as well as the use of Voronoi representations for efficiently determining distance. We experimentally show that ciForager can achieve speedups of up to 1000 times over previous approaches. As a result, it becomes feasible for the first time to discover regions of correlated change in extremely large graphs, such as the entire BGP routing topology of the Internet.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {11},
numpages = {50},
keywords = {shortest path distance, connected components, Dynamic graph mining, fault detection, correlated change}
}

@article{10.1145/2362383.2362384,
author = {Wang, Zhenxing and Chan, Laiwan},
title = {Learning Bayesian Networks from Markov Random Fields: An Efficient Algorithm for Linear Models},
year = {2012},
issue_date = {October 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/2362383.2362384},
doi = {10.1145/2362383.2362384},
abstract = {Dependency analysis is a typical approach for Bayesian network learning, which infers the structures of Bayesian networks by the results of a series of conditional independence (CI) tests. In practice, testing independence conditioning on large sets hampers the performance of dependency analysis algorithms in terms of accuracy and running time for the following reasons. First, testing independence on large sets of variables with limited samples is not stable. Second, for most dependency analysis algorithms, the number of CI tests grows at an exponential rate with the sizes of conditioning sets, and the running time grows of the same rate. Therefore, determining how to reduce the number of CI tests and the sizes of conditioning sets becomes a critical step in dependency analysis algorithms. In this article, we address a two-phase algorithm based on the observation that the structures of Markov random fields are similar to those of Bayesian networks. The first phase of the algorithm constructs a Markov random field from data, which provides a close approximation to the structure of the true Bayesian network; the second phase of the algorithm removes redundant edges according to CI tests to get the true Bayesian network. Both phases use Markov blanket information to reduce the sizes of conditioning sets and the number of CI tests without sacrificing accuracy. An empirical study shows that the two-phase algorithm performs well in terms of accuracy and efficiency.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {10},
numpages = {31},
keywords = {Bayesian networks, causal modeling, graphical models}
}

@article{10.1145/2297456.2297458,
author = {Das, Sanmay and Magdon-Ismail, Malik},
title = {A Model for Information Growth in Collective Wisdom Processes},
year = {2012},
issue_date = {July 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2297456.2297458},
doi = {10.1145/2297456.2297458},
abstract = {Collaborative media such as wikis have become enormously successful venues for information creation. Articles accrue information through the asynchronous editing of users who arrive both seeking information and possibly able to contribute information. Most articles stabilize to high-quality, trusted sources of information representing the collective wisdom of all the users who edited the article. We propose a model for information growth which relies on two main observations: (i) as an article’s quality improves, it attracts visitors at a faster rate (a rich-get-richer phenomenon); and, simultaneously, (ii) the chances that a new visitor will improve the article drops (there is only so much that can be said about a particular topic). Our model is able to reproduce many features of the edit dynamics observed on Wikipedia; in particular, it captures the observed rise in the edit rate, followed by 1/t decay. Despite differences in the media, we also document similar features in the comment rates for a segment of the LiveJournal blogosphere.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {6},
numpages = {10},
keywords = {dynamical systems, social networks, Collective intelligence}
}

@article{10.1145/2297456.2297461,
author = {Bhattacharya, Indrajit and Godbole, Shantanu and Joshi, Sachindra and Verma, Ashish},
title = {Cross-Guided Clustering: Transfer of Relevant Supervision across Tasks},
year = {2012},
issue_date = {July 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2297456.2297461},
doi = {10.1145/2297456.2297461},
abstract = {Lack of supervision in clustering algorithms often leads to clusters that are not useful or interesting to human reviewers. We investigate if supervision can be automatically transferred for clustering a target task, by providing a relevant supervised partitioning of a dataset from a different source task. The target clustering is made more meaningful for the human user by trading-off intrinsic clustering goodness on the target task for alignment with relevant supervised partitions in the source task, wherever possible. We propose a cross-guided clustering algorithm that builds on traditional k-means by aligning the target clusters with source partitions. The alignment process makes use of a cross-task similarity measure that discovers hidden relationships across tasks. When the source and target tasks correspond to different domains with potentially different vocabularies, we propose a projection approach using pivot vocabularies for the cross-domain similarity measure. Using multiple real-world and synthetic datasets, we show that our approach improves clustering accuracy significantly over traditional k-means and state-of-the-art semi-supervised clustering baselines, over a wide range of data characteristics and parameter settings.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {9},
numpages = {28},
keywords = {cluster alignment, transfer, Multitask}
}

@article{10.1145/2297456.2297457,
author = {Mavroeidis, Dimitrios and Magdalinos, Panagis},
title = {A Sequential Sampling Framework for Spectral K-Means Based on Efficient Bootstrap Accuracy Estimations: Application to Distributed Clustering},
year = {2012},
issue_date = {July 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2297456.2297457},
doi = {10.1145/2297456.2297457},
abstract = {The scalability of learning algorithms has always been a central concern for data mining researchers, and nowadays, with the rapid increase in data storage capacities and availability, its importance has increased. To this end, sampling has been studied by several researchers in an effort to derive sufficiently accurate models using only small data fractions. In this article we focus on spectral k-means, that is, the k-means approximation as derived by the spectral relaxation, and propose a sequential sampling framework that iteratively enlarges the sample size until the k-means results (objective function and cluster structure) become indistinguishable from the asymptotic (infinite-data) output. In the proposed framework we adopt a commonly applied principle in data mining research that considers the use of minimal assumptions concerning the data generating distribution. This restriction imposes several challenges, mainly related to the efficiency of the sequential sampling procedure. These challenges are addressed using elements of matrix perturbation theory and statistics. Moreover, although the main focus is on spectral k-means, we also demonstrate that the proposed framework can be generalized to handle spectral clustering.The proposed sequential sampling framework is consecutively employed for addressing the distributed clustering problem, where the task is to construct a global model for data that resides in distributed network nodes. The main challenge in this context is related to the bandwidth constraints that are commonly imposed, thus requiring that the distributed clustering algorithm consumes a minimal amount of network load. This illustrates the applicability of the proposed approach, as it enables the determination of a minimal sample size that can be used for constructing an accurate clustering model that entails the distributional characteristics of the data. As opposed to the relevant distributed k-means approaches, our framework takes into account the fact that the choice of the number of clusters has a crucial effect on the required amount of communication. More precisely, the proposed algorithm is able to derive a statistical estimation of the required relative sizes for all possible values of k. This unique feature of our distributed clustering framework enables a network administrator to choose an economic solution that identifies the crude cluster structure of a dataset and not devote excessive network resources for identifying all the “correct” detailed clusters.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {5},
numpages = {37},
keywords = {distributed clustering, bootstrapping, matrix perturbation theory, clustering, Asymptotic convergence, sampling, spectral}
}

@article{10.1145/2297456.2297459,
author = {Xu, Tianbing and Zhang, Zhongfei and Yu, Philip S. and Long, Bo},
title = {Generative Models for Evolutionary Clustering},
year = {2012},
issue_date = {July 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2297456.2297459},
doi = {10.1145/2297456.2297459},
abstract = {This article studies evolutionary clustering, a recently emerged hot topic with many important applications, noticeably in dynamic social network analysis. In this article, based on the recent literature on nonparametric Bayesian models, we have developed two generative models: DPChain and HDP-HTM. DPChain is derived from the Dirichlet process mixture (DPM) model, with an exponential decaying component along with the time. HDP-HTM combines the hierarchical dirichlet process (HDP) with a hierarchical transition matrix (HTM) based on the proposed Infinite hierarchical Markov state model (iHMS). Both models substantially advance the literature on evolutionary clustering, in the sense that not only do they both perform better than those in the existing literature, but more importantly, they are capable of automatically learning the cluster numbers and explicitly addressing the corresponding issues. Extensive evaluations have demonstrated the effectiveness and the promise of these two solutions compared to the state-of-the-art literature.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {7},
numpages = {27},
keywords = {Evolutionary clustering, hierarchical transition matrix, DPChain, HDP-HTM, iHMS}
}

@article{10.1145/2297456.2297460,
author = {Wang, Shaojun and Schuurmans, Dale and Zhao, Yunxin},
title = {The Latent Maximum Entropy Principle},
year = {2012},
issue_date = {July 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/2297456.2297460},
doi = {10.1145/2297456.2297460},
abstract = {We present an extension to Jaynes’ maximum entropy principle that incorporates latent variables. The principle of latent maximum entropy we propose is different from both Jaynes’ maximum entropy principle and maximum likelihood estimation, but can yield better estimates in the presence of hidden variables and limited training data. We first show that solving for a latent maximum entropy model poses a hard nonlinear constrained optimization problem in general. However, we then show that feasible solutions to this problem can be obtained efficiently for the special case of log-linear models---which forms the basis for an efficient approximation to the latent maximum entropy principle. We derive an algorithm that combines expectation-maximization with iterative scaling to produce feasible log-linear solutions. This algorithm can be interpreted as an alternating minimization algorithm in the information divergence, and reveals an intimate connection between the latent maximum entropy and maximum likelihood principles. To select a final model, we generate a series of feasible candidates, calculate the entropy of each, and choose the model that attains the highest entropy. Our experimental results show that estimation based on the latent maximum entropy principle generally gives better results than maximum likelihood when estimating latent variable models on small observed data samples.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {8},
numpages = {42},
keywords = {expectation maximization, Maximum entropy, latent variable models, iterative scaling, information geometry}
}

@article{10.1145/2133360.2133362,
author = {Li, Chun and Yang, Qingyan and Wang, Jianyong and Li, Ming},
title = {Efficient Mining of Gap-Constrained Subsequences and Its Various Applications},
year = {2012},
issue_date = {March 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2133360.2133362},
doi = {10.1145/2133360.2133362},
abstract = {Mining frequent subsequence patterns is a typical data-mining problem and various efficient sequential pattern mining algorithms have been proposed. In many application domains (e.g., biology), the frequent subsequences confined by the predefined gap requirements are more meaningful than the general sequential patterns. In this article, we propose two algorithms, Gap-BIDE for mining closed gap-constrained subsequences from a set of input sequences, and Gap-Connect for mining repetitive gap-constrained subsequences from a single input sequence. Inspired by some state-of-the-art closed or constrained sequential pattern mining algorithms, the Gap-BIDE algorithm adopts an efficient approach to finding the complete set of closed sequential patterns with gap constraints, while the Gap-Connect algorithm efficiently mines an approximate set of long patterns by connecting short patterns. We also present several methods for feature selection from the set of gap-constrained patterns for the purpose of classification and clustering. Our extensive performance study shows that our approaches are very efficient in mining frequent subsequences with gap constraints, and the gap-constrained pattern based classification/clustering approaches can achieve high-quality results.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {2},
numpages = {39},
keywords = {Sequential pattern, repetitive subsequence, closed subsequence, gap-constraint}
}

@article{10.1145/2133360.2133363,
author = {Liu, Fei Tony and Ting, Kai Ming and Zhou, Zhi-Hua},
title = {Isolation-Based Anomaly Detection},
year = {2012},
issue_date = {March 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2133360.2133363},
doi = {10.1145/2133360.2133363},
abstract = {Anomalies are data points that are few and different. As a result of these properties, we show that, anomalies are susceptible to a mechanism called isolation. This article proposes a method called Isolation Forest (iForest), which detects anomalies purely based on the concept of isolation without employing any distance or density measure---fundamentally different from all existing methods.As a result, iForest is able to exploit subsampling (i) to achieve a low linear time-complexity and a small memory-requirement and (ii) to deal with the effects of swamping and masking effectively. Our empirical evaluation shows that iForest outperforms ORCA, one-class SVM, LOF and Random Forests in terms of AUC, processing time, and it is robust against masking and swamping effects. iForest also works well in high dimensional problems containing a large number of irrelevant attributes, and when anomalies are not available in training sample.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {3},
numpages = {39},
keywords = {isolation forest, ensemble methods, outlier detection, isolation, Anomaly detection, random tree ensemble, binary tree}
}

@article{10.1145/2133360.2133364,
author = {Jin, Yu and Duffield, Nick and Erman, Jeffrey and Haffner, Patrick and Sen, Subhabrata and Zhang, Zhi-Li},
title = {A Modular Machine Learning System for Flow-Level Traffic Classification in Large Networks},
year = {2012},
issue_date = {March 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2133360.2133364},
doi = {10.1145/2133360.2133364},
abstract = {The ability to accurately and scalably classify network traffic is of critical importance to a wide range of management tasks of large networks, such as tier-1 ISP networks and global enterprise networks. Guided by the practical constraints and requirements of traffic classification in large networks, in this article, we explore the design of an accurate and scalable machine learning based flow-level traffic classification system, which is trained on a dataset of flow-level data that has been annotated with application protocol labels by a packet-level classifier. Our system employs a lightweight modular architecture, which combines a series of simple linear binary classifiers, each of which can be efficiently implemented and trained on vast amounts of flow data in parallel, and embraces three key innovative mechanisms, weighted threshold sampling, logistic calibration, and intelligent data partitioning, to achieve scalability while attaining high accuracy. Evaluations using real traffic data from multiple locations in a large ISP show that our system accurately reproduces the labels of the packet level classifier when runs on (unlabeled) flow records, while meeting the scalability and stability requirements of large ISP networks. Using training and test datasets that are two months apart and collected from two different locations, the flow error rates are only 3% for TCP flows and 0.4% for UDP flows. We further show that such error rates can be reduced by combining the information of spatial distributions of flows, or collective traffic statistics, during classification. We propose a novel two-step model, which seamlessly integrates these collective traffic statistics into the existing traffic classification system. Experimental results display performance improvement on all traffic classes and an overall error rate reduction by 15%. In addition to a high accuracy, at runtime, our implementation easily scales to classify traffic on 10Gbps links.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {4},
numpages = {34},
keywords = {Communications network, traffic classification, machine learning}
}

@article{10.1145/2133360.2133361,
author = {Ienco, Dino and Pensa, Ruggero G. and Meo, Rosa},
title = {From Context to Distance: Learning Dissimilarity for Categorical Data Clustering},
year = {2012},
issue_date = {March 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/2133360.2133361},
doi = {10.1145/2133360.2133361},
abstract = {Clustering data described by categorical attributes is a challenging task in data mining applications. Unlike numerical attributes, it is difficult to define a distance between pairs of values of a categorical attribute, since the values are not ordered. In this article, we propose a framework to learn a context-based distance for categorical attributes. The key intuition of this work is that the distance between two values of a categorical attribute Ai can be determined by the way in which the values of the other attributes Aj are distributed in the dataset objects: if they are similarly distributed in the groups of objects in correspondence of the distinct values of Ai a low value of distance is obtained. We propose also a solution to the critical point of the choice of the attributes Aj. We validate our approach by embedding our distance learning framework in a hierarchical clustering algorithm. We applied it on various real world and synthetic datasets, both low and high-dimensional. Experimental results show that our method is competitive with respect to the state of the art of categorical data clustering approaches. We also show that our approach is scalable and has a low impact on the overall computational time of a clustering task.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {1},
numpages = {25},
keywords = {distance learning, clustering, Categorical data}
}

@article{10.1145/2086737.2086738,
author = {Elkan, Charles and Koren, Yehuda},
title = {Guest Editorial for Special Issue KDD’10},
year = {2012},
issue_date = {February 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2086737.2086738},
doi = {10.1145/2086737.2086738},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {18},
numpages = {2}
}

@article{10.1145/2086737.2086744,
author = {Shahaf, Dafna and Guestrin, Carlos},
title = {Connecting Two (or Less) Dots: Discovering Structure in News Articles},
year = {2012},
issue_date = {February 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2086737.2086744},
doi = {10.1145/2086737.2086744},
abstract = {Finding information is becoming a major part of our daily life. Entire sectors, from Web users to scientists and intelligence analysts, are increasingly struggling to keep up with the larger and larger amounts of content published every day. With this much data, it is often easy to miss the big picture.In this article, we investigate methods for automatically connecting the dots---providing a structured, easy way to navigate within a new topic and discover hidden connections. We focus on the news domain: given two news articles, our system automatically finds a coherent chain linking them together. For example, it can recover the chain of events starting with the decline of home prices (January 2007), and ending with the health care debate (2009).We formalize the characteristics of a good chain and provide a fast search-driven algorithm to connect two fixed endpoints. We incorporate user feedback into our framework, allowing the stories to be refined and personalized. We also provide a method to handle partially-specified endpoints, for users who do not know both ends of a story. Finally, we evaluate our algorithm over real news data. Our user studies demonstrate that the objective we propose captures the users’ intuitive notion of coherence, and that our algorithm effectively helps users understand the news.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {24},
numpages = {31},
keywords = {Coherence}
}

@article{10.1145/2086737.2086741,
author = {Gomez-Rodriguez, Manuel and Leskovec, Jure and Krause, Andreas},
title = {Inferring Networks of Diffusion and Influence},
year = {2012},
issue_date = {February 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2086737.2086741},
doi = {10.1145/2086737.2086741},
abstract = {Information diffusion and virus propagation are fundamental processes taking place in networks. While it is often possible to directly observe when nodes become infected with a virus or publish the information, observing individual transmissions (who infects whom, or who influences whom) is typically very difficult. Furthermore, in many applications, the underlying network over which the diffusions and propagations spread is actually unobserved. We tackle these challenges by developing a method for tracing paths of diffusion and influence through networks and inferring the networks over which contagions propagate. Given the times when nodes adopt pieces of information or become infected, we identify the optimal network that best explains the observed infection times. Since the optimization problem is NP-hard to solve exactly, we develop an efficient approximation algorithm that scales to large datasets and finds provably near-optimal networks.We demonstrate the effectiveness of our approach by tracing information diffusion in a set of 170 million blogs and news articles over a one year period to infer how information flows through the online media space. We find that the diffusion network of news for the top 1,000 media sites and blogs tends to have a core-periphery structure with a small set of core media sites that diffuse information to the rest of the Web. These sites tend to have stable circles of influence with more general news media sites acting as connectors between them.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {21},
numpages = {37},
keywords = {social networks, blogs, information cascades, news media, meme-tracking, Networks of diffusion}
}

@article{10.1145/2086737.2086739,
author = {Iwata, Tomoharu and Yamada, Takeshi and Sakurai, Yasushi and Ueda, Naonori},
title = {Sequential Modeling of Topic Dynamics with Multiple Timescales},
year = {2012},
issue_date = {February 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2086737.2086739},
doi = {10.1145/2086737.2086739},
abstract = {We propose an online topic model for sequentially analyzing the time evolution of topics in document collections. Topics naturally evolve with multiple timescales. For example, some words may be used consistently over one hundred years, while other words emerge and disappear over periods of a few days. Thus, in the proposed model, current topic-specific distributions over words are assumed to be generated based on the multiscale word distributions of the previous epoch. Considering both the long- and short-timescale dependency yields a more robust model. We derive efficient online inference procedures based on a stochastic EM algorithm, in which the model is sequentially updated using newly obtained data; this means that past data are not required to make the inference. We demonstrate the effectiveness of the proposed method in terms of predictive performance and computational efficiency by examining collections of real documents with timestamps.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {19},
numpages = {27},
keywords = {multiscale, online learning, Topic model, time-series analysis}
}

@article{10.1145/2086737.2086743,
author = {Yu, Hsiang-Fu and Hsieh, Cho-Jui and Chang, Kai-Wei and Lin, Chih-Jen},
title = {Large Linear Classification When Data Cannot Fit in Memory},
year = {2012},
issue_date = {February 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2086737.2086743},
doi = {10.1145/2086737.2086743},
abstract = {Recent advances in linear classification have shown that for applications such as document classification, the training process can be extremely efficient. However, most of the existing training methods are designed by assuming that data can be stored in the computer memory. These methods cannot be easily applied to data larger than the memory capacity due to the random access to the disk. We propose and analyze a block minimization framework for data larger than the memory size. At each step a block of data is loaded from the disk and handled by certain learning methods. We investigate two implementations of the proposed framework for primal and dual SVMs, respectively. Because data cannot fit in memory, many design considerations are very different from those for traditional algorithms. We discuss and compare with existing approaches that are able to handle data larger than memory. Experiments using data sets 20 times larger than the memory demonstrate the effectiveness of the proposed method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {23},
numpages = {23},
keywords = {linear classification, large-scale learning, support vector machines, Block minimization methods}
}

@article{10.1145/2086737.2086742,
author = {Chen, Jianhui and Liu, Ji and Ye, Jieping},
title = {Learning Incoherent Sparse and Low-Rank Patterns from Multiple Tasks},
year = {2012},
issue_date = {February 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2086737.2086742},
doi = {10.1145/2086737.2086742},
abstract = {We consider the problem of learning incoherent sparse and low-rank patterns from multiple tasks. Our approach is based on a linear multitask learning formulation, in which the sparse and low-rank patterns are induced by a cardinality regularization term and a low-rank constraint, respectively. This formulation is nonconvex; we convert it into its convex surrogate, which can be routinely solved via semidefinite programming for small-size problems. We propose employing the general projected gradient scheme to efficiently solve such a convex surrogate; however, in the optimization formulation, the objective function is nondifferentiable and the feasible domain is nontrivial. We present the procedures for computing the projected gradient and ensuring the global convergence of the projected gradient scheme. The computation of the projected gradient involves a constrained optimization problem; we show that the optimal solution to such a problem can be obtained via solving an unconstrained optimization subproblem and a Euclidean projection subproblem. We also present two projected gradient algorithms and analyze their rates of convergence in detail. In addition, we illustrate the use of the presented projected gradient algorithms for the proposed multitask learning formulation using the least squares loss. Experimental results on a collection of real-world data sets demonstrate the effectiveness of the proposed multitask learning formulation and the efficiency of the proposed projected gradient algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {22},
numpages = {31},
keywords = {trace norm, low-rank and sparse patterns, Multitask learning}
}

@article{10.1145/2086737.2086740,
author = {Huh, Seungil and Fienberg, Stephen E.},
title = {Discriminative Topic Modeling Based on Manifold Learning},
year = {2012},
issue_date = {February 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/2086737.2086740},
doi = {10.1145/2086737.2086740},
abstract = {Topic modeling has become a popular method used for data analysis in various domains including text documents. Previous topic model approaches, such as probabilistic Latent Semantic Analysis (pLSA) and Latent Dirichlet Allocation (LDA), have shown impressive success in discovering low-rank hidden structures for modeling text documents. These approaches, however do not take into account the manifold structure of the data, which is generally informative for nonlinear dimensionality reduction mapping. More recent topic model approaches, Laplacian PLSI (LapPLSI) and Locally-consistent Topic Model (LTM), have incorporated the local manifold structure into topic models and have shown resulting benefits. But they fall short of achieving full discriminating power of manifold learning as they only enhance the proximity between the low-rank representations of neighboring pairs without any consideration for non-neighboring pairs. In this article, we propose a new approach, Discriminative Topic Model (DTM), which separates non-neighboring pairs from each other in addition to bringing neighboring pairs closer together, thereby preserving the global manifold structure as well as improving local consistency. We also present a novel model-fitting algorithm based on the generalized EM algorithm and the concept of Pareto improvement. We empirically demonstrate the success of DTM in terms of unsupervised clustering and semisupervised classification accuracies on text corpora and robustness to parameters compared to state-of-the-art techniques.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {20},
numpages = {25},
keywords = {dimensionality reduction, document clustering and classification, Topic modeling, semisupervised learning}
}

@article{10.1145/1993077.1993079,
author = {Maier, Marc and Rattigan, Matthew and Jensen, David},
title = {Indexing Network Structure with Shortest-Path Trees},
year = {2011},
issue_date = {August 2011},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1993077.1993079},
doi = {10.1145/1993077.1993079},
abstract = {The ability to discover low-cost paths in networks has practical consequences for knowledge discovery and social network analysis tasks. Many analytic techniques for networks require finding low-cost paths, but exact methods for search become prohibitive for large networks, and data sets are steadily increasing in size. Short paths can be found efficiently by utilizing an index of network structure, which estimates network distances and enables rapid discovery of short paths. Through experiments on synthetic networks, we demonstrate that one such novel network structure index based on the shortest-path tree outperforms other previously proposed indices. We also show that it generalizes across arbitrarily weighted networks of various structures and densities, provides accurate estimates of distance, and has efficient time and space complexity. We present results on real data sets for several applications, including navigation, diameter estimation, centrality computation, and clustering---all made efficient by virtue of the network structure index.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {15},
numpages = {25},
keywords = {social network analysis, weighted networks, network structure index, Knowledge discovery in graphs}
}

@article{10.1145/1993077.1993078,
author = {Wang, Dingding and Zhu, Shenghuo and Li, Tao and Chi, Yun and Gong, Yihong},
title = {Integrating Document Clustering and Multidocument Summarization},
year = {2011},
issue_date = {August 2011},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1993077.1993078},
doi = {10.1145/1993077.1993078},
abstract = {Document understanding techniques such as document clustering and multidocument summarization have been receiving much attention recently. Current document clustering methods usually represent the given collection of documents as a document-term matrix and then conduct the clustering process. Although many of these clustering methods can group the documents effectively, it is still hard for people to capture the meaning of the documents since there is no satisfactory interpretation for each document cluster. A straightforward solution is to first cluster the documents and then summarize each document cluster using summarization methods. However, most of the current summarization methods are solely based on the sentence-term matrix and ignore the context dependence of the sentences. As a result, the generated summaries lack guidance from the document clusters. In this article, we propose a new language model to simultaneously cluster and summarize documents by making use of both the document-term and sentence-term matrices. By utilizing the mutual influence of document clustering and summarization, our method makes; (1) a better document clustering method with more meaningful interpretation; and (2) an effective document summarization method with guidance from document clustering. Experimental results on various document datasets show the effectiveness of our proposed method and the high interpretability of the generated summaries.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {14},
numpages = {26},
keywords = {nonnegative matrix factorization with given bases, multidocument summarization, Document clustering}
}

@article{10.1145/1993077.1993080,
author = {Wong, Raymond Chi-Wing and Fu, Ada Wai-Chee and Wang, Ke and Yu, Philip S. and Pei, Jian},
title = {Can the Utility of Anonymized Data Be Used for Privacy Breaches?},
year = {2011},
issue_date = {August 2011},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1993077.1993080},
doi = {10.1145/1993077.1993080},
abstract = {Group based anonymization is the most widely studied approach for privacy-preserving data publishing. Privacy models/definitions using group based anonymization includes k-anonymity, l-diversity, and t-closeness, to name a few. The goal of this article is to raise a fundamental issue regarding the privacy exposure of the approaches using group based anonymization. This has been overlooked in the past. The group based anonymization approach by bucketization basically hides each individual record behind a group to preserve data privacy. If not properly anonymized, patterns can actually be derived from the published data and be used by an adversary to breach individual privacy. For example, from the medical records released, if patterns such as that people from certain countries rarely suffer from some disease can be derived, then the information can be used to imply linkage of other people in an anonymized group with this disease with higher likelihood. We call the derived patterns from the published data the foreground knowledge. This is in contrast to the background knowledge that the adversary may obtain from other channels, as studied in some previous work. Finally, our experimental results show such an attack is realistic in the privacy benchmark dataset under the traditional group based anonymization approach.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {16},
numpages = {24},
keywords = {data publishing, k-anonymity, Privacy preservation, l-diversity}
}

@article{10.1145/1993077.1993081,
author = {Lin, Yu-Ru and Sun, Jimeng and Sundaram, Hari and Kelliher, Aisling and Castro, Paul and Konuru, Ravi},
title = {Community Discovery via Metagraph Factorization},
year = {2011},
issue_date = {August 2011},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1993077.1993081},
doi = {10.1145/1993077.1993081},
abstract = {This work aims at discovering community structure in rich media social networks through analysis of time-varying, multirelational data. Community structure represents the latent social context of user actions. It has important applications such as search and recommendation. The problem is particularly useful in the enterprise domain, where extracting emergent community structure on enterprise social media can help in forming new collaborative teams, in expertise discovery, and in the long term reorganization of enterprises based on collaboration patterns. There are several unique challenges: (a) In social media, the context of user actions is constantly changing and coevolving; hence the social context contains time-evolving multidimensional relations. (b) The social context is determined by the available system features and is unique in each social media platform; hence the analysis of such data needs to flexibly incorporate various system features. In this article we propose MetaFac (MetaGraph Factorization), a framework that extracts community structures from dynamic, multidimensional social contexts and interactions. Our work has three key contributions: (1) metagraph, a novel relational hypergraph representation for modeling multirelational and multidimensional social data; (2) an efficient multirelational factorization method for community extraction on a given metagraph; (3) an online method to handle time-varying relations through incremental metagraph factorization. Extensive experiments on real-world social data collected from an enterprise and the public Digg social media Web site suggest that our technique is scalable and is able to extract meaningful communities from social media contexts. We illustrate the usefulness of our framework through two prediction tasks: (1) in the enterprise dataset, the task is to predict users’ future interests on tag usage, and (2) in the Digg dataset, the task is to predict users’ future interests in voting and commenting on Digg stories. Our prediction significantly outperforms baseline methods (including aspect model and tensor analysis), indicating the promising direction of using metagraphs for handling time-varying social relational contexts.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
articleno = {17},
numpages = {44},
keywords = {dynamic social network analysis, community discovery, MetaFac, relational hypergraph, nonnegative tensor factorization, metagraph factorization}
}

@article{10.1145/1921632.1921636,
author = {Dunlavy, Daniel M. and Kolda, Tamara G. and Acar, Evrim},
title = {Temporal Link Prediction Using Matrix and Tensor Factorizations},
year = {2011},
issue_date = {February 2011},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1921632.1921636},
doi = {10.1145/1921632.1921636},
abstract = {The data in many disciplines such as social networks, Web analysis, etc. is link-based, and the link structure can be exploited for many different data mining tasks. In this article, we consider the problem of temporal link prediction: Given link data for times 1 through T, can we predict the links at time T + 1? If our data has underlying periodic structure, can we predict out even further in time, i.e., links at time T + 2, T + 3, etc.? In this article, we consider bipartite graphs that evolve over time and consider matrix- and tensor-based methods for predicting future links. We present a weight-based method for collapsing multiyear data into a single matrix. We show how the well-known Katz method for link prediction can be extended to bipartite graphs and, moreover, approximated in a scalable way using a truncated singular value decomposition. Using a CANDECOMP/PARAFAC tensor decomposition of the data, we illustrate the usefulness of exploiting the natural three-dimensional structure of temporal link data. Through several numerical experiments, we demonstrate that both matrix- and tensor-based techniques are effective for temporal link prediction despite the inherent difficulty of the problem. Additionally, we show that tensor-based techniques are particularly effective for temporal data with varying periodic patterns.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {10},
numpages = {27},
keywords = {tensor factorization, link prediction, CANDECOMP, PARAFAC, evolution, Link mining}
}

@article{10.1145/1921632.1921635,
author = {de Vries, Timothy and Ke, Hui and Chawla, Sanjay and Christen, Peter},
title = {Robust Record Linkage Blocking Using Suffix Arrays and Bloom Filters},
year = {2011},
issue_date = {February 2011},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1921632.1921635},
doi = {10.1145/1921632.1921635},
abstract = {Record linkage is an important data integration task that has many practical uses for matching, merging and duplicate removal in large and diverse databases. However, quadratic scalability for the brute force approach of comparing all possible pairs of records necessitates the design of appropriate indexing or blocking techniques. The aim of these techniques is to cheaply remove candidate record pairs that are unlikely to match. We design and evaluate an efficient and highly scalable blocking approach based on suffix arrays. Our suffix grouping technique exploits the ordering used by the index to merge similar blocks at marginal extra cost, resulting in a much higher accuracy while retaining the high scalability of the base suffix array method. Efficiently grouping similar suffixes is carried out with the use of a sliding window technique. We carry out an in-depth analysis of our method and show results from experiments using real and synthetic data, which highlight the importance of using efficient indexing and blocking in real-world applications where datasets contain millions of records. We extend our disk-based methods with the capability to utilise main memory based storage to construct Bloom filters, which we have found to cause significant speedup by reducing the number of costly database queries by up to 70% in real data. We give practical implementation details and show how Bloom filters can be easily applied to Suffix Array based indexing.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {9},
numpages = {27},
keywords = {Record linkage, suffix arrays, blocking}
}

@article{10.1145/1921632.1921633,
author = {Sun, Jimeng and Liu, Yan and Tang, Jie and Apte, Chid},
title = {Introduction to Special Issue on Large-Scale Data Mining},
year = {2011},
issue_date = {February 2011},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1921632.1921633},
doi = {10.1145/1921632.1921633},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {7},
numpages = {1}
}

@article{10.1145/1921632.1921639,
author = {Menon, Aditya Krishna and Elkan, Charles},
title = {Fast Algorithms for Approximating the Singular Value Decomposition},
year = {2011},
issue_date = {February 2011},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1921632.1921639},
doi = {10.1145/1921632.1921639},
abstract = {A low-rank approximation to a matrix A is a matrix with significantly smaller rank than A, and which is close to A according to some norm. Many practical applications involving the use of large matrices focus on low-rank approximations. By reducing the rank or dimensionality of the data, we reduce the complexity of analyzing the data. The singular value decomposition is the most popular low-rank matrix approximation. However, due to its expensive computational requirements, it has often been considered intractable for practical applications involving massive data. Recent developments have tried to address this problem, with several methods proposed to approximate the decomposition with better asymptotic runtime. We present an empirical study of these techniques on a variety of dense and sparse datasets. We find that a sampling approach of Drineas, Kannan and Mahoney is often, but not always, the best performing method. This method gives solutions with high accuracy much faster than classical SVD algorithms, on large sparse datasets in particular. Other modern methods, such as a recent algorithm by Rokhlin and Tygert, also offer savings compared to classical SVD algorithms. The older sampling methods of Achlioptas and McSherry are shown to sometimes take longer than classical SVD.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {13},
numpages = {36},
keywords = {experimental evaluation, low rank approximation, Singular value decomposition}
}

@article{10.1145/1921632.1921637,
author = {Magdalinos, Panagis and Doulkeridis, Christos and Vazirgiannis, Michalis},
title = {Enhancing Clustering Quality through Landmark-Based Dimensionality Reduction},
year = {2011},
issue_date = {February 2011},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1921632.1921637},
doi = {10.1145/1921632.1921637},
abstract = {Scaling up data mining algorithms for data of both high dimensionality and cardinality has been lately recognized as one of the most challenging problems in data mining research. The reason is that typical data mining tasks, such as clustering, cannot produce high quality results when applied on high-dimensional and/or large (in terms of cardinality) datasets. Data preprocessing and in particular dimensionality reduction constitute promising tools to deal with this problem. However, most of the existing dimensionality reduction algorithms share also the same disadvantages with data mining algorithms, when applied on large datasets of high dimensionality. In this article, we propose a fast and efficient dimensionality reduction algorithm (FEDRA), which is particularly scalable and therefore suitable for challenging datasets. FEDRA follows the landmark-based paradigm for embedding data objects in a low-dimensional projection space. By means of a theoretical analysis, we prove that FEDRA is efficient, while we demonstrate the achieved quality of results through experiments on datasets of higher cardinality and dimensionality than those employed in the evaluation of competitive algorithms. The obtained results prove that FEDRA manages to retain or ameliorate clustering quality while projecting in less than 10% of the initial dimensionality. Moreover, our algorithm produces embeddings that enable the faster convergence of clustering algorithms. Therefore, FEDRA emerges as a powerful and generic tool for data pre-processing, which can be integrated in other data mining algorithms, thus enhancing their performance.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {11},
numpages = {44},
keywords = {Landmarks, dimensionality reduction, clustering quality}
}

@article{10.1145/1921632.1921634,
author = {Kang, U. and Tsourakakis, Charalampos E. and Appel, Ana Paula and Faloutsos, Christos and Leskovec, Jure},
title = {HADI: Mining Radii of Large Graphs},
year = {2011},
issue_date = {February 2011},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1921632.1921634},
doi = {10.1145/1921632.1921634},
abstract = {Given large, multimillion-node graphs (e.g., Facebook, Web-crawls, etc.), how do they evolve over time? How are they connected? What are the central nodes and the outliers? In this article we define the Radius plot of a graph and show how it can answer these questions. However, computing the Radius plot is prohibitively expensive for graphs reaching the planetary scale.There are two major contributions in this article: (a) We propose HADI (HAdoop DIameter and radii estimator), a carefully designed and fine-tuned algorithm to compute the radii and the diameter of massive graphs, that runs on the top of the Hadoop/MapReduce system, with excellent scale-up on the number of available machines (b) We run HADI on several real world datasets including YahooWeb (6B edges, 1/8 of a Terabyte), one of the largest public graphs ever analyzed.Thanks to HADI, we report fascinating patterns on large networks, like the surprisingly small effective diameter, the multimodal/bimodal shape of the Radius plot, and its palindrome motion over time.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {8},
numpages = {24},
keywords = {small web, hadoop, graph mining, HADI, Radius plot}
}

@article{10.1145/1921632.1921638,
author = {Cheng, Hong and Zhou, Yang and Yu, Jeffrey Xu},
title = {Clustering Large Attributed Graphs: A Balance between Structural and Attribute Similarities},
year = {2011},
issue_date = {February 2011},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1921632.1921638},
doi = {10.1145/1921632.1921638},
abstract = {Social networks, sensor networks, biological networks, and many other information networks can be modeled as a large graph. Graph vertices represent entities, and graph edges represent their relationships or interactions. In many large graphs, there is usually one or more attributes associated with every graph vertex to describe its properties. In many application domains, graph clustering techniques are very useful for detecting densely connected groups in a large graph as well as for understanding and visualizing a large graph. The goal of graph clustering is to partition vertices in a large graph into different clusters based on various criteria such as vertex connectivity or neighborhood similarity. Many existing graph clustering methods mainly focus on the topological structure for clustering, but largely ignore the vertex properties, which are often heterogenous. In this article, we propose a novel graph clustering algorithm, SA-Cluster, which achieves a good balance between structural and attribute similarities through a unified distance measure. Our method partitions a large graph associated with attributes into k clusters so that each cluster contains a densely connected subgraph with homogeneous attribute values. An effective method is proposed to automatically learn the degree of contributions of structural similarity and attribute similarity. Theoretical analysis is provided to show that SA-Cluster is converging quickly through iterative cluster refinement. Some optimization techniques on matrix computation are proposed to further improve the efficiency of SA-Cluster on large graphs. Extensive experimental results demonstrate the effectiveness of SA-Cluster through comparisons with the state-of-the-art graph clustering and summarization methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {12},
numpages = {33},
keywords = {structural proximity, attribute similarity, Graph clustering}
}

@article{10.1145/1870096.1870097,
author = {Zhong, Ning and Piatetsky-Shapiro, Gregory and Yao, Yiyu and Yu, Philip S.},
title = {ACM TKDD Special Issue on Knowledge Discovery for Web Intelligence},
year = {2010},
issue_date = {December 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1870096.1870097},
doi = {10.1145/1870096.1870097},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {1},
numpages = {1}
}

@article{10.1145/1870096.1870102,
author = {Liu, Kun and Terzi, Evimaria},
title = {A Framework for Computing the Privacy Scores of Users in Online Social Networks},
year = {2010},
issue_date = {December 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1870096.1870102},
doi = {10.1145/1870096.1870102},
abstract = {A large body of work has been devoted to address corporate-scale privacy concerns related to social networks. Most of this work focuses on how to share social networks owned by organizations without revealing the identities or the sensitive relationships of the users involved. Not much attention has been given to the privacy risk of users posed by their daily information-sharing activities.In this article, we approach the privacy issues raised in online social networks from the individual users’ viewpoint: we propose a framework to compute the privacy score of a user. This score indicates the user’s potential risk caused by his or her participation in the network. Our definition of privacy score satisfies the following intuitive properties: the more sensitive information a user discloses, the higher his or her privacy risk. Also, the more visible the disclosed information becomes in the network, the higher the privacy risk. We develop mathematical models to estimate both sensitivity and visibility of the information. We apply our methods to synthetic and real-world data and demonstrate their efficacy and practical utility.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {6},
numpages = {30},
keywords = {information propagation, Social networks, expectation maximization, item-response theory, maximum-likelihood estimation}
}

@article{10.1145/1870096.1870101,
author = {Sakurai, Yasushi and Faloutsos, Christos and Papadimitriou, Spiros},
title = {Fast Discovery of Group Lag Correlations in Streams},
year = {2010},
issue_date = {December 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1870096.1870101},
doi = {10.1145/1870096.1870101},
abstract = {The study of data streams has received considerable attention in various communities (theory, databases, data mining, networking), due to several important applications, such as network analysis, sensor monitoring, financial data analysis, and moving object tracking. Our goal in this article is to monitor multiple numerical streams and determine which pairs are correlated with lags, as well as the value of each such lag. Lag correlations and anticorrelations are frequent and very interesting in practice. For example, a decrease in interest rates typically precedes an increase in house sales by a few months; higher amounts of fluoride in drinking water may lead to fewer dental cavities some years later. Other lag settings include network analysis, sensor monitoring, financial data analysis, and tracking of moving objects. Such data streams are often correlated or anticorrelated, but with unknown lag.We propose BRAID, a method of detecting lag correlations among data streams. BRAID can handle data streams of semi-infinite length incrementally, quickly, and with small resource consumption. However, BRAID requires space and time quadratic on a number of streams k. We also propose ThinBRAID, which is even faster than BRAID, requiring O(k) space and time per time tick. Our theoretical analysis shows that BRAID/ThinBRAID can estimate lag correlations with little or, often, with no error. Our experiments on real and realistic data show that BRAID and ThinBRAID detect the correct lag perfectly most of the time (the largest relative error was about 1%), while they are significantly faster (up to 40,000 times) than the na\"{\i}ve implementation.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {5},
numpages = {43},
keywords = {Time-series, cross-correlation, data streams}
}

@article{10.1145/1870096.1870100,
author = {Plangprasopchok, Anon and Lerman, Kristina},
title = {Modeling Social Annotation: A Bayesian Approach},
year = {2010},
issue_date = {December 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1870096.1870100},
doi = {10.1145/1870096.1870100},
abstract = {Collaborative tagging systems, such as Delicious, CiteULike, and others, allow users to annotate resources, for example, Web pages or scientific papers, with descriptive labels called tags. The social annotations contributed by thousands of users can potentially be used to infer categorical knowledge, classify documents, or recommend new relevant information. Traditional text inference methods do not make the best use of social annotation, since they do not take into account variations in individual users’ perspectives and vocabulary. In a previous work, we introduced a simple probabilistic model that takes the interests of individual annotators into account in order to find hidden topics of annotated resources. Unfortunately, that approach had one major shortcoming: the number of topics and interests must be specified a priori. To address this drawback, we extend the model to a fully Bayesian framework, which offers a way to automatically estimate these numbers. In particular, the model allows the number of interests and topics to change as suggested by the structure of the data. We evaluate the proposed model in detail on the synthetic and real-world data by comparing its performance to Latent Dirichlet Allocation on the topic extraction task. For the latter evaluation, we apply the model to infer topics of Web resources from social annotations obtained from Delicious in order to discover new resources similar to a specified one. Our empirical results demonstrate that the proposed model is a promising method for exploiting social knowledge contained in user-generated annotations.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {4},
numpages = {32},
keywords = {Collaborative tagging, resource discovery, probabilistic model, social annotation, social information processing}
}

@article{10.1145/1870096.1870099,
author = {Bouguessa, Mohamed and Wang, Shengrui and Dumoulin, Benoit},
title = {Discovering Knowledge-Sharing Communities in Question-Answering Forums},
year = {2010},
issue_date = {December 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1870096.1870099},
doi = {10.1145/1870096.1870099},
abstract = {In this article, we define a knowledge-sharing community in a question-answering forum as a set of askers and authoritative users such that, within each community, askers exhibit more homogeneous behavior in terms of their interactions with authoritative users than elsewhere. A procedure for discovering members of such a community is devised. As a case study, we focus on Yahoo! Answers, a large and diverse online question-answering service. Our contribution is twofold. First, we propose a method for automatic identification of authoritative actors in Yahoo! Answers. To this end, we estimate and then model the authority scores of participants as a mixture of gamma distributions. The number of components in the mixture is determined using the Bayesian Information Criterion (BIC), while the parameters of each component are estimated using the Expectation-Maximization (EM) algorithm. This method allows us to automatically discriminate between authoritative and nonauthoritative users. Second, we represent the forum environment as a type of transactional data such that each transaction summarizes the interaction of an asker with a specific set of authoritative users. Then, to group askers on the basis of their interactions with authoritative users, we propose a parameter-free transaction data clustering algorithm which is based on a novel criterion function. The identified clusters correspond to the communities that we aim to discover. To evaluate the suitability of our clustering algorithm, we conduct a series of experiments on both synthetic data and public real-life data. Finally, we put our approach to work using data from Yahoo! Answers which represent users’ activities over one full year.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {3},
numpages = {49},
keywords = {Clustering, mixture models, transaction data}
}

@article{10.1145/1870096.1870098,
author = {Tang, Jie and Yao, Limin and Zhang, Duo and Zhang, Jing},
title = {A Combination Approach to Web User Profiling},
year = {2010},
issue_date = {December 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1870096.1870098},
doi = {10.1145/1870096.1870098},
abstract = {In this article, we study the problem of Web user profiling, which is aimed at finding, extracting, and fusing the “semantic”-based user profile from the Web. Previously, Web user profiling was often undertaken by creating a list of keywords for the user, which is (sometimes even highly) insufficient for main applications. This article formalizes the profiling problem as several subtasks: profile extraction, profile integration, and user interest discovery. We propose a combination approach to deal with the profiling tasks. Specifically, we employ a classification model to identify relevant documents for a user from the Web and propose a Tree-Structured Conditional Random Fields (TCRF) to extract the profile information from the identified documents; we propose a unified probabilistic model to deal with the name ambiguity problem (several users with the same name) when integrating the profile information extracted from different sources; finally, we use a probabilistic topic model to model the extracted user profiles, and construct the user interest model. Experimental results on an online system show that the combination approach to different profiling tasks clearly outperforms several baseline methods. The extracted profiles have been applied to expert finding, an important application on the Web. Experiments show that the accuracy of expert finding can be improved (ranging from +6% to +26% in terms of MAP) by taking advantage of the profiles.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {2},
numpages = {44},
keywords = {information extraction, topic modeling, text mining, name disambiguation, social network, User profiling}
}

@article{10.1145/1839490.1839494,
author = {Becchetti, Luca and Boldi, Paolo and Castillo, Carlos and Gionis, Aristides},
title = {Efficient Algorithms for Large-Scale Local Triangle Counting},
year = {2010},
issue_date = {October 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1839490.1839494},
doi = {10.1145/1839490.1839494},
abstract = {In this article, we study the problem of approximate local triangle counting in large graphs. Namely, given a large graph G=(V,E) we want to estimate as accurately as possible the number of triangles incident to every node v∈ V in the graph. We consider the question both for undirected and directed graphs. The problem of computing the global number of triangles in a graph has been considered before, but to our knowledge this is the first contribution that addresses the problem of approximate local triangle counting with a focus on the efficiency issues arising in massive graphs and that also considers the directed case. The distribution of the local number of triangles and the related local clustering coefficient can be used in many interesting applications. For example, we show that the measures we compute can help detect the presence of spamming activity in large-scale Web graphs, as well as to provide useful features for content quality assessment in social networks.For computing the local number of triangles (undirected and directed), we propose two approximation algorithms, which are based on the idea of min-wise independent permutations [Broder et al. 1998]. Our algorithms operate in a semi-streaming fashion, using O(|V|) space in main memory and performing O(log |V|) sequential scans over the edges of the graph. The first algorithm we describe in this article also uses O(|E|) space of external memory during computation, while the second algorithm uses only main memory. We present the theoretical analysis as well as experimental results on large graphs, demonstrating the practical efficiency of our approach.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {13},
numpages = {28},
keywords = {massive-graph computing, Web computing, Clustering coefficient, social networks}
}

@article{10.1145/1839490.1839491,
author = {Thomas, Lini T. and Valluri, Satyanarayana R. and Karlapalem, Kamalakar},
title = {MARGIN: Maximal Frequent Subgraph Mining},
year = {2010},
issue_date = {October 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1839490.1839491},
doi = {10.1145/1839490.1839491},
abstract = {The exponential number of possible subgraphs makes the problem of frequent subgraph mining a challenge. The set of maximal frequent subgraphs is much smaller to that of the set of frequent subgraphs providing ample scope for pruning. MARGIN is a maximal subgraph mining algorithm that moves among promising nodes of the search space along the “border” of the infrequent and frequent subgraphs. This drastically reduces the number of candidate patterns in the search space. The proof of correctness of the algorithm is presented. Experimental results validate the efficiency and utility of the technique proposed.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {10},
numpages = {42},
keywords = {Graph mining, maximal frequent subgraph mining}
}

@article{10.1145/1839490.1839493,
author = {Chen, Jinlin and Xiao, Keli},
title = {BISC: A Bitmap Itemset Support Counting Approach for Efficient Frequent Itemset Mining},
year = {2010},
issue_date = {October 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1839490.1839493},
doi = {10.1145/1839490.1839493},
abstract = {The performance of a depth-first frequent itemset (FI) miming algorithm is closely related to the total number of recursions. In previous approaches this is mainly decided by the total number of FIs, which results in poor performance when a large number of FIs are involved. To solve this problem, a three-strategy adaptive algorithm, bitmap itemset support counting (BISC), is presented. The core strategy, BISC1, is used in the innermost steps of the recursion. For a database D with only s frequent items, a depth-first approach need up to s levels of recursions to detect all the FIs (up to 2s). BISC1 completely replaces these recursions with a special summation that directly calculates the supports of all the possible 2s candidate itemsets. With BISC1 the run-time is entirely independent of the database after one database scan, and the per-candidate cost is only s. To offset the exponential growth of cost (both time and space) with BISC1 as s increases, a second strategy, BISC2, is introduced to effectively double the acceptable range of s. BISC2 divides an itemset into prefix and suffix and improves the performance by pruning all the itemsets with infrequent prefixes. If the total number of frequent items in D is high, the classic database projection strategy is used. In this case for the first s items a single run of BISC (1 or 2) is applied. For each of the remaining items, a projected database is created and the mining process proceeds recursively. To achieve optimal performance, BISC adaptively decides which strategy to use based on the dataset and minimum support. Experiments show that BISC outperforms previous approaches in all the datasets tested. Even though this does not guarantee that BISC will always perform the best, the result is impressive given the fact that most existing algorithms are only efficient in some types of datasets. The memory usage of BISC is also comparable to those of other algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {12},
numpages = {37},
keywords = {Data mining algorithms, frequent itemset mining, association rule mining}
}

@article{10.1145/1839490.1839492,
author = {Deodhar, Meghana and Ghosh, Joydeep},
title = {SCOAL: A Framework for Simultaneous Co-Clustering and Learning from Complex Data},
year = {2010},
issue_date = {October 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1839490.1839492},
doi = {10.1145/1839490.1839492},
abstract = {For difficult classification or regression problems, practitioners often segment the data into relatively homogeneous groups and then build a predictive model for each group. This two-step procedure usually results in simpler, more interpretable and actionable models without any loss in accuracy. In this work, we consider problems such as predicting customer behavior across products, where the independent variables can be naturally partitioned into two sets, that is, the data is dyadic in nature. A pivoting operation now results in the dependent variable showing up as entries in a “customer by product” data matrix. We present the Simultaneous CO-clustering And Learning (SCOAL) framework, based on the key idea of interleaving co-clustering and construction of prediction models to iteratively improve both cluster assignment and fit of the models. This algorithm provably converges to a local minimum of a suitable cost function. The framework not only generalizes co-clustering and collaborative filtering to model-based co-clustering, but can also be viewed as simultaneous co-segmentation and classification or regression, which is typically better than independently clustering the data first and then building models. Moreover, it applies to a wide range of bi-modal or multimodal data, and can be easily specialized to address classification and regression problems. We demonstrate the effectiveness of our approach on both these problems through experimentation on a variety of datasets.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {11},
numpages = {31},
keywords = {multimodal data, dyadic data, regression, co-clustering, classification, Predictive modeling}
}

@article{10.1145/1839490.1839495,
author = {Zhang, Yin and Zhou, Zhi-Hua},
title = {Multilabel Dimensionality Reduction via Dependence Maximization},
year = {2010},
issue_date = {October 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1839490.1839495},
doi = {10.1145/1839490.1839495},
abstract = {Multilabel learning deals with data associated with multiple labels simultaneously. Like other data mining and machine learning tasks, multilabel learning also suffers from the curse of dimensionality. Dimensionality reduction has been studied for many years, however, multilabel dimensionality reduction remains almost untouched. In this article, we propose a multilabel dimensionality reduction method, MDDM, with two kinds of projection strategies, attempting to project the original data into a lower-dimensional feature space maximizing the dependence between the original feature description and the associated class labels. Based on the Hilbert-Schmidt Independence Criterion, we derive a eigen-decomposition problem which enables the dimensionality reduction process to be efficient. Experiments validate the performance of MDDM.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {14},
numpages = {21},
keywords = {Dimensionality reduction, multilabel learning}
}

@article{10.1145/1839490.1839496,
author = {Cui, Ying and Fern, Xiaoli Z. and Dy, Jennifer G.},
title = {Learning Multiple Nonredundant Clusterings},
year = {2010},
issue_date = {October 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1839490.1839496},
doi = {10.1145/1839490.1839496},
abstract = {Real-world applications often involve complex data that can be interpreted in many different ways. When clustering such data, there may exist multiple groupings that are reasonable and interesting from different perspectives. This is especially true for high-dimensional data, where different feature subspaces may reveal different structures of the data. However, traditional clustering is restricted to finding only one single clustering of the data. In this article, we propose a new clustering paradigm for exploratory data analysis: find all non-redundant clustering solutions of the data, where data points in the same cluster in one solution can belong to different clusters in other partitioning solutions. We present a framework to solve this problem and suggest two approaches within this framework: (1) orthogonal clustering, and (2) clustering in orthogonal subspaces. In essence, both approaches find alternative ways to partition the data by projecting it to a space that is orthogonal to the current solution. The first approach seeks orthogonality in the cluster space, while the second approach seeks orthogonality in the feature space. We study the relationship between the two approaches. We also combine our framework with techniques for automatically finding the number of clusters in the different solutions, and study stopping criteria for determining when all meaningful solutions are discovered. We test our framework on both synthetic and high-dimensional benchmark data sets, and the results show that indeed our approaches were able to discover varied clustering solutions that are interesting and meaningful.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {15},
numpages = {32},
keywords = {diverse clustering, orthogonalization, Nonredundant clustering, disparate clustering}
}

@article{10.1145/1857947.1857948,
author = {Wang, Wei},
title = {TKDD Special Issue SIGKDD 2009},
year = {2010},
issue_date = {October 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1857947.1857948},
doi = {10.1145/1857947.1857948},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {16},
numpages = {1}
}

@article{10.1145/1857947.1857952,
author = {Wu, Mingxi and Jermaine, Chris and Ranka, Sanjay and Song, Xiuyao and Gums, John},
title = {A Model-Agnostic Framework for Fast Spatial Anomaly Detection},
year = {2010},
issue_date = {October 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1857947.1857952},
doi = {10.1145/1857947.1857952},
abstract = {Given a spatial dataset placed on an n \texttimes{}n grid, our goal is to find the rectangular regions within which subsets of the dataset exhibit anomalous behavior. We develop algorithms that, given any user-supplied arbitrary likelihood function, conduct a likelihood ratio hypothesis test (LRT) over each rectangular region in the grid, rank all of the rectangles based on the computed LRT statistics, and return the top few most interesting rectangles. To speed this process, we develop methods to prune rectangles without computing their associated LRT statistics.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {20},
numpages = {30},
keywords = {antibiotic resistance, spatial anomaly, Anomaly detection, likelihood ratio test}
}

@article{10.1145/1857947.1857951,
author = {Liu, Chao and Guo, Fan and Faloutsos, Christos},
title = {Bayesian Browsing Model: Exact Inference of Document Relevance from Petabyte-Scale Data},
year = {2010},
issue_date = {October 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1857947.1857951},
doi = {10.1145/1857947.1857951},
abstract = {A fundamental challenge in utilizing Web search click data is to infer user-perceived relevance from the search log. Not only is the inference a difficult problem involving statistical reasonings but the bulky size, together with the ever-increasing nature, of the log data imposes extra requirements on scalability. In this paper, we propose the Bayesian Browsing Model (BBM), which performs exact inference of the document relevance, only requires a single pass of the data (i.e., the optimal scalability), and is shown effective.We present two sets of experiments to evaluate the model effectiveness and scalability. On the first set of over 50 million search instances of 1.1 million distinct queries, BBM outperforms the state-of-the-art competitor by 29.2% in log-likelihood while being 57 times faster. On the second click log set, spanning a quarter of petabyte, we showcase the scalability of BBM: we implemented it on a commercial MapReduce cluster, and it took only 3 hours to compute the relevance for 1.15 billion distinct query-URL pairs.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {19},
numpages = {26},
keywords = {click log analysis, Web search, Bayesian models}
}

@article{10.1145/1857947.1857949,
author = {Chen, Ye and Pavlov, Dmitry and Canny, John F.},
title = {Behavioral Targeting: The Art of Scaling Up Simple Algorithms},
year = {2010},
issue_date = {October 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1857947.1857949},
doi = {10.1145/1857947.1857949},
abstract = {Behavioral targeting (BT) leverages historical user behavior to select the ads most relevant to users to display. The state-of-the-art of BT derives a linear Poisson regression model from fine-grained user behavioral data and predicts click-through rate (CTR) from user history. We designed and implemented a highly scalable and efficient solution to BT using Hadoop MapReduce framework. With our parallel algorithm and the resulting system, we can build above 450 BT-category models from the entire Yahoo’s user base within one day, the scale that one can not even imagine with prior systems. Moreover, our approach has yielded 20% CTR lift over the existing production system by leveraging the well-grounded probabilistic model fitted from a much larger training dataset.Specifically, our major contributions include: (1) A MapReduce statistical learning algorithm and implementation that achieve optimal data parallelism, task parallelism, and load balance in spite of the typically skewed distribution of domain data. (2) An in-place feature vector generation algorithm with strict linear-time complexity O(n) regardless of the granularity of sliding target window. (3) An in-memory caching scheme that significantly reduces the number of disk IOs to make large-scale learning practical. (4) Highly efficient data structures and sparse representations of models and data to enable fast model updates. We believe that our work makes significant contributions to solving large-scale machine learning problems of industrial relevance in general. Finally, we report comprehensive experimental results, using industrial proprietary codebase and datasets.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {17},
numpages = {31},
keywords = {high-performance and terascale computing, behavioral targeting, Distributed data mining, statistical methods, large-scale, generalized linear model, Hadoop, user modeling, nonnegative matrix factorization, grid computing, MapReduce, parallel data mining}
}

@article{10.1145/1857947.1857950,
author = {Mohammed, Noman and Fung, Benjamin C. M. and Hung, Patrick C. K. and Lee, Cheuk-Kwong},
title = {Centralized and Distributed Anonymization for High-Dimensional Healthcare Data},
year = {2010},
issue_date = {October 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1857947.1857950},
doi = {10.1145/1857947.1857950},
abstract = {Sharing healthcare data has become a vital requirement in healthcare system management; however, inappropriate sharing and usage of healthcare data could threaten patients’ privacy. In this article, we study the privacy concerns of sharing patient information between the Hong Kong Red Cross Blood Transfusion Service (BTS) and the public hospitals. We generalize their information and privacy requirements to the problems of centralized anonymization and distributed anonymization, and identify the major challenges that make traditional data anonymization methods not applicable. Furthermore, we propose a new privacy model called LKC-privacy to overcome the challenges and present two anonymization algorithms to achieve LKC-privacy in both the centralized and the distributed scenarios. Experiments on real-life data demonstrate that our anonymization algorithms can effectively retain the essential information in anonymous data for data analysis and is scalable for anonymizing large datasets.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {18},
numpages = {33},
keywords = {Privacy, healthcare, anonymity, classification}
}

@article{10.1145/1754428.1754431,
author = {Ji, Shuiwang and Tang, Lei and Yu, Shipeng and Ye, Jieping},
title = {A Shared-Subspace Learning Framework for Multi-Label Classification},
year = {2010},
issue_date = {May 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1754428.1754431},
doi = {10.1145/1754428.1754431},
abstract = {Multi-label problems arise in various domains such as multi-topic document categorization, protein function prediction, and automatic image annotation. One natural way to deal with such problems is to construct a binary classifier for each label, resulting in a set of independent binary classification problems. Since multiple labels share the same input space, and the semantics conveyed by different labels are usually correlated, it is essential to exploit the correlation information contained in different labels. In this paper, we consider a general framework for extracting shared structures in multi-label classification. In this framework, a common subspace is assumed to be shared among multiple labels. We show that the optimal solution to the proposed formulation can be obtained by solving a generalized eigenvalue problem, though the problem is nonconvex. For high-dimensional problems, direct computation of the solution is expensive, and we develop an efficient algorithm for this case. One appealing feature of the proposed framework is that it includes several well-known algorithms as special cases, thus elucidating their intrinsic relationships. We further show that the proposed framework can be extended to the kernel-induced feature space. We have conducted extensive experiments on multi-topic web page categorization and automatic gene expression pattern image annotation tasks, and results demonstrate the effectiveness of the proposed formulation in comparison with several representative algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {8},
numpages = {29},
keywords = {shared subspace, least squares loss, kernel methods, gene expression pattern image annotation, web page categorization, Multi-label classification, singular value decomposition}
}

@article{10.1145/1754428.1754429,
author = {Vadera, Sunil},
title = {CSNL: A Cost-Sensitive Non-Linear Decision Tree Algorithm},
year = {2010},
issue_date = {May 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1754428.1754429},
doi = {10.1145/1754428.1754429},
abstract = {This article presents a new decision tree learning algorithm called CSNL that induces Cost-Sensitive Non-Linear decision trees. The algorithm is based on the hypothesis that nonlinear decision nodes provide a better basis than axis-parallel decision nodes and utilizes discriminant analysis to construct nonlinear decision trees that take account of costs of misclassification.The performance of the algorithm is evaluated by applying it to seventeen datasets and the results are compared with those obtained by two well known cost-sensitive algorithms, ICET and MetaCost, which generate multiple trees to obtain some of the best results to date. The results show that CSNL performs at least as well, if not better than these algorithms, in more than twelve of the datasets and is considerably faster. The use of bagging with CSNL further enhances its performance showing the significant benefits of using nonlinear decision nodes.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {6},
numpages = {25},
keywords = {Decision tree learning, cost-sensitive learning}
}

@article{10.1145/1754428.1754430,
author = {Kandylas, Vasileios and Upham, S. Phineas and Ungar, Lyle H.},
title = {Analyzing Knowledge Communities Using Foreground and Background Clusters},
year = {2010},
issue_date = {May 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1754428.1754430},
doi = {10.1145/1754428.1754430},
abstract = {Insight into the growth (or shrinkage) of “knowledge communities” of authors that build on each other's work can be gained by studying the evolution over time of clusters of documents. We cluster documents based on the documents they cite in common using the Streemer clustering method, which finds cohesive foreground clusters (the knowledge communities) embedded in a diffuse background. We build predictive models with features based on the citation structure, the vocabulary of the papers, and the affiliations and prestige of the authors and use these models to study the drivers of community growth and the predictors of how widely a paper will be cited. We find that scientific knowledge communities tend to grow more rapidly if their publications build on diverse information and use narrow vocabulary and that papers that lie on the periphery of a community have the highest impact, while those not in any community have the lowest impact.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {7},
numpages = {35},
keywords = {Text mining, clustering, community evolution, knowledge communities, citation analysis}
}

@article{10.1145/1754428.1754432,
author = {Ruggieri, Salvatore and Pedreschi, Dino and Turini, Franco},
title = {Data Mining for Discrimination Discovery},
year = {2010},
issue_date = {May 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1754428.1754432},
doi = {10.1145/1754428.1754432},
abstract = {In the context of civil rights law, discrimination refers to unfair or unequal treatment of people based on membership to a category or a minority, without regard to individual merit. Discrimination in credit, mortgage, insurance, labor market, and education has been investigated by researchers in economics and human sciences. With the advent of automatic decision support systems, such as credit scoring systems, the ease of data collection opens several challenges to data analysts for the fight against discrimination. In this article, we introduce the problem of discovering discrimination through data mining in a dataset of historical decision records, taken by humans or by automatic systems. We formalize the processes of direct and indirect discrimination discovery by modelling protected-by-law groups and contexts where discrimination occurs in a classification rule based syntax. Basically, classification rules extracted from the dataset allow for unveiling contexts of unlawful discrimination, where the degree of burden over protected-by-law groups is formalized by an extension of the lift measure of a classification rule. In direct discrimination, the extracted rules can be directly mined in search of discriminatory contexts. In indirect discrimination, the mining process needs some background knowledge as a further input, for example, census data, that combined with the extracted rules might allow for unveiling contexts of discriminatory decisions. A strategy adopted for combining extracted classification rules with background knowledge is called an inference model. In this article, we propose two inference models and provide automatic procedures for their implementation. An empirical assessment of our results is provided on the German credit dataset and on the PKDD Discovery Challenge 1999 financial dataset.},
journal = {ACM Trans. Knowl. Discov. Data},
month = may,
articleno = {9},
numpages = {40},
keywords = {classification rules, Discrimination}

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr

branch_name: refs/heads/main