Mean-field theory of graph neural networks in graph partitioning
A theoretical performance analysis of the graph neural network (GNN) is presented. For classification tasks, the neural network approach has the advantage in terms of flexibility that it can be employed in a data-driven manner, whereas Bayesian inference requires the assumption of a specific model. A fundamental question is then whether GNN has a high accuracy in addition to this flexibility. Moreover, whether the achieved performance is predominately a result of the backpropagation or the architecture itself is a matter of considerable interest. To gain a better insight into these questions, a mean-field theory of a minimal GNN architecture is developed for the graph partitioning problem. This demonstrates a good agreement with numerical experiments.
Code (0)
등록된 구현이 없습니다.
Tasks
Bayesian InferenceGeneral ClassificationGraph Neural Networkgraph partitioningSimilar Papers 제목 키워드 기반
Weighted Laplacian and Its Theoretical Applications
In this paper, we develop a novel weighted Laplacian method, which is partially inspired by the theory of graph Laplacian, to study recent popular graph problems, such as multilevel graph partitioning and balanced minimu…
Clusteringgraph partitioningDeep Learning and Spectral Embedding for Graph Partitioning
We present a graph bisection and partitioning algorithm based on graph neural networks. For each node in the graph, the network outputs probabilities for each of the partitions. The graph neural network consists of two m…
Deep LearningGraph Neural Networkgraph partitioningOn spectral partitioning of signed graphs
We argue that the standard graph Laplacian is preferable for spectral partitioning of signed graphs compared to the signed Laplacian. Simple examples demonstrate that partitioning based on signs of components of the lead…
Hypergraph Partitioning using Tensor Eigenvalue Decomposition
Hypergraphs have gained increasing attention in the machine learning community lately due to their superiority over graphs in capturing super-dyadic interactions among entities. In this work, we propose a novel approach …
graph partitioninghypergraph partitioningRegular Intersection Emptiness of Graph Problems: Finding a Needle in a Haystack of Graphs with the Help of Automata
The Int_reg-problem of a combinatorial problem P asks, given a nondeterministic automaton M as input, whether the language L(M) accepted by M contains any positive instance of the problem P. We consider the Int_reg-probl…
graph partitioning