Neural algorithmic reasoning is an emerging area of machine learning focusing on building models that can imitate the execution of classic algorithms, such as sorting, shortest paths, etc. One of the main challenges is to learn algorithms that are able to generalize to out-of-distribution data, in particular with significantly larger input sizes. Recent work on this problem has demonstrated the advantages of learning algorithms step-by-step, giving models access to all intermediate steps of the original algorithm. In this work, we instead focus on learning neural algorithmic reasoning only from the input-output pairs without appealing to the intermediate supervision. We propose simple but effective architectural improvements and also build a self-supervised objective that can regularise intermediate computations of the model without access to the algorithm trajectory. We demonstrate that our approach is competitive to its trajectory-supervised counterpart on tasks from the CLRS Algorithmic Reasoning Benchmark and achieves new state-of-the-art results for several problems, including sorting, where we obtain significant improvements. Thus, learning without intermediate supervision is a promising direction for further research on neural reasoners.
Paper
Similar papers
Peer review
Summary
The paper addresses neural algorithmic reasoning without the supervision of intermediate steps of reasoning. Typically, neural algorithmic reasoning requires supervision on the intermediate steps of reasoning. The paper proposes a method that does not require intermediate supervision and achieves competitive results with full-supervised benchmarks. The paper proposed a modified no-hint reasoning scheme that mimics the hints-supervision setting and self-supervised objective using the contrastive loss term for nodes for each step.
Strengths
Overall the paper addresses an important problem of the integration of reasoning with neural networks. The motivation is clearly argued in the paper. Neural algorithmic reasoning has been showing its strong capacity for structured reasoning as neural networks, but the approach requires dense supervision on intermediate steps. The proposed method mitigates this issue, reducing the amount of required effort and thus would extend the capacity and applicability of neural algorithmic reasoning for different tasks. The proposed method achieves competitive results against fully supervised benchmarks and shows its advantages. The obtained results are interesting and promising. The source code is available in the supplementary material.
Weaknesses
My major concerns regarding this paper are as follows. - The explanation of the method is somewhat unclear and is not easy to follow. For example, Hint-ReLIC is repeatedly referred to and used as an explanation. However, the paper does not provide enough explanations regarding Hint-ReLIC (although textual explanations are distributed in different parts of the paper), and that makes the presentation not easy to follow. Readers would gain benefits from a bit more detailed explanations regarding the key relevant method in the background section to understand the proposed method. - Experimental details are not explained enough. In Table 1, some cells do not contain values, but no specific reasons are clarified in the main text (if I am not missing them). In the right-most column of Table 1 and Table 2, values for Insertion/Bubble/Quick/Heap sort are all the same, even though the experiments are conducted on 5 different random seeds and stochastic gradient descent. This seems to imply that the proposed method produces exactly the same values for each different random seed across different tasks via stochastic optimization. If there is an explanation for why this happens, it would need to be mentioned in the main text.
Questions
Why are some values not available in Table 1? In the right-most column of Table 1 and Table 2, values for Insertion/Bubble/Quick/Heap sort are all the same, even though the experiments are conducted on 5 different random seeds and stochastic gradient descent. Why does this happen?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
Limitations
Some limitations are argued in the paper.
Summary
This paper addresses the challenge of developing neural networks capable of performing algorithmic reasoning. The paper discusses disadvantages about the use of intermediate hints during training of algorithmic reasoners. The authors propose a regularisation term to ensure that meaningful representations are learnt during the neural execution of algorithms, even when no supervision occurs on intermediate steps.
Strengths
The paper is written clearly. Discussion of background and prior work is comprehensive. Source code is provided for reproducibility of the experiments. The paper is not very original, as it borrows concepts and formulations from [1]. However, the authors use these concepts in an alternative way. While [1] uses the regularisation loss to build a causal model, the authors use it to ensure that a neural network computes the same representations (at all steps) for any two inputs x_1, x_2 for which the execution of the algorithm A would be the same. I find this idea a clever augmentation technique. Quantitative results show supposedly good improvements in sorting algorithms with respect to baselines. [1] B. Bevilacqua, K. Nikiforou, B. Ibarz, I. Bica, M. Paganini, C. Blundell, J. Mitrovic, and P. Velickovic. Neural algorithmic reasoning with causal regularisation.
Weaknesses
As mentioned above, all concepts and regularisation terms are not new and borrowed as-is from [1]. Experimental details are somewhat scarce and sometimes imprecise. For instance, the authors do not state the hidden dimensions of their models. Furthermore, this technique seems to be applicable only on a small portion of all problems in the CLRS benchmark, which greatly limits the potentiality of the method. Fundamentally, this technique seems to be only useful in the case of sorting, since in all other tested techniques it performs significantly worse. Plus, training networks the way authors propose in this paper will not align with any specific algorithm dynamics (as the authors correctly recognised in the limitation). In fact, judging from the sorting results (98.74% everywhere) it seems that the network has learnt a different algorithm w.r.t to insertion/bubble/quick/heap sort (or possibly only one of them). The authors main point is that the regularisation term is forcing similar representations for the inputs to have the same execution trajectories, but there’s no experiments nor theoretical analysis confirming this property. One thing I find very concerning is that the authors claim to fix the number of steps of the network (i.e., the number of steps in the “neural execution” phase) to be linearly dependent on the number of input size (i.e., O(n)). This means that the network must have learnt a sorting algorithm that achieves around 98% accuracy and runs in linear time, which feels very strange, unless the constant is high enough to behave well with array of 64 elements (test size). [1] B. Bevilacqua, K. Nikiforou, B. Ibarz, I. Bica, M. Paganini, C. Blundell, J. Mitrovic, and P. Velickovic. Neural algorithmic reasoning with causal regularisation.
Questions
Q1) Can the Authors provide some insights on why the proposed technique only works for sorting algorithms? Q2) The proposed technique seems likely to be effectively used in conjunction with supervision on hints: have the Authors tried that? Or do the Authors believe that it is not applicable? Q3) Given that the manuscript reports 98.74% \pm 1.12 for all sorting algorithms, it looks like that the network is not aligning with any specific sorting algorithm, but potentially learns a different one. Have the Authors tried investigating in this direction? Q4) What is the exact number of steps that the network performs during algorithm rollout?
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
2 fair
Contribution
1 poor
Limitations
Limitations are adequately addressed.
Summary
The paper is about neural algorithmic reasoning, which is the task of building models that can execute classical algorithms. The paper focuses on learning algorithms without intermediate supervision, which means using only input-output pairs and not the steps (hints) of the algorithm. The paper proposes two improvements for this setting: a simple architectural change that makes the model more similar to the hint-based version, and a self-supervised objective that regularizes the model by forcing similar representations for inputs with the same execution trajectories. The paper shows that these improvements lead to competitive or state-of-the-art results on a subset of the CLRS benchmark. The paper argues that learning algorithms without intermediate supervision is a promising direction for neural algorithmic reasoning.
Strengths
1. Learning algorithms without intermediate supervision is an important direction for neural algorithmic reasoning. 2. The contrastive term added is insightful and the corresponding results are promising.
Weaknesses
1. The fundamental difference between the proposed "no-hint" and the original "no-hint" has not been stated clearly - the proposed "no hint" seems to only have added the hidden layer size or the neural network capacity. If so, the comparison against the original “no-hint” is unfair. Can the authors give a more detailed description of the proposed “no hint” architecture? Also, please list relevant hyperparameters (like size, layers) on the network, and conduct a comparative experiment on the network size. 2. The “step count” setting in section 5.2 is also confusing: is step count the main reason why the proposed no-hint performs better than the original no-hint? 3. Table 2 is somewhat confusing: No hint (with our updates) & Binary Search has 93.21 ± 1.10 which is different from 87.12 ± 2.23 or 85.29 ± 4.52 in Table 1. Also, I think taking the maximum of No hints (ours) and Add contr. (ours) as “ours” in Table 2 is not a good choice since they are different methods proposed. 4. Although the proposed new contrast item can improve the performance without hints, I doubt that the design of this item is extremely challenging (which might have already been mentioned in section 6 limitations), even more so than obtaining hint data. This is because the design of this item requires a deep understanding of the target algorithm itself and the designer must be an algorithm expert, while obtaining hint data only requires a corresponding executable algorithm. This may deviate from the original intention of “without intermediate supervision” and greatly reduce the actual effectiveness of this paper. 5. The writing needs to be improved.
Questions
1. Table 2 should be merged into Table 1 since only one column is different. 2. Can you show the latent representation change with the number of steps? Can it correspond to the hint of the algorithm?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
2 fair
Contribution
3 good
Limitations
Limitations have been discussed by the authors.
Summary
This paper proposes a novel method for Algorithmic Reasoning without intermediate supervision. The core idea is to use a self-supervised objective that regularize the internal computations. The authors evaluated the proposed method with CLRS algorithmic reasoning benchmark and achieve state-of-the-art performance on a subset of problems. To the best of my knowledge, the contribution is novel and clear and I recommend acceptance.
Strengths
This paper is well-motivated and relatively easy to follow. The design of regularization for the self supervision scheme is also quite intuitive. The evaluations are comprehensive and seems to support the effectiveness of the proposed approach. I appreciate the specific emphasis of potential limitations.
Weaknesses
While the main experiment/evaluation is informative, I would appreciate if the authors address some potential ablations such as varying numbers of augmentations.
Questions
In the limitation sections, the authors mentioned the issues with requirements for strong inductive bias for the self-supervised regularization scheme. I would appreciate the authors to address the potential concern on computation with respect to search.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
As mentioned in Strength, I appreciate authors' detailed inclusion of limitations. I do not think there are major limitations in addition to the said ones given the current content.
Summary
The paper focuses on neural networks that learn to execute algorithms, using the CLRS benchmark. It tackles the case of learning to execute when there are no hints available (no access to intermediate steps of the algorithm's trace). To do that, it proposes two modifications: the first is architectural, which is maintaining the latent representation of the current step and using it for the next step, which previous no-hint architectures discard and architectures using the hints use to decode the predicted hint and compute an additional loss by comparing with the ground-truth hint. The second one proposes a contrastive loss aimed to reduce the function search space, by using the following invariance: inputs that have the same (algorithmic) trajectory (belonging to the same equivalence class should have the same representation. The two modifications improve on the no hints baseline and in many cases match the model with hints.
Strengths
As the strengths outweigh the weaknesses of this paper, I recommend acceptance in its current form. I would be happy to increase my score if some of the weaknesses are addressed. The strengths of the paper include great clarity and sensible proposals to improve no-hint performance, such as maintaining a similar computation graph and using invariances to reduce the search space in lack of stronger inductive biases. Moreover, the evaluation is thorough and the improvements brought show a clear step in the direction of accurately learning algorithms without hints.
Weaknesses
I think the paper would be greatly strengthened by improving the motivation towards doing no-hint learning. As the performance of the proposed models is not consistently better than that using hints, it is likely that at the moment, this is not enough evidence to convince towards porting to no-hint neural algorithmic reasoners for polynomial algorithms. One way to improve this would be to improve it empirically (considering other invariances, introducing stronger inductive biases, extending the number of algorithms it is applicable to—perhaps applying the model to NP-hard problems, where having hints is not scalable because of exponential-time complexity), or providing ablation studies of some of the initial motivating points: abilities of no-hint architectures to do parallel processing or new ways/insights of learning to solve the problem. I also think that the argument of human effort should be further clarified in the limitations — while hints are generated using the algorithm's implementation therefore they come "for free" with the dataset generator, finding augmentations requires understanding of the algorithm's invariances, which is also based on human effort. It would be useful if a few phrases could be clarified: - “We note that the computation of hint predictions and encoding them to the processor in the encoded-decoded mode can be expressed as an additional message-passing step over the nodes, edges, and graph features” could be made clearer by including information on how hints are computed - "a latent representation of type mask located at edges” is not immediately obvious - it is mentioned that the setup is the same as in previous work, but restating the training and testing regime (such as size of inputs) would be beneficial.
Questions
Please see weaknesses section.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
4 excellent
Contribution
3 good
Limitations
The authors have included a discussion on the limitations of the proposed method.
Reply to the rebuttal
I thank the authors for the detailed clarification. As the concerns are addressed adequately, I raise the score to 6 (from 5). I defer to the other reviewers for the deep assessment of the novelty/originality of this work due to my limited knowledge.
Thanks for the response! Some of my concerns have been addressed but I still have the following ones: **1. About the "no-hint" structure.** The authors say that "Such modifications add a small group of parameters for the encoder (green line in Figure 2) and decoder (red line in Figure 2) (encoder and decoder are single linear layers), keeping the hidden size of the model the same." So my original understanding is correct, right? "no hint" seems to only add two linear layers, and the effect is to increase the network capacity. Or, can the authors explain more about the design of the "encoder and decoder"? There is no evidence why the added layers are named "encoder and decoder" because there is no demarcation between the so-called encoder and decoder like corresponding loss, explicit tensor form transformation, etc. Think about seq2seq models, the demarcation between the encoder and decoder is very clear. As a comparison, I cannot see the demarcation in "no hint". And that's why I take the "encoder-decoder" design as simply increasing network capacity and ask the authors to list hyperparameters of the network. Or, one simple question: What does the latent representation look like and how do you supervise the training of it? "Hint" is not necessary here but you must have some constraints like losses or architecture designs or training algorithms, to make the latent representation behaves like a hint. Otherwise, they are simple linear layers. **2. The design of this item requires a deep understanding of the target algorithm itself and the designer must be an algorithm expert.** Can the authors give a concrete example of the design cost of the two methods? This is important for validating the motivation.
Thank you for being involved in the discussion and for all your questions, which highlight the parts of the paper that need to be additionally clarified! **1. About the "no-hint" structure.** >So my original understanding is correct, right? "no hint" seems to only add two linear layers, and the effect is to increase the network capacity. Yes, the difference is just in two linear layers, which are presented in the model with hint supervision. In other words, we argue that for a fair comparison versus the hint model, one needs to remove the loss on the intermediate steps, keeping the computational graph the same, while the previous work removed these linear layers (Figure 2 of the paper). >Or, can the authors explain more about the design of the "encoder and decoder"? Such naming is nested from the model with hints, the encoder maps abstract objects (node features, edge weights) to the latent space, while the decoder constructs abstract objects (e.g., a pointer from a node to another node) from the latent space. We agree that for a no-hint model, this naming is useful only for encoding inputs and decoding outputs of the model, while for the intermediate steps there is no abstract meaning. Also, phrases like «we propose to run the no-hint model in the encoded-decoded mode» (line 161) from the paper are used only for consistency with hint-based models. We will make it more transparent in the text. >What does the latent representation look like and how do you supervise the training of it? Such a «decoded» intermediate state is a single logit for each edge (line 283) (binary mask over the edges), which is «encoded» to the adjacent node features at the next step of the computation. Such states have no additional constraints: - the no-hint model is trained only with supervision loss on the output of the model (and not the intermediate steps); - the proposed contrastive term forces invariance of these states for equivalent inputs, but these states are not supposed to ‘behave like a hint’ (while potentially could). **2. The design of this item requires a deep understanding of the target algorithm itself and the designer must be an algorithm expert.** >Can the authors give a concrete example of the design cost of the two methods? First, we would like to note that we do not argue that finding the invariances is in some sense easier or harder than building good hints, both methods have additional costs. But the main difference between these two methods is not the cost, but that the invariance utilizes the fact that models usually find solutions that are more aligned with their architectures (so aligning them to a particular trajectory can be a suboptimal or difficult task). Answering your question: We believe that for hint supervision, the main cost is to align the model to the desired algorithm: for each architecture, one needs to decompose the algorithm execution trajectory to the sequence of steps, each of which the model should predict. Also, one needs to carefully design transitions between steps, making hints predictable from previous steps, but not so simple, keeping the execution trajectory relatively short. For example, we would refer to the hint trajectories from the CLRS Algorithmic Reasoning Benchmark (Veličković et al., 2022) for the Insertion Sort algorithm. The insertion phase is “compressed” to the single step of message-passing (which is possible due to the parallel processing of modern architectures), another option was to use another constant steps count or $O(n)$ steps (similar to the ground-truth algorithm), even the simple algorithm produces a lot of different ways to convert it to the hints trajectory and each particular choice directly affects the performance of the model, as intermediate predictions are supervised to correspond exactly to the hints. Given the fact that for 14 of 18 problems the no-hint (ours) performance is better than hint supervision, we could say that existing hints/hint losses are possibly not optimal. As for the proposed contrastive technique, the main cost is to understand for which inputs the algorithm will perform identically. For example, for comparison sort algorithms this is easy (we can consider inputs with the same relative order of the elements), for other algorithms it may require a deeper understanding of the underlying problem. The common idea behind the contrastive term is utilizing the same execution trajectory for different inputs. Even a simple notion on the relative order of the inputs is applicable for several different problems since sorting or taking the maximum occurs as a subtask in a variety of problems (e.g., in addition to the MST problem described in the paper, there is also building the heap/search tree from some values). Once such invariants are found, it is clear how to apply the contrastive term regardless of the architecture used. We hope this answers the question and we are open to further discussion on the raised points.
Thanks for the authors' response! I have doubts about the two questions, and I have raised my score. However, I'm still not convinced by the "we do not argue that finding the invariances is in some sense easier or harder than building good hints" and take it as a weakness of the paper.
Considerations on rebuttal
First of all, thanks to the Authors for their response and for clarifying previously obscure experimental details. Let there be no doubts, both contributions (i.e., modification of the no-hint regime and addition of the self supervised term) are sensible and interesting investigations, especially considering targeting of NP-hard problems, where we clearly cannot supervise on intermediate hints. However, there are still fundamental issues in the work: 1) From the authors’ response it has emerged that data for all algorithms are cliques (even for sorting algorithms were usually data are arrays and could very well be represented as undirected chains), this should be specified clearly in the text. This is a direct consequences of using the Triplet-GMPNN processor. As being fully-connected, cliques suit the ``parallel processing’’ paradigm that the authors present in lines 136-139 as a motivation for introducing the self-supervised term. That is also the reason why their model could perform sorting in O(n) steps. The performance of the method was not tested in case where algorithmic data are represented differently from cliques, or, equivalently, if a different processor was used (not based on fully-connected graphs), making the assessment of the proposed approach not possible in such cases. Surely, one can always take into account the fully-connected version of any graphs when applying this method, but this would {\it greatly} impact scalability. The method would be inapplicable for large graphs. 2) Figure 1(b) shows that the self-supervised term does bring representations closer, for nodes having the same algorithm trajectory. However, I think that the authors must include also other baselines in that analysis, such as Hint-ReliC, and move the figure somewhere in the main paper. It is important to compare the behaviour of node representations also for other baselines, especially considering that GNNs in general tend to bring neighboring nodes' representations closer anyway. I expect the authors' proposed method still performs the best, but I believe it has to be verified and illustrated clearly. 3) Since the model is not aligning with any specific algorithms, it is not fair to present results on Heapsort, Quicksort, Bubblesort and Insertion Sort as four different results. Indeed, without supervising on hints these four algorithms are indistinguishable from one another. This is confirmed by the fact that the model achieved exactly the same accuracy on all four algorithms, as I pointed out in the original Q3. Overall, this method seems to tackle {it solving of algorithmic problems} rather than {\it learning of algorithms}. One may argue that in order to {\it solve} algorithmic problems, the network must learn an algorithm anyway. While I agree with this, I still find the comparisons within Table 1 not sensible, since those results show how well algorithms are imitated in principle. 4) Follow-up question from 3): I suspect that authors' used the same 5 seeds for all experiments on sorting, since results are * exactly * the same and algorithms are indistinguishable given the absence of supervision on intermediate steps. For the same reason, I believe the same should happen for MST algorithms (Kruskal and Prim), but results are different there. Did the authors use different seeds for Kruskal and Prim?
Thank you for your involvement in the discussion and valuable comments! Let us address the remaining concerns: Q1) Let us explain why we believe that our contributions do not rely on the full graph. First, parallel processing arises even with the mentioned chain graph inputs, as a single message-passing step can simultaneously update all nodes at once. We also note that even on the chain graph, sorting could perform in O(n) steps on the message-passing framework with global graph features (the presence of the global state requires only one additional node with $n$ additional edges). For example, in the insertion sort, the insertion phase for each node could be done in $O(1)$ (as proposed by the original hints trajectory from the CLRS Algorithmic Reasoning Benchmark, where hints were designed for parallelizable but not necessarily fully-connected architectures, such as, e.g., a chain). Second, the proposed contrastive term is also not relying on the density of the graph, as this term can be used with any architecture. Since both our ideas (no-hint modifications and contrastive term) can be applied to any processor, we have chosen Triplet-GMPNN as the state-of-the-art processor showing good results in the previous work (Ibarz et al., 2022; Bevilacqua et al., 2023). We agree that the details of Triplet-GMPNN should be added to the experiment setup and will do this. Q2) We are grateful to the reviewers for their ideas for additional experiments and will definitely add all the figures and tables from the general response to the updated version of the paper. We would be happy to use the Hint-ReLIC models for additional experiments, however, the original implementation of this method is not published yet. We will add other hint-based sorting models (Bubble sort, Merge sort, Quicksort) as baselines to this comparison. Q3) It is true that without hints different algorithms become indistinguishable from one another and it is more suitable to consider the original problem (e.g., sorting), rather than a particular way of solving it. But we note that the alignment of the model to the particular execution trajectory is usually not the goal, but mainly the approach to improve the generalization abilities of the models (Veličković et al., 2022). So the comparison of the OOD performance for different methods (such as, for example, aligning to Bubble Sort with hint supervision, to Merge Sort with Hint-ReLIC, or training the sorting problem without hints) is reasonable and crucial on the path to strongly generalizable reasoners. We also agree that demonstrating no-hint performance under the names of the particular algorithms can be confusing, however, such choice is used as a convention in previous work (Mahdavi et al. (2023), Bevilacqua et al., (2023)). We will clarify this in the text by adding the corresponding comment for the table. If you have any other suggestions for how to better present this result - we will be happy to incorporate them in the revised version. Q4) Yes, as all the sorting tasks become the same and scores may differ only by a random seed, so we reported the same numbers for all sorting algorithms to highlight this. However, for the MST problem, while the underlying problem is the same and the same input/output can be used, there are differences coming from the CLRS Algorithmic Reasoning Benchmark: the Kruskal algorithm takes the graph as an input and the output is a binary mask on the edges from the MST, while the Prim algorithm takes as input the graph and the starting node and predicts for each node the pointer to another node (representing the order of extension of connected components). Such differences produce separate optimization problems. We would like to know whether we have answered all the questions and concerns raised by the reviewer. We are happy to discuss further any of the raised weaknesses and questions!
Further response
A1) I acknowledge that sorting can be performed, theoretically, in O(n) processor steps even in the case of a chain graph. I expect, however, a degradation in performance compared to the full graph version (whether this degradation would be significant is to be verified through experimentation). Parallelism is indeed preserved, but the network would be obviously unable to perform as many comparisons as it does for the full graph version. A2) I am happy to hear about adding more baselines to the mentioned experiments. A3) In my previous question, I was not only referring to the no-hint version but also to the model with the contrastive term. I acknowledge that the authors followed prior work in presenting results of Table 1. However, I strongly encourage the authors to clarify this in the text. A4) I see. I thank the authors for clarifying many of my concerns and for engaging in a very fruitful discussion. I consider, however, the lack of experiments on non-fully connected graphs a major drawback of the empirical evaluation of the proposed approach. In light of this, I decided to raise my score but I am not fully convinced that this work, without a stronger empirical evaluation, deserves a full accept.
We thank the reviewer for their deep involvement in the discussion and for raising the score! Regarding a major drawback, mentioned by the reviewer: We would note that currently there is a significant gap in performance between full-graph and sparse architectures, making the dense architectures the objects of the main interest in the field: Mahdavi et al. (2023) - MPNN over the full graph combined with transformer over the full graph; Bevilacqua et al., (2023) - Triplet-GMPNN; Ibarz et al. (2022) - Triplet-GMPNN; Diao and Loynd, (2022) - transformer over the full graph. For example, Ibarz et al. (2022) demonstrates >= 25% performance gain over other architectures on average across different algorithms. Even given the fact that our contributions do not rely on the full graph and improve the current state-of-the-art performance, we agree that proposed changes can affect the performance differently depending on the architecture. We would be happy to consider sparse architectures in our evaluation and will be happy if you mention some architectures you would like to see in such experiments. To the best of our knowledge, there are no sparse architectures with performance close to the current state-of-the-art models.
Thank you for the response! The main point I raised has been partially addressed through one of the new studies, strengthening my opinion that the paper should be accepted. I increased my score accordingly.
Decision
Accept (poster)