GMN of AI medicine article interpretation

Graph Matching Networks for Learning the Similarity of Graph Structured Objects

Abstract

Graph embedding and efficient similarity reasoning

• GNN It has become an effective model for various supervised prediction problems defined on structured data , We demonstrate how to train graph neural networks （GNN）, It can generate graph embedding in vector space , So as to achieve effective similarity reasoning

A new graph matching network model

• Take a pair of graphs as input , Through a new method based on cross-graph attention The matching mechanism of , Through the joint reasoning of the graph , Calculate the similarity between them

Experimental proof

• The challenging problem of functional similarity search based on control flow graph

introduction

Figure introduction to neural network

Solve the similarity problem

• Used to solve vulnerability checking of binary functions
• Flow chart comparison of binary functions

Put forward GNN

• Embedding a graph into a vector space

  • Learn to embed models

    • Similar graphs are closer to each other in vector space

  • Each graph is independently mapped to an embedded vector , And then all the similarity calculations are done in vector space

  • therefore

    • Embedding of graphs in large databases can be precomputed and indexed , This enables us to use fast nearest neighbor search for efficient retrieval

GNN An extension of

• Graph matching network （GMNs）

  • For similarity learning
  • adopt cross-graph attention The mechanism calculates the similarity score , To correlate nodes across graphs and identify differences
  • By making the representation of the graph more dependent on “ Pairs of graphs ”, The matching model is more powerful than the embedded model , Provides a good accuracy calculation tradeoff .

Experimental proof

• A composite graph that captures structural similarity edit-distance Learning tasks
• The practical task of reasoning about structural similarity and semantic similarity

related work

GNN And the graph shows learning

Graph similarity and graph Kernels

• Graph kernels

  • Used to measure the similarity of graphs , But it needs better design kernels

Distance measurement learning

• Early work on metric learning mostly assumed that data already existed in vector space , And only the linear metric matrix can correctly measure the distance in this space , To group similar examples together , The different examples are far apart

Siamese The Internet

• Subtheme 1

graph hashes

• Artificially designed hash function ; Good at accurate matching , But not good at estimating similarity

Methods

graph embedding model

• Independent embeddings

  • encoder

    • Add points and edges ,map To the hidden space

      • Use MLP

  • GNN

    • Through the whole picture , Flow information
    • Calculation node representation： Coding local adjacency matrix information, etc
    • Point can integrate all information

  • obtain graph representations

    • hG
    • further MLPG( MLP())

• Calculated distance ,distance

  • European distance or Hamming distance

graph matching networks (GMNs)

• Main idea

  • Calculate the similarity score , by a pair of graphs jointly on the pair
  • Calculate... For each graph representation （jonitly on the pair)

• message passing Step and embedding model Different

  • Not only from graph Get information in , Also get information from the graph （ appear other graph Of all node）

• Calculate the information in the diagram , similar embedding model

• Calculate... In a graph each node And all the nodes of another graph attend

  • Calculate the attention

• Calculate the information between graphs

  • Combine all of the attention weights node representation And , Then take a different

• Algorithm implementation

  • a few similar function
  • cross-graph attention
  • Graph matching layer and graph matching networks

Training

• labeled data examples
• training on pairs
• training on triplets

Dataset

Task

• The graph edit distance task

Reference link

Graph Matching Networks for Learning the Similarity of Graph Structured Objects
https://arxiv.org/abs/1904.12787