Community search in heterogeneous graphs is fundamental to applications such as expert team formation and scholarly collaboration. Many existing studies leverage meta-paths, which are sequences of node and edge types, to capture semantic relationships in heterogeneous graphs. However, most of them only consider the existence of meta-path instances, overlooking their frequency and thus failing to capture relationship strength. This limitation can result in communities that include nodes with numerous but weak relations. To capture the strength of relationships in heterogeneous graphs, we define the Strong Community (StrCom) model, which evaluates the strength between users based on the number of connecting meta-path instances. Building upon this model, we further propose the Budgeted Strong Community (BSC) problem by incorporating a size constraint. We provide theoretical analyses showing that the BSC problem is NP-hard and not in APX. To address this problem, we design three strategies-Shrink, Expand, and Hybrid-along with several optimization techniques to improve efficiency. Extensive experiments on large real-world datasets (e.g., DBLP, YAGO, DBpedia) demonstrate the effectiveness and efficiency of our approach. Specifically, our method achieves 3.49-107.09× higher PathSim scores for StrCom and two to five orders of magnitude higher scores for BSC compared to state-of-the-art baselines, demonstrating that the identified communities are both semantically coherent and structurally compact.

Detecting anomaly edges for dynamic graphs aims to identify edges significantly deviating from the normal pattern and can be applied in various domains, such as cybersecurity, financial transactions and AIOps. With the evolving of time, the types of anomaly edges are emerging and the labeled anomaly samples are few for each type. Current methods are either designed to detect randomly inserted edges or require sufficient labeled data for model training, which harms their applicability for real-world applications. In this paper, we study this problem by cooperating with the rich knowledge encoded in large language models(LLMs) and propose a method, namely AnomalyLLM. To align the dynamic graph with LLMs, AnomalyLLM pretrains a dynamic-aware encoder to generate the representations of edges and reprograms the edges using the prototypes of word embeddings. Along with the encoder, we design an in-context learning framework that integrates the information of a few labeled samples to achieve few-shot anomaly detection. Experiments on four datasets reveal that AnomalyLlmcan not only significantly improve the performance of few-shot anomaly detection, but also achieve superior results on new anomalies without any update of model parameters.

System logs, recording critical information about system operations, serve as indispensable tools for system anomaly detection. Graph-based methods have demonstrated superior performance compared to other methods in capturing the interdependencies of log events. However, existing methods often neglect the complex substructure patterns of nodes within log graphs, making it challenging to capture the subtle alteration in event type, structure, and the location of exceptions that indicate node anomalies. To address this limitation, this paper proposes a novel framework called Substructure-aware Log Anomaly Detection at Code File Level (SLAD). It first introduces a Monte Carlo Tree Search strategy tailored specifically for log anomaly detection to discover representative substructures. Then, SLAD incorporates a substructure distillation way to enhance the efficiency of anomaly inference based on the representative substructures. After that, we introduce a soft pruning to obtain key substructure for nodes. Experimental results show SLAD outperforms all baselines. Particularly, SLAD demonstrates at least 15 times faster than substructure-based graph learning methods in anomaly inference.

The activities in many real-world applications, such as e-commerce and online education, are usually modeled as a dynamic bipartite graph that evolves over time. It is a critical task to detect anomalies inductively in a dynamic bipartite graph. Previous approaches either focus on detecting pre-defined types of anomalies or cannot handle nodes that are unseen during the training stage. To address this challenge, we propose an effective method to learn anonymous edge representation (AER) that captures the characteristics of an edge without using identity information. We further propose a model named AER-AD to utilize AER to detect anomalies in dynamic bipartite graphs in an inductive setting. Extensive experiments on both real-life and synthetic datasets are conducted to illustrate that AER-AD outperforms state-of-the-art baselines. In terms of AUC and F1, AER-AD is able to achieve 8.38% and 14.98% higher results than the best inductive representation baselines, and 6.99% and 19.59% than the best anomaly detection baselines.

The wide spread of rumors inflicts damages on social media platforms. Detecting rumors has become an emerging problem concerning the public and government. A crucial problem for rumors detection on social media is the lack of reliably pre-annotated dataset to train classification models. To solve this problem, we propose an unsupervised model that detects rumors by measuring how well the tweets follow the normal patterns. However, the problem is challenging in how to automatically discover the normal patterns of tweets. To tackle the challenge, we first propose a novel tree variational autoencoder model that reconstructs the sentiment labels along the propagation tree of a factual tweet. Then we propose a cross-alignment method to align the multiple modalities, i.e., tree structure and propagation features, and output the final prediction results. We conduct extensive experiments on a real-world dataset collected from Weibo. The experiments show that the proposed method significantly outperforms the state-of-the-art unsupervised methods and adapts better to the concept drift than state-of-the-art supervised methods.

Representing words as embeddings has been proven to be successful in improving the performance in many natural language processing tasks. Different from the traditional methods that learn the embeddings from large text corpora, ensemble methods have been proposed to leverage the merits of pre-trained word embeddings as well as external semantic sources. In this paper, we propose a knowledge-enriched ensemble method to combine information from both knowledge graphs and pre-trained word embeddings. Specifically, we propose an attention network to retrofit the semantic information in the lexical knowledge graph into the pre-trained word embeddings. In addition, we further extend our method to contextual word embeddings and multi-sense embeddings. Extensive experiments demonstrate that the proposed word embeddings outperform the state-of-the-art models in word analogy, word similarity and several downstream tasks. The proposed word sense embeddings outperform the state-of-the-art models in word similarity and word sense induction tasks.

With the proliferation of online social networks, a great deal of online user action data has been generated. Such data has enabled the study of information diffusion prediction, which is a fundamental problem for understanding the propagation of information on social media platforms. In diffusion prediction models, there are two standard components, i.e., a social graph and information diffusion cascades. We observe that both components exhibit latent hierarchical structures. However, most existing models are designed based on euclidean spaces, and hence cannot effectively capture complex patterns, especially hierarchical structures. Therefore, we investigate a novel research problem to learn hyperbolic representations for information diffusion prediction. To reflect the different characteristics of social graphs and diffusion cascades, we encode them into two latent hyperbolic spaces with different trainable curvatures. In addition, to model influence dependencies, we propose a co-attention mechanism to capture the processes of diffusion cascades using positional embeddings. Given a set of activated seed users, we jointly exploit diffusion cascades and social links to predict which users will be influenced. We conduct extensive experiments on four real-world datasets. Empirical results demonstrate that the proposed H-Diffu model significantly outperforms several state-of-the-art diffusion prediction frameworks.

Representing words as embeddings in a continuous vector space has been proven to be successful in improving the performance in many natural language processing (NLP) tasks. Beyond the traditional methods that learn the embeddings from large text corpora, ensemble methods have been proposed to leverage the merits from pre-trained word embeddings as well as external semantic sources. In this paper, we propose a knowledge-enhanced ensemble method to combine both knowledge graphs and pre-trained word embedding models. Specifically, we interpret relations in knowledge graphs as linear translation from one word to another. We also propose a novel weighting scheme to further distinguish edges in the knowledge graph with same type of relation. Extensive experiments demonstrate that our proposed method is up to 20% times better than state-of-the-art in word analogy task and up to 16% times better than state-of-the-art in word similarity task.

With the popularity of online educational platforms, English learners can learn and practice no matter where they are and what they do. English grammar is one of the important components in learning English. To learn English grammar effectively, it requires students to practice questions containing focused grammar knowledge. In this paper, we study a novel problem of retrieving English grammar questions with similar grammatical focus. Since the grammatical focus similarity is different from textual similarity or sentence syntactic similarity, existing approaches cannot be applied directly to our problem. To address this problem, we propose a syntactic based approach for English grammar question retrieval which can retrieve related grammar questions with similar grammatical focus effectively. In the proposed syntactic based approach, we first propose a new syntactic tree, namely parse-key tree, to capture English grammar questions’ grammatical focus. Next, we propose two kernel functions , namely relaxed tree kernel and part-of-speech order kernel, to compute the similarity between two parse-key trees of the query and grammar questions in the collection. Then, the retrieved grammar questions are ranked according to the similarity between the parse-key trees. In addition, if a query is submitted together with answer choices, conceptual similarity and textual similarity are also incorporated to further improve the retrieval accuracy . The performance results have shown that our proposed approach outperforms the state-of-the-art methods based on statistical analysis and syntactic analysis.