0
$\begingroup$

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?)

$\endgroup$
0

1 Answer 1

0
$\begingroup$

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:

enter image description here

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .