PaperlayerView exact revision on arXiv

Source-linked AI summary

Congruence Decomposition with Neural Block Solvers for Large-Scale PCI Assignment

Yeqing Qiu, Chengpiao Huang, Ye Xue, Akang Wang, Fan Xu, Zhipeng Jiang, Dong Zhang, Ruoyu Sun, Qingjiang Shi, Zhi-Quan Luo

arXiv:2608.21485v1cs.LGeess.SP

TL;DR

Large-scale 5G deployments require intelligent optimization of network parameters for interference management, while PCI assignment must jointly address modular interference, collisions, and confusions. The paper uses congruence decomposition with GNN-based neural block solvers and reports lower interference, eliminated conflicts, and improved computational efficiency across synthetic and real-world cellular networks.

  • Problem

    Large-scale 5G deployments need effective optimization of network parameters because dense environments expose a gap between theoretical capabilities and actual user experience, while PCI assignment involves coupled modular interference, collision, and confusion objectives.

  • Method

    The framework exploits arithmetic relations among PCI moduli to decompose modular assignment into blockwise Min-k-Partition subproblems, solves them with GNN parameterization, and uses graph coloring for collision and confusion constraints.

  • Results

    Across synthetic and real-world cellular networks, the method simultaneously reduces collisions and confusions, achieves the lowest multi-modular interference among competitive baselines, and reaches a 2.04× speedup over the strongest decomposition-based baseline on a network with thousands of cells.

  • Takeaways & Limitations

    The MMD framework addresses collision and confusion elimination, while GPO improves the performance and efficiency of multi-modular interference optimization for large-scale PCI assignment.

Abstract

from arXiv · show

Physical Cell Identity (PCI) assignment is essential for interference management in dense 5G networks. As cellular networks scale, PCI reuse becomes unavoidable, which may cause collisions, confusions, and multiple forms of modular interference. Jointly mitigating these effects gives rise to a large-scale, multi-objective combinatorial optimization problem that is difficult to solve efficiently at practical network scales. In this work, we propose a congruence decomposition framework with neural block solvers for large-scale PCI assignment. The proposed decomposition exploits the arithmetic structure of PCI values to decouple multiple modular interference objectives into a collection of blockwise Min-$k$-Partition subproblems, followed by a graph coloring procedure to resolve PCI conflicts. For the resulting NP-hard Min-$k$-Partition subproblems, we develop neural block solvers by parameterizing their relaxed quadratic formulations with graph neural networks, enabling efficient optimization at large scales. Discrete assignments are recovered through conditional expectation rounding with theoretical guarantees. Experiments on synthetic cellular graphs and real-world 5G networks show that the proposed method consistently outperforms existing modular-interference-aware baselines in modular interference reduction, conflict elimination, and computational efficiency.

I. Introduction

Dense 5G PCI assignment must jointly manage collisions, confusions, and multiple modular-interference objectives, creating a large-scale combinatorial problem. The paper proposes congruence decomposition with neural block solvers and reports improved interference reduction, conflict elimination, and scalability.

  • Motivation: Dense 5G deployments make PCI reuse unavoidable, so improper assignments can create collisions, confusions, and modular interference.
  • Related Work: Existing graph-coloring methods address collisions and confusions but omit arithmetic residue relations that induce modular interference.
  • Contributions: The proposed framework exploits arithmetic relations among moduli to decompose modular objectives into blockwise Min-k-Partition problems, followed by graph coloring for conflicts.
  • Contributions: Neural block solvers parameterize relaxed Min-k-Partition solutions with GNNs, while deterministic conditional-expectation rounding recovers discrete assignments without increasing the relaxed objective.
  • Evaluation: On synthetic and real-world cellular networks, the method reduces collisions and confusions, achieves the lowest multi-modular interference among competitive baselines, and reaches a 2.04× speedup on a network with thousands of cells.
  • Problem Formulation: The PCI problem assigns each cell a value in Z1008 while minimizing modular interference and eliminating collisions and confusions under common moduli (3, 4, 6, 30).

III. Congruence Decomposition for Multi-Modular PCI Assignment

The congruence decomposition converts multiple modular PCI objectives into structured blockwise optimization by separating modular residues from quotient variables. Each block update becomes a weighted Min-k-Partition problem, and monotone block coordinate descent terminates in finitely many updates.

  • Decomposition Framework: PCI values are represented through a common modulus p = lcm(p1, ..., pm), separating a residue r that determines interference from a quotient q that resolves remaining conflicts.
  • Decomposition Framework: Because interference depends only on r, the problem separates into modular assignment for interference minimization and quotient assignment for residual conflict elimination.
  • Arbitrary Modular Objectives: For arbitrary, possibly noncoprime moduli, CRT and su-adic decomposition represent modular congruences through subsets of prime-power coefficient blocks.
  • Arbitrary Modular Objectives: The blockwise reformulation replaces each modular congruence with equality constraints on selected coefficient blocks.
  • Blockwise Optimization: Sequentially updating one block while fixing the others yields a weighted Min-k-Partition subproblem with k = s_u^δu,h.
  • Convergence: Under accepted updates that decrease their associated objectives, the resulting block coordinate descent procedure terminates after finitely many updates.
  • PCI Specialization: For moduli 3, 4, 6, and 30, p = 60 and four residue blocks encode the objectives as nested blockwise equality relations.

C. Graph Coloring for Quotient Assignment

The quotient-assignment subproblem becomes graph coloring on a restricted graph containing pairs with identical remainders, followed by heuristic adjustment to enforce the PCI range constraint.

  • The restricted edge set contains constrained cell pairs whose mod-p remainders are identical.
  • Quotient assignment reduces to graph coloring on (V, E′), with colors representing quotient values.
  • GGC provides an efficient approximate solution to the quotient-coloring problem.
  • Violations of pqi + ri ∈ Z1008 are corrected by reassigning feasible quotients that minimize additional collisions and confusions.Violating nodes are processed in descending order of degree, including second-order neighbors.
  • The overall stage combines graph coloring with tailored feasibility adjustment.

D. Summary

The framework alternates blockwise modular-interference minimization with graph coloring for collision and confusion handling, producing a complete PCI assignment procedure.

  • The framework has two stages: blockwise Min-k-Partition solves for modular interference, followed by graph coloring under the PCI range constraint.
  • Multi-modular decomposition generalizes graph partitioning beyond the coprime setting by solving a sequence of block subproblems.
  • The neural block solver, GPO, addresses the resulting weighted Min-k-Partition problems.
  • Algorithm 1 takes an interference matrix, edge set, modulus set, and weights, and returns a PCI assignment.
  • The procedure iterates over mod-p assignment blocks and updates them until no improving block update remains.
  • After constructing a restricted edge set, the method applies GGC and heuristically reassigns quotients that violate the PCI range.

A. Effective Block Graph Construction

For each decomposition block, the method constructs an effective weighted graph whose edges capture the interference contributions remaining under the current block assignments.

  • Each block induces an effective weighted graph over N nodes, with weights representing relevant interference contributions conditioned on other assignments.
  • Product masks remove node pairs whose modular equality has already been broken by fixed active blocks.
  • The block problem is formulated as a weighted Min-k-Partition problem.
  • The block assignment is encoded as a one-hot matrix X ∈ {0, 1}N×k, yielding a quadratic objective.

B. GNN-Parametrized Relaxed Optimization

The neural solver relaxes each discrete block assignment to simplex-valued variables and uses a GNN to optimize the resulting quadratic objective in a graph-aware way.

  • The discrete problem is relaxed over the Cartesian product of N k-dimensional probability simplices.
  • A GNN parameterizes the relaxed assignment because the Min-k-Partition gradient has the form of weighted neighborhood aggregation.
  • The GNN uses trainable node embeddings and layered message passing with weighted neighbor aggregation.
  • A final row-wise softmax produces simplex-valued outputs.
  • Parameters are optimized separately for each weighted block instance, and the relaxed solution is obtained by one forward evaluation.

C. Conditional Expectation Rounding

Conditional expectation rounding deterministically converts a relaxed Min-k-Partition solution into a feasible discrete assignment without increasing the objective. Incremental edge-local updates reduce the rounding complexity, while monotone refinement can further improve the result.

  • C. Conditional Expectation Rounding: Randomized rounding preserves the relaxed objective only in expectation, motivating derandomization through conditional expectation.The auxiliary product distribution makes the relaxed objective equal to the expected randomized objective.
  • C. Conditional Expectation Rounding: The method fixes each node to the label with minimum conditional cost, producing a deterministic discrete feasible solution no worse than the relaxed input.The guarantee is established through conditional expectation and summarized by Theorem IV.1.
  • C. Conditional Expectation Rounding: The incremental implementation reduces rounding complexity from O(k^2N|E|) to O(k|E|) by updating edge-local expectations only when nodes are fixed.This avoids independently recomputing conditional costs for every node.

D. Edge-Based Refinement

The complete block solver combines instance-wise GNN optimization, deterministic rounding, and edge-based refinement. Compared with PMD, it avoids penalty tuning and restricts local search to interference-relevant edges, improving scalability while preserving monotone improvement.

  • D. Edge-Based Refinement: The GNN-parametrized solver optimizes a relaxed block assignment, applies conditional expectation rounding, and then refines the discrete labels by edge-based local search.These are the three stated stages of the proposed Min-k-Partition solver.
  • D. Edge-Based Refinement: Unlike PMD's penalty-based iterative quadratic approach, the proposed solver directly optimizes a penalty-free simplex relaxation through graph-aware GNN parametrization.The contrast removes the outer penalty-parameter loop used by PMD.
  • D. Edge-Based Refinement: Edge-restricted refinement examines only interference-relevant pairs rather than all node pairs, reducing local-search overhead while retaining monotonic improvement.Every accepted move decreases the objective.
  • D. Edge-Based Refinement: Fig. 3 averages results across synthetic graphs varying network size and connection radius, while the experiments jointly evaluate modular interference, conflicts, and runtime.The evaluation includes MMD-GPO, MMD-PMD, and four additional baselines.

B. Synthetic Data Experiments

Synthetic experiments use random geometric graphs spanning three network sizes and three spatial densities, with 20 instances per configuration. MMD-GPO achieves low modular interference, eliminates conflicts, and scales better than decomposition-based alternatives, consistent with real-world evaluations.

  • B. Synthetic Data Experiments: Synthetic networks use RGG(N, r), with cells uniformly distributed in a unit square and interference inversely proportional to Euclidean distance.The model represents spatial wireless interference through geometric neighborhoods and weighted edges.
  • B. Synthetic Data Experiments: The study varies N ∈{500, 1000, 2000} and r ∈{0.05, 0.1, 0.2}, generating 20 independent instances for each of nine configurations.The radii represent sparse, medium, and dense graphs, yielding 180 instances overall.
  • B. Synthetic Data Experiments: MMD-GPO and MMD-PMD achieve substantially lower modular interference than other baselines, with MMD-GPO consistently outperforming MMD-PMD.The comparison supports both the decomposition framework and the additional gain from GPO.
  • B. Synthetic Data Experiments: MMD-GPO and MMD-PMD completely eliminate collisions and confusions across all synthetic settings, whereas remaining heuristics retain conflicts as network size grows.GGC also reaches zero conflicts but does not optimize modular interference.
  • B. Synthetic Data Experiments: For N ≥1000, MMD-GPO is substantially faster than MMD-PMD across completed settings, while MMD-PMD times out on the largest instances.Per-instance GNN optimization cost is included in the reported runtime.
  • B. Synthetic Data Experiments: On 2,000-cell real-world data, MMD-GPO improves interference over MMD-PMD by 2.8% and runs about 2× faster while preserving conflict-free feasibility.It also outperforms other modular-interference-aware baselines by 3.4% ∼53%.

Appendix A Proof of Theorem III.1

The proof establishes the congruence characterization through prime-power digit equalities and proves that conditional expectation rounding returns a discrete assignment no worse than the relaxation.

  • Congruence equivalence: Congruence modulo the composite interference modulus is equivalent to satisfying the corresponding congruences for every prime factor.The proof reduces the global congruence condition to prime-power conditions.
  • Congruence equivalence: Each prime-power congruence is equivalent to equality of all base-s_u digits below the relevant positional-weight threshold.The argument uses sorted s_u-adic exponents and uniqueness of the expansion.
  • Congruence equivalence: Collecting the digit-equality conditions over all prime factors yields exactly the required blockwise equalities for every (u, h) in J_l.This completes the equivalence between the modular condition and the block constraints.
  • Rounding guarantee: Sequentially fixing each node according to conditional expectation rounding does not increase the conditional expected objective.The argument applies the law of total expectation at each node-fixing step.
  • Rounding guarantee: The resulting discrete assignment has objective value no larger than the relaxed solution.This deterministic guarantee avoids relying only on repeated randomized trials.

Appendix D Efficient Implementation of Algorithm 2

The implementation rounds relaxed simplex assignments incrementally by maintaining edge-local expectations, selecting the best label per node, and updating only affected edges.

  • Incremental rounding: The procedure maps the relaxed assignment X in the simplex product to a discrete one-hot assignment.The discrete output is evaluated using the original objective.
  • Incremental rounding: For each candidate label, the algorithm evaluates only changes on edges incident to the node being fixed.Neighbor contributions use fixed labels when available and relaxed probabilities otherwise.
  • Incremental rounding: Each node receives the label minimizing its incremental objective change, after which affected edge-local quantities are updated.This avoids recomputing the full quadratic form at every step.
  • Complexity: O(k|E|) total time is achieved for initialization and rounding, improving over the naive O(k2N|E|) rounding complexity.The bound follows from inspecting incident edges incrementally across all node-label evaluations.
Loading 2608.21485v1…