Diffusion operator and spectral analysis for directed hypergraph Laplacian

DOI10.1016/J.TCS.2019.03.032MaRDI QIDQ2317870zbMATH OpenOpenAlexWikidataFDO

Authors T.-H. Hubert Chan, Zhihao Gavin Tang, Xiaowei Wu, Chenzi Zhang

Publication date 13 August 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.01560

zbMATH Keywords

Cheeger's inequalitydiffusion processdirected hypergraph Laplacian

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Hypergraphs (05C65) Diffusion processes (60J60)

Abstract: In spectral graph theory, the Cheeger's inequality gives upper and lower bounds of edge expansion in normal graphs in terms of the second eigenvalue of the graph's Laplacian operator. Recently this inequality has been extended to undirected hypergraphs and directed normal graphs via a non-linear operator associated with a diffusion process in the underlying graph. In this work, we develop a unifying framework for defining a diffusion operator on a directed hypergraph with stationary vertices, which is general enough for the following two applications. 1. Cheeger's inequality for directed hyperedge expansion. 2. Quadratic optimization with stationary vertices in the context of semi-supervised learning. Despite the crucial role of the diffusion process in spectral analysis, previous works have not formally established the existence of the corresponding diffusion processes. In this work, we give a proof framework that can indeed show that such diffusion processes are well-defined. In the first application, we use the spectral properties of the diffusion operator to achieve the Cheeger's inequality for directed hyperedge expansion. In the second application, the diffusion operator can be interpreted as giving a continuous analog to the subgradient method, which moves the feasible solution in discrete steps towards an optimal solution.

Recommendations

• Spectral properties of hypergraph Laplacian and approximation algorithms
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
• Laplacians and the Cheeger inequality for directed graphs

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Algorithmic extensions of Cheeger's inequality to higher eigenvalues and partitions
• Approximation algorithm for sparsest \(k\)-partitioning
• Cheeger inequalities for submodular transformations
• Digraph Laplacian and the degree of asymmetry
• Directed hypergraphs and applications
• Eigenvalues and expanders
• Expander graphs and their applications
• Finding Cheeger cuts in hypergraphs via heat equation
• scientific article; zbMATH DE number 475375 (Why is no real title available?)
• scientific article; zbMATH DE number 3894826 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
• Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
• Laplacian eigenvalues and partition problems in hypergraphs
• Laplacians and the Cheeger inequality for directed graphs
• Many sparse cuts via higher eigenvalues
• Normalized graph Laplacians for directed graphs
• On clusterings: good, bad and spectral
• On the second eigenvalue of hypergraphs
• Spectral properties of hypergraph Laplacian and approximation algorithms

Cited in

(7)

• Finding Cheeger cuts in hypergraphs via heat equation
• Spectral properties of hypergraph Laplacian and approximation algorithms
• Hypergraph Laplacians in Diffusion Framework
• Cheeger inequalities for submodular transformations
• Three conjectures of Ostrander on digraph Laplacian eigenvectors
• The structure and dynamics of networks with higher order interactions
• Networks beyond pairwise interactions: structure and dynamics

This page was built for publication: Diffusion operator and spectral analysis for directed hypergraph Laplacian

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2317870)