Gasse

研究发现：图变换器在MILP上的表现受限于1-WL测试

一篇新论文对用于混合整数线性规划（MILP）的全局注意力图变换器的表达能力进行了特征化。研究证明，包括Graphormer和Set Transformer等架构在内的这些模型受到一维Weisfeiler-Leman（1-WL）测试的限制。这意味着在1-WL测试下等价的MILP实例将从这些变换器接收相同的图嵌入，从而无法恢复某些图不变量。研究表明，超越1-WL的表达能力主要来自输入编码，而非注意力机制本身。