Constellation Recognition: GNN + Symbolic AI — Developing a Hybrid Model

Let us begin with a quiz.
Can you find Orion in this image?

Since we have the opportunity, we will save the correct answer for later and move on to the main topic of this article.

Have you ever looked up at a clear night sky and tried to trace Orion’s Belt or the ladle-shaped pattern of the Big Dipper?

Humans possess an extraordinary cognitive ability known as “pareidolia.” Our brains are naturally predisposed to extract meaningful geometric patterns from random, unstructured

Pareidolia - Wikipedia

Wikimedia Foundation, Inc.Contributors to Wikimedia projects

However, for computers, recognizing these shapes within a sea of noisy coordinates is known to be an extremely difficult task.

In this article, we explain how we built a hybrid graph neural network (GNN) and symbolic reasoning engine capable of detecting, separating, and reconstructing multiple overlapping constellations—Orion, Cassiopeia, and the Big Dipper—from noisy, unstructured coordinate point clouds.

Even under conditions involving extreme noise, arbitrary rotation, and coordinate scaling, the engine achieved a test macro F1 score of 96.91%. Below, we explain how we accomplished this.

Night-Sky Quiz: Question 2

Now, let us reveal the correct answer to the first question.

The constellation recognition AI developed for this article uses a GNN and successfully identified Orion.

The result is shown below.

Did you get it right?

Here is the next question. This time, Orion, Cassiopeia, and the Big Dipper are hidden in the image. Can you find all of them?

Once again, we will save the answer for later and continue with the main topic.

Why Conventional Computer Vision Cannot Handle This Problem

If you asked a modern AI engineer to classify shapes, they would probably first consider using a convolutional neural network (CNN) such as ResNet or YOLO.

However, CNNs operate on structured pixel grids. Stars do not exist on a pixel grid. They are unstructured coordinates in space.

Converting coordinate data into an image—a process known as rasterization—to feed it into a CNN creates several serious problems.

Loss of precision: Rasterization forces high-precision coordinates onto a discrete pixel grid, introducing quantization noise.

Sparse noise: Most pixels in a constellation map represent empty, dark space with a value of $0$, causing CNNs to waste a significant amount of computational resources.

Lack of spatial invariance: Without extensive and expensive data augmentation, CNNs struggle to generalize across arbitrary rotations, translations, and changes in global scale.

To solve these problems, we modeled the sky as a graph. Each star is represented as a node, while edges connect nearby stars.

Feature Engineering: Local Geometric Signatures

To make the system invariant to rotation, translation, and scale, we developed Local Geometric Signatures (LGS).

Instead of passing raw coordinates directly into the GNN, each star node calculates a scale-invariant descriptor based on its local neighborhood.

For each node, we use a K-nearest neighbors (K-NN) query to identify its K=6 nearest neighboring nodes.

We then calculate the Euclidean distance to each of these six neighbors.

Each distance is divided by the mean distance from the node to its neighboring nodes.

This produces a six-dimensional, scale-invariant local fingerprint for each star. Because these ratios remain constant even when the entire star field is enlarged, reduced, translated, or rotated, they provide the GNN with a robust and invariant descriptor.

Custom Edge-Update GNN

We built a custom PyTorch Geometric GNN with four message-passing layers.

Unlike standard GNNs, which update only node features, our layers update both node embeddings and edge attributes simultaneously.

Node embeddings: Aggregate features from neighboring stars.

Edge embeddings: Predict edge-level classification logits across four classes: noise or background, Orion connections, Cassiopeia connections, and Big Dipper connections.

We trained the model on a dataset of 1,500 synthetic star fields.

Because genuine constellation connections are extremely rare compared with random connections between noise points, we used weighted cross-entropy loss to address the resulting class imbalance.

Symbolic Guardrails: Topological Isomorphism Filter

Deep-learning models use statistical approaches and therefore make mistakes.

In a noisy star field, a GNN may correctly predict 90% of a constellation’s edges while missing a single connection or predicting a false-positive bridge between two entangled constellations.

This can produce outputs that are visually distorted or topologically impossible.

To guarantee correct reconstruction, we placed a symbolic post-processing guardrail after the GNN.

First, we run the GNN and obtain the edge probabilities for each class.

Next, we collect candidate edges with probabilities greater than 0.05, along with the candidate stars, or nodes, that form those edges.

We then perform a graph-isomorphism search using backtracking. This maps the candidate nodes onto strictly defined templates: the exact adjacency matrices for Orion, Cassiopeia, and the Big Dipper.

A shape is drawn only when the search finds a valid match that satisfies every topological connection in the constellation.

This hybrid approach combines fast noise removal through deep learning with the structural accuracy guaranteed by symbolic logic.

Performance Evaluation

We evaluated the model using a test set containing extreme coordinate jitter, global scaling, and rotation.

Test macro F1 score: 96.91%

Invariance test F1 score: 96.68%, demonstrating complete scale and rotation invariance

Topological reconstruction accuracy: 100% shape accuracy across all matched outputs

Night-Sky Quiz: Question 2 — Answer

Now it is finally time to reveal the answer to the earlier quiz.

All of the constellations were clustered on the left side. Did you find them?

Once again, the AI successfully recognized every constellation.

Conclusion

By combining a graph neural network with symbolic topological constraints, we built a system that bridges the gap between statistical pattern recognition and logical geometric truth.

The potential applications of this hybrid architecture extend far beyond observing the night sky. It can be applied to a wide range of fields, including 3D point-cloud classification, molecular mapping, and the processing of astronomical coordinates.