Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning

• URL: http://arxiv.org/abs/2104.03546v1
• Date: Thu, 8 Apr 2021 06:54:24 GMT
• Title: Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning
• Authors: Alice Gatti, Zhixiong Hu, Pieter Ghysels, Esmond G. Ng, Tess Smidt
• Abstract summary: We present a novel method for graph partitioning based on reinforcement learning and graph convolutional neural networks. The proposed method achieves similar partitioning quality than METIS and Scotch. The method generalizes from one class of graphs to another, and works well on a variety of graphs from the SuiteSparse sparse matrix collection.
• Score: 0.13999481573773068
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel method for graph partitioning, based on reinforcement learning and graph convolutional neural networks. The new reinforcement learning based approach is used to refine a given partitioning obtained on a coarser representation of the graph, and the algorithm is applied recursively. The neural network is implemented using graph attention layers, and trained using an advantage actor critic (A2C) agent. We present two variants, one for finding an edge separator that minimizes the normalized cut or quotient cut, and one that finds a small vertex separator. The vertex separators are then used to construct a nested dissection ordering for permuting a sparse matrix so that its triangular factorization will incur less fill-in. The partitioning quality is compared with partitions obtained using METIS and Scotch, and the nested dissection ordering is evaluated in the sparse solver SuperLU. Our results show that the proposed method achieves similar partitioning quality than METIS and Scotch. Furthermore, the method generalizes from one class of graphs to another, and works well on a variety of graphs from the SuiteSparse sparse matrix collection.

Related papers

• Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
  Cluster deletion is an NP-hard graph clustering objective with applications in computational and social network analysis. We first provide a tighter analysis of two previous approximation algorithms, improving their approximation guarantees from 4 to 3. We show that both algorithms can be derandomized in a surprisingly simple way, by greedily taking a maximum degree in an auxiliary graph and forming a cluster around it.
  arXiv  Detail & Related papers  (2024-04-24T18:39:18Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations [0.0]
  We use a learning framework for a pruning process of the input graph towards reducing the clique of the maximum enumeration problem. We study the role of using different vertex representations on the performance of this runtime method. We observe that using local graph features in the classification process produce more accurate results when combined with a feature elimination process.
  arXiv  Detail & Related papers  (2022-10-30T22:04:32Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Deep Learning and Spectral Embedding for Graph Partitioning [0.13999481573773068]
  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.
  arXiv  Detail & Related papers  (2021-10-16T16:57:01Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  This paper presents a convex-analytic framework to learn from data. We show that a triangular convexity decomposition is guaranteed by a transform of the corresponding to its upper part.
  arXiv  Detail & Related papers  (2021-09-17T17:46:12Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• Enhancing Balanced Graph Edge Partition with Effective Local Search [41.4257628524592]
  Graph partition is a key component to achieve workload balance and reduce job completion time in parallel graph processing systems. In this paper, we study local search algorithms for this problem to further improve the partition results from existing methods.
  arXiv  Detail & Related papers  (2020-12-17T08:58:06Z)
• 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)
• Scaling Graph Clustering with Distributed Sketches [1.1011268090482575]
  We present a method inspired by spectral clustering where we instead use matrix sketches derived from random dimension-reducing projections. We show that our method produces embeddings that yield performant clustering results given a fully-dynamic block model stream. We also discuss the effects of block model parameters upon the required dimensionality of the subsequent embeddings, and show how random projections could significantly improve the performance of graph clustering in distributed memory.
  arXiv  Detail & Related papers  (2020-07-24T17:38:04Z)

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.