Anomalous subgraph detection via Sparse Principal Component Analysis

Navraj Singh, Benjamin A. Miller, Nadya T. Bliss, Patrick J. Wolfe

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations


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.

Original languageEnglish (US)
Title of host publication2011 IEEE Statistical Signal Processing Workshop, SSP 2011
Number of pages4
StatePublished - 2011
Externally publishedYes
Event2011 IEEE Statistical Signal Processing Workshop, SSP 2011 - Nice, France
Duration: Jun 28 2011Jun 30 2011

Publication series

NameIEEE Workshop on Statistical Signal Processing Proceedings


Other2011 IEEE Statistical Signal Processing Workshop, SSP 2011


  • Anomaly detection
  • community detection
  • graph analysis
  • semidefinite programming
  • sparse principal component analysis

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Applied Mathematics
  • Signal Processing
  • Computer Science Applications


Dive into the research topics of 'Anomalous subgraph detection via Sparse Principal Component Analysis'. Together they form a unique fingerprint.

Cite this