Quadratic Unconstrained Binary Optimization (QUBO) is a generic technique to
model various NP-hard Combinatorial Optimization problems (CO) in the form of
binary variables. Ising Hamiltonian is used to model the energy function of a
system. QUBO to Ising Hamiltonian is regarded as a technique to solve various
canonical optimization problems through quantum optimization algorithms.
Recently, PI-GNN, a generic framework, has been proposed to address CO problems
over graphs based on Graph Neural Network (GNN) architecture. They introduced a
generic QUBO-formulated Hamiltonian-inspired loss function that was directly
optimized using GNN. PI-GNN is highly scalable but there lies a noticeable
decrease in the number of satisfied constraints when compared to
problem-specific algorithms and becomes more pronounced with increased graph
densities. Here, We identify a behavioral pattern related to it and devise
strategies to improve its performance. Another group of literature uses
Reinforcement learning (RL) to solve the aforementioned NP-hard problems using
problem-specific reward functions. In this work, we also focus on creating a
bridge between the RL-based solutions and the QUBO-formulated Hamiltonian. We
formulate and empirically evaluate the compatibility of the QUBO-formulated
Hamiltonian as the generic reward function in the RL-based paradigm in the form
of rewards. Furthermore, we also introduce a novel Monty Carlo Tree
Search-based strategy with GNN where we apply a guided search through manual
perturbation of node labels during training. We empirically evaluated our
methods and observed up to 44% improvement in the number of constraint
violations compared to the PI-GNN.

通过引入 QUBO 变换哈密顿量和建立 RL 模型的奖励函数，我们提出了一种改进 PI-GNN 算法的方法，并采用 Monty Carlo Tree Search 策略和 GNN 结合进行训练，实验结果表明在满足约束条件方面有 44% 的改进。

基于图神经网络的 QUBO 规划激发哈密顿损失函数用于组合优化的强化学习

A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss  Function for Combinatorial Optimization using Reinforcement Learning

Many real-world graph learning tasks require handling dynamic graphs where
new nodes and edges emerge. Dynamic graph learning methods commonly suffer from
the catastrophic forgetting problem, where knowledge learned for previous
graphs is overwritten by updates for new graphs. To alleviate the problem,
continual graph learning methods are proposed. However, existing continual
graph learning methods aim to learn new patterns and maintain old ones with the
same set of parameters of fixed size, and thus face a fundamental tradeoff
between both goals. In this paper, we propose Parameter Isolation GNN (PI-GNN)
for continual learning on dynamic graphs that circumvents the tradeoff via
parameter isolation and expansion. Our motivation lies in that different
parameters contribute to learning different graph patterns. Based on the idea,
we expand model parameters to continually learn emerging graph patterns.
Meanwhile, to effectively preserve knowledge for unaffected patterns, we find
parameters that correspond to them via optimization and freeze them to prevent
them from being rewritten. Experiments on eight real-world datasets corroborate
the effectiveness of PI-GNN compared to state-of-the-art baselines.

本文提出一种参数隔离的图神经网络（PI-GNN）方法，通过扩展模型参数并冻结不受动态图影响的参数以保留之前学习的知识，解决动态图学习中的灾难性遗忘问题，实验证明其优于现有方法。