In this work, we are interested in the large graph similarity computation problem , which is one of the most important graph-based problems. Traditional techniques to compute the exact or approximate values of Graph Edit Distance (GED) and Maximum Common Subgraph (MCS) require at least polynomial time complexity over node numbers thus are not able to handle this problem when the numbers of nodes are large . Recently the develop of deep learning techniques provide a promising solution for this problem by training a network which is able to encode graphs to  feature vectors and then compute similarity based on feature vectors. However, when we look into these techniques and classify them to embedding models and matching models , problems arise . Embedding models can be quite fast but perform poorly due to the lack of interaction across graphswhile matching models involve this for much better performance but satisfy far more on time consumption . Similar to the process of large biological molecular identification , where we first maps the whole molecular to molecular groups and then identify them based on the "abstracted smaller molecular", the feature aggregation across two whole graphs is always redundant, especially when the number of nodes is large. Thus we here present a novel framework for large graph similarity computation problem. We first embed and coarsen the large graphs to "abstracted smaller graphs " with denser local topology , similar to molecular groups in biological concept. Then we aggregate both the internal features in "abstracted smaller graphs " and external features across "abstracted smaller graph pair", leading to feature vectors for each graph, with which we calculate the final similarity score. Experiments demonstrate that our proposed framework outperforms state-of-the-art methods in graph similarity computation tasks and has significant improvement in time efficiency .
In this work, we focus on large graph similarity computation problem and propose a novel ``embedding-coarsening-matching'' learning framework, which outperforms state-of-the-art methods in this task and has significant improvement in time efficiency. Graph similarity computation for metrics such as Graph Edit Distance (GED) is typically NP-hard, and existing heuristics-based algorithms usually achieves a unsatisfactory trade-off between accuracy and efficiency . Recently the development of deep learning techniques provides a promising solution for this problem by a data-driven approach which trains a network to encode graphs to their own feature vectors and computes similarity based on feature vectors. These deep-learning methods can be classified to two categories, embedding models and matching models . Embedding models such as GCN-Mean and GCN-Max, which directly map graphs to respective feature vectors, run faster but the performance is usually poor due to the lack of interactions across graphs. Matching models such as GMN, whose encoding process involves interaction across the two graphs, are more accurate but interaction between whole graphs brings a significant increase in time consumption (at least quadratic time complexity over number of nodes). Inspired by large biological molecular identification where the whole molecular is first mapped to functional groups and then identified based on these functional groups, our ``embedding-coarsening-matching'' learning framework first embeds and coarsens large graphs to coarsened graphs with denser local topology and then matching mechanism is deployed on the coarsened graphs for the final similarity scores. Detailed experiments have been conducted and the results demonstrate the efficiency and effectiveness of our proposed framework .
R
are interested in the
focus on
R
, which is one of the most important graph-based problems. Traditional techniques to compute the exact or approximate values of Graph
and propose a novel ``embedding-coarsening-matching'' learning framework, which outperforms state-of-the-art methods in this task and has significant improvement in time efficiency. Graph similarity computation for metrics such as Graph
R
and Maximum Common Subgraph (MCS) require at least polynomial time complexity over node numbers thus are not able to handle this problem when the numbers of nodes are large
is typically NP-hard, and existing heuristics-based algorithms usually achieves a unsatisfactory trade-off between accuracy and efficiency
R
develop
development
R
provide
provides
R
training a network which is able
a data-driven approach which trains a network
A
their own
R
then compute
computes
R
However, when we look into these techniques and classify them to
These deep-learning methods can be classified to two categories,
D
, problems arise
R
can be quite fast but perform poorly
such as GCN-Mean and GCN-Max, which directly map graphs to respective feature vectors, run faster but the performance is usually poor
R
interaction across graphswhile matching models involve this for much better performance but satisfy far more on time consumption . Similar to the process of
interactions across graphs. Matching models such as GMN, whose encoding process involves interaction across the two graphs, are more accurate but interaction between whole graphs brings a significant increase in time consumption (at least quadratic time complexity over number of nodes). Inspired by
R
, where we first maps
where
R
to molecular
is first mapped to functional
R
identify them based on the "abstracted smaller molecular", the feature aggregation across two whole graphs is always redundant, especially when the number of nodes is large. Thus we here present a novel framework for large graph similarity computation problem. We first embed and coarsen the
identified based on these functional groups, our ``embedding-coarsening-matching'' learning framework first embeds and coarsens
R
"abstracted smaller graphs "
coarsened graphs
R
, similar to molecular groups in biological concept. Then we aggregate both the internal features in "abstracted smaller graphs " and external features across "abstracted smaller graph pair", leading to feature vectors for each graph, with which we calculate
and then matching mechanism is deployed on the coarsened graphs for
R
score. Experiments demonstrate that
scores. Detailed experiments have been conducted and the results demonstrate the efficiency and effectiveness of
D
outperforms state-of-the-art methods in graph similarity computation tasks and has significant improvement in time efficiency