Research map / Architectures and efficiency / Spiking networks
Slack-Free Spiking Neural Network Formulation for Hypergraph Minimum Vertex Cover
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a slack-free spiking neural network (SF-HMVC) that solves hypergraph minimum vertex cover directly from the ILP using NEBM neurons plus feedback neurons for constraint checking, avoiding QUBO penalty terms and slack variables, and runs it on Intel Loihi 2.
Problem
Hypergraph minimum vertex cover (HMVC) is hard to solve with SNN-based QUBO solvers because penalty reformulation requires many slack variables, enlarging the search space and causing infeasible or unembeddable solutions.
Approach
Instead of penalty-based QUBO with slack variables, add one feedback (FB) spiking neuron per hyperedge constraint that detects violations and sends excitatory spikes to the connected NEBM vertex neurons, so the SNN directly searches the ILP's feasible space with neuron count N+K instead of N+(r-1)K.
Key results
- On synthetic HMVC instances, QUBO-Loihi either returned infeasible solutions (e.g., 19 with 1214 violations on HMVC02) or could not be embedded, while SF-HMVC-Loihi returned feasible solutions on all instances, e.g., 29 vs 30 for QUBO-CPU on HMVC04.
- SF-HMVC-Loihi consumed far less energy than ILP-CPU and QUBO-CPU on MVC/HMVC instances (e.g., 0.04 J vs 15.79 J for ILP-CPU on HMVC04 and >3600 s / 27582 J for QUBO-CPU).
- SF-HMVC-Loihi solved all DIMACS MVC instances within about 10 s but gave larger covers than the global ILP/QUBO solvers (e.g., 240 vs 206 on C250.9).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use slack-free SF-HMVC-Loihi instead of the slack-variable QUBO SNN | HMVC · Synthetic HMVC instances | feasibility and solution quality | Helped |
| Use slack-free SF-HMVC-Loihi instead of QUBO-Loihi | HMVC · 3-uniform_HMVC01 | runtime (seconds): 57.82 -> 1.02 | Helped |
| Use slack-free SF-HMVC-Loihi instead of QUBO-CPU | HMVC · 3-uniform_HMVC01 | energy usage (Joules): 14748.67 -> 0.04 | Helped |
| Use SF-HMVC-Loihi rather than ILP-CPU | HMVC · Synthetic HMVC instances | energy usage | Helped |
| Use ILP-CPU instead of SF-HMVC-Loihi | MVC · DIMACS MVC instances | solution quality ∥z∥1 | Helped |
| Use SF-HMVC-Loihi rather than ILP-CPU | MVC · DIMACS MVC instances | runtime | Mixed |
| Use SF-HMVC-Loihi rather than CPU global solvers | MVC · DIMACS MVC instances | energy usage | Helped |
Surprising findings
- SF-HMVC-Loihi occasionally found smaller covers than QUBO-CPU on larger HMVC instances (e.g., 10 vs 50 on 3-uniform_HMVC07 among N/A-marked Loihi cases; 29 vs 30 on HMVC04), attributed to QUBO-CPU difficulty growing with problem size.
Limitations
- Limited capacity of a single Loihi 2 chip restricted instance sizes (many HMVC instances N/A).
- No public HMVC benchmarks; generalization to practical instances untested.
- No error bars because the random seed could not be changed on Loihi 2; SNNs are heuristic without theoretical guarantees.
Experimental setup
Datasets: DIMACS MVC benchmark (complement graphs) 11 synthetic HMVC instances
Benchmarks: DIMACS MVC instances (15) synthetic HMVC instances (11)
Metrics: solution quality (||z||_1) feasibility (constraint violations) runtime (s) energy (J)
Baselines: ILP-CPU (Gurobi) QUBO-CPU (Gurobi) QUBO-Loihi 2 (NEBM SNN)
Builds on: NEBM-based QUBO solver (Intel) penalty method for QUBO reformulation Lava framework
Closest papers by meaning
- QP-SNN: Quantized and Pruned Spiking Neural Networks (ICLR 2025 · similarity 0.88)
- S$^2$NN: Sub-bit Spiking Neural Networks (NeurIPS 2025 · similarity 0.87)
- Are Conventional SNNs Really Efficient? A Perspective from Network Quantization (CVPR 2024 · similarity 0.87)
- Sign Gradient Descent-based Neuronal Dynamics: ANN-to-SNN Conversion Beyond ReLU Network (ICML 2024 · similarity 0.87)
- Spike-driven Transformer V2: Meta Spiking Neural Network Architecture Inspiring the Design of Next-generation Neuromorphic Chips (ICLR 2024 · similarity 0.86)
- Proxy Target: Bridging the Gap Between Discrete Spiking Neural Networks and Continuous Control (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.