Node Classification and Search on the Rubik's Cube Graph with GNNs

• URL: http://arxiv.org/abs/2501.18580v2
• Date: Fri, 31 Jan 2025 18:57:14 GMT
• Title: Node Classification and Search on the Rubik's Cube Graph with GNNs
• Authors: Alessandro Barro,
• Abstract summary: This study focuses on the application of deep geometric models to solve the 3x3x3 Rubik's Rubik. We begin by discussing the cube's graph representation and defining distance as the model's optimization objective. The distance approximation task is reformulated as a node classification problem, effectively addressed using Graph Neural Networks (GNNs)
• Score: 55.2480439325792
• License:
• Abstract: This study focuses on the application of deep geometric models to solve the 3x3x3 Rubik's Cube. We begin by discussing the cube's graph representation and defining distance as the model's optimization objective. The distance approximation task is reformulated as a node classification problem, effectively addressed using Graph Neural Networks (GNNs). After training the model on a random subgraph, the predicted classes are used to construct a heuristic for $A^*$ search. We conclude with experiments comparing our heuristic to that of the DeepCubeA model.

Related papers

• Graph Spring Neural ODEs for Link Sign Prediction [49.71046810937725]
  We propose a novel message-passing layer architecture called Graph Spring Network (GSN) modeled after spring forces. We show that our method achieves accuracy close to the state-of-the-art methods with node generation time speedup factors of up to 28,000 on large graphs.
  arXiv  Detail & Related papers  (2024-12-17T13:50:20Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  Graph matching is a commonly used technique in computer vision and pattern recognition. Recent data-driven approaches have improved the graph matching accuracy remarkably. We propose a graph neural network (GNN) based approach to combine the advantages of data-driven and traditional methods.
  arXiv  Detail & Related papers  (2024-03-11T06:34:05Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  Graph Neural Networks (GNNs) rely on graph convolutions to exploit meaningful patterns in networked data. We propose to learn GNNs on very large graphs by leveraging the limit object of a sequence of growing graphs, the graphon.
  arXiv  Detail & Related papers  (2022-10-27T16:00:45Z)
• Learning task-specific features for 3D pointcloud graph creation [0.8629912408966145]
  We propose a principled way of creating a graph from a 3D pointcloud. Our method is based on performing k-NN over a transformation of the input 3D pointcloud. We also introduce a regularization method based on stress minimization, which allows to control how distant is the learnt graph from our baseline: k-NN over xyz space.
  arXiv  Detail & Related papers  (2022-09-02T11:13:02Z)
• Deep Manifold Learning with Graph Mining [80.84145791017968]
  We propose a novel graph deep model with a non-gradient decision layer for graph mining. The proposed model has achieved state-of-the-art performance compared to the current models.
  arXiv  Detail & Related papers  (2022-07-18T04:34:08Z)
• SN-Graph: a Minimalist 3D Object Representation for Classification [4.145824494809195]
  In this paper, we propose a Sphere Node Graph (SN-Graph) to represent 3D objects. Specifically, we extract a certain number of internal spheres (as nodes) from the signed distance field (SDF), and then establish connections (as edges) among the sphere nodes to construct a graph. Experiments conducted on the ModelNet40 dataset show that when there are fewer nodes in the graph or the tested objects are rotated arbitrarily, the classification accuracy of SN-Graph is significantly higher.
  arXiv  Detail & Related papers  (2021-05-31T08:24:09Z)
• Exploiting Local Geometry for Feature and Graph Construction for Better 3D Point Cloud Processing with Graph Neural Networks [22.936590869919865]
  We propose improvements in point representations and local neighborhood graph construction within the general framework of graph neural networks. We show that the proposed network achieves faster training convergence, i.e. 40% less epochs for classification.
  arXiv  Detail & Related papers  (2021-03-28T21:34:59Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  Graph Neural Networks (GNNs) have achieved great success in graph representation learning. GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order tests, are inefficient as they cannot sparsity of underlying graph structure. We propose Distance Depiction (DE) as a new class of graph representation learning.
  arXiv  Detail & Related papers  (2020-08-31T23:15:40Z)
• Point-GNN: Graph Neural Network for 3D Object Detection in a Point Cloud [3.04585143845864]
  We propose a graph neural network to detect objects from a LiDAR point cloud. We encode the point cloud efficiently in a fixed radius near-neighbors graph. In Point-GNN, we propose an auto-registration mechanism to reduce translation variance.
  arXiv  Detail & Related papers  (2020-03-02T23:44:12Z)

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.