Experimental performance of graph neural networks on random instances of max-cut

Afonso S. Bandeira; Soledad Villar; Weichi Yao

REVIEW 4 major objections 5 minor 31 references

Experimental performance of graph neural networks on random instances of max-cut

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Unsupervised graph neural networks match the Goemans-Williamson SDP on random max-cut instances.

desk verdict A small, honest benchmark applying an existing LGNN architecture to unsupervised max-cut; the math is right and the code is public, but the 'comparable to SDP' claim is not actually established without error bars and a clear aggregation rule. read the letter →

arxiv 1908.05767 v1 pith:TZ5IEDND submitted 2019-08-15 math.OC cs.LG

Weichi Yao , Afonso S. Bandeira , Soledad Villar This is my paper · ORCID

classification math.OCcs.LG MSC 05C8068T0790C2290C2768R10

keywords max-cutrandomregulargraphsgraphneuralnetworkssemidefiniteprogrammingextremaloptimizationunsupervisedlearningpolicygradientasymptoticoptimality

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This note asks whether graph neural networks can be taught, without labels, to find good max-cut solutions on random regular graphs. It reports that they can: an unsupervised line-graph neural network trained to maximize the cut directly produces cuts comparable to those from the standard semidefinite-programming relaxation of max-cut, while the physics-inspired extremal optimization heuristic consistently finds better cuts than both. Because random regular graphs have no planted ground truth, the paper scores every candidate solution against the known asymptotic value of the optimal max-cut, giving the comparison an absolute yardstick. A reader should care because the result suggests unsupervised learning can serve as a practical heuristic for NP-hard combinatorial optimization on random inputs, even though it does not beat a well-tuned local search.

What carries the argument

The load-bearing object is the Line Graph Neural Network (LGNN): a neural network that propagates signals on the original graph and on its line graph using the degree, adjacency, power-graph, and non-backtracking operators, then merges node and edge features through indicator matrices. For max-cut it is trained without labels by maximizing a differentiable proxy for the cut value: either the relaxed quadratic form $(2p-1)^T L_G (2p-1)/4$, where $p$ is the probability that a vertex is assigned to side 1, or a policy-gradient estimator that samples assignments and updates through the score function $\nabla \log \pi$. The two baselines are the semidefinite relaxation with random rounding and extremal optimization, which repeatedly flips the variable with the worst normalized fitness under a power-law selection rule. The evaluation yardstick is the asymptotic max-cut formula that supplies $P^* \approx 0.7632$, used to normalize every reported cut value.

What would settle it

Solve small random d-regular graphs exactly (for example all $n \le 30$ with $d = 3$ and $10$) and compare the three methods' $P$ values against the true maximum cut; if the methods' ranking by $P$ disagrees with their ranking by true cut size, the asymptotic yardstick is not a valid finite-$n$ comparator.

Watch

Extended reading notes

Core claim

The paper's central claim is that, for max-cut on random d-regular graphs with $n = 50$ to $500$ vertices and degrees $d = 3$ to $20$, an unsupervised graph neural network trained with either a continuous relaxation or a policy-gradient estimator of the cut objective attains performance comparable to the semidefinite-programming relaxation, and that extremal optimization outperforms both. Each cut is converted to the standardized score $P = (z/n - d/4)/\sqrt{d/4}$, whose known asymptotic optimum is $P^* \approx 0.7632$; across all reported tables, $P$ increases as graphs become sparser and larger, so all three methods approach the asymptotic optimum in those regimes. The paper frames this as experimental evidence that unsupervised machine learning can be successfully adapted to hard optimization problems on random inputs, with the GNN result being the least anticipated of the three.

Load-bearing premise

The comparison assumes the known asymptotic formula for the optimal max-cut is an accurate yardstick at the finite sizes tested, so that a higher $P$ always indicates a better cut relative to the true optimum.

Editorial extensions

If this is right

If the finding holds, unsupervised graph neural networks are a viable heuristic for max-cut on random regular graphs at moderate sizes, requiring no labels and no planted signal.
Extremal optimization, not the neural method, is the strongest of the three, so further theoretical study of that heuristic is the more direct route to provable guarantees.
The monotone approach toward $P^*$ as graphs grow sparser and larger indicates that finite-size effects, rather than algorithmic failure, account for most of the observed gap to the asymptotic optimum.
Because the GNN and the SDP land in the same performance band, the two approaches are comparable alternatives in this regime rather than one dominating the other.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper trains a fresh network for each $(n,d)$ pair; an untested consequence is whether one network transfers across sizes or degrees, which would tell whether the GNN has learned a general algorithm or fit each regime separately.
If finite-size corrections to the asymptotic max-cut formula are method-dependent, rankings by $P$ could differ from rankings by true cut quality; a small-$n$ exact benchmark would settle this.
The two training variants perform inconsistently relative to each other across tables, suggesting that a variance-reduced policy-gradient estimator or a hybrid loss could close part of the gap to extremal optimization.
Because similarly scored cuts can be structurally different, solution diversity, not just cut value, may matter for applications that need multiple candidate partitions.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: this is a legitimate experimental note, not a breakthrough. What's new is that they take Chen, Li, Bruna's line graph network and use it for unsupervised max-cut with two losses (relaxation and policy gradient), then compare against SDP and EO on random regular graphs. The loss derivations (Eqs. 5-8) check out; the policy-gradient step is the standard REINFORCE trick, and the relaxation is a clean continuous substitute. They evaluate against an external asymptotic constant and against fixed baseline algorithms, so there is no circularity. Code is public.

Credit where due: the authors are careful to note that SDP's fractional solution isn't the right asymptotic benchmark, and they report all three methods across a reasonable sweep of n and d. The observation that EO wins consistently in these ranges is consistent with earlier physics literature and useful as a sanity check for anyone working on learned heuristics.

The soft spots are real but concentrated. The abstract says GNNs are 'comparable' to SDP, but the point estimates tell a more qualified story: at n=500, d=20 the better GNN trails SDP by about 0.049 P, and at d=15 by 0.071 P; at d<=5 it slightly beats SDP; the policy-gradient variant is worse. No error bars, no number of independent GNN training runs, no confidence intervals. The tables also do not say whether the 1000 test graphs are disjoint from the 5000 training graphs. So the paper does not currently establish the headline claim, and 'GNNs' is ambiguous because the two variants differ by as much as 0.07 P. That is a load-bearing omission, and it should be fixed with standard errors and per-variant reporting.

The reader's worry about the Dembo et al. yardstick at finite n is less concerning than it looks. Since P is a monotone transformation of cut size at fixed (n,d), method-by-method rankings are unaffected by whether P* is exact for finite n. The 'closer to asymptotic optimum' language does depend on P*, but the main comparisons stand or fall on the missing UQ, not on finite-size corrections.

Who's this for? Anyone working on GNNs for combinatorial optimization will want it on the radar. It's a small result, and I wouldn't cite it as evidence that learned heuristics are competitive with SDP. A serious referee should engage with it, because the experiment is reproducible and the question is worth asking; but it needs a revised version with uncertainty quantification and a more precise claim.

Referee Report

4 major / 5 minor

Summary. The paper experimentally compares three methods for max-cut on random d-regular graphs: a line-graph neural network (GNN) trained with two unsupervised losses (a relaxation loss and a policy-gradient loss), the Goemans–Williamson semidefinite programming (SDP) relaxation with random rounding, and extremal optimization (EO). Performance is measured through the normalized statistic P defined in Eq. (9), which compares the cut value to the Dembo et al. asymptotic constant P*. The authors report that GNNs attain performance comparable to the SDP, that EO consistently outperforms both, and that all methods produce cuts closer to the asymptotic optimum when graphs are sparser and larger. The paper includes a derivation of the two GNN losses and points to publicly available code.

Significance. If the headline claims were backed by adequate statistical evidence, this would be a useful experimental contribution on the applicability of unsupervised GNNs to NP-hard optimization on random instances, complementing existing supervised GNN results on the stochastic block model. The derivation of the two unsupervised losses is correct, and the use of a known asymptotic benchmark to evaluate heuristics is an appropriate strategy. The authors also make their code publicly available, which aids reproducibility. However, the reported tables contain single point estimates without error bars, confidence intervals, or variance over training runs, so the comparative claims are difficult to assess; the evidence as it stands does not establish the abstract's strongest statements.

major comments (4)

[§3.1, Tables 1–3; abstract] The central claim that GNNs attain 'comparable' performance to SDP is not supported by the reported point estimates alone. Tables 1–3 give a single P value per method per (n,d) with no standard deviations, confidence intervals, or number of independent GNN training runs, and the two GNN variants (relaxation and policy gradient) differ by up to about 0.07 P (e.g., at n=500, d=5 in Table 1, relaxation gives 0.7014 while policy gradient gives 0.6682). The SDP-minus-GNN gap changes sign with d (e.g., at n=500, d=20 the policy-gradient GNN trails SDP by about 0.048, while at d=5 the relaxation GNN leads SDP by about 0.012), so without a pre-specified 'comparable' threshold and an explicit aggregation rule over the two variants, the abstract's headline is not established.
[§3.1, Tables 2 and 3] The text states that 'in both cases, the computed P for all three methods increase as the node size n increases,' but Tables 2 and 3 contradict this. For d=3, SDP P drops from 0.7091 at n=200 to 0.7015 at n=500, and the policy-gradient GNN drops from 0.7010 at n=200 to 0.6928 at n=500. For d=10, SDP P drops from 0.6919 at n=200 to 0.6820 at n=500, and the policy-gradient GNN drops from 0.6598 at n=200 to 0.5989 at n=500. The claim in the abstract that all methods improve with larger n is therefore contradicted by the reported data.
[§4] The conclusion that 'extremal optimization is the most computationally efficient' is unsupported by any runtime data in the paper. The only complexity statement is a citation of Boettcher and Percus's O(N) claim, but the experimental section fixes EO's iteration budget at tmax = 10^4 n and does not report wall-clock times, iteration counts to convergence, or comparable measurements for SDP and the GNN. A claim about computational efficiency requires at least a runtime comparison.
[§3] The manuscript does not state whether the 5000 training graphs are disjoint from the 1000 evaluation graphs, nor the number of GNN training runs, epochs, or random initializations. Without this information, the reader cannot assess whether the reported GNN numbers are representative or whether they are selected from multiple runs. This is particularly important because the two GNN variants are stochastic and the evaluation set is fixed.

minor comments (5)

[Abstract and Introduction] Several typos appear throughout, such as 't echniques' in the abstract, 'they where first proposed' in the Introduction, and 'of and edges connecting' in §2.2; a full proofreading pass is recommended.
[Eq. (9) and surrounding text] The use of the asymptotic constant P* from Dembo et al. as a finite-n yardstick is reasonable for ranking methods at fixed (n,d) because P is a monotone transformation of cut size, but the statement that a value P closer to P* implies the cut is 'among the best possible' should be qualified, since finite-size corrections may differ across degrees.
[§2.2] The definitions of 'good' and 'bad' edges are counterintuitive: the text first calls edges within the same set 'good' in the context of maximizing cut, then uses them to derive a loss to be minimized; please clarify the sign convention or use neutral terminology.
[§3, SDP fractional solution] The claim that the SDP's fractional solution has P = 1 in the limit and 'is not an improvement over a simple spectral method' is stated without a derivation or explicit citation; please add a reference or a one-line argument to support this observation.
[§2.3.2, Eq. (8)] The equality in Eq. (8) is correct only as an unbiased estimator of the gradient of the expected return; the sampled objective is not the same as the expected return, so the presentation should emphasize that the empirical gradient is a stochastic estimate, not an exact equality.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the evaluation is benchmarked against the external Dembo et al. asymptotic value and fixed baseline algorithms, with the GNN loss being the cut objective itself.

full rationale

The paper's derivation chain is self-contained against external benchmarks. The quantity being evaluated, P in Eq. (9), is a monotone transformation of the cut size z at fixed (n,d), anchored to the external Dembo et al. asymptotic theorem; it is not a fitted or learned quantity. The GNN is trained by maximizing the cut objective itself (Eq. (5)), so reporting cut-based P values is not a renamed prediction of an input parameter. SDP and EO are fixed external/standard baselines with specified parameter choices, and no fitted parameter from the GNN is used to define the benchmark. The self-citations (Bandeira et al. 2018 and Nowak et al. 2018) are contextual references and are not load-bearing for the numerical claims. Concerns about missing error bars, seed variance, and the breadth of the word 'comparable' are empirical-evidence issues, not circularity.

Assumptions & free parameters 5 free parameters · 3 assumptions · 0 invented entities

Central claim rests on the Dembo et al. asymptotic max-cut formula used to define the P metric, on the assumption that finite-size P values compare meaningfully across methods, and on the hand-chosen hyperparameters of EO and GNN. No invented entities are introduced.

free parameters (5)

EO rank distribution exponent tau = 1.4
Fixed from Boettcher and Percus (2001) numerical findings; not re-fit here, but EO performance and the claim that EO wins depend on this choice.
EO iteration budget = 10^4 * n
Set following Boettcher and Percus (2001) to be sufficiently large; it affects how close EO gets to a local optimum.
EO restarts = 2 (best run)
The paper chooses the best of two EO runs, which biases reported EO values upward relative to a single run.
SDP random rounding count = 500
The best cut over 500 random roundings is reported; more roundings could improve SDP's rounded value.
GNN hyperparameters = J=3, K=30, b_k=10, 5000 training graphs
Copied from Chen et al. (2017) rather than tuned for max-cut; the relative ranking of GNNs could shift with different settings.

assumptions (3)

standard math The Dembo et al. asymptotic formula MaxCut(GReg(n,d)) = n(d/4 + P* sqrt(d/4)) + o(n), P* about 0.7632, holds and is used to define the P metric.
Invoked in Section 3 before Eq. (9) as the benchmark for evaluating cut quality.
domain assumption At the tested sizes (n = 50 to 500, d = 3 to 20), a higher P in Eq. (9) accurately indicates a better max-cut solution.
The paper does not quantify finite-size corrections or verify that P ranks methods identically to true max-cut values.
domain assumption The 1000 test graphs are drawn from the same uniform random d-regular distribution as the 5000 training graphs and the asymptotic theory.
Training and evaluation distributions match, but the paper does not test transfer to other graph families.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Experimental performance of graph neural networks on random instances of max-cut." pith.science (2026). https://pith.science/paper/TZ5IEDND

@misc{pith2026190805767,
  author       = {Pith},
  title        = {Pith review of: Experimental performance of graph neural networks on random instances of max-cut},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TZ5IEDND}},
  note         = {Machine review of arXiv:1908.05767}
}

read the original abstract

This note explores the applicability of unsupervised machine learning techniques towards hard optimization problems on random inputs. In particular we consider Graph Neural Networks (GNNs) -- a class of neural networks designed to learn functions on graphs -- and we apply them to the max-cut problem on random regular graphs. We focus on the max-cut problem on random regular graphs because it is a fundamental problem that has been widely studied. In particular, even though there is no known explicit solution to compare the output of our algorithm to, we can leverage the known asymptotics of the optimal max-cut value in order to evaluate the performance of the GNNs. In order to put the performance of the GNNs in context, we compare it with the classical semidefinite relaxation approach by Goemans and Williamson~(SDP), and with extremal optimization, which is a local optimization heuristic from the statistical physics literature. The numerical results we obtain indicate that, surprisingly, Graph Neural Networks attain comparable performance to the Goemans and Williamson SDP. We also observe that extremal optimization consistently outperforms the other two methods. Furthermore, the performances of the three methods present similar patterns, that is, for sparser, and for larger graphs, the size of the found cuts are closer to the asymptotic optimal max-cut value.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 25 canonical work pages

[1]

M. R. Garey and D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness . W. H. Freeman & Co., New York, NY, USA, 1990

work page 1990
[2]

M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programing. Journal of the ACM (JACM), 42 0 (6): 0 1115--1145, 1995

work page 1995
[3]

Community detection and stochastic block models: recent developments

Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18 0 (1): 0 6446--6531, 2017

2017
[4]

Dembo, A

A. Dembo, A. Montanari, and S. Sen. Extremal cuts of sparse random graphs. The Annals of Probability, 45 0 (2): 0 1190--1217, 2017

work page 2017
[5]

A conjecture on the maximum cut and bisection width in random regular graphs

Lenka Zdeborov \'a and Stefan Boettcher. A conjecture on the maximum cut and bisection width in random regular graphs. Journal of Statistical Mechanics: Theory and Experiment, 2010 0 (02): 0 P02020, 2010

work page 2010
[6]

Notes on computational-to-statistical gaps: predictions using statistical physics

Afonso S Bandeira, Amelia Perry, and Alexander S Wein. Notes on computational-to-statistical gaps: predictions using statistical physics. arXiv preprint arXiv:1803.11132, 2018

arXiv 2018
[7]

Gori , G

M. Gori , G. Monfardini , and F. Scarselli . A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pages 729--734, 2005

work page 2005
[8]

M. M. Bronstein , J. Bruna , Y. LeCun , A. Szlam , and P. Vandergheynst . Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34 0 (4): 0 18--42, 2017

work page 2017

Show all 31 references

[9]

Z. Chen, X. Li, and J. Bruna. Supervised community detection with line graph neural networks. arXiv e-prints, art. arXiv:1705.08415, 2017

2017 arXiv
[10]

Boettcher and A

S. Boettcher and A. G. Percus. Extremal optimization: M ethods derived from co-evolution. Proceedings of the 1999 Genetic and Evolutionary Computation Conference (GECCO '99), pages 825--832, 1999

1999
[11]

Boettcher and A

S. Boettcher and A. G. Percus. Extremal optimization for graph partitioning. Physical Review E, 64, 026114, 2001

2001
[12]

Optimization with extremal dynamics for the traveling salesman problem

Yu-Wang Chen, Yong-Zai Lu, and Peng Chen. Optimization with extremal dynamics for the traveling salesman problem. Physica A: Statistical Mechanics and its Applications, 385 0 (1): 0 115--123, 2007

2007
[13]

Optimization of the S herrington- K irkpatrick hamiltonian

Andrea Montanari. Optimization of the S herrington- K irkpatrick hamiltonian. arXiv preprint arXiv:1812.10897, 2018

2018 arXiv
[14]

Boettcher and A

S. Boettcher and A. G. Percus. Nature’s way of optimizing. Artificial Intelligence, 119: 0 275--286, 2000

2000
[15]

Bak and K

P. Bak and K. Sneppen. Punctuated equilibrium and criticality in a simple model of evolution. Physical Review Letters, 71 0 (24), 1993

1993
[16]

Spectral redemption in clustering sparse networks

Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborov \'a , and Pan Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, 110 0 (52): 0 20935--20940, 2013

2013
[17]

Spectral clustering of graphs with the bethe hessian

Alaa Saade, Florent Krzakala, and Lenka Zdeborov \'a . Spectral clustering of graphs with the bethe hessian. In Advances in Neural Information Processing Systems, pages 406--414, 2014

2014
[18]

Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs

Charles Bordenave, Marc Lelarge, and Laurent Massouli \'e . Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1347--1357. IEEE, 2015

2015
[19]

Revised note on learning quadratic assignment with graph neural networks

Alex Nowak, Soledad Villar, Afonso S Bandeira, and Joan Bruna. Revised note on learning quadratic assignment with graph neural networks. In 2018 IEEE Data Science Workshop (DSW), pages 1--5. IEEE, 2018

2018
[20]

Scarselli, M

F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Trans. Neural Networks, 20 0 (1): 0 61--80, 2009

2009
[21]

Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel. Gated graph sequence neural networks. arXiv preprint arXiv:1511.05493, 2015

2015 arXiv
[22]

Duvenaud, D

D. Duvenaud, D. Maclaurin, J. Aguilera-Iparraguirre, A. Aspuru-Guzik R. G\' o mez-Bombarelli, T. Hirzel, and R. P. Adams. Convolutional networks on graphs for learning molecular fingerprints. Neural Information Processing Systems, 2015

2015
[23]

Sukhbaatar, A

S. Sukhbaatar, A. Szlam, and R. Fergus. Learning multiagent communication with backpropagation. Advances in Neural Information Processing Systems, pages 2244--2252, 2016

2016
[24]

Degris , P

T. Degris , P. M. Pilarski , and R. S. Sutton . Model-free reinforcement learning with continuous action in practice. In 2012 American Control Conference (ACC), pages 2177--2182, 2012

2012
[25]

Watkins and P

C. Watkins and P. Dayan. Q-learning. Machine Learning, 8 0 (3): 0 279--292, 1992

1992
[26]

R. S. Sutton, D. A. McAllester, S. P. Singh, and Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. In Neural Information Processing Systems 12, pages 1057--1063, 1999

1999
[27]

The peculiar phase structure of random graph bisection

Allon G Percus, Gabriel Istrate, Bruno Gon c alves, Robert Z Sumi, and Stefan Boettcher. The peculiar phase structure of random graph bisection. Journal of Mathematical Physics, 49 0 (12): 0 125219, 2008

2008
[28]

The parisi formula

Michel Talagrand. The parisi formula. Annals of mathematics, pages 221--263, 2006

2006
[29]

Semidefinite programs on sparse random graphs and their application to community detection

Andrea Montanari and Subhabrata Sen. Semidefinite programs on sparse random graphs and their application to community detection. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 814--827. ACM, 2016

2016
[30]

SDPNAL +: a majorized semismooth newton-cg augmented lagrangian method for semidefinite programming with nonnegative constraints

Liuqin Yang, Defeng Sun, and Kim-Chuan Toh. SDPNAL +: a majorized semismooth newton-cg augmented lagrangian method for semidefinite programming with nonnegative constraints. Mathematical Programming Computation, 7 0 (3): 0 331--366, 2015

2015
[31]

Implementation of GNN , SDP and EO for max-cut

Weichi Yao. Implementation of GNN , SDP and EO for max-cut. https://github.com/ElainaYao/maxCut, 2019

2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

M. R. Garey and D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness . W. H. Freeman & Co., New York, NY, USA, 1990

work page 1990

[2] [2]

M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programing. Journal of the ACM (JACM), 42 0 (6): 0 1115--1145, 1995

work page 1995

[3] [3]

Community detection and stochastic block models: recent developments

Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18 0 (1): 0 6446--6531, 2017

2017

[4] [4]

Dembo, A

A. Dembo, A. Montanari, and S. Sen. Extremal cuts of sparse random graphs. The Annals of Probability, 45 0 (2): 0 1190--1217, 2017

work page 2017

[5] [5]

A conjecture on the maximum cut and bisection width in random regular graphs

Lenka Zdeborov \'a and Stefan Boettcher. A conjecture on the maximum cut and bisection width in random regular graphs. Journal of Statistical Mechanics: Theory and Experiment, 2010 0 (02): 0 P02020, 2010

work page 2010

[6] [6]

Notes on computational-to-statistical gaps: predictions using statistical physics

Afonso S Bandeira, Amelia Perry, and Alexander S Wein. Notes on computational-to-statistical gaps: predictions using statistical physics. arXiv preprint arXiv:1803.11132, 2018

arXiv 2018

[7] [7]

Gori , G

M. Gori , G. Monfardini , and F. Scarselli . A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pages 729--734, 2005

work page 2005

[8] [8]

M. M. Bronstein , J. Bruna , Y. LeCun , A. Szlam , and P. Vandergheynst . Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34 0 (4): 0 18--42, 2017

work page 2017