Learnable Kernel Density Estimation for Graphs

• URL: http://arxiv.org/abs/2505.21285v1
• Date: Tue, 27 May 2025 14:53:09 GMT
• Title: Learnable Kernel Density Estimation for Graphs
• Authors: Xudong Wang, Ziheng Sun, Chris Ding, Jicong Fan,
• Abstract summary: Key challenge in graph density estimation is capturing both structural patterns and semantic variations.<n>This work proposes a framework LGKDE that learns kernel density estimation for graphs.
• Score: 28.551276298283227
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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 complexity. 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.

Related papers

• WATS: Calibrating Graph Neural Networks with Wavelet-Aware Temperature Scaling [43.23012871829196]
  We propose Wavelet-Aware Temperature Scaling (WATS), a post-hoc calibration framework that assigns node-specific temperatures based on graph wavelet features.<n>WATS harnesses the scalability and topology sensitivity of graph wavelets to refine confidence estimates, all without retraining or access to neighboring logits or predictions.
  arXiv  Detail & Related papers  (2025-06-30T12:23:57Z)
• Fast Kernel Density Estimation with Density Matrices and Random Fourier Features [0.0]
  kernels density estimation (KDE) is one of the most widely used nonparametric density estimation methods. DMKDE uses density matrices, a quantum mechanical formalism, and random Fourier features, an explicit kernel approximation, to produce density estimates. DMKDE is on par with its competitors for computing density estimates and advantages are shown when performed on high-dimensional data.
  arXiv  Detail & Related papers  (2022-08-02T02:11:10Z)
• Learning Transfer Operators by Kernel Density Estimation [0.0]
  We recast the problem within the framework of statistical density estimation. We demonstrate the validity and effectiveness of this approach in estimating the eigenvectors of the Frobenius-Perron operator. We suggest the possibility of incorporating other density estimation methods into this field.
  arXiv  Detail & Related papers  (2022-08-01T14:28:10Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)
• Density-Based Clustering with Kernel Diffusion [59.4179549482505]
  A naive density corresponding to the indicator function of a unit $d$-dimensional Euclidean ball is commonly used in density-based clustering algorithms. We propose a new kernel diffusion density function, which is adaptive to data of varying local distributional characteristics and smoothness.
  arXiv  Detail & Related papers  (2021-10-11T09:00:33Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Density of States Graph Kernels [10.200937444995944]
  Graph kernels are an established technique for quantifying similarity between graphs. We recast random walk kernels under the more general framework of density of states. We use our interpretation to construct scalable, composite density of states based graph kernels.
  arXiv  Detail & Related papers  (2020-10-21T22:44:59Z)
• Nonparametric Density Estimation from Markov Chains [68.8204255655161]
  We introduce a new nonparametric density estimator inspired by Markov Chains, and generalizing the well-known Kernel Density Estor. Our estimator presents several benefits with respect to the usual ones and can be used straightforwardly as a foundation in all density-based algorithms.
  arXiv  Detail & Related papers  (2020-09-08T18:33:42Z)
• Generalized Spectral Clustering via Gromov-Wasserstein Learning [10.558951653323286]
  We establish a bridge between spectral clustering and Gromov-Wasserstein Learning (GWL) GWL is a recent optimal transport-based approach to graph partitioning. We show that when comparing against a two-node template graph using the heat kernel at the infinite time limit, the resulting partition agrees with the partition produced by the Fiedler vector.
  arXiv  Detail & Related papers  (2020-06-07T14:29:32Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.