Problem radius is the graph distance, measured in hops, over which nodes can significantly affect one another for a task. It indicates how far information must travel through message passing for a GNN to model the relevant interaction. section 4.5.2 section 5.5.2
Use problem radius to guide GNN depth and architecture:
- Estimate how many hops separate nodes whose interaction matters to the prediction. section 4.5.2 section 5.5.2
- Choose enough message-passing layers to span that radius, while avoiding unnecessary depth that can increase over-smoothing. section 4.5.2 section 5.5.2
- For large radii, consider skip connections, neighborhood sampling, or added shortcut edges; each trades local detail against longer-range information. section 5.5.2
- Validate the assumed radius against the data: distant nodes may dominate molecular properties but matter much less in some motion-prediction relationships. section 5.5.2
Contrasting graph domains
A social network can have a large problem radius when a celebrity influences distant users. In a large molecule, atoms at opposite ends may jointly determine toxicity. By contrast, motion prediction may give the knee more influence on the foot than the head does. section 4.5.2 section 5.5.2
Figure 5.19 Visualization of over-squashing (Source: Alon and Yahav [7])
Visualizes over-squashing, a key failure mode when information from a large problem radius must pass through local message-passing paths. section 5.5.2
