liveBook · Manning

Graph

As explained in Graph Neural Networks in Action

A graph data model specifies how entities, relationships, attributes, and constraints are represented as graph elements.

Use a graph when relationships between entities matter to the question you are trying to answer. A table can describe each passenger on the Titanic in a separate row; a graph can also make family ties and shared cabins visible as connections. The choice is not automatic: an edge should represent a relationship you can justify from the data or a stated assumption. section 1.2.5 section 1.4.1

A graph consists of nodes (or vertices) for entities and edges (or links) for relationships. Nodes carry features, such as a person’s age. An adjacency matrix records which node pairs connect: a 1 can mean an edge exists and a 0 that it does not. For an undirected graph, connections work both ways, so the matrix is symmetric. An edge weight can express a stronger relationship by replacing a binary entry with another value. section 1.2.1

Table 1.1 The adjacency matrix for the simple graph in figure 1.1
A
B
C
D
E
A
0
1
0
0
1
B
1
0
1
1
1
C
0
1
0
1
0
D
0
1
1
0
1
E
1
1
0
1
0

Compare the two mirrored entries for any connected pair: the matrix makes an undirected graph’s symmetry concrete. section 1.2.1

Choose the structure that matches the relationships:

  • A homogeneous graph uses one node type and one edge type; a heterogeneous graph can distinguish, for example, job candidates from companies and their employment relationships. section 1.2.2
  • A bipartite graph separates nodes into two sets and permits connections across sets, not within one set. Pins connected to boards illustrate the constraint. section 1.2.2
  • A cyclic graph has a route back to its starting node without retracing steps; an acyclic graph does not. A directed acyclic graph adds direction while excluding cycles. section 1.2.2

Turning passenger records into a graph

Make passengers nodes, retain passenger details as features, and add edges for supported relationships such as family membership or a shared cabin. Cabins or families can instead become their own nodes. Links inferred from names or ticket numbers require assumptions; they are not relationships simply because two rows look similar. section 1.2.5

For a graph-learning project, decide on nodes, edges and features before choosing storage or preprocessing. Data then needs suitable sampling, batching and train/validation/test splits for a graph neural network (GNN). Its message-passing layers combine a node’s features with information from neighbors. Check whether the structure helps: when relationships are insignificant, a GNN is not the natural choice. Structural exploration—such as inspecting connected components, density and clustering—can also expose issues before training. section 1.5.1 section 4.2.3 section 1.6

How Graph Neural Networks in Action covers it

How deep it goes
Defines nodes, edges and adjacency matrices, sketches graph types, and points readers seeking fuller graph fundamentals to an appendix.
Examples
Uses a small adjacency matrix, Titanic passenger relationships and structural exploration of a Yelp review graph.
What it assumes
Introduces graph fundamentals without assuming prior graph knowledge, while assuming familiarity with neural-network training terminology.
What you can do after
Build it from scratch by choosing entities, relationships and features, then assess whether graph structure warrants a GNN.
How it connects
Connects adjacency matrices and graph types to graph neural networks, message passing and permutation invariance.
Cover of Graph Neural Networks in Action
liveBookmanning.com
Read Graph Neural Networks in Action on liveBook Get the book at manning.com

Also explained in

Compare how 21 books explain graph →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Graph Neural Networks in Action. The section links point to the parts of the book it draws on.