Graph Translation

See this page in: fr
 

Study of the graph translation using the GraSP Matlab® toolbox available on Inria GForge and 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);
Example Graph: Vertices

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);
Example Graph: Edges

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}|');
Delta signal
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|');
Heat kernel: magnitudes

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