Questions about the action space and the calculation of Q(s,a) about finder

[FFrankyy]

Thanks for your interests.
Q1. I want to ask about the way you calculate Q(s,a). After obtained the node embedding, and the graph embedding, do you throw them into some NN models to calculate Q(s, a)? By concating node embedding and graph embedding and then throw them into MLP?
A1. Before we feed action embedding and state embedding into MLP, we use cross product to model their finer dependencies, see the supplementary information for more details.

Q2. The representation of action. May I ask that how you define the action space? I mean, if the DRL ouptuts a scalar as the action, and if the graph's labels are permuted, how does the policy network output the same action? Sorry if I missed to see them in your supplemententary information. It seems that there is no clear definition. Did I miss to notice them?

A2. The action space is defined as the whole nodes, which we label them in a random order initially, and it has no effects to the final results. Each step, we just set the Q values of those nodes that have been removed to be negative infinity, as as to avoid choosing those invalid actions, on the basis of Q greedy strategy.

Q3. The node embedding, especially for a larger graph( 50 or 100 nodes), after passing the GNN model, would be similar to some node. For example, node A and nobe B may has the same embedding, so the policy network cannot determine which node to remove. Do you also notice this problem?

A3. For this case, we just randomly choose these nodes with the same Q values, and we find it not matter.

Q4. If the action space is fixed in the training process, how does it scale to larger graphs when testing? I thinks it is restricted by both GNN module and DRL action space.

A4. GNN models' parameters are independent of the graph scale, once trained well, the input graph can be larger than what it was trained on. For DRL, or especially Q function, the input is the node embedding and state embedding, once we feed Q with these two embeddings, it can output the Q value, which is still independent of the graph scale. Both of them contribute to the inductivity of FINDER, i.e., train on small scale graphs, and test on larger instances.

[FFrankyy]

Thanks for your interests.

Q1. I want to ask about the way you calculate Q(s,a). After obtained the node embedding, and the graph embedding, do you throw them into some NN models to calculate Q(s, a)? By concating node embedding and graph embedding and then throw them into MLP?

A1. Before we feed action embedding and state embedding  into MLP, we use cross product to model their finer dependencies, see the supplementary information for more details.

Q2. The representation of action. May I ask that how you define the action space? I mean, if the DRL ouptuts a scalar as the action, and if the graph's labels are permuted, how does the policy network output the same action? Sorry if I missed to see them in your supplemententary information. It seems that there is no clear definition. Did I miss to notice them?

A2. The action space is defined as the whole nodes, which we label them in a random order initially, and it has no effects to the final results. Each step, we just set the Q values of those nodes that have been removed to be negative infinity, as as to avoid choosing those invalid actions, on the basis of Q greedy strategy.

Q3. The node embedding, especially for a larger graph( 50 or 100 nodes), after passing the GNN model, would be similar to some node. For example, node A and nobe B may has the same embedding, so the policy network cannot determine which node to remove. Do you also notice this problem?

A3. For this case, we just randomly choose these nodes with the same Q values, and we find it not matter.

Q4. If the action space is fixed in the training process, how does it scale to larger graphs when testing? I thinks it is restricted by both GNN module and DRL action space.

A4. GNN models' parameters are independent of the graph scale, once trained well, the input graph can be larger than what it was trained on. For DRL, or especially Q function, the input is the node embedding and state embedding, once we feed Q with these two embeddings, it can output the Q value, which is still independent of the graph scale. Both of them contribute to the inductivity of FINDER, i.e., train on small scale graphs, and test on larger instances.

[yangysc]

Thanks for your reply. It's very helpful.