<p>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, <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\textsf{IACS}^{+}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi mathvariant="sans-serif">IACS</mi> <mo>+</mo> </msup> </math></EquationSource> </InlineEquation>, based on inductive learning, which can infer new queries for different communities and graphs. Specifically, <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\textsf{IACS}^{+}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi mathvariant="sans-serif">IACS</mi> <mo>+</mo> </msup> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\textsf{IACS}^{+}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi mathvariant="sans-serif">IACS</mi> <mo>+</mo> </msup> </math></EquationSource> </InlineEquation>. Our approach <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\textsf{IACS}^{+}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi mathvariant="sans-serif">IACS</mi> <mo>+</mo> </msup> </math></EquationSource> </InlineEquation> achieves average absolute improvements of <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$29.96\%$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>29.96</mn> <mo>%</mo> </mrow> </math></EquationSource> </InlineEquation> in <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\textsf{F1}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="sans-serif">F</mi> <mn mathvariant="sans-serif">1</mn> </mrow> </math></EquationSource> </InlineEquation>-score for ACS tasks.</p>

$\textsf{IACS}^{+}$: Inductive Attributed Community Search via Learning across Graphs

期刊论文
发表日期：

2026年7月1日

查看全文

Ao Liu,
Shuheng Fang,
Kangfei Zhao,
Zhixun Li,
Jeffrey Xu Yu,
Zhiwei Zhang,
Guoli Yang,
Kaiyu Feng,
Ye Yuan,
Guoren Wang

摘要

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, $\textsf{IACS}^{+}$ ${IACS}^{+}$ , based on inductive learning, which can infer new queries for different communities and graphs. Specifically, $\textsf{IACS}^{+}$ ${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 $\textsf{IACS}^{+}$ ${IACS}^{+}$ . Our approach $\textsf{IACS}^{+}$ ${IACS}^{+}$ achieves average absolute improvements of $29.96\%$ $29.96 %$ in $\textsf{F1}$ $F 1$ -score for ACS tasks.

\(\textsf{IACS}^{+}\): Inductive Attributed Community Search via Learning across Graphs

摘要