liveBook · Manning

K-hop neighborhood

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

A k-hop neighborhood is the set of graph nodes whose shortest-path distance from a specified node is at most k.

A k-hop neighborhood contains the nodes reachable from a specified node within k edges. In a graph convolutional network, each layer extends the information available to the node by one hop. section 11.3.1

Track neighborhood growth through message passing:

  • The first layer aggregates a node’s own features and information from immediate neighbors. section 11.3.1
  • The second layer reaches neighbors of neighbors, giving access to nodes two hops away. section 11.3.1
  • Additional layers propagate and aggregate information across progressively larger neighborhoods. section 11.3.1

Cora node embeddings

A two-layer GCN generates node embeddings for Cora, a citation network of 2,708 publications and 5,429 links. PyTorch Geometric supplies the Planetoid dataset and GCNConv layers. section 11.3.1

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes
Defines radius k and connects layers to hop distance, but stops short of describing neighborhood-extraction algorithms.
Examples
Demonstrates two-hop propagation through a two-layer GCN trained on the Cora citation network with PyTorch Geometric.
What you can do after
Apply it via PyTorch Geometric to relate GCN depth to the graph context encoded in node embeddings.
How it connects
Connects k-hop neighborhoods with graph embedding, graph convolutional networks, message passing, and node classification.
Cover of Optimization Algorithms: AI techniques for design, planning, and control problems
liveBookmanning.com
Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.