240715_Thuy_Labseminar[SeedGNN: Graph Neural Network for Supervised Seeded Graph Matching].pptx

SeedGNN: Graph Neural Network for Supervised Seeded Graph Matching

1. SeedGNN: Graph Neural Network for Supervised Seeded Graph Matching Van Thuy Hoang Network Science Lab Dept. of Artificial Intelligence The Catholic University of Korea E-mail: [email protected] 2024-07-15 ICML 23

2. Problem: Graph matching Graph matching techniques have been applied to the following applications: Matching between movie segments and synopsis paragraphs. https://openaccess.thecvf.com/content_ICCV_2019/papers/Xiong_A_Graph-Based_Framework_to_Bridge_Movies_and_Synopses_ICCV_2019_paper.pdf

3. Problem: Graph matching Graph matching techniques have been applied to the following applications Image correspondence https://openaccess.thecvf.com/content_ICCV_2019/papers/Xiong_A_Graph-Based_Framework_to_Bridge_Movies_and_Synopses_ICCV_2019_paper.pdf

4. Problem: Graph matching Molecules matching https://openaccess.thecvf.com/content_ICCV_2019/papers/Xiong_A_Graph-Based_Framework_to_Bridge_Movies_and_Synopses_ICCV_2019_paper.pdf

5. Illustration of GNN-based graph similarity learning Problem For graph similarity prediction mainly employ GNNs to learn graph representations and leverage the learned representations into CNNs for predicting similarity scores, which is approached as a classification or regression problem. Fully connected layers are often added for the similarity score prediction in an end-to-end learning framework. Bai Y, Xu D, Gu K, Wu X, Marinovic A, Ro C, Sun Y, Wang W (2019b) Neural maximum common subgraph detection with guided subgraph extraction. https://openreviewnet/pdf?id=BJgcwh4FwS

6. Problem: seeded graph matching Problem Goal : find the mapping between unmatched nodes using seeds 1 Pre-matched nodes (seeds) Unmatched nodes 𝐺1 𝐺2 Applications : computer vision, social network de-anonymization, computational biology, and natural language processing …

7. GNNs for seeded graph matching Problem SeedGNN Supervised learning Learn to use seeds

8. Architecture Two components Convolution module aggregates neighboring information near the node pair Percolation module filters out noisy information Combining these two modules allows adaptive feature choosing

9. Architecture Convolution Module Given two graphs Injective mapping π : V1 → V2 Training set : Flatten(·) to denote the matrix reshape operation that converts a n1 × n2 × d matrix to a matrix of n1n2 × d, where the (i, j, :)-th entry of the input matrix is the ((i−1)n2 +j, :)-th entry of the output matrix seeded relationship as inputs:

10. Architecture Convolution Module Taking the seed encoding vector s1 as input, the counting of 1-hop witnesses can be written as Likewise, we may further compute the l-hop witness-like information hl in the l-th layer of our SeedGNN as:

11. Architecture Convolution Module For computation : update function ϕ is implemented as a K-layer neural network: The k-th layer of ϕl can be formulated as :

12. Architecture Percolation Module To match highconfidence nodes at one layer and to propagate the matched entries correspond to true (resp. fake) pair To obtain a similarity matrix in the l-th layer by mapping the node-pair representations ml to a 1-dimension vector, which is:

13. Architecture Convolution Module The matching result by Hungarian algorithm

14. Architecture Convolution Module The witness like information and new seeds computed by each layer Loss Function :

15. Experimental results Performance comparison Observation: The iterative 2-hop algorithm has the best performance for sparse graphs (p = 0.01) SeedGNN is capable of choosing the right features automatically to match different types of graphs.

16. Experiments Problem Comparison of GNN methods on SHREC’16 dataset. Provided with only a very small fraction of seeds (θ = 0.01), our SeedGNN can significantly outperform the semi-supervised methods.

17. Discussion and Conclusion Problem: Graph matching Findings: Convolution module aggregates neighboring information near the node pair Percolation module filters out noisy information Combining these two modules allows adaptive feature choosing Limitations: Only consider using topological structure in our SeedGNN. Compared to non-learning methods, SeedGNN requires additional training process and higher computational complexity.