- 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 (whereM
is a subset of an automorphism of the graphSG
)
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
andb
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
andn2
in the graphif
n1
andn2
are unique — then simply use theirid
s and the only edge we need to check is n1→n2if 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: