Slack-Free Spiking Neural Network Formulation for Hypergraph Minimum Vertex Cover

Authors: ngoc-bang  tam
  nguyen
anh-dzung  doan
zhipeng  cai
tat-jun  chin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-04-24 15:07:46

Abstract: Neuromorphic computers open up the potential of energy-efficient computation using spiking neural networks (SNN), which consist of neurons that exchange spike-based information asynchronously. In particular, SNNs have shown promise in solving combinatorial optimization. Underpinning the SNN methods is the concept of energy minimization of an Ising model, which is closely related to quadratic unconstrained binary optimization (QUBO). Thus, the starting point for many SNN methods is reformulating the target problem as QUBO, then executing an SNN-based QUBO solver. For many combinatorial problems, the reformulation entails introducing penalty terms, potentially with slack variables, that implement feasibility constraints in the QUBO objective. For more complex problems such as hypergraph minimum vertex cover (HMVC), numerous slack variables are introduced which drastically increase the search domain and reduce the effectiveness of the SNN solver. In this paper, we propose a novel SNN formulation for HMVC. Rather than using penalty terms with slack variables, our SNN architecture introduces additional spiking neurons with a constraint checking and correction mechanism that encourages convergence to feasible solutions. In effect, our method obviates the need for reformulating HMVC as QUBO. Experiments on neuromorphic hardware show that our method consistently yielded high quality solutions for HMVC on real and synthetic instances where the SNN-based QUBO solver often failed, while consuming measurably less energy than global solvers on CPU.

Main paper: 
 introduction: 
 Neuromorphic computing research aims to develop computational models inspired by neural architectures found in nature. Spiking neural networks (SNN), in which a network of processing units (neurons) asynchronously transmit spike-based messages to each other [34] , is a notable representative of the neuromorphic paradigm. Through parallelism, stochastic behavior, event-driven computing and other biologically-inspired properties, SNNs promise higher energy efficiency than conventional computing, which includes the successful artificial neural networks (ANN) [16] .The advent of neuromorphic computing hardware that can implement SNNs has boosted research in the area. Notable examples include IBM TrueNorth [25] and Intel Loihi [12, 30, 35] . Rigorous benchmarking [13] indicate the promise of SNNs in delivering energy efficient computations, which not only benefit edge computing applications, but also reducing the energy consumption of data centers. The recent introduction of Intel Hala Point [1] , the world's largest neuromorphic supercomputer with 1.15 billion neurons and 138.2 billion synapses, is a testament of confidence in the technology.Two major classes of problems have been explored for SNNs: machine learning and combinatorial optimization [13] . Representative approaches in the former include training SNNs using asynchronous variants of backpropagation, and converting pre-trained ANNs into equivalent SNNs for deployment on neuromorphic hardware. Works in the latter develop SNNs to solve specific optimization problems, where the spike-based temporal information processing is exploited to achieve computational benefits over classical methods. Our work focuses on combinatorial optimization.The concept of energy minimization of the Ising model underpins SNN techniques for combinatorial optimization. The task is closely related to quadratic unconstrained binary optimization (QUBO)EQUATIONwhere Q ∈ Z N ×N is a symmetric coefficient matrix (we restrict Q to integers to facilitate the SNN treatment; integers are sufficient nonetheless for the targeted combinatorial problem). Several SNNs have been developed to solve QUBO [6, 14, 3, 32] ; Sec. 3.2 will describe such a method. To bring such SNNs to bear on other combinatorial problems, the problems must first be reformulated into QUBO [11, 22] . For problems with feasibility constraints, penalty terms and often slack variables will be added to the QUBO objective to implement the constraints. Examples are provided below. Problem 1 (Minimum vertex cover (MVC)). Let G = (V, E) be a graph with vertices V = {1, . . . , N } and edges E = {e 1 , . . . , e K }, where each e k = ⟨i (k) , j (k) ⟩ ⊂ V connects two vertices.A vertex cover of G is a subset Z of V such that every edge is incident with at least a vertex in Z.The goal of MVC is to find the vertex cover with the smallest number of vertices. LetEQUATIONbe a binary vector whose role is to select a subset of V , where z i = 1 indicates that the i-th vertex is selected, and z i = 0 means otherwise. MVC can be expressed asEQUATIONEQUATIONNote that ∥z∥ 1 = ∥z∥ 2 for binary z and the equality constraints in (3) are quadratic in z. Rewriting the equality constraints as penalty terms, we obtain the QUBOEQUATIONIntuitively, solutions z that violate the constraints in (3) will raise the total cost in (4) and hence be penalized. The quantity λ ∈ Z is the penalty weight that controls the degree of penalization due to constraint violations. Note that while (4) is not exactly in the form (1) due to the existence of a constant, the remaining steps to rearrange (4) to (1) are minor; see supplementary material. Problem 2 (Hypergraph minimum vertex cover (HMVC)). Let H = (V, F ) be an r-uniform hypergraph with vertices V = {1, . . . , N } and hyperedges F = {f 1 , . . . , f K }, where each f k ⊂ V is incident with exactly r vertices, r ≥ 2. A vertex cover of H is a subset Z of V such that every hyperedge is incident with at least a vertex in Z. The goal of HMVC is to find the vertex cover with the smallest number of vertices. Note that HMVC reduces to MVC if r = 2. For each hyperedge f k , define a binary vector bEQUATIONwhere ∥b (k) ∥ 1 = r, and b(k) i = 1 means that vertex i is incident to f k and b (k) i= 0 means otherwise. HMVC can then be written asEQUATIONwhich is a 0-1 integer linear program (ILP). Since r variables (r ≥ 2) exist in each linear inequality constraint, in general it is not possible to express it as a quadratic equality constraint, cf . (3). Instead, the path to QUBO will involve converting each inequality into an equality constraintEQUATIONwhich requires introducing r ′ binary slack variables for each f kEQUATIONwhere r ′ = r -1 and 1 r ′ is a column vector of 1 of size r ′ . Installing the equality constraints as quadratic penalty terms, we obtain the QUBOEQUATIONwhere λ ∈ Z is the penalty weight. See supp. material for rewriting the QUBO in form (1) .A major difference between the QUBO reformulations for MVC and HMVC is that the latter requires slack variables, the quantity of which scales linearly with the number K and degree r of hyperedges. This significantly increases the search space and difficulty of the optimization. As we will show in Sec. 5, the established SNN-based QUBO solver [3] is unable to satisfactorily solve HMVC based on (9) . This presents an obstacle towards applying SNNs to a combinatorial problem with many practical applications, e.g., computational biology [9] , computer network security [19] , resource allocation [7] and social network analysis [23] . Fundamentally, HMVC is a general optimization problem that encompasses several related formulations, such as set cover, hitting set, and traversal [5] ,giving it wide applicability. The issue calls for a more effective SNN for HMVC.To solve HMVC more effectively, we propose an SNN that is composed of a mix of non-equilibrium Boltzmann machine (NEBM) spiking neurons [32] and a custom feedback spiking neuron. One feedback neuron is introduced for each constraint in (6) to check for constraint violations and encourage the overall state to return to feasibility. A major benefit of our handcrafted SNN is obviating the need to reformulate HMVC as QUBO based on the penalty method, which not only avoids the usage of slack variables, but also removes the necessity to tune the penalty weight.Results on Intel Loihi 2 [30] indicate that our SNN significantly outperformed the QUBO approach on HMVC, in that our method consistently yielded high-quality solutions on synthetic and real problem instances where the SNN-based QUBO solver [3] often failed to return feasible results. Moreover, our SNN consumed measurably much less energy than global solvers on CPU.Our work follows the spirit of other handcrafted SNNs for combinatorial optimization [8, 31, 17, 21, 36] . However, such works have mainly been targeted at constraint satisfaction problems, whereas our SNN is aimed at a graph-based optimization problem, i.e., HMVC (more details in Sec. 2). 
related work: 
 Previous studies have shown that an SNN with a topology corresponding to the matrix Q can efficiently solve QUBO [3, 6, 14] . This enables neuromorphic computing to solve combinatorial problems that can be encoded as QUBO, such as graph partitioning [26] . In addition, via the penalty method [29, Chap. 17], other combinatorial problems with constraints can be reformulated into QUBO [15] . Problem 1 has discussed this for MVC, which has been evaluated on a neuromorphic processor [11] . Other works that employed QUBO reformulation include [32, 22] who solved maximum independent set and ILP. However, more complex problems will require the introduction of slack variables, which increases the search space and difficulty for an SNN solution. Problem 2 has illustrated this for HMVC.The majority of handcrafted SNNs for combinatorial optimization aim to solve constraint satisfaction problems (CSPs). Jonke et al. [21] proposed a stochastic SNN for traveling salesman problem. Since then, several SNN solvers have been proposed for CSPs, such as, Sudoku [8, 31] , graph coloring [17] , and Boolean satisfiability problem [21, 36] . These existing approaches share a common strategy: constructing a specific SNN topology that is strongly tailored to the constraints of each CSP. This is to ensure that these SNN solvers can seek valid values for a set of variables that satisfy the specified constraints. In other words, the primary objective of these handcrafted SNNs is to find feasible solutions to the combinatorial optimization problem. Although our approach shares a similar spirit to these handcrafted SNNs in that we directly construct SNN topology using constraints, our SNN topological graph is specifically designed to seek not only a feasible solution but also the optimal one.The QUBO formulation is amenable to Ising-specific analog and digital hardware solvers, including spintronics, memristors, and quantum annealers [27] . However, given our focus on SNNs, we leverage the state-of-the-art Loihi 2 neuromorphic accelerator to implement the SNN solutions for both QUBO and our method, due to its high flexibility in SNN design and programmable neuron model. For a comprehensive overview of Loihi 2's capabilities, we refer readers to [24, 32, 35] .There is a large body of work on SNNs for machine learning; we refer to [13] for a thorough survey. While SNNs are usually less accurate than ANNs [28] , under certain temporal dynamics, SNNs can surpass ANNs. SNNs have also been used for robotics. For instance, [24] implemented their SNN-based quadratic programming solver for model predictive control on Loihi 2, achieving two orders-of-magnitude gains in energy-delay product compared to CPU solvers. Another study demonstrated the applications of SNN in optical flow estimation for event cameras [33] , which showed significant potential for real-time operations. In addition, SNNs have been applied to depth estimation for event sensors [10] , where their method computed the optical flow on the neuromorphic chip and integrated the optical flow with camera velocity to estimate depth.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: Sec. 6 discusses the limitations of the work (see L1 to L4). Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
preliminaries: 
 An SNN can be viewed as a "program" for a neuromorphic computer [34] . Formally, an SNN comprises a set of spiking neurons N = {n i } N i=1 and synapses, where each synapse connects a pair of neurons. The interconnections can be summarized by a matrix W = [w ij ] ∈ Z N ×N , where the element w ij indicates the strength of connection between n i and n j , and w ij = 0 signifies an absence of connection between the pair. The architecture of an SNN and the model of the spiking neuron define the behavior of the program. Here, we describe the NEBM spiking neuron model (Sec. 3.1) and the NEBM-based SNN for QUBO (Sec. 3.2) [32] .NEBM neurons produce outputs probabilistically based on the Boltzmann distribution [32] . An NEBM neuron n i contains a binary state s i ∈ {0, 1} that indicates whether the neuron is firing (s i = 1) or not (s i = 0), and an internal state u i ∈ Z that accumulates outputs from connected neurons.While in theory spiking neurons operate asynchronously, practical neuromorphic computers such as Intel Loihi are fully digital devices [12] . The continuous time dynamics of a spiking neuron are approximated using fixed-size discrete timesteps t. It should be reminded that t relates to the algorithmic time of the computation rather than the time of a global synchronous clock.Based on the algorithmic time formalism, at timestep t, an NEBM neuron n i accumulates inputs from connected neurons into its internal stateEQUATIONwhere ∆s(t-1) jis the output spike of neuron n j from the previous timestep. The internal state of n i is then converted to a switching probability P sEQUATION)where T is the temperature. If the switching probability ( 11) exceeds a randomly generated thresholdθ i ∈ [0, 1], s i is set to 1.From here, an output or delta spike is calculatedEQUATION)If ∆s(t)i takes a non-zero value, i.e., the state s i changes from the previous timestep, n i propagates a delta spike to all its connected neurons and enters a refractory period for r i timesteps. Within the refractory period, the binary state s i remains unchanged. Note that temperature T and length of the refractory period r i are hyperparameters of NEBM neurons. For more details of NEBM, its hyperparameters and how it is implemented on Loihi 2 given hardware constraints (i.e. no division operator), we refer readers to [32] .The energy encoded by the neuronal states in an SNN isEQUATIONFollowing [32] , the NEBM-based SNN algorithm to minimize the energy is summarized in Alg. 2 (see Appendix). Intuitively, the method repeatedly samples and explores the neuronal states guided by the structure of the synapses and evolving state values [21] . The algorithm is executed on the neuromorphic hardware for M algorithmic timesteps, and the state configurations probed at the M timesteps are returned. The state configurations are evaluated off-chip, with the best one returned as the solution. Note that we employ an early version of NEBM where T is kept constant in Alg. 2, though T can be annealed to fine-tune the search. We refer interested readers to [32] for recent advancements of NEBM and NEBM-based QUBO solver.To enable Alg. 2 to solve QUBO, following [32] , we perform the following mapping:• Assign each binary variable z i to a neuron n i , and equating the state s i with the value of z i .• Associate the quadratic coefficients Q = [q ij ] ∈ Z N ×N with the synapse weights W, i.e., Q = W. This also implies the existence of self connections for the neurons, where q ii = w ii is the strength of the self connection for neuron n i .Fig. 1b illustrates the mapping. Note that the "mapping" does not imply that E equates to the QUBO cost; rather, the minimization of E by Alg. 2 tends to lead to the minimization of the QUBO cost. In this sense, the SNN is a heuristic method to solve QUBO.4 Slack-free SNN formulation for HMVC Instead of converting HMVC to QUBO following the derivations in Problem 2 and applying the SNN described in Sec. 3.2, we develop a novel slack-free SNN that directly solves HMVC. Referring to the 0-1 ILP (6), we construct our SNN, named SF-HMVC, as follows:• As before, each binary variable z i is encoded as the state s i of an NEBM neuron n i .• Each k-th constraint b (k) T z ≥ 1 is represented by a neuron m k , whose dynamics are governed by a custom neuron model called feedback or FB (more details below).Algorithm 1 Our proposed SF-HMVC (note: the algorithm is executed for each NEBM neuron n i and FB neuron m k on the neuromorphic hardware in a parallel way; see [13] for details).Require: Co-occurrence matrix F, adjacency matrix A, temp. T and refract. period r i . 1: Initialize s(0) i ← 0, ∆s (0) i ← 0, u (0) i ← -f ii , refract_counter (0) i ← 0 2: for each timestep t do 3: u (t) i ← u (t-1) i + N j̸ =i f ij ∆s (t-1) j + K k=1 a ik ∆c (t-1) k 4: p (t) i ← 1 1 + exp(u (t) i /T ) 5: θ i ← rand(0, 1) 6:if neuron n i is not in refractory period then 7: if p (t) i ≥ θ i then 8: s (t) i ← 1 9:s (t) i ← s (t-1) i 13: refract_counter (t) i ← max(refract_counter (t-1) i -1, 0) 14: ∆s (t) i ← s (t) i -s (t-EQUATIONk ← -1EQUATIONk ← 1 EQUATIONwhere 0 K×K is a K × K matrix of zeros,-A = [b (1) • • • b (K) ] ∈ {0, 1}N ×K is the adjacency matrix between NEBM and FB neurons (intuitively, the k-th FB neuron m k is connected to the NEBM neurons corresponding to z i 's that appear in the k-th constraint); and-F = [f ij ] = AA T ∈ Z N ×Nis the co-occurrence matrix of the NEBM neurons (intuitively, f ij is high if z i and z j appear frequently together in the constraints, while f ii is high if z i appear in many constraints).Fig. 1c illustrates the proposed SNN construction, while Alg. 1 summarizes the associated algorithm.Note that Alg. 1 involves two types of neurons that implement different dynamics, and the neurons are executed in parallel on the neuromorphic hardware [13] . The internal state for m k isv (t) k = N i=1 a ik s (t) i (15)where a ik is the element of i-th row and k-th column of matrix A. An FB neuron m k is deterministically activated (i.e., its binary state c k becomes 1) whenever the connected NEBM neurons are all inactive (i.e., v k = 0), and vice versa. Then, a negative spike ∆c k is generated if the value of c k is 1, so as to send excitatory signals to the connected NEMB neurons to attempt to satisfy the constraint; otherwise no spikes are generated. The point here is not to over-excite NEBM neurons. Then, the internal state of an NEBM neuron n i accumulates inhibitory signals from the connected NEBM neurons and excitatory signals from the connected FB neurons, i.e.,EQUATION)Similar to Alg. 2, Alg. 1 is executed on the neuromorphic hardware for M algorithmic timesteps, and the best state configuration probed and evaluated off-chip is taken as the solution. Note that the probing mechanism incurs significant overhead in the execution time of current implementation [10] , and an on-chip evaluation strategy could be implemented to address this bottleneck [24, 32] .Based on the construction of the QUBO-based SNN and the proposed SF-HMVC, we can model the number of spiking neurons required to encode each SNN:• n neurons (QUBO) = N + (r -1)K • n neurons (SF-HMVC) = N + KAs N, K and r collectively define the size of the input problem, we can conclude that SF-HMVC scales linearly whereas the QUBO-based SNN scales quadratically with respect to the problem size.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments: 
 Implementation Our method SF-HMVC was implemented on the Loihi assembly language through Lava framework [2] and deployed on the neuromorphic chip of Intel Loihi 2 [30] with M = 1000 algorithmic timesteps (denoted as SF-HMVC-Loihi). Using grid search, we selected temperature T from the range [2, 4, 8, 16, 24, 32] , refractory period r i from the range [8, 16, 32, 64, 128] (note that all NEBM neurons were given the same refractory period). We set λ = 2 for QUBO ( 4) (same as [11] ) and grid search λ = [1, 10, 100, 1000] for QUBO ( 9) . Note that we were unable to change the seed of the random number generator on Intel Loihi 2, which prevented us from repeatedly executing SNNs to obtain error bars in the solution quality. Also, we noticed that energy consumption and runtime of our method and all competitors remained fairly consistent across different runs.Dataset We employed the DIMACS benchmark dataset [20] . DIMACS includes graph instances that are both synthetically generated and sourced from real-world applications, including coding theory, fault diagnosis, Keller's conjecture, etc. The original DIMACS graphs were for maximum clique problems; we converted these to MVC instances by taking the complement graphs. Only 15 MVC instances where the corresponding SNN for SF-HMVC could fit on Loihi 2 were selected.Competitors SF-HMVC-Loihi was compared to the following methods:• ILP-CPU: MVC was solved using the ILP (3) with Gurobi [18] and evaluated on CPU.• QUBO-CPU: MVC was solved using QUBO (4) with Gurobi [18] and evaluated on CPU. We set λ = 2 (same as [11] ). • QUBO-Loihi: MVC was solved using QUBO (4) with NEBM-based SNN (see Sec. 3.2) and evaluated on Intel Loihi 2. We set T = 16, r i = 64, λ = 2. All hyperparameters of the competitors were selected using grid search. The configuration that demonstrated consistent performance across all problem instances was selected for each method. For SF-HMVC-Loihi, we set T = 4, r i = 8.Metrics Solution quality, runtime (in seconds), and energy consumption (in Joules) were reported for all methods. Runtime and energy consumption on Intel Loihi 2's Oheo Gulch board were measured through the built-in profiler of Lava-Loihi v0.6.0 extension. Runtime on CPU was recorded using built-in functions of Gurobi and the energy usage was recorded using pyJoules [4] on a workstation with an Intel Core i7-11700K CPU @ 3.6GHz and 32GB RAM running Ubuntu 20.04.6 LTS.Tabs. 1 and 2 display the results. Overall, SF-HMVC-Loihi was comparable to QUBO-Loihi in all three aspects: solution quality, runtime, and energy usage (the discrepancy between them will be clearer in the next experiment). ILP-CPU and QUBO-CPU outperformed SF-HMVC-Loihi in terms of solution quality (see Tab. 1), since both ILP-CPU and QUBO-CPU were globally optimal methods. The equal solution quality of the global methods also indicated the existence of a suitable penalty weight for QUBO (4) in the grid search range of λ. On runtime (see Tab. 2), though ILP-CPU and QUBO-CPU solved many instances in under 1 s, a few instances took them minutes to hours to solve. In contrast, SF-HMVC-Loihi consistently solved all instances within 10 s. Also, on energy usage, our method significantly outperformed ILP-CPU and QUBO-CPU. Dataset We generated 11 synthetic HMVC instances as follows: first, a set of N vertices V were created, then a set of K degree-r hyperedges F were randomly generated. The values of N , K and r were selected to ensure that the SNN (for SF-HMVC) could fit on Loihi 2.Competitors SF-HMVC-Loihi was compared to the following methods:• ILP-CPU: HMVC was solved using the ILP Eq. ( 6) with Gurobi [18] and evaluated on CPU.• QUBO-CPU: HMVC was solved using QUBO Eq. ( 9) with Gurobi [18] and evaluated on CPU. We set λ = 10. • QUBO-Loihi: HMVC was solved using QUBO Eq. ( 9) with NEBM-based SNN (see Sec. 3.2) and evaluated on Intel Loihi 2 [30] . We set T = 32, r i = 8, λ = 10.All hyperparameters of these competitors were selected using grid search. The configuration that demonstrated consistent performance across all problem instances was selected for each method. For SF-HMVC-Loihi, we set T = 8, r i = 8.Tabs. 3 and 4 display the results. As expected, ILP-CPU outperformed SF-HMVC-Loihi in solution quality, since ILP-CPU was a global method. Interestingly, our method occasionally found better solutions than QUBO-CPU. This was probably because, as the problem difficulty (number of variables) increases, it became more challenging for QUBO-CPU. Note that SF-HMVC-Loihi handled all instances reasonably well. In contrast, QUBO-Loihi either could not find feasible solutions, or correspoding SNN could not be embedded onto Loihi 2. This suggests that the introduction of slack variables in QUBO-Loihi made the search space and/or problem size too large.As presented in Table 4 , while ILP-CPU performed better than SF-HMVC-Loihi in terms of runtime, our method was more efficient in terms of energy consumption. Furthermore, our method significantly surpassed QUBO-CPU and QUBO-Loihi in both runtime and energy efficiency. 
limitations and conclusions: 
 Several limitations of our work can be identified:L1: The capacity of the neuromorphic computer available to us (a single Intel Loihi 2 chip [30] which has 128 neuromorphic cores) was relatively low, which prevented testing of large problem instances. L2: There is a lack of public benchmarks on HMVC problems. L1 and L2 together precluded an assessment of the generalizability of the methods more practical problem instances. L3: Changing the seed of the random number generator on Intel Loihi 2 was inaccessible to us, which precluded error bars in solution quality. Despite the limitations above, the results showed clear trends of the greater scalability of the proposed method SF-HMVC, in that it was able to solve HMVC problem instances where the existing method could not. Moreover, SF-HMVC on Loihi 2 exhibited measurably lower energy consumption than global solvers on CPU, further supporting neuromorphic computing as an energy-efficient alternative. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: Please refer to Sec. 5 for details.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We have reviewed and followed the Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA]Justification: The paper focuses on combinatorial optimization at the fundamental level, which does not have immediate societal impacts.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: High risk data or models are not involved in this research.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 
licenses for existing assets: 
 Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We have properly referenced all relevant data, code and papers.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [Yes] Justification: We have provided the pseudo code of the algorithm and all implementation details of the method. Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Algorithm 2 NEBM-based SNN for energy minimization (note: the algorithm is executed for each neuron n i on the neuromorphic hardware in a parallel way; see [13] for details).Require: Weight matrix W, temperature T and length of refractory period r i . 1: Initialize sEQUATIONEQUATIONEQUATION← 0 2: for each timestep t do 3:u (t) i ← u (t-1) i + N j̸ =i w ij ∆s (t-1) j 4: p (t) i ← 1 1 + exp(u (t) i /T ) 5: θ i ← rand(0, 1) 6:if neuron n i is not in refractory period then 7: if p (t) i ≥ θ i then 8: s (t) i ← 1 9:s (t) i ← s (t-1) i 13: refract_counter (t) i ← max(refract_counter (t-1) i -1, 0) 14: ∆s (t) i ← s (t) i -s (t-1) i 15: send ∆s (t) i to connected neurons 16: if ∆s (t) i ̸ = 0 then 17:neuron n i enters refractory period 18:refract_counter (t) i ← r i NeurIPS Paper Checklist 1.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: A novel SNN is introduced to solve HMVC. The derivation in Sec. 4 show the proposed SNN does not require new slack variables, as claimed in the abstract and introduction. The experimental results align with the claims that the proposed SNN consistently yields high quality solutions on synthetic and real HMVC instances where the established method mostly fails (to reach feasibility), and that the proposed SNN measurably consumed less energy on the neurmorphic hardware than the CPU solution.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: The paper presents a novel method for solving the Hypergraph Minimum Vertex Cover (HMVC) problem using Spiking Neural Networks on neuromorphic hardware. This method enables the neuromorphic system to solve small instances of the HMVC problem more effectively than previous methods, consuming less energy than traditional optimization techniques.

All reviewers agree that this paper presents a significant advance and vote for acceptance.

Reviews: review: paper_summary: paper_summary: The paper presents a method that solves a specific type of problem of combinatorial optimization (hypergraph minimum vertex cover) through spiking neural networks. The method, tested on small versions of the problem, enables a neuromorphic hardware system made by Intel to arrive at a result in cases where previous methods did not, and with less energy consumption than certain other methods if they are ran on CPU.
strength_weakness: strength_weakness: On the other hand, the paper has several weaknesses.

1. The paper does not make clear how significant the type of problem addressed here (HMVC) is, and why it is significant.

2. A figure illustrating an example toy problem of HMVC as well as its solution in the QUBO-based SNN and in the newly proposed method would be very helfpul in clarifying the paper's contribution.

3. The literature review around neuromorphic hardware is rather narrow, and largely focuses on Loihi alone. For example, even narrowly focusing on hardware for Ising models, here is a review of various implementations that could be cited: https://www.nature.com/articles/s42254-022-00440-8

4. Section 2 cites works where SNNs have performed well, but only does this for tasks outside of machine learning. For machine learning there is only a pointer to a survey, which is related to Loihi again, and again focuses largely beyond machine learning. This should be mitigated, especially because in reality, machine learning is arguably the more popular application of SNNs, and spiking machine learning models have in fact outperformed non-spiking ones concretely and under fair hardware conditions in certain cases. Here are the two examples that I am aware of: https://arxiv.org/abs/2009.06808 (under certain temporal dynamics SNNs were shown to be theoretically optimal and practically surpassed ANNs in accuracy) and https://openreview.net/forum?id=iMH1e5k7n3LI (spikes improved inference speed without accuracy drops, and even on GPUs).

5. Most importantly, I believe that the paper's contribution to the broader field of Neural Networks might not be significant, for the following reasons.

- 5a. The work is specifically related to SNNs alone, and specifically related to their use for combinatorial optimization and even more narrowly, specifically HMVC. That is a rather niche scenario.
- 5b. The results are on rather small scale demonstrations.
- 5c. It is unclear that there is any advantage from the neuromorphic aspect. Specifically, the presented heuristic-based algorithm (or a suitable adaptation) has not been tested on CPU. It seems that in the same way that previous SNN approaches were comparable to QUBO and could thus be run on CPU, there must be an analog of the new method that can also be tested on CPU, and might be more energy efficient than Loihi. After all, QUBO on CPU is more efficient than QUBO on Loihi, as the paper shows. Similarly, is QUBO on CPU the baseline to beat to claim a neuromorphic advantage, or should it be eg a microcontroller or an FPGA?

6. The authors mention that they could not change the random seed to obtain statistics. For a stochastic algorithm like the one presented, this seems rather important. Could this be mitigated, eg by running the algorithm on CPU and obtaining some statistics there?
questions: questions: Could the authors address the above points?

Is there an intuitive explanation why QUBO on Loihi is less efficient than on CPU, and does this explanation not apply to the authors' new approach?

Why can't the random seed be changed?
limitations: limitations: Some of the limitations mentioned in this review are mentioned in the paper, but not all.
paper_summary: paper_summary: The paper presents a novel approach to solving the Hypergraph Minimum Vertex Cover (HMVC) problem using Spiking Neural Networks (SNNs) on neuromorphic hardware, which is a significant contribution to the field of combinatorial optimization in neuromorphic computing. Here's a detailed review based on various aspects of the paper:
strength_weakness: strength_weakness: * The comparison is mainly limited to traditional SNN-based QUBO solvers. Including comparisons with other contemporary optimization techniques, especially those that are non-neuromorphic, could provide a clearer benchmarking against the state-of-the-art in broader combinatorial optimization research.
* While the paper claims improved energy efficiency, detailed metrics or comparative energy consumption data are lacking. Providing explicit energy consumption figures or a more detailed analysis could help substantiate these claims and compare them with other methods' energy profiles.
* Although the paper discusses the potential scalability of the approach, there is limited empirical evidence supporting this claim, especially in terms of larger and more complex problem instances. Detailed scalability analysis, possibly through theoretical modeling or additional experiments, would be beneficial.
* The effectiveness of the proposed method is closely tied to the availability and performance of specific neuromorphic hardware. This dependency could limit its accessibility and practicality, especially in environments where such hardware is not readily available or is cost-prohibitive.
questions: questions: * Are there any more dataset available for benchmarking?
* What measures have been taken to prevent overfitting in the model during the experimental phase?
* Are there any scalability concerns when applying this method to larger or more complex problem sets?
limitations: limitations: limitations are discussed in the paper
paper_summary: paper_summary: This paper presents a novel approach to solving the Hypergraph Minimum Vertex Cover (HMVC) problem using spiking neural networks (SNNs). The authors introduce a slack-free formulation (SF-HMVC) that directly translates the constraints of the HMVC problem into the dynamics of SNN neurons, specifically targeting implementation on neuromorphic hardware such as Intel's Loihi 2. The paper demonstrates that the proposed method can effectively solve HMVC problems and provides a comparative analysis with other optimization techniques, such as Integer Linear Programming (ILP) and Quadratic Unconstrained Binary Optimization (QUBO).
strength_weakness: strength_weakness: 1. Algorithm 1 is not the algorithm proposed in the article, yet it occupies a significant portion of the paper. It is recommended to move it to the appendix.

2. Could the authors provide a more detailed explanation of the setup and motivation for the W matrix, such as how the A matrix and F matrix are configured?

3. The experiments are influenced by many hyperparameters, such as $\lambda$ and timestep $T$. It is recommended to conduct appropriate ablation experiments.
questions: questions: Please see weakness.
limitations: limitations: The authors raise some limitaions, for example, the capacity of the Loihi 2 is low, which is limited by the development of hardware.
paper_summary: paper_summary: Traditional SNN methods for combinatorial optimization necessitate the use of penalty terms with slack variables to maintain feasibility constraints. The paper introduces a novel Spiking Neural Network (SNN) formulation designed to solve the Hypergraph Minimum Vertex Cover (HMVC) problem without requiring slack variables. The proposed SF-HMVC replaces slack variables with additional spiking neurons that check and correct constraints, facilitating convergence to feasible solutions.
strength_weakness: strength_weakness: 1. The scale of experiments are relatively small and simple.
2. Lack of comparison with other solving methods, e.g. Gurobi and D-Wave.
3. There are some typos. E.g. in line 102, *whot* -> *who*.
questions: questions: 1. How scalable is the proposed SNN method with future advancements in neuromorphic hardware?
2. Can the approach be generalized to other combinatorial optimization problems beyond HMVC?
limitations: limitations: 1. The neuromorphic hardware capacity is currently limited, restricting the scale of problem instances that can be tested.
2. There is a lack of public HMVC benchmarks, complicating the evaluation of the method's generalizability.

Comments: title: Response to the authors
comment: I would like to thank the authors for their responses. My concerns and lack of clarity have been largely addressed, and I found the paper interesting and potentially impactful. I am raising my score.
Dear authors,

Thanks for your rebuttal. I think the authors addressed my questions and I appreciate the supplemented experiments. So I increase my confidence score.
As outlined in the abstract, our **claimed contribution** is a scalable handcrafted SNN called SF-HMVC for solving HMVC on neuromorphic computers. The claim was justified via scalability analysis and experiments on Loihi 2 that compared SF-HMVC against the previous QUBO-based SNN. The results on Loihi 2 also showed that SF-HMVC was more *energy-efficient* than the CPU solutions.

It seems Que6's Official Comments were mainly focused on *hardware efficiency*; based on the comments, this can roughly be understood as the "amount" of hardware resources required per "unit problem size".

It is debatable if basic metrics such as number of cores and transistors are meaningful for predicting the relative hardware efficiencies of processors with fundamentally different architectures (von Neumann versus neuromorphic) and characteristics [31], e.g., CPU cores focus on computation while neuromorphic cores integrate computation and memory.

In any case, the veracity of our **claimed contribution** does not strongly depend on the hardware efficiency of Loihi 2 relative to other neuromorphic implementations or CPU. Specifically,
- Due to our slack-free formulation, SF-HMVC will provably consume less hardware resources than QUBO-SNN on a neuromorphic computer, be it Loihi or other neuromorphic implementations that have higher hardware efficiency than Loihi.
- Even if neuromorphic computing is fundamentally less hardware-efficient than the CPU, our results present clear evidence of the superior *energy efficiency* of SF-HMVC compared to the CPU solutions, which is a major benefit for applications where energy efficiency is paramount.

Responding to Que6's questions:
- An SNN allocates one neuron to handle a specific variable in the input problem. Thus, the maximum problem size that an SNN can solve is limited by the number of neurons that a neuromorphic computer can support. The limit on HMVC size that is solvable on Loihi 2 is thus due to limitations in the hardware implementation, and not due to a fundamental weakness of neuromorphic computing.
- SF-HMVC is an SNN that we designed to operate on Loihi 2. We have added results that show that the simulation of SF-HMVC on CPU consumed several orders of magnitude more energy than SF-HMVC on Loihi 2. This at least shows that SF-HMVC could benefit from intrinsic neuromorphic processing in a way that its direct CPU simulation could not.
- Note that there are CPU algorithms for solving HMVC that does not require QUBO reformulation and/or additional slack variables. The baseline method ILP-CPU which solves HMVC as integer linear programming using the Gurobi software is one such method (see Sec. 5.1 **Competitors**). ILP-CPU was capable of solving all the HMVC instances in our experiments, thus, arguably ILP-CPU is at least as "hardware-efficient" on the CPU as SF-HMVC is on Loihi 2. However, our results in Tables 3 and 4 show that ILP-CPU was *less energy-efficient* than SF-HMVC-Loihi.

   It is possible that there exists a CPU analog of SF-HMVC that is more hardware-efficient on CPU than SF-HMVC is on Loihi 2, however, without providing sufficient details (e.g., pseudocode), it is not possible to prove or disprove the reviewer's claim/suspicion. More importantly, it is unknown if the CPU analog will be more *energy-efficient* than SF-HMVC-Loihi.
I would like to thank the authors for their response.
It is helpful. However, some important parts remain partly unclear.

My understanding that QUBO on Loihi is less efficient than on CPU was based on the fact that except for its smallest versions, the problem did not fit on Loihi.
The Loihi 2 board that was used, as far as I understand, has 128 cores, whereas the compared Intel Core i7-11700K CPU has only 8. Also, both chips have about the same number of transistors. This seems to be a type of inefficiency on the Loihi side.

Based on this context, I will rephrase and expand on some of my previous questions that I found to be only partly addressed by the authors.

- What causes this hardware inefficiency? In other words, what is Loihi's hardware bottleneck for larger problems, be it with QUBO or with SF-HMVC, and is it a fundamental weakness of neuromorphic computing in general, or rather of the specific implementation that is Loihi?
- Is there a fundamental reason why SF-HMVC cannot have an analogue that would work on CPU? Essentially, is there a neuromorphic principle that is exploited for this approach but cannot be used with CPUs?
- I suspect that a hypothetical SF-HMVC-CPU implementation would not only be more efficient than QUBO (CPU or Loihi), but would also allow for larger problems with fewer hardware resources than SF-HMVC-Loihi. This suspicion is based on the comparison between QUBO-CPU and QUBO-Loihi. Is this suspicion wrong, and, if so, why?
Thanks for authors' rebuttal!

Overall I believe this is a technically solid work and I'm keeping my original rating with increased confidence.