Subgraph matching, which aims to determine whether a query graph is a substructure of a target graph, is a crucial problem in various domains. However, subgraph matching is an NP-complete problem. Although prior studies have overcome the computational bottleneck as a supervised learning task, such methods are impractical for label-lacking real scenarios. Therefore, addressing the subgraph matching effectively under limited or without labels is still a key problem. To tackle this problem, we propose ADMatcher, a self-supervised Subgraph Matching method via Adaptive Dense-Aware Graph Contrastive Learning (GCL). We leverage GCL with adaptive augmentation and ensure the augmented graph is a subgraph of the original graph during augmentation stage to learn the subgraph relationship. Specifically, as traditional stochastic augmentations may severely damage the intrinsic properties, we add three dense subgraph augmentation strategies to aware internal useful information. Furthermore, since general data augmentations often use manually selecting strategies, we adopt a min-max optimization method that adaptively adjusts the proportions of different augmentation strategies. Eventually, we redesign the encoder and train the model without labels in self-supervised way. Experiments demonstrate that ADMatcher can outperform the supervised state-of-the-art method with uniformly distributed features, adaptively select better augmentation strategies, and achieve faster training and convergence.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

ADMatcher: Self-supervised Subgraph Matching via Adaptive Dense-Aware Graph Contrastive Learning

  • Hao Yan,
  • Lei Du,
  • Mengjiao Wang,
  • Xiangyu Song,
  • Yan Jia,
  • Liyi Zeng,
  • Zhaoquan Gu

摘要

Subgraph matching, which aims to determine whether a query graph is a substructure of a target graph, is a crucial problem in various domains. However, subgraph matching is an NP-complete problem. Although prior studies have overcome the computational bottleneck as a supervised learning task, such methods are impractical for label-lacking real scenarios. Therefore, addressing the subgraph matching effectively under limited or without labels is still a key problem. To tackle this problem, we propose ADMatcher, a self-supervised Subgraph Matching method via Adaptive Dense-Aware Graph Contrastive Learning (GCL). We leverage GCL with adaptive augmentation and ensure the augmented graph is a subgraph of the original graph during augmentation stage to learn the subgraph relationship. Specifically, as traditional stochastic augmentations may severely damage the intrinsic properties, we add three dense subgraph augmentation strategies to aware internal useful information. Furthermore, since general data augmentations often use manually selecting strategies, we adopt a min-max optimization method that adaptively adjusts the proportions of different augmentation strategies. Eventually, we redesign the encoder and train the model without labels in self-supervised way. Experiments demonstrate that ADMatcher can outperform the supervised state-of-the-art method with uniformly distributed features, adaptively select better augmentation strategies, and achieve faster training and convergence.