Permutation invariance

As explained in Graph Neural Networks in Action

Permutation invariance is the property that a computation produces the same result regardless of the ordering of equivalent graph elements.

A graph can be represented with its nodes in different orders without changing the relationships between them. Permutation invariance means a graph-learning method is unaffected by that ordering: shuffling the rows and corresponding columns of an adjacency matrix should not change its performance. This makes it a useful design principle for relational data. section 1.2.4

In a graph neural network, information moves across connections between nodes. When a node gathers information from its neighbors, the aggregation operation must not depend on which neighbor appears first. Averaging, summing, or taking the maximum of neighborhood values are examples of operations that meet this requirement. section 1.5.2 section 3.4.1

Figure 3.12 A comparison of convolution over grid data (left; e.g., a 2D image) and over a graph (right).

Compare the fixed grid neighborhood of an image with a graph neighborhood defined by edges. The graph operation must handle connected nodes without relying on their order. section 3.4.1

This is an inductive bias, not a rule for every dataset. Shuffling image rows or columns changes the image; image models instead commonly seek translational invariance. Choose permutation-invariant operations when order is incidental to the relationships being modeled, rather than when position carries meaning. section 1.2.4

How Graph Neural Networks in Action covers it

How deep it goes

Defines invariance through adjacency-matrix shuffling and explains its role in neighborhood aggregation, without a formal proof or implementation.

Examples

Contrasts shuffled adjacency matrices with scrambled images and uses averaging, summing, and maximum operations over graph neighborhoods.

What it assumes

Assumes familiarity with neural-network training terms while defining permutation invariance through graph representations and neighborhood operations.

What you can do after

Evaluate/understand whether a graph neighborhood operation depends on node order when selecting an aggregation method.

How it connects

Connects adjacency matrices, inductive bias, message passing, graph convolution, neighborhood aggregation, and translational invariance.

liveBookmanning.com

Read Graph Neural Networks in Action on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Optimization Algorithms: AI techniques for design, planning, and control problemsPermutation invariance is the property that a function produces the same output regardless of the ordering of its inputs.

Compare how 2 books explain permutation invariance →

Related concepts

• positional embeddingaddressed by · A positional embedding is a learned or fixed representation that encodes an element’s position or order in a sequence and is incorporated into its content representation.
• inductive biaskind of · Inductive bias is the set of assumptions a learning method uses to favor some hypotheses or generalizations over others when learning from data.
• graph machine learningused by · Graph machine learning comprises machine-learning methods that learn representations, predictions, or patterns from graph-structured data and relationships.
• graph neural networkused by · A graph neural network is a neural-network model that learns representations or predictions from graph-structured data by combining information from connected entities.
• permutation equivariancecontrasts with · Permutation equivariance is the property that permuting equivalent inputs produces correspondingly permuted outputs.

This explainer was generated by Manning's knowledge graph from the text of Graph Neural Networks in Action. The section links point to the parts of the book it draws on.