File size: 8,440 Bytes
1aa2cd7
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
---
license: apache-2.0
datasets:
- GraphWiz/GraphInstruct-RFT-72K
metrics:
- accuracy
pipeline_tag: text-generation
tags:
- graph problem
---

# GraphWiz 

Project Page: [https://graph-wiz.github.io/](https://graph-wiz.github.io/)

Paper: [https://arxiv.org/abs/2402.16029.pdf](https://arxiv.org/abs/2402.16029)

Code: [https://github.com/nuochenpku/Graph-Reasoning-LLM](https://github.com/nuochenpku/Graph-Reasoning-LLM)


GraphWiz is a powerful instruction-following LLM that can map textural descriptions of graphs and structures, and then solve different graph problems explicitly in natural language.

Training strategies include two stages: **Mixed-task Training** and **DPO Alignment**.


## Results


| *Models* | **Cycle** | **Connect** | **Bipartite** | **Topology** | **Shortest** | **Triangle** | **Flow** | **Hamilton** | **Subgraph** | **Average** |
|:-------------------------------------:|:-------------------------------:|:--------------------------------:|:----------------------------------:|:---------------------------------:|:---------------------------------:|:---------------------------------:|:-----------------------------:|:---------------------------------:|:---------------------------------:|:--------------------------------------:|
| *In-Context Learning* |||||||||||
| **GPT-4 (zero-shot)**                 | 38.75                           | 17.00                            | 65.25                              | 5.00                              | 9.25                              | 5.75                              | 3.25                          | 59.25                             | 45.50                             | 27.67                                  |
| **GhatGPT (2-shot)**                  | 51.25                           | 43.75                            | 70.75                              | 4.50                              | 3.50                              | 17.25                             | 8.50                          | 54.25                             | 43.00                             | 32.97                                  |
| **GPT-4 (2-shot)**                    | 52.50                           | 62.75                            | 74.25                              | 25.25                             | 18.25                             | 31.00                             | 7.75                          | {75.75}                    | 46.75                             | 43.81                                  |
| *Mistral-7B* |||||||||||
| **Naive SFT**                         | 73.75                           | 83.50                            | 78.50                              | 1.00                              | 23.00                             | 47.00                             | 28.75                         | 31.75                             | 41.25                             | 46.56                                  |
| **GraphWiz**                        | **92.00**                  | **89.50**                     | 72.00                              | 19.00                             | **31.25**                      | 38.75                             | 29.25                         | 26.50                             | **85.50**                      | 53.75                                  |
| **GraphWiz-DPO**                    | 85.50                           | 79.50                            | **85.50**                     | **85.25**                      | 12.50                             | 29.00                             | 35.50                         | 62.75                             | 48.50                             | 58.22                                  |
| *LLaMA 2-7B* |||||||||||
| **Naive SFT**                         | 73.75                           | 83.50                            | 41.25                              | 4.00                              | 9.50                              | 30.00                             | 16.50                         | 69.00                             | 75.45                             | 44.81                                  |
| **GraphWiz**                        | 91.50                           | 87.00                            | 74.00                              | 18.00                             | **28.00**                    | 38.25                             | 24.50                         | 52.25                             | **82.25**                    | 55.08                                  |
| **GraphWiz-DPO**                    | 89.00                           | 82.50                            | 84.75                              | 46.75                             | 24.00                             | **52.75**                      | **43.50**                | **81.50**                      | 77.25                             | **65.00**                           |
| *LLaMA 2-13B* |||||||||||
| **Naive SFT**                         | 73.75                           | 83.75                            | 59.00                              | 0.50                              | 11.75                             | 34.75                             | 24.25                         | 59.75                             | 54.75                             | 44.69                                  |
| **GraphWiz**                        | **94.75**                    | 87.00                            | 78.00                              | 28.00                             | 27.75                             | 36.00                             | 24.50                         | 59.00                             | 81.50                             | 57.39                                  |
| **GraphWiz-DPO**                    | 87.50                           | **88.50**                   | **88.25**                       | **72.75**                    | 22.00                             | **48.75**                    | **43.75**                  | 46.50                             | 77.00                             | **63.89**                         |



## Examples

```
G-Q: Determine whether or not there is a cycle in an undirected graph. In an undirected graph..,the
 nodes are numbered from 0 to 88, and the edges are: (0, 73) (0, 51) (0, 10) (0, 63) (0, 28) (1, 62) (1, 57) (1, 84) (1, 61) (1, 5)
 (1, 24) (2, 84) (2, 3) (2, 66) (2, 68) (2, 17) (2, 35) (2, 34) (2, 15) (3, 39) (3, 52) (3, 16) (3, 15) (3, 8) (4, 69) (4, 85)
 (4, 36) (4, 72) (5, 44) (6, 77) (6, 7) (7, 85) (8, 64) (8, 23) (8, 28) (9, 34) (9, 31) (9, 61) (9, 28) (10, 26) (11, 37) (11, 39)
 (11, 19) (11, 64) (13, 73) (13, 61) (13, 80) (13, 85) (14, 86) (14, 59) (14, 32) (14, 58) (14, 85) (14, 66) (15, 43) (15, 48) (15, 73)
 (15, 19) (15, 47) (15, 68) (16, 46) (16, 60) (16, 84) (17, 44) (17, 72) (17, 36) (17, 37) (17, 61) (18, 20) (18, 24) (18, 22) (18, 41)
 (19, 45) (19, 83) (20, 25) (20, 29) (21, 38) (21, 64) (21, 24) (21, 22) (21, 34) (22, 23) (23, 34) (23, 30) (23, 83) (24, 47) (24, 50)
 (25, 59) (25, 42) (25, 70) (25, 72) (26, 45) (26, 30) (26, 87) (26, 80) (26, 50) (27, 77) (27, 58) (27, 60) (27, 29) (28, 36) (28, 59)
 (28, 88) (29, 31) (29, 33) (29, 56) (29, 55) (29, 78) (29, 73) (29, 82) (30, 34) (31, 58) (31, 70) (32, 78) (33, 73) (33, 68) (34, 48)
(34, 88) (34, 51) (34, 66) (34, 54) (35, 43) (35, 56) (36, 44) (36, 39) (37, 57) (37, 71) (38, 47) (38, 58) (38, 88) (39, 74) (39, 48)
 (39, 45) (39, 42) (40, 60) (40, 59) (40, 71) (40, 76) (41, 79) (42, 60) (42, 62) (42, 72) (43, 57) (44, 47) (44, 74) (44, 75) (44, 82)
 (44, 70) (45, 68) (45, 67) (45, 71) (46, 84) (47, 56) (48, 75) (49, 71) (49, 58) (50, 76) (51, 55) (51, 87) (51, 79) (52, 78) (56, 69)
(56, 83) (56, 79) (57, 76) (57, 70) (57, 72) (57, 78) (59, 70) (60, 80) (60, 76) (60, 77) (60, 75) (61, 74) (61, 77) (62, 84) (62, 66)
 (66, 69) (68, 88) (70, 88) (70, 76) (71, 81) (71, 72) (71, 86) (72, 75) (73, 82) (73, 83) (74, 85). Is there a cycle in this graph?


GraphWiz: 
There are many possible ways to find a cycle in this graph, but one example is: Starting from node 0, we can go to node 73 (via edge 0-73), then to node 82 (via edge 73-82),
then to node 44 (via edge 82-44), then to node 17 (via edge 44-17), then to node 36 (via edge 17-36), then to node 28 (via edge 36-28),
and back to node 0 (via edge 28-0). This forms a cycle [0-73-82-44-17-36-28-0] without revisiting any edge. So, there is a cycle in this graph.

```