Permutation Invariance

A function f acting on a set of elements X = {x₁, x₂, ..., xₙ} is permutation invariant if for any permutation π of the indices, f(x₁, x₂, ..., xₙ) = f(x_{π(1)}, x_{π(2)}, ..., x_{π(n)}). This is a direct consequence of the Deep Sets theorem, which proves that any such function can be decomposed into a transformation ψ applied to each element individually, followed by a symmetric aggregation function ρ (like sum, mean, or max) applied to the set of transformed elements: f(X) = ρ(ψ(xᵢ) ∀ xᵢ ∈ X). This decomposition is the architectural blueprint for all permutation-invariant neural network layers.

It is critical to distinguish permutation invariance from permutation equivariance. An invariant function produces an output that is completely unchanged by input reordering. An equivariant function, however, produces an output whose ordering changes in the same way as the input ordering. For example, a node-level GNN layer is equivariant: if you permute the input nodes, the output node features are permuted identically. A graph-level readout function (like a global sum pool) is invariant: it produces a single, fixed vector for the entire graph regardless of node order. This distinction is fundamental to designing multi-layer GNN architectures.

The aggregation function is the engine of permutation invariance in GNNs. To ensure invariance, this operator must be commutative and associative, accepting a variable number of inputs and yielding the same result irrespective of their sequence. Common choices include:

• Sum: The most expressive linear operator, capable of counting distinct features.
• Mean: Normalizes by neighborhood size, preventing feature explosion but losing count information.
• Max: Provides a non-linear, set-like operation focusing on the most salient features. The choice of aggregator directly impacts a model's ability to distinguish between different graph structures, a property studied through the lens of the Weisfeiler-Lehman (WL) graph isomorphism test.

In a Cellular Topology Graph, base stations (gNBs) are represented as nodes with no inherent, canonical ordering. A network operator may index them arbitrarily in a database. Permutation invariance guarantees that a GNN-based resource allocator or energy optimizer will produce the same global policy decision (e.g., total predicted network throughput) or the same per-node action (e.g., a power adjustment for a specific gNB) regardless of this arbitrary indexing. This property ensures the model's reasoning is based purely on the topological relationships (interference, handover adjacency) and node features (load, capacity), not on a meaningless artifact of data preparation.

Permutation invariance is not learned; it is architecturally enforced. A standard multi-layer perceptron (MLP) applied to a concatenated list of node features is not permutation invariant, as it is sensitive to the feature order. To build an invariant model, one must explicitly use operations like:

• Global pooling layers after a series of equivariant message-passing layers.
• Set Transformer blocks, which use self-attention without positional encodings.
• Janossy pooling, which averages the output of a permutation-sensitive function over many random permutations. Designing the architecture to be symmetric by construction is the only way to guarantee this property for all possible inputs.

By explicitly encoding the symmetry of the input domain, permutation invariance acts as a powerful inductive bias. This dramatically reduces the hypothesis space the model must search during training, leading to improved sample efficiency and generalization. A GNN trained on cellular topologies of a certain size can generalize to networks of different sizes and node orderings without retraining, because its fundamental operation—aggregating information from a local neighborhood—is independent of the global graph size and node indexing. This is a key advantage over non-invariant methods that would require a fixed-size, ordered input vector.