Two layers cannot see three hops
numeric▲▲△Give every node the feature on a path of four nodes and on a path of five. Apply the graph convolution’s one, two and three times, and compare the value at node , an end of each path. When do the two first differ, and why then?
Hint
After applications node depends on the degrees and features within hops. In both paths nodes , and have the same degrees; node does not.
Solution
| layers | path of four | path of five |
|---|---|---|
The values agree for two layers and differ at the third. Node ‘s value after layers uses the entries of along walks of length at most from it. Those entries depend on the degrees at both ends of each edge walked. Within two hops of node the walks touch only nodes , and , whose degrees are , and in both paths. The third layer walks the edge from node to node , and node has degree in the shorter path and in the longer.
So a two-layer network cannot tell whether node 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.