On Incorporating Scale into Graph Networks

This paper was on Graph Learning on Wednesdays (GLOW) on <2025-05-28 Wed>. (I had to miss the session :[ )

GNNs are not UV-complete

UV-completeness: A model that is consistent in the sense that as the cutoff-distance (distance below which we cannot model any phenomena because they are too fine-grained for the resolution at which we are modelling) goes to zero, the model recovers the true original physical description.

Consider an ethane molecule:

     H      H
     |      |
H -- C ---- C -- H
     |      |
     H      H

and a coarse grained graph in which we aggregate \(CH_3\) groups into super-nodes S:


S ---- S

where the adjacencies are inverse of the inter-atomic distances.

A GCN-layer updates the node feature matrix \(X \in \mathbb{R}^{N \times F}\) as

\[ X \leftarrow \hat{A} X W. \]

Where \(W\) mixes between channels, and \(\hat{A}\) is the renormalized adjacency matrix: \(\hat{A}_{ij} \sim A_{ij}/\sqrt{d_i d_j}\) .

As we move hydrogen atoms towards the super-atoms (S), the weights of the H-C edges (in the adjacency matrix) goes to infinity. Since weights between the super-atoms remain constant, the renormalized entries \(\hat{A}_{\text{super-atom-1,super-atom-2}}\) tends to zero.

This means that as we go from the higher resolution graph (ethane) to a lower resolution graph \((S_2)\) , information flow between super-nodes is effectively cut-off. This means that the lower resolution graph looks more like:

 H      H
HC      CH
 H      H

and the graphs/node embeddings of this graph and the \(S_2\) graph differ greatly.

Designing a UV-complete layer

The diffusion equation on a graph is given by \(dX(T)/dt = - L . X(t)\) , with solution \(X(t) = e^{-Lt}.X(0)\) .

The paper shows that \(\eta_\omega(t) = \lVert e^{-t L_\omega} - J^{\uparrow} e^{t \underline{L}} J^{\downarrow} \rVert \rightarrow 0\) , for any fixed \(t \gt 0\) as \(\omega \rightarrow 0\) .

\(\omega\) is the scale of the finer graph, \(L\) is a graph laplacian, and one of the \(J\) s averages over strongly connected clusters to form a super-node (the paper says this is a linear interpolation, right now I don't understand how). The other J is the adjoint.

What this means is that diffusion with the Laplacian of the finer graph is more and more the same as transforming it the final graph to the coarser graph, running diffusion using the coarse laplacian, and then transforming the result back.

Thus, the traditional GNN update is insufficient for UV-completeness, but the update rule \(X \rightarrow e^{-t L_\omega} X W\) does not have this limitation.

The paper shows a more general update rule \(X \leftarrow \psi(L_\omega) X W \) , where \(\psi\) is a weighted sum over \(k\) different diffusions upto various times \(t\) , such that each diffusion is close to round-trip diffusion as before, and the coefficients of the diffusions are not too large, is UV-complete for large \(\omega\) by a triangle-inequality argument.

UV-complete GNNs

The paper then shows how to construct entire networks using this layer, but I'm skipping this part (and the 30 page(!) appendix) for now.

Experiments show that the new update rule is UV-complete (as the graph grows finer, node latent distances between the coarse graph and the original fine graph's node features tend to zero).