liveBook · Manning

Embedding

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

A function that maps input entities or features into numerical representations used by a model.

An embedding maps graph entities into continuous numerical vectors. Graph nodes and edges start in a discrete, often high-dimensional domain; their embeddings occupy a lower-dimensional space intended to retain useful structural information. This makes graph data available to machine-learning tasks such as node classification, link prediction, and community detection. section 11.3.1 section 11.3

From connections to vectors

Imagine a graph connecting soccer players to their clubs and nationalities. An encoder can assign each node a vector using its position, neighborhood, features, or a combination of these. The aim is for connected or nearby nodes to have similar embeddings, while distant nodes are less similar. The vectors are learned representations, not a replacement for the original relationships. section 11.3 section 11.3.1

Figure 11.4 Graph embedding

The diagram shows the mapping from an input graph to its lower-dimensional embedding space. section 11.3.1

Two approaches differ in what they can embed after training:

  • Transductive methods learn representations for nodes present during training. They suit static graphs but cannot directly embed unseen nodes and can be difficult to scale. Random-walk methods such as node2vec and DeepWalk are examples. section 11.3.1
  • Inductive methods learn a function that can generate embeddings for unseen nodes or graphs, rather than storing representations only for training nodes. section 11.3.1

A practical node-embedding example uses the Cora dataset and a graph convolutional network (GCN) in PyTorch Geometric. Two GCNConv layers process node features alongside graph connections; the example trains with Adam on labeled nodes. For an optimization application, a graph neural network first produces embeddings, a multilayer perceptron predicts which nodes or edges belong to a solution, and graph search seeks a feasible traveling-salesperson tour. An embedding supports that pipeline; it is not itself a feasible tour. section 11.3.1 section 11.7

Listing 11.2 Node embedding using GCN
import numpy as np
from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import PCA
from sklearn.pipeline import Pipeline
import torch
import torch.nn.functional as F
from torch_geometric.datasets import Planetoid
from torch_geometric.nn import GCNConv
from torch_geometric.utils import to_networkx

Open the PyTorch Geometric listing for the imports and dataset workflow used in the node-embedding example. section 11.3.1

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

How deep it goes
Defines the encoder and similarity objective, distinguishes transductive from inductive methods, and illustrates a GCN implementation; full TSP training is deferred.
Examples
Uses a soccer-player relationship graph, Cora node embeddings with PyTorch Geometric, and a traveling-salesperson solution pipeline.
What it assumes
Builds from graph nodes, edges, and machine-learning basics rather than assuming prior knowledge of graph embeddings.
What you can do after
Apply it via PyTorch Geometric to generate node representations with a GCN, then distinguish those representations from downstream predictions or solutions.
How it connects
Connects graph machine learning, graph convolutional networks, representation learning, node classification, link prediction, and graph search.
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

Also explained in

Compare how 47 books explain embedding →

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.