Answers.Body: <p>The OP's (i.e. my) assumption is wrong. It is <strong>not</strong> true that for almost all random graphs under no permutation a pattern is visible, as can be  seen in Tiago P. Peixoto's paper <a href="https://arxiv.org/pdf/1705.10225.pdf" rel="nofollow noreferrer">Bayesian stochastic blockmodeling</a>, p. 4:</p>
  <p><a href="https://i.sstatic.net/Ab6pZ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Ab6pZ.png" alt="enter image description here" /></a></p>
  <p>The opposite seems to be correct: For almost all random graphs there <strong>are</strong> permutations such that patterns are visible.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-10T20:01:43.250Z
Answers.LastActivityDate: 2021-05-10T20:01:43.250Z
Answers.UserDisplayName: Hans-Peter Stricker
Answers.Body: <p>I feel the commentary about &quot;recognizable-patterns&quot; is a bit misleading.</p>
  <p>In deep-learning graphs are, usually, fed into networks called GNNs (Graph NNs).</p>
  <p>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).</p>
  <p>Basic GNNs are referred to as convolutional graph networks (GCNs) because this neighborhood-level aggregation is akin to a convolution.</p>
  <p>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!</p>
  <p><a href="https://i.sstatic.net/vBa7R.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/vBa7R.png" alt="enter image description here" /></a></p>
  <p><a href="https://arxiv.org/pdf/2112.09992.pdf" rel="nofollow noreferrer">Source</a></p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-03-03T15:24:06.260Z
Answers.Text: Related: https://ai.stackexchange.com/questions/39095/relevance-of-weisfeiler-lehman-graph-isomorphism-test-limitation-for-graph-neura
Answers.UserDisplayName: Rexcirus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-31T22:11:23.577Z
Answers.LastActivityDate: 2023-01-31T22:11:23.577Z
Answers.UserDisplayName: Mariah
Body: <p>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 <strong>almost all</strong> random graphs under <strong>no</strong> permutation a pattern is visible, but for <strong>all</strong> graphs under <strong>almost all</strong> permutations a pattern is <em>in</em>visible.</p>
  <p>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<span class="math-container">$\times$</span>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 <strong>not</strong>? Or are there any tricks?</p>
  <p>(One trick might be to draw the graph <a href="https://en.wikipedia.org/wiki/Force-directed_graph_drawing" rel="nofollow noreferrer">force-directed</a> and hope that it settles in a recognizable configuration. But this to be detectable would require a much larger pixel map than 100<span class="math-container">$\times$</span>100. But why not?)</p>
  
Tags: <neural-networks><machine-learning><pattern-recognition><geometric-deep-learning><graph-theory>
Title: How can abstract graphs be recognized by neural nets?
UserDisplayName: Hans-Peter Stricker
ThreadText: # How can abstract graphs be recognized by neural nets?
  
  (Asked by: username_0 on 2021-05-03)
  
  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 *in*visible.
  
  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](https://en.wikipedia.org/wiki/Force-directed_graph_drawing) 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?)
  
  **Tags:** neural-networks, machine-learning, pattern-recognition, geometric-deep-learning, graph-theory
  
  ---
  
  ## 2 answers
  
  ### Answer by username_0 on 2021-05-10. Score: 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](https://arxiv.org/pdf/1705.10225.pdf), p. 4:
  
  [![enter image description here](https://i.sstatic.net/Ab6pZ.png)](https://i.sstatic.net/Ab6pZ.png)
  
  The opposite seems to be correct: For almost all random graphs there **are** permutations such that patterns are visible.
  
  
  ---
  
  ### Answer by username_1 on 2023-01-31. Score: 1
  
  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!
  
  [![enter image description here](https://i.sstatic.net/vBa7R.png)](https://i.sstatic.net/vBa7R.png)
  
  [Source](https://arxiv.org/pdf/2112.09992.pdf)
  
  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.
  
  > **Comments:**
  > **username_2**: Related: https://ai.stackexchange.com/questions/39095/relevance-of-weisfeiler-lehman-graph-isomorphism-test-limitation-for-graph-neura  
  
  ---
  
  