Do GNNs operate on enitre graphs or do they basically iterate over each node one-by-one?

Question

I understand how GNNs/GCNs aggregate an arbitrary number of nodes' information from the neighborhood of a target node in order to predict an attribute of that target node. What I don't understand is, when we predict this attribute to all nodes in a graph, is the graph processed as a whole somehow, or are we basically iterating the same GNN over all the nodes one-by-one.

Toy examples on the internet rarely involve larger graphs, so what I've seen is that they treat this like batches, and all nodes are processed together, concurrently, yet, not as a "whole". Given a larger graph (1000s of nodes), surely the GNN must be iterated over them, right? Which would mean, that we can scale GNNs to very large graphs too, as the size of the GNN layers wouldn't scale with the size of the graph, would it?

Answer 1

is the graph processed as a whole somehow, or are we basically iterating the same GNN over all the nodes one-by-one.

Yes, the graph is processed as a whole and we don't really iterate the same GNN over all the nodes one-by-one, but rather we convolve the nodes via the GNN. It is the idea of a convolution to apply the same local function over the space of a domain (like a graph or an image). After one application, this yields local encodings. Multiple consecutive convolutions generate increasingly global representations of the data.

Mathematically, a GNN layer computes

$$\mathbf{h}_u^l = \sum_{\forall v \in \mathcal{N}(u)} \mathbf{h}_v^{l-1},$$

where $\mathbf{h}_u^l$ is the encoding of node $u$ after layer $l$ and $\mathcal{N}(u)$ is the neighborhood of node $u$. You can see how the new encoding of node $u$ depends on the previous encodings of surrounding nodes $v \in \mathcal{N}(u)$. This intertwines/convolves intermediate encodings over the space of the graph and thus it is NOT a one-by-one node encoding method.

I hope this makes it clear, feel free to follow up. You can also look at image convolutions to better understand the concept, as images are a regular domain and the technique is basically the same.