VF3/VF3L misses valid subgraph isomorphism matches

[zzppcczpc]

VF3 Bug Report: Missing Valid Subgraph Isomorphism Matches

Summary

VF3/VF3L algorithm misses some valid subgraph isomorphism matches under certain conditions. The algorithm returns 31 matches when there should be 34 valid matches.These 34 valid matches were found by the code I wrote myself. My initial aim was to use the VF algorithm as a reference algorithm to verify the correctness of the code I wrote myself. Below are the 34 valid matches I found:
Found 34 matches:
Results written to result2.txt
[1] q0->390 q1->504 q2->450 q3->802
[2] q0->390 q1->504 q2->702 q3->802
[3] q0->390 q1->504 q2->880 q3->802
[4] q0->390 q1->504 q2->896 q3->802
[5] q0->471 q1->504 q2->556 q3->30
[6] q0->471 q1->504 q2->556 q3->31
[7] q0->471 q1->504 q2->556 q3->179
[8] q0->471 q1->504 q2->556 q3->262
[9] q0->471 q1->504 q2->556 q3->272
[10] q0->471 q1->504 q2->556 q3->285
[11] q0->471 q1->504 q2->556 q3->338
[12] q0->471 q1->504 q2->556 q3->732
[13] q0->471 q1->504 q2->556 q3->802
[14] q0->471 q1->504 q2->556 q3->1357
[15] q0->471 q1->504 q2->780 q3->30
[16] q0->471 q1->504 q2->780 q3->31
[17] q0->471 q1->504 q2->780 q3->179
[18] q0->471 q1->504 q2->780 q3->262
[19] q0->471 q1->504 q2->780 q3->272
[20] q0->471 q1->504 q2->780 q3->285
[21] q0->471 q1->504 q2->780 q3->338
[22] q0->471 q1->504 q2->780 q3->732
[23] q0->471 q1->504 q2->780 q3->802
[24] q0->471 q1->504 q2->780 q3->1357
[25] q0->471 q1->504 q2->2221 q3->30
[26] q0->471 q1->504 q2->2221 q3->31
[27] q0->471 q1->504 q2->2221 q3->179
[28] q0->471 q1->504 q2->2221 q3->262
[29] q0->471 q1->504 q2->2221 q3->272
[30] q0->471 q1->504 q2->2221 q3->285
[31] q0->471 q1->504 q2->2221 q3->338
[32] q0->471 q1->504 q2->2221 q3->732
[33] q0->471 q1->504 q2->2221 q3->802
[34] q0->471 q1->504 q2->2221 q3->1357
The output of the VF algorithm is:
Loaded in: 0.006957
FastCheck in: 0
Classification in: 5.9e-05
Solution Found
0,390:1,504:2,450:3,802:
0,390:1,504:2,702:3,802:
0,390:1,504:2,880:3,802:
0,390:1,504:2,896:3,802:
0,471:1,504:2,556:3,30:
0,471:1,504:2,780:3,30:
0,471:1,504:2,2221:3,30:
0,471:1,504:2,556:3,31:
0,471:1,504:2,780:3,31:
0,471:1,504:2,2221:3,31:
0,471:1,504:2,556:3,179:
0,471:1,504:2,780:3,179:
0,471:1,504:2,2221:3,179:
0,471:1,504:2,556:3,262:
0,471:1,504:2,2221:3,262:
0,471:1,504:2,556:3,272:
0,471:1,504:2,2221:3,272:
0,471:1,504:2,556:3,285:
0,471:1,504:2,780:3,285:
0,471:1,504:2,2221:3,285:
0,471:1,504:2,556:3,338:
0,471:1,504:2,780:3,338:
0,471:1,504:2,2221:3,338:
0,471:1,504:2,556:3,732:
0,471:1,504:2,2221:3,732:
0,471:1,504:2,556:3,802:
0,471:1,504:2,780:3,802:
0,471:1,504:2,2221:3,802:
0,471:1,504:2,556:3,1357:
0,471:1,504:2,780:3,1357:
0,471:1,504:2,2221:3,1357:
First Solution in: 2.48855e-05
Matching Finished in: 3.71465e-05
Solutions: 31
There are three matches that this VF code has omitted but are actually valid:
[18] q0->471 q1->504 q2->780 q3->262
[19] q0->471 q1->504 q2->780 q3->272
[22] q0->471 q1->504 q2->780 q3->732
For details, please see below.

data.txt
query.txt

Environment

• VF3lib version: latest from GitHub (https://github.com/MiviaLab/vf3lib)
• OS: Windows 11 + WSL (Ubuntu)
• Compiler: g++ with C++11

Test Case

Query Graph (query)

A star graph with 4 nodes and 3 edges:

t 4 3
v 0 1 3
v 1 0 1
v 2 2 1
v 3 5 1
e 0 1 0
e 0 2 0
e 0 3 0

Structure:

• Node 0 (label=1) is the center node
• Node 0 has outgoing edges to nodes 1, 2, 3
• Node 1 (label=0), Node 2 (label=2), Node 3 (label=5) are leaf nodes

Data Graph (data)

A directed graph with 3312 nodes and 4715 edges (4591 edges after removing 124 self-loops, as VF3 does not support self-loops).

Key nodes involved in the bug:

v 262 5 9
v 272 5 10
v 471 1 29
v 504 0 6
v 556 2 6
v 732 5 19
v 780 2 18
v 2221 2 4

Key edges from node 471:

e 471 262 0
e 471 272 0
e 471 504 0
e 471 556 0
e 471 732 0
e 471 780 0
e 471 2221 0

Commands Executed

# Compile
make

# Run subgraph isomorphism
./bin/vf3l query.grf data.grf -s

Expected vs Actual Results

Expected: 34 matches

All valid matches where:

• Query node 0 (label=1) maps to data node 471 (label=1)
• Query node 1 (label=0) maps to data node 504 (label=0)
• Query node 2 (label=2) maps to data node 780 (label=2)
• Query node 3 (label=5) maps to any node with label=5 that 471 has an edge to

Node 471 has edges to these label=5 nodes: 30, 31, 179, 262, 272, 285, 338, 732, 802, 1357

So there should be 10 matches with the pattern 0,471:1,504:2,780:3,xxx

Actual: 31 matches (missing 3)

VF3 output:

Solution Found
0,390:1,504:2,450:3,802:
0,390:1,504:2,702:3,802:
0,390:1,504:2,880:3,802:
0,390:1,504:2,896:3,802:
0,471:1,504:2,556:3,30:
0,471:1,504:2,780:3,30:
0,471:1,504:2,2221:3,30:
0,471:1,504:2,556:3,31:
0,471:1,504:2,780:3,31:
0,471:1,504:2,2221:3,31:
0,471:1,504:2,556:3,179:
0,471:1,504:2,780:3,179:
0,471:1,504:2,2221:3,179:
0,471:1,504:2,556:3,262:      <-- has 556, missing 780
0,471:1,504:2,2221:3,262:     <-- has 2221, missing 780
0,471:1,504:2,556:3,272:      <-- has 556, missing 780
0,471:1,504:2,2221:3,272:     <-- has 2221, missing 780
0,471:1,504:2,556:3,285:
0,471:1,504:2,780:3,285:
0,471:1,504:2,2221:3,285:
0,471:1,504:2,556:3,338:
0,471:1,504:2,780:3,338:
0,471:1,504:2,2221:3,338:
0,471:1,504:2,556:3,732:      <-- has 556, missing 780
0,471:1,504:2,2221:3,732:     <-- has 2221, missing 780
0,471:1,504:2,556:3,802:
0,471:1,504:2,780:3,802:
0,471:1,504:2,2221:3,802:
0,471:1,504:2,556:3,1357:
0,471:1,504:2,780:3,1357:
0,471:1,504:2,2221:3,1357:
31 2.45103e-05 3.70758e-05

Missing Matches (3 total)

0,471:1,504:2,780:3,262
0,471:1,504:2,780:3,272
0,471:1,504:2,780:3,732

Verification of Missing Matches

All 3 missing matches are valid:

Match 1: 0,471:1,504:2,780:3,262

Query Node	Query Label	Data Node	Data Label	Match
0	1	471	1	✓
1	0	504	0	✓
2	2	780	2	✓
3	5	262	5	✓

Edge verification:

• Query edge 0→1: Data edge 471→504 exists ✓
• Query edge 0→2: Data edge 471→780 exists ✓
• Query edge 0→3: Data edge 471→262 exists ✓

Match 2: 0,471:1,504:2,780:3,272

Query Node	Query Label	Data Node	Data Label	Match
0	1	471	1	✓
1	0	504	0	✓
2	2	780	2	✓
3	5	272	5	✓

Edge verification:

• Query edge 0→1: Data edge 471→504 exists ✓
• Query edge 0→2: Data edge 471→780 exists ✓
• Query edge 0→3: Data edge 471→272 exists ✓

Match 3: 0,471:1,504:2,780:3,732

Query Node	Query Label	Data Node	Data Label	Match
0	1	471	1	✓
1	0	504	0	✓
2	2	780	2	✓
3	5	732	5	✓

Edge verification:

• Query edge 0→1: Data edge 471→504 exists ✓
• Query edge 0→2: Data edge 471→780 exists ✓
• Query edge 0→3: Data edge 471→732 exists ✓

Observation

The missing matches all share the same pattern:

• Query node 2 maps to data node 780
• Query node 3 maps to nodes 262, 272, or 732

Interestingly, data node 780 also has outgoing edges to 262, 272, and 732:

e 780 262 0
e 780 272 0
e 780 732 0

This suggests the bug may be related to the predecessors selection in NextPair() function in VF3LightSubState.hpp. The algorithm might be incorrectly using node 780 (mapping of query node 2) as the predecessor to search for candidates for query node 3, instead of node 471 (mapping of query node 0).

Affected Versions

Both vf3 and vf3l executables produce the same incorrect result (31 matches instead of 34).

Files

The test files (query, data, query.grf, data.grf) are available in the parent directory for reproduction.

[zzppcczpc]

data.txt
query.txt