Denoising Diffusion Probabilistic Models (DDPMs) have recently demonstrated exceptional performance in generating high-quality data. In this work, we propose CommunityDF, a novel framework that applies DDPMs to the community search problem, which involves identifying subgraphs containing nodes closely related to a given query node. However, three key challenges arise in this context: (I) learning effective node representations from limited examples, (II) discretizing continuous node representations into community members, and (III) reducing the number of diffusion steps without sacrificing performance. To tackle these, CommunityDF introduces several innovations. First, we focus on subgraphs around the query node to reduce interference from unrelated nodes, improve scalability. We then employ a contrastive learning approach, treating node states at different diffusion steps as positive examples and designing various negative sampling strategies to learn high-quality node representations from limited examples. Second, we propose a dynamic thresholding mechanism that effectively converts continuous representations into community members. Finally, we reduce the number of diffusion steps by leveraging the rough communities to initialize the process with rough community structures, which accelerates convergence while maintaining high accuracy. Extensive experiments on seven real-world datasets demonstrate that CommunityDF outperforms existing methods by 16%-47%, establishing it as a state-of-the-art solution for community search. The source code is available at https://github.com/JiazunChen/CommunityDF.

Graph matching is a critical task with diverse real-world applications. Present cutting-edge methodologies incorporate graph neural architectures combined with incremental anchor refinement, calculating the matching similarity directly via node embeddings. The graph neural architectures provide enhanced encoding of both structural and attribute information, yielding more accurate results, and incremental anchor refinement contributes to the overall low complexity of these methods. However, this method of direct similarity calculation expects all neighboring nodes of one anchor to bear a resemblance in their embeddings to all neighbors of its counterpart. This requirement might obscure the distinctiveness of nodes within a localized region. Moreover, the integration of incorrectly identified anchor pairs during the incremental refinement process can significantly degrade subsequent matching performance. To tackle the challenges, we introduce a novel method, Deep Neighbor Matching (DeepNM), designed to explicitly measure the similarity between the neighborhoods of nodes, thereby functioning as a graph matching training loss. Further, we demonstrate that this similarity measurement, based on common neighbor statistics, is more resilient to inaccurately identified anchor pairs. Our comprehensive experiments on both synthetic and real-world datasets offer empirical evidence that DeepNM is compatible with the incremental graph matching paradigm and has outstanding performance. Graph matching is a critical task with diverse real-world applications. Current cutting-edge methodologies incorporate GNN (Graph Neural Network) combined with incremental anchor refinement, calculating the matching similarity directly via node embeddings. However, the direct similarity computation based on aggregated embeddings from GNN may obscure the distinctiveness of nodes within a localized region. In addition, the possible wrongly added anchor pairs in the iterations and the lack of capturing the relationships to anchors may further affect the performance. In order to tackle these challenges, this paper proposes a method named DeepNM, which attempts to find node matching based on their neighbors' similarities. Specifically, DeepNM introduces a Sinkhorn-based similarity on a node's neighborhood's embeddings, which serves as both a training loss and a matching metric tailored to the graph matching problem. Additionally, we demonstrate that the Sinkhorn-based similarity, which relies on common neighbor statistics, is highly resilient to inaccurately identified anchor pairs within the context of incremental graph matching. Our comprehensive experiments on synthetic and real-world datasets demonstrate that DeepNM, compatible with the incremental graph matching paradigm, excels particularly well at matching graphs where common neighbors provide good matches. Applying the DeepNM pipeline to real social networks results in a 6% improvement, and applying the Sinkhorn similarity on knowledge graphs results in an average improvement of 1.7% over the best baseline.

Example-based community search utilizes hidden patterns of given examples rather than explicit rules, reducing users' burden and enhancing flexibility. However, existing works face challenges such as low scalability, high training cost, and improper termination during the search. Aiming at tackling all these issues, this paper proposes a community search framework named CommunityAF with three well-designed components. The first is a GNN (graph neural network) component that combines community-aware structure features to incrementally learn node embeddings over a large graph for the other two components. The second is an autoregres-sive flow-based generation component designed for fast training and model stability. The third is a scoring component that evaluates the communities and provides scores for a stable termination. Moreover, to show that CommunityAF has the sufficient expressive power to cover the rules, we demonstrate that the scoring component with node features weighted by degree-related factors is able to mimic the existing structure-based community metrics. We introduce a square ranking loss to guide the training of the scoring component, and further devise a flexible termination strategy based on the inferred score change pattern over a sequence of candidate communities using beam search. We compare CommunityAF with four different categories of community search methods on six real-world datasets. The results illustrate that CommunityAF outperforms these community search methods, and achieves an average 15.3% improvement in effectiveness and 4x to 20x speedups on different datasets relative to the state-of-the-art generative method.

Community Search, which locates the desired sub-graph containing the query node, is a fundamental operation in network analysis. Most of the existing systems rely on pre-defined rules to find the community, while we argue that the target community is always specific for different purposes and the pre-defined rules may not be suitable. In this work, we demonstrate VICS-GNN, a Visual Interactive system for Community Search via graph Neural Network. VICS-GNN provides end users with a flexible, user-friendly front end to manage and explore the sub-graph around the query node, allows users labeling nodes to guide G NN models in learning community rules by combining content and structural features, and locates the community interactively and iteratively. In the demonstration, demo visitors will be invited to experience the VICS-GNN system using real-world data from Wikipedia and Sina Weibo to feel how convenient and intuitive it is to help with community search.

Searching a community containing a given query vertex in an online social network enjoys wide applications like recommendation, team organization, etc. When applied to real-life networks, the existing approaches face two major limitations. First, they usually take two steps, i.e. , crawling a large part of the network first and then finding the community next, but the entire network is usually too big and most of the data are not interesting to end users. Second, the existing methods utilize hand-crafted rules to measure community membership, while it is very difficult to define effective rules as the communities are flexible for different query vertices. In this paper, we propose an Interactive Community Search method based on Graph Neural Network (shortened by ICS-GNN) to locate the target community over a subgraph collected on the fly from an online network. Specifically, we recast the community membership problem as a vertex classification problem using GNN, which captures similarities between the graph vertices and the query vertex by combining content and structural features seamlessly and flexibly under the guide of users' labeling. We then introduce a k -sized Maximum-GNN-scores (shortened by kMG ) community to describe the target community. We next discover the target community iteratively and interactively. In each iteration, we build a candidate subgraph using the crawled pages with the guide of the query vertex and labeled vertices, infer the vertex scores with a GNN model trained on the subgraph, and discover the kMG community which will be evaluated by end users to acquire more feedback. Besides, two optimization strategies are proposed to combine ranking loss into the GNN model and search more space in the target community location. We conduct the experiments in both offline and online real-life data sets, and demonstrate that ICS-GNN can produce effective communities with low overhead in communication, computation, and user labeling.