Publications

Refine Results

(Filters Applied) Clear All

By

A spectral framework for anomalous subgraph detection

August 15, 2015
  |
Journal Article
Author:
Benjamin A. Miller
…
Published in:
IEEE Trans. Signal Process., Vol. 63, No. 16, 15 August 2015, 4191-4206.
Topic:
big data
R&D area:
R&D group:

Summary

A wide variety of application domains is concerned with data consisting of entities and their relationships or connections, formally represented as graphs. Within these diverse application areas, a common problem of interest is the detection of a subset of entities whose connectivity is anomalous with respect to the rest of the data. While the detection of such anomalous subgraphs has received a substantial amount of attention, no application-agnostic framework exists for analysis of signal detectability in graph-based data. In this paper, we describe a framework that enables such analysis using the principal eigenspace of a graph's residuals matrix, commonly called the modularity matrix in community detection. Leveraging this analytical tool, we show that the framework has a natural power metric in the spectral norm of the anomalous subgraph's adjacency matrix (signal power) and of the background graph's residuals matrix (noise power). We propose several algorithms based on spectral properties of the residuals matrix, with more computationally expensive techniques providing greater detection power. Detection and identification performance are presented for a number of signal and noise models, including clusters and bipartite foregrounds embedded into simple random backgrounds, as well as graphs with community structure and realistic degree distributions. The trends observed verify intuition gleaned from other signal processing areas, such as greater detection power when the signal is embedded within a less active portion of the background. We demonstrate the utility of the proposed techniques in detecting small, highly anomalous subgraphs in real graphs derived from Internet traffic and product co-purchases.
READ LESS

Summary

A wide variety of application domains is concerned with data consisting of entities and their relationships or connections, formally represented as graphs. Within these diverse application areas, a common problem of interest is the detection of a subset of entities whose connectivity is anomalous with respect to the rest of...

READ MORE
A spectral framework for anomalous subgraph detection

Detection theory for graphs

January 30, 2013
  |
Journal Article
Author:
Benjamin A. Miller
…
Published in:
Lincoln Laboratory Journal, Vol. 20, No. 1, 2013, pp. 10-30.
Topic:
signal processing
R&D area:
R&D group:

Summary

Graphs are fast emerging as a common data structure used in many scientific and engineering fields. While a wide variety of techniques exist to analyze graph datasets, practitioners currently lack a signal processing theory akin to that of detection and estimation in the classical setting of vector spaces with Gaussian noise. Using practical detection examples involving large, random "background" graphs and noisy real-world datasets, the authors present a novel graph analytics framework that allows for uncued analysis of very large datasets. This framework combines traditional computer science techniques with signal processing in the context of graph data, creating a new research area at the intersection of the two fields.
READ LESS

Summary

Graphs are fast emerging as a common data structure used in many scientific and engineering fields. While a wide variety of techniques exist to analyze graph datasets, practitioners currently lack a signal processing theory akin to that of detection and estimation in the classical setting of vector spaces with Gaussian...

READ MORE
Detection theory for graphs

A scalable signal processing architecture for massive graph analysis

March 25, 2012
  |
Conference Paper
Author:
Benjamin A. Miller
…
Published in:
ICASSP 2012, Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, 25-30 March 2012, pp. 5329-32.
Topic:
supercomputing
R&D area:
R&D group:

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
A scalable signal processing architecture for massive graph analysis

Moments of parameter estimates for Chung-Lu random graph models

March 25, 2012
  |
Conference Paper
Author:
Nicholas F. Arcolano
…
Published in:
ICASSP 2012, Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, 25-30 March 2012, pp. 3961-4.
Topic:
signal processing
R&D area:
R&D group:

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
Moments of parameter estimates for Chung-Lu random graph models

Anomalous subgraph detection via sparse principal component analysis

June 28, 2011
  |
Conference Paper
Author:
Navraj Singh
…
Published in:
Proc. 2011 IEEE Statistical Signal Processing Workshop (SSP), 28-30 June 2011, pp. 485-488.
Topic:
signal processing
R&D area:
R&D group:

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
Anomalous subgraph detection via sparse principal component analysis

Subgraph detection using eigenvector L1 norms

December 6, 2010
  |
Conference Paper
Author:
Benjamin A. Miller
…
Published in:
23rd Int. Conf. on Neural Info. Process. Syst., NIPS, 6-9 December 2010, pp. 1633-41.
Topic:
signal processing
R&D area:
R&D group:

Summary

When working with network datasets, the theoretical framework of detection theory for Euclidean vector spaces no longer applies. Nevertheless, it is desirable to determine the detectability of small, anomalous graphs embedded into background networks with known statistical properties. Casting the problem of subgraph detection in a signal processing context, this article provides a framework and empirical results that elucidate a "detection theory" for graph-valued data. Its focus is the detection of anomalies in unweighted, undirected graphs through L1 properties of the eigenvectors of the graph's so-called modularity matrix. This metric is observed to have relatively low variance for certain categories of randomly-generated graphs, and to reveal the presence of an anomalous subgraph with reasonable reliability when the anomaly is not well-correlated with stronger portions of the background graph. An analysis of subgraphs in real network datasets confirms the efficacy of this approach.
READ LESS

Summary

When working with network datasets, the theoretical framework of detection theory for Euclidean vector spaces no longer applies. Nevertheless, it is desirable to determine the detectability of small, anomalous graphs embedded into background networks with known statistical properties. Casting the problem of subgraph detection in a signal processing context, this...

READ MORE
Subgraph detection using eigenvector L1 norms

Toward signal processing theory for graphs and non-Euclidean data

March 15, 2010
  |
Conference Paper
Author:
Benjamin A. Miller
…
Published in:
ICASSP 2010, IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, 15 March 2010, pp. 5415-5417.
Topic:
signal processing
R&D area:
R&D group:

Summary

Graphs are canonical examples of high-dimensional non-Euclidean data sets, and are emerging as a common data structure in many fields. While there are many algorithms to analyze such data, a signal processing theory for evaluating these techniques akin to detection and estimation in the classical Euclidean setting remains to be developed. In this paper we show the conceptual advantages gained by formulating graph analysis problems in a signal processing framework by way of a practical example: detection of a subgraph embedded in a background graph. We describe an approach based on detection theory and provide empirical results indicating that the test statistic proposed has reasonable power to detect dense subgraphs in large random graphs.
READ LESS

Summary

Graphs are canonical examples of high-dimensional non-Euclidean data sets, and are emerging as a common data structure in many fields. While there are many algorithms to analyze such data, a signal processing theory for evaluating these techniques akin to detection and estimation in the classical Euclidean setting remains to be...

READ MORE
Toward signal processing theory for graphs and non-Euclidean data

Time-varying autoregressive tests for multiscale speech analysis

September 6, 2009
  |
Conference Paper
Author:
Daniel Rudoy
…
Published in:
INTERSPEECH 2009, 10th Annual Conf. of the International Speech Communication Association, pp. 2839-2842.
Topic:
speech enhancement
R&D area:
R&D group:

Summary

In this paper we develop hypothesis tests for speech waveform nonstationarity based on time-varying autoregressive models, and demonstrate their efficacy in speech analysis tasks at both segmental and sub-segmental scales. Key to the successful synthesis of these ideas is our employment of a generalized likelihood ratio testing framework tailored to autoregressive coefficient evolutions suitable for speech. After evaluating our framework on speech-like synthetic signals, we present preliminary results for two distinct analysis tasks using speech waveform data. At the segmental level, we develop an adaptive short-time segmentation scheme and evaluate it on whispered speech recordings, while at the sub-segmental level, we address the problem of detecting the glottal flow closed phase. Results show that our hypothesis testing framework can reliably detect changes in the vocal tract parameters across multiple scales, thereby underscoring its broad applicability to speech analysis.
READ LESS

Summary

In this paper we develop hypothesis tests for speech waveform nonstationarity based on time-varying autoregressive models, and demonstrate their efficacy in speech analysis tasks at both segmental and sub-segmental scales. Key to the successful synthesis of these ideas is our employment of a generalized likelihood ratio testing framework tailored to...

READ MORE
Time-varying autoregressive tests for multiscale speech analysis

Adaptive short-time analysis-synthesis for speech enhancement

March 31, 2008
  |
Conference Paper
Author:
Prabahan Basu
…
Published in:
2008 IEEE Int. Conf. on Acoustics, Speech and Signal Processing, ICASSP, 31 March - 4 April 2008.
Topic:
speech enhancement
R&D area:
R&D group:

Summary

In this paper we propose a multiresolution short-time analysis method for speech enhancement. It is well known that fixed resolution methods such as the traditional short-time Fourier transform do not generally match the time-frequency structure of the signal being analyzed resulting in poor estimates of the speech and noise spectra required for enhancement. This can lead to the reduction of quality in the enhanced signal through the introduction of artifacts such as musical noise. To counter these limitations, we propose an adaptive short-time analysis-synthesis scheme for speech enhancement in which the adaptation is based on a measure of local time-frequency concentration. Synthesis is made possible through a modified overlap-add procedure. Empirical results using voiced speech indicate a clear improvement over a fixed time-frequency resolution enhancement scheme both in terms of mean-square error and as indicated by informal listening tests.
READ LESS

Summary

In this paper we propose a multiresolution short-time analysis method for speech enhancement. It is well known that fixed resolution methods such as the traditional short-time Fourier transform do not generally match the time-frequency structure of the signal being analyzed resulting in poor estimates of the speech and noise spectra...

READ MORE
Adaptive short-time analysis-synthesis for speech enhancement
1-9 of 9