forked from convexfi/spectralGraphTopology
/
README.Rmd
129 lines (101 loc) · 6.98 KB
/
README.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
---
title: "spectralGraphTopology"
output:
md_document:
variant: markdown_github
---
<!-- README.md is generated from README.Rmd. Please edit that file -->
```{r, echo = FALSE}
library(knitr)
opts_chunk$set(
collapse = TRUE,
comment = "#>",
fig.path = "man/figures/README-",
fig.align = "center",
fig.retina = 2,
out.width = "75%",
dpi = 96
)
knit_hooks$set(pngquant = hook_pngquant)
```
# spectralGraphTopology
[](https://app.codecov.io/gh/mirca/spectralGraphTopology)
[](https://cran.r-project.org/package=spectralGraphTopology)
[](https://cran.r-project.org/package=spectralGraphTopology)
[](http://www.rcpp.org/)
<a href="https://mirca.github.io/spectralGraphTopology/"><img style="float: right;" width="250" src="./man/figures//circles3_reduced.gif" align="right" /></a>
**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 leverage 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.
**Documentation**: [**https://mirca.github.io/spectralGraphTopology**](https://mirca.github.io/spectralGraphTopology/).
## Installation
From inside an R session, type:
```{r, eval = FALSE}
> install.packages("spectralGraphTopology")
```
Alternatively, you can install the development version from GitHub:
```{r, eval = FALSE}
> devtools::install_github("dppalomar/spectralGraphTopology")
```
#### Microsoft Windows
On MS Windows environments, make sure to install the most recent version of ``Rtools``.
#### macOS
**spectralGraphTopology** depends on [`RcppArmadillo`](https://github.com/RcppCore/RcppArmadillo)
which requires [`gfortran`](https://CRAN.R-project.org/bin/macosx/tools/).
## Usage: clustering
We illustrate the usage of the package with simulated data, as follows:
```{r plot_k_component, message=FALSE}
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 data points
k <- 2 # number of components
# estimate underlying graph
S <- crossprod(t(twomoon$data))
graph <- learn_k_component_graph(S, k = k, beta = .25, 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)
```
## 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:
- J. V. de Miranda Cardoso, D. P. Palomar (2019). spectralGraphTopology: Learning Graphs from
Data via Spectral Constraints. <https://CRAN.R-project.org/package=spectralGraphTopology>
- S. Kumar, J. Ying, J. V. de Miranda Cardoso, and D. P. Palomar (2020). [A unified framework
for structured graph learning via spectral constraints](https://www.jmlr.org/papers/v21/19-276.html). Journal of Machine Learning Research (21), pages 1-60.
- S. Kumar, J. Ying, J. V. de Miranda Cardoso, D. P. Palomar (2019). [Structured graph learning via Laplacian spectral constraints](https://papers.nips.cc/paper/9339-structured-graph-learning-via-laplacian-spectral-constraints.pdf). Advances in Neural Information Processing Systems.
In addition, consider citing the following bibliography according to their
implementation:
| **function** | **reference** |
|-----------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| `cluster_k_component_graph` | N., Feiping, W., Xiaoqian, J., Michael I., and H., Heng. (2016). [The Constrained Laplacian Rank Algorithm for Graph-based Clustering](https://dl.acm.org/doi/10.5555/3016100.3016174), AAAI'16. |
| `learn_laplacian_gle_mm` | Licheng Zhao, Yiwei Wang, Sandeep Kumar, and Daniel P. Palomar, [Optimization Algorithms for Graph Laplacian Estimation via ADMM and MM](https://palomar.home.ece.ust.hk/papers/2019/ZhaoWangKumarPalomar-TSP2019.pdf), IEEE Trans. on Signal Processing, vol. 67, no. 16, pp. 4231-4244, Aug. 2019 |
| `learn_laplacian_gle_admm` | Licheng Zhao, Yiwei Wang, Sandeep Kumar, and Daniel P. Palomar, [Optimization Algorithms for Graph Laplacian Estimation via ADMM and MM](https://palomar.home.ece.ust.hk/papers/2019/ZhaoWangKumarPalomar-TSP2019.pdf), IEEE Trans. on Signal Processing, vol. 67, no. 16, pp. 4231-4244, Aug. 2019 |
| `learn_combinatorial_graph_laplacian` | H. E. Egilmez, E. Pavez and A. Ortega, [Graph learning from data under Laplacian and structural constraints](https://ieeexplore.ieee.org/document/7979524), Journal of Selected Topics in Signal Processing, vol. 11, no. 6, pp. 825-841, Sept. 2017 |
## Links
Package: [CRAN](https://CRAN.R-project.org/package=spectralGraphTopology) and
[GitHub](https://github.com/dppalomar/spectralGraphTopology)
README file: [GitHub-readme](https://github.com/dppalomar/spectralGraphTopology/blob/master/README.md)
Vignette: [GitHub-html-vignette](https://raw.githack.com/dppalomar/spectralGraphTopology/master/vignettes/SpectralGraphTopology.html),
[CRAN-html-vignette](https://cran.r-project.org/package=spectralGraphTopology/vignettes/SpectralGraphTopology.html),
[NeurIPS'19 Promotional slides](https://docs.google.com/viewer?url=https://github.com/dppalomar/spectralGraphTopology/raw/master/vignettes/NeurIPS19-promo-slides.pdf),
[NeurIPS'19 Promotional video](https://www.youtube.com/watch?v=klAqFvyQx7k)