1
$\begingroup$

I have the following problem.

I am given a graph with a lot (>30000) nodes. Nodes are associated with a low (<10)-dimensional feature vector, and edges are associated with a low (<10)-dimensional feature vector. In addition, all nodes start out having the color white.

At every time step until completion, I want to select a subset of the nodes in the graph and color them blue. Then I receive a reward based on my coloring. I continue until all nodes are colored blue, and the total reward is the sum (maybe with a gamma factor) of my total rewards.

Do you have suggestions of papers to read where the task was choosing an appropriate subgraph from a larger graph?

Just doing a node classification task using a Graph Convolutional Network doesn't seem to do well, I suspect because, given that a good heuristic for reward is connectivity, it would need to learn to choose an optimal neighborhood in the graph and upweight only that neighborhood.

To contextualize, each of the nodes of the graph represents a constraint that will be sent to an incremental SMT solver, and edges represent shared variables or other relationships between the constraints. I have found empirically that giving these constraints incrementally to the SMT solver when in a good order can be faster than just dumping the entire problem into an SMT solver, since the SMT solver doesn't have the best heuristics for this particular SMT problem. However, eventually, I want to add all the constraints, i.e., color the entire graph. The cost is the amount of time the solver takes on each set, with a reward at the end for completing all the constraints.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.