Graph Coloring: Comparing Cluster Graphs to Factor Graphs

• URL: http://arxiv.org/abs/2110.02048v1
• Date: Tue, 5 Oct 2021 13:57:30 GMT
• Title: Graph Coloring: Comparing Cluster Graphs to Factor Graphs
• Authors: Simon Streicher and Johan du Preez
• Abstract summary: We present a means of formulating and solving graph coloring problems with probabilistic graphical models. In contrast to the prevalent literature that uses factor graphs for this purpose, we instead approach it from a cluster graph perspective.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a means of formulating and solving graph coloring problems with probabilistic graphical models. In contrast to the prevalent literature that uses factor graphs for this purpose, we instead approach it from a cluster graph perspective. Since there seems to be a lack of algorithms to automatically construct valid cluster graphs, we provide such an algorithm (termed LTRIP). Our experiments indicate a significant advantage for preferring cluster graphs over factor graphs, both in terms of accuracy as well as computational efficiency.

Related papers

• The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure [18.00833762891405]
  Graph Lottery Ticket (GLT) Hypothesis: There is an extremely sparse backbone for every graph. We study 8 key metrics of interest that directly influence the performance of graph learning algorithms. We propose a straightforward and efficient algorithm for finding these GLTs in arbitrary graphs.
  arXiv  Detail & Related papers  (2023-12-08T00:24:44Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  We study graph data augmentation by mixup, which has been used successfully on images. We propose S-Mixup, a simple yet effective mixup method for graph classification by soft alignments.
  arXiv  Detail & Related papers  (2023-06-11T22:04:28Z)
• Deep Graph-Level Clustering Using Pseudo-Label-Guided Mutual Information Maximization Network [31.38584638254226]
  We study the problem of partitioning a set of graphs into different groups such that the graphs in the same group are similar while the graphs in different groups are dissimilar. To solve the problem, we propose a novel method called Deep Graph-Level Clustering (DGLC) Our DGLC achieves graph-level representation learning and graph-level clustering in an end-to-end manner.
  arXiv  Detail & Related papers  (2023-02-05T12:28:08Z)
• CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning [65.1042892570989]
  We propose a contrastive graph matching network (CGMN) for self-supervised graph similarity learning. We employ two strategies, namely cross-view interaction and cross-graph interaction, for effective node representation learning. We transform node representations into graph-level representations via pooling operations for graph similarity computation.
  arXiv  Detail & Related papers  (2022-05-30T13:20:26Z)
• Synthetic Graph Generation to Benchmark Graph Learning [7.914804101579097]
  Graph learning algorithms have attained state-of-the-art performance on many graph analysis tasks. One reason is due to the very small number of datasets used in practice to benchmark the performance of graph learning algorithms. We propose to generate synthetic graphs, and study the behaviour of graph learning algorithms in a controlled scenario.
  arXiv  Detail & Related papers  (2022-04-04T10:48:32Z)
• Product Graph Learning from Multi-domain Data with Sparsity and Rank Constraints [17.15829643665034]
  We propose an efficient iterative solver for learning sparse product graphs from data. We extend this solver to infer multi-component graph factors with applications to product graph clustering. The efficacy of the developed framework is demonstrated using several numerical experiments on synthetic data and real data.
  arXiv  Detail & Related papers  (2020-12-15T04:59:32Z)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  We present Dirichlet Graph Variational Autoencoder (DGVAE) with graph cluster memberships as latent factors. Motivated by the low pass characteristics in balanced graph cut, we propose a new variant of GNN named Heatts to encode the input graph into cluster memberships.
  arXiv  Detail & Related papers  (2020-10-09T07:35:26Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Wasserstein Embedding for Graph Learning [33.90471037116372]
  Wasserstein Embedding for Graph Learning (WEGL) is a framework for embedding entire graphs in a vector space. We leverage new insights on defining similarity between graphs as a function of the similarity between their node embedding distributions. We evaluate our new graph embedding approach on various benchmark graph-property prediction tasks.
  arXiv  Detail & Related papers  (2020-06-16T18:23:00Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)
• Adaptive Graph Auto-Encoder for General Data Clustering [90.8576971748142]
  Graph-based clustering plays an important role in the clustering area. Recent studies about graph convolution neural networks have achieved impressive success on graph type data. We propose a graph auto-encoder for general data clustering, which constructs the graph adaptively according to the generative perspective of graphs.
  arXiv  Detail & Related papers  (2020-02-20T10:11:28Z)

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.