j8typz 发表于 2024-8-31 12:06:32

Nat. Mach. Intell.：图神经网络(GNN)，组合优化


    <div style="color: black; text-align: left; margin-bottom: 10px;">
      <div style="color: black; text-align: left; margin-bottom: 10px;">
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">组合优化Combinatorial optimization问题，<span style="color: black;">广泛</span>存在于科学和工业过程。现代深度学习deep learning工具，以前所未有的规模<span style="color: black;">处理</span>了这些问题，<span style="color: black;">不外</span>，结合统计<span style="color: black;">理学</span>学见解的统一框架，仍然很迫切。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;"><span style="color: black;">近期</span>，美国 亚马逊AWS 量子<span style="color: black;">处理</span><span style="color: black;">方法</span>实验室(Amazon Quantum So</span><span style="color: black;">lutions Lab) Martin J. A. Schuetz，J. Kyle Brubaker，Helmut G. Katzgraber，在Nature Machine Intelligence上<span style="color: black;">发帖</span>，<span style="color: black;">报告</span>演示了图神经网络graph neural networks<span style="color: black;">处理</span>组合优化问题。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">该<span style="color: black;">办法</span>广泛适用于二次无约束二元优化问题形式的典型NP-hard问题，如最大割maximum cut、最小顶点覆盖minimum vertex cover、最大独立集，以及多项式无约束二元优化问题形式的Ising Spin Glasses及其高阶推广<span style="color: black;">许多</span>方面。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;"><span style="color: black;">同期</span>，一种驰豫策略relaxation strategy应用于问题哈密顿量，以生成可微分的损失函数，该损失函数可用来训练图神经网络，并在无监督训练过程完成后，简单投影应用于整数变量。</span><span style="color: black;">标准最大割集和最大独立集问题的数值结果验证了这一<span style="color: black;">办法</span>。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;"><span style="color: black;">科研</span><span style="color: black;">发掘</span>，图神经网络优化器性能，相当或优于现有解算器，并且能够扩展到超过现有技术水平，以<span style="color: black;">处理</span><span style="color: black;">拥有</span>数百万变量的问题。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><img src="https://p3-sign.toutiaoimg.com/tos-cn-i-tjoges91tu/T4YrUxuHnyXb22~noop.image?_iz=58558&amp;from=article.pc_detail&amp;lk3s=953192f4&amp;x-expires=1725642937&amp;x-signature=IIqZlzXIgvVp%2FHI3K3fk04gsRiE%3D" style="width: 50%; margin-bottom: 20px;"></p>
            <h1 style="color: black; text-align: left; margin-bottom: 10px;"><span style="color: black;">Combinatorial optimization with physics-inspired graph neural networks</span></h1><span style="color: black;">基于<span style="color: black;">理学</span>图神经网络的组合优化。</span>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><img src="https://p3-sign.toutiaoimg.com/tos-cn-i-tjoges91tu/T4YrUyV7oYsmhE~noop.image?_iz=58558&amp;from=article.pc_detail&amp;lk3s=953192f4&amp;x-expires=1725642937&amp;x-signature=I5WZTrHVPbR%2FfXDR5cwyURQ4Mhw%3D" style="width: 50%; margin-bottom: 20px;"></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">图1：组合优化图神经网络graph neural networks，GNN<span style="color: black;">办法</span>示意图。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><img src="https://p3-sign.toutiaoimg.com/tos-cn-i-tjoges91tu/T4YrUzM1b8j4JS~noop.image?_iz=58558&amp;from=article.pc_detail&amp;lk3s=953192f4&amp;x-expires=1725642937&amp;x-signature=t6XEijGM3E%2BU5Cqb0iD8A0abRQ8%3D" style="width: 50%; margin-bottom: 20px;"></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">图2：受<span style="color: black;">理学</span>学启发图神经网络GNN优化器的端到端工作流程图。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><img src="https://p3-sign.toutiaoimg.com/tos-cn-i-tjoges91tu/T4YrV0Y2MT6DMT~noop.image?_iz=58558&amp;from=article.pc_detail&amp;lk3s=953192f4&amp;x-expires=1725642937&amp;x-signature=kel23g8CzoMSLrffJmuqWQrc%2FAE%3D" style="width: 50%; margin-bottom: 20px;"></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">图3：n=100节点的随机3-正则图的最大割MaxCut示例解。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><img src="https://p3-sign.toutiaoimg.com/tos-cn-i-tjoges91tu/T4YrV2N8JHrWvg~noop.image?_iz=58558&amp;from=article.pc_detail&amp;lk3s=953192f4&amp;x-expires=1725642937&amp;x-signature=nNVngzwnv%2Fv4krQarkpcUqmjmxs%3D" style="width: 50%; margin-bottom: 20px;"></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">图4：最大割MaxCut数值结果。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><img src="https://p3-sign.toutiaoimg.com/tos-cn-i-tjoges91tu/T4YrVYL6x5XSUa~noop.image?_iz=58558&amp;from=article.pc_detail&amp;lk3s=953192f4&amp;x-expires=1725642937&amp;x-signature=od2%2BLyxmaMlY37YG4QWIHEYQC5o%3D" style="width: 50%; margin-bottom: 20px;"></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">图5：最大独立集maximum independent set，MIS问题的数值结果。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">该项<span style="color: black;">科研</span>，提出并分析了一种多功能、可扩展的通用求解器，该求解器由图神经网络GNNS<span style="color: black;">供给</span>支持，并借鉴了统计<span style="color: black;">理学</span>学理念。该<span style="color: black;">办法</span>适用于任何k-局部伊辛k-local Ising模型，<span style="color: black;">包含</span>典型NP-hard组合优化问题，如最大割、最大团、最小顶点覆盖或最大独立集问题等66。从伊辛Ising公式出发，去掉决策变量上的完整性约束，并将驰豫策略relaxation strategy应用于问题哈密顿量，以生成可微损失函数，该损失函数对图神经网络GNN的节点<span style="color: black;">暗示</span>，进行无监督训练。<span style="color: black;">而后</span>，<span style="color: black;">针对</span>图中的<span style="color: black;">每一个</span>顶点，图神经网络GNN训练以生成软分配，预测属于两个类之一的可能性。为了找到与原始问题公式一致二元（双色）标记，采用简单的投影启发式projection heuristics 。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">总体而言，这种<span style="color: black;">办法</span>，<span style="color: black;">能够</span>与现有专用求解器竞争，例如设计用于<span style="color: black;">处理</span>最大切割问题的Goemans–Williamson算法，并有可能利用统计<span style="color: black;">理学</span>学的丰富工具箱，例如<span style="color: black;">包含</span>相变<span style="color: black;">科研</span>。在当前中等规模量子时代，该<span style="color: black;">办法</span><span style="color: black;">能够</span><span style="color: black;">做为</span>新兴量子技术（<span style="color: black;">包含</span>专用量子6和量子启发退火20）的广泛适用、可扩展基准，<span style="color: black;">同期</span>不受资源限制，<span style="color: black;">亦</span>不局限于QUB形式，相干伊辛机Ising machines<span style="color: black;">亦</span>是如此。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;"><strong style="color: blue;">展望：</strong></span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">1、为更好地理解图神经网络GNN，在组合优化环境中的局限性，进一步<span style="color: black;">科研</span>是有序的、系统的图神经网络GNN，与一大类优化问题的最先进解算器，进行基准测试，<span style="color: black;">同期</span>利用图神经网络GNN实现<span style="color: black;">全部</span>全局，<span style="color: black;">包含</span>例如Graphsage或Graph Attention Networks(GATS)，以潜在地利用<span style="color: black;">重视</span>力机制，<span style="color: black;">提高</span>图神经网络GNN ansatz，该<span style="color: black;">重视</span>力机制，使得顶点能够在聚合<span style="color: black;">过程</span><span style="color: black;">时期</span>，对相邻<span style="color: black;">描述</span>neighbour representations进行加权。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">2、当在<span style="color: black;">设备</span>集群上，以小批量方式利用分布式训练时，所提出的图神经网络GNN<span style="color: black;">办法</span>，应该能够适应数亿个节点的问题规模，从而挑战几个现有解算器的能力。尽管<span style="color: black;">日前</span>实例，<span style="color: black;">重点</span><span style="color: black;">触及</span>随机初始化过程，初始节点嵌入问题，但在<span style="color: black;">将来</span>，<span style="color: black;">运用</span>预先训练的权重（迁移学习）<span style="color: black;">起步</span>训练过程，<span style="color: black;">能够</span><span style="color: black;">加强</span><span style="color: black;">处理</span>问题的时间。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">3、随机投影randomized projection<span style="color: black;">方法</span>，有望潜在地<span style="color: black;">加强</span>优化器性能，<span style="color: black;">或</span>贪心后处理greedy post-processing，<span style="color: black;">加强</span>这些策略，该后处理例程，<span style="color: black;">经过</span>一系列局部位翻转，<span style="color: black;">检测</span>局部最优性。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">4、该<span style="color: black;">办法</span><span style="color: black;">能够</span>推广到超图hypergraphsPUBO问题，其中超边hyper-edges <span style="color: black;">能够</span><span style="color: black;">包括</span>两个以上的节点，而不需要资源密集型度缩减<span style="color: black;">方法</span>，这与资源受限QUBO求解器相反。还有潜在的应用，涵盖了多体相互<span style="color: black;">功效</span>的现实世界优化问题，如在调度 scheduling 问题，或化学<span style="color: black;">发掘</span>问题。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">总之，<span style="color: black;">设备</span>学习、运筹学和<span style="color: black;">理学</span>学之间的交叉融合，开辟了许多新兴的<span style="color: black;">科研</span>方向，<span style="color: black;">最后</span><span style="color: black;">目的</span>是进一步<span style="color: black;">加强</span><span style="color: black;">处理</span>组合优化问题的能力。</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;">文献链接：https://www.nature.com/articles/s42256-022-00468-6</span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;"><span style="color: black;"><span style="color: black;">DOI</span><span style="color: black;">: https://doi.org/10.1038/s42256-022-00468-6</span></span></p>
            <p style="font-size: 16px; color: black; line-height: 40px; text-align: left; margin-bottom: 15px;">本文译自Nature。</p>

      </div>
    </div>




nykek5i 发表于 2024-9-26 06:43:01

你的话深深触动了我，仿佛说出了我心里的声音。

7wu1wm0 发表于 2024-10-6 10:46:57

你的见解独到，让我受益匪浅，非常感谢。

4zhvml8 发表于 2024-10-14 00:20:19

同意、说得对、没错、我也是这么想的等。

4zhvml8 发表于 2024-10-29 17:40:47

“沙发”（SF，第一个回帖的人）‌
页: [1]
查看完整版本: Nat. Mach. Intell.：图神经网络(GNN)，组合优化