This is where navigation should be.


GSP_LEARN_GRAPH_L2_DEGREES - Learn graph from pairwise distances using l2 prior on nodes degrees

Usage

[W, stat] = gsp_learn_graph_l2_degrees(Z, a)
[W, stat] = gsp_learn_graph_l2_degrees(Z, a, params)

Description

Inputs:
Z : Matrix with (squared) pairwise distances of nodes a : ||L||_F^2 prior constant (bigger a -> more dense W) params : Optional parameters
Outputs:
W : Weighted adjacency matrix stat : Optional output statistics (adds small overhead)

'W = gsp_learn_graph_l2_degrees(Z, a, params)' computes a weighted adjacency matrix \(W\) from squared pairwise distances in \(Z\), using the smoothness assumption that \(\text{trace}(X^TLX)\) is small, where \(X\) is the data (columns) changing smoothly from node to node on the graph and \(L = D-W\) is the combinatorial graph Laplacian.

Alternatively, Z can contain other types of distances and use the smoothness assumption that

\begin{equation*} \sum_i\sum_j W_{ij}Z_{ij} \end{equation*}

is small.

The minimization problem solved is

\begin{equation*} \min_W \sum_i\sum_j W_{ij}Z_{ij} +\frac{\alpha}{2}\|W\|_F^2 +\frac{\alpha}{2}\|W1\|_2^2 s.t. \|W\|=n \end{equation*}

subject to \(W\) being a valid weighted adjacency matrix (non-negative, symmetric, with zero diagonal). Note that

\begin{equation*} \|W\|_F^2 + \|W1\|_2^2 = \|L\|_F^2 \end{equation*}

The algorithm used is forward-backward-forward (FBF) based primal dual optimization (see references).

Example:

G = gsp_sensor(256);
f1 = @(x,y) sin((2-x-y).^2);
f2 = @(x,y) cos((x+y).^2);
f3 = @(x,y) (x-.5).^2 + (y-.5).^3 + x - y;
f4 = @(x,y) sin(3*((x-.5).^2+(y-.5).^2));
X = [f1(G.coords(:,1), G.coords(:,2)), f2(G.coords(:,1), G.coords(:,2)), f3(G.coords(:,1), G.coords(:,2)), f4(G.coords(:,1), G.coords(:,2))];
figure; subplot(2,2,1); gsp_plot_signal(G, X(:,1)); title('1st smooth signal');
subplot(2,2,2); gsp_plot_signal(G, X(:,2)); title('2nd smooth signal');
subplot(2,2,3); gsp_plot_signal(G, X(:,3)); title('3rd smooth signal');
subplot(2,2,4); gsp_plot_signal(G, X(:,4)); title('4th smooth signal');
Z = gsp_distanz(X').^2;
[W] = gsp_learn_graph_l2_degrees(Z*25, 1);
W(W<1e-5) = 0;
G2 = gsp_update_weights(G, W);
figure; gsp_plot_graph(G2); title('Graph with edges learned from above 4 signals');

This code produces the following output:

# iters:  200. Rel primal: 3.4923e-03 Rel dual: 4.6112e-04   1.661e+03
Time needed is 0.159397 seconds
gsp_learn_graph_l2_degrees_1_1.png gsp_learn_graph_l2_degrees_1_2.png

Additional parameters

  • params.W_init : Initialization point. default: zeros(size(Z))
  • verbosity : Above 1 adds a small overhead. Default: 1
  • maxit : Maximum number of iterations. Default: 1000
  • tol : Tolerance for stopping criterion. Default: 1e-5
  • step_size : Step size from the interval (0,1). Default: 0.5
  • fix_zeros : Fix a set of edges to zero (true/false)
  • edge_mask : Mask indicating the non zero edges if "fix_zeros"

The stopping criterion is whether both relative primal and dual distance between two iterations are below a given tolerance.

To set the step size use the following rule of thumb: Set it so that relative change of primal and dual converge with similar rates (use verbosity > 1).

References:

V. Kalofolias. How to learn a graph from smooth signals. Technical report, AISTATS 2016: proceedings at Journal of Machine Learning Research (JMLR)., 2016.

N. Komodakis and J.-C. Pesquet. Playing with duality: An overview of recent primal? dual approaches for solving large-scale optimization problems. Signal Processing Magazine, IEEE, 32(6):31--54, 2015.

V. Kalofolias and N. Perraudin. Large Scale Graph Learning from Smooth Signals. arXiv preprint arXiv:1710.05654, 2017. [ .pdf ]