Skip to content

GNN Problems

  • Observation: more layers = worse performance
  • Paradoxically, need more layers to capture long-range information
    • The number of layers needs to match the Bottleneck of Graph Neural Networks, which conceptualizes the distance away from a node that contains information important to the task.

  • Adding layers often gives exponential increase in receptive field (i.e., you get the neighbors’ neighbors) – lots of information to capture since we need the neighbors of the neighbors of the neighbors. Given a d-dimensional vector of 32-bit float values flatten each float into 32-digit binary vector to represent states: \(Ω = 2^{32d}\) This gives an upper-bound on the number of structures a vector could possibly distinguish among. Capacity needed to fit training data of a toy problem:

  • Adding fully-connected adjacency (“FA”) layers for final GNN layer (i.e., pretended graph was fully connected) consistently improved performance

    • This shows that there was meaningful info in other nodes that wasn’t captured by the multi-layered GNN
  • However, using FAs in all layers (i.e., ignoring real graph structure) produced much worse results

Best improvement achieved for GGNN's

Over-smoothing vs Over-squashing⚓︎

  • Over-smoothing: node representations become indistinguishable when the number of layers increases due to taking aggregates of aggregates of…
  • Over-squashing: information from an exponentially-growing receptive field is compressed into fixed-length node vectors
    • Similar in concept to RNNs, which need to represent e.g., a sequence of words in a fixed-length vector, and this can become a bottleneck for long sequences

Solution 1: Skip Connections⚓︎

High-level idea: copy/paste information from a lower layer so that the new layer doesn’t have to keep track of everything • Several different types… - Residual connection—connect \(l − 1\) to \(l\): \(\hat ℎ^l = f(ℎ^l,ℎ^{l-1})\) - Initial connection—connect \(l = 0\) to all \(l\): \(\hat ℎ^l = f(ℎ^l,ℎ^0)\) - Dense skip connection—connect \(l′ < l\) to l: \(\hat ℎ^l = f(ℎ^l,ℎ^{l'|l'<l})\) - Jumping Knowledge connection—connect all layers to the final layer: \(\hat ℎ^L = f(ℎ^L,ℎ^{l|l < L})\)

Solution 2: Graph Normalization⚓︎

Solution 3: Graph Rewiring⚓︎

  • High-level idea : change the graph (edge set) to make it more message-passing friendly
    • There is no guarantee that the natural graph structure is equal to the one that expresses optimal computational dependencies
    • There are noisy edges, and some important relationships may not be captured by an edge
  • Diffusion-based approaches: smooth A with a diffusion process (includes multi-hop info) and sparsify to get a new A
  • Geometric “Ricci-curvature” approach: selectively remove edges that bridge different communities, as this causes the exponential increase