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

• Solution - Visual Example

• Solution - Algorithm

• Can ChatGPT-4o Solve It?

• My Thoughts

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 2 is also acceptable.

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

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 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:

• Each node is identified by its id

• Nodes a and b are unique

• + nodes are non-unique

Even though + nodes are identical, they have different internal ids.

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:

Each node in the current graph G has an internal id — alpha beta gamma delta:

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

The mapping is between {alpha beta gamma delta} and {1 2 3 4} — that is, between node ids 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).

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

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

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:

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 ids 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 ids, we are left with the list of edges to check

• Take the first one that fits (that is, when added the graph is still equivalent to the SG solution graph)

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 ids 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:

(1) ChatGPT-4o generates levels for Graph Game by parsing nodes and edges from neural network architecture diagrams

(2) ChatGPT-4o vs. Spatial Reasoning IQ Test

(3) ChatGPT-4o converts image to text, then recreates it image from text