How can abstract graphs be recognized by neural nets?

Question

Recognition of optical patterns (as pixel maps) by neural networks is standard. But optical patterns may be only slightly distorted or noisy, and may not be arbitrarily scrambled – e.g. by permutations of rows and columns of the pixel map – without losing the possibility to recognize them. This in turn is the normal case for abstract graphs in their standard representation as adjacency matrices: only under some permutations of nodes a possible pattern is visible. In general, for almost all random graphs under no permutation a pattern is visible, but for all graphs under almost all permutations a pattern is invisible.

How can this be handled in the context of either unsupervised or supervised learning? Assume you have a huge set of graphs with 100 nodes and 1,000 edges, given as 100$\times$100 adjacency matrices under arbitrary permutations, but with only two isomorphism classes. How could a neural network find this out and learn from the samples? Is this possibly common knowledge: that it can not? Or are there any tricks?

(One trick might be to draw the graph force-directed and hope that it settles in a recognizable configuration. But this to be detectable would require a much larger pixel map than 100$\times$100. But why not?)

Answer 1

The OP's (i.e. my) assumption is wrong. It is not true that for almost all random graphs under no permutation a pattern is visible, as can be seen in Tiago P. Peixoto's paper Bayesian stochastic blockmodeling, p. 4:

The opposite seems to be correct: For almost all random graphs there are permutations such that patterns are visible.

Answer 2

I feel the commentary about "recognizable-patterns" is a bit misleading.

In deep-learning graphs are, usually, fed into networks called GNNs (Graph NNs).

GNNs work by updating features on nodes or edges, with message-passing: neighborhoods of each node/edge are aggregated in a way that is permutation invariant (to deal with many digital representations of the same graph).

Basic GNNs are referred to as convolutional graph networks (GCNs) because this neighborhood-level aggregation is akin to a convolution.

But GCN's power is limited by what's called the 1-WL test. More plainly, GCNs can fail to distiniguish two non-isomorphic graphs. For example, imagine two non-isomorphic graphs that are locally the same!

Source

So in your case, you have a bunch of graphs but only two isomorphism classes - a GNN will definitely return the same output for graphs within the same class (because locally, and also globally but that isn't relevant, they are the same). Whether they can distinguish between the classes depends on the examples themselves.