OpenRaiser/Intern-Atlas huggingface dataset:
Measuring the effects of preprocessing decisions and network forces in dynamic network analysis
Authors: Jerry Scripps, Pang-Ning Tan, Abdol-Hossein Esfahanian
Venue: KDD
Year: 2009

Social networks have become a major focus of research in recent years, initially directed towards static networks but increasingly, towards dynamic ones. In this paper, we investigate how different pre-processing decisions and different network forces such as selection and influence affect the modeling of dynamic networks. We also present empirical justification for some of the modeling assumptions made in dynamic network analysis (e.g., first-order Markovian assumption) and develop metrics to measure the alignment between links and attributes under different strategies of using the historical network data. We also demonstrate the effect of attribute drift, that is, the importance of individual attributes in forming links change over time.
Anomalous window discovery through scan statistics for linear intersecting paths (SSLIP)
Authors: Lei Shi, Vandana Pursnani Janeja
Venue: KDD
Year: 2009

Anomalous windows are the contiguous groupings of data points. In this paper, we propose an approach for discovering anomalous windows using Scan Statistics for Linear Intersecting Paths (SSLIP). A linear path refers to a path represented by a line with a single dimensional spatial coordinate marking an observation point. Our approach for discovering anomalous windows along linear paths comprises of the following distinct steps: (a) Cross Path Discovery: where we identify a subset of intersecting paths to be considered, (b) Anomalous Window Discovery: where we outline three order invariant algorithms, namely SSLIP, Brute Force-SSLIP and Central Brute Force-SSLIP, for the traversal of the cross paths to identify varying size directional windows along the paths. For identifying an anomalous window we compute an unusualness metric, in the form of a likelihood ratio to indicate the degree of unusualness of this window with respect to the rest of the data. We identify the window with the highest likelihood ratio as our anomalous window, and (c) Monte Carlo Simulations: to ascertain whether this window is truly anomalous and not just a random occurrence we perform hypothesis testing by computing a p-value using Monte Carlo Simulations. We present extensive experimental results in real world accident datasets for various highways with known issues(code and data available from [27], [21]). Our results show that our approach indeed is effective in identifying anomalous traffic accident windows along multiple intersecting highways.
Causality quantification and its applications: structuring and modeling of multivariate time series
Authors: Takashi Shibuya, Tatsuya Harada, Yasuo Kuniyoshi
Venue: KDD
Year: 2009

Time series prediction is an important issue in a wide range of areas. There are various real world processes whose states vary continuously, and those processes may have influences on each other. If the past information of one process X improves the predictability of another process Y, X is said to have a causal influence on Y. In order to make good predictions, it is necessary to identify the appropriate causal relationships. In addition, the processes to be modeled may include symbolic data as well as numerical data. Therefore, it is important to deal with symbolic and numerical time series seamlessly when attempting to detect causality.
Data mining at NASA: from theory to applications
Authors: Ashok N. Srivastava
Venue: KDD
Year: 2009

NASA has some of the largest and most complex data sources in the world, with data sources ranging from the earth sciences, space sciences, and massive distributed engineering data sets from commercial aircraft and spacecraft. This talk will discuss some of the issues and algorithms developed to analyze and discover patterns in these data sets. We will also provide an overview of a large research program in Integrated Vehicle Health Management. The goal of this program is to develop advanced technologies to automatically detect, diagnose, predict, and mitigate adverse events during the flight of an aircraft. A case study will be presented on a recent data mining analysis performed to support the Flight Readiness Review of the Space Shuttle Mission STS-119.
Mining brain region connectivity for alzheimer's disease study via sparse inverse covariance estimation
Authors: Liang Sun, Rinkal Patel, Jun Liu, Kewei Chen, Teresa Wu, Jing Li, Eric Reiman, Jieping Ye
Venue: KDD
Year: 2009

Effective diagnosis of Alzheimer's disease (AD), the most common type of dementia in elderly patients, is of primary importance in biomedical research. Recent studies have demonstrated that AD is closely related to the structure change of the brain network, i.e., the connectivity among different brain regions. The connectivity patterns will provide useful imaging-based biomarkers to distinguish Normal Controls (NC), patients with Mild Cognitive Impairment (MCI), and patients with AD. In this paper, we investigate the sparse inverse covariance estimation technique for identifying the connectivity among different brain regions. In particular, a novel algorithm based on the block coordinate descent approach is proposed for the direct estimation of the inverse covariance matrix. One appealing feature of the proposed algorithm is that it allows the user feedback (e.g., prior domain knowledge) to be incorporated into the estimation process, while the connectivity patterns can be discovered automatically. We apply the proposed algorithm to a collection of FDG-PET images from 232 NC, MCI, and AD subjects. Our experimental results demonstrate that the proposed algorithm is promising in revealing the brain region connectivity differences among these groups.
Ranking-based clustering of heterogeneous information networks with star network schema
Authors: Yizhou Sun, Yintao Yu, Jiawei Han
Venue: KDD
Year: 2009

A heterogeneous information network is an information network
Social influence analysis in large-scale networks
Authors: Jie Tang, Jimeng Sun, Chi Wang, Zi Yang
Venue: KDD
Year: 2009

In large social networks, nodes (users, entities) are influenced by others for various reasons. For example, the colleagues have strong influence on one's work, while the friends have strong influence on one's daily life. How to differentiate the social influences from different angles(topics)? How to quantify the strength of those social influences? How to estimate the model on real large networks?
Constant-factor approximation algorithms for identifying dynamic communities
Authors: Chayant Tantipathananandh, Tanya Y. Berger-Wolf
Venue: KDD
Year: 2009

We propose two approximation algorithms for identifying communities in dynamic social networks. Communities are intuitively characterized as "unusually densely knit" subsets of a social network. This notion becomes more problematic if the social interactions change over time. Aggregating social networks over time can radically misrepresent the existing and changing community structure. Recently, we have proposed an optimization-based framework for modeling dynamic community structure. Also, we have proposed an algorithm for finding such structure based on maximum weight bipartite matching. In this paper, we analyze its performance guarantee for a special case where all actors can be observed at all times. In such instances, we show that the algorithm is a small constant factor approximation of the optimum. We use a similar idea to design an approximation algorithm for the general case where some individuals are possibly unobserved at times, and to show that the approximation factor increases twofold but remains a constant regardless of the input size. This is the first algorithm for inferring communities in dynamic networks with a provable approximation guarantee. We demonstrate the general algorithm on real data sets. The results confirm the efficiency and effectiveness of the algorithm in identifying dynamic communities.
DOULION: counting triangles in massive graphs with a coin
Authors: Charalampos E. Tsourakakis, U Kang, Gary L. Miller, Christos Faloutsos
Venue: KDD
Year: 2009

Counting the number of triangles in a graph is a beautiful algorithmic problem which has gained importance over the last years due to its significant role in complex network analysis. Metrics frequently computed such as the clustering coefficient and the transitivity ratio involve the execution of a triangle counting algorithm. Furthermore, several interesting graph mining applications rely on computing the number of triangles in the graph of interest.
Learning, indexing, and diagnosing network faults
Authors: Ting Wang, Mudhakar Srivatsa, Dakshi Agrawal, Ling Liu
Venue: KDD
Year: 2009

Modern communication networks generate massive volume of operational event data, e.g., alarm, alert, and metrics, which can be used by a network management system (NMS) to diagnose potential faults. In this work, we introduce a new class of indexable fault signatures that encode temporal evolution of events generated by a network fault as well as topological relationships among the nodes where these events occur. We present an efficient learning algorithm to extract such fault signatures from noisy historical event data, and with the help of novel space-time indexing structures, we show how to perform efficient, online signature matching. We provide results from extensive experimental studies to explore the efficacy of our approach and point out potential applications of such signatures for many different types of networks including social and information networks.
Network science: an introduction to recent statistical approaches
Authors: Stanley Wasserman
Venue: KDD
Year: 2009

Network science focuses on relationships between social entities. It is used widely in the social and behavioral sciences, as well as in political science, economics, organizational science, and industrial engineering. The social network perspective has been developed over the last sixty years by researchers in psychology, sociology, and anthropology, and morerecently, to a lesser extent, in physics. Network science is gaining recognition and standing in the general social and behavioral science communities as the theoretical basis for examining social structures. This basis has been clearly defined by many theorists, and the paradigm convincingly applied to important substantive problems. However, the paradigm requires a new and different set of concepts and analytic tools, beyond those provided by standard quantitative (particularly, statistical) methods. These concepts and tools are the topics of this talk.
A LRT framework for fast spatial anomaly detection
Authors: Mingxi Wu, Xiuyao Song, Chris Jermaine, Sanjay Ranka, John Gums
Venue: KDD
Year: 2009

Given a spatial data set placed on an n x n grid, our goal is to find the rectangular regions within which subsets of the data set 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.
Named entity mining from click-through data using weakly supervised latent dirichlet allocation
Authors: Gu Xu, Shuang-Hong Yang, Hang Li
Venue: KDD
Year: 2009

This paper addresses Named Entity Mining (NEM), in which we mine knowledge about named entities such as movies, games, and books from a huge amount of data. NEM is potentially useful in many applications including web search, online advertisement, and recommender system. There are three challenges for the task: finding suitable data source, coping with the ambiguities of named entity classes, and incorporating necessary human supervision into the mining process. This paper proposes conducting NEM by using click-through data collected at a web search engine, employing a topic model that generates the click-through data, and learning the topic model by weak supervision from humans. Specifically, it characterizes each named entity by its associated queries and URLs in the click-through data. It uses the topic model to resolve ambiguities of named entity classes by representing the classes as topics. It employs a method, referred to as Weakly Supervised Latent Dirichlet Allocation (WS-LDA), to accurately learn the topic model with partially labeled named entities. Experiments on a large scale click-through data containing over 1.5 billion query-URL pairs show that the proposed approach can conduct very accurate NEM and significantly outperforms the baseline.
Incorporating site-level knowledge for incremental crawling of web forums: a list-wise strategy
Authors: Jiang-Ming Yang, Rui Cai, Chunsong Wang, Hua Huang, Lei Zhang, Wei-Ying Ma
Venue: KDD
Year: 2009

We study in this paper the problem of incremental crawling of web forums, which is a very fundamental yet challenging step in many web applications. Traditional approaches mainly focus on scheduling the revisiting strategy of each individual page. However, simply assigning different weights for different individual pages is usually inefficient in crawling forum sites because of the different characteristics between forum sites and general websites. Instead of treating each individual page independently, we propose a list-wise strategy by taking into account the site-level knowledge. Such site-level knowledge is mined through reconstructing the linking structure, called sitemap, for a given forum site. With the sitemap, posts from the same thread but distributed on various pages can be concatenated according to their timestamps. After that, for each thread, we employ a regression model to predict the time when the next post arrives. Based on this model, we develop an efficient crawler which is 260% faster than some state-of-the-art methods in terms of fetching new generated content; and meanwhile our crawler also ensure a high coverage ratio. Experimental results show promising performance of Coverage, Bandwidth utilization, and Timeliness of our crawler on 18 various forums.
Effective multi-label active learning for text classification
Authors: Bishan Yang, Jian-Tao Sun, Tengjiao Wang, Zheng Chen
Venue: KDD
Year: 2009

Labeling text data is quite time-consuming but essential for automatic text classification. Especially, manually creating multiple labels for each document may become impractical when a very large amount of data is needed for training multi-label text classifiers. To minimize the human-labeling efforts, we propose a novel multi-label active learning approach which can reduce the required labeled data without sacrificing the classification accuracy. Traditional active learning algorithms can only handle single-label problems, that is, each data is restricted to have one label. Our approach takes into account the multi-label information, and select the unlabeled data which can lead to the largest reduction of the expected model loss. Specifically, the model loss is approximated by the size of version space, and the reduction rate of the size of version space is optimized with Support Vector Machines (SVM). An effective label prediction method is designed to predict possible labels for each unlabeled data point, and the expected loss for multi-label data is approximated by summing up losses on all labels according to the most confident result of label prediction. Experiments on several real-world data sets (all are publicly available) demonstrate that our approach can obtain promising classification result with much fewer labeled data than state-of-the-art methods.
Efficient methods for topic model inference on streaming document collections
Authors: Limin Yao, David M. Mimno, Andrew McCallum
Venue: KDD
Year: 2009

Topic models provide a powerful tool for analyzing large text collections by representing high dimensional data in a low dimensional subspace. Fitting a topic model given a set of training documents requires approximate inference techniques that are computationally expensive. With today's large-scale, constantly expanding document collections, it is useful to be able to infer topic distributions for new documents without retraining the model. In this paper, we empirically evaluate the performance of several methods for topic inference in previously unseen documents, including methods based on Gibbs sampling, variational inference, and a new method inspired by text classification. The classification-based inference method produces results similar to iterative inference methods, but requires only a single matrix multiplication. In addition to these inference methods, we present SparseLDA, an algorithm and data structure for evaluating Gibbs sampling distributions. Empirical results indicate that SparseLDA can be approximately 20 times faster than traditional LDA and provide twice the speedup of previously published fast sampling methods, while also using substantially less memory.
Intelligent file scoring system for malware detection from the gray list
Authors: Yanfang Ye, Tao Li, Qingshan Jiang, Zhixue Han, Li Wan
Venue: KDD
Year: 2009

Currently, the most significant line of defense against malware is anti-virus products which focus on authenticating valid software from a white list, blocking invalid software from a black list, and running any unknown software (i.e., the gray list) in a controlled manner. The gray list, containing unknown software programs which could be either normal or malicious, is usually authenticated or rejected manually by virus analysts. Unfortunately, along with the development of the malware writing techniques, the number of file samples in the gray list that need to be analyzed by virus analysts on a daily basis is constantly increasing. In this paper, we develop an intelligent file scoring system (IFSS for short) for malware detection from the gray list by an ensemble of heterogeneous base-level classifiers derived by different learning methods, using different feature representations on dynamic training sets. To the best of our knowledge, this is the first work of applying such ensemble methods for malware detection. IFSS makes it practical for virus analysts to identify malware samples from the huge gray list and improves the detection ability of anti-virus software. It has already been incorporated into the scanning tool of Kingsoft's Anti-Virus software. The case studies on large and real daily collection of the gray list illustrate that the detection ability and efficiency of our IFSS system outperforms other popular scanning tools such as NOD32 and Kaspersky.
Learning patterns in the dynamics of biological networks
Authors: Chang Hun You, Lawrence B. Holder, Diane J. Cook
Venue: KDD
Year: 2009

Our dynamic graph-based relational mining approach has been developed to learn structural patterns in biological networks as they change over time. The analysis of dynamic networks is important not only to understand life at the system-level, but also to discover novel patterns in other structural data. Most current graph-based data mining approaches overlook dynamic features of biological networks, because they are focused on only static graphs. Our approach analyzes a sequence of graphs and discovers rules that capture the changes that occur between pairs of graphs in the sequence. These rules represent the graph rewrite rules that the first graph must go through to be isomorphic to the second graph. Then, our approach feeds the graph rewrite rules into a machine learning system that learns general transformation rules describing the types of changes that occur for a class of dynamic biological networks. The discovered graph-rewriting rules show how biological networks change over time, and the transformation rules show the repeated patterns in the structural changes. In this paper, we apply our approach to biological networks to evaluate our approach and to understand how the biosystems change over time. We evaluate our results using coverage and prediction metrics, and compare to biological literature.
Toward autonomic grids: analyzing the job flow with affinity streaming
Authors: Xiangliang Zhang, Cyril Furtlehner, Julien Perez, Cécile Germain-Renaud, Michèle Sebag
Venue: KDD
Year: 2009

The Affinity Propagation (AP) clustering algorithm proposed by Frey and Dueck (2007) provides an understandable, nearly optimal summary of a dataset, albeit with quadratic computational complexity. This paper, motivated by Autonomic Computing, extends AP to the data streaming framework. Firstly a hierarchical strategy is used to reduce the complexity to O(N1+ε); the distortion loss incurred is analyzed in relation with the dimension of the data items. Secondly, a coupling with a change detection test is used to cope with non-stationary data distribution, and rebuild the model as needed. The presented approach StrAP is applied to the stream of jobs submitted to the EGEE Grid, providing an understandable description of the job flow and enabling the system administrator to spot online some sources of failures.
Parallel community detection on large networks with propinquity dynamics
Authors: Yuzhou Zhang, Jianyong Wang, Yi Wang, Lizhu Zhou
Venue: KDD
Year: 2009

Graphs or networks can be used to model complex systems. Detecting community structures from large network data is a classic and challenging task. In this paper, we propose a novel community detection algorithm, which utilizes a dynamic process by contradicting the network topology and the topology-based propinquity, where the propinquity is a measure of the probability for a pair of nodes involved in a coherent community structure. Through several rounds of mutual reinforcement between topology and propinquity, the community structures are expected to naturally emerge. The overlapping vertices shared between communities can also be easily identified by an additional simple postprocessing. To achieve better efficiency, the propinquity is incrementally calculated. We implement the algorithm on a vertex-oriented bulk synchronous parallel(BSP) model so that the mining load can be distributed on thousands of machines. We obtained interesting experimental results on several real network data.