This is the implementation of paper "GFinder: Approximate attributed subgraph matching".
History: At the begining, the algorithm was named FastDynamic and I submitted the paper to Ijcai, but it was rejected by Ijcai. Then, I renamed the algorithm to GLooker, and submitted it to CIKM, but it was rejected again. Finally, I renamed the algorithm to GFinder, and the paper was accepted.
If you have anyquestion about the algorithm, please open an issue.
Updated 2020-Dec-12. Another version of G-Finder which can support edge type similarity can be found at https://github.com/lihuiliullh/GFinder-Proj It contains some docx which tell details of how to run G-Finder. Its test data can also be used here.
This Project (G-Looker) is implemented on visual studio C++ 2015, windows 10 64 bits. Some sample data files are stored in direcotry "./testdata"
Usage:
You can use visual studio to open the project, and run the project.
--or
If you want to run G-Looker, use the command like this:
FastDynamic.exe data_file_name query_file_name top-k node-miss-cost intermediate-vertex-cost edge-miss-cost hop-number
For example:
.\FastDynamic.exe C:\flickr.txt.format C:\query_noise_7.txt.format 10 30 10 10 0
data_file_name: The data file query_file_name: The query file top-k: how many results you would like to find. node-miss-cost: missing node cost used in loss function (see our paper for more details) intermediate-vertex-cost: intermediate vertex cost used in loss function (see our paper for more details) edge-miss-cost: missing edge cost used in loss function (see our paper for more details) hop-number: if hop-number == 0, means 2 hop. If hop-number >=1 means 1 hop.
For example:
.\FastDynamic.exe C:\flickr.txt.format C:\query_noise_7.txt.format 10 30 10 10 0 (use two-hop distance)
.\FastDynamic.exe C:\flickr.txt.format C:\query_noise_7.txt.format 10 30 10 10 1 (use one-hop distance)
.\FastDynamic.exe C:\flickr.txt.format C:\query_noise_7.txt.format 10 30 10 10 2 (use one-hop distance)
Explaination of the data format
t 1 5
v 0 1
v 1 1
v 2 3
v 3 2
v 4 2
e 0 1 0,1;0,1
e 0 4 1,1;1,1
e 1 2 2,1;2,1
e 2 3 0,1;0,1
e 3 4 0,1;0,1
Explaination
t denotes the start of a graph
1 is the graph, starts from 1
5 means there are 5 nodes in the graph
v x y
v means it is a node
x is the node id, starts from 0
y is the node label, starts from 1
edge label starts from 0
e x y a1,b1,a2,b2,...;n1,m1,n2,m2,...
e means this is an edge
x is the source node id
y is the target node id
a1,b1,a2,b2,... means there are b1 edges from x to y with edge label a1, there are b2 edges from x to y with edge label a2 and so on.
n1,m1,n2,m2,... means there are m1 edges from y to x with edge label n1, there are m2 edges from y to x with edge label n2 and so on.
For example,
e 0 1 0,1;0,1 means there is 1 edge from node0 to node1 with label 0, and 1 edge from node1 to node0 with label 0
e 1 2 2,1;2,1 means there is 1 edge from node1 to node2 with label 2, and 1 edge from node2 to node1 with label 2