Answers.Body: <blockquote>
  <p>is the graph processed as a whole somehow, or are we basically iterating the same GNN over all the nodes one-by-one.</p>
  </blockquote>
  <p>Yes, the graph is processed as a whole and we don't really <em>iterate</em> 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.</p>
  <p>Mathematically, a GNN layer computes</p>
  <p><span class="math-container">$$\mathbf{h}_u^l = \sum_{\forall v \in \mathcal{N}(u)} \mathbf{h}_v^{l-1},$$</span></p>
  <p>where <span class="math-container">$\mathbf{h}_u^l$</span> is the encoding of node <span class="math-container">$u$</span> after layer <span class="math-container">$l$</span> and <span class="math-container">$\mathcal{N}(u)$</span> is the neighborhood of node <span class="math-container">$u$</span>. You can see how <strong>the new encoding of node <span class="math-container">$u$</span> depends on the previous encodings of surrounding nodes <span class="math-container">$v \in \mathcal{N}(u)$</span></strong>. This intertwines/convolves intermediate encodings over the space of the graph and thus it is NOT a one-by-one node encoding method.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-04-05T09:20:16.710Z
Answers.LastActivityDate: 2023-04-05T09:20:16.710Z
Answers.UserDisplayName: Chillston
Body: <p>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.</p>
  <p>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 &quot;whole&quot;. 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?</p>
  
Tags: <graph-neural-networks>
Title: Do GNNs operate on enitre graphs or do they basically iterate over each node one-by-one?
UserDisplayName: oliver.c
ThreadText: # Do GNNs operate on enitre graphs or do they basically iterate over each node one-by-one?
  
  (Asked by: username_0 on 2023-04-04)
  
  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?
  
  **Tags:** graph-neural-networks
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-04-05. Score: 0
  
  > 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.
  
  
  ---
  
  