Message passing lets a graph node update its representation using information from connected nodes. A road segment, for example, may have a travel-time estimate that misses delays on nearby segments. Representing segments as nodes and their connections as edges lets a graph neural network include neighboring traffic in each segment’s embedding. section 11.3.1
Think of the update in successive passes:
- Start with node features and the graph’s connections. section 11.3.1
- After one pass, each node has information from its neighbors. After a second, it can reflect information from its neighbors’ neighbors. section 11.3.1
- Use the resulting embeddings for a downstream task, such as node classification or predicting whether an edge exists. section 11.3.1
From messages to a TSP tour
For a traveling salesperson problem, define node features and connections, then use a GNN or GCN to generate embeddings through message passing. An MLP predicts which nodes or edges belong to a solution; graph search uses those predictions to find a feasible candidate tour. The embeddings guide the search—they are not themselves a tour. A pretrained-model example avoids the substantial preprocessing and code needed to train this pipeline from scratch. section 11.7
Figure 11.6 Message passing and updating in GCN
The diagram shows message passing and updating in a GCN; use it to trace how information moves between connected nodes. section 11.3.1
class GCN(torch.nn.Module):
def __init__(self):
super(GCN, self).__init__()
self.conv1 = GCNConv(dataset.num_node_features, 16)
self.conv2 = GCNConv(16, dataset.num_classes)
self.dropout = torch.nn.Dropout(0.5)
def forward(self, data):
x, edge_index = data.x, data.edge_index
x = self.conv1(x, edge_index)
x = F.relu(x)
x = F.dropout(x, training=self.training)
x = self.conv2(x, edge_index)
return x
The PyTorch Geometric example applies two GCNConv layers to node features and edge connections, giving a compact implementation to inspect alongside the neighborhood-pass intuition. section 11.3.1
