Minimal Dirichlet energy partitions for graphs
Motivated by a geometric problem, we introduce a new non-convex graph partitioning objective where the optimality criterion is given by the sum of the Dirichlet eigenvalues of the partition components. A relaxed formulation is identified and a novel rearrangement algorithm is proposed, which we show is strictly decreasing and converges in a finite number of iterations to a local minimum of the relaxed objective function. Our method is applied to several clustering problems on graphs constructed from synthetic data, MNIST handwritten digits, and manifold discretizations. The model has a semi-supervised extension and provides a natural representative for the clusters as well.
Code (0)
등록된 구현이 없습니다.
Tasks
Clusteringgraph partitioningSimilar Papers 제목 키워드 기반
Consistency of Dirichlet Partitions
A Dirichlet $k$-partition of a domain $U \subseteq \mathbb{R}^d$ is a collection of $k$ pairwise disjoint open subsets such that the sum of their first Laplace-Dirichlet eigenvalues is minimal. A discrete version of Diri…
Dirichlet Energy Enhancement of Graph Neural Networks by Framelet Augmentation
Graph convolutions have been a pivotal element in learning graph representations. However, recursively aggregating neighboring information with graph convolutions leads to indistinguishable node features in deep layers, …
Node ClassificationJoint Feature and Differentiable $ k $-NN Graph Learning using Dirichlet Energy
Feature selection (FS) plays an important role in machine learning, which extracts important features and accelerates the learning process. In this paper, we propose a deep FS method that simultaneously conducts feature …
feature selectionGraph LearningA Fractional Graph Laplacian Approach to Oversmoothing
Graph neural networks (GNNs) have shown state-of-the-art performances in various applications. However, GNNs often struggle to capture long-range dependencies in graphs due to oversmoothing. In this paper, we generalize …
Bayesian Nonparametric Models on Decomposable Graphs
Over recent years Dirichlet processes and the associated Chinese restaurant process (CRP) have found many applications in clustering while the Indian buffet process (IBP) is increasingly used to describe latent feature m…
Clustering