Timezone: »
Graph Similarity Computation (GSC) is essential to wide-ranging graph applications such as retrieval, plagiarism/anomaly detection, etc. The exact computation of graph similarity, e.g., Graph Edit Distance (GED), is an NP-hard problem that cannot be exactly solved within an adequate time given large graphs. Thanks to the strong representation power of graph neural network (GNN), a variety of GNN-based inexact methods emerged. To capture the subtle difference across graphs, the key success is designing the dense interaction with features fusion at the early stage, which, however, is a trade-off between speed and accuracy. For slow learning of graph similarity, this paper proposes a novel early-fusion approach by designing a co-attention-based feature fusion network on multilevel GNN features. To further improve the speed without much accuracy drop, we introduce an efficient GSC solution by distilling the knowledge from the slow early-fusion model to the student one for fast inference. Such a student model also enables the offline collection of individual graph embeddings, speeding up the inference time in orders. To address the instability through knowledge transfer, we decompose the dynamic joint embedding into the static pseudo individual ones for precise teacher-student alignment. The experimental analysis on the real-world datasets demonstrates the superiority of our approach over the state-of-the-art methods on both accuracy and efficiency. Particularly, we speed up the prior art by more than 10x on the benchmark AIDS data.
Author Information
Can Qin (Northeastern University)
Handong Zhao (Adobe Research)
Lichen Wang (Northeastern University)
Huan Wang
Yulun Zhang (ETH Zürich)
Yun Fu (Northeastern University)
More from the Same Authors
-
2021 Spotlight: Aligned Structured Sparsity Learning for Efficient Image Super-Resolution »
Yulun Zhang · Huan Wang · Can Qin · Yun Fu -
2021 : User-in-the-Loop Named Entity Recognition via Counterfactual Learning »
Tong Yu · Junda Wu · Ruiyi Zhang · Handong Zhao · Shuai Li -
2021 Poster: Aligned Structured Sparsity Learning for Efficient Image Super-Resolution »
Yulun Zhang · Huan Wang · Can Qin · Yun Fu -
2021 Poster: Learning to Generate Realistic Noisy Images via Pixel-level Noise-aware Adversarial Training »
Yuanhao Cai · Xiaowan Hu · Haoqian Wang · Yulun Zhang · Hanspeter Pfister · Donglai Wei -
2021 Poster: UniDoc: Unified Pretraining Framework for Document Understanding »
Jiuxiang Gu · Jason Kuen · Vlad I Morariu · Handong Zhao · Rajiv Jain · Nikolaos Barmpalios · Ani Nenkova · Tong Sun -
2020 Poster: Learning to Mutate with Hypergradient Guided Population »
Zhiqiang Tao · Yaliang Li · Bolin Ding · Ce Zhang · Jingren Zhou · Yun Fu -
2020 Poster: Neural Sparse Representation for Image Restoration »
Yuchen Fan · Jiahui Yu · Yiqun Mei · Yulun Zhang · Yun Fu · Ding Liu · Thomas Huang -
2020 Poster: Self-Supervised Relationship Probing »
Jiuxiang Gu · Jason Kuen · Shafiq Joty · Jianfei Cai · Vlad I. Morariu · Handong Zhao · Tong Sun -
2019 Poster: PointDAN: A Multi-Scale 3D Domain Adaption Network for Point Cloud Representation »
Can Qin · Haoxuan You · Lichen Wang · C.-C. Jay Kuo · Yun Fu -
2017 Poster: Matching on Balanced Nonlinear Representations for Treatment Effects Estimation »
Sheng Li · Yun Fu -
2012 Poster: Fast Resampling Weighted v-Statistics »
Chunxiao Zhou · jiseong Park · Yun Fu -
2012 Spotlight: Fast Resampling Weighted v-Statistics »
Chunxiao Zhou · jiseong Park · Yun Fu