ADMatcher: Self-supervised Subgraph Matching via Adaptive Dense-Aware Graph Contrastive Learning
摘要
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.