Slack-Free Spiking Neural Network Formulation for Hypergraph Minimum Vertex Cover
Authors: Tam Ngoc-Bang Nguyen
Anh-Dzung Doan
zhipeng cai
Tat-Jun Chin
Venue: NeurIPS 2024 poster (2024)
Keywords: Neuromorphic computing
spiking neural network
hypergraph minimum vertex cover
Primary area: optimization
TL;DR: We developed a novel SNN for hypergraph minimum vertex cover.

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.

Slack-Free Spiking Neural Network Formulation for Hypergraph Minimum Vertex Cover
Tam Ngoc-Bang Nguyen', Anh-Dzung Doan', Zhipeng Caf', Tat-Jun Chin Australian Institute for Machine Learning, The University of Adelaide,
Intel Labs
(tam. nguyen, doan, tat jutt-jun.o cuin.c.innaaaeeeeeeeeeeeeeee Gadeladde edu au zhipeng cai mai@intel.com com
Abstract
Neuromorphic computers open up the potential of 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 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 effective- ness of the SNN solver. In this paper, we propose 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 neuromor-
computation
obviates the need for reformulating HMVC as QUBO. Experiments phic 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.
Introduction
Neuromorphic computing research aims to develop computational models inspired by neural archi- tectures found in nature. Spiking neural networks (SNN), in which network of processing units (neurons) asynchronously transmit spike-based messages to each other (34], is a notable representa- tive of the neuromorphic paradigm. Through parallelism, stochastic behavior, event-driven computing and other biologically-inspinn 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 delivering energy efficient computations, which not only benefit edge computing applications, but also reducing the energy consumption of data cen- ters. The recent introduction of Intel Hala Point I. 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
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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)
min z QZ. (0,1)_
where Q E ZNX 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 solve QUBO 6 14 32]: Sec. S.c. will describe such a method. To bring such SNNs to bear on other combinatorial problems, the problems must first be reformulated into QUBO [1 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 (Minimum vertex cover (MVC)). Let G (V, E) be graph with vertices V {L...., ] and edges E = {ei,..... eg}, where each e (((*),(()) C V connects two vertices. vertex cover of is a subset Z of V such that every edge is incident with at least a vertex Z. The goal of MVC is to find the vertex cover with the smallest number of vertices. Let
z = [....... =N|" E 1)
(2)
be a binary vector whose role is to select a subset of V. where 2, 1 indicates that the i-th vertex is selected, and 24 = 0 means otherwise. MVC can be expressed as
min 2E(U.1} N
||
s.t.
(1- - 2,00 (1 - =)(0) = 0, 4k- = I,..,, K.
Note that ||z|| ||/|2 for binary and the equality constraints in (3) are quadratic in Rewriting the equality constraints as penalty terms, we obtain the QUBO
K
min (0.1
21(0) )(1 22(4)).
(4)
k=1
Intuitively, solutions z that violate the constraints in 3 will raise the total cost in (4) and hence be penalized. The quantity X E 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 (T) due the existence of
constant, the remaining steps to rearrange (4) to ① are minor; see supplementary material.
O
Problem (Hypergraph minimum vertex cover (HMVC)). Let H = (V. F) be an r-uniform hypergraph with vertices V = {1, . N} and hyperedges F {fi (J fx), where each f& V is incident with exactly r vertices, r 2 2. A vertex cover of H is subset Z of V such that every hyperedge is incident with at least vertex in Z. The goal of HMVC
find the vertex cover with the smallest number of vertices. Note that HMVC reduces to MVC if = 2. For each hyperedge fs. define a binary vector
b (k)
(k) b
DTT 10,
where (+) 1 HMVC can then be written as
r. and ((() means that vertex is incident to fú and (R40) means otherwise.
min *E 10
||z||
(6)
s.t.
b
(1))
z 1,
=k=,.... K.
which is 0-1 integer linear program (ILP). Since variables (r 2 2) exist in each linear inequality constraint, in general it is not possible to express it as a quadratic equality constraint, of. (3). Instead, the path to QUBO will involve converting each inequality into an equality constraint
b (T) z 1 1k) 1,
2

---

which requires introducing r' binary slack variables for each fx
y ( = lui ,r.., IT E {0,1}"
(8)
where r' = -1 and 1, is a column vector of 1 of size r'. Installing the equality constraints as quadratic penalty terms, we obtain the QUBO
K
min (E,0,1) Ay TE -/0,1
1
+ A Σ
(b(0)²
2 1, -
(9)
k=1
where À E Z is the penalty weight. See supp. material for rewriting the QUBO in form
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 of hyperedges. This significantly increases the search space and difficulty of the optimization. As we will show in Sec. the existing SNN-based QUBO solver (3] is unable to satisfactorily solve HMVC based on ( This presents an obstacle towards applying SNNs to a combinatorial problem with many practical applications, e.g., computational biology [9]. computer network security [9], resource allocation
and social network analysis [23]. Fundamentally, HMVC is general optimization problem that
encompasses several related formulations, such as set cover, hitting set, and traversal [5] giving
wide applicability. The issue calls for a more effective SNN for HMVC.
1.1 Contributions
To solve HMVC more effectively, we propose an SNN that is composed of a mix of non-equillee -quiluiiii 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 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
36). However, such works have mainly been targeted constraint satisfaction problems, whereas SNN is aimed at a graph-based optimization problem, i.e., HMVC (more details in Sec. 2
2 Related work
Previous studies have shown that an SNN with topology corresponding to the matrix Q can efficiently solve QUBO 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 D has discussed this for MVC, which has been evaluated on neuromorphic processor 11I Other works that employed QUBŌ reformulation include [32 22 who solved maximum independent set and II.. However, more complex problems will require the introduction of slack variables, which increases the scarch space and difficulty for an SNN solution. Problem has illustrated this for HMVC.
The majority of handcrafted SNNs for combinatorial optimization aim solve constraint satisfaction problems (CSPs). Jonke et al. (21) proposed stochastic SNN for traveling salesman problem. Since then, several SNN solvers have been proposed for CSPs, such as, Sudoku BI. graph coloring [17]. and Boolean satisfiability problem [21] 36]. These existing approaches share 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. other words, the primary objective of these handcrafted SNNs to find feasible solutions to the combinatorial optimization problem. Although our approach shares similar spirit
3

---

m2
3TH
n
(a) Vertices
V
(1,2,3, 4).
hyperedges
f1
(1,2,3).fz
[1,3,4), fa (1,
(b) QUBO-SNN
(c) SF-HMVC
Figure 1: (a) HMVC input hypergraph: 3-uniform hypergraph with vertices and hyperedges. (b) SNN for QUBO (9) derived from (a). Both the variables and introduced slack variables are NEBM neurons. The edge weights are omitted for brevity. (c) The SNN from our method for input (a). NEBM and FB neurons are in orange and green resp. Dashed circles indicate self-connections.
to these handcrafted SNNs in that we directly construct SNN topology using constraints, our SNN topological graph specifically designed to seek not only a feasible solution but also optimal one.
The QUBO formulation is amenable to Ssig-sspeiffi analog and digital hardware solvers, including spintronics, memristors, and quantum annealers 277 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 its high flexibility in SNN design and programmable neuron model. For comprehensive overview of Loihi 2's capabilities, we refer readers to 224 32 35
There is large body of work on SNNs for machine learning; we refer to [3 for thorough survey. While SNNs are usually less accurate than ANNs (28). under certain temporal dynamics,
SNNs surpass ANNs. SNNs have also been used for roboties. For instance, 24 implemented their SNN-based quadratic programming solver for model predictive control on Loihi 2, achieving two ceders-of-magnitee 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 estimate depth.
3 Preliminaries
An SNN can be viewed as "program" for neuromorphic computer 34 Formally, an SNN
comprises a set of spiking neurons A' {n and synapses, where each synapse connects a pair of neurons. The interconnections can be summarized by a matrix W = [w,]] E Z.NxN, where the element wij indicates the strength of connection between and ntj, and w.j = 0 signifies absence of connection between the pair. The architecture of an SNN and the model the spiking neuron define the behavior of the program. Here, describe the NEBM spiking neuron model (Sec. 3.1 and the NEBM- based SNN for QUBO (Sec. adapted from Intel's original implementation
3.1 NEBM
NEBM neurons produce outputs probabilistically based on the Boltzmann distribution [32]. An NEBM neuron n, contains a binary state E {0, 1} that indicates whether the neuron is firing (s; = or not (s; = 0), and an internal state u; E Z that accumulates outputs from connected neurons.
While theory spiking neurons operate asynchronously, practical neuromorphic computers such as Intel Loihi are fully digital devices [2]. The continuous time dynamics of a spiking neuron are approximated using fixed-size discrete timesteps should be reminded that & relates to the algorithmic time of the computation rather than the time of global synchronous clock.

---

Based on the algorithmic time formalism, at timestep E, an NEBM neuron Ry accumulates inputs from connected neurons into internal state
(t-1) 1)
Wiy As (t-1)
(10)
j
where ا the output spike of neuron n, from the previous timestep. The internal state of n. is then converted to a switching probability
p(0)
8 -
(11)
1+ e
where T is the lemperature. If the switching probability 11 exceeds randomly generated threshold 0. E [0, 1]. 83 is set to 1. From here, an output or delta spike is calculated
As
(t-1)
(12)
If As takes a non-zero value, i.e., the state changes from the previous timestep, n, propagates a delta spike to all its connected neurons and enters a refractory period for r; timesteps. Within the refractory period, the binary state 8; remains unchanged. Note that temperature T and length of the refractory period r; are hyperparameters of NEBM neurons. For more details of NEBM, its hyperparameters and how it is implemented on Loihi 2 given hardware constraints (i.c. division operator), we refer readers to
3.2 NEBM-based SNN for QUBO
The energy encoded by the neuronal states in an SNN
N
=
S
(13)
Following 32]. the NEBM-basel SNN algorithm to minimize the energy is summarized in Alg. (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 the neuromorphic hardware for M algorithmic timesteps, and the state configurations probed at the M timesteps returned. The state configurations as the solution. Note that we employ an early version of NEBM where is kept constant in Alg. 2 though T can be annealed fine-tune the search. We refer interested readers to 322 for recent advancements of NEBM and the general-purpose NEBM-based QUBO solver.
evaluated off-chip, with the best returned
To enable Alg. 2 to solve QUBO, following 32). perform the following mapping:
Assign each binary variable 2; to neuron 74, and equating the state s; with the value of 24.
Associate the quadratic coefficients Q = [ay] E NNN with the synapse weights W, i.e., Q = W.
This also implies the existence of self connections for the neurons, where qü of the self connection for neuron 72.-
is the strength
Fig. Ib illustrates the mapping. Note that the "mapping" does not imply that & equates to the QUBO cost; rather, the minimization of & by Alg. 2 tends 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 novel slack-free SNN that directly solves HMVC. Referring to the 0-1 ILP (6) we construct our SNN, named SF SF-HMVC, follows:
before, each binary variable 2; is encoded as the state 8; of an NEBM neuron n,-
Each k-th constraint (*) is represented by a neuron my, whose dynamics are governed by custom neuron model called feedback or FB (more details below).
5

---

Algorithm Our proposed SF-HMVC (note: the algorithm is executed for each NEBM neuron n4
and FB neuron my on the neuromorphic hardware in a parallel way; see [T3] for details).
Require: Co-occurrence matrix F, adjacency matrix A, temp. T and refract. period r;
1: Initialize o + 0, As, t 0, u, (0)
(0)
t - füi, refract__ " 0
2: for each timestep do
N Σ
3:
(t- 1)
fig As
an (1-1) Ax
jth
k=1
4: Pl
exp(u /T)
5:
0g < rond(0,1
6:
if neuron n4 is not in refractory period then
7:
if Pt 2 8 then
8:
NEBM neuron
9:
else
11:
else
(t-1)
12:
refract counter max(refract_ (t-1) 1,0)
13:
I)
14:
15:
send As to connected neurons
16:
if As + 0 then
17:
neuron n, enters refractory period refract counter: (t)
18:
refractt_cunter, + r
Require: Adjacency matrix A.
1: for each timestep do
2:
a
3:
if
u
k
0 then
4:
+ 1,
A
FB neuron
5:
else
6:
if
then
(t) 0, Act (t) 0
7:
Ck
8:
else
(1) 0, A
9:
10:
send Ack k to connected neurons
The weight matrix of our SNN which consists of N + K neurons (s1...., 8N. ........ mx] is
W
AT
F
Ox*K E (((++))((++)),
A
(14)
where 0к* is K x K matrix of zeros.
= [b(1) [K] E [0, is the adjacency matrix between NEBM and FB neurons (intuitively, the k-th FB neuron my is connected to the NEBM neurons corresponding to 2, that appear in the k-thh constraint); and
F =F= [fy] = AAT E NxN is the co-occurrence matrix the NEBM neurons (intuitively, Súj is high if z; and zj appear frequently together in the constraints, while fa is high if z; appear in many constraints).
Fig. Ic illustrates the proposed SNN construction, while Alg. summarizes the associated algorithm.

---

Note that Alg. iivoolves two types of neurons that implement different dynamics, and the neurons are executed parallel on the neuromorphic hardware [3]
The internal state for my
(C)
0sk8;
(4)
(15)
where as is the element of i-th row and k-th column of matrix A. An FB neuron my is determin- istically activated (i.e., its binary state og becomes 1) whenever the connected NEBM neurons are all inactive (i.e.,
0), and vice versa. Then, negative spike Ac₃ is generated if the value of Ck 1, so as send excitatory signals to the connected NEMB neurons attempt to satisfy the constraint:
otherwise no spikes are generated. The point here is not to over-excite NEBM neurons. Then, the internal state an NEBM neuron n, accumulates inhibitory signals from the connected NEBM neurons and excitatory signals from the connected FB neurons, i.e.
N Σ j
K
(c) ui U
(L-1)
S (1-1) + Σ
(1-1)
(16)
Similar to Alg. 2 Alg. [ is executed on the neuromorphic hardware for M algorithmic timesteps, and the best state configuration probed and evaluated off-chip is taken the solution. Note that the probing mechanism incurs significant overhead the execution time of current implementation 10] and on-chip evaluation strategy could be implemented to address this bottleneck [24 32
Scalability analysis Based on the construction of the QUBO-based SNN and the proposed SF- HMVC, model the number of spiking neurons required to encode each SNN:
Necurons (QUBO) N + (r 1)K
Aegurons (SF = K
As N, and 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.
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 SF-HMVC-oohhi. Using grid search, we selected temperature T from the range [2, 4, 8, 16, 24, 32), refractory period from the range [8, 16. 32, 64, 128 (note that all NEBM neurons were given the same refractory period). We set X
for QUBO (same as 11I) and grid search X = [1, 10, 100, 1000] for QUBO Note that we were unable change the seed of the random number generator on Intel Loihi 2, which prevented us from repeatedly executing SNNs obtain error bars in the solution quality. Also, noticed that energy consumption and runtime of our method and all competitors remained fairly consistent across different runs.
5.1 MVC
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-HWVC-Loihi was compared to the following methods:
ILP-CPU: MVC was solved using the ILP ( with Gurobi [8] and evaluated on CPU.
QUBO-CPU: MVC was solved using QUBO with Gurobi [8 and evaluated on CPU, We set
À (same as (T]).
QUBD-Loihi: MVC was solved using QUBO with NEBM-based SNN (see Sec. 3.2 and evaluated on Intel Loihi 2. We set T 16, =
7

---

Table 1: Solution quality ||z||
the MVC methods for all DIMACS MVC instances.
ILP- CPU
QUBO- CPU
QUBO- Loihi
SF-HMVC-
Instance
[V]
E
Loihi
C125,9
125
787
91
91
122
116
C250.9
250
3141
206
206
239
240
gen200 Len200_p0.9.0000 44
200
1990
156
156
185
199
gen200_p0.. _t1___000....0 p0.9_55 _5
200
1990
145
145
187
191
hamming6-2
64
192
32
32
51
32
hamming6-4
64
1312
60
60
64
61
hamming8-2
256
1024
128
128
236
128
johnson8-2-44
28
168
24
24
28
24
johnson8-4-4
70
560
56
56
59
69
johnson16-244
120
1680
112
112
120
119
keller4
171
5100
160
160
171
170
MANN a9
45
72
29
29
38
37
MANN a27
378
702
252
252
352
324
san200_0.9_1
200
1990
130
130
178
199
sanr200_00 _09
200
2037
158
158
184
199
Table 2: Runtime (in seconds) and energy usage (in Joules) of MVC methods. Note that indicates that the energy was too high for pyJoules to measure.
ILP-CPU
QUBO-CPU
QUBO-Loite
SF HMVC-Loihi
Instance
Time
Energy
Time
Energy
Time
Energy
Time
Energy
0.05
C250.9
>3600
144380.55
>3600
36:
7.36
0.26
7.37
0.18
gen200 p0..
387.83
gen2000_mg 8on200_p0.99. 90.00_0_00._555
0.03
2.12
2.59
203.84
5.98
0.04
5,17
0.01
hamming6.2
0
0.07
0.01
0.46
2.09
0.02
1.84
0.06
hamming6-4
0.03
2.25
0.36
25
0.07
1.83
0.06
hamming8-2
0
0.19
0.03
1.53
7.64
0.04
7.55
0.04
johnson8-22
3.16
johnson8-44 4
0
0.15
0.26
18.83
2.26
0.02
1.99
0.05
johnson16-2-4
3.74
316.75
3.72
kellert
1.14
114.13
1628.92
185173.36
5.13
0.11
5,15
0.03
MANN a9
0
0.97
0.02
2.24
1.55
0.07
1.35
0.01
MANN a27
0.18
12.06
0.82
72.92
10.95
9.58
san200_0.9
0.01
0.87
0.27
22.70
5.99
0.25
5.28
0.04
0.9
77.92
20591.27
All hyperparameters of the competitors were selected using grid search. The configuration that demonstrated consistent performance across all problem instances selected for each method. For SF Loiiii we set T 4, 4,
Metrics Solution quality, runtime (in seconds), and energy consumption (in Joules) were reported for all methods. Runtime and energy consumption 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 workstation with an Intel Core 17-1K CPU @ 3.6GHz and 32GB RAM running Ubuntu 20.04.6 LTS.
Results Tabs. and 2 display the results. Overall, SF-HMVC-Loihi was comparable to QUBD-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 QUBD-CPU outperformed SF-HMVC-Loihi in terms of solution quality (see Tab. [T] since both ILP-CPU and QUBO-CPU were globally optimal methods. The equal solution quality of the global methods also indicated the existence of suitable penalty weight for QUBO 4 in the grid search range of X. runtime (see Tab. - though ILP-CPU and QUBO-CPU solved many instances in under
few instances took them minutes hours to solve. contrast, -FFHMVC-Loihi consistently solved instances within 10 Also, energy usage, method significantly outperformed ILP-CPU and QUBD-CPU,

---

Table Solution quality ||z||a of the HMVC methods for all synthetic HMVC instances. Infeasible solutions are indicated in red, with number of constraint violations in brackets. N/A means that the SNN was not able to be embedded into the Loihi 2 due to capacity limitations.
ILP-
QUBO-
QUBO-
4F-HMVC-
Instance
V
F
CPU
CPU
Loihi
Loihi
3-uniform HMVC01
30
981
3
3 (68)
3
3-uniform_HMVC022 HMVC02
30
2129
19 (1214)
E-uniform_HMVV HMVC03
30
2888
15
15
N/A
15
3-uniform HMVC04
30
3327
30
N/A
29
3-uniform HMVC05
50
3506
5
N/A
5
3-uniform HMVC06
50
6538
N/A
3-uniform _MVCO7
50
7333
10
50
N/A
10
3-uniform HMVC08
70
7326
N/A
3-uniform HMVC09
100
5979
20
20
N/A
20
3-uniform HMVC10
200
7430
10
10
N/A
19
4-uniform HMVCI1
30
4914
15
N/A
5
5.2 HMVC
Dataset We generated 11 synthetic HMVC instances as follows: first, a set of N vertices V were created, then a of K degree-r hyperedges E' were randomly generated. The values of N, K and were selected to ensure that the SNN (for SF-HMVC) could fit on Loihi 2.
Competitors SF-HMVC-Loihi
compared to the following methods:
ILP-CPU: HMVC was solved using the ILP Eq.
(6) with Gurobi [8] and evaluated on CPU,
QUBO-CPU: HMVC was solved using QUBO Eq. with Gurobi 18 and evaluated on CPU. We
À = 10.
with NEBM- SNN (see Sec. 3.2 and evaluated on Intel Loihi 2 B00. We set T = 32, = 8 10.
QUBD-Loihi: HMVC was solved using QUBO Eq.
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, set 7 8, 8.
Results Tabs. and display the results. As expected,
outperformed SF-HMVC-Loihi in global method. Interestingly, method occasionally found
solution quality, since ILP-CPU better solutions than QUBO-CPU. This was probably because, as the problem difficulty (number of variables) increases, it became all instances reasonably well. contrast, QUBO-Loihi either could not find feasible solutions, or correspoding SNN could not 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.
challenging for QUBO-CPU. Note that SF-HMVC-Loihe handled
As presented in Table 4 while ILP-CPU performed better than SF-HMVC-Lohhi 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 chip 33 which has 128 neuromorphic cores) was relatively low, which prevented testing of large problem instances.
L2: There a lack of public benchmarks on HMVC problems. LI and L.2 together precluded an assessment of the generalizability of the methods more practical problem instances.
L.:: Changing the seed of the random number generator on Intel Loihi was inaccessible to us, which precluded error bars in solution quality.

---

Table 4: Runtime (in seconds) and energy usage (in Joules) HMVC methods. Note that oc indicates that the energy was too high for pyJoules to measure, while N/A indicates the instance could not be embedded into Loihi 2 due to capacity limitations.
Instance
ILP-CPU
QUBO-CPU
QUBD-Loihi
3F-HMVC-Loihi
Time
Energy
Time
Energy
Time
Energy
Time
Energy
3 3-inffomm HIVVC1
0.00
0.24
198.38
14748.67
57.82
18.89
1.02
0.04
3-uniform HMVO12
0.01
0.27
1464.06
100916.35
174.32
269.43
1.00
0.02
uniform HIMVO0
1548.77
3-uniform HMVC14
0.26
15.79
>3600
27582.99
M/A
W/A
1.02
0.01
3-uniform HMVO05
0,58
>3600
00
N/A
W/A
1.49
3-uniform
-uunfom__MVCU6 HMVCU6
0,02
1,03
>3600
33883.58
B/A
X/A
1.78
0.08
JIMCC07 HIMVCU7
0.03
1.52
53600
54487.73
N/A
W/A
1.52
0.16
3-unifarm HMVC08
0.02
0.67
>3600
N/A
M/A
2.32
0.05
3-uniform HMVC19
0.02
0.66
>3000
00
N/A
W/A
3.18
0.03
3-uniform HMVC10
2.50
19186.52
4-uniform_ HMVCII
0.02
0.45
>3600
106312.87
M/A
W/A
1.18
0.03
L4: SNNs are ultimately heuristic algorithms, which complicate theoretical analyses on solution quality and runtime complexity.
Despite the limitations above, the results showed clear trends of the greater scalability of the proposed method SF-HMVC, in that 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-efficiee alternative.
Acknowledgments and Disclosure of Funding
We would like to acknowledge Intel Labs and the Intel Neuromorphic Research Community (INRC) for providing access to Loihi 2. We thank Intel's Neuromorphic Computing Lab (NCL) for developing NEBM algorithm and NEBM-based QUBO solvers, which was central to work. We thank Philipp Stratmann from NCL for the documentation related to NEBM. We also thank all the members of NCL for their support technical issues. Tat-Jun Chin is SmartSat CRC Professorial Chair of Sentient Satellites.
10

---

References
[1] Intel Builds World's Largest
Neuromorphic System to Enable More Sustain-
able AL
intel-builde builds-worlde worlds- https://ww..ntee..ccmmmmoom /attaal.ccooccoceeet////////////
https://www inteln
haas///nnnossrrom/eesss// html
[2] Lava: A software framework for Neuromorphic Computing, Intel Corporation. https://
gi github.cm comb//a-ncaaacncaaaaaa
[3] Quadratic Unconstrained Binary Optimization (QUBO) with Lava, Intel Corpora-
tion.
[4] Spirals, 2019. pyjoules. httpss//pyyooueee.eeetddddoosoep
[5] Vertex cover in hypergraphs, Wikipedia. https://en. https://en.iikipedi.. wtt.iiiaarrg/iii//eeeeeee cover Lover_in_hyye hyrperrrhppsgga
[6] M. Z. Alom, B. V. Essen, A. T. Moody, D. P. Widemann, and T. M. Taha. Quadratic uncon- strained binary optimization (qubo) on neuromorphic computing system. In International Joint Conference on Neural Networks, 2017.
[7] N. Bansal and S. Khot. Inapproximability of hypergraph vertex cover and applications to scheduling problems. In S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, and P. G. Spirakis, editors, Automata, Languages and Programming, pages 250-261, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
[8] Binas, G. Indiveri, and M. Pfeiffer. Spiking analog vlsi neuron assemblies constraint satisfaction problem solvers. IEEE International Symposium on Circuits and Systems, 2016.
[9] C. Chauve, M. Patterson, and A. Rajaraman. Hypergraph covering problems motivated by genome assembly questions. In T. Lecroq and L. Mouchard, editors, Combinatorial Algorithmss, pages 428 432. Springer Berlin Heidelberg. 2013.
[10] S. Chiavazza, S. M. Meyer, and Y. Sandamirskaya. Low-latency monocular depth estimation using event timing neuromorphic hardware. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 4071-4080, 2023.
[11] K. Corder, J. V. Monaco, and M. M. Vindiola. Solving vertex cover via ising model on neuromorphic processor. In IEEE International Symposium on Circuits and Systems, 2018.
[12] M. Davies, N. Srinivasa, T.-H. Lin, G. Chinya, Y. Cao, S. H. Choday, G. Dimou, P. Joshi, N. Imam, S. Jain, Y. Liao, C.-K. Lin, A. Lines, Liu, D. Mathaikutty, McCoy, Paul,
J. Tse, G. Venkataramanan, Y.H.. Weng, A. Wild, Y. Yang, and H. Wang. Loihi: A neuromorphic manycore processor with on-chip learning. IEEE Micro, 38(1):82-99, 2018
[13] M. Davies, A. Wild, G. Orchard, Y. Sandamirskaya, G. A. F. Guerra, P. Joshi, P. Plank, and R. Risbud. Advancing neuromorphic computing with loihi: A survey of results and outlook. Proceedings of the IEEE, 109(5):911 199494911-934, 2021.
[14] Y. Fang and A. S. Lele. Solving quadratic unconstrained binary optimization with collaborative spiking neural networks. In IEEE International Conference on Rebooting Computing. 2022.
[15] Glover, G. Kochenberger, Hennig, and Y. Du. Quantum bridge analytics tutorial on formulating and using qubo models. Annals of Operations Research, 2022.
[16] I. Goodfellow, Y. Bengio, and A. Courville. Deep Learning. MIT Press, 2016. http: www..deeppeermingbood. org.
[17] G. A. F. Guerra and S. B. Furber. Using stochastic spiking neural networks spinnaker to solve constraint satisfaction problems. Frontiers in neuroscience, 2017.
[18] Gurobi. https::/ :/www..//www../ www.bi.cc..o com/
Accessed: 2024-05-22.

---

[19] A. Guzzo, A. Pugliese, A. Rullo, and D. Saccà. Intrusion detection with hypergraph-basee attack models. In M. Croitoru, S. Rudolph, S. Woltran, and C. Gonzales, editors, Graph Structures for Knowledge Representation and Reasoning, pages 58-73 Springer International Publishing, 2014.
[20] D. S. Johnson and M. A. Trick. Cliques, coloring, and satisfiability: second DIMACS imple- mentation challenge, October 11-3, 1993, volume 26. American Mathematical Soc., 1996.
[21] Z. Jonke, S. Habenschuss, and W. Maass. Solving constraint satisfaction problems with networks of spiking neurons. Frontiers in neuroscience, 10: 15666666,222 2016.
[22] A. Kumar and L.. Vijaykumar. On neuromorphic computing: A case study on radio resource allocation with lava software framework. 2023.
[23] J. Leskovee, A. Krause, C. Guestrin, C. Faloutsos, J. M. VanBriesen, and N. S. Glance. Cost- effective outbreak detection in networks. In P. Berkhin, R. Caruana, and X. Wu, editors, Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, California, USA, August 12-15, 2007, pages 420-429. ACM, 2007.
[24] A. R. Mangalore, G. A. Fonseca, S. R. Risbud, P. Stratmann, and A. Wild. Neuromorphic quadratic programming for efficient and scalable model predictive control: Towards advancing speed and energy efficiency in robotic control. IEEE Robotics & Automation Magazine, 2024.
[25] P. Merolla, J. V. Arthur, R. Alvarez-lcaza, A. S. Cassidy, J. Sawada, F. Akopyan, B. L. Jackson, N. Imam, C. Guo, Y. Nakamura, B. Brezzo, I. Vo, K. Esser, R. Appuswamy, B. Taba, A. Amir, M. Flickner, W. P. Risk, R. Manohar, and D. S. Modha. A million spiking-neuron integrated circuit with a scalable communication network and interface. Science, 345:668 - 673, 2014.
[26] S. M. Mniszewski. Graph partitioning as quadratic unconstrained binary optimization (qubo) on spiking neuromorphic hardware. In Proceedings of the International Conference Neuro- morphic Systems.
[27] N. Mohseni, P. L. McMahon, and T. Byrnes. Ising machines as hardware solvers of combinatorial optimization problems. Nature Reviews Physics, 4(6):363-379, 2022.
[28] T. Moraitis, A. Sebastian, and E. Eleftheriou. Optimality of short-term synaptic plasticity in modelling certain dynamic environments. arXiv preprint Stti:20009008006 2020.
[29] J. Nocedal and S. J. Wright. Numerical Optimization. Springer New York, New York, NY, 2006.
[30] G. Orehard, E. P. Frady, D. B. D. Rubin, S. Sanborn, S. B. Shrestha, F, T. Sommer, and M. Davies. Efficient neuromorphic signal processing with Loihi 2. In IEEE Workshop on Signal Processing Systems (SiPS), pages 254-259, 2021.
[31] C. Ostrau, C. Klarhorst, M. Thies, and U. Rückert. Comparing neuromorphic systems by solving sudoku problems. In International Conference on High Performance Computing & &Simulation, 2019.
[32] A. Pierro, P. Stratmann, G. A. F. Guerra, S. Risbud, T. Shea, A. R. Mangalore, and A. Wild. Solving qubo on the loihi 2 neuromorphic processor. arXiv preprint 2rXiv:2408.03076, 2024.
[33] Y. Schnider, S. Wožniak, M. Gehrig, J. Lecomte, A. Von Amim, L.. Benini, D. Scaramuzza, and A. Pantazi. Neuromorphic optical flow and real-time implementation with event cameras. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4128-4137, 2023.
[34] C. D. Schuman, S. R. Kulkarni, M. Parsa, J. P. Mitchell, B. Kay, et al. Opportunitics for neuromorphic computing algorithms and applications. Nature Computational Science, 2(1):10- 19, 2022.
[35] S. B. Shrestha, J. Timcheck, P. Frady. L. Campos-Macias, and M. Davies. Efficient video and audio processing with loihi 2. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 13481-13485. IEEE, 2024.
12

---

[36] C. Yakopeic, N. Rahman, T. Atahary, T. M. Taha, and S. Douglass. Leveraging the manycore architecture of the Loihi spiking processor to perform quai-complete constraint satisfaction. In International Joint Conference on Neural Networks, 2020.
13

---

Appendix
Algorithm 2 NEBM-based SNN for energy minimization (note: the algorithm is executed for each neuron n2 on the neuromorphic hardware parallel way; see [[3] for details).
Require: Weight matrix W, temperature T and length of refractory period T/-
1: Initialize st + 0, As; + 0, u, (0)
(0)
t - Wü: refract_ counnerr (0) +
2: for each timestep do
N
(1)
Whj As 11-1)
3:
u
jæi
4:
Pi
+ exp(ux (2) /T)
5:
0, < r0nd(00,)
6:
if neuron n4 is not in refractory period then
7:
if Pt
(t) 2 0, then
8:
+1
9:
else
10:
+
11:
else
(t-1)
12:
refract counter (
max(fefract_coumte) (t-1) 1,0)
13:
(f-1)
15:
send to connected neurons
16:
if As + 0 then
17:
neuron n, enters refractory period
18:
refract counter refract_counter] + r₃
14

---

NeurIPS Paper Checklist
1. Claims
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. show the proposed SNN does not require new slack variables, as claimed in the abstract and intro- duction. 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 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
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
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Sec. discusses the limitations of the work (see LI to L4).
Guidelines:
The answer NA means that the paper has 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 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 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, 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 impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
15

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have provided a detailed methodology description and pseudo code in The data generation process and the experiment setup are fully described in Sec. 5
Sec. 4
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
16

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We will release all MVC and HMVC problem instances after the peer reviewing period. Release of source code is not possible at the moment due to internal organizational policy and contractual restrictions.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttpss//nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ btsias.ccc/ubblc/guiieeee http:/ggiieee//oeeeeeee
www.hbmmsssiooPooo ssioncl for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We have specified all experiment details in Sec.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Error bars are not available due to hardware limitations (see L3 in Sec. 6)
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

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 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 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please refer to Sec. 3oc.5lee 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 compute required for each of the individual experimental runs as well 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http///euripp..ee httppp.cccpubllbp hcc/publiccBthhcccciieeee......l
Answer: [Yes]
Justification:
We have reviewed and followed the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. 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.
18

---

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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
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 dataset.
The authors should state which version of the asset used and, possible, include URI.
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.
19

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
batasets.papersstt
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 available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are 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 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.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No crowdsourcing or research with human subjects involved.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
20

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
21


Reviews:
[{"review_id": "bGgptw4vRO", "reviewer": "Reviewer_Que6", "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.", "questions": "Could the authors address the above points?\n\nIs 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?\n\nWhy can't the random seed be changed?", "limitations": "Some of the limitations mentioned in this review are mentioned in the paper, but not all.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The work advances the field of neural networks beyond machine learning, i.e. in combinatorial optimization.\n\nMoreover, it concerns spiking neural networks, a field that has been attracting growing interest.\n\nFurthermore, the method is actually tested in neuromorphic hardware, contrary to many papers in the field that only include theoretical implications for neuromorphic hardware.\n\nMoreover, the work presents new partial evidence that neuromorphic algorithms and neuromorphic hardware may have advantages over more conventional approaches, a promise of this research field that has been long looking for fulfillment.", "weaknesses": "On the other hand, the paper has several weaknesses.\n\n1. The paper does not make clear how significant the type of problem addressed here (HMVC) is, and why it is significant.\n\n2. 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.\n\n3. 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\n\n4. 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).\n\n5. Most importantly, I believe that the paper's contribution to the broader field of Neural Networks might not be significant, for the following reasons.\n\n- 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.\n- 5b. The results are on rather small scale demonstrations.\n- 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?\n\n6. 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the feedback.\n\n1. We have indicated in L79 the practical applications of HMVC in \"computational biology [9], computer network security [19], resource allocation [7] and social network analysis [23].\" More fundamentally, HMVC is a general problem with many related formulations (set cover, hitting set, transversal, MVC, max independent set) [A], hence, HMVC algorithms have wide applicability. In short, HMVC is a significant problem and a good SNN algorithm for it will have major impact. If accepted, we will expand on the above.\n\n2. Fig. 1 illustrates a toy problem and the previous QUBO-based SNN and our handcrafted SNN (SF-HMVC). If accepted, we will update the figure with solutions from both methods.\n\n3. Note that our focus is on *SNN algorithms for optimization* (L39). In L29 we have touched upon IBM TrueNorth [25] and Intel Loihi [12,28] which are the two major neuromorphic hardware that have supported the development and experimentation of SNN-based optimization [6, 10, 11, 13, 24, 26, 28, 30, 32].\n\n   We agree that highlighting other potential implementations is useful. If accepted, we will cite the Nature Reviews Physics paper suggested by the reviewer, which covers diverse technologies at various stages of maturity such as spintronics, memristors, quantum annealers, etc.\n\n4. Since our focus is on SNN for optimization, Sec. 2 mainly surveyed works related to that. Nevertheless, we agree that the section could include major works on SNN for machine learning. If accepted, we will include the references.\n\n5. Our focus on SNN for optimization is closely aligned with the Primary Area of **Optimization (e.g., convex and non-convex, stochastic, robust)** in NeurIPS 2024.\n\n- 5a. HMVC is a fundamental problem with wide applicability---we have justified this in point 1 above.\n\n   Second, as the reviewer said, SNN \"... has been attracting growing interest\". Combinatorial optimization is a major strand of research in SNN [8,11,13,17,21,22,26,32]. Moreover, the Nature Reviews Physics paper cited by the reviewer surveys numerous hardware implementations to *solve combinatorial optimization*---clearly this indicates the importance of research into novel hardware and algorithms for combinatorial optimization.\n\n- 5b. Note that we have comprehensively evaluated the algorithm on the DIMACS benchmark [20] for MVC and synthetic instances for HMVC. As stated in L206, only instances that fit on Loihi 2 could be tested. Nonetheless, small HMVC instances (Tables 3 and 4) were already sufficient to illustrate the superiority of our `SF-HMVC-Loihi` over the previous `QUBO-Loihi`.\n\n   While the current capacity of Loihi 2 limits the problem size (which also affected [10, 13, 24, 28, 32]), our careful formulations and rigorous benchmarking provide a clear indication of the potential of our approach. Indeed, the reviewer counted \"actual testing in neuromorphic hardware\" as a strength.\n\n   See also our responses to K44F and 9cvo on scalability.\n\n- 5c. The reviewer suggested the existence of a CPU analog of our new method that \"might be more energy efficient than Loihi\", but did not provide details of this algorithm.\n\n   Note that the previous SNN is QUBO-based and hence has a direct CPU analog. In contrast, our method is a *handcrafted* SNN for HMVC that is not QUBO-based. It is unclear what the CPU analog of our method is.\n   \n   Second, the reviewer claimed that our paper showed that \"QUBO on CPU is more efficient than QUBO on Loihi\" (based on the context, we presume this meant *energy efficiency*). Note that all our results (Tables 2 and 4) point to a much higher energy consumption by the CPU solutions (`QUBO-CPU` and `ILP-CPU`) than the SNN solutions (`QUBO-Loihi` and `SF-HMVC-Loihi`) ==> The reviewer probably misread the results.\n\n   We believe CPU is the correct baseline since it is the currently dominant hardware for combinatorial optimization. Comparisons with microcontrollers and FPGAs are also interesting, which we will conduct as future research; thanks for the suggestion!\n\n6. To obtain statistics of results, we simulated the SNNs on CPU via the Lava Software Framework; see `QUBO-Lava` and `SF-HMVC-Lava` in the PDF under **Author Rebuttal**. Note that Lava simulates asynchronous processing on CPU and hence the performance (particulary the energy consumption) does not closely reflect the performance on neuromorphic hardware.\n\n   It is also important to note that the Lava versions are not the *intrinsic* CPU analogs of the SNN methods.\n\n**Why QUBO on Loihi is less efficient than on CPU?**\n\nAgain, we believe the reviewer has mistaken, since our results (Tables 2 and 4) point to a much higher energy consumption by `QUBO-CPU` than `QUBO-Loihi`.\n\nOur method `SF-HMVC-Loihi` also consumed much less energy than `QUBO-CPU` and `ILP-CPU`.\n\n**Why can't the random seed be changed?**\n\nThe current Intel API that was available to us did not include functionality to change the random seed on Loihi 2. However, note the additional results on Lava simulation mentioned above.\n\n**Summary**\n\nThe reviewer did not report technical flaws. The main concerns seem to be on the relevance and significance of the contribution, which we have adequately addressed. We hope our clarifications on the experiments and results further demonstrate the significance of our findings.\n\n[A] Wikipedia: Vertex cover in hypergraphs", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eg1m39KAdV", "reviewer": "Reviewer_K44F", "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:", "questions": "* Are there any more dataset available for benchmarking?\n* What measures have been taken to prevent overfitting in the model during the experimental phase?\n* Are there any scalability concerns when applying this method to larger or more complex problem sets?", "limitations": "limitations are discussed in the paper", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The integration of spiking neural networks (SNNs) with quantum-inspired optimization techniques represents a novel approach to solving hard minimum vertex cover (HMVC) problems. This hybrid method leverages the strengths of both neuromorphic computing and quantum mechanics principles, potentially opening new avenues for complex problem-solving.\n* The authors provide a clear explanation of the neuromorphic computing background, the limitations of existing SNN approaches, and the rationale behind their novel method. The use of NEBM spiking neurons and the detailed description of the network architecture and dynamics add depth to the technical discussion.", "weaknesses": "* 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.\n* 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.\n* 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.\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the feedback.\n\n- Note that we have compared against two contemporary (non-neuromorphic) optimization techniques: integer linear programming (ILP) and quadratic unconstrained binary optimization (QUBO), both implemented using a leading optimization sofware (Gurobi) and executed on an Intel Core i7 CPU. See columns `ILP-CPU` and `QUBO-CPU` in Tables 1 to 4.\n\n- Note that we have included explicit energy consumption figures in Tables 2 and 4 for all methods. The energy measurements were obtained using the built-in profiler in the Loihi framework for the SNN solutions and pyJoules [5] for the CPU solutions.\n\n   To summarize, the SNNs on neuromorphic hardware (`SF-HMVC-Loihi` and `QUBO-Loihi`) consumed significantly less energy (at least 1 order of magnitude less, and often several orders of magnitudes less) than the CPU-based methods (`ILP-CPU` and `QUBO-CPU`).\n\n   Also, from Table 3, our method `SF-HMVC-Loihi` could return good solutions for all HMVC instances, whereas `QUBO-Loihi` was infeasible in a majority of the instances.\n\n- The reviewer makes a good point, thanks! Since the capacity of the current neurmorphic hardware precludes testing on larger and more complex HMVC instances, detailed scalability analysis is useful.\n\n   We conduct this analysis by modeling the number of spiking neurons $n_{neurons}$ needed by either the QUBO-based SNN or the proposed SF-HMVC. Let $N$, $K$ and $r$ respectively be the number of vertices, number of hyperedges, and hyperedge degree/size of the input hypergraph ($r > 2$ for HMVC; see Problem 2 in the paper). We have:\n\n   $n_{neurons} \\text{(QUBO)} = N + (r-1)K$\n\n   $n_{neurons} \\text{(SF-HMVC)} = N + K$\n\n   Fig. 1 illustrates the SNN construction. Since $N$, $K$ and $r$ collectively define the size of the input, we can conclude that *SF-HMVC scales linearly* whereas the *QUBO-based SNN scales quadratically* with the problem size. Observe the HMVC results in Tables 3 and 4 where QUBO-SNN failed to be embedded in Loihi 2 due to exceeding the resource limits, whereas SF-HMVC could still find high-quality solutions. If accepted, we will add the above analysis.\n\n- Note that the SNN formalism [31] is independent of neuromorphic hardware implementation, hence, SNN algorithm design and comparative analysis can be abstracted from the hardware, e.g., see above on $n_{neurons}$.\n   \n   While empirical validation is tied to the hardware, we note that practical neuromorphic hardware has become very accessible in recent years. For example, academic researchers can sign up at no cost to the Intel Neuromorphic Research Community to obtain free cloud-based access to Loihi 2. Smaller firms are also offerring mature neuromophic hardware at affordable prices, e.g., see BrainChip's Akida™ PCIe Board.\n\n**Are there any more dataset available for benchmarking?**\n\nThere are other datasets for benchmarking (e.g., BHOSLIB for MVC). However, the selected problem instances were already sufficient to convincingly illustrate the benefit for the proposed approach. Particularly for HMVC, the proposed SNN (SF-HMVC) could provide good results on Loihi 2, while the baseline QUBO-based SNN either returned infeasible results or could not be executed on the hardware due to exceeding resource limits. See Tables 3 and 4.\n\nWhile testing on larger instances will require larger-scale hardware, note that Intel recently unveiled the world's largest neuromorphic system, containing \"1.15 billion neurons and 128 billion synapses\" [1]. Thus, it is important for the AI/ML community to focus on SNN algorithm development now.\n\n**What measures have been taken to prevent overfitting in the model during the experimental phase?**\n\nNote that our SNN directly optimizes solutions for the combinatorial problem without involving separate training and inference phases. An interpretation of preventing \"overfitting\" in our case can be finding hyperparameter settings that generally work for all instances.\n\nAs mentioned in L213, for each method, we conducted grid search for hyperparameters and selected a single configuration that demonstrated consistent performance across all problem instances. If accepted, we will further elaborate this point.\n\n**Are there any scalability concerns when applying this method to larger or more complex problem sets?**\n\nIn the analysis above, we have shown that our SNN (SF-HMVC) scales linearly while the baseline QUBO-based SNN scales quadratically, hence, our method is provably more scalable. The fact that SF-HMVC does not need to optimize slack variables will also allow it to return higher quality results due to simpler loss landscapes.\n\nThe current main limitation is due to the hardware, which, as highlighted above, is on the way to be resolved judging by recent major developments (see above).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GOVuRGnQZ8", "reviewer": "Reviewer_cGCZ", "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).", "questions": "Please see weakness.", "limitations": "The authors raise some limitaions, for example, the capacity of the Loihi 2 is low, which is limited by the development of hardware.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-written.\n\n2. The proposed SF-HMVC approach is designed to be scalable, handling larger problem instances effectively. The parallel nature of neuromorphic computing allows for efficient processing of complex optimization problems.\n\n3. The results show that SF-HMVC can occasionally outperform QUBO-CPU methods in solution quality for larger problem instances, indicating that the SNN-based approach can be competitive with traditional optimization algorithms.", "weaknesses": "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.\n\n2. 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?\n\n3. The experiments are influenced by many hyperparameters, such as $\\lambda$ and timestep $T$. It is recommended to conduct appropriate ablation experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the feedback.\n\n1. We included Algorithm 1 in the paper to make it self-contained, however, if accepted, we will move it to the appendix in the camera-ready version.\n\n2. The motivation of the $\\mathbf{W}$ matrix is to capture the connection strengths between neurons within the SF-HMVC SNN, which can be interpreted as interactions between NEBM-NEBM and NEBM-FB neurons.\n\n- The binary variables in Eq. 6 are encoded as NEBM neurons, which are designed to inhibit each other to facilitate the minimization of the objective function. The connection strengths between NEBM-NEBM neurons are associated with $\\mathbf{F}$ matrix, where the entries $f_{ij}$ are calculated based on the occurrence and co-occurrence of variables $z_i$, $z_j$ within the problem constraints.\n\n - The $\\mathbf{A}$ matrix defines the connection between NEBM versus FB neurons. The motivation of the $A$ matrix is to introduce an FB neuron to each set of NEBM neurons that belong to the same constraints. The FB neuron is active only when all NEBM neurons under its \"observation\" are turned off (corresponding to the constraint being violated) and remains silent otherwise. Once activated, the FB neuron sends excitatory signals until the constraint is satisfied.\n\n   We hope the above clarifies the setup and motivation for $\\mathbf{W}$ matrix.\n\n3. Note that the baseline QUBO-based SNN (Algorithm 1) requires 3 hyperparameters:\n   - $\\lambda$ for the weight of the penalty term.\n   - $T$ for the temperature.\n   - $r_i$ for the refractory period.\n\n   The proposed SNN SF-HMVC (Algorithm 2) requires only 2 hyperparameters ($T$ and $r_i$) due to our slack-free formulation. Moreover, since the total number of steps $M$ given to both algorithms is fixed to $1000$, for brevity we do not perform ablation on $M$.\n\n   Figure R3 in the PDF under **Author Rebuttal** shows the ablation studies of the influence of $T$ and $r_i$ on the solution quality of SF-HMVC on Loihi 2. The results show that there are hyperparameter configurations where our method consistently yielded high-quality solutions.\n\n   Also, as mentioned in L194, we have conducted grid search to find common settings of hyperparameters ($\\lambda$ for the QUBO formulations, temperature and refractory period for the SNN models) that work well for all problem instances. If accepted, we will define the chosen hyperparameter values in the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QY6X8Xjblx", "reviewer": "Reviewer_9cvo", "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.", "questions": "1. How scalable is the proposed SNN method with future advancements in neuromorphic hardware?\n2. Can the approach be generalized to other combinatorial optimization problems beyond HMVC?", "limitations": "1. The neuromorphic hardware capacity is currently limited, restricting the scale of problem instances that can be tested.\n2. There is a lack of public HMVC benchmarks, complicating the evaluation of the method's generalizability.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. Innovative approach to solving HMVC without slack variables, reducing the search space and improving solver effectiveness.\n2. Consistently high-quality solutions across multiple problem instances.\n3. The paper structure is well-organized.", "weaknesses": "1. The scale of experiments are relatively small and simple.\n2. Lack of comparison with other solving methods, e.g. Gurobi and D-Wave.\n3. There are some typos. E.g. in line 102, *whot* -> *who*.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the feedback.\n\n1. Despite the relatively small problem instances that can be solved by the neuromorphic hardware available (Loihi 2), we would like to point out that the selected problem instances were already sufficient to convincingly illustrate the benefit for the proposed approach. Particularly for HMVC, the proposed SNN (SF-HMVC) could provide good results on Loihi 2, while the baseline QUBO-based SNN either returned infeasible results or could not be executed on the hardware due to exceeding resource limits. See Tables 3 and 4.\n\n2. Note that we have compared against Gurobi solver; see **Competitors** in Sec. 5.1, and columns `ILP-CPU` and `QUBO-CPU` in Tables 1, 2, 3, and 4. Being an established optimization software that guarantees global optimality, the Gurobi-based solutions provide a reference for the quality. Other the other hand, the energy consumption figures in Tables 2 and 4 show that the SNN algorithms, particularly `SF-HMVC` consume at least an order of magnitude less energy than Gurobi.\n\n   Thanks for the suggestion to compare against D-Wave. While both neuromorphic computers and quantum annealers are Ising solvers and thus can solve QUBO, the fact is that solving HMVC on D-Wave will still require adding slack variables to convert HMVC to QUBO. The additional variables will consume the qubit budget, thus reducing the size of the HMVC instances that can be solved using D-Wave. In contrast, the neuromorphic paradigm provides more fiexibility to handcraft SNNs, which we exploited to develop SF-HMVC, which is a slack-free formulation. Nonetheless, we agree that comparing against D-Wave is interesting, which we will leave as future work.\n\n3. Thank you for pointing out the typos! If accepted, we will carefully check the paper and remove typos.\n\n**How scalable is the proposed SNN method with future advancements in neuromorphic hardware?**\n\n   We have added an analysis of the scalability of SF-HMVC versus the QUBO-based SNN:\n\n   Let $n_{neurons}$ be the number of spiking neurons needed by the SNN, and $N$, $K$ and $r$ respectively be the number of vertices, number of hyperedges, and hyperedge degree/size of the input hypergraph ($r > 2$ for HMVC; see Problem 2). We have:\n\n   $n_{neurons} \\text{(QUBO)} = N + (r-1)K$\n\n   $n_{neurons} \\text{(SF-HMVC)} = N + K$\n\n   Fig. 1 illustrates the SNN construction. Fundamentally, treating $N$, $K$ and $r$ as input (size) parameters, *SF-HMVC scales linearly* whereas the *QUBO-based SNN scales quadratically* with the HMVC problem size.\n\n**Can the approach be generalized to other combinatorial optimization problems beyond HMVC?**\n\nAs surveyed in Sec. 2, the flexibility of the neuromorphic approach allows SNNs to be handcrafted for combinatorial problems. So far, this has included constraint satisfaction problems (in the context of Sudoku [8,29], graph coloring [17], graph hamiltonian [21]) and Boolean satisfiability [21,32].\n\nOur work is the first to conduct combinatorial *optimization* using a handcrafted SNN (previous such works were QUBO-based that employed the generic SNN QUBO solver).\n\nBased on the broader research and our work, there is great potential to generalize the handcrafted approach to other combinatorial optimization problems. Moreover, HMVC is a general problem with many related formulations (set cover, hitting set, transversal) and special cases (MVC, max independent set), hence, our method is applicable to a wide variety of problems.\n\n**The neuromorphic hardware capacity is currently limited**\n\n   Note that while our experiments were conducted on a single-chip system, stackable multiple-chip systems have been developed [A]. We also highlight the recent unveiling of the world's largest neuromorphic system by Intel, which contains \"1.15 billion neurons and 128 billion synapses\" [1]. With significant commitment by the chipmaking industry on neuromorphic computing, there is great potential for the hardware limitation to be resolved in the near term, thus, it is important for the AI/ML community to focus on SNN algorithm development now.\n\n**Lack of public HMVC benchmarks**\n\nWe would like to reiterate point 1 above, where the current datasets/results are already sufficient to convincingly illustrate the much better scalability and performance of the proposed SF-HMVC over the QUBO-based SNN.\n\n[A] Mehonic et al. Roadmap to Neuromorphic Computing with Emerging Technologies. arXiv:2407.02353", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the AC for handling our submission and the reviewers for their insightful comments.

K44F, cGCZ and 9cvo thought that the paper was technically solid. Que6 also did not report any technical flaws.

Que6's concerns were mainly on relevance and significance: note that our focus on spiking neural networks (SNN) for optimization is closely aligned with the Primary Area of "Optimization (convex and non-convex, discrete, stochastic, robust)" in NeurIPS 2024. Moreover, hypergraph minimum vertex cover (HMVC) is a fundamental combinatorial problem with many related formulations and practical applications. Thus, an effective SNN algorithm for HMVC will have major impact.

Also, we believe Que6 misread the results; the data in Tables 2 and 4 clearly show that the SNNs executed on Loihi (`QUBO-SNN` and `SF-HMVC-SNN`) consistently consumed much less energy than the CPU solutions (`ILP-CPU` and `QUBO-CPU`).

Based on a comment by K44F and 9cvo, we have added scalability analysis of the proposed SF-HMVC. Briefly, SF-HMVC scales linearly whereas the baseline QUBO-based SNN scales quadratically with the HMVC problem size. The analysis was empirically validated in the experiments, where `QUBO-SNN` was infeasible on Loihi 2 for the HMVC instances, whereas `SF-HMVC-SNN` could solve the same instances on Loihi 2 effectively (see Tables 3 and 4). In future iterations of neuromorphic hardware, `SF-HMVC-SNN` will retain its computational advantages over `QUBO-SNN`, due to our slack-free formulation for HMVC and handcrafted SNN design (Sec. 4).

More broadly, recent developments on neuromorphic technology (e.g., [1]) indicate the near-term availability of large-scale neuromorphic processors and/or clusters, hence, the current capacity limitation on Loihi 2 should not deter the NeurIPS community from researching SNN algorithms.

We also added the following results in the attached PDF:
- [Tables R1 and R2] Following a suggestion by Que6, to circumvent the inability to change the random seed on Loihi 2 and obtain statistics on the solution quality, we simulated the SNNs on the CPU via the Lava framework that allows changing the random seed (see `QUBO-Lava` and `SF-HMVC-Lava` in the uploaded PDF). Note that `QUBO-Lava` and `SF-HMVC-Lava` are not *instrinsic* CPU analogs of the SNN algorithms, hence, their performance (solution quality, energy consumption, runtime) are not reflective of what is achievable on the neuromorphic hardware.
- [Figure R3] Following a suggestion by cGCZ, we conducted ablation studies for the hyperparameters of `SF-HMVC-Loihi` on MVC and HMVC instances. The results show that there are hyperparameter configurations where our method consistently yielded high-quality solutions; see our response to cGCZ for more details of this experiment.

For more details of the above, please see our individual responses to the reviewers.

**Summary**

The reviewers found the paper technically solid and/or did not indicate technical flaws. We have addressed the main concerns on relevance, significance, scalability and hardware limitation, as well as obtained statistics on solution quality via SNN simulation on CPU. We thank the AC and reviewers again for their time.

Meta-review: 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.
Decision: Accept (poster)