Deep neural networks for graphs (DNNGs) represent an emerging field that studies how the deep learning method can be generalized to graph-structured data. Since graphs are a powerful and flexible tool to represent complex information in the form of patterns and their relationships, ranging from molecules to protein-to-protein interaction networks, to social or transportation networks, or up to knowledge graphs, potentially modeling systems at very different scales, these methods have been exploited for many application domains.

Abstract Braess' paradox is a classical result in the theory of congestion games. It motivates theoretically why adding a resource (e.g., an arc) to a network may sometimes worsen, rather than improve, the overall network performance. Differently from previous literature, which studies Braess' paradox in a non‐cooperative game‐theoretic setting, in this work, a framework is proposed to investigate its occurrence by exploiting cooperative games with transferable utility (TU games) on networks. In this way, instead of focusing on the marginal contribution to the network utility provided by the insertion of an arc when a single initial scenario is considered, the arc average marginal utility with respect to various initial scenarios, that is, its Shapley value in a suitably‐defined TU game, is evaluated. It is shown that, for choices of the utility function of the TU game modeling congestion, there are cases for which the Shapley value associated with an arc is negative, meaning that its average marginal contribution to the network utility is negative.

In this work, a computational method is proposed to automatically investigate the perception of the origin of full-body human movement and its propagation. The method is based on a mathematical game built over a suitably defined graph structure representing the human body. The players of this game are the graph vertices, which form a subset of body joints. Since each vertex contributes to a shared goal (i.e., to the way in which a specific movement-related feature is transferred among the joints), a cooperative game-theoretical model (specifically a transferable-utility game) is adopted, which is able (via the Shapley value) to measure the relevance of the various joints in human movement when performing full-body movement analysis. The method is theoretically investigated and applied to a motion capture dataset obtained from subjects who performed expressive movements. Finally, the method is validated through an online survey, in which several dancers/nondancers participated. The results show the capability of the proposed approach to represent the evolution of the most important joint responsible for originating each dancer's movement.

Abstract A basic question in network analysis concerns the quantification of the importance of each node in terms of network connectivity. To this end, a possible approach consists in using cooperative game theory tools to define a measure of node centrality. In this paper, given a transportation network, a cooperative game model with transferable utility (TU game) is considered. The nodes of the network represent the players in such a game, and the Shapley values of the nodes are used to measure centrality. The model, called Transportation Network cooperative (TNc) game, integrates within the utility function of the TU game the network topology and the demand. Properties of TNc games and their associated utility functions are investigated. Numerical results are reported, to get insights into the obtained properties.

The choice of dictionaries of computational units suitable for efficient computation of binary classification tasks is investigated. To deal with exponentially growing sets of tasks with increasingly large domains, a probabilistic model is introduced. The relevance of tasks for a given application area is modeled by a product probability distribution on the set of all binary-valued functions. Approximate measures of network sparsity are studied in terms of variational norms tailored to dictionaries of computational units. Bounds on these norms are proven using the Chernoff-Hoeffding bound on sums of independent random variables that need not be identically distributed. Consequences of the probabilistic results for the choice of dictionaries of computational units are derived. It is shown that when a priori knowledge of a type of classification tasks is limited, then the sparsity may be achieved only at the expense of large sizes of dictionaries.

Optimal control theory and machine learning techniques are combined to formulate and solve in closed form an optimal control formulation of online learning from supervised examples with regularization of the updates. The connections with the classical linear quadratic gaussian (LQG) optimal control problem, of which the proposed learning paradigm is a nontrivial variation as it involves random matrices, are investigated. The obtained optimal solutions are compared with the Kalman filter estimate of the parameter vector to be learned. It is shown that the proposed algorithm is less sensitive to outliers with respect to the Kalman estimate (thanks to the presence of the regularization term), thus providing smoother estimates with respect to time. The basic formulation of the proposed online learning framework refers to a discrete-time setting with a finite learning horizon and a linear model. Various extensions are investigated, including the infinite learning horizon and, via the so-called kernel trick, the case of nonlinear models.

The mathematical foundations of a new theory for the design of intelligent agents are presented. The proposed learning paradigm is centered around the concept of constraint, representing the interactions with the environment, and the parsimony principle. The classical regularization framework of kernel machines is naturally extended to the case in which the agents interact with a richer environment, where abstract granules of knowledge, compactly described by different linguistic formalisms, can be translated into the unified notion of constraint for defining the hypothesis set. Constrained variational calculus is exploited to derive general representation theorems that provide a description of the optimal body of the agent (i.e., the functional structure of the optimal solution to the learning problem), which is the basis for devising new learning algorithms. We show that regardless of the kind of constraints, the optimal body of the agent is a support constraint machine (SCM) based on representer theorems that extend classical results for kernel machines and provide new representations. In a sense, the expressiveness of constraints yields a semantic-based regularization theory, which strongly restricts the hypothesis set of classical regularization. Some guidelines to unify continuous and discrete computational mechanisms are given so as to accommodate in the same framework various kinds of stimuli, for example, supervised examples and logic predicates. The proposed view of learning from constraints incorporates classical learning from examples and extends naturally to the case in which the examples are subsets of the input space, which is related to learning propositional logic clauses.

A learning paradigm is proposed and investigated, in which the classical framework of learning from examples is enhanced by the introduction of hard pointwise constraints, i.e., constraints imposed on a finite set of examples that cannot be violated. Such constraints arise, e.g., when requiring coherent decisions of classifiers acting on different views of the same pattern. The classical examples of supervised learning, which can be violated at the cost of some penalization (quantified by the choice of a suitable loss function) play the role of soft pointwise constraints. Constrained variational calculus is exploited to derive a representer theorem that provides a description of the functional structure of the optimal solution to the proposed learning paradigm. It is shown that such an optimal solution can be represented in terms of a set of support constraints, which generalize the concept of support vectors and open the doors to a novel learning paradigm, called support constraint machines. The general theory is applied to derive the representation of the optimal solution to the problem of learning from hard linear pointwise constraints combined with soft pointwise constraints induced by supervised examples. In some cases, closed-form optimal solutions are obtained.

Kernel machines traditionally arise from an elegant formulation based on measuring the smoothness of the admissible solutions by the norm in the reproducing kernel Hilbert space (RKHS) generated by the chosen kernel. It was pointed out that they can be formulated in a related functional framework, in which the Green's function of suitable differential operators is thought of as a kernel. In this letter, our own picture of this intriguing connection is given by emphasizing some relevant distinctions between these different ways of measuring the smoothness of admissible solutions. In particular, we show that for some kernels, there is no associated differential operator. The crucial relevance of boundary conditions is especially emphasized, which is in fact the truly distinguishing feature of the approach based on differential operators. We provide a general solution to the problem of learning from data and boundary conditions and illustrate the significant role played by boundary conditions with examples. It turns out that the degree of freedom that arises in the traditional formulation of kernel machines is indeed a limitation, which is partly overcome when incorporating the boundary conditions. This likely holds true in many real-world applications in which there is prior knowledge about the expected behavior of classifiers and regressors on the boundary.

Optimality conditions for Call Admission Control (CAC) problems with nonlinearly constrained feasibility regions and K classes of users are derived. The adopted model is a generalized stochastic knapsack, with exponentially distributed interarrival times of the objects. Call admission strategies are restricted to the family of Coordinate-Convex (CC) policies. For K = 2 classes of users, both general structural properties of the optimal CC policies and structural properties that depend on the revenue ratio are investigated. Then, the analysis is extended to the case K > 2. The theoretical results are exploited to narrow the set of admissible solutions to the associated knapsack problem, i.e., the set of CC policies to which an optimal one belongs. With respect to results available in the literature, less restrictive conditions on the optimality of the complete-sharing policy are obtained. To illustrate the role played by the theoretical results on the combinatorial CAC problem, simulation results are presented, which show how the number of candidate optimal CC policies dramatically decreases as the derived optimality conditions are imposed.

The role of input dimension$d$is studied in approximating, in various norms, target sets of$d$-variable functions using linear combinations of adjustable computational units. Results from the literature, which emphasize the number$n$of terms in the linear combination, are reformulated, and in some cases improved, with particular attention to dependence on$d$. For worst-case error, upper bounds are given in the factorized form$\xi(d)\kappa(n)$, where$\kappa$is nonincreasing (typically$\kappa(n) \sim n^{-1/2}$). Target sets of functions are described for which the function$\xi$is a polynomial. Some important cases are highlighted where$\xi$decreases to zero as$d \to \infty$. For target functions, extent (e.g., the size of domains in${\BBR}^d$where they are defined), scale (e.g., maximum norms of target functions), and smoothness (e.g., the order of square-integrable partial derivatives) may depend on$d$, and the influence of such dimension-dependent parameters on model complexity is considered. Results are applied to approximation and solution of optimization problems by neural networks with perceptron and Gaussian radial computational units.

Necessary optimality conditions for Call Admission Control (CAC) problems with nonlinearly-constrained feasibility regions and two classes of users are derived. The policies are restricted to the class of coordinate-convex policies. Two kinds of structural properties of the optimal policies and their robustness with respect to changes of the feasibility region are investigated: 1) general properties not depending on the revenue ratio associated with the two classes of users and 2) more specific properties depending on such a ratio. The results allow one to narrow the search for the optimal policies to a suitable subset of the set of coordinate-convex policies.

A variational norm associated with sets of computational units and used in function approximation, learning from data, and infinite-dimensional optimization is investigated. For sets Gk obtained by varying a vector y of parameters in a fixed-structure computational unit K(-,y) (e.g., the set of Gaussians with free centers and widths), upper and lower bounds on the GK-variation norms of functions having certain integral representations are given, in terms of the £1-norms of the weighting functions in such representations. Families of functions for which the two norms are equal are described.

Various regularization techniques are investigated in supervised learning from data. Theoretical features of the associated optimization problems are studied, and sparse suboptimal solutions are searched for. Rates of approximate optimization are estimated for sequences of suboptimal solutions formed by linear combinations of n-tuples of computational units, and statistical learning bounds are derived. As hypothesis sets, reproducing kernel Hilbert spaces and their subsets are considered.

In this paper, approximation by linear combinations of an increasing number$n$of computational units with adjustable parameters (such as perceptrons and radial basis functions) is investigated. Geometric upper bounds on rates of convergence of approximation errors are derived. The bounds depend on certain parameters specific for each function to be approximated. The results are illustrated by examples of values of such parameters in the case of approximation by linear combinations of orthonormal functions.

A methodology to design state estimators for a class of nonlinear continuous-time dynamic systems that is based on neural networks and nonlinear programming is proposed. The estimator has the structure of a Luenberger observer with a linear gain and a parameterized (in general, nonlinear) function, whose argument is an innovation term representing the difference between the current measurement and its prediction. The problem of the estimator design consists in finding the values of the gain and of the parameters that guarantee the asymptotic stability of the estimation error. Toward this end, if a neural network is used to take on this function, the parameters (i.e., the neural weights) are chosen, together with the gain, by constraining the derivative of a quadratic Lyapunov function for the estimation error to be negative definite on a given compact set. It is proved that it is sufficient to impose the negative definiteness of such a derivative only on a suitably dense grid of sampling points. The gain is determined by solving a Lyapunov equation. The neural weights are searched for via nonlinear programming by minimizing a cost penalizing grid-point constraints that are not satisfied. Techniques based on low-discrepancy sequences are applied to deal with a small number of sampling points, and, hence, to reduce the computational burden required to optimize the parameters. Numerical results are reported and comparisons with those obtained by the extended Kalman filter are made.

Sets of multivariable functions are described for which worst case errors in linear approximation are larger than those in approximation by neural networks. A theoretical framework for such a description is developed in the context of nonlinear approximation by fixed versus variable basis functions. Comparisons of approximation rates are formulated in terms of certain norms tailored to sets of basis functions. The results are applied to perceptron networks.

An optimization-based learning algorithm for feedforward neural networks is presented, in which the network weights are determined by minimizing a sliding-window cost. The algorithm is particularly well suited for batch learning and allows one to deal with large data sets in a computationally efficient way. An analysis of its convergence and robustness properties is made. Simulation results confirm the effectiveness of the algorithm and its advantages over learning based on backpropagation and extended Kalman filter.

The tightness of bounds on rates of approximation by feedforward neural networks is investigated in a more general context of nonlinear approximation by variable-basis functions. Tight bounds on the worst case error in approximation by linear combinations of n elements of an orthonormal variable basis are derived.

Sets of multivariable functions that can be approximated with "dimension-independent" rates either by linear approximators or by neural networks having various types of computational units are compared. The comparison is made by exhibiting families of functions belonging to suitable difference sets.

We develop some mathematical tools for comparison of rates of fixed versus variable basis function approximation. Using these tools, we describe sets of multivariable functions, for which lower bounds on worst-case errors in approximation by n-dimensional linear subspaces are larger than upper bounds on such errors in approximation by perceptron networks with n hidden units.