Graph-level anomaly detection (GLAD) is a critical task to identify graphs with abnormal properties in various domains, ranging from fraudulent social networks to malicious botnets on online platforms. The dominant paradigm for existing GLAD detectors has been partially unsupervised, relying on training data composed exclusively of normal samples. However, this partially unsupervised paradigm inevitably requires a costly expert filtering process to ensure the training data is free of anomalies. This creates a significant gap between current approaches and the real-world necessity of a fully unsupervised paradigm, which involves training a model directly on real-world data ''as-is'', with its inherent mix of normal and anomalous samples. To bridge this gap, we incorporate uncertainty learning into GLAD to promote fully unsupervised learning. We propose two frameworks: Score Uncertainty Learning (SUL) and Graph-data Uncertainty Learning (GUL). Specifically, SUL enhances existing GLAD detectors by modeling uncertainty through Gaussian distributions over the detectors' predictions, adaptively attenuating the influence of potential anomalies. GUL is an end-to-end framework that iteratively optimizes anomaly detection and uncertainty modeling via an Expectation-Maximization algorithm. In addition, we develop a dedicated loss that utilizes potential anomalies to enhance the effectiveness and robustness of GUL. Empirical results on sixteen benchmark datasets, covering real-world graphs from social networks and online platforms, demonstrate the superiority of our methods and highlight the promise of incorporating uncertainty into fully unsupervised GLAD.

Graph-level anomaly detection (GLAD) identifies graphs exhibiting abnormal properties within a graph dataset.Despite promising results in this task, the state-of-the-art methods cannot be fully trusted and deployed in realistic scenarios due to their black-box nature.To alleviate this, existing methods try to explain predictions by extracting important subgraphs from each graph, as instancelevel explanations.However, instance-level explanations across all samples are costly to verify and insufficient to capture the model's general behaviors.Thus, we propose a global interpretable Graph-Level Anomaly Detection model via Prototype (GLADPro), which provides global-level explanations throughout the entire dataset, that is, the significant subgraph patterns that consistently influence the model's decisions.Specifically, GLADPro incorporates prototype learning with the information bottleneck principle, enabling prototypes to capture the most significant subgraph patterns as global-level explanations through persistent interactions with key subgraphs from input graphs.In addition, a regularization term is proposed to prevent the collapse traps with theoretical proof.Finally, we filter redundant prototypes using the maximum mean discrepancy metric.Extensive experiments demonstrate the superiority of GLADPro in anomaly detection and explainability; for instance, on the mutagen dataset, it reduces the number of explanations to verify from 1403 to only 6.

Abstract In heterogeneous graph analysis, existing self-supervised learning (SSL) methods face several key challenges. Primarily, these approaches are tailored for node-level tasks and fail to effectively capture global graph-level features, a crucial aspect for comprehensive graph understanding. Furthermore, they predominantly rely on meta-path-based techniques to unravel graph structures, a process that can be computationally intensive and often intractable for complex networks. Another significant limitation is their inability to account for nonpairwise relationships, a common characteristic in real-world networks like protein-protein interaction and collaboration networks, limiting their effectiveness in graph-level learning where high-order connectivity is essential. To address these issues, we propose an innovative SSL framework for heterogeneous hypergraph embedding, expressly designed to enhance graph-level classification. Our framework introduces multi-hop attention in hypergraph convolution, a significant leap from existing attention mechanisms specifically for hypergraphs that primarily focus on immediate neighborhoods. This multi-hop approach allows for an expansive capture of relational structures, both near and far, uncovering intricate patterns integral to accurate graph-level classification. Complementing this, we implement an informative graph-level attentive pooling mechanism that surpasses traditional aggregation methods. It intelligently synthesizes features, taking into account their structural and semantic importance within the hypergraph, thereby preserving critical contextual information. Furthermore, we refine our contrastive learning approach and introduce targeted negative sampling strategies, creating a more robust learning environment that excels at discerning nuanced graph-level features. Rigorous evaluation against established graph kernels, graph neural networks, and graph pooling methods on real-world datasets demonstrates our model’s superior performance, validating its effectiveness in addressing the complexities inherent in heterogeneous graph-level classification.

Anomalies often occur in real-world information networks/graphs, such as malevolent users in online review networks and fake news in social media. When representing such structured network data as graphs, anomalies usually appear as anomalous nodes that exhibit significantly deviated structure patterns, or different attributes, or the both. To date, numerous unsupervised methods have been developed to detect anomalies based on residual analysis, which assumes that anomalies will introduce larger residual errors (i.e., graph reconstruction loss). While these existing works achieved encouraging performance, in this paper, we formally prove that their employed learning objectives, i.e., MSE and cross-entropy losses, encounter significant limitations in learning the major data distributions, particularly for anomaly detection, and through our preliminary study, we reveal that the vanilla residual analysis-based methods cannot effectively investigate the rich graph structure. Upon these discoveries, we propose a novel structure-biased graph anomaly detection framework (SALAD) to attain anomalies’ divergent patterns with the assistance of a specially designed node representation augmentation approach. We further present two effective training objectives to empower SALAD to effectively capture the major structure and attribute distributions by emphasizing less on anomalies that introduce higher reconstruction errors under the encoder-decoder framework. The detection performance on eight widely-used datasets demonstrates SALAD's superiority over twelve state-of-the-art baselines. Additional ablation and case studies validate that our data augmentation method and training objectives result in the impressive performance.

Deep learning is increasingly crucial in scientific discovery, accelerating research in various fields. Exploring brain science using deep learning has garnered significant interest, particularly in the recognition of brain disorders. However, existing methods face limitations in the discriminability of learned brain graph representations and the identification of neurological biomarkers associated with brain disorders. Moreover, the lack of model explainability leads to suboptimal brain graph analysis. To address these challenges, we propose a bi-level brain graph contrastive learning framework with an interpretable learning kernel for brain disorder analysis. Our framework diverges from traditional graph contrastive learning methods by augmenting meaningful brain graphs using the counterfactual thinking-based mechanism, ensuring reliable graph generation that preserves discriminative information. Secondly, we introduce bi-level contrastive loss with intra-and inter-class contrasts to enhance the brain graph representation learning. Most importantly, we design an interpretable brain graph learning kernel to highlight critical regions and connections, thereby facilitating the discovery of potential neurological biomarkers associated with brain disorders in subsequent analysis. The effectiveness of our method11https://githuh.com/JustinGie/Cf-BCL in brain graph representation learning and discriminative substructure detection is demonstrated through the evaluation of disorder prediction and pathogenic analysis on three real-world brain disorder datasets. Moreover, our framework may provide novel insights into brain science based on the results of comparison with medical research.

In this paper, we propose an interpretable brain graph contrastive learning framework, which aims to learn brain graph representations by a unsupervised way for disorder prediction and pathogenic analysis. Our framework consists of two key designs: We first utilize the controllable data augmentation strategy to perturb unimportant structures and attribute features for the generation of brain graphs. Then, considering that the difference of healthy and patient brain graphs is small, we introduce hard negative sample evaluation to weight negative samples of the contrastive loss, which can learn more discriminative brain graph representations. More importantly, our method can observe salient brain regions and connections for pathogenic analysis. We conduct disorder prediction and interpretable analysis experiments on three real-world neuroimaging datasets to demonstrate the effectiveness of our framework.

Graph pooling technique as the essential component of graph neural networks has gotten increasing attention recently and it aims to learn graph-level representations for the whole graph. Besides, graph pooling is important in graph classification and graph generation tasks. However, current graph pooling methods mainly coarsen a sequence of small-sized graphs to capture hierarchical structures, potentially resulting in the deterioration of the global structure of the original graph and influencing the quality of graph representations. Furthermore, these methods artificially select the number of graph pooling layers for different graph datasets rather than considering each graph individually. In reality, the structure and size differences among graphs necessitate a specific number of graph pooling layers for each graph. In this work, we propose reinforced pooling graph neural networks via adaptive hybrid graph coarsening networks. Specifically, we design a hybrid graph coarsening strategy to coarsen redundant structures of the original graph while retaining the global structure. In addition, we introduce multi-agent reinforcement learning to adaptively perform the graph coarsening process to extract the most representative coarsened graph for each graph, enhancing the quality of graph-level representations. Finally, we design graph-level contrast to improve the preservation of global information in graph-level representations. Extensive experiments with rich baselines on six benchmark datasets show the effectiveness of ReiPool1.

Representation learning in unlabeled heterogeneous graphs has gained significant interest. The heterogeneity in graphs not only provides rich information but also poses challenges to model complex relations in self-supervised learning (SSL) manner. Existing SSL-based approaches are usually designed for node-level tasks and are unable to capture global graph-level features. Also, they often employ computationally expensive meta-path-based techniques, to learn the intrinsic graph structure, that are intractable. Importantly, they overlook non-pairwise relationships among nodes in heterogeneous graphs, for instance in protein-protein interaction networks or collaboration networks, limiting the effectiveness of graph-level learning. To address these issues, we propose a novel self-supervised heterogeneous hypergraph learning framework that captures the richness of heterogeneity, and high-order connectivity in graph-level classification. Unlike traditional methods that rely on meta-path-based approaches to incorporate high-order information, we introduce a k-hop neighborhood strategy to construct intra-graph hyperedges, and a shared attribute-based approach for inter-graph hyperedges to construct the heterogeneous hypergraph. Furthermore, we introduce a context-aware graph-level pooling mechanism that facilitates adaptive aggregation of relevant information across the hypergraph, considering both local and global contexts. Lastly, we design a self-supervised contrastive learning framework by introducing a high-order-aware adaptive augmentation mechanism. This enables the model to learn meaningful graph-level representations from less-labeled data. We evaluate our proposed model against graph kernels, graph neural networks, and graph pooling-based baselines on real-world datasets, demonstrating an overall performance improvement of 5.81% that validates the effectiveness and superiority of the proposed method.

The proliferation of fake news in social media has been recognized as a severe problem for society, and substantial attempts have been devoted to fake news detection to alleviate the detrimental impacts. Knowledge graphs (KGs) comprise rich factual relations among real entities, which could be utilized as ground-truth databases and enhance fake news detection. However, most of the existing methods only leveraged natural language processing and graph mining techniques to extract features of fake news for detection and rarely explored the ground knowledge in knowledge graphs. In this work, we propose a novel Heterogeneous Graph Neural Network via Knowledge Relations for Fake News Detection (HGNNR4FD). The devised framework has four major components: 1) A heterogeneous graph (HG) built upon news content, including three types of nodes, i.e., news, entities, and topics, and their relations. 2) A KG that provides the factual basis for detecting fake news by generating embeddings via relations in the KG. 3) A novel attention-based heterogeneous graph neural network that can aggregate information from HG and KG, and 4) a fake news detector, which is capable of identifying fake news based on the news embeddings generated by HGNNR4FD. We further validate the performance of our method by comparison with seven state-of-art baselines and verify the effectiveness of the components through a thorough ablation analysis. From the results, we empirically demonstrate that our framework achieves superior results and yields improvement over the baselines regarding evaluation metrics of accuracy, precision, recall, and F1-score on four real-world datasets.

Graph neural networks (GNNs) are now the mainstream method for mining graph-structured data and learning low-dimensional node- and graph-level embeddings to serve downstream tasks. However, limited by the bottleneck of interpretability that deep neural networks present, existing GNNs have ignored the issue of estimating the appropriate number of dimensions for the embeddings. Hence, we propose a novel framework called Minimum Graph Entropy principle-guided Dimension Estimation, i.e. MGEDE, that learns the appropriate embedding dimensions for both node and graph representations. In terms of node-level estimation, a minimum entropy function that counts both structure and attribute entropy, appraises the appropriate number of dimensions. In terms of graph-level estimation, each graph is assigned a customized embedding dimension from a candidate set based on the number of dimensions estimated for the node-level embeddings. Comprehensive experiments with node and graph classification tasks and nine benchmark datasets verify the effectiveness and generalizability of MGEDE.

Anomalies are rare observations (e.g., data records or events) that deviate significantly from the others in the sample. Over the past few decades, research on anomaly mining has received increasing interests due to the implications of these occurrences in a wide range of disciplines - for instance, security, finance, and medicine. For this reason, anomaly detection, which aims to identify these rare observations, has become one of the most vital tasks in the world and has shown its power in preventing detrimental events, such as financial fraud, network intrusions, and social spam. The detection task is typically solved by identifying outlying data points in the feature space, which, inherently, overlooks the relational information in real-world data. At the same time, graphs have been prevalently used to represent the structural/relational information, which raises thegraph anomaly detection problem- identifying anomalous graph objects (i.e., nodes, edges and sub-graphs) in a single graph, or anomalous graphs in a set/database of graphs. Conventional anomaly detection techniques cannot tackle this problem well because of the complexity of graph data (e.g., irregular structures, relational dependencies, node/edge types/attributes/directions/multiplicities/weights, large scale, etc.). However, thanks to the advent of deep learning in breaking these limitations, graph anomaly detection with deep learning has received a growing attention recently. In this survey, we aim to provide a systematic and comprehensive review of the contemporary deep learning techniques for graph anomaly detection. Specifically, we provide a taxonomy that follows a task-driven strategy and categorizes existing work according to the anomalous graph objects that they can detect. We especially focus on the challenges in this research area and discuss the key intuitions, technical details as well as relative strengths and weaknesses of various techniques in each category. From the survey results, we highlight 12 future research directions spanning unsolved and emerging problems introduced by graph data, anomaly detection, deep learning and real-world applications. Additionally, to provide a wealth of useful resources for future studies, we have compiled a set of open-source implementations, public datasets, and commonly-used evaluation metrics. With this survey, our goal is to create a “one-stop-shop” that provides a unified understanding of the problem categories and existing approaches, publicly available hands-on resources, and high-impact open challenges for graph anomaly detection using deep learning.

Event detection in power systems aims to identify triggers and event types, which helps relevant personnel respond to emergencies promptly and facilitates the optimization of power supply strategies. However, the limited length of short electrical record texts causes severe information sparsity, and numerous domain-specific terminologies of power systems makes it difficult to transfer knowledge from language models pre-trained on general-domain texts. Traditional event detection approaches primarily focus on the general domain and ignore these two problems in the power system domain. To address the above issues, we propose a Multi-Channel graph neural network utilizing Type information for Event Detection in power systems, named MC-TED , leveraging a semantic channel and a topological channel to enrich information interaction from short texts. Concretely, the semantic channel refines textual representations with semantic similarity, building the semantic information interaction among potential event-related words. The topological channel generates a relation-type-aware graph modeling word dependencies, and a word-type-aware graph integrating part-of-speech tags. To further reduce errors worsened by professional terminologies in type analysis, a type learning mechanism is designed for updating the representations of both the word type and relation type in the topological channel. In this way, the information sparsity and professional term occurrence problems can be alleviated by enabling interaction between topological and semantic information. Furthermore, to address the lack of labeled data in power systems, we built a Chinese event detection dataset based on electrical Power Event texts, named PoE . In experiments, our model achieves compelling results not only on the PoE dataset, but on general-domain event detection datasets including ACE 2005 and MAVEN.

Graph anomaly detection in this paper aims to distinguish abnormal nodes that behave differently from the benign ones accounting for the majority of graph-structured instances. Receiving increasing attention from both academia and industry, yet existing research on this task still suffers from two critical issues when learning informative anomalous behavior from graph data. For one thing, anomalies are usually hard to capture because of their subtle abnormal behavior and the shortage of background knowledge about them, which causes severe anomalous sample scarcity. Meanwhile, the overwhelming majority of objects in real-world graphs are normal, bringing the class imbalance problem as well. To bridge the gaps, this paper devises a novel Data Augmentation-based Graph Anomaly Detection (DAGAD) framework for attributed graphs, equipped with three specially designed modules: 1) an information fusion module employing graph neural network encoders to learn representations, 2) a graph data augmentation module that fertilizes the training set with generated samples, and 3) an imbalance-tailored learning module to discriminate the distributions of the minority (anomalous) and majority (normal) classes. A series of experiments on three datasets prove that DAGAD outperforms ten state-of-the-art baseline detectors concerning various mostly-used metrics, together with an extensive ablation study validating the strength of our proposed modules.

Graph anomaly detection, here, aims to find rare patterns that are significantly different from other nodes. Attributed graphs containing complex structure and attribute information are ubiquitous in our life scenarios such as bank account transaction graph and paper citation graph. Anomalous nodes on attributed graphs show great difference from others in the perspectives of structure and attributes, and give rise to various types of graph anomalies. In this paper, we investigate three types of graph anomalies: local, global, and structure anomalies. And, graph neural networks (GNNs) based anomaly detection methods attract considerable research interests due to the power of modeling attributed graphs. However, the convolution operation of GNNs aggregates neighbors information to represent nodes, which makes node representations more similar and cannot effectively distinguish between normal and anomalous nodes, thus result in sub-optimal results. To improve the performance of anomaly detection, we propose a novel community-aware attributed graph anomaly detection framework (ComGA). We design a tailored deep graph convolutional network (tGCN) to anomaly detection on attributed graphs. Extensive experiments on eight real-life graph datasets demonstrate the effectiveness of ComGA.

The objective of fraud detection is to distinguish fraudsters from normal users. In graph/network environments, both fraudsters and normal users are modeled as nodes, and the connections between those nodes are represented as edges. Fraudsters typically try to camouflage themselves with “normal” behaviors, say, by deliberately establishing many connections to normal users. Such camouflage inherently makes their appearance inconsistent with the essence of what it is to be normal, and gives rise to inconsistencies in the graph. In this paper, we investigate three aspects of these graph inconsistencies: features, topologies, and relations. To date, graph-based fraud detectors have shown a rather limited capability to fuse information about different types of inconsistencies. Apart from that, there is another problem of imbalance to overcome. This is because fraudsters usually only account for a very small percentage of all users. To achieve a promising capability, i.e., dual-resistant to graph inconsistency and imbalance, we present a new fraud detection model FRAUDRE based on Graph Neural Networks. Extensive experiments comparing eight up-to-date baselines on two real-world datasets, Amazon and YelpChi, demonstrate the superiority of FRAUDRE.