In that post, you say that you have a graph of 10100 vertices with a particular structure. In that scenario, where is that structured graph of 10100 vertices coming from? Presumably there’s some way you know the graph looks like this
rather than looking like this
If you know that your graph is a nice sparse graph that has lots of symmetries, you can take advantage of those properties to skip redundant parts of the computation (and when each of your 10100 nodes has at most 100 inbound edges and 100 outbound edges, then you only have on the order of a trillion distinct nodes (if we consider e.g.(0, 0, 0, ..., 0, 0, 1) to be identical to (0, 0, 0, ..., 0, 1, 0, ..., 0, 0, 0)).
It’s probably worth looking at the process which is generating this graph, and figuring out if we can translate the output of that process directly to a coordinate in our 100-dimensional space without going through the “translate the output to a graph, and then embed that graph” intermediate step.
The point is that you are just given some graph. This graph is expected to have subgraphs which are lattice graphs. But you don’t know where they are. And the graph is so big that you can’t iterate the entire graph to find these lattices. Therefore you need a way to embed the graph without traversing it fully.
In that post, you say that you have a graph of 10100 vertices with a particular structure. In that scenario, where is that structured graph of 10100 vertices coming from? Presumably there’s some way you know the graph looks like this
rather than looking like this
If you know that your graph is a nice sparse graph that has lots of symmetries, you can take advantage of those properties to skip redundant parts of the computation (and when each of your 10100 nodes has at most 100 inbound edges and 100 outbound edges, then you only have on the order of a trillion distinct nodes (if we consider e.g.
(0, 0, 0, ..., 0, 0, 1)to be identical to(0, 0, 0, ..., 0, 1, 0, ..., 0, 0, 0)).It’s probably worth looking at the process which is generating this graph, and figuring out if we can translate the output of that process directly to a coordinate in our 100-dimensional space without going through the “translate the output to a graph, and then embed that graph” intermediate step.
The point is that you are just given some graph. This graph is expected to have subgraphs which are lattice graphs. But you don’t know where they are. And the graph is so big that you can’t iterate the entire graph to find these lattices. Therefore you need a way to embed the graph without traversing it fully.