``count_subgraph_isomorphisms'' fails to find all matching subgraphs

[wangzk]

Hi developpers, Thank you for providing the R igraph package which I find very useful for graph analysis. However, a few days ago, when I tried to use the ``count_subgraph_isomorphisms'' API, I found it failed to find all subgraphs. Maybe it is a bug in igraph's implementation of VF2 algorithm or I might call the API in a wrong way. I reporte the issue here to seek for help. Thank you for looking at this report.

I had a target graph "WordNet" which comes from the WordNet dataset and contains 76,853 vertices and 132,537 edges. I tried to find all isomorphic subgraphs of a pattern graph in this WordNet target graph. The pattern graph is small. It only consists of 3 vertices and 3 edges. The pattern graph and the target graph are both colored graph.

I call the count_subgraph_isomorphisms API in the following way:

library(igraph)
# read a colorred graph from edge and vertex file
read_graph_file <- function(edge_file, vertex_file) {
  # please consult the file format explaination file in the attachment about the file format we used
  vertex_info = read.table(vertex_file)
  vertex_data = vertex_info$V1 # read vertex id
  color_data = vertex_info$V2 # read color of each vertex
  edge_data = read.table(edge_file) # read edge file
  g <- graph_from_data_frame(edge_data)
  V(g)$color <- as.vector(color_data)
}
# load the data graph(target graph)
data_graph <- read_graph_file("WordNet/WordNet.edge.txt", "WordNet/WordNet.vertex.txt")
# load the query graph(pattern graph)
query_graph <- read_graph_file("query/edge.txt", "query/vertex.txt")
# call subgraph isomorphism API
count_subgraph_isomorphisms(pattern=query_graph, target=data_graph, method="vf2")
# get the list of all subgraphs
subgraph1 <- subgraph_isomorphisms(pattern=query_graph, target=data_graph, method="vf2")

In the previous code, igraph found 4,294 subgraphs. There are 4 extra subgraphs who appear in the target graph and are isomorphic to the pattern graph, but igraph failed to find them.

It is a little wierd to see the result since igraph find most of the subgraphs, but it failed to find some specific subgraph.

I have compressed all the graph files and the R source code file in a zip file.Please download that zip file from the following link zip file

Steps to reproduce the bug:

1. Uncompress the zip file.
2. Open an R session and make the top directory in the uncompressed directory as the working directory.
3. Run the "Count_Isomorphism.R"
4. See the printed result. A undump text file is stored in `igraph-result.csv'.

There are 4 subgraphs missing in the igraph's result file. The 4 subgraphs are:

18,18372,1
26546,18372,1
18372,26546,1
18372,16,1

Would you like to check it?

Thank you very much :-)

[szhorvat]

@wangzk Do you still have the test data for this?

[szhorvat]

Closing, since we cannot reproduce this without test data. I wonder if the problem was due to non-simple graphs.