Graph coloring is a problem with varied applications in industry and science
such as scheduling, resource allocation, and circuit design. The purpose of
this paper is to establish if a new gradient based iterative solver framework
known as heat diffusion can solve the graph coloring problem. We propose a
solution to the graph coloring problem using the heat diffusion framework. We
compare the solutions against popular methods and establish the competitiveness
of heat diffusion method for the graph coloring problem.

本文旨在使用热扩散框架解决图着色问题，并与传统方法进行比较，证明热扩散方法在图着色问题中的竞争力。

利用热扩散进行图着色

Graph Coloring Using Heat Diffusion

Combinatorial optimization problems are widespread but inherently challenging
due to their discrete nature.The primary limitation of existing methods is that
they can only access a small fraction of the solution space at each iteration,
resulting in limited efficiency for searching the global optimal. To overcome
this challenge, diverging from conventional efforts of expanding the solver's
search scope, we focus on enabling information to actively propagate to the
solver through heat diffusion. By transforming the target function while
preserving its optima, heat diffusion facilitates information flow from distant
regions to the solver, providing more efficient navigation. Utilizing heat
diffusion, we propose a framework for solving general combinatorial
optimization problems. The proposed methodology demonstrates superior
performance across a range of the most challenging and widely encountered
combinatorial optimizations. Echoing recent advancements in harnessing
thermodynamics for generative artificial intelligence, our study further
reveals its significant potential in advancing combinatorial optimization.

使用热扩散来解决组合优化问题，在全球最优搜索中提供更高效的导航，展示了在组合优化方面的卓越性能以及在推进组合优化中的潜在作用。

通过热传导实现高效的组合优化

Efficient Combinatorial Optimization via Heat Diffusion

The task of semi-supervised classification aims at assigning labels to all
nodes of a graph based on the labels known for a few nodes, called the seeds.
One of the most popular algorithms relies on the principle of heat diffusion,
where the labels of the seeds are spread by thermoconductance and the
temperature of each node at equilibrium is used as a score function for each
label. In this paper, we prove that this algorithm is not consistent unless the
temperatures of the nodes at equilibrium are centered before scoring. This
crucial step does not only make the algorithm provably consistent on a block
model but brings significant performance gains on real graphs.

半监督分类的目标是基于所知少数节点（称为种子）的标签来为图的所有节点分配标签。本文证明了在计算得分之前需要对节点的温度进行居中处理，否则该算法是不一致的。这一关键步骤不仅使得算法在块模型上可以证明是一致的，还在实际图上带来了显著的性能提升。

一种用于半监督图学习的一致性扩散算法

A Consistent Diffusion-Based Algorithm for Semi-Supervised Graph  Learning

Graph neural networks (GNNs) have demonstrated significant promise in
modelling relational data and have been widely applied in various fields of
interest. The key mechanism behind GNNs is the so-called message passing where
information is being iteratively aggregated to central nodes from their
neighbourhood. Such a scheme has been found to be intrinsically linked to a
physical process known as heat diffusion, where the propagation of GNNs
naturally corresponds to the evolution of heat density. Analogizing the process
of message passing to the heat dynamics allows to fundamentally understand the
power and pitfalls of GNNs and consequently informs better model design.
Recently, there emerges a plethora of works that proposes GNNs inspired from
the continuous dynamics formulation, in an attempt to mitigate the known
limitations of GNNs, such as oversmoothing and oversquashing. In this survey,
we provide the first systematic and comprehensive review of studies that
leverage the continuous perspective of GNNs. To this end, we introduce
foundational ingredients for adapting continuous dynamics to GNNs, along with a
general framework for the design of graph neural dynamics. We then review and
categorize existing works based on their driven mechanisms and underlying
dynamics. We also summarize how the limitations of classic GNNs can be
addressed under the continuous framework. We conclude by identifying multiple
open research directions.

图神经网络（GNNs）在建模关系型数据方面表现出显著的潜力，并被广泛应用于各个领域。图神经网络的关键机制是所谓的消息传递，其中信息从邻域迭代地聚合到中心节点。将消息传递过程类比为热扩散动力学可以从根本上理解 GNNs 的优势和局限，并进而指导模型设计。最近，出现了大量使用连续动态学的 GNNs 的作品，旨在解决 GNNs 已知的局限性，如过度平滑和过度压缩。在这项调查中，我们首次系统全面地审查了使用连续动态学视角的研究。为此，我们介绍了适应 GNNs 的连续动态学的基本要素，以及对图神经动力学设计的一般框架。然后，我们根据它们的驱动机制和基础动力学对现有作品进行了回顾和分类。我们还总结了如何在连续框架下解决经典 GNNs 的局限性。最后，我们确定了多个开放的研究方向。