GraphWiz/LLaMA2-13B

GraphWiz

Project Page: https://graph-wiz.github.io/

Paper: https://arxiv.org/abs/2402.16029.pdf

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