Understanding Graph Reasoning: Key Structures and Concepts Explained

Flying with post-covid jitters into the Megaquake warning.

I have been a bit off lately, battling a light but annoying case of COVID-19, which has left me floating through an ADHD version of my life. Having slightly recovered, I hope that now I find time to work on my plan to make August the month of Graph Reasoning.

To make matters worse, I will be flying to Japan tomorrow. There are some rumors of a once-in-a-century Nankai Trough Megaquake coming up. Since the last Nankai quake was more than 80 years ago it seems serious. Even Primeminiser Kishida decided to cancel his overseas trip. Maybe he was looking for a reason to not go. But I don’t want to second-guess his motivations. The last time I was in Japan, 5 people died in a plane crash while I was en route to the airport.

Life is full of these choices where everything can change in a heartbeat

Imagine you are standing at the center of a vast urban intersection, where every street is a line and every building a node. Picture it as if you're in the middle of Tokyo, staring at a grid of possibilities, where each corner could lead you to an alternate version of your life—a different apartment, a different job, a different you.

But instead of making a random choice, you need to navigate these connections with purpose, like an algorithm trying to optimize your route to happiness. You’re not just moving from point A to point B; you’re considering (reasoning) the implications of every detour. Will that extra stop cost you time, or will it lead to a serendipitous encounter? Each decision ripples through the network, altering the paths available to you, just like how a single line of code can change the behavior of an entire program.

One road leads to your certain death in an earthquake, one to the love of your life.

Graph Reasoning

Now, if everything was connected to everything else with equal weight, it’d be chaos—like trying to navigate a conversation in a noisy bar where everyone’s shouting at once. You’d need something to organize that mess, something that gives shape and meaning to the connections.

That’s where graph reasoning comes in, like different ways of understanding the tangled web of existence.

If one would run a standard TF-IDF keyword ranking algorithm over my introductory paragraph, probably, the terms "Japan, Prime Minister Kishida, Haneda Airport, Earthquake, Nankai Trough" would come out on top.

There are many relationships hidden in just these 5 entities. If you want to learn more about named entity recognition read this. For this post, I’d like to focus on visualizing them in a graph where the identified entities (nodes) are connected by relationships (edges).

In the Graph representation, each element of the list "Japan, Prime Minister Kishida, Haneda Airport, Earthquake, Nankai Trough" is a node, and the edges are neither defined, weighted, or directed. Even extremely simple ones like the one above can quickly explain complex relationships.

1. “Haneda Airport” is in “Japan”

2. “Kishida is Prime Minster” of “Japan”

3. “Nankai Trough” causes “Earthquake”

Observe the pairwise structure. In Mathematics, graphs are mathematical structures used to model pairwise relations between objects. So how can these nodes and edges assist a cognitive agent to reason better? The first step to a deeper understanding of this is an analysis of the different types of graph structures.

Prerequisites

A word on prerequisites. NetworkX is a fantastic Python library that can help do a lot of the heavy lifting for the graph creation for you. I used Matplotlib for the dataviz.

Most graphs below are a marginally revised version of this

plt.figure(figsize=(8, 6))
pos = nx.spring_layout(G, center=(0, 0), k=0.3)  
nx.draw(G, pos, with_labels=True, node_color='skyblue', node_size=3000, font_size=8, edge_color='gray')

plt.title("Template Graph")
plt.show()

Graph Structures

Erdős–Rényi (ER) Model:

This type of graph is named after Hungarian mathematicians Paul Erdős and Alfréd Rényi. The ER model is used for generating random graphs. To generate a graph using the ER model, we start with a fixed number of nodes (vertices) and randomly connect pairs of nodes with a certain probability. The ER model is often used to study random graphs and phase transitions. It helps to understand how connectivity emerges in a system with random interactions. Applications include modeling the spread of diseases, information flow, and social networks.

# Define the number of nodes
n = 5

# Define the probability of edge creation
p = 0.75

# Create a random Erdős–Rényi graph
G = nx.erdos_renyi_graph(n, p, seed=42)

There are two ways to construct a BA graph.

1. G(n, M): Choose a graph uniformly at random from all graphs with n nodes and M edges.

2. G(n, p): Construct a graph by connecting labeled nodes randomly. Each edge is included in the graph with probability p, independently of other edges.

I selected the latter for this exercise.