IACS+: Inductive Attributed Community Search via Learning across Graphs

Attributed community search (ACS) aims to identify subgraphs satisfying both structural cohesiveness and attribute homogeneity in attributed graphs, given a query consisting of query nodes and query attributes. Previously, algorithmic approaches deal with ACS through a two-stage paradigm, which suffers from structural inflexibility and attribute irrelevance. To overcome these limitations, learning-based approaches have recently been proposed to learn both structures and attributes simultaneously as a one-stage paradigm. However, these approaches train a transductive model that assumes the graph used for inference on unseen queries is the same as the graph used for training. That limits the generalization and adaptation of these approaches to different heterogeneous graphs. In this paper, we propose a new framework, Inductive Attributed Community Search, IACS+, based on inductive learning, which can infer new queries for different communities and graphs. Specifically, IACS+ employs an encoder-decoder neural architecture to handle one ACS task at a time, where a task consists of a graph with only a few queries and their corresponding ground-truth. We design a three-phase workflow, ‘training, adaptation, inference & refinement’, that learns a shared model to absorb and induce prior effective common knowledge about ACS across different tasks. The shared model can then swiftly adapt to a new task with a small number of ground-truth labels. We conduct substantial experiments on 8 real-world datasets to verify the effectiveness of IACS+. Our approach IACS+ achieves average absolute improvements of 29.96% in F1-score for ACS tasks.