Md. Asif Uddin
    I.14.X01

    A graph convolution on a path of three

    numeric▲△△

    For the path 11–22–33, write A^\hat{\mat A} of (I.14.5) and apply it to the signal (1,0,0)(1,0,0), a unit at one end. Where has the signal gone after one layer?

    Hint

    With self-loops the degrees are 22, 33 and 22, and A^vu=1/d~vd~u\hat A_{vu}=1/\sqrt{\tilde d_v\tilde d_u} for neighbours and for u=vu=v.

    Solution

    The matrix is

    A^=[1216016131601612].\hat{\mat A}=\begin{bmatrix} \tfrac12&\tfrac1{\sqrt6}&0\\[2pt] \tfrac1{\sqrt6}&\tfrac13&\tfrac1{\sqrt6}\\[2pt] 0&\tfrac1{\sqrt6}&\tfrac12 \end{bmatrix}.

    Its first column is the output for the input (1,0,0)(1,0,0): (0.5,  0.408248,  0)(0.5,\;0.408248,\;0). Half of the unit stays at node 11, part moves to its neighbour, and node 33, two hops away, receives nothing. A second layer would reach it, as I.14.T2 says.

    The output’s entries add to 0.9082480.908248, not 11: the symmetric normalisation does not preserve sums. It preserves the vector of square roots of degrees, (2,3,2)(\sqrt2,\sqrt3,\sqrt2), which it maps to itself.

    Draws on