CS Paper Radar

On the Observability and Controllability of Leaky-ReLU Networks

Liangjie Sun, Wai-Ki Ching, Shun-ichi Azuma, Tatsuya Akutsu

eess.SY ·submitted 2026-08-10 03:06 UTC · v1
theory

Abstract

This paper studies minimum-node observability and controllability of Leaky rectified linear unit (Leaky-ReLU) networks under degree constraints. The objective is to characterize how many state nodes must be measured or directly actuated to determine the initial state from a finite output sequence or to steer the network between arbitrary states within a finite horizon. For observability, a graph-theoretic analysis yields a class-wide upper bound on the minimum number of observation nodes. We construct a family of networks attaining this bound, thereby determining the exact worst-case minimum number of observation nodes. We also construct networks that are observable from a single node over a finite horizon, establishing the exact best-case value of one. By establishing an observability--controllability duality under the corresponding degree constraints, we obtain analogous exact best- and worst-case results for the minimum number of control nodes. A comparison with ReLU networks shows how replacing the zero negative slope with a nonzero slope changes the observation-node requirement. More generally, the observability arguments require only injectivity of the activation function, whereas the controllability results extend to bijective activation functions.

Closest papers

Nearest neighbours by meaning across the whole index.

On the Number of Observation Nodes in Recurrent Neural Networks with Linear Threshold and ReLU Functions

eess.SY ·2026-08-30 ·Liangjie Sun, Wai-Ki Ching, Tatsuya Akutsu
theory similarity 0.77
Abstract

This paper investigates how node update rules and admissible state domains affect the minimum number of observation nodes required for global finite-horizon observability in recurrent neural networks with linear-threshold and ReLU update functions. Over a common binary state domain, we construct a class of $K$-linear-threshold ($K$-LT) networks whose initial states can be uniquely reconstructed from the finite output trajectory of a single observation node. We further establish a dynamical equivalence between binary-valued $K$-ReLU networks and $K$-AND Boolean networks, which transfers existing class-level observation-node bounds to binary-valued $K$-ReLU networks. For nonnegative-valued ReLU networks, the observability problem reduces to the classical linear-system setting whenever the relevant pre-activations remain nonnegative. For general real-valued ReLU networks, we prove that global finite-horizon observability requires at least $n/2$ observation nodes when no restriction is imposed on the number of state variables involved in each node update. This lower bound is tight when $n=2K$, for which we construct a $K$-ReLU network observable from exactly $K$ nodes. These results show that both update rules and state domains fundamentally affect extremal observation requirements: temporal evolution can concentrate finite-state information into a single measured trajectory, whereas activation-induced rank loss creates an intrinsic sensor lower bound in continuous-state ReLU networks.

0.29

On the Minimal Controllability of Boolean Networks With $k$-Regular Dependency Graphs

eess.SY math.OC ·2026-11-05 ·Christopher H. Fok, Chi-Wing Wong, Wai-Ki Ching
theory similarity 0.60
Abstract · 16 pages

Boolean networks (BNs) are widely used to model gene regulatory networks and other biological systems. In this paper, we investigate the minimal controllability problem for BNs subject to degree constraints. We first establish three new best-case upper bounds for XOR-BNs whose dependency graphs are $k$-regular. We then introduce classes of BNs that are invariant under cyclically partite transformation (CPT-invariant) and prove theorems connecting BN controllability with the surjectivity of vector-valued Boolean functions. Finally, by combining an analysis of this surjectivity with a probabilistic argument, we derive a new general lower bound on the minimum number of control nodes required for majority-type threshold BNs with $(2k+1)$-regular dependency graphs.

0.30

Observability Blocking in a Linear Synchronization Network with Partial State Measurements

eess.SY ·2026-08-26 ·Alexis Moreno, Abdullah Al Maruf
similarity 0.58
Abstract · 8 pages, 3 figures, submitted to the IEEE Conference on Decision and Control (CDC)

Large-scale networked systems are increasingly vulnerable to adversaries that can infer system dynamics from a small set of compromised nodes. This paper addresses the problem of blocking such inference using limited state information. While existing state-feedback methods achieve observability blocking with eigenvalue preservation, they require full state access and are impractical for large networks. We propose multiple control strategies that operate under partial state measurements. The first approach employs output feedback to achieve observability blocking while preserving a subset of open-loop eigenvalues. The second approach leverages an observer to reconstruct the system state and enables full-state feedback control, preserving all eigenvalues and providing greater flexibility in sensor placement. We further extend the observer-based design to a distributed framework. Numerical examples demonstrate the scope and validity of the proposed methods.

0.30

The Complexity of ReLU Network Synthesis from a Parameter Multiset

cs.CC cs.LG ·2026-11-02 ·Dimitrios Myrisiotis
similarity 0.57
Abstract · 110 pages, 1 table

We ask how hard it is to build a ReLU network when its parameter values are given in advance. An instance supplies an appropriate encoding of a target behavior, a multiset of rational numbers, and a bound on the number of neurons (output included). The question is whether one can choose the graph of a ReLU network within the bound, and place the numbers on its edges and biases so that it meets the target. This separates the numbers from the architecture. Matching two labeled examples exactly is already $\mathsf{NP}$-complete, so we ask what changes when the target must hold on every input or on average. Agreeing with a Boolean circuit on every Boolean input is $Σ_2^{\mathsf P}$-complete, already for four neurons. Agreeing with a given ReLU network on every real input lies in $\mathsf{DP}$ for every fixed neuron bound and is $\mathsf{DP}$-complete for three neurons. Approximating a ReLU network on the unit cube within absolute error one everywhere is $Σ_2^{\mathsf P}$-complete, even with no hidden neurons and all numbers equal and positive. Deciding whether some network has expected squared loss at most a threshold is $\mathsf{NP}^{\mathsf{PP}}$-complete for uniform Boolean inputs. For uniform inputs on the unit cube and for standard Gaussian inputs with a positive threshold, the same holds for two neurons when a positive risk gap, given in binary and possibly exponentially small, separates yes from no instances. Without a gap, the cube version is complete for guessing a polynomial-length string, then comparing a sum of exponentially many rationals with a threshold, all computable in polynomial time from the input and the guess.

0.20

Antagonistic Control: Foundations, Scalability and Nonlinearity

eess.SY math.OC ·2026-08-23 ·Sribalaji C. Anand, André M. H. Teixeira
similarity 0.57
Abstract · Under review

This paper studies the worst-case impact of constrained control inputs: an input seeks to maximize the average cost of some outputs, measured in the $L_2$ or $L_1$ norm, while remaining bounded in terms of other outputs. This problem template subsumes classical metrics such as the $H_\infty$ norm and the output-to-output gain, and arises in adversarial control, security assessment, and robust control. For linear time-invariant systems, we provide an exact semi-definite program (SDP) when there is a single constraint, and SDPs computing upper bounds when there are multiple constraints. We derive sufficient conditions, in terms of system zeros and relative degrees, under which the worst-case cost is unbounded, together with a constructive closed-loop modification that removes the unboundedness. From a security standpoint, unbounded values reveal structural limitations in detecting certain attack inputs. For positive systems, we provide scalable formulations whose complexity grows linearly in the state dimension: a scalable SDP for quadratic costs, and an exact linear program for linear costs. The results extend to nonlinear polynomial systems via a sum-of-squares program. We illustrate the results with numerical examples.

0.20

A Polynomial-Time Algorithm for the Minimal Input/Output Node Cardinality Disturbance Decoupling Problem over Networks via Output Feedback

eess.SY math.OC ·2026-10-15 ·Luca Claude Gino Lebon, Jorke de Vlas, Johannes K. Fichte, Claudio Altafini
similarity 0.57
Abstract · MATLAB functions implementing the results presented in this article are available in the GitLab repository: https://gitlab.liu.se/lucle71/no…

For networked systems, we propose a polynomial-time algorithm for solving the minimal input/output node cardinality disturbance decoupling problem via output feedback. The algorithm computes an optimal solution, namely, a pair of minimum-cardinality sets of control input and measurement output nodes that achieve disturbance decoupling, by solving a min-cut/max-flow problem on an extended network.

0.28

Safe Exploration of Arbitrary Dynamic Dangerous Networks

cs.DC ·2026-09-17 ·Caterina Feletti, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro
theory similarity 0.56
Abstract

Given a team of agents on the nodes of a graph-based network, the exploration problem requires each node to be visited by at least one agent. In the classical distributed setting of static networks, agents do not know the topology of the network; in the more recently investigated setting of dynamic networks, they may have prior knowledge about the graph class (e.g., trees, tori, rings) or other parameters (e.g., number of nodes). Gotoh et al. (2021) are the first to study the exploration problem of arbitrary dynamic networks, under the necessary minimal assumption that any two nodes will be connected by a temporal path infinitely often (temporal connectivity assumption). In this paper, we extend their study of exploration under temporal connectivity by considering dangerous dynamic networks, i.e., containing possibly one or more black holes. Whenever an agent enters a black hole, it will be trapped forever. The safe exploration problem requires a team to explore all the safe nodes, ensuring that at least one agent will never be trapped in a black hole. We first prove that, given the necessary (and sufficient) number of agents, a team of oblivious agents can perpetually explore the safe nodes without any prior knowledge of the network or the team, without agent or node IDs, under semi-synchronous schedulers. Then, we provide an algorithm that enables agents to safely explore the network and terminate. In this case, agents are equipped with unique IDs and persistent memory, and they know the number of safe nodes. Yet, in both cases, we prove that it is impossible for a team of agents on dynamic networks to correctly mark only the ports leading to black holes.

0.05

Safety Analysis of Parameterized Networks with Shared Counters

cs.LO ·2026-11-13 ·June Roupin, Arnaud Sangnier
similarity 0.55
Abstract

We study networks with an unbounded number of processes sharing some natural counters that can be decremented, incremented and tested to zero. We look at two safety problems: the first one asks whether there is a network with an execution bringing a process in a given final state and the other one asks the execution to bring all the processes in the final state. In their full generality, these two problems are undecidable, but we show that decidability can be regained by either using a single counter or by forbidding the use of zero-tests (as it is is the case in Vector Addition Systems with States). For these decidable cases, we obtain low complexity results, the problems being solvable either in non-deterministic logarithmic space or in polynomial time.

0.25