PLACE: Prompt Learning for Attributed Community Search in Large Graphs

Attributed Community Search (ACS) aims to identify communities in an attributed graph with structural cohesiveness and attribute homogeneity for given queries. While algorithmic approaches often suffer from structural inflexibility and attribute irrelevance, recent years have witnessed a boom in learning-based approaches that employ Graph Neural Networks (GNNs) to simultaneously model structural and attribute information. To improve GNN efficacy and efficiency, these approaches adopt various techniques to refine the input graph and queries, including query-dependent node pruning and feature enhancement. However, these refinements are either detached from the end-to-end optimization with the backbone model, or impose additional burdens on training resources, limiting their adaptability and practical usage in diverse graphs. In this paper, we propose PLACE(Prompt Learning for Attributed Community Search), a graph prompt learning framework for ACS. Inspired by prompt-tuning in Natural Language Processing (NLP), PLACE constructs a query-specific prompt graph consisting of learnable attribute tokens and virtual node tokens, and inserts it into the original graph to form a prompt-augmented graph. The learned prompt tokens act as a bridge that enriches the query context within the graph, enabling the GNN to more effectively capture patterns of structural cohesiveness and attribute similarity pertinent to each query. We employ an alternating training paradigm to jointly optimize the prompt parameters and the GNN, and design a divide-and-conquer strategy that scales PLACEto million-scale graphs. Extensive experiments on 9 real-world graphs across 3 types of ACS queries demonstrate that PLACE outperforms 6 baselines, achieving an average F1 improvement of 14% over the state-of-the-art.