A graph-theoretic approach to multitasking
A key feature of neural network architectures is their ability to support the simultaneous interaction among large numbers of units in the learning and processing of representations. However, how the richness of such interactions trades off against the ability of a network to simultaneously carry out multiple independent processes -a salient limitation in many domains of human cognition -remains largely unexplored. In this paper we use a graph-theoretic analysis of network architecture to address this question, where tasks are represented as edges in a bipartite graph G = (A ∪ B, E). We define a new measure of multitasking capacity of such networks, based on the assumptions that tasks that need to be multitasked rely on independent resources, i.e., form a matching, and that tasks can be multitasked without interference if they form an induced matching. Our main result is an inherent tradeoff between the multitasking capacity and the average degree of the network that holds regardless of the network architecture. These results are also extended to networks of depth greater than 2. On the positive side, we demonstrate that networks that are random-like (e.g., locally sparse) can have desirable multitasking properties. Our results shed light into the parallel-processing limitations of neural systems and provide insights that may be useful for the analysis and design of parallel architectures.
The authors lay an ambitious groundwork for studying the multitasking capability of general neural network architectures. They prove a variety of theorems concerning behavior of their defined criteria--the multitasking capacity \alpha--and how it relates to graph connectivity and size via graph matchings and degree.
Pros:  The problem being studied is quite clearly motivated, and the authors present a genuinely novel new measure for attempting to understand the multitasking capability of networks.  The authors fairly systematically calculate bounds on their parameter in a variety of different graph-theoretic scenarios.
Cons:  It's unclear how practically useful the parameter \alpha will be for real networks currently in use.  Admittedly, this work is preliminary, and the authors point out this shortcoming in their conclusion.  While it is likely the topic of an upcoming study, it would benefit the thrust of the paper considerably if some \alpha's were calculated for networks that are actually in use, or *some* sort of numerical comparison were demonstrated (ex: it's recently become popular to train neural networks to perform multiple tasks simultaneously--what does \alpha have to say about the topologies of these networks?)
Plainly, it's not obvious from a first read of the paper that \alpha *means* anything short of being an abstract quantity one can calculate for graphs.  Additional reads clarify the connection, but making some sort of empirical contact with networks used in practice (beyond the throwaway lines in the conclusion about pseudorandom graphs) would greatly clarify the practical use of (or even intuition for) the \alpha parameter.
That said, this reviewer thinks the article should still be accepted in the absence of such an empirical study, because performing such a study would likely (at least) double the length of the paper (which would be silly).  At the minimum, though, this reviewer would appreciate a bit more discussion of the practical use of the parameter.