Md. Asif Uddin
    I.14.X07

    Two layers cannot see three hops

    numeric▲▲△

    Give every node the feature 11 on a path of four nodes and on a path of five. Apply the graph convolution’s A^\hat{\mat A} one, two and three times, and compare the value at node 11, an end of each path. When do the two first differ, and why then?

    Hint

    After kk applications node 11 depends on the degrees and features within kk hops. In both paths nodes 11, 22 and 33 have the same degrees; node 44 does not.

    Solution
    layerspath of fourpath of five
    110.9082480.9082480.9082480.908248
    220.8929560.8929560.8929560.892956
    330.8904080.8904080.8802130.880213

    The values agree for two layers and differ at the third. Node 11‘s value after kk layers uses the entries of A^\hat{\mat A} along walks of length at most kk from it. Those entries depend on the degrees at both ends of each edge walked. Within two hops of node 11 the walks touch only nodes 11, 22 and 33, whose degrees are 11, 22 and 22 in both paths. The third layer walks the edge from node 33 to node 44, and node 44 has degree 11 in the shorter path and 22 in the longer.

    So a two-layer network cannot tell whether node 11 sits on a path of four or five, whatever its width or weights. That is I.14.T2 at work: a task that depends on something three hops away needs three layers, and the averaging of proposition 3 makes each extra layer cost something.

    Draws on