Search

One of the key challenges in machine learning is to find interpretable representations of learned functions. The M\"obius transform is essential for this purpose, as its coefficients correspond to unique importance scores for sets of input variables. This transform is closely related to widely used game-theoretic notions of importance like the Shapley and Bhanzaf value, but it also captures crucial higher-order interactions. Although computing the obius Transform of a function with $n$ inputs involves $2^n$ coefficients, it becomes tractable when the function is sparse and of low-degree as we show is the case for many real-world functions. Under these conditions, the complexity of the transform computation is significantly reduced. When there are $K$ non-zero coefficients, our algorithm recovers the M\"obius transform in $O(Kn)$ samples and $O(Kn^2)$ time asymptotically under certain assumptions, the first non-adaptive algorithm to do so. We also uncover a surprising connection between group testing and the M\"obius transform. For functions where all interactions involve at most $t$ inputs, we use group testing results to compute the M\"obius transform with $O(Kt\log n)$ sample complexity and $O(K\mathrm{poly}(n))$ time. A robust version of this algorithm withstands noise and maintains this complexity. This marks the first $n$ sub-linear query complexity, noise-tolerant algorithm for the M\"obius transform. In several examples, we observe that representations generated via sparse M\"obius transform are up to twice as faithful to the original function, as compared to Shaply and Banzhaf values, while using the same number of terms., Comment: 34 pages, 16 figures

In this paper we discuss the results recently published in~[1] about algebraic signal models (ASMs) based on non commutative algebras and their use in convolutional neural networks. Relying on the general tools from algebraic signal processing (ASP), we study the filtering and stability properties of non commutative convolutional filters. We show how non commutative filters can be stable to small perturbations on the space of operators. We also show that although the spectral components of the Fourier representation in a non commutative signal model are associated to spaces of dimension larger than one, there is a trade-off between stability and selectivity similar to that observed for commutative models. Our results have direct implications for group neural networks, multigraph neural networks and quaternion neural networks, among other non commutative architectures. We conclude by corroborating these results through numerical experiments.

In this paper, we introduce a convolutional architecture to perform learning when information is supported on multigraphs. Exploiting algebraic signal processing (ASP), we propose a convolutional signal processing model on multigraphs (MSP). Then, we introduce multigraph convolutional neural networks (MGNNs) as stacked and layered structures where information is processed according to an MSP model. We also develop a procedure for tractable computation of filter coefficients in the MGNN and a low cost method to reduce the dimensionality of the information transferred between layers. We conclude by comparing the performance of MGNNs against other learning architectures on an optimal resource allocation task for multi-channel communication systems., Comment: arXiv admin note: text overlap with arXiv:2209.11354

Graph convolutional learning has led to many exciting discoveries in diverse areas. However, in some applications, traditional graphs are insufficient to capture the structure and intricacies of the data. In such scenarios, multigraphs arise naturally as discrete structures in which complex dynamics can be embedded. In this paper, we develop convolutional information processing on multigraphs and introduce convolutional multigraph neural networks (MGNNs). To capture the complex dynamics of information diffusion within and across each of the multigraph's classes of edges, we formalize a convolutional signal processing model, defining the notions of signals, filtering, and frequency representations on multigraphs. Leveraging this model, we develop a multigraph learning architecture, including a sampling procedure to reduce computational complexity. The introduced architecture is applied towards optimal wireless resource allocation and a hate speech localization task, offering improved performance over traditional graph neural networks.

Restructuring route networks (i.e., modifying the graph of origin-destination pairs) remains a promising alternative for reducing the airline industry's environmental impact. However, there exists a fundamental trade-off between emissions from flight and airport accessibility, since flights connecting underserved, low-accessibility communities tend to possess high CO2 per seat-mile ratios. Thus, this work develops an open-source analytical framework and methodology that restructures U.S. airline route networks to simultaneously minimize emissions and maximize airport accessibility. To achieve this goal, this paper designs a metric to quantify airport accessibility and combines it with an open-source system-wide emissions estimation methodology. This facilitates the creation of a mixed-integer linear optimization model that returns revised flight frequencies and aircraft allotment. Using United Airlines 2019 Q3 data as a case study, this model is able to construct an alternative route network with a 25% reduction on the total number of flights, 4.4% decrease in the average emissions per seat-mile and a 17.6% improvement in the spread of the airports' accessibility scores, all while satisfying historic passenger demand.

Through an aviation emissions estimation tool that is both publicly-accessible and comprehensive, researchers, planners, and community advocates can help shape a more sustainable and equitable U.S. air transportation system. To this end, we develop an open-source, data-driven methodology to calculate the system-wide emissions of the U.S. domestic civil aviation industry. This process utilizes and integrates six different public datasets provided by the Bureau of Transportation Statistics (BTS), the Federal Aviation Agency (FAA), EUROCONTROL, and the International Civil Aviation Organization (ICAO). At the individual flight level, our approach examines the specific aircraft type, equipped engine, and time in stage of flight to produce a more granular estimate than competing approaches. Enabled by our methodology, we then calculate system-wide emissions, considering four different greenhouse gases (CO2, NOx, CO, HC) during the Landing, Take-off (LTO) and Climb, Cruise, and Descent (CCD) flight cycles. Our results elucidate that emissions on a particular route can vary significantly due to aircraft and engine choice, and that emission rates differ significantly from airline to airline. We also find that CO2 alone is not a sufficient proxy for emissions, as NOx, when converted to its CO2-equivalency, exceeds CO2 during both LTO and CCD.

In this paper we introduce and study the algebraic generalization of non commutative convolutional neural networks. We leverage the theory of algebraic signal processing to model convolutional non commutative architectures, and we derive concrete stability bounds that extend those obtained in the literature for commutative convolutional neural networks. We show that non commutative convolutional architectures can be stable to deformations on the space of operators. We develop the spectral representation of non commutative signal models to show that non commutative filters process Fourier components independently of each other. In particular we prove that although the spectral decompositions of signals in non commutative models are associated to eigenspaces of dimension larger than one, there exists a trade-off between stability and selectivity, which is controlled by matrix polynomial functions in spaces of matrices of low dimension. This tradeoff shows how when the filters in the algebra are restricted to be stable, there is a loss in discriminability that is compensated in the network by the pointwise nonlinearities. The results derived in this paper have direct applications and implications in non commutative convolutional architectures such as group neural networks, multigraph neural networks, and quaternion neural networks, for which we provide a set of numerical experiments showing their behavior when perturbations are present.

Many algorithms for control of multi-robot teams operate under the assumption that low-latency, global state information necessary to coordinate agent actions can readily be disseminated among the team. However, in harsh environments with no existing communication infrastructure, robots must form ad-hoc networks, forcing the team to operate in a distributed fashion. To overcome this challenge, we propose a task-agnostic, decentralized, low-latency method for data distribution in ad-hoc networks using Graph Neural Networks (GNN). Our approach enables multi-agent algorithms based on global state information to function by ensuring it is available at each robot. To do this, agents glean information about the topology of the network from packet transmissions and feed it to a GNN running locally which instructs the agent when and where to transmit the latest state information. We train the distributed GNN communication policies via reinforcement learning using the average Age of Information as the reward function and show that it improves training stability compared to task-specific reward functions. Our approach performs favorably compared to industry-standard methods for data distribution such as random flooding and round robin. We also show that the trained policies generalize to larger teams of both static and mobile agents.