In youngser/TwoTruth: On a `Two Truths` Phenomenon in Spectral Graph Clustering

library(knitr)
knitr::opts_chunk$set(echo=TRUE, eval=FALSE,warning=FALSE)

opts_knit$set(aliases=c(h='fig.height', w='fig.width', cap='fig.cap', scap='fig.scap'))                                                                               
opts_knit$set(eval.after = c('fig.cap','fig.scap'))                                                                            
knit_hooks$set(document = function(x) {                                                                                        
          gsub('(\\\\end\\{knitrout\\}[\n]+)', '\\1\\\\noindent ', x)                                                                  
          })

 fn = local({
   i = 0
   function(x) {
     i <<- i + 1
#     paste('Figure ', i, ': ', x, sep = '')
     paste('', '', x, sep = '')
   }
 })

Department of Applied Mathematics and Statistics
Center for Imaging Science
Department of Biomedical Engineering
Human Language Technology Center of Excellence
Johns Hopkins University
and
University of Massachusetts, Amherst, MA
and
Institute for Defense Analyses, Center for Computing Science

---

Carey E. Priebe, Youngser Park, Joshua T. Vogelstein, John M. Conroy, Vince Lyzinskic, Minh Tang, Avanti Athreya, Joshua Cape, and Eric Bridgeford, "On a 'Two Truths' Phenomenon in Spectral Graph Clustering," Proceedings of National Academy of Science, submitted, 2018.

Abstract

Clustering is concerned with coherently grouping observations without any explicit concept of true groupings. Spectral graph clustering -- clustering the vertices of a graph based on their spectral embedding -- is commonly approached via K-means (or, more generally, Gaussian mixture model) clustering composed with either Laplacian or Adjacency spectral embedding (LSE or ASE). Recent theoretical results provide new understanding of the problem and solutions, and lead us to a 'Two Truths' LSE vs. ASE spectral graph clustering phenomenon convincingly illustrated here via a diffusion MRI connectome data set: the different embedding methods yield different clustering results, with LSE capturing left hemisphere/right hemisphere affinity structure and ASE capturing gray matter/white matter core-periphery structure.

Keywords: Spectral Embedding, Spectral Clustering, Graph, Network, Connectome

Fig. 1. Illustration of the Two Truths phenomenon.

Supplemental Information (SI)

Data

Here we make available the connectome data used for our illustration: $m = 114$ graphs on $n \approx 40,000$ vertices, and for each graph every vertex has a {Left,Right} label and a {Gray,White} label.

NB: The original diffusion MRI connectomes are symmetric, hollow, and weighted. This is not meant to be a finding of neurscientific significance; rather, this is an illustration of the 'Two Truths' phenomenon. As such, we consider the largest connected component of binarized versions of the connectomes.

R Package

To run the experiemnts in the paper, please follow these steps.
(NB: All the codes are in the demo folder at github.)

require(devtools)
devtools::install_github("youngser/TwoTruth")
# WARNING: may take a while to install all the required packages

Demos

To reproduce most of the Figures and Tables in the manuscript, please follow these steps:

library(TwoTruth)

demo(doFig5)
demo(doFig6) 
demo(doFig7) 

Software and Hardware Information

library(help='TwoTruth')
sessionInfo()

---

prepared by [e-mail] on r date()

youngser/TwoTruth documentation built on May 25, 2019, 7:23 p.m.