Modern resting-state functional magnetic resonance imaging (rs-fMRI) provides a wealth of information about the inherent functional connectivity of the human brain. However, understanding the role of negative correlations and the nonlinear topology of rs-fMRI remains a challenge. To address these challenges, we propose a novel graph embedding technique, phase angle spatial embedding (PhASE), to study the “intrinsic geometry” of the functional connectome. PhASE both incorporates negative correlations as well as reformulates the connectome modularity problem as a kernel two-sample test, using a kernel method that induces a maximum mean discrepancy (MMD) in a reproducing kernel Hilbert space (RKHS). By solving a graph partition that maximizes this MMD, PhASE identifies the most functionally distinct brain modules. As a test case, we analyzed a public rs-fMRI dataset to compare male and female connectomes using PhASE and minimum spanning tree inferential statistics. These results show statistically significant differences between male and female resting-state brain networks, demonstrating PhASE to be a robust tool for connectome analysis.