LEO Satellite Network Orchestration with Heterogeneous Graph Neural Networks

Source: arXiv:2606.31950 · Published 2026-06-30 · By Aruna Jayarajan, N. Cameron Matson, Karthikeyan Sundaresan

TL;DR

The paper addresses the challenge of real-time network orchestration in Low Earth Orbit (LEO) satellite constellations, which are highly dynamic and involve coordinating assignments between satellites, gateways, and ground user cells. Traditional local heuristics for assignment (e.g., nearest satellite or least-loaded gateway) lead to load imbalances and partial coverage, while global optimization methods are accurate but computationally prohibitive for timely operation. To overcome this, the authors propose NEO-GNN, a heterogeneous Graph Neural Network that models the satellite-ground network as a dynamic spatiotemporal heterogeneous graph with distinct node types for satellites, gateways, and cells. It is trained using constraint-based unsupervised losses to jointly maximize coverage and balanced utilization with efficient inference for real-time deployment.

NEO-GNN learns assignment policies from continuous and random temporal snapshots capturing satellite mobility and traffic patterns. Experiments on realistic Starlink-like constellations (1584 satellites, 54 gateways, 4569 cells) show that NEO-GNN achieves ∼15–25% better ground cell coverage and 20–30% higher traffic demand satisfaction compared to local heuristics, while running over 100× faster than global optimizers (inference under 620 ms vs optimizer solving minutes). The model also generalizes well to dynamic visibility changes and partial satellite failures, enabling scalable and resilient network orchestration in bent-pipe LEO systems.

Key findings

• Local heuristic assignment causes skewed demand loads, with fewer than half satellites actively serving cells, leading to poor utilization (Fig. 2).
• Global optimization reduces median satellite load but requires solving times from 2 seconds (small networks) to over 600 seconds (mid-size 4750 node networks), impractical given satellite visibility windows (Table I).
• NEO-GNN inference time is under 620 ms for a 4750-node graph, enabling near-real-time orchestration.
• On a Starlink Phase I-like constellation with 1584 satellites, 54 gateways, and 4569 ground cells, NEO-GNN improves coverage by 15–25% and demand satisfaction by 20–30% over local heuristics.
• Training on 24 hours of 20-second interval snapshots, combining continuous and random samples, enables the model to generalize across dynamic topology changes (Fig. 4).
• The heterogeneous GNN structure with separate node types and edge types for satellites, gateways, and cells allows better role-specific message passing and constraint modeling than homogeneous GNNs.
• The loss function incorporating coverage, capacity, and uniqueness constraints enables unsupervised learning of practical, balanced assignments without labeled data.
• NEO-GNN shows resilience under partial satellite failures and can adapt to localized demand or network changes via local inference onboard satellites.

Threat model

n/a — The paper focuses on operational network orchestration challenges in LEO satellite systems rather than adversarial security threats. It assumes a benign environment aiming to optimize resource allocation under physical and architectural constraints without malicious interference.

Methodology — deep read

1. Threat Model & Assumptions: The adversary model is not explicitly a security threat but operational constraints are considered. The dynamic network must assign satellites to cover ground cells and route traffic via gateways under limited satellite visibility windows and capacity constraints. Assumes bent-pipe architecture (no inter-satellite forwarding) with predictable satellite orbits.

2. Data: Uses realistic network simulations mimicking Starlink Phase I with 1,584 satellites, 54 gateways, and 4,569 hexagonal ground cells covering the US. User demand per cell is uniform (20 Mbps), satellite max capacity 3 Gbps, gateway capacity modeled based on real placements. The temporal dataset includes 24 hours with snapshots every 20 seconds, shuffled into continuous and random temporal batches for training and testing.

3. Architecture/Algorithm: Models the LEO network as a dynamic heterogeneous graph with node types—satellites, gateways, ground cells. Separate learnable embeddings (64-dim) for each type. Typed edges represent visibility: satellite-cell, satellite-gateway, satellite-satellite (used for message passing but no ISL data forwarding in current evaluation). A heterogeneous GNN with type-specific message passing aggregates neighbor embeddings. After L message passing layers, satellite embeddings feed into parallel MLP heads producing assignment probabilities to cells (sigmoid) and gateways (softmax). Assignments are probabilistic but encouraged to be unique.

4. Training regime: Unsupervised constraint-based training with a composite loss balancing (a) coverage losses ensuring all ground cells and gateways are covered, (b) capacity constraint losses penalizing load beyond satellite/gateway capacities, and (c) unique assignment losses encouraging one-to-one mappings. Loss weights are tuned for performance balance. Training occurs on temporal graph snapshots in batches of size 1, mixing continuous sequences and random samples to improve generalization. Training curves (Fig.4) show steady decline.

5. Evaluation Protocol: Benchmarked against local heuristics (nearest satellite, least-loaded gateway), global optimizer (solved with Gurobi), and network-based baselines on the same temporally disjoint test sets. Metrics include fraction of ground cells covered, aggregate demand satisfaction, and latency of assignment computation. Ablations on loss components and model variants described but detailed results are in paper. Scalability tested on varying network sizes.

6. Reproducibility: The paper does not mention public code or data release. The network simulation approximates real Starlink parameters with publicly available gate locations. Exact optimizer setup used commercial solver (Gurobi). The unsupervised nature suggests training does not rely on labeled assignments.

One concrete example: At a given 20s snapshot, the model inputs node features (positions, demands, visibility multipliers), performs L rounds of heterogeneous message passing updating node embeddings, then each satellite's MLP head outputs soft assignment scores to visible cells and gateways. The loss function penalizes uncovered cells, overloaded satellites, and multiple assignments, guiding the model to balanced real-time decisions that approach global optimum load distribution but computed orders of magnitude faster.

Technical innovations

• Modeling a dynamic LEO satellite-ground network as a heterogeneous graph with distinct node/edge types for satellites, gateways, and ground cells, enabling role-aware message passing.
• Designing unsupervised constraint-based loss functions incorporating coverage, capacity, and assignment uniqueness directly in training to avoid reliance on labeled optimal solutions.
• Using temporal training on mixed continuous and random graph snapshots capturing the dynamic satellite mobility and visibility patterns to generalize across varying network states.
• Achieving near-global optimization performance for satellite-cell-gateway assignment at over 100× speedup enabling real-time orchestration.

Datasets

• Starlink-like LEO satellite network simulation — 1,584 satellites, 54 gateways, 4,569 ground cells — based on public Starlink gateway locations and Uber H3 geospatial indexing

Baselines vs proposed

• Local heuristic (nearest satellite + least-loaded gateway): demand satisfaction ≈ 50%, coverage 75% vs NEO-GNN: demand satisfaction 70–80%, coverage 90–100%
• Global optimizer (Gurobi): achieves optimal load balancing but solver time ranges from 2s (small networks) to 600+ s (4750 nodes) vs NEO-GNN inference < 0.62 s on 4750-node network
• NEO-GNN approximates global optimization performance while enabling scalable real-time inference

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2606.31950.

Fig 4: Total training and testing loss across time-varying graph

Limitations

• Evaluation primarily targets bent-pipe architectures; ISL-enabled constellations not fully explored, limiting applicability to more advanced satellite systems.
• Demand model is uniform per cell; real-world heterogeneous demand patterns and temporal variance are not deeply evaluated.
• No explicit adversarial or malicious behavior tested (e.g., signal jamming, spoofing, or targeted satellite failures).
• Training and evaluation are conducted in simulation, and no real-world deployment or online learning scenarios demonstrated.
• Reproducibility limited by lack of public code and reliance on commercial optimizer for baseline comparisons.
• Model output assignments may still partially violate capacity constraints due to demand-capacity ratio; real system fairness impacts are not quantified.

Open questions / follow-ons

• How well does NEO-GNN generalize to highly heterogeneous and temporally varying real-world user demand profiles beyond uniform traffic assumptions?
• Can the framework be extended to incorporate inter-satellite link (ISL) architectures and joint routing decisions beyond bent-pipe models?
• What are the robustness guarantees and failure modes under adversarial attacks, e.g., satellite spoofing, gateway denial, or demand manipulation?
• How might continual online learning or domain adaptation be integrated to adjust to sudden topology or traffic shifts in deployed satellite constellations?

Why it matters for bot defense

While this paper is focused on real-time network orchestration for satellite constellations, the underlying techniques and insights have direct relevance to bot-defense and CAPTCHA practitioners working on distributed, resource-constrained, and dynamic networks. The heterogeneous graph neural network approach illustrates how to incorporate multiple node types with distinct capabilities and constraints into a unified model, a concept useful for modeling adversarial networks or client-server bot ecosystems. The unsupervised constraint-based training also provides a methodology for learning operational policies under hard system constraints without requiring fully labeled data — potentially useful for CAPTCHA challenge orchestration or bot detection where labeled attack data is scarce.

Additionally, the real-time inference requirement under mobility and partial observability mirrors challenges in CAPTCHA systems needing fast, adaptive decision-making on client interactions with limited context. Though the application domain differs, the approach to scalable embedding-based inference under constraints offers a promising direction for improving resilience and fairness in bot-defense architectures leveraging heterogeneous, evolving network data.

Cite

@article{arxiv2606_31950,
  title={ LEO Satellite Network Orchestration with Heterogeneous Graph Neural Networks },
  author={ Aruna Jayarajan and N. Cameron Matson and Karthikeyan Sundaresan },
  journal={arXiv preprint arXiv:2606.31950},
  year={ 2026 },
  url={https://arxiv.org/abs/2606.31950}
}

Read the full paper

• arXiv:2606.31950 (abstract)
• arXiv:2606.31950 (PDF)