liveBook · Manning

Undirected graph

As explained in Graph Neural Networks in Action

An undirected graph is a graph whose edges have no direction, so a connection from one node to another also connects the reverse pair.

An undirected graph represents relationships without direction: if node A connects to node B, B also connects to A. Nodes are also called vertices, and edges are also called links. section 1.2.1

An adjacency matrix stores every connection in one table. For an undirected graph, the matrix is symmetric across its diagonal because each edge appears in both directions. section 1.2.1

Use the matrix entries to distinguish common graph properties:

  • Store 1 for an unweighted edge and 0 for no edge. section 1.2.1
  • Store a larger value when one relationship has greater weight than another. section 1.2.1
  • Inspect the diagonal to identify self-loops: zero means no connection from a node to itself, while a nonzero value adds one. section 1.2.1
  • Represent the same relationships with adjacency lists, edge lists, or an incidence matrix instead of an adjacency matrix. section 1.2.1

Sensor and referral networks

A sensor network can use a constant, unweighted undirected adjacency matrix connecting 31 sensor positions across time. A staffing network can treat candidates as nodes and referrals as undirected, unweighted edges by ignoring referral direction and repeat referrals. section 6.2.1 section 8.1.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

Use the adjacency matrix to inspect the symmetric connections of a simple five-node graph. section 1.2.1

Figure 6.5 Sensor networks showing the error of wrongly inferring graph structures. The nodes are human skeletal connections. The left figure shows a network with edges inferred from node proximity (closest nodes connected to one another). This figure does not reflect a real human skeleton. The true set of edges is shown in the right figure.
figure

Compare an incorrectly inferred sensor network with the true skeletal connections to see why graph structure must reflect the real relationships. section 6.2.1

How Graph Neural Networks in Action covers it

How deep it goes
Explains matrix symmetry, weights, self-loops, and alternative representations through concrete graph structures.
Examples
Uses a five-node adjacency matrix, skeletal sensor connections, and candidate referral networks as concrete examples.
What you can do after
Apply direction-free edges when representing relationships and prepare the resulting structure for a GNN pipeline.
How it connects
Connects undirected graphs with adjacency matrices, weighted graphs, unweighted graphs, self-loops, edge lists, and graph neural networks.
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 5 books explain undirected 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.