Pith. sign in

REVIEW 4 major objections 5 minor 60 references

ReFill: Reinforcement Learning for Fill-In Minimization

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

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

Pith's one-line read A GNN policy trained with masked PPO yields elimination orders with less fill-in than the minimum-degree and minimum-fill-in heuristics, by up to 18.6% on single graphs and 2.21% on average on unseen graphs.

desk verdict A plausible RL-for-fill-in idea with an honest limitations section, but the headline gains rest on best-of-k sampling and per-instance training, so the outperformance claim is not yet established. read the letter →

arxiv 2501.16130 v2 pith:234RKAN6 submitted 2025-01-27 cs.LG

Elfarouk Harb , Ho Shan Lam This is my paper · ORCID
classification cs.LG
keywords fill-inminimizationreinforcementlearninggraphneuralnetworksPPOeliminationorderingsparselinearsystemsactionmaskingGaussian
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

ReFill casts fill-in minimization during Gaussian elimination as a reinforcement-learning game: at each step the agent eliminates one remaining vertex of the graph that encodes the sparse matrix's nonzero pattern, and receives a penalty equal to the number of new nonzero entries created. The paper claims that a two-layer graph network trained with PPO learns to pick better vertices than the two classical greedy heuristics, Minimum Degree (MDH) and Minimum Fill-In (MFillH), provided that the agent's choices are restricted to vertices these heuristics would consider. On grid graphs and real PACE 2017 instances the learned orders reduce fill-in by up to 18.6% relative to MDH and 9.8% relative to MFillH, and a single trained policy generalizes to 200 unseen $G(50, 0.2)$ random graphs with average improvements of 2.21% and 1.05%. This matters because fill-in drives the memory and runtime of sparse direct solvers, and the two heuristics have been near-universal defaults for decades; for applications that solve many matrices with the same or similar sparsity patterns, even a few percent less fill-in compounds into real savings.

What carries the argument

The machinery is a masked Markov decision process paired with a graph-convolutional policy optimized by PPO. The state is the current elimination graph together with a deleted-vertex mask; the legal actions at each step are exactly the vertices that have minimum current degree or would introduce minimum fill-in, which keeps the action space small; the reward is minus the number of fill-in edges created by the chosen elimination. The GCN scores each candidate from three node features, normalized degree, prospective fill-in, and whether the vertex is already eliminated, and masked PPO trains the scoring over 500,000 timesteps, so the agent effectively learns when to follow degree, when to follow fill-in, and how to break their ties.

What would settle it

Check an exact minimum-fill-in solution for a small graph, such as the PACE instances that have known exact answers, against ReFill's mask: if at any step the optimal order eliminates a vertex that is neither minimum-degree nor minimum-fill-in, that step is excluded from ReFill's action set and the mask is provably suboptimal on that graph.

Watch

Extended reading notes

Core claim

The paper's central claim is that a learned policy restricted to the candidate sets of the two classical heuristics still beats both heuristics themselves. ReFill keeps minimum-degree and minimum-fill-in vertices as the only allowable eliminations at every step, and trains a two-layer graph convolutional network with PPO to choose among them, with the reward at each step being the negative of the fill-in edges that elimination adds. The result is an elimination order with less fill-in than MDH and MFillH on almost every graph tested, plus a single policy that generalizes to fresh random graphs from the same distribution as training; the paper frames this as learning when to apply which heuristic and how to break its ties.

Load-bearing premise

The paper assumes that no good elimination order ever requires eliminating a vertex outside the masked set of minimum-degree or minimum-fill-in candidates.

Editorial extensions

If this is right

  • On 5×5 through 10×10 grid graphs ReFill matches or beats MDH and MFillH everywhere, tying at 5×5, with improvements up to 13.6% over MDH and 9.8% over MFillH.
  • On the 11 PACE 2017 graphs ReFill beats MDH on 10 of 11 (up to 18.6%) and beats MFillH on 9 of 11 while tying one and losing the remaining one by 1.5%.
  • Trained on 35 random $G(50, 0.2)$ graphs with one parameter set, the policy generalizes to 200 unseen graphs from that distribution with average fill-in reductions of 2.21% vs. MDH and 1.05% vs. MFillH, taking the best of 25 sampled orders per graph.
  • Taking the minimum fill-in of ReFill's order and the better heuristic order gives a further 0.63% average improvement, so the learned order can be bootstrapped rather than trusted outright.
  • Masking is load-bearing for training: the non-masking ablation converges far more slowly and stalls at local optima, while masking reaches fill-in below both heuristics, and each graph trains in under 30 minutes.

Reading between the lines

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

  • The reported gains are best interpreted as learned tie-breaking: since the mask only admits vertices the two heuristics already tie over, ReFill cannot discover eliminations that both heuristics would reject, only re-rank the ones they accept.
  • A direct test of the masking premise would compare ReFill's masked action sets against exact minimum-fill-in solutions on small instances; any optimal step outside the mask marks a hard ceiling for every masked policy on that graph.
  • Because the node features and aggregation are size-agnostic, the same trained weights could be probed on grids larger than 10×10 to see whether the learned tie-breaking transfers across scale, which the paper does not test.
  • The paper's closing suggestion of progressively relaxing the mask during training is a concrete extension: a curriculum that starts masked and widens the action set late might recover the divergent-from-heuristic orderings the mask currently excludes while keeping convergence fast.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper proposes ReFill, a reinforcement learning framework for the NP-hard fill-in minimization problem in sparse Gaussian elimination. A GNN-based policy is trained with masked PPO to select vertex elimination orders; at each step the action space is restricted to vertices that have minimum degree or minimum fill-in. The reward is the negative fill-in introduced by the chosen elimination. Experiments on 6x6 to 10x10 grid graphs and on 11 PACE 2017 Track-B graphs report fill-in reductions over the Minimum Degree Heuristic (MDH) and Minimum Fill-In Heuristic (MFillH) of up to 18.6% and 9.8%, respectively, using per-graph training and selecting the best elimination order found. A generalization experiment trains one policy on 35 G(50,0.2) graphs and evaluates on 200 new graphs from the same distribution, reporting average improvements of 2.21% over MDH and 1.05% over MFillH by sampling 25 orders per test graph and taking the minimum fill-in.

Significance. If the claims are sustained, ReFill would be a useful contribution to learned sparse-direct-solver heuristics, particularly for repeated-solve settings where a policy can be trained on the same sparsity pattern. The paper has real strengths: the MDP formulation with explicit fill-in reward is natural, the action-masking idea is a sensible way to reduce the combinatorial action space, the authors provide hyperparameter tables and code in the supplemental material, and the generalization experiment on unseen G(50,0.2) graphs is an honest test of transfer within a distribution. However, the current experimental evidence is weaker than the abstract claims. The central evaluation uses best-of-k sampling against deterministic single-run heuristics, per-graph training on the test instances, and no variance or confidence intervals. The comparison is therefore asymmetric and does not yet establish that the learned policy itself, as a standalone ordering rule, outperforms the heuristics.

major comments (4)
  1. [Section 4.3 / Appendix D] The generalization result rests on a best-of-25 evaluation protocol: Appendix D states that for each test graph 'we sample 25 elimination orders for each graph using the trained model, and report the minimum fill-in order found for each graph.' MDH and MFillH are evaluated as single deterministic orderings. Any stochastic policy with enough rollouts can beat a deterministic heuristic even if its expected or greedy rollout is worse, so the reported 2.21%/1.05% averages do not measure the quality of the learned policy as a standalone ordering rule. The paper must report the mean fill-in over the 25 sampled orders, the greedy (single-rollout) order from the trained policy, and the fraction of the 200 graphs on which that single rollout actually beats both heuristics. Confidence intervals or paired tests are also needed, since the histograms in Figures 19-21 show many instances with negative improvement.
  2. [Section 4.1 / Table 1] For Table 1, the evaluation metric is 'We select the best elimination order found by our RL algorithm' and training is performed separately on each test graph with per-graph hyperparameters listed in Appendix B. This is a per-instance stochastic search procedure, not an evaluation of a reusable learned policy; the reported numbers are single best-of-search results with no variance across random seeds. To support the paper's claims, the authors should report the fill-in of the final trained policy's greedy rollout on each graph (not the best over the training trajectory), and should include standard deviations over at least a few seeds. At minimum, the text should explicitly state that Table 1 measures per-instance RL search rather than generalization of a single learned ordering rule.
  3. [Section 3 (A Bird's-Eye View) / Section 5] The action-masking restriction is load-bearing: ReFill only allows actions among vertices that have minimum degree or minimum fill-in at each step. The paper justifies this by saying there is 'a high chance of including the truly optimal choice in most scenarios' but provides no proof or systematic measurement, and Section 5 itself acknowledges that masking 'risks excluding elimination orders that diverge from these heuristics.' If the optimal elimination order ever requires eliminating a vertex outside the masked candidate set, ReFill cannot find it. The authors should provide a concrete test on small graphs where exact minimum fill-in is computable (e.g., the PACE 2017 exact solver or exhaustive search for n <= 20) and report how often the optimal next vertex lies inside the masked action set, and how often an optimal order is reachable under the masking constraint. This is needed to bound what ReFill can in principle achieve.
  4. [Section 4.2 / Section 1 (Nested Dissection discussion)] The comparison set is too narrow for the strength of the claims. Only MDH and MFillH are used as baselines; nested dissection, which the paper itself discusses as a powerful method for grids, is not evaluated. On grid graphs nested dissection often produces near-optimal fill-in, so the reported 13.6% improvement over MDH may be an artifact of comparing against a weak baseline. Likewise, the PACE 2017 Track-B dataset comes with exact minimum fill-in values, yet the paper never reports the gap to optimal. The authors should add at least nested dissection and an approximate minimum degree algorithm (e.g., AMD) as baselines, and report the distance between ReFill's fill-in and the known optimal values on the PACE instances.
minor comments (5)
  1. [Section 4.2] The text uses '92.GRAPH' in uppercase while Table 1 and the dataset names are lowercase; please make the naming consistent.
  2. [Figures 4-18] Several captions contain typos such as 'Aberage Fill-in' and 'RFill'; these should be corrected to 'Average Fill-in' and 'ReFill'.
  3. [Appendix D] The command line writes results to 'nonmaskingresults/gnp.graph' even though the experiment uses action masking (--action_masking 1); the output path is misleading and should be renamed.
  4. [Section 4.1.1 / Appendix B] The description of the policy network should specify the number of hidden layers and the output head more precisely; Appendix B gives node_dim values per graph but does not clarify whether '--policy_sizes' being empty means a default architecture, and how the single scalar per node is converted to an action distribution under masking.
  5. [Section 3 / Equation (1)] The symbol pi is used both for the elimination ordering in Eq. (1) and for the learned policy pi*(u | G); this notational collision should be resolved for clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the training reward is the true fill-in cost and all reported comparisons are against external heuristics.

full rationale

The paper's derivation chain is self-contained with respect to external benchmarks. The RL objective is stated directly as the fill-in cost: 'The reward for each action is defined as the negative of the number of fill-in edges added by eliminating the chosen node' (Section 3), and the evaluation compares total fill-in against the standard Minimum Degree and Minimum Fill-In heuristics. There is no fitted constant that is later renamed as a prediction, and no load-bearing self-citation or imported uniqueness theorem. The action-masking scheme restricts the policy to vertices with minimum degree or minimum fill-in, which is a real limitation of the search space and is explicitly acknowledged in Section 5 ('masking actions to prioritize minimum degree or fill-in candidates ... risks excluding elimination orders that diverge from these heuristics'), but this is not circular: the policy can still learn tie-breaking rules within that restricted set, and the reported fill-in is measured from the actual elimination process rather than being defined in terms of the heuristics. The best-of-25 rollout selection in the generalization experiment is an evaluation-design weakness, but it does not make the reported result equivalent to a fitted parameter or to the training objective by construction. Therefore, no circular step meeting the evidentiary standard can be identified.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

No new physical or mathematical entities are introduced. The approach relies on standard graph-theoretic fill-in characterization, the no-cancellation assumption, and the unproved claim that masking to MDH/MFillH candidates retains optimal or near-optimal actions. The main hand-chosen inputs are per-graph training hyperparameters and the practice of reporting the best of 25 sampled orders in the generalization experiment.

free parameters (2)
  • Per-graph training hyperparameters (learning rate, node embedding dimension, policy sizes, number of timesteps… = learning rate 1e-4 or 5e-5; node dim 8, 16, or 32; see Table 2 and Appendices C-D
    Results in Table 1 are produced with different hyperparameters for each graph, chosen by hand; no sensitivity analysis is given, so the reported gains may depend on these choices.
  • Generalization rollout count (best-of-k selection) = 25 sampled orders per graph
    The generalization experiment reports the minimum fill-in among 25 stochastic rollouts, which is a selection procedure that benefits the learned policy relative to deterministic baselines.
assumptions (4)
  • standard math Rose-Tarjan-Lueker path characterization of fill-in (Theorem 1.1)
    Used to define fill-in cost exactly in terms of graph elimination; taken from [42] without proof.
  • domain assumption No lucky cancellations during Gaussian elimination
    Footnote 1 in Section 1 assumes nonzero entries are not cancelled numerically, so graph-theoretic fill-in matches actual factorization. Standard in sparse direct methods but can fail for specific matrices.
  • ad hoc to paper Minimum degree and minimum fill-in candidate sets contain near-optimal or optimal elimination choices at every step
    Section 3 action masking justification: 'preserving a high chance of including the truly optimal choice in most scenarios'. This is not proven and is the central restriction of the method.
  • domain assumption Graphs in the generalization test are drawn from the same distribution G(50,0.2) as training graphs
    Section 4.3 and Appendix D: generalization is demonstrated only within this distribution; performance across other matrix classes is not established, and the paper notes training across diverse graphs is unstable.

how reviews work

0 comments
Cite this review

Pith. "Pith review of ReFill: Reinforcement Learning for Fill-In Minimization." pith.science (2026). https://pith.science/paper/234RKAN6

@misc{pith2026250116130,
  author       = {Pith},
  title        = {Pith review of: ReFill: Reinforcement Learning for Fill-In Minimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/234RKAN6}},
  note         = {Machine review of arXiv:2501.16130}
}
abstract

Efficiently solving sparse linear systems $Ax=b$, where $A$ is a large, sparse, symmetric positive semi-definite matrix, is a core challenge in scientific computing, machine learning, and optimization. A major bottleneck in Gaussian elimination for these systems is fill-in, the creation of non-zero entries that increase memory and computational cost. Minimizing fill-in is NP-hard, and existing heuristics like Minimum Degree and Nested Dissection offer limited adaptability across diverse problem instances. We introduce \textit{ReFill}, a reinforcement learning framework enhanced by Graph Neural Networks (GNNs) to learn adaptive ordering strategies for fill-in minimization. ReFill trains a GNN-based heuristic to predict efficient elimination orders, outperforming traditional heuristics by dynamically adapting to the structure of input matrices. Experiments demonstrate that ReFill outperforms strong heuristics in reducing fill-in, highlighting the untapped potential of learning-based methods for this well-studied classical problem.

Figures

Figures reproduced from arXiv: 2501.16130 by the authors.

Figure 1
Figure 1. (a) A symmetric positive-definite matrix A and its factorization after Gaussian elimination with a fixed variable elimination order. This ordering introduces three fill-in entries at positions A2,4, A2,5, and A4,5, which were initially zero but became non-zero during elimination. (b) The same matrix after applying a permutation π = (5, 1, 2, 3, 4) via permutation matrix Pπ, which reorders the rows and columns of A b… view at source ↗
Figure 2
Figure 2. (a) The matrix A from [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. ReFill reinforcement learning environment. (a) An example observation s is updated by deleting vertex 1, introducing 3 fill-in edges (−3 reward). (b) Schematic of the RL loop using a GNN and masked PPO. 4.3 Generalization Experiment Appendix D discusses the generalization experiment in more details. On average, ReFill learns elimination heuristics that give an elimination order that is a 2.21% improvement over MDH a… view at source ↗
Figures from the paper (18 more)
Figure 4
Figure 4. Figure 4: Average fill-in (lower is better) on 8 × 8 grid, comparing masking vs. no masking during training. 4.6 Summary Overall, ReFill demonstrates that a tailored RL approach with GCN-based policies and action masking can outperform standard heuristics on both grid graphs and…
Figure 5
Figure 5. Figure 5: Average fill-in (lower is better) on 8 × 8 grid, comparing masking vs. no masking during training. $ python main . py d a t a s e t s / g ri d . n9 . graph −−o u t p u t f i l e n o n m a s ki n g r e s ul t s / g ri d . n9 . graph −−p o l i c y s i z e s 32 32 −−t o t…
Figure 6
Figure 6. Figure 6: Average fill-in (lower is better) on 9 × 9 grid, comparing masking vs. no masking during training. $ python main . py d a t a s e t s / g ri d . n10 . graph −−o u t p u t f i l e n o n m a s ki n g r e s ul t s / g ri d . n10 . graph −−p o l i c y s i z e s 32 32 −−t o…
Figure 7
Figure 7. Figure 7: Average fill-in (lower is better) on 10 × 10 grid, comparing masking vs. no masking during training. $ python main . py d a t a s e t s / 2. graph −−o u t p u t f i l e n o n m a s ki n g r e s ul t s / 2. graph −−p o l i c y s i z e s 16 16 −−t o t a l t i m e s t e p…
Figure 8
Figure 8. Figure 8: Average fill-in (lower is better) on 2.graph, comparing masking vs. no masking during training. $ python main . py d a t a s e t s / 3. graph −−o u t p u t f i l e n o n m a s ki n g r e s ul t s / 3. graph −−p o l i c y s i z e s 32 32 −−t o t a l t i m e s t e p s 50…
Figure 9
Figure 9. Figure 9: Average fill-in (lower is better) on 3.graph, comparing masking vs. no masking during training. $ python main . py d a t a s e t s / 1 1. graph −−o u t p u t f i l e n o n m a s ki n g r e s ul t s / 1 1. graph −−p o l i c y s i z e s 32 32 −−t o t a l t i m e s t e p …
Figure 10
Figure 10. Figure 10: Average fill-in (lower is better) on 11.graph, comparing masking vs. no masking during training. 21 [PITH_FULL_IMAGE:figures/full_fig_p021_10.png]
Figure 11
Figure 11. Figure 11: Average fill-in (lower is better) on 13.graph, comparing masking vs. no masking during training. $ python main . py d a t a s e t s / 1 8. graph −−o u t p u t f i l e n o n m a s ki n g r e s ul t s / 1 8. graph −−p o l i c y s i z e s 32 32 −−t o t a l t i m e s t e …
Figure 12
Figure 12. Figure 12: Average fill-in (lower is better) on 18.graph, comparing masking vs. no masking during training. $ python main . py d a t a s e t s / 2 3. graph −−o u t p u t f i l e n o n m a s ki n g r e s ul t s / 2 3. graph −−p o l i c y s i z e s 64 32 −−t o t a l t i m e s t e …
Figure 13
Figure 13. Figure 13: Average fill-in (lower is better) on 23.graph, comparing masking vs. no masking during training. $ python main . py d a t a s e t s / 2 6. graph −−o u t p u t f i l e n o n m a s ki n g r e s ul t s / 2 6. graph −−p o l i c y s i z e s 32 32 −−t o t a l t i m e s t e …
Figure 14
Figure 14. Figure 14: Average fill-in (lower is better) on 26.graph, comparing masking vs. no masking during training. $ python main . py d a t a s e t s / 4 0. graph −−o u t p u t f i l e n o n m a s ki n g r e s ul t s / 4 0. graph −−p o l i c y s i z e s 64 32 −−t o t a l t i m e s t e …
Figure 15
Figure 15. Figure 15: Average fill-in (lower is better) on 40.graph, comparing masking vs. no masking during training. 24 [PITH_FULL_IMAGE:figures/full_fig_p024_15.png]
Figure 16
Figure 16. Figure 16: Average fill-in (lower is better) on 92.graph, comparing masking vs. no masking during training. $ python main . py d a t a s e t s / 9 9. graph −−o u t p u t f i l e n o n m a s ki n g r e s ul t s / 9 9. graph −−p o l i c y s i z e s 64 32 −−t o t a l t i m e s t e …
Figure 17
Figure 17. Figure 17: Average fill-in (lower is better) on 99.graph, comparing masking vs. no masking during training. $ python main . py d a t a s e t s / 1 0 0. graph −−o u t p u t f i l e n o n m a s ki n g r e s ul t s / 1 0 0. graph −−p o l i c y s i z e s 64 32 −−t o t a l t i m e s …
Figure 18
Figure 18. Figure 18: Average fill-in (lower is better) on 100.graph, comparing masking vs. no masking during training. 26 [PITH_FULL_IMAGE:figures/full_fig_p026_18.png]
Figure 19
Figure 19. Figure 19: Improvement percentages over the 200 instances of [PITH_FULL_IMAGE:figures/full_fig_p027_19.png]
Figure 20
Figure 20. Figure 20: Improvement percentages over the 200 instances of [PITH_FULL_IMAGE:figures/full_fig_p028_20.png]
Figure 21
Figure 21. Figure 21: Improvement percentages over the 200 instances of [PITH_FULL_IMAGE:figures/full_fig_p028_21.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 47 canonical work pages

  1. [1]

    Low Data Drug Discovery with One-shot Learning

    Han Altae-Tran, Bharath Ramsundar, Aneesh S. Pappu, and Vijay S. Pande. Low data drug discovery with one-shot learning. CoRR, abs/1611.03199, 2016

    work page Pith review arXiv 2016

  2. [2]

    Amestoy, Timothy A

    Patrick R. Amestoy, Timothy A. Davis, and Iain S. Duff. An approximate minimum degree ordering algorithm. SIAM Journal on Matrix Analysis and Applications , 17(4):886–905, 1996

    work page 1996

  3. [3]

    Ahmed Begga, Francisco Escolano, Miguel Angel Lozano, and Edwin R. Hancock. Diffusion-jump gnns: Homophiliation via learnable metric filters. CoRR, abs/2306.16976, 2023

    work page Pith review arXiv 2023

  4. [4]

    Machine learning for combinatorial optimization: A methodological tour d’horizon

    Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research, 290(2):405–421, 2021

    work page 2021

  5. [5]

    Lower bounds for the parameterized complexity of minimum fill-in and other completion problems

    Ivan Bliznets, Marek Cygan, Pawe l Komosa, Micha l Pilipczuk, and Luk´ aˇ s Mach. Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. ACM Transactions on Algorithms (TALG), 16(2):1–31, 2020

    work page 2020

  6. [6]

    Boisvert, Roldan Pozo, Karin Remington, Richard F

    Ronald F. Boisvert, Roldan Pozo, Karin Remington, Richard F. Barrett, and Jack J. Dongarra. Matrix market: a web resource for test matrix collections. In Proceedings of the IFIP TC2/WG2.5 Working Conference on Quality of Numerical Software: Assessment and Enhancement , page 125–137, GBR, 1997. Chapman & Hall, Ltd

    work page 1997

  7. [7]

    State-of-the-art sparse direct solvers

    Matthias Bollh¨ ofer, Olaf Schenk, Radim Janalik, Steve Hamm, and Kiran Gullapalli. State-of-the-art sparse direct solvers. Parallel algorithms in computational science and engineering , pages 3–33, 2020

    work page 2020

  8. [8]

    A Journey through the History of Numerical Linear Algebra

    Claude Brezinski, G´ erard Meurant, and Michela Redivo-Zaglia. A Journey through the History of Numerical Linear Algebra. SIAM, 2022

    work page 2022

Show all 60 references
  1. [9]

    Yixin Cao and R.B. Sandeep. Minimum fill-in: Inapproximability and almost tight lower bounds. Information and Computation , 271:104514, 2020

    2020

  2. [10]

    Simple and deep graph convolutional networks

    Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event , volume 119 of Proceedings of Machine Learning R...

    2020

  3. [11]

    Supervised community detection with line graph neural networks

    Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019 . OpenReview.net, 2019

    2019

  4. [12]

    A survey of parameterized algorithms and the complexity of edge modification

    Christophe Crespelle, P ˚ al Grøn ˚ as Drange, Fedor V Fomin, and Petr Golovach. A survey of parameterized algorithms and the complexity of edge modification. Computer Science Review , 48:100556, 2023

    2023

  5. [13]

    A fast minimum degree algorithm and matching lower bound

    Robert Cummings, Matthew Fahrbach, and Animesh Fatehpuria. A fast minimum degree algorithm and matching lower bound. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’21, page 724–734, USA, 2021. Society for Industrial and Applied Mathematics

    2021

  6. [14]

    Graph reinforcement learning for combinatorial optimization: A survey and unifying perspective, 2024

    Victor-Alexandru Darvariu, Stephen Hailes, and Mirco Musolesi. Graph reinforcement learning for combinatorial optimization: A survey and unifying perspective, 2024. 13

    2024

  7. [15]

    The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration

    Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration. In Daniel Lokshtanov and Naomi Nishimura, editors, 12th International Symposium on Parameterized and Exa...

    2017

  8. [16]

    Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson

    Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. CoRR, abs/2003.00982, 2020

    2003 arXiv

  9. [17]

    Nested dissection of a regular finite element mesh

    Alan George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis , 10(2):345–363, 1973

    1973

  10. [18]

    Pande, and Jure Leskovec

    Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay S. Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020 . OpenReview....

    2020

  11. [19]

    A closer look at invalid action masking in policy gradient algorithms

    Shengyi Huang and Santiago Onta˜ n´ on. A closer look at invalid action masking in policy gradient algorithms. 2020

    2020

  12. [20]

    Optimization of graph neural networks with natural gradient descent

    Mohammad Rasool Izadi, Yihao Fang, Robert Stevenson, and Lizhen Lin. Optimization of graph neural networks with natural gradient descent. In Xintao Wu, Chris Jermaine, Li Xiong, Xiaohua Hu, Olivera Kotevska, Siyuan Lu, Weija Xu, Srinivas Aluru, Chengxiang Zhai, Eyhab Al-Masri,...

    2020

  13. [21]

    An efficient graph convolutional network technique for the travelling salesman problem

    Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227 , 2019

    1906 arXiv

  14. [22]

    Learning combinatorial optimization algorithms over graphs

    Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems (NeurIPS) , 30, 2017

    2017

  15. [23]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Variational graph auto-encoders. CoRR, abs/1611.07308, 2016

    2016 arXiv

  16. [24]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017

    2017

  17. [25]

    Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475, 2019

    Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475, 2019

    2019 arXiv

  18. [26]

    Bronstein

    Ron Levie, Federico Monti, Xavier Bresson, and Michael M. Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Trans. Signal Process., 67(1):97–109, 2019

    2019

  19. [27]

    Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceed...

    2016

  20. [28]

    Joseph W. H. Liu. Modification of the minimum-degree algorithm by multiple elimination. ACM Trans. Math. Softw. , 11(2):141–153, June 1985. 14

    1985

  21. [29]

    Is heterophily A real nightmare for graph neural networks to do node classification? CoRR, abs/2109.05641, 2021

    Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Is heterophily A real nightmare for graph neural networks to do node classification? CoRR, abs/2109.05641, 2021

    2021 arXiv

  22. [30]

    Streaming graph neural networks

    Yao Ma, Ziyi Guo, Zhaochun Ren, Jiliang Tang, and Dawei Yin. Streaming graph neural networks. In Jimmy X. Huang, Yi Chang, Xueqi Cheng, Jaap Kamps, Vanessa Murdock, Ji-Rong Wen, and Yiqun Liu, editors, Proceedings of the 43rd International ACM SIGIR conference on research and ...

    2020

  23. [31]

    Markowitz

    Harry M. Markowitz. The elimination form of the inverse and its application to linear programming. Management Science, 3(3):255–269, 1957

    1957

  24. [32]

    Reinforcement learning for combinatorial optimization: A survey

    Nina Mazyavkina, Sergei Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400, 2021

    2021

  25. [33]

    Finding increasingly large extremal graphs with alphazero and tabu search, 2023

    Abbas Mehrabian, Ankit Anand, Hyunjik Kim, Nicolas Sonnerat, Matej Balog, Gheorghe Comanici, Tudor Berariu, Andrew Lee, Anian Ruoss, Anna Bulanova, Daniel Toyama, Sam Blackwell, Bernardino Romera Paredes, Petar Veliˇ ckovi´ c, Laurent Orseau, Joonkyung Lee, Anurag Murty Naredl...

    2023

  26. [34]

    Rusu, Joel Veness, Marc G

    Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, ...

    2015

  27. [35]

    Maximum matchings in planar graphs via gaussian elimination

    Marcin Mucha and Piotr Sankowski. Maximum matchings in planar graphs via gaussian elimination. Algorithmica, 45(1):3–20, May 2006

    2006

  28. [36]

    Attending to graph trans- formers

    Luis M¨ uller, Mikhail Galkin, Christopher Morris, and Ladislav Ramp´ asek. Attending to graph trans- formers. CoRR, abs/2302.04181, 2023

    2023 arXiv

  29. [37]

    Recurrent space-time graph neural networks

    Andrei Liviu Nicolicioiu, Iulia Duta, and Marius Leordeanu. Recurrent space-time graph neural networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alch´ e-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems ...

    2019

  30. [38]

    Stable-baselines3: Reliable reinforcement learning implementations

    Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. Stable-baselines3: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22(268):1–8, 2021

    2021

  31. [39]

    Self- supervised graph transformer on large-scale molecular data

    Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self- supervised graph transformer on large-scale molecular data. In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in N...

    2020

  32. [40]

    Triangulated graphs and the elimination process

    Donald J Rose. Triangulated graphs and the elimination process. Journal of Mathematical Analysis and Applications, 32(3):597–609, 1970. 15

    1970

  33. [41]

    Donald J. Rose. A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In RONALD C. READ, editor, Graph Theory and Computing, pages 183–217. Academic Press, 1972

    1972

  34. [42]

    Donald J. Rose, R. Endre Tarjan, and George S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing , 5(2):266–283, 1976

    1976

  35. [43]

    Rossi and Nesreen K

    Ryan A. Rossi and Nesreen K. Ahmed. Networkrepository: An interactive data repository with multi-scale visual analytics, 2014

    2014

  36. [44]

    The graph neural network model

    Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks , 20(1):61–80, 2008

    2008

  37. [45]

    Proximal policy optimization algorithms

    John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. In arXiv preprint arXiv:1707.06347 , 2017

    2017 arXiv

  38. [46]

    Sutherland, and Ali Kemal Sinop

    Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Confere...

    2023

  39. [47]

    Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al

    David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484–489, 2016

    2016

  40. [48]

    Mastering the game of go without human knowledge

    David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354–359, 2017

    2017

  41. [49]

    Smit, Jianan Zhou, Robbert Reijnen, Yaoxin Wu, Jian Chen, Cong Zhang, Zaharah Bukhsh, Yingqian Zhang, and Wim Nuijten

    Igor G. Smit, Jianan Zhou, Robbert Reijnen, Yaoxin Wu, Jian Chen, Cong Zhang, Zaharah Bukhsh, Yingqian Zhang, and Wim Nuijten. Graph neural networks for job shop scheduling problems: A survey, 2024

    2024

  42. [50]

    Attention-based graph neural networks: a survey

    Chengcheng Sun, Chenhao Li, Xiang Lin, Tianji Zheng, Fanrong Meng, Xiaobin Rui, and Zhixiao Wang. Attention-based graph neural networks: a survey. Artif. Intell. Rev. , 56(S2):2263–2310, 2023

    2023

  43. [51]

    Sutton and Andrew G

    Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2nd edition, 2018

    2018

  44. [52]

    Or-gym: A reinforcement learning library for operations research problems

    Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Or-gym: A reinforcement learning library for operations research problems. In NeurIPS Datasets and Benchmarks , 2021

    2021

  45. [53]

    Graph attention networks

    Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li` o, and Yoshua Bengio. Graph attention networks. CoRR, abs/1710.10903, 2017

    2017 arXiv

  46. [54]

    Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Trans. Neural Networks Learn. Syst. , 32(1):4–24, 2021

    2021

  47. [55]

    Computing the minimum fill-in is np-complete

    Mihalis Yannakakis. Computing the minimum fill-in is np-complete. SIAM Journal on Algebraic Discrete Methods, 2(1):77–79, 1981. 16

    1981

  48. [56]

    Hamilton, and Jure Leskovec

    Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrnn: A deep generative model for graphs. CoRR, abs/1802.08773, 2018

    2018 arXiv

  49. [57]

    Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J. Kim. Graph transformer networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alch´ e-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 3...

    2019

  50. [58]

    Graph convolutional networks: Algorithms, applications and open challenges

    Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski. Graph convolutional networks: Algorithms, applications and open challenges. In Xuemin Chen, Arunabha Sen, Wei Wayne Li, and My T. Thai, editors, Computational Data and Social Networks - 7th International Conference, CSo...

    2018

  51. [59]

    Deep learning on graphs: A survey

    Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey. IEEE Trans. Knowl. Data Eng., 34(1):249–270, 2022

    2022

  52. [60]

    Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal A. C. Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors,...

    2021

Pith tools

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