- Sabrina Ramonov
- Posts
- ChatGPT-4o vs. Graph Theory

# ChatGPT-4o vs. Graph Theory

## How Does ChatGPT-4o Perform on Abstract Math and Reasoning Tasks?

Can multimodal ChatGPT-4o solve a **graph problem** I encountered while building Graph Game?

Let’s find out.

Here’s the **abstract math TLDR** for the impatient:

a collection of non-unique nodes of the same node type forms a symmetric group

any automorphism (permutation) of such symmetric group defines an equivalent graph

the set of all equivalent graphs is in correspondence with the cartesian product of all such symmetric groups (a subset of all graph automorphisms with permuted )

`

`AddEdge(G, e, M)``

preserves node invariants (where`M`

is a subset of an automorphism of the graph`SG`

)

**If that doesn’t make any sense to you…**

**but you want to know if ChatGPT-4o can figure it out, keep reading!** 😀

# Problem Statement

I built Graph Game to test your understanding of neural network architectures by making you assemble them from scratch.

In Graph Game, you connect one edge at a time.

Each node has an `id`

and some data associated with it.

There are two types of nodes:

**unique nodes**— you have to connect exactly that node e.g.**x_t****non-unique nodes**— doesn’t matter which one you pick as long as they connect the same

For example, let’s say we have:

3 unique nodes:

**x_t, h_t, y_t**3 non-unique nodes:

**x**hadamard product nodes

Your objective is to complete the graph: **y_t = x_t x h_t**

You need to connect the unique nodes.

But when you get to the non-unique **“x”** nodes, it shouldn’t matter which one you connect, as long as the invariants match (i.e. incoming / outgoing connections).

If you have multiple non-unique node types (e.g. **“x”** and **“+”**), then you can only swap** x** for another **x**,** **and you can only swap **+ **for another **+.**

For example…

**Figure 1 is acceptable:**

Figure 1 | Sabrina Ramonov

**Figure 2 is also acceptable.**

Because it doesn’t matter which non-unique **x** node you connect to:

Figure 2 | Sabrina Ramonov

**But Figure 3 below is wrong!**

Even though you can connect to whichever non-unique node **x**, you still need to ensure the graph is valid and corresponds to your equation.

By connecting** h_t** to the 2nd non-unique node **x**, the graph no longer corresponds to: **y_t = x_t x h_t.**

Figure 3 | Sabrina Ramonov

**Figure 4 **shows another example of** a wrong graph **in Graph Game**.**

Green lines are correct edges.

Red lines are incorrect edges:

Figure 1 and Figure 2, both correct, are equivalent graphs.

But Figure 3 is not equivalent to them.

It sounds obvious, but think about it…

**Given **`m`

** node types **`nt_1`

**, **`nt_2`

**, …, **`nt_m`

** — each with **`cnt_1`

**, …, **`cnt_m`

** equivalent nodes, how many equivalent graphs do you have?**

Our goal is to write a function that takes:

a new edge

`e`

current graph

`G`

solution graph

`SG`

… and determines whether edge `e`

is correct.

In other words, here is the problem statement:

**Is the resulting graph **`AddEdge(G, e) ~ SG`

** equivalent to **`SG`

** up to renaming of non-unique nodes of the same type?**

# Solution - Visual Example

Let’s start with one example and lots of pictures.

Here is a sample solution graph `SG`

:

Sabrina Ramonov

Each node is identified by its

`id`

Nodes

`a`

and`b`

are unique`+`

nodes are non-unique

SG

**Even though **`+`

** nodes are identical, they have different internal **`id`

**s.**

Let’s start solving the graph. At first, when you load Graph Game, there are no edges connecting nodes. The current graph `G`

looks like this:

Sabrina Ramonov

Each node in the current graph `G`

has an internal `id`

— alpha beta gamma delta:

Sabrina Ramonov

**When you connect nodes, there are only 2 graphs that are equivalent to the solution graph:**

Sabrina Ramonov

Sabrina Ramonov

**The mapping is between {alpha beta gamma delta} and {1 2 3 4}** — that is, between node `id`

s of the current graph `G`

and the solution graph `SG`

.

At the start, the mapping is empty because there are no edges.

We don’t need to keep track of unique nodes, because we know that `alpha`

maps to `1`

and `delta`

maps to `4`

. These nodes are unique so there is only one choice for them.

However, there are two choices for the `+`

node — beta and gamma.

Suppose we are trying to add an edge from `alpha`

to `gamma`

Because `a`

is unique and there is an edge between 1 and 3 in the solution graph, it’s obvious that `gamma`

should map to `3`

.

We update the mapping and draw an edge (the mapping is shown in red).

Current Graph G | Solution Graph SG |

Now let’s try to add an edge from beta to delta:

Current Graph G | Solution Graph SG |

Obviously, it’s not a correct edge.

To check it, first we rename our nodes using the mapping.

Since `b`

is a unique node, it can only map to 4.

Since `3`

is already mapped from `gamma`

, the only mapping choice for `beta`

is `2`

Current Graph G | Solution Graph SG |

However, in our solution graph `SG`

, there is no edge from `id`

=2 to `id=`

4.

On the other hand, connecting gamma to delta results in:

Current Graph G | Solution Graph SG |

The mapping is in red.

When we check this candidate, we have:

delta unique node

gamma non-unique node

But gamma is already mapped to 3!

**As long as the added edge is in the mapping (in this case, between 3 & 4) we’re all good. **Because all previous edges were added before and are correct, so we only need to check the new edge.

We don’t have any more edges to add, so we’re done!

# Solution - Algorithm

Here is the solution presented as an algorithm.

We use **iterative edge adding:**

Fancy way of saying **“when an edge is added, check the graph is valid”**.

If you use a non-unique node in the connections, the incoming and outgoing edges should remain consistent with the original graph.

We'll maintain a **“renaming map”** to track how `G`

maps into `SG`

.

The only way to “map” a node is by adding an edge to it.

At any given point, every unmapped node has degree 0 because it has no incoming or outgoing edges.

We start with graph `G`

— it has no edges and all the same nodes as `SG`

.

Then, we track assignment of mappings between `S`

and `SG`

at every step.

**If we add an edge between **`source_id`

** and **`target_id`

** nodes, we must check the resulting graph is a subset of an equivalent graph to **`SG`

**. **

Here’s how it works step-by-step:

Given a mapping between some non-unique nodes of G and SG, we want to add an edge between nodes

`n1`

and`n2`

in the graph**if**`n1`

**and**`n2`

**are unique**— then simply use their`id`

s and the only edge we need to check is n1→n2**if one of them is NON unique**— then, for each non-unique node**if the node is in the mapping**, then use the mapped id**if the node is NOT in the mapping**, then we replace its id with a list of nodes of the same type

After replacing

`id`

s, we are left with the list of edges to checkTake the first one that fits (that is, when added the graph is still equivalent to the

`SG`

solution graph)

Giphy

**The algorithm’s output should tell us whether the edge is correct or not, and return the updated “renaming map”.**

All we have to do is:

Keep track of where the `id`

s of the non-unique nodes in the current graph `G`

map to `SG`

and whether, after adding an edge, we preserved all node degrees.

Because the process is done iteratively, starting with graph `S`

with no edges, then in the beginning `G`

is a subgraph of any graph equivalent to `SG`

.

Each time we pick a correct edge, we add the mapping to our “renaming map”.

Eventually, we’ll map the whole graph and find a solution.

# Can ChatGPT-4o Solve It?

I gave this problem to ChatGPT-4o after solving it.

Curious if it would come up with a solution.

Here’s my prompt and ChatGPT session:

```
prompt:
You are an expert competition programmer. Solve the following problem and output a solution in python and unit tests:
```
Given a graph `SG` where each node can be either unique or non-unique. Non-unique nodes are identified by `group_id` and are interchangeable. This means that renaming the ids of these nodes produces an equivalent graph. For example, non-unique nodes of the same group_id `n1`, `n2`, `n3`, unique nodes `u1`, `u2` the following graphs are equivalent:
- G1 with the same nodes and edges `u1` -> `n1` and `n1` -> `u2`
- G2 with the same nodes and edges `u1` -> `n2` and `n2` -> `u2`
Write a function `add_edge(e, g, sg)` which takes a graph `g` which is a subgraph of a graph equivalent to `sg` and a new edge `e`. This function should output `True` if adding an edge `e` to graph `g` results in a subgraph of an graph equivalent to `sg`.
```
```

```
def add_edge(e, g, sg):
def parse_graph(graph):
adj_list = {}
for edge in graph:
if edge[0] not in adj_list:
adj_list[edge[0]] = []
adj_list[edge[0]].append(edge[1])
return adj_list
def identify_groups(graph):
group_ids = {}
for edge in graph:
for node in edge:
if isinstance(node, tuple): # assuming non-unique nodes are represented as (group_id, node_id)
group_id = node[0]
if group_id not in group_ids:
group_ids[group_id] = []
group_ids[group_id].append(node)
return group_ids
def are_equivalent(graph1, graph2, group_ids1, group_ids2):
from itertools import permutations
def permute_graph(graph, group_permutations):
permuted_graph = {}
for node in graph:
if isinstance(node, tuple) and node[0] in group_permutations:
new_node = group_permutations[node[0]][node[1]]
permuted_graph[new_node] = [group_permutations[n[0]][n[1]] if isinstance(n, tuple) and n[0] in group_permutations else n for n in graph[node]]
else:
permuted_graph[node] = [group_permutations[n[0]][n[1]] if isinstance(n, tuple) and n[0] in group_permutations else n for n in graph[node]]
return permuted_graph
def compare_graphs(g1, g2):
if len(g1) != len(g2):
return False
for node in g1:
if node not in g2 or sorted(g1[node]) != sorted(g2[node]):
return False
return True
for group_id in group_ids2:
nodes = group_ids2[group_id]
permutations_list = list(permutations(nodes))
for perm in permutations_list:
group_permutations = {group_id: {nodes[i]: perm[i] for i in range(len(nodes))}}
permuted_graph1 = permute_graph(graph1, group_permutations)
if compare_graphs(permuted_graph1, graph2):
return True
return False
def is_subgraph(g1, g2):
for node in g1:
if node in g2:
for neighbor in g1[node]:
if neighbor not in g2[node]:
return False
else:
return False
return True
# Parse the graphs
g_adj = parse_graph(g)
sg_adj = parse_graph(sg)
# Identify groups in g and sg
g_groups = identify_groups(g)
sg_groups = identify_groups(sg)
# Add the new edge to g
new_edge = (e[0], e[1])
if new_edge[0] not in g_adj:
g_adj[new_edge[0]] = []
g_adj[new_edge[0]].append(new_edge[1])
# Check if the new g is a subgraph of any equivalent graph to sg
if is_subgraph(g_adj, sg_adj) or are_equivalent(g_adj, sg_adj, g_groups, sg_groups):
return True
else:
return False
# Unit tests
import unittest
class TestAddEdge(unittest.TestCase):
def test_case_1(self):
g = [("u1", ("g1", "n1"))]
sg = [("u1", ("g1", "n1")), (("g1", "n1"), "u2")]
e = (("g1", "n1"), "u2")
self.assertTrue(add_edge(e, g, sg))
def test_case_2(self):
g = [("u1", ("g1", "n1"))]
sg = [("u1", ("g1", "n1")), (("g1", "n1"), "u2")]
e = ("u1", "u2")
self.assertFalse(add_edge(e, g, sg))
if __name__ == "__main__":
unittest.main()
```

# My Thoughts

At first, ChatGPT returned a bunch of placeholders in the code, like “implement graph equivalence here”.

Thanks, professor ChatGPT.

Then I asked it to fill in the blanks.

**Its python code output** **runs,** **but the tests fail.**

**Can you see where ChatGPT went wrong? **🤔

Interestingly, it went in the direction of computing graph permutations of non-unique nodes and checking if they’re equivalent.

Computing all the permutations is time consuming since the number of permutations is `c1!c2!…cn!`

for `n`

partitions with the same node type.

But it doesn’t take into account the iterative nature of the process. It also ignored my explicit request in the prompt to add one edge at a time.

**If you liked this post, you might also enjoy:**