Geometric instability of graph neural networks on large graphs

Understand

We analyse the geometric instability of embeddings produced by graph neural networks (GNNs).

• Existing methods are only applicable for small graphs and lack context in the graph domain.
• We propose a simple, efficient and graph-native Graph Gram Index (GGI) to measure such instability which is invariant to permutation, orthogonal transformation, translation and order of evaluation.
• This allows us to study the varying instability behaviour of GNN embeddings on large graphs for both node classification and link prediction.