Publications

Refine Results

(Filters Applied) Clear All

Temporal and multi-source fusion for detection of innovation in collaboration networks

Published in:
Proc. of the 18th Int. Conf. On Information Fusion, 6-9 July 2015.

Summary

A common problem in network analysis is detecting small subgraphs of interest within a large background graph. This includes multi-source fusion scenarios where data from several modalities must be integrated to form the network. This paper presents an application of novel techniques leveraging the signal processing for graphs algorithmic framework, to well-studied collaboration networks in the field of evolutionary biology. Our multi-disciplinary approach allows us to leverage case studies of transformative periods in this scientific field as truth. We build on previous work by optimizing the temporal integration filters with respect to truth data using a tensor decomposition method that maximizes the spectral norm of the integrated subgraph's adjacency matrix. We also demonstrate that we can mitigate data corruption via fusion of different data sources, demonstrating the power of this analysis framework for incomplete and corrupted data.
READ LESS

Summary

A common problem in network analysis is detecting small subgraphs of interest within a large background graph. This includes multi-source fusion scenarios where data from several modalities must be integrated to form the network. This paper presents an application of novel techniques leveraging the signal processing for graphs algorithmic framework...

READ MORE

Planted clique detection below the noise floor using low-rank sparse PCA

Published in:
Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, ICASSP, 19-24 April 2015.

Summary

Detection of clusters and communities in graphs is useful in a wide range of applications. In this paper we investigate the problem of detecting a clique embedded in a random graph. Recent results have demonstrated a sharp detectability threshold for a simple algorithm based on principal component analysis (PCA). Sparse PCA of the graph's modularity matrix can successfully discover clique locations where PCA-based detection methods fail. In this paper, we demonstrate that applying sparse PCA to low-rank approximations of the modularity matrix is a viable solution to the planted clique problem that enables detection of small planted cliques in graphs where running the standard semidefinite program for sparse PCA is not possible.
READ LESS

Summary

Detection of clusters and communities in graphs is useful in a wide range of applications. In this paper we investigate the problem of detecting a clique embedded in a random graph. Recent results have demonstrated a sharp detectability threshold for a simple algorithm based on principal component analysis (PCA). Sparse...

READ MORE

Spectral anomaly detection in very large graphs: Models, noise, and computational complexity(92.92 KB)

Published in:
Proceedings of Seminar 14461: High-performance Graph Algorithms and Applications in Computational Science, Wadern, Germany

Summary

Anomaly detection in massive networks has numerous theoretical and computational challenges, especially as the behavior to be detected becomes small in comparison to the larger network. This presentation focuses on recent results in three key technical areas, specifically geared toward spectral methods for detection.
READ LESS

Summary

Anomaly detection in massive networks has numerous theoretical and computational challenges, especially as the behavior to be detected becomes small in comparison to the larger network. This presentation focuses on recent results in three key technical areas, specifically geared toward spectral methods for detection.

READ MORE

Bayesian discovery of threat networks

Published in:
IEEE Trans. Signal Process., Vol. 62, No. 20, 15 October 2014, pp. 5324-38.

Summary

A novel unified Bayesian framework for network detection is developed, under which a detection algorithm is derived based on random walks on graphs. The algorithm detects threat networks using partial observations of their activity, and is proved to be optimum in the Neyman-Pearson sense. The algorithm is defined by a graph, at least one observation, and a diffusion model for threat. A link to well-known spectral detection methods is provided, and the equivalence of the random walk and harmonic solutions to the Bayesian formulation is proven. A general diffusion model is introduced that utilizes spatio-temporal relationships between vertices, and is used for a specific space-time formulation that leads to significant performance improvements on coordinated covert networks. This performance is demonstrated using a new hybrid mixed-membership blockmodel introduced to simulate random covert networks with realistic properties.
READ LESS

Summary

A novel unified Bayesian framework for network detection is developed, under which a detection algorithm is derived based on random walks on graphs. The algorithm detects threat networks using partial observations of their activity, and is proved to be optimum in the Neyman-Pearson sense. The algorithm is defined by a...

READ MORE

Sparse matrix partitioning for parallel eigenanalysis of large static and dynamic graphs

Published in:
HPEC 2014: IEEE Conf. on High Performance Extreme Computing, 9-11 September 2014.

Summary

Numerous applications focus on the analysis of entities and the connections between them, and such data are naturally represented as graphs. In particular, the detection of a small subset of vertices with anomalous coordinated connectivity is of broad interest, for problems such as detecting strange traffic in a computer network or unknown communities in a social network. These problems become more difficult as the background graph grows larger and noisier and the coordination patterns become more subtle. In this paper, we discuss the computational challenges of a statistical framework designed to address this cross-mission challenge. The statistical framework is based on spectral analysis of the graph data, and three partitioning methods are evaluated for computing the principal eigenvector of the graph's residuals matrix. While a standard one-dimensional partitioning technique enables this computation for up to four billion vertices, the communication overhead prevents this method from being used for even larger graphs. Recent two-dimensional partitioning methods are shown to have much more favorable scaling properties. A data-dependent partitioning method, which has the best scaling performance, is also shown to improve computation time even as a graph changes over time, allowing amortization of the upfront cost.
READ LESS

Summary

Numerous applications focus on the analysis of entities and the connections between them, and such data are naturally represented as graphs. In particular, the detection of a small subset of vertices with anomalous coordinated connectivity is of broad interest, for problems such as detecting strange traffic in a computer network...

READ MORE

Spectral subgraph detection with corrupt observations

Published in:
Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, ICASSP, 4-9 May 2014.

Summary

Recent work on signal detection in graph-based data focuses on classical detection when the signal and noise are both in the form of discrete entities and their relationships. In practice, the relationships of interest may not be directly observable, or may be observed through a noisy mechanism. The effects of imperfect observations add another layer of difficulty to the detection problem, beyond the effects of typical random fluctuations in the background graph. This paper analyzes the impact on detection performance of several error and corruption mechanisms for graph data. In relatively simple scenarios, the change in signal and noise power is analyzed, and this is demonstrated empirically in more complicated models. It is shown that, with enough side information, it is possible to fully recover performance equivalent to working with uncorrupted data using a Bayesian approach, and a simpler cost-optimization approach is shown to provide a substantial benefit as well.
READ LESS

Summary

Recent work on signal detection in graph-based data focuses on classical detection when the signal and noise are both in the form of discrete entities and their relationships. In practice, the relationships of interest may not be directly observable, or may be observed through a noisy mechanism. The effects of...

READ MORE

Velocity estimation improvements for the ASR-9 Weather Systems Processor

Published in:
American Meteorological Society Annual Meeting, 2-6 February 2014.

Summary

The Airport Surveillance Radar (ASR-9) is a rapid-scanning terminal aircraft detection system deployed at airports around the United States. To provide cost-effective wind shear detection capability at medium-density airports, the Weather Systems Processor (WSP) was developed and added on to the ASR-9 at 35 sites. The WSP on the ASR-9 is capable of utilizing dual fan-beam estimates of reflectivity and velocity in order to detect low-level features such as gust fronts, wind shear, and microbursts, which would normally be best detectable by a low-scanning pencil beam radar. An upgrade to the ASR-9 WSP, which is currently ongoing, allows for additional computational complexity in the front-end digital signal processing algorithms compared to previous iterations of the system. This paper will explore ideas for improving velocity estimates, including low-level dual beam weight estimation, de-aliasing, and noise reduction. A discussion of the unique challenges afforded by the ASR-9's block-stagger pulse repetition time is presented, along with thoughts on how to overcome limitations which arise from rapid-scanning and the inherent lack of pulses available for coherent averaging.
READ LESS

Summary

The Airport Surveillance Radar (ASR-9) is a rapid-scanning terminal aircraft detection system deployed at airports around the United States. To provide cost-effective wind shear detection capability at medium-density airports, the Weather Systems Processor (WSP) was developed and added on to the ASR-9 at 35 sites. The WSP on the ASR-9...

READ MORE

A least mean squares approach of iterative array calibration for scalable digital phased array radar panels

Published in:
2013 IEEE Int. Symp. On Phased Array Systems and Technology, 15-18 October 2013.
Topic:
R&D group:

Summary

This paper describes a semiautonomous approach to calibrate a phased array system, with particular use on an S-band aperture that is being developed at MIT Lincoln Laboratory. Each element of the array is controlled by an independent digital phase shifter, whose control signal may be uniquely defined. As active electronically steerable arrays (AESAs) continually evolve towards mostly digital paradigms that will support real-time computing, as opposed to look-up table approaches, then adaptive calibration approaches may be pursued for maximum AESA performance. This calibration work is being completed as one component of Lincoln Laboratory's effort within the multifunction phased array radar (MPAR) initiative.
READ LESS

Summary

This paper describes a semiautonomous approach to calibrate a phased array system, with particular use on an S-band aperture that is being developed at MIT Lincoln Laboratory. Each element of the array is controlled by an independent digital phase shifter, whose control signal may be uniquely defined. As active electronically...

READ MORE

A method for improved cross-pol isolation based on the use of auxiliary elements

Published in:
2013 IEEE Int. Symp. On Phased Array Systems and Technology, 15-18 October 2013.

Summary

This paper describes a method to answer the following questions: can several of the elements of a phased array be employed as auxiliary (AUX) elements and how can the phase of each be adjusted so that the (1) cross-polarization (cross-pol) isolation is minimized to 40 dB, (2) the sidelobe levels of the main lobe are minimally impacted, and (3) the width and height of the main lobe are minimally impacted? This calibration work is being completed as one component of Lincoln Laboratory's effort within the multifunction phased array radar (MPAR) initiative. Devoting a few of the elements to serve as the AUX channels to specifically operate to mitigate the effects of the cross-pol influence, the distributed sidelobe levels will not suffer much impact; yet, the impact of the AUX elements will have deepened the cross-pol isolation at the peak of the co-polar beam can occur because the AUX elements can achieve a high degree of narrowband angular resolution.
READ LESS

Summary

This paper describes a method to answer the following questions: can several of the elements of a phased array be employed as auxiliary (AUX) elements and how can the phase of each be adjusted so that the (1) cross-polarization (cross-pol) isolation is minimized to 40 dB, (2) the sidelobe levels...

READ MORE

Very large graphs for information extraction (VLG) - summary of first-year proof-of-concept study

Summary

In numerous application domains relevant to the Department of Defense and the Intelligence Community, data of interest take the form of entities and the relationships between them, and these data are commonly represented as graphs. Under the Very Large Graphs for Information Extraction effort--a one-year proof-of-concept study--MIT LL developed novel techniques for anomalous subgraph detection, building on tools in the signal processing research literature. This report documents the technical results of this effort. Two datasets--a snapshot of Thompson Reuters? Web of Science database and a stream of web proxy logs--were parsed, and graphs were constructed from the raw data. From the phenomena in these datasets, several algorithms were developed to model the dynamic graph behavior, including a preferential attachment mechanism with memory, a streaming filter to model a graph as a weighted average of its past connections, and a generalized linear model for graphs where connection probabilities are determined by additional side information or metadata. A set of metrics was also constructed to facilitate comparison of techniques. The study culminated in a demonstration of the algorithms on the datasets of interest, in addition to simulated data. Performance in terms of detection, estimation, and computational burden was measured according to the metrics. Among the highlights of this demonstration were the detection of emerging coauthor clusters in the Web of Science data, detection of botnet activity in the web proxy data after 15 minutes (which took 10 days to detect using state-of-the-practice techniques), and demonstration of the core algorithm on a simulated 1-billion-vertex graph using a commodity computing cluster.
READ LESS

Summary

In numerous application domains relevant to the Department of Defense and the Intelligence Community, data of interest take the form of entities and the relationships between them, and these data are commonly represented as graphs. Under the Very Large Graphs for Information Extraction effort--a one-year proof-of-concept study--MIT LL developed novel...

READ MORE