arxiv: 2605.05330 · v1 · submitted 2026-05-06 · 💻 cs.LG · cs.AI· cs.DM· cs.NE

Recognition: unknown

Graph Normalization: Fast Binarizing Dynamics for Differentiable MWIS

Laurent Guigues

Authors on Pith no claims yet

Pith reviewed 2026-05-08 16:32 UTC · model grok-4.3

classification 💻 cs.LG cs.AIcs.DMcs.NE

keywords graph normalizationmaximum weight independent setmajorization minimizationreplicator dynamicsmotzkin straus theoremdifferentiable optimizationevolutionary games

0 comments

The pith

Graph Normalization converges to binary indicators of maximum independent sets via a majorization-minimization dynamical system on graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents Graph Normalization as a dynamical system that approximates the NP-hard Maximum Weight Independent Set problem in a differentiable manner. It establishes that GN always converges to a binary solution indicating a maximum independent set, providing theoretical guarantees absent in methods like Belief Propagation. This convergence occurs through repeated exact majorization-minimization steps that improve the relaxed primal objective. The system is shown equivalent to replicator dynamics in an evolutionary game where fitness increases according to Fisher's theorem. Such properties enable its use in deep learning for handling hard constraints differentiably.

Core claim

Graph Normalization realizes a fast quasi-Newton descent on graphs through an exact Majorization-Minimization step that systematically improves the MWIS relaxed primal objective. We prove that GN always converges to a binary indicator of a Maximum Independent Set. GN is equivalent to the Replicator Dynamics of a nonlinear evolutionary game in which vertices compete for inclusion in an independent set, and the average fitness equals the MWIS objective and strictly increases. This yields a weighted extension of the Motzkin-Straus theorem in which maximum independent sets correspond to local minima of a quadratic form over a tilted simplex. For the assignment problem, GN acts as a Sinkhorn-like

What carries the argument

The Graph Normalization dynamical system, which performs exact majorization-minimization updates to produce fast binarizing dynamics for MWIS.

If this is right

GN serves as a fast binarization post-processor for state-of-the-art relaxed MWIS solvers such as Bregman-Sinkhorn.
On real-world benchmarks with up to one million edges, GN finds high-quality solutions in seconds on a CPU.
The method generalizes to the assignment problem by naturally producing hard assignments while respecting arbitrary constraint graphs.
GN enables differentiable hard decisions under constraints for applications including structured sparse attention and dynamic network pruning.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The evolutionary game interpretation could allow borrowing techniques from population dynamics to design new optimization algorithms for other graph problems.
Integrating GN into neural network architectures might improve performance on tasks requiring discrete selections such as mixture-of-experts routing.
Since GN improves the primal objective at each step, it could be used to refine solutions from other heuristics in a principled way.

Load-bearing premise

The majorization-minimization step is exact and the dynamical system is well-defined with the claimed convergence properties for arbitrary undirected graphs.

What would settle it

A specific undirected graph and weight assignment where running the GN iterations fails to reach a binary vector or where the objective value does not increase monotonically.

Figures

Figures reproduced from arXiv: 2605.05330 by Laurent Guigues.

**Figure 2.** Figure 2: Examples of Continuous GN Atoms. 3. Empty: F(A) = ∅ otherwise. Most GN atomic spectra are empty. We say that a graph with a non empty spectrum is Atomic. Regular graphs are always atomic: indeed if A is d-regular then the uniform vector x0 = 1 d+11 is always a solution of Bx0 = 1 2 . Among regular graphs, some have a discrete spectrum (e.g. the 4-cycle C4), i.e., are only normalized for uniform weights, bu… view at source ↗

**Figure 3.** Figure 3: Energy profiles on K2 w0 γ = 1 4 γ = 1 2 γ = √ 1 2 γ = 1 γ = √ 2 γ = 2 γ = 4 1 0.0 0.5 1.0 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 0.0 0.5 1.0 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 0.0 0.5 1.0 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 0.0 0.5 1.0 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 0.0 0.5 1.0 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 0.0 0.5 1.0 0.00 0.25 0.50 0.75 1.00 1.25 1.5… view at source ↗

read the original abstract

We introduce Graph Normalization (GN), a principled dynamical system on graphs that serves as a differentiable approximation engine for the NP-hard Maximum Weight Independent Set (MWIS) problem. MWIS encompasses many combinatorial challenges, including optimal assignment, scheduling, set packing, and MAP inference in discrete Markov Random Fields. Unlike Belief Propagation, we prove GN always converges to a binary indicator of a Maximum Independent Set. GN realizes a fast quasi-Newton descent through an exact Majorization-Minimization step, systematically improving the MWIS relaxed primal objective. We establish an equivalence between GN and the Replicator Dynamics of a nonlinear evolutionary game, where vertices compete for inclusion in an independent set. While a non-potential game, the GN game follows Fisher's Fundamental Theorem of Natural Selection, where the average fitness equals the MWIS primal objective and strictly increases. This connection leads to a weighted extension of the Motzkin-Straus theorem, showing MISes are in bijection with the local minima of a quadratic form over a tilted simplex. For the Assignment Problem, GN acts as a variant of the Sinkhorn algorithm that naturally converges to a hard assignment while generalizing to arbitrary constraint graphs. We demonstrate GN's performance as a fast binarization engine for the state-of-the-art Bregman-Sinkhorn relaxed MWIS solver. On real-world benchmarks with up to 1M edges, GN identifies solutions within 1% of the best known results in seconds on a CPU. GN opens new avenues for deep learning architectures requiring differentiable, "hard" decisions under constraints, with applications in structured sparse attention, dynamic network pruning, and Mixture-of-Experts. Beyond core AI, the GN framework enables end-to-end learning of constrained optimization in computer vision, computational biology, and resource allocation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Graph Normalization gives a dynamical binarizer for MWIS with game theory ties, but convergence reaches only local optima.

read the letter

Graph Normalization introduces a dynamical binarizer for MWIS that converges via exact MM steps and game equivalence, but only to local optima of the quadratic objective rather than guaranteed global maximum weight solutions. The paper does a few things well. It defines an exact majorization-minimization update that keeps the trajectory inside the simplex and strictly increases the relaxed primal objective at each step. The connection to replicator dynamics of a nonlinear game, with the average fitness matching the objective and increasing per Fisher's theorem, gives a clean theoretical handle. The weighted Motzkin-Straus extension that links local minima to independent sets is a solid addition. Practically, the benchmarks show it post-processes the Bregman-Sinkhorn solver to solutions within 1% of best known on graphs with a million edges in just seconds on CPU, which is fast and usable. The view of it as a Sinkhorn variant for the assignment problem on general graphs is a good point. The soft spot is the optimality claim. The abstract says it converges to a binary indicator of a Maximum Independent Set, but the Motzkin-Straus part correctly identifies local minima, and the dynamics can get stuck in basins leading to suboptimal maximal sets when weights differ. The stress-test note is accurate on this; the construction does not provide escape to the global MWIS. I would want to verify the full derivations for the game equivalence and that the MM step works exactly on arbitrary undirected graphs without extra assumptions. This paper targets researchers in differentiable combinatorial optimization and structured prediction. Readers working on hard decisions in neural nets or on game models for graphs would find the ideas and the speed results worth their time. It deserves a serious referee because the novelty in the dynamics and the empirical performance are real, even with the need to tighten the global optimality language. I would send it for peer review.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces Graph Normalization (GN) as a dynamical system for differentiable approximation of the NP-hard Maximum Weight Independent Set (MWIS) problem. It claims to prove that GN always converges to a binary indicator of a Maximum Independent Set via an exact Majorization-Minimization step and replicator dynamics, establishes equivalence to a nonlinear evolutionary game obeying Fisher's Fundamental Theorem (with average fitness equaling the MWIS primal objective), provides a weighted extension of the Motzkin-Straus theorem linking MISes to local minima of a quadratic over a tilted simplex, and demonstrates its use as a fast binarization post-processor for Bregman-Sinkhorn relaxed solvers, achieving near-optimal solutions on real-world graphs with up to 1M edges.

Significance. If the convergence, game equivalence, and Motzkin-Straus extension hold with the stated properties, GN would offer a theoretically grounded, CPU-efficient mechanism for obtaining hard combinatorial decisions from continuous relaxations, with direct utility for differentiable constrained optimization in deep learning (e.g., sparse attention, network pruning). The explicit link to evolutionary game theory and the empirical scaling to large instances are notable strengths that could influence both combinatorial optimization and structured prediction pipelines.

major comments (2)

[Abstract] Abstract: The claim that GN 'always converges to a binary indicator of a Maximum Independent Set' is load-bearing for the central contribution but appears to describe convergence to local minima of the quadratic form (corresponding to maximal independent sets) rather than the global MWIS optimum. The replicator dynamics and exact MM step ensure strict increase of the objective and simplex invariance, yet on graphs admitting multiple maximal IS of unequal weight the basins of attraction can yield suboptimal solutions; the weighted Motzkin-Straus extension and game equivalence do not provide an escape mechanism to the global optimum.
[Convergence proof and majorization-minimization] Convergence proof and § on majorization-minimization: The assertion that the MM step is exact and the dynamical system is well-defined for arbitrary undirected graphs requires an explicit derivation showing that the update remains in the simplex, strictly increases the relaxed primal, and avoids fixed points that are not binary indicators; without this, the guarantee of convergence to a binary MIS cannot be verified and may contain gaps for non-regular or weighted graphs.

minor comments (2)

[Abstract] Abstract: The performance claim of 'solutions within 1% of the best known results in seconds on a CPU' for graphs with up to 1M edges would be strengthened by naming the specific benchmarks, reporting exact gap statistics, and cross-referencing the corresponding table or figure.
[Applications paragraph] Applications paragraph: The listed uses in structured sparse attention and Mixture-of-Experts are promising but would benefit from a short concrete example or citation showing how GN is embedded as a differentiable layer in an end-to-end training loop.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. The comments highlight important distinctions in convergence guarantees and the need for more explicit derivations, which we address below with planned revisions to clarify the results without overstating them.

read point-by-point responses

Referee: [Abstract] Abstract: The claim that GN 'always converges to a binary indicator of a Maximum Independent Set' is load-bearing for the central contribution but appears to describe convergence to local minima of the quadratic form (corresponding to maximal independent sets) rather than the global MWIS optimum. The replicator dynamics and exact MM step ensure strict increase of the objective and simplex invariance, yet on graphs admitting multiple maximal IS of unequal weight the basins of attraction can yield suboptimal solutions; the weighted Motzkin-Straus extension and game equivalence do not provide an escape mechanism to the global optimum.

Authors: We agree with the referee that the abstract's wording is imprecise and requires correction. GN converges to binary indicators of maximal independent sets, which are local minima of the quadratic form per the weighted Motzkin-Straus extension and the replicator dynamics equivalence (following Fisher's Fundamental Theorem). These are not guaranteed to be global MWIS optima, as basins of attraction can lead to suboptimal maximal sets on graphs with multiple maximal IS of differing weights. The dynamics provide no escape to the global optimum. We will revise the abstract, introduction, and conclusion to state convergence to a maximal independent set (a local MWIS solution) rather than claiming the global maximum. This clarification preserves the core contribution of a fast, theoretically grounded binarization method while accurately reflecting the local nature of the attractors. revision: yes
Referee: [Convergence proof and majorization-minimization] Convergence proof and § on majorization-minimization: The assertion that the MM step is exact and the dynamical system is well-defined for arbitrary undirected graphs requires an explicit derivation showing that the update remains in the simplex, strictly increases the relaxed primal, and avoids fixed points that are not binary indicators; without this, the guarantee of convergence to a binary MIS cannot be verified and may contain gaps for non-regular or weighted graphs.

Authors: The manuscript derives the GN update as an exact majorization-minimization step equivalent to replicator dynamics, which by construction preserves the simplex and monotonically increases the relaxed primal objective. Fixed points correspond to binary indicators of independent sets under the stated conditions. However, we acknowledge that the presentation would benefit from a more self-contained, step-by-step derivation. In the revision we will add an explicit lemma (with proof) verifying simplex invariance, strict objective increase away from fixed points, and that non-binary fixed points are not stable attractors, explicitly covering non-regular and weighted graphs. This will close any potential gaps in verifiability. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation is a self-contained proof of dynamical properties

full rationale

The paper defines GN via an exact majorization-minimization step on a relaxed MWIS objective, establishes equivalence to replicator dynamics on a nonlinear game, invokes Fisher's theorem to show strict increase of the average fitness (equal to the primal objective), and derives a weighted Motzkin-Straus bijection between MIS indicators and local minima over the tilted simplex. These steps are presented as consequences of the construction and standard external theorems rather than reductions to fitted parameters or self-referential definitions. No load-bearing self-citations, ansatz smuggling, or renaming of known results appear; the convergence claim is a direct property of the flow staying in the simplex and monotonically improving the objective, independent of the target MWIS optimum. The derivation does not collapse to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only access prevents identification of concrete free parameters, axioms, or invented entities; the central claims rest on unstated assumptions about graph structure and exactness of the majorization-minimization step.

pith-pipeline@v0.9.0 · 5621 in / 1178 out tokens · 74314 ms · 2026-05-08T16:32:57.783346+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

64 extracted references · 5 canonical work pages · 2 internal anchors

[1]

Ranking via Sinkhorn Propagation

Ryan Prescott Adams and Richard S Zemel. Ranking via sinkhorn propagation.arXiv preprint arXiv:1106.1925, 2011

work page Pith review arXiv 1925
[2]

Polynomial-time algorithms for multimarginal optimal transport problems with structure.Mathematical Programming, 199(1):1107–1178, 2023

Jason M Altschuler and Enric Boix-Adsera. Polynomial-time algorithms for multimarginal optimal transport problems with structure.Mathematical Programming, 199(1):1107–1178, 2023

2023
[3]

Hedy Attouch, J ´erˆome Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and reg- ularized gauss–seidel methods.Mathematical programming, 137(1):91–129, 2013

2013
[4]

Molecular docking with gaussian boson sampling.Science advances, 6(23):eaax1950, 2020

Leonardo Banchi, Mark Fingerhuth, Tomas Babej, Christopher Ing, and Juan Miguel Arrazola. Molecular docking with gaussian boson sampling.Science advances, 6(23):eaax1950, 2020

2020
[5]

On projection algorithms for solving convex feasibility problems.SIAM review, 38(3):367–426, 1996

Heinz H Bauschke and Jonathan M Borwein. On projection algorithms for solving convex feasibility problems.SIAM review, 38(3):367–426, 1996

1996
[6]

Neural Combinatorial Optimization with Reinforcement Learning

Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combi- natorial optimization with reinforcement learning.arXiv preprint arXiv:1611.09940, 2016

work page Pith review arXiv 2016
[7]

A branch-and-bound algorithm for the knapsack problem with conflict graph.INFORMS Journal on Computing, 29(3):457– 473, 2017

Andrea Bettinelli, Valentina Cacchiani, and Enrico Malaguti. A branch-and-bound algorithm for the knapsack problem with conflict graph.INFORMS Journal on Computing, 29(3):457– 473, 2017

2017
[8]

I. M. Bomze. Evolution towards the maximum clique.Journal of Global Optimization, 10(2):143–164, 1997. Crucial reference - First to apply replicator dynamics to the maximum clique problem (dual of MWIS). Shows that replicator dynamics converge to maximal cliques under certain conditions

1997
[9]

I. M. Bomze, M. Budinich, P. M. Pardalos, and M. Pelillo. The maximum clique problem. In Handbook of Combinatorial Optimization, pages 1–74. Springer, 2002. Survey of continuous- based methods for max clique, including replicator dynamics. Positions these methods within combinatorial optimization

2002
[10]

Bomze, Marcello Pelillo, and Vincenzo Stix

Immanuel M. Bomze, Marcello Pelillo, and Vincenzo Stix. Approximating the maximum weight clique using replicator dynamics.IEEE Transactions on Neural Networks, 11(6):1228– 1241, 2000

2000
[11]

Segmentation as maximum-weight independent set

William Brendel and Sinisa Todorovic. Segmentation as maximum-weight independent set. In Advances in neural information processing systems, pages 307–315, 2010

2010
[12]

On a relation between graph edit distance and maximum common subgraph

Horst Bunke. On a relation between graph edit distance and maximum common subgraph. Pattern recognition letters, 18(8):689–694, 1997

1997
[13]

Unified scaling laws for routed language models.International Conference on Machine Learning (ICML), 2022

Aidan Clark, Diego De Las Casas, Aurelia Guy, Arthur Mensch, Michela Paganini, Jordan Hoffmann, Bogdan Damoc, Blake Hechtman, Jack Trevor, Ivo Danihelka, et al. Unified scaling laws for routed language models.International Conference on Machine Learning (ICML), 2022

2022
[14]

Sinkhorn distances: Lightspeed computation of optimal transport

Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. InAdvances in Neural Information Processing Systems (NeurIPS), volume 26, 2013

2013
[15]

Cvetkovi´c, Michael Doob, and Horst Sachs.Spectra of Graphs: Theory and Appli- cations

Drago ˇs M. Cvetkovi´c, Michael Doob, and Horst Sachs.Spectra of Graphs: Theory and Appli- cations. Pure and Applied Mathematics. Academic Press, New York, 1980

1980
[16]

Combinatorial auctions: A survey.INFORMS Journal on computing, 15(3):284–309, 2003

Sven De Vries and Rakesh V V ohra. Combinatorial auctions: A survey.INFORMS Journal on computing, 15(3):284–309, 2003

2003
[17]

DeepSeek-V3 Technical Report

DeepSeek-AI. Deepseek-v3 technical report.arXiv preprint arXiv:2412.19437, 2024

work page internal anchor Pith review arXiv 2024
[18]

The pickup and delivery problem with time windows.European journal of operational research, 54(1):7–22, 1991

Yvan Dumas, Jacques Desrosiers, and Francois Soumis. The pickup and delivery problem with time windows.European journal of operational research, 54(1):7–22, 1991. 10

1991
[19]

Constraint composite graph-based lifted message passing for distributed constraint optimization problems

Ferdinando Fioretto, Hong Xu, Sven Koenig, and TK Satish Kumar. Constraint composite graph-based lifted message passing for distributed constraint optimization problems. InISAIM, 2018

2018
[20]

Evolutionary games in economics.Econometrica: Journal of the Econo- metric Society, 59(3):637–666, 1991

Daniel Friedman. Evolutionary games in economics.Econometrica: Journal of the Econo- metric Society, 59(3):637–666, 1991

1991
[21]

freeman San Francisco, 1979

Michael R Garey and David S Johnson.Computers and intractability, volume 174. freeman San Francisco, 1979

1979
[22]

PhD thesis, Paris Sciences et Lettres, 2019

Aude Genevay.Entropy-regularized optimal transport for machine learning. PhD thesis, Paris Sciences et Lettres, 2019

2019
[23]

Continu- ous characterizations of the maximum clique problem.Mathematics of Operations Research, 22(3):754–768, 1997

Luana E Gibbons, Donald W Hearn, Panos M Pardalos, and Motakuri V Ramana. Continu- ous characterizations of the maximum clique problem.Mathematics of Operations Research, 22(3):754–768, 1997

1997
[24]

A graduated assignment algorithm for graph matching

Steven Gold and Anand Rangarajan. A graduated assignment algorithm for graph matching. IEEE Transactions on pattern analysis and machine intelligence, 18(4):377–388, 1996

1996
[25]

Softmax to softassign: Neural network algorithms for combinatorial optimization.Journal of Artificial Neural Networks, 2(4):381–399, 1996

Steven Gold, Anand Rangarajan, et al. Softmax to softassign: Neural network algorithms for combinatorial optimization.Journal of Artificial Neural Networks, 2(4):381–399, 1996

1996
[26]

A Bregman-Sinkhorn algorithm for the maximum weight independent set problem.arXiv preprint arXiv:2408.02086, 2024

Stefan Haller, Borys Savchynskyy, Maximilian Schl ¨oter, and Bogdan Savchynskyy. A Bregman-Sinkhorn algorithm for the maximum weight independent set problem.arXiv preprint arXiv:2408.02086, 2024

work page arXiv 2024
[27]

Hofbauer and K

J. Hofbauer and K. Sigmund.Evolutionary Games and Population Dynamics. Cambridge University Press, 1998. Comprehensive treatment of replicator dynamics, potential games, and stability analysis. Establishes the connection between replicator dynamics and gradient flows on the simplex

1998
[28]

A tutorial on mm algorithms.The American Statistician, 58(1):30–37, 2004

David R Hunter and Kenneth Lange. A tutorial on mm algorithms.The American Statistician, 58(1):30–37, 2004

2004
[29]

Erd ˝os goes neural: an unsupervised learning frame- work for combinatorial optimization on graphs

Nikolaos Karalias and Andreas Loukas. Erd ˝os goes neural: an unsupervised learning frame- work for combinatorial optimization on graphs. InAdvances in Neural Information Processing Systems (NeurIPS), volume 33, pages 6659–6670, 2020

2020
[30]

Reducibility among combinatorial problems

Richard M Karp. Reducibility among combinatorial problems. InComplexity of Computer Computations, pages 85–103. Springer, 1972

1972
[31]

The maximum weight trace problem in multiple sequence alignment

John Kececioglu. The maximum weight trace problem in multiple sequence alignment. In Annual Symposium on Combinatorial Pattern Matching, pages 106–119. Springer, 1993

1993
[32]

Learning combinatorial optimization algorithms over graphs.Advances in neural information processing systems, 30, 2017

Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs.Advances in neural information processing systems, 30, 2017

2017
[33]

The invisible hand algorithm: Solving the assignment problem with statistical physics.Neural networks, 7(3):477–490, 1994

Jeffrey J Kosowsky and Alan L Yuille. The invisible hand algorithm: Solving the assignment problem with statistical physics.Neural networks, 7(3):477–490, 1994

1994
[34]

The hungarian method for the assignment problem.Naval research logistics quarterly, 2(1-2):83–97, 1955

Harold W Kuhn. The hungarian method for the assignment problem.Naval research logistics quarterly, 2(1-2):83–97, 1955

1955
[35]

metavar: Introducing metavariant species models for reference-free metagenomic- based population genomics.PLoS One, 15(12):e0244637, 2020

Romuald Laso-Jadart, Christophe Ambroise, Pierre Peterlongo, and Mohammed-Amin Madoui. metavar: Introducing metavariant species models for reference-free metagenomic- based population genomics.PLoS One, 15(12):e0244637, 2020

2020
[36]

Algorithms for non-negative matrix factorization.Ad- vances in neural information processing systems, 13, 2000

Daniel Lee and H Sebastian Seung. Algorithms for non-negative matrix factorization.Ad- vances in neural information processing systems, 13, 2000

2000
[37]

Practical graph isomorphism

Brendan D McKay et al. Practical graph isomorphism. 1981. 11

1981
[38]

Learning latent permu- tations with gumbel-sinkhorn networks

Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permu- tations with gumbel-sinkhorn networks. InInternational Conference on Learning Representa- tions (ICLR), 2018

2018
[39]

Stanley Metcalfe

J. Stanley Metcalfe. Competition, fisher’s principle and economic evolution.Evolutionary Economics, 4(1):1–31, 1994

1994
[40]

Maxima for graphs and a new proof of a theorem of tur´an.Canadian Journal of Mathematics, 17:533–540, 1965

Theodore S Motzkin and Ernst G Straus. Maxima for graphs and a new proof of a theorem of tur´an.Canadian Journal of Mathematics, 17:533–540, 1965

1965
[41]

The maximum weight independent set prob- lem for data association in multiple hypothesis tracking

Dimitri J Papageorgiou and Michael R Salpukas. The maximum weight independent set prob- lem for data association in multiple hypothesis tracking. InOptimization and Cooperative Control Strategies, pages 235–255. Springer, 2009

2009
[42]

Differentiation of blackbox combinatorial solvers

Marin Vlastelica Pogan ˇci´c, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. InInternational conference on learning representations, 2019

2019
[43]

Convergence properties of the softassign quadratic assignment algorithm.Neural Computation, 11(6):1455–1474, 1999

Anand Rangarajan, Alan Yuille, and Steven Gold. Convergence properties of the softassign quadratic assignment algorithm.Neural Computation, 11(6):1455–1474, 1999

1999
[44]

A convergence proof for the softassign quadratic assignment algorithm

Anand Rangarajan, Alan L Yuille, Steven Gold, and Eric Mjolsness. A convergence proof for the softassign quadratic assignment algorithm. InAdvances in neural information processing systems, pages 620–626, 1997

1997
[45]

Tessetrack: End-to-end learnable multi-person articulated 3d pose tracking

N Dinesh Reddy, Laurent Guigues, Leonid Pishchulin, Jayan Eledath, and Srinivasa G Narasimhan. Tessetrack: End-to-end learnable multi-person articulated 3d pose tracking. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 15190–15200, 2021

2021
[46]

Message passing for maximum weight independent set.IEEE Transactions on Information Theory, 55(11):4822–4834, 2009

Sujay Sanghavi, Devavrat Shah, and Alan S Willsky. Message passing for maximum weight independent set.IEEE Transactions on Information Theory, 55(11):4822–4834, 2009

2009
[47]

Super- glue: Learning feature matching with graph neural networks

Paul-Edouard Sarlin, Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich. Super- glue: Learning feature matching with graph neural networks. InProceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 4938–4947, 2020

2020
[48]

Coupled replicator equations for the dynamics of learn- ing in multiagent systems.Physical Review E, 67(1):015206, 2003

Yuzuru Sato and James P Crutchfield. Coupled replicator equations for the dynamics of learn- ing in multiagent systems.Physical Review E, 67(1):015206, 2003

2003
[49]

Concerning nonnegative matrices and doubly stochastic matrices.Pacific Journal of Mathematics, 21(2):343–348, 1967

Richard Sinkhorn and Paul Knopp. Concerning nonnegative matrices and doubly stochastic matrices.Pacific Journal of Mathematics, 21(2):343–348, 1967

1967
[50]

Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks

Leandros Tassiulas and Anthony Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. In29th IEEE Conference on Decision and Control, pages 2130–2132. IEEE, 1990

1990
[51]

P. D. Taylor and L. B. Jonker. Evolutionary stable strategies and game dynamics.Mathematical Biosciences, 40(1-2):145–156, 1978. Introduced the continuous replicator dynamics equation. Foundation for all later work

1978
[52]

An optimisation algorithm for maximum independent set with applications in map labelling

Bram Verweij and Karen Aardal. An optimisation algorithm for maximum independent set with applications in map labelling. InEuropean Symposium on Algorithms, pages 426–437. Springer, 1999

1999
[53]

mHC: Manifold-Constrained Hyper-Connections

Zhenda Xie, Yixuan Wei, Huanqi Cao, Chenggang Zhao, Chengqi Deng, Jiashi Li, Damai Dai, Huazuo Gao, Jiang Chang, Kuai Yu, et al. mhc: Manifold-constrained hyper-connections. arXiv preprint arXiv:2512.24880, 2025

work page internal anchor Pith review arXiv 2025
[54]

Fast action proposals for human action detection and search

Gang Yu and Junsong Yuan. Fast action proposals for human action detection and search. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1302– 1311, 2015

2015
[55]

Stereo and eye movement.Biological Cybernetics, 63:1–12, 1990

Alan L Yuille, Davi Geiger, and H Bozic. Stereo and eye movement.Biological Cybernetics, 63:1–12, 1990. 12

1990
[56]

Deep learning of graph matching

Andrei Zanfir and Cristian Sminchisescu. Deep learning of graph matching. InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2684–2693, 2018

2018
[57]

Indoor scene reconstruction from a single view as maximum weight independent set

Wei Zhuo, Mathieu Salzmann, Xuming He, and Miaomiao Li. Indoor scene reconstruction from a single view as maximum weight independent set. InProceedings of the IEEE Confer- ence on Computer Vision and Pattern Recognition (CVPR), pages 5000–5009, 2016. A Fixed Points of the Unregularized GN Map A fixed pointxof the GN map defined by Equation 1 is a normaliz...

2016
[58]

A single point (discrete):S(A) ={x}whendet(B)̸= 0andx=B −11>0. In that case, becauseB −1 = 1 det(B) adj(B)whereadj(B)is the adjoint ofBandBis binary, det(B)andadj(B)both have integer values, hence all values ofB −11are fractions proportional to 1/|det(B)|. Figure 1 provides some examples. 13 Figure 1: Examples of Discrete GN Atoms
[59]

In that caseS(A) = (x 0 + ker(B))∩(0,1) n is the intersection of an affine space with the open unit cube

A continuous manifold:whendet(B) = 0and∃x 0 >0 :Bx 0 = 1. In that caseS(A) = (x 0 + ker(B))∩(0,1) n is the intersection of an affine space with the open unit cube. The manifold of fixed points is connected and has dimensiondim(ker(B)). Figure 2 provides some examples. The dimension of the manifold is indicated byDim. The values on the nodes contain Dimvar...
[60]

Most GN atomic spectra areempty

Empty:F(A) =∅otherwise. Most GN atomic spectra areempty. We say that a graph with a non empty spectrum isAtomic. Regular graphsare always atomic: indeed ifAisd-regular then the uniform vectorx 0 = 1 d+1 1 is always a solution ofBx 0 =1 2. Among regular graphs, some have a discrete spectrum (e.g. the 4-cycleC 4), i.e., are only normalized for uniform weigh...
[61]

Equality at the Tangent Point: By substitution,G(y k, yk) = 1 2(yk)T By k −v T yk = ˜Eγ,v(yk)
[62]

The next iteratey k+1 is obtained by minimizing the majorant

Global Dominance: BecauseBis asymmetricnon-negative matrix, the diagonal majoriza- tion lemma [36] ensuresy T By≤ P i (By k)i yk i y2 i thus ˜Eγ,v(y)≤G(y, y k)for ally≥0. The next iteratey k+1 is obtained by minimizing the majorant. SinceGis a separable quadratic function with a diagonal Hessian∇ 2 yy G=diag (By k)i yk i , it is strictly convex providedy ...
[63]

Forγ <1, the energy is strictly convex with a unique minimum atx= 1/2

Unweighted case (w0 = 1). Forγ <1, the energy is strictly convex with a unique minimum atx= 1/2. Iterated GN converges to the fractional point(1/2,1/2)from any initialization 3. Forγ= 1, the energy is flat and anyx∈[0,1]a stable minimum. Any positive initialization is projected to the simplex in1iteration of graph normalization and stable after that. Forγ...
[64]

As show by the Tilted Simplex Motzkin-Straus Theorem 6,w 0 ̸= 1corresponds to tilting the sim- plex

Weighted case (w0 >1). As show by the Tilted Simplex Motzkin-Straus Theorem 6,w 0 ̸= 1corresponds to tilting the sim- plex. The energy value on the MIS atx= 0isE γ,w0(0) = 1/w0. Asγincreases, the system goes through two phase transitions. 3Note thatγ= 0is a special case which corresponds to completely removing the edges from the graph, leaving the WRGN up...