Diffusion Models for Cayley Graphs

• URL: http://arxiv.org/abs/2503.05558v1
• Date: Fri, 07 Mar 2025 16:33:16 GMT
• Title: Diffusion Models for Cayley Graphs
• Authors: Michael R. Douglas, Cristofero Fraser-Taliente,
• Abstract summary: We show how to formulate problems in the framework of diffusion models.<n>We propose a reversed score'' ansatz which substantially improves over previous comparable algorithms.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We review the problem of finding paths in Cayley graphs of groups and group actions, using the Rubik's cube as an example, and we list several more examples of significant mathematical interest. We then show how to formulate these problems in the framework of diffusion models. The exploration of the graph is carried out by the forward process, while finding the target nodes is done by the inverse backward process. This systematizes the discussion and suggests many generalizations. To improve exploration, we propose a ``reversed score'' ansatz which substantially improves over previous comparable algorithms.

Related papers

• CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs [0.0]
  This paper is the second in a series of studies on developing efficient artificial intelligence-based approaches to pathfinding on large graphs.<n>We present a novel combination of a reinforcement learning approach with a more direct diffusion distance approach from the first paper.<n>We provide strong support for the OEIS-A186783 conjecture that the diameter is equal to n(n-1)/2 by machine learning and mathematical methods.
  arXiv  Detail & Related papers  (2025-02-25T21:53:41Z)
• Gotta match 'em all: Solution diversification in graph matching matched filters [13.841897638543033]
  We present a novel approach for finding multiple noisily embedded template graphs in a very large background graph. Our method builds upon the graph-matching-matched-filter technique proposed in Sussman et al.
  arXiv  Detail & Related papers  (2023-08-25T15:53:30Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• Optimization on Manifolds via Graph Gaussian Processes [4.471962177124311]
  This paper integrates manifold learning techniques within a emphGaussian process upper confidence bound algorithm to optimize an objective function on a manifold.
  arXiv  Detail & Related papers  (2022-10-20T02:15:34Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  We study Grover's search algorithm focusing on continuous-time quantum walk on graphs. Instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph endowed Laplacians.
  arXiv  Detail & Related papers  (2022-07-04T19:33:06Z)
• Improving Diffusion Models for Inverse Problems using Manifold Constraints [55.91148172752894]
  We show that current solvers throw the sample path off the data manifold, and hence the error accumulates. To address this, we propose an additional correction term inspired by the manifold constraint. We show that our method is superior to the previous methods both theoretically and empirically.
  arXiv  Detail & Related papers  (2022-06-02T09:06:10Z)
• 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)
• Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
  We propose a new algorithm for finding an unknown number of geometric models, e.g., homographies. We present a number of applications where the use of multiple geometric models improves accuracy. These include pose estimation from multiple generalized homographies; trajectory estimation of fast-moving objects.
  arXiv  Detail & Related papers  (2021-03-25T14:35:07Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  Adversarial examples are a widely studied phenomenon in machine learning models. We propose an algorithm for evaluating the adversarial robustness of $k$-nearest neighbor classification.
  arXiv  Detail & Related papers  (2020-11-19T08:49:10Z)
• 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.