Graph Translation

See this page in:

Study of the graph translation using the GraSP Matlab® toolbox available on Github.

Graph Translation example

We show here how the graph translation is constructed and how it compares to two different time shift like operators, namely the generalized translations and the graph shift.

Example graph

We use a graph of \(100\) vertices randomly drawn in a 2D square of size 10x10 using the uniform distribution.

g = grasp_plane_rnd(100);
g.show_graph_options.color_map = flipud(colormap('hot'));
g.show_graph_options.show_colorbar = true;
grasp_show_graph(gca, g, 'show_edges', false, 'show_colorbar', false);

Add edges between vertices at distance less than \(3\). Weight the edges by a Gaussian kernel \(a_{ij}=exp(-\frac{d(i,j)^2}{2\sigma^2})\) with \(\sigma^2=1/1.5\). Note that grasp_adjacency_thresh thresholds the weights on the edges, and not the distances.

g.A = grasp_adjacency_gaussian(g, 1/1.5);
g.A = grasp_adjacency_thresh(g, exp(-3 * 3 ^ 2));
g.A_layout = 0;
grasp_show_graph(gca, g, 'show_edges', true, 'show_colorbar', false);

Create the Fourier transform.

g = grasp_eigendecomposition(g);

Create the translation operators.

[~, TG] = grasp_translation(g);
T1 = grasp_generalized_translation(g, 1);
GS = g.A;

Example graph signal: delta

Translate a delta signal to study the impulse response.

d10 = grasp_delta(g, 10);
grasp_show_graph(gca, g, 'node_values', abs(d10), 'value_scale', [0 2]);
title('|\delta_{10}|');

grasp_show_graph(gca, g, 'node_values', abs(TG * d10), 'value_scale', [0 1]);
title('|T_g \delta_{10}|');

Magnitude of the output of the graph translation applied to a delta signal

grasp_show_graph(gca, g, 'node_values', abs(T1 * d10), 'value_scale', [0 max(abs(T1 * d10))], 'highlight_nodes', 1);
title('|T_1 \delta_{10}|');

Magnitude of the output of a generalized translation applied to a delta signal

grasp_show_graph(gca, g, 'node_values', abs(GS * d10), 'value_scale', [0 1]);
title('|A \delta_{10}|');

Magnitude of the output of the graph shift applied to a delta signal

Iterate the graph translation and the graph shift. We observe the saturation of the color scale for the graph shift due to the non-isometry of this operator.

kmax = 100;
translated_gt(100, kmax + 1) = 0;
translated_gs(100, kmax + 1) = 0;
for k = 0:kmax
    translated_gt(:, k + 1) = TG ^ k * d10;
    translated_gs(:, k + 1) = GS ^ k * d10;
end

mod_options = struct('value_scale', [0 1]);
titles_mod = arrayfun(@(k) ['$|T_g^{' int2str(k) '} d_{10}|$'], 0:kmax, 'UniformOutput', false);
grasp_generate_gif(gcf, 'html/tg_d10_mod_anim.gif', g, abs(translated_gt), titles_mod, 24, mod_options);

Animation of successive application of the graph translation to a delta: magnitude

ang_options = struct('value_scale', [-pi pi], 'color_map', 'hsv');
titles_ang = arrayfun(@(k) ['$\angle(T_g^{' int2str(k) '} d_{10})$'], 0:kmax, 'UniformOutput', false);
grasp_generate_gif(gcf, 'html/tg_d10_ang_anim.gif', g, angle(translated_gt), titles_ang, 24, ang_options);

Animation of successive application of the graph translation to a delta: angle

gs_options = struct('value_scale', [0 1]);
titles_gs = arrayfun(@(k) ['$|A^{' int2str(k) '} d_{10}|$'], 0:kmax, 'UniformOutput', false);
grasp_generate_gif(gcf, 'html/gs_d10_anim.gif', g, abs(translated_gs), titles_gs, 24, gs_options);

Animation of successive application of the graph shift to a delta: magnitude

Normalized output for the graph shift

for k = 0:kmax
    translated_gs(:, k + 1) = translated_gs(:, k + 1) / norm(translated_gs(:, k + 1));
end
titles_gs = arrayfun(@(k) ['$|A^{' int2str(k) '} d_{10}| / ||A^{' int2str(k) '} d_{10}||_2$'], 0:kmax, 'UniformOutput', false);
cla(gca);
grasp_generate_gif(gcf, 'html/gs_d10_norm_anim.gif', g, abs(translated_gs), titles_gs, 24, gs_options);

Animation of successive application of the graph shift to a delta: magnitude, l2-normalized

Example graph signal: heat kernel

As defined in [Shuman, Ricaud, Vandergheynst 2015], \(X\) is a heat kernel defined as \(\widehat{X}(l)=Cexp(-10\lambda_l)\), with \(\|X\|_2 = 1\).

cla(gca);
X = grasp_heat_kernel(g, 10);
X = X / norm(X);
grasp_show_graph(gca, g, 'node_values', abs(X));
title('|X|');

Translate \(X\).

grasp_show_graph(gca, g, 'node_values', abs(TG * X), 'value_scale', [0 max(abs(TG * X))]);
title('|T_g X|');

Magnitude of the output of the graph translation applied to a heat kernel

grasp_show_graph(gca, g, 'node_values', abs(T1 * X), 'value_scale', [0 max(abs(T1 * X))], 'highlight_nodes', 1);
title('|T_1 X|');

Magnitude of the output of a generalized translation applied to a heat kernel

grasp_show_graph(gca, g, 'node_values', abs(GS * X), 'value_scale', [0 max(abs(GS * X))]);
title('|A X|');

Magnitude of the output of the graph shift applied to a heat kernel

Iterate the graph translation and the graph shift on the signal \(X\). The output of the graph shift is normalised.

kmax = 100;
translated_gt(100, kmax + 1) = 0;
translated_gs(100, kmax + 1) = 0;
for k = 0:kmax
    translated_gt(:, k + 1) = TG ^ k * X;
    tmp = GS ^ k * X;
    translated_gs(:, k + 1) = tmp / norm(tmp);
end
mod_options = struct('value_scale', [0 max(abs(translated_gt(:)))]);
titles_mod = arrayfun(@(k) ['$|T_g^{' int2str(k) '} X|$'], 0:kmax, 'UniformOutput', false);
grasp_generate_gif(gcf, 'html/tg_X_mod_anim.gif', g, abs(translated_gt), titles_mod, 24, mod_options);

Animation of successive application of the graph translation to a heat kernel: magnitude

ang_options = struct('value_scale', [-pi pi], 'color_map', 'hsv');
titles_ang = arrayfun(@(k) ['$\angle(T_g^{' int2str(k) '} X)$'], 0:kmax, 'UniformOutput', false);
grasp_generate_gif(gcf, 'html/tg_X_ang_anim.gif', g, angle(translated_gt), titles_ang, 24, ang_options);

Animation of successive application of the graph translation to a heat kernel: angle

gs_options = struct('value_scale', [0 max(abs(translated_gs(:)))]);
titles_gs = arrayfun(@(k) ['$|A^{' int2str(k) '} X| / ||A^{' int2str(k) '} X||_2$'], 0:kmax, 'UniformOutput', false);
grasp_generate_gif(gcf, 'html/gs_X_norm_anim.gif', g, abs(translated_gs), titles_gs, 24, gs_options);

Animation of successive application of the graph shift to a heat kernel: magnitude, l2-normalized