The wide use of abbreviated column names (derived from English words or Chinese Pinyin) in database tables poses significant challenges for table-centric tasks in natural language processing and database management.Such a column name expansion task, referred to as the NameGuess task, has previously been addressed by fine-tuning Large Language Models (LLMs) on synthetically generated rule-based data.However, the current approaches yield suboptimal performance due to two fundamental limitations: 1) the rule-generated abbreviation data fails to reflect real-world distribution, and 2) the failure of LLMs to follow the rulesensitive patterns in NameGuess persistently.For the data realism issue, we propose a novel approach that integrates a subsequence abbreviation generator trained on human-annotated data and collects non-subsequence abbreviations to improve the training set.For the rule violation issue, we propose a decoding system constrained on an automaton that represents the rules of abbreviation expansion.We extended the original English NameGuess test set to include non-subsequence and PinYin scenarios.Experimental results show that properly tuned 7/8B moderate-size LLMs with a refined decoding system can surpass the few-shot performance of state-of-the-art LLMs, such as the GPT-4 series.The code and data are presented in the supplementary material.

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.

Graph Neural Networks (GNNs) have achieved great success in various graph mining tasks. However, drastic performance degradation is always observed when a GNN is stacked with many layers. As a result, most GNNs only have shallow architectures, which limits their expressive power and exploitation of deep neighborhoods. Most recent studies attribute the performance degradation of deep GNNs to the over-smoothing issue. In this paper, we disentangle the conventional graph convolution operation into two independent operations: Propagation (P) and Transformation (T). Following this, the depth of a GNN can be split into the propagation depth (Dp) and the transformation depth (Dt). Through extensive experiments, we find that the major cause for the performance degradation of deep GNNs is the model degradation issue caused by large Dt rather than the over-smoothing issue mainly caused by large Dp. Further, we present Adaptive Initial Residual (AIR), a plug-and-play module compatible with all kinds of GNN architectures, to alleviate the model degradation issue and the over-smoothing issue simultaneously. Experimental results on six real-world datasets demonstrate that GNNs equipped with AIR outperform most GNNs with shallow architectures owing to the benefits of both large DD_p$ and Dt, while the time costs associated with AIR can be ignored.

Node mapping between large graphs (or network alignment) plays a key preprocessing role in joint-graph data mining applications like social link prediction, cross-platform recommendation, etc. Most existing approaches attempt to perform alignment at the granularity of entire graphs, while handling the whole graphs may lower the scalability and the noisy nodes/edges in the graphs may impact the effectiveness. From the observation that potential node mappings always appear near known corresponding nodes, we propose iMAP, a novel sub-graph expansion based alignment framework to incrementally construct meaningful sub-graphs and perform alignment on each sub-graph pair iteratively, which reduces the unnecessary computation cost in the original raw networks and improves effectiveness via excluding possible noises. Specifically, iMap builds a candidate sub-graph around known matched nodes initially. In each following iteration, iMap trains an alignment model to infer the node mapping relationship between sub-graphs, from which the sub-graphs are further extended and refined. In addition, we design a Graph Neural Network(GNN) based model named MAP on each sub-graph pair in the iMap framework. MAP utilizes trainable Multi-layer Perception (MLP) prediction heads for similarity computation and employs a mixed loss function consisting of the ranking loss for contrastive learning and the cross-entropy loss for classification. Extensive experiments conducted on real social networks demonstrate superior efficiency and effectiveness (above 12% improvement) of our proposed method compared to several state-of-the-art methods.

Building home assistant robots has long been a goal for vision and robotics researchers. To achieve this task, a simulated environment with physically realistic simulation, sufficient articulated objects, and transferability to the real robot is indispensable. Existing environments achieve these requirements for robotics simulation with different levels of simplification and focus. We take one step further in constructing an environment that supports household tasks for training robot learning algorithm. Our work, SAPIEN, is a realistic and physics-rich simulated environment that hosts a large-scale set of articulated objects. SAPIEN enables various robotic vision and interaction tasks that require detailed part-level understanding.We evaluate state-of-the-art vision algorithms for part detection and motion attribute recognition as well as demonstrate robotic interaction tasks using heuristic approaches and reinforcement learning algorithms. We hope that SAPIEN will open research directions yet to be explored, including learning cognition through interaction, part motion discovery, and construction of robotics-ready simulated game environment.