Learning Graphs from Data via Spectral Constraints

Block coordinate descent estimators to learn k-component, bipartite, and k-component bipartite graphs from data by imposing spectral constraints on the eigenvalues and eigenvectors of the Laplacian and adjacency matrices. Those estimators leverages spectral properties of the graphical models as a prior information, which turn out to play key roles in unsupervised machine learning tasks such as clustering and community detection. This package is based on the paper "A Unified Framework for Structured Graph Learning via Spectral Constraints" by S. Kumar et al (2019) .

spectralGraphTopology provides estimators to learn k-component, bipartite, and k-component bipartite graphs from data by imposing spectral constraints on the eigenvalues and eigenvectors of the Laplacian and adjacency matrices. Those estimators leverages spectral properties of the graphical models as a prior information, which turn out to play key roles in unsupervised machine learning tasks such as community detection.

From inside an R session, type:

Alternatively, you can install the development version from GitHub:

$ git clone https://github.com/dppalomar/spectralGraphTopology.git
$ cd spectralGraphTopology
$ make build && make install

Microsoft Windows

On MS Windows environments, make sure to install the most recent version of Rtools.

Usage: clustering

We illustrate the usage of the package with simulated data, as follows:

library(spectralGraphTopology)
library(clusterSim)
library(igraph)
set.seed(42)
 
# generate graph and data
n <- 50  # number of nodes per cluster
twomoon <- clusterSim::shapes.two.moon(n)  # generate datapoints
k <- 2  # number of components
 
# estimate underlying graph
S <- crossprod(t(twomoon$data))
graph <- learn_k_component_graph(S, k = k, beta = .5, verbose = FALSE, abstol = 1e-3)
 
# plot
# build network
net <- igraph::graph_from_adjacency_matrix(graph$Adjacency, mode = "undirected", weighted = TRUE)
# colorify nodes and edges
colors <- c("#706FD3", "#FF5252")
V(net)$cluster <- twomoon$clusters
E(net)$color <- apply(as.data.frame(get.edgelist(net)), 1,
                      function(x) ifelse(V(net)$cluster[x[1]] == V(net)$cluster[x[2]],
                                        colors[V(net)$cluster[x[1]]], '#000000'))
V(net)$color <- colors[twomoon$clusters]
# plot nodes
plot(net, layout = twomoon$data, vertex.label = NA, vertex.size = 3)

For more examples, check out our gallery.

Contributing

We welcome all sorts of contributions. Please feel free to open an issue to report a bug or discuss a feature request.

Citation

If you made use of this software please consider citing:

S. Kumar, J. Ying, J. V. de Miranda Cardoso, and D. P. Palomar (2019). A unified framework for structured graph learning via spectral constraints. https://arxiv.org/abs/1904.09792

In case you made use of the function cluster_k_component_graph, consider citing:

N., Feiping, W., Xiaoqian, J., Michael I., and H., Heng. (2016). The Constrained Laplacian Rank Algorithm for Graph-based Clustering, AAAI'16. http://dl.acm.org/citation.cfm?id=3016100.3016174