Which class of neural network problem is this?
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.