Graph Matching Networks for Learning the Similarity of Graph Structured Objects

https://arxiv.org/abs/1904.12787

by bookofjoe • 7 years ago

117 6 7 years ago

jboggan• 7 years ago

For context, determining if two graphs are isomorphic is NP-complete.

firebatpi• 7 years ago

Graph isomorphism is actually not known to be NP-complete. Many complexity theorists believe it isn't, since if it is, then the polynomial hierarchy collapses.

dnlgl• 7 years ago

It is already all but known to be quasi-polynomial, thanks to László Babai: https://www.quantamagazine.org/graph-isomorphism-vanquished-...

salty_biscuits• 7 years ago

Also approximate matching via spectral methods is polynomial. You basically take eigendecomposition of graph adjacency matrix and take inner product of eigenvectors, because spectrum is invariant under permutation of node labels. Works well on noise free and large graphs, because you are unlikely to be unlucky enough to land on isospectral graphs.

jcims• 7 years ago

I'm imagining a number of use cases for something like this in the information security domain but don't know enough about graph theory to chew into this paper. Would it be possible to do something like k-means with this to identify patterns in existing graphs as well?

xvilka• 7 years ago

Thanks! Looks quite interesting. Hopefully better seamless GNN support in Julia's FluxML[1].

[1] https://github.com/FluxML/Flux.jl/issues/625

Graph Matching Networks for Learning the Similarity of Graph Structured Objects

Related Stories