I have managed to describe a problem in quantum computing as the optimization of a function f(graph,vector), over graphs and real vectors. For a given graph, I can optimize the vector with standard methods (say, gradient descent), but the search over graphs has to be a brute force random search, because I don't know what makes a graph 'good' for this application.

In any case, computing the value of f for a given graph and a given vector takes a time of the order of seconds, so even if I already knew good graphs the optimization of the vector would be feasible yet time consuming.

What I would love to try is to train a NN to find good pairs of graphs and vectors. Where do I start from? What kind of NN problem is this?

  • $\begingroup$ I suspect you'd be better off by first trying to apply standard optimization techniques to f. You say you don't know what makes a graph "good", but you can still potentially apply optimization methods. What can you tell us about f? Does it have any structure? Can it be described concisely? Does it have any kind of "continuity" properties (small changes to the graph often lead to only small changes to the value of f(graph,vector)), and if so, what do you think they might be? $\endgroup$ – D.W. Apr 7 '17 at 16:50
  • $\begingroup$ f in my case is computed by an algorithm, but mathematically speaking it is an extreme value of an inner product. The graph represents a network of quantum interactions, the vector is a specification of their strength and f is a measure of the network performance. $\endgroup$ – Ziofil Apr 8 '17 at 7:47

If I understand the question correctly, you want to find the optimum of the function $F(G) := \min_{v\in V} f(G,v)$*, where $V$ is your vector space, over all valid graphs $G$. Additionally, you can compute $F(G)$ for any given graph.

First of all, I doubt only neural networks are going to be very helpful. The main strength of neural networks is to classify given training data. Judging from your question, I doubt training data is abundant.

The general problem of heuristically** optimizing an arbitrary function (here: $F$) over a discrete solution space (here: all valid graphs $G$) is usually solved by applying metaheuristics, such as local search methods (e.g. Hill climbing, simulated annealing, tabu search) or evolutionary algorithms.

These methods require you specify some structure of your solution space.

For local search, you need to define a neighbour relation between solutions to provide structure, such that

  • The neighbour relation is symmetric

  • Any two solutions are 'reachable' from another by

  • The difference in $F$ between neighbours is usually (hopefully?) low.

For this problem, we could consider two graphs neigbours if we can reach the other by removing or adding an edge. This is clearly symmetric and all solutions are reachable if we assume all graphs have the same vertices. Then, all that's left is to hope that the network performance $F(G)$ usually doesn't change much if we remove/swap two edges.

Most likely, this neighbour relation does not suffice, as this is very problem-specific. If you have such a neighbour relation, you can apply some local search method and get a hopefully good answer.

*: (You may want the maximum instead, but that doesn't really change anything, of course)

**: In other words, we 'attempt' to find a good answer without any optimality guarantees. Note that this is even 'weaker' than approximation. These methods are often justified, as many optimisation problems over discrete domains cannot even be approximated efficiently. I think this is acceptable, as neural networks usually cannot guarantee any optimality either.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.