Learnable Kernel Density Estimation for Graphs and Its Application to Graph-Level Anomaly Detection

This work proposes a framework LGKDE that learns kernel density estimation for graphs. The key challenge in graph density estimation lies in effectively capturing both structural patterns and semantic variations while maintaining theoretical guarantees. Combining graph kernels and kernel density estimation (KDE) is a standard approach to graph density estimation, but has unsatisfactory performance due to the handcrafted and fixed features of kernels. Our method LGKDE leverages graph neural networks to represent each graph as a discrete distribution and utilizes maximum mean discrepancy to learn the graph metric for multi-scale KDE, where all parameters are learned by maximizing the density of graphs relative to the density of their well-designed perturbed counterparts. The perturbations are conducted on both node features and graph spectra, which helps better characterize the boundary of normal density regions. Theoretically, we establish consistency and convergence guarantees for LGKDE, including bounds on the mean integrated squared error, robustness, and generalization. We validate LGKDE by demonstrating its effectiveness in recovering the underlying density of synthetic graph distributions and applying it to graph anomaly detection across diverse benchmark datasets. Extensive empirical evaluation shows that LGKDE demonstrates superior performance compared to state-of-the-art baselines on most benchmark datasets.

Many real-world objects can be represented as graphs, which describe entities and their relationships. For example, a molecule can be viewed as a graph of atoms connected by chemical bonds, and a social network can be viewed as a graph of people connected by interactions. In many applications, we want to learn what normal graphs look like and then identify graphs that appear abnormal. This problem is known as graph-level anomaly detection. This paper introduces LGKDE, a method for learning how likely a graph is to belong to the normal data distribution. Instead of relying on fixed, hand-designed rules for comparing graphs, LGKDE learns a data-driven way to compare graph structures and then estimates how typical each graph is. During training, it also creates carefully perturbed versions of normal graphs, helping the model better recognize the boundary between normal and abnormal patterns. We provide theoretical analysis showing that LGKDE becomes more reliable with more training data and remains stable under small changes to graphs. Experiments on both synthetic and real benchmark datasets show that LGKDE can capture meaningful graph patterns and improve graph-level anomaly detection compared with existing methods.