汪润中-机器学习与传统算法融合的图相似度求解

1 .机器学习与传统算法融合的图相似度求解 Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. To appear in CVPR 2021. 汪润中 2021/3/25 runzhong.wang@sjtu.edu.cn Runzhong Wang1 Tianqi Zhang1 Tianshu Yu2 Junchi Yan1 Xiaokang Yang1 1 Shanghai Jiao Tong University 2 Arizona State University 

2 . Runzhong Wang - 汪润中 📧📧 runzhong.wang@sjtu.edu.cn 🏠🏠 http://runzhong.wang • second year PhD student of Wen-Tsün Wu Honorable Class • AI Institute & Department of CSE, Shanghai Jiao Tong University (SJTU) • Supervisors: • Prof. Xiaokang Yang (杨小康) • Prof. Junchi Yan (严骏驰) Research interests: • Combinatorial Optimization • Graphs • Related Machine Learning methods Currently working on: • Deep learning on combinatorial problems e.g. graph matching 

3 . Publications • [CVPR 2021] Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. Runzhong Wang, Tianqi Zhang, Tianshu Yu, Junchi Yan, Xiaokang Yang. • [NeurIPS 2020] Graduated Assignment for Joint Multi-Graph Matching and Clustering with Application to Unsupervised Graph Matching Network Learning. Runzhong Wang, Junchi Yan, Xiaokang Yang. • [TPAMI 2020] Combinatorial Learning of Robust Deep Graph Matching: an Embedding based Approach. Runzhong Wang, Junchi Yan, Xiaokang Yang. • [ICLR 2020] Learning deep graph matching with channel-independent embedding and Hungarian attention. Tianshu Yu, Runzhong Wang, Junchi Yan, Baoxin Li. • [ICCV 2019 (oral)] Learning Combinatorial Embedding Networks for Deep Graph Matching. Runzhong Wang, Junchi Yan, Xiaokang Yang. • [ICCV 2019] InstaBoost: Boosting Instance Segmentation via Probability Map Guided Copy-Pasting. *Hao-shu Fang, *Jianhua Sun, *Runzhong Wang, Minghao Gou, Yong-Lu Li, Cewu Lu. 

4 .Graph Matching e 1 c d 2 4 b 3 5 a f Graph matching finds node correspondence among graphs. 4 

5 . Graph Matching Off-diagonal elements Affinity Matrix encodes both node- edge-edge similarity node and edge-edge affinity: e 1 c d 2 4 node-node similarity b 3 5 a f Diagonal elements 5 keypoints 6 keypoints Formulated as quadratic assignment problem (QAP): 𝑇𝑇 vec( 𝐗𝐗 ) max vec 𝐗𝐗 𝐊𝐊 𝐗𝐗 30 × 30 matrix s. t. 𝐗𝐗 ∈ 0,1 5×6 , 𝐗𝐗𝐗𝐗 = 𝟏𝟏, 𝐗𝐗 𝐓𝐓 𝟏𝟏 ≤ 𝟏𝟏 𝐊𝐊 (30 = 5 × 6) NP-Hard 5 

6 .Pattern Recognition Problems Malware Detection Image Matching Graph Edit Distance 

7 .Combinatorial Optimization Problems • Circuit Layout: Minimize overall wiring length • Facility Layout: Minimize distance × traffic 7 

8 . Graph Similarity Measurement 2,6-甲氧基苯基 苯甲基 Penicillin (青霉素) Methicillin (甲氧西林) If two molecules are similar, they probably have similar chemical properties. How to measure the similarity? 8 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

9 . Graph Edit Distance Input Graphs: 𝓖𝓖𝟏𝟏 𝓖𝓖𝟐𝟐 Graph Edit Distance, GED: An edit path 删边 删边 删点 𝓖𝓖𝟏𝟏 𝓖𝓖𝟐𝟐 代价=1 代价=1 代价=1 GED(𝓖𝓖𝟏𝟏 , 𝓖𝓖𝟐𝟐 ) = 3 9 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

10 . A Matching View of Graph Edit Distance Input Graphs: 𝓖𝓖𝟏𝟏 𝓖𝓖𝟐𝟐 Graph Edit Distance, GED: Unmatched Cost = 3 𝓖𝓖𝟏𝟏 𝓖𝓖𝟐𝟐 GED(𝓖𝓖𝟏𝟏 , 𝓖𝓖𝟐𝟐 ) = 3 Matched Cost = 0 Equivalent with the “edit path” definition. 10 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

11 . What if Matching is Wrong… Input Graphs: 𝓖𝓖𝟏𝟏 𝓖𝓖𝟐𝟐 Graph Edit Distance, GED: 𝓖𝓖𝟏𝟏 𝓖𝓖𝟐𝟐 Unmatched Cost = 4 Matched Cost = 1 GED(𝓖𝓖𝟏𝟏 , 𝓖𝓖𝟐𝟐 ) = 5 > Optimal GED(𝓖𝓖𝟏𝟏 , 𝓖𝓖𝟐𝟐 ) = 3 11 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

12 . GED: A Combinatorial Optimization Problem Graph Edit Distance finds the optimal edit path with minimal edit cost. Computing GED is NP-Complete. ：All possible edit paths : Cost of edit operation 𝑒𝑒𝑖𝑖 12 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

13 . A Visualization Example Only geometric information are used to build graphs. similar graphs unsimilar graph 13 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

14 . GNN-based Graph Similarity Learning graph vectors Pros: pooling • Fast • Accurate propagation Cons: intra-graph cross-graph intra-graph propagation propagation • Do not provide the edit path propagation • Not reliable: What if the model fails? input graphs 14 Y. Li, C. Gu, T. Dullien, O. Vinyals, P. Kohli. Graph Matching Networks for Learning the Similarity of Graph Structured Objects. In ICML 2019. 

15 . Traditional Approach: A* Algorithm The key of A* Algorithm 15 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

16 . A* Search Tree Root 1 node is … matched 2 nodes are … matched The search tree grows … exponentially 16 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

17 . To Reduce the Search Tree of A* Can be exactly computed very fast Cannot be exactly computed Intuitively: If ℎ 𝑝𝑝 is accurate, the search tree can be reduced. Traditional algorithm: compute ℎ 𝑝𝑝 by heuristic. 17 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

18 . To Reduce the Search Tree of A* Can be exactly computed very fast Cannot be exactly computed If ℎ 𝑝𝑝 ≤ ℎ 𝑝𝑝 𝑜𝑜𝑜𝑜𝑜𝑜 , then A* guarantees to find the optimum. 18 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

19 . The Best of Two Worlds: Compute ℎ(𝑝𝑝) in A* by Neural Network Input graphs Output ℎ(𝑝𝑝) We break the optimal guarantee ℎ 𝑝𝑝 ≤ ℎ 𝑝𝑝 𝑜𝑜𝑜𝑜𝑜𝑜 for time efficiency. 19 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

20 . Graph Convolution Network Mainly inspired by Graph Convolutional Network (GCN) Kipf and Welling, “Semi-Supervised Classification with Graph Convolutional Networks.” ICLR 2017. Feature aggregated from adjacent nodes. 𝑓𝑓𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑓𝑓𝑚𝑚𝑚𝑚𝑚𝑚 𝑓𝑓𝑚𝑚𝑚𝑚𝑚𝑚 updated node 𝑓𝑓𝑚𝑚𝑚𝑚𝑚𝑚 adjacent node aggregation path 𝑓𝑓𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 and 𝑓𝑓𝑚𝑚𝑚𝑚𝑚𝑚 are neural networks and weight-sharing among all nodes. 20 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

21 . Graph Convolution Mainly inspired by Graph Convolutional Network (GCN) Kipf and Welling, “Semi-Supervised Classification with Graph Convolutional Networks.” ICLR 2017. Feature aggregated from adjacent nodes. 𝑓𝑓𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑓𝑓𝑚𝑚𝑚𝑚𝑚𝑚 updated node 𝑓𝑓𝑚𝑚𝑚𝑚𝑚𝑚 adjacent node 𝑓𝑓𝑚𝑚𝑚𝑚𝑚𝑚 aggregation path 𝑓𝑓𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 and 𝑓𝑓𝑚𝑚𝑚𝑚𝑚𝑚 are neural networks and weight-sharing among all nodes. 21 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

22 . Graph Convolution Mainly inspired by Graph Convolutional Network (GCN) Kipf and Welling, “Semi-Supervised Classification with Graph Convolutional Networks.” ICLR 2017. Feature aggregated from adjacent nodes. 𝑓𝑓𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑓𝑓𝑚𝑚𝑚𝑚𝑚𝑚 updated node 𝑓𝑓𝑚𝑚𝑚𝑚𝑚𝑚 adjacent node aggregation path 𝑓𝑓𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 and 𝑓𝑓𝑚𝑚𝑚𝑚𝑚𝑚 are neural networks and weight-sharing among all nodes. 22 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

23 . Efficiency Issue with GCN Assume we have There are 19 states to matched two nodes: explore: • 19 ℎ(𝑝𝑝) to compute • A naïve approach: forward pass for 19 times • More time-efficient way? 23 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

24 . Time-Efficient Dynamic Embedding We borrow the idea from dynamic programming: 1) Cache & reuse intermediate results 2) Prune unnecessary branches 24 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

25 . Experiment Results 三个真实数据集上图编辑距离的精度指标 分子 二进制程序图 图像 机器学习引导的算法保持了传统求解器的高精度 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

26 . Better Efficiency via GNN 传统算法 vs GNN引导算法：遍历搜索树的规模 传统算法 vs GNN引导算法：求解时间 26 Rrunzhong Wang, J. Yan, X. Yang. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR 2021. 

27 .此处请输出出处和引用 27 

28 .Thank you! Q&A