Publications

Refine Results

(Filters Applied) Clear All

Toward matched filter optimization for subgraph detection in dynamic networks

Published in:
2012 SSP: 2012 IEEE Statistical Signal Processing Workshop, 5-8 August 2012, pp. 113-116.

Summary

This paper outlines techniques for optimization of filter coefficients in a spectral framework for anomalous subgraph detection. Restricting the scope to the detection of a known signal in i.i.d. noise, the optimal coefficients for maximizing the signal's power are shown to be found via a rank-1 tensor approximation of the subgraph's dynamic topology. While this technique optimizes our power metric, a filter based on average degree is shown in simulation to work nearly as well in terms of power maximization and detection performance, and better separates the signal from the noise in the eigenspace.
READ LESS

Summary

This paper outlines techniques for optimization of filter coefficients in a spectral framework for anomalous subgraph detection. Restricting the scope to the detection of a known signal in i.i.d. noise, the optimal coefficients for maximizing the signal's power are shown to be found via a rank-1 tensor approximation of the...

READ MORE

A stochastic system for large network growth

Published in:
IEEE Signal Process. Lett., Vol. 19, No. 6, June 2012, pp. 356-359.

Summary

This letter proposes a new model for preferential attachment in dynamic directed networks. This model consists of a linear time-invariant system that uses past observations to predict future attachment rates, and an innovation noise process that induces growth on vertices that previously had no attachments. Analyzing a large citation network in this context, we show that the proposed model fits the data better than existing preferential attachment models. An analysis of the noise in the dataset reveals power-law degree distributions often seen in large networks, and polynomial decay with respect to age in the probability of citing yet-uncited documents.
READ LESS

Summary

This letter proposes a new model for preferential attachment in dynamic directed networks. This model consists of a linear time-invariant system that uses past observations to predict future attachment rates, and an innovation noise process that induces growth on vertices that previously had no attachments. Analyzing a large citation network...

READ MORE

A scalable signal processing architecture for massive graph analysis

Published in:
ICASSP 2012, Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, 25-30 March 2012, pp. 5329-32.

Summary

In many applications, it is convenient to represent data as a graph, and often these datasets will be quite large. This paper presents an architecture for analyzing massive graphs, with a focus on signal processing applications such as modeling, filtering, and signal detection. We describe the architecture, which covers the entire processing chain, from data storage to graph construction to graph analysis and subgraph detection. The data are stored in a new format that allows easy extraction of graphs representing any relationship existing in the data. The principal analysis algorithm is the partial eigendecomposition of the modularity matrix, whose running time is discussed. A large document dataset is analyzed, and we present subgraphs that stand out in the principal eigenspace of the time varying graphs, including behavior we regard as clutter as well as small, tightly-connected clusters that emerge over time.
READ LESS

Summary

In many applications, it is convenient to represent data as a graph, and often these datasets will be quite large. This paper presents an architecture for analyzing massive graphs, with a focus on signal processing applications such as modeling, filtering, and signal detection. We describe the architecture, which covers the...

READ MORE

Goodness-of-fit statistics for anomaly detection in Chung-Lu random graphs

Published in:
ICASSP 2012, Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, 25-30 March 2012, pp. 3265-8.

Summary

Anomaly detection in graphs is a relevant problem in numerous applications. When determining whether an observation is anomalous with respect to the model of typical behavior, the notion of "goodness of fit" is important. This notion, however, is not well understood in the context of graph data. In this paper, we propose three goodness-of-fit statistics for Chung-Lu random graphs, and analyze their efficacy in discriminating graphs generated by the Chung-Lu model from those with anomalous topologies. In the results of a Monte Carlo simulation, we see that the most powerful statistic for anomaly detection depends on the type of anomaly, suggesting that a hybrid statistic would be the most powerful.
READ LESS

Summary

Anomaly detection in graphs is a relevant problem in numerous applications. When determining whether an observation is anomalous with respect to the model of typical behavior, the notion of "goodness of fit" is important. This notion, however, is not well understood in the context of graph data. In this paper...

READ MORE

Moments of parameter estimates for Chung-Lu random graph models

Published in:
ICASSP 2012, Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, 25-30 March 2012, pp. 3961-4.

Summary

As abstract representations of relational data, graphs and networks find wide use in a variety of fields, particularly when working in non- Euclidean spaces. Yet for graphs to be truly useful in in the context of signal processing, one ultimately must have access to flexible and tractable statistical models. One model currently in use is the Chung- Lu random graph model, in which edge probabilities are expressed in terms of a given expected degree sequence. An advantage of this model is that its parameters can be obtained via a simple, standard estimator. Although this estimator is used frequently, its statistical properties have not been fully studied. In this paper, we develop a central limit theory for a simplified version of the Chung-Lu parameter estimator. We then derive approximations for moments of the general estimator using the delta method, and confirm the effectiveness of these approximations through empirical examples.
READ LESS

Summary

As abstract representations of relational data, graphs and networks find wide use in a variety of fields, particularly when working in non- Euclidean spaces. Yet for graphs to be truly useful in in the context of signal processing, one ultimately must have access to flexible and tractable statistical models. One...

READ MORE

Dynamic Distributed Dimensional Data Model (D4M) database and computation system

Summary

A crucial element of large web companies is their ability to collect and analyze massive amounts of data. Tuple store databases are a key enabling technology employed by many of these companies (e.g., Google Big Table and Amazon Dynamo). Tuple stores are highly scalable and run on commodity clusters, but lack interfaces to support efficient development of mathematically based analytics. D4M (Dynamic Distributed Dimensional Data Model) has been developed to provide a mathematically rich interface to tuple stores (and structured query language "SQL" databases). D4M allows linear algebra to be readily applied to databases. Using D4M, it is possible to create composable analytics with significantly less effort than using traditional approaches. This work describes the D4M technology and its application and performance.
READ LESS

Summary

A crucial element of large web companies is their ability to collect and analyze massive amounts of data. Tuple store databases are a key enabling technology employed by many of these companies (e.g., Google Big Table and Amazon Dynamo). Tuple stores are highly scalable and run on commodity clusters, but...

READ MORE

Fundamental Questions in the Analysis of Large Graphs

Summary

Graphs are a general approach for representing information that spans the widest possible range of computing applications. They are particularly important to computational biology, web search, and knowledge discovery. As the sizes of graphs increase, the need to apply advanced mathematical and computational techniques to solve these problems is growing dramatically. Examining the mathematical and computational foundations of the analysis of large graphs generally leads to more questions than answers. This book concludes with a discussion of some of these questions.
READ LESS

Summary

Graphs are a general approach for representing information that spans the widest possible range of computing applications. They are particularly important to computational biology, web search, and knowledge discovery. As the sizes of graphs increase, the need to apply advanced mathematical and computational techniques to solve these problems is growing...

READ MORE

A knowledge-based operator for a genetic algorithm which optimizes the distribution of sparse matrix data

Published in:
Parallel Architectures and Bioinspired Algorithms

Summary

We present the Hogs and Slackers genetic algorithm (GA) which addresses the problem of improving the parallelization efficiency of sparse matrix computations by optimally distributing blocks of matrices data. The performance of a distribution is sensitive to the non-zero patterns in the data, the algorithm, and the hardware architecture. In a candidate distributions the Hogs and Slackers GA identifies processors with many operations – hogs, and processors with fewer operations – slackers. Its intelligent operation-balancing mutation operator then swaps data blocks between hogs and slackers to explore a new data distribution.We show that the Hogs and Slackers GA performs better than a baseline GA. We demonstrate Hogs and Slackers GA’s optimization capability with an architecture study of varied network and memory bandwidth and latency.
READ LESS

Summary

We present the Hogs and Slackers genetic algorithm (GA) which addresses the problem of improving the parallelization efficiency of sparse matrix computations by optimally distributing blocks of matrices data. The performance of a distribution is sensitive to the non-zero patterns in the data, the algorithm, and the hardware architecture. In...

READ MORE

Eigenspace analysis for threat detection in social networks

Published in:
Int. Conf. on Information Fusion, 5 July 2011.

Summary

The problem of detecting a small, anomalous subgraph within a large background network is important and applicable to many fields. The non-Euclidean nature of graph data, however, complicates the application of classical detection theory in this context. A recent statistical framework for anomalous subgraph detection uses spectral properties of a graph's modularity matrix to determine the presence of an anomaly. In this paper, this detection framework and the related algorithms are applied to data focused on a specific application: detection of a threat subgraph embedded in a social network. The results presented use data created to simulate threat activity among noisy interactions. The detectability of the threat subgraph and its separability from the noise is analyzed under a variety of background conditions in both static and dynamic scenarios.
READ LESS

Summary

The problem of detecting a small, anomalous subgraph within a large background network is important and applicable to many fields. The non-Euclidean nature of graph data, however, complicates the application of classical detection theory in this context. A recent statistical framework for anomalous subgraph detection uses spectral properties of a...

READ MORE

Anomalous subgraph detection via sparse principal component analysis

Published in:
Proc. 2011 IEEE Statistical Signal Processing Workshop (SSP), 28-30 June 2011, pp. 485-488.

Summary

Network datasets have become ubiquitous in many fields of study in recent years. In this paper we investigate a problem with applicability to a wide variety of domains - detecting small, anomalous subgraphs in a background graph. We characterize the anomaly in a subgraph via the well-known notion of network modularity, and we show that the optimization problem formulation resulting from our setup is very similar to a recently introduced technique in statistics called Sparse Principal Component Analysis (Sparse PCA), which is an extension of the classical PCA algorithm. The exact version of our problem formulation is a hard combinatorial optimization problem, so we consider a recently introduced semidefinite programming relaxation of the Sparse PCA problem. We show via results on simulated data that the technique is very promising.
READ LESS

Summary

Network datasets have become ubiquitous in many fields of study in recent years. In this paper we investigate a problem with applicability to a wide variety of domains - detecting small, anomalous subgraphs in a background graph. We characterize the anomaly in a subgraph via the well-known notion of network...

READ MORE