Order doesn't matter: permutation invariance

The same shape can be listed in very many orders

A permutation is a reordering of a list. Three points A, B and C can be listed in 3 × 2 × 1 = 6 orders: ABC, ACB, BAC, BCA, CAB and CBA. In general, n points have n! orders ("n factorial", the product 1 × 2 × … × n). That number grows fast: 10 points have 3,628,800 orders, and 1,000 points have a number of orders with 2,568 digits.

A program that stores a cloud has to pick one order, often the order a scanner happened to produce. A model could try to learn that order does not matter by seeing many shuffled copies of each cloud. With so many orders, it could never see them all. So models for point sets build the property in.

Some summaries ignore the order, and some do not

Take the points A = (1, 2), B = (4, 0) and C = (2, 3), and list them twice: as A, B, C and as C, A, B.

Predict first. For each summary in the table, will the two orders give the same answer?

The last row is a warning about networks. A linear layer fed the coordinates as one long list, [x₁, y₁, x₂, …], gives every place its own weight, exactly like that row. So it is not permutation invariant, and it also cannot accept a different number of points.

Answers for each point should move with their points

Some functions give one answer per point, such as a label for each point or the sum x + y of each point. For the order A, B, C that sum gives [3, 4, 5]. For the order C, A, B it gives [5, 3, 4]: the same answers, reordered the same way as the points. That is permutation equivariance. Each point keeps its own answer, wherever it sits in the list.

Models of point sets usually combine the two properties. First they run equivariant steps that compute features for each point, such as the same small network applied to every point, or attention without position information. Then they take one invariant step, such as a sum or a maximum, to summarize the whole set. PointNet pooling is the simplest example.

permutation.py

import numpy as np

P = np.array([[1.0, 2.0], [4.0, 0.0], [2.0, 3.0]])   # A, B, C
Q = P[[2, 0, 1]]                                     # the same points as C, A, B
w = np.array([1.0, 2.0, 3.0])                        # one weight per list position

print(P.sum(axis=0), Q.sum(axis=0))    # invariant
print(P.max(axis=0), Q.max(axis=0))    # invariant
print(w @ P, w @ Q)                    # rows weighted by w, then added: not invariant
print(P.sum(axis=1), Q.sum(axis=1))    # x + y of each point: equivariant

[7. 5.] [7. 5.]
[4. 3.] [4. 3.]
[15. 11.] [16.  7.]
[3. 4. 5.] [5. 3. 4.]