Geometric instability of graph neural networks on large graphs
This addresses a methodological gap for researchers working with GNNs on large-scale graph data, though it appears incremental as it builds on existing instability analysis by extending it to larger graphs.
The paper tackles the problem of analyzing geometric instability in embeddings from graph neural networks (GNNs) on large graphs, proposing a Graph Gram Index (GGI) that is invariant to various transformations and enabling study of instability for node classification and link prediction.
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.