Search

Transformer neural networks (TNN) excel in natural language processing (NLP), machine translation, and computer vision (CV) without relying on recurrent or convolutional layers. However, they have high computational and memory demands, particularly on resource-constrained devices like FPGAs. Moreover, transformer models vary in processing time across applications, requiring custom models with specific parameters. Designing custom accelerators for each model is complex and time-intensive. Some custom accelerators exist with no runtime adaptability, and they often rely on sparse matrices to reduce latency. However, hardware designs become more challenging due to the need for application-specific sparsity patterns. This paper introduces ADAPTOR, a runtime-adaptive accelerator for dense matrix computations in transformer encoders and decoders on FPGAs. ADAPTOR enhances the utilization of processing elements and on-chip memory, enhancing parallelism and reducing latency. It incorporates efficient matrix tiling to distribute resources across FPGA platforms and is fully quantized for computational efficiency and portability. Evaluations on Xilinx Alveo U55C data center cards and embedded platforms like VC707 and ZCU102 show that our design is 1.2$\times$ and 2.87$\times$ more power efficient than the NVIDIA K80 GPU and the i7-8700K CPU respectively. Additionally, it achieves a speedup of 1.7 to 2.25$\times$ compared to some state-of-the-art FPGA-based accelerators., Comment: arXiv admin note: text overlap with arXiv:2409.14023

Transformer neural networks (TNNs) are being applied across a widening range of application domains, including natural language processing (NLP), machine translation, and computer vision (CV). Their popularity is largely attributed to the exceptional performance of their multi-head self-attention blocks when analyzing sequential data and extracting features. To date, there are limited hardware accelerators tailored for this mechanism, which is the first step before designing an accelerator for a complete model. This paper proposes \textit{FAMOUS}, a flexible hardware accelerator for dense multi-head attention (MHA) computation of TNNs on field-programmable gate arrays (FPGAs). It is optimized for high utilization of processing elements and on-chip memories to improve parallelism and reduce latency. An efficient tiling of large matrices has been employed to distribute memory and computing resources across different modules on various FPGA platforms. The design is evaluated on Xilinx Alveo U55C and U200 data center cards containing Ultrascale+ FPGAs. Experimental results are presented that show that it can attain a maximum throughput, number of parallel attention heads, embedding dimension and tile size of 328 (giga operations/second (GOPS)), 8, 768 and 64 respectively on the U55C. Furthermore, it is 3.28$\times$ and 2.6$\times$ faster than the Intel Xeon Gold 5220R CPU and NVIDIA V100 GPU respectively. It is also 1.3$\times$ faster than the fastest state-of-the-art FPGA-based accelerator., Comment: arXiv admin note: text overlap with arXiv:2409.13975

We investigate the construction of latent spaces through self-supervised learning to support semantically meaningful operations. Analogous to operational amplifiers, these "operational latent spaces" (OpLaS) not only demonstrate semantic structure such as clustering but also support common transformational operations with inherent semantic meaning. Some operational latent spaces are found to have arisen "unintentionally" in the progress toward some (other) self-supervised learning objective, in which unintended but still useful properties are discovered among the relationships of points in the space. Other spaces may be constructed "intentionally" by developers stipulating certain kinds of clustering or transformations intended to produce the desired structure. We focus on the intentional creation of operational latent spaces via self-supervised learning, including the introduction of rotation operators via a novel "FiLMR" layer, which can be used to enable ring-like symmetries found in some musical constructions., Comment: 7 pages, 6 figures. Accepted to AES International Symposium on AI and the Musician

We consider the problem of optimal control of district cooling energy plants (DCEPs) consisting of multiple chillers, a cooling tower, and a thermal energy storage (TES), in the presence of time-varying electricity price. A straightforward application of model predictive control (MPC) requires solving a challenging mixed-integer nonlinear program (MINLP) because of the on/off of chillers and the complexity of the DCEP model. Reinforcement learning (RL) is an attractive alternative since its real-time control computation is much simpler. But designing an RL controller is challenging due to myriad design choices and computationally intensive training. In this paper, we propose an RL controller and an MPC controller for minimizing the electricity cost of a DCEP, and compare them via simulations. The two controllers are designed to be comparable in terms of objective and information requirements. The RL controller uses a novel Q-learning algorithm that is based on least-squares policy iteration. We describe the design choices for the RL controller, including the choice of state space and basis functions, that are found to be effective. The proposed MPC controller does not need a mixed integer solver for implementation, but only a nonlinear program (NLP) solver. A rule-based baseline controller is also proposed to aid in comparison. Simulation results show that the proposed RL and MPC controllers achieve similar savings over the baseline controller, about 17%., Comment: 18 pages, 12 figures. arXiv admin note: text overlap with arXiv:2203.07500

In this paper, we evaluate the use of a trained Long Short-Term Memory (LSTM) network as a surrogate for a Euler-Bernoulli beam model, and then we describe and characterize an FPGA-based deployment of the model for use in real-time structural health monitoring applications. The focus of our efforts is the DROPBEAR (Dynamic Reproduction of Projectiles in Ballistic Environments for Advanced Research) dataset, which was generated as a benchmark for the study of real-time structural modeling applications. The purpose of DROPBEAR is to evaluate models that take vibration data as input and give the initial conditions of the cantilever beam on which the measurements were taken as output. DROPBEAR is meant to serve an exemplar for emerging high-rate "active structures" that can be actively controlled with feedback latencies of less than one microsecond. Although the Euler-Bernoulli beam model is a well-known solution to this modeling problem, its computational cost is prohibitive for the time scales of interest. It has been previously shown that a properly structured LSTM network can achieve comparable accuracy with less workload, but achieving sub-microsecond model latency remains a challenge. Our approach is to deploy the LSTM optimized specifically for latency on FPGA. We designed the model using both high-level synthesis (HLS) and hardware description language (HDL). The lowest latency of 1.42 $\mu$S and the highest throughput of 7.87 Gops/s were achieved on Alveo U55C platform for HDL design., Comment: Accepted at 33rd International Conference on Field-Programmable Logic and Applications (FPL)

Understanding scaling relations of social and environmental attributes of urban systems is necessary for effectively managing cities. Urban scaling theory (UST) has assumed that population density scales positively with city size. We present a new global analysis using a publicly available database of 933 cities from 38 countries. Our results showed that (18/38) 47% of countries analyzed supported increasing density scaling (pop ~ area) with exponents ~5/6 as UST predicts. In contrast, 17 of 38 countries (~45%) exhibited density scalings statistically indistinguishable from constant population densities across cities of varying sizes. These results were generally consistent in years spanning four decades from 1975 to 2015. Importantly, density varies by an order of magnitude between regions and countries and decreases in more developed economies. Our results (i) point to how economic and regional differences may affect the scaling of density with city size and (ii) show how understanding country- and region-specific strategies could inform effective management of urban systems for biodiversity, public health, conservation and resiliency from local to global scales., Comment: 4 figures, 1 table, Appendix and Supplemental

Humans collaborate in different contexts such as in creative or scientific projects, in workplaces and in sports. Depending on the project and external circumstances, a newly formed collaboration may include people that have collaborated before in the past, and people with no collaboration history. Such existing relationships between team members have been reported to influence the performance of teams. However, it is not clear how existing relationships between team members should be quantified, and whether some relationships are more likely to occur in new collaborations than others. Here we introduce a new family of structural patterns, m-patterns, which formalize relationships between collaborators and we study the prevalence of such structures in data and a simple random-hypergraph null model. We analyze the frequency with which different collaboration structures appear in our null model and show how such frequencies depend on size and hyperedge density in the hypergraphs. Comparing the null model to data of human and non-human collaborations, we find that some collaboration structures are vastly under- and overrepresented in empirical datasets. Finally, we find that structures of scientific collaborations on COVID-19 papers in some cases are statistically significantly different from those of non-COVID-19 papers. Examining citation counts for 4 different scientific fields, we also find indications that repeat collaborations are more successful for 2-author scientific publications and less successful for 3-author scientific publications as compared to other collaboration structures., Comment: 25 pages, 9 figures

Graph neural networks (GNNs) have shown superiority in many prediction tasks over graphs due to their impressive capability of capturing nonlinear relations in graph-structured data. However, for node classification tasks, often, only marginal improvement of GNNs over their linear counterparts has been observed. Previous works provide very few understandings of this phenomenon. In this work, we resort to Bayesian learning to deeply investigate the functions of non-linearity in GNNs for node classification tasks. Given a graph generated from the statistical model CSBM, we observe that the max-a-posterior estimation of a node label given its own and neighbors' attributes consists of two types of non-linearity, a possibly non-linear transformation of node attributes and a ReLU-activated feature aggregation from neighbors. The latter surprisingly matches the type of non-linearity used in many GNN models. By further imposing Gaussian assumption on node attributes, we prove that the superiority of those ReLU activations is only significant when the node attributes are far more informative than the graph structure, which nicely matches many previous empirical observations. A similar argument can be achieved when there is a distribution shift of node attributes between the training and testing datasets. Finally, we verify our theory on both synthetic and real-world networks.

Choices made by individuals have widespread impacts--for instance, people choose between political candidates to vote for, between social media posts to share, and between brands to purchase--moreover, data on these choices are increasingly abundant. Discrete choice models are a key tool for learning individual preferences from such data. Additionally, social factors like conformity and contagion influence individual choice. Traditional methods for incorporating these factors into choice models do not account for the entire social network and require hand-crafted features. To overcome these limitations, we use graph learning to study choice in networked contexts. We identify three ways in which graph learning techniques can be used for discrete choice: learning chooser representations, regularizing choice model parameters, and directly constructing predictions from a network. We design methods in each category and test them on real-world choice datasets, including county-level 2016 US election results and Android app installation and usage data. We show that incorporating social network structure can improve the predictions of the standard econometric choice model, the multinomial logit. We provide evidence that app installations are influenced by social context, but we find no such effect on app usage among the same participants, which instead is habit-driven. In the election data, we highlight the additional insights a discrete choice framework provides over classification or regression, the typical approaches. On synthetic data, we demonstrate the sample complexity benefit of using social information in choice models., Comment: 20 pages, 4 figures, 4 tables. Accepted to Network Science

Here we assess the applicability of graph neural networks (GNNs) for predicting the grain-scale elastic response of polycrystalline metallic alloys. Using GNN surrogate models, grain-averaged stresses during uniaxial elastic tension in Low Solvus High Refractory (LSHR) Ni Superalloy and Ti 7wt%Al (Ti-7Al), as example face centered cubic and hexagonal closed packed alloys, are predicted. A transfer learning approach is taken in which GNN surrogate models are trained using crystal elasticity finite element method (CEFEM) simulations and then the trained surrogate models are used to predict the mechanical response of microstructures measured using high-energy X-ray diffraction microscopy (HEDM). The performance of using various microstructural and micromechanical descriptors for input nodal features to the GNNs is explored through comparisons to traditional mean-field theory predictions, reserved full-field CEFEM data, and measured far-field HEDM data. The effects of elastic anisotropy on GNN model performance and outlooks for extension of the framework are discussed.

District cooling energy plants (DCEPs) consisting of chillers, cooling towers, and thermal energy storage (TES) systems consume a considerable amount of electricity. Optimizing the scheduling of the TES and chillers to take advantage of time-varying electricity price is a challenging optimal control problem. The classical method, model predictive control (MPC), requires solving a high dimensional mixed-integer nonlinear program (MINLP) because of the on/off actuation of the chillers and charging/discharging of TES, which are computationally challenging. RL is an attractive alternative to MPC: the real time control computation is a low-dimensional optimization problem that can be easily solved. However, the performance of an RL controller depends on many design choices. In this paper, we propose a Q-learning based reinforcement learning (RL) controller for this problem. Numerical simulation results show that the proposed RL controller is able to reduce energy cost over a rule-based baseline controller by approximately 8%, comparable to savings reported in the literature with MPC for similar DCEPs. We describe the design choices in the RL controller, including basis functions, reward function shaping, and learning algorithm parameters. Compared to existing work on RL for DCEPs, the proposed controller is designed for continuous state and actions spaces., Comment: 10 pages, extended ACC2022 version

Minimizing a sum of simple submodular functions of limited support is a special case of general submodular function minimization that has seen numerous applications in machine learning. We develop fast techniques for instances where components in the sum are cardinality-based, meaning they depend only on the size of the input set. This variant is one of the most widely applied in practice, encompassing, e.g., common energy functions arising in image segmentation and recent generalized hypergraph cut functions. We develop the first approximation algorithms for this problem, where the approximations can be quickly computed via reduction to a sparse graph cut problem, with graph sparsity controlled by the desired approximation factor. Our method relies on a new connection between sparse graph reduction techniques and piecewise linear approximations to concave functions. Our sparse reduction technique leads to significant improvements in theoretical runtimes, as well as substantial practical gains in problems ranging from benchmark image segmentation tasks to hypergraph clustering problems.

The association between tie strength and social structure is a fundamental topic in the social sciences. We study this association by analyzing tie strength in higher-order networks, an increasingly relevant model which can encode group interactions between three or more individuals. First, we introduce three measures based on algebraic topology which characterize the network context and influence of an edge. Our experimental results across 15 datasets indicate that these measures outperform standard network proxies in estimating tie strength. We further find that these measures can replicate and explain a puzzle wherein certain bridging ties are surprisingly strong. We then consider a single centrality measure which combines the three initial measures, is highly inversely related to tie strength, and can be interpreted through an information exchange process which highlights ties that have access to useful information. In this sense, we are able to illuminate the information advantages of weak ties due to their network position.

A collection of over 3000 pages of emails sent by Anthony Fauci and his staff were released in an effort to understand the United States government response to the COVID-19 pandemic. We describe how this email data was translated into a resource consisting of json files that make many future studies easy. Findings from our processed data include (i) successful organizational partitions using the simple mincut techniques in Zachary's karate club methodology, (ii) a natural example where the normalized cut and minimum conductance set are extremely different, and (iii) organizational groups identified by optimum modularity clusters that illustrate a working hierarchy. These example uses suggest the data will be useful for future research and pedagogical uses in terms of human and system behavioral interactions. We explain a number of ways to turn email information into a network, a hypergraph, a temporal sequence, and a tensor for subsequent analysis as well as a few examples of such analysis., Comment: Code and data available from https://github.com/nveldt/fauci-email

Graphs are a common model for complex relational data such as social networks and protein interactions, and such data can evolve over time (e.g., new friendships) and be noisy (e.g., unmeasured interactions). Link prediction aims to predict future edges or infer missing edges in the graph, and has diverse applications in recommender systems, experimental design, and complex systems. Even though link prediction algorithms strongly depend on the set of edges in the graph, existing approaches typically do not modify the graph topology to improve performance. Here, we demonstrate how simply adding a set of edges, which we call a \emph{proposal set}, to the graph as a pre-processing step can improve the performance of several link prediction algorithms. The underlying idea is that if the edges in the proposal set generally align with the structure of the graph, link prediction algorithms are further guided towards predicting the right edges; in other words, adding a proposal set of edges is a signal-boosting pre-processing step. We show how to use existing link prediction algorithms to generate effective proposal sets and evaluate this approach on various synthetic and empirical datasets. We find that proposal sets meaningfully improve the accuracy of link prediction algorithms based on both neighborhood heuristics and graph neural networks. Code is available at \url{https://github.com/CUAI/Edge-Proposal-Sets}.

With the wide-spread availability of complex relational data, semi-supervised node classification in graphs has become a central machine learning problem. Graph neural networks are a recent class of easy-to-train and accurate methods for this problem that map the features in the neighborhood of a node to its label, but they ignore label correlation during inference and their predictions are difficult to interpret. On the other hand, collective classification is a traditional approach based on interpretable graphical models that explicitly model label correlations. Here, we introduce a model that combines the advantages of these two approaches, where we compute the marginal probabilities in a conditional random field, similar to collective classification, and the potentials in the random field are learned through end-to-end training, akin to graph neural networks. In our model, potentials on each node only depend on that node's features, and edge potentials are learned via a coupling matrix. This structure enables simple training with interpretable parameters, scales to large networks, naturally incorporates training labels at inference, and is often more accurate than related approaches. Our approach can be viewed as either an interpretable message-passing graph neural network or a collective classification method with higher capacity and modernized training.

Finding dense subgraphs of a large graph is a standard problem in graph mining that has been studied extensively both for its theoretical richness and its many practical applications. In this paper we introduce a new family of dense subgraph objectives, parameterized by a single parameter $p$, based on computing generalized means of degree sequences of a subgraph. Our objective captures both the standard densest subgraph problem and the maximum $k$-core as special cases, and provides a way to interpolate between and extrapolate beyond these two objectives when searching for other notions of dense subgraphs. In terms of algorithmic contributions, we first show that our objective can be minimized in polynomial time for all $p \geq 1$ using repeated submodular minimization. A major contribution of our work is analyzing the performance of different types of peeling algorithms for dense subgraphs both in theory and practice. We prove that the standard peeling algorithm can perform arbitrarily poorly on our generalized objective, but we then design a more sophisticated peeling method which for $p \geq 1$ has an approximation guarantee that is always at least $1/2$ and converges to 1 as $p \rightarrow \infty$. In practice, we show that this algorithm obtains extremely good approximations to the optimal solution, scales to large graphs, and highlights a range of different meaningful notions of density on graphs coming from numerous domains. Furthermore, it is typically able to approximate the densest subgraph problem better than the standard peeling algorithm, by better accounting for how the removal of one node affects other nodes in its neighborhood.

Standard methods in preference learning involve estimating the parameters of discrete choice models from data of selections (choices) made by individuals from a discrete set of alternatives (the choice set). While there are many models for individual preferences, existing learning methods overlook how choice set assignment affects the data. Often, the choice set itself is influenced by an individual's preferences; for instance, a consumer choosing a product from an online retailer is often presented with options from a recommender system that depend on information about the consumer's preferences. Ignoring these assignment mechanisms can mislead choice models into making biased estimates of preferences, a phenomenon that we call choice set confounding; we demonstrate the presence of such confounding in widely-used choice datasets. To address this issue, we adapt methods from causal inference to the discrete choice setting. We use covariates of the chooser for inverse probability weighting and/or regression controls, accurately recovering individual preferences in the presence of choice set confounding under certain assumptions. When such covariates are unavailable or inadequate, we develop methods that take advantage of structured choice set assignment to improve prediction. We demonstrate the effectiveness of our methods on real-world choice data, showing, for example, that accounting for choice set confounding makes choices observed in hotel booking and commute transportation more consistent with rational utility-maximization., Comment: 12 pages, KDD 2021 version

Hypergraphs are a common model for multiway relationships in data, and hypergraph semi-supervised learning is the problem of assigning labels to all nodes in a hypergraph, given labels on just a few nodes. Diffusions and label spreading are classical techniques for semi-supervised learning in the graph setting, and there are some standard ways to extend them to hypergraphs. However, these methods are linear models, and do not offer an obvious way of incorporating node features for making predictions. Here, we develop a nonlinear diffusion process on hypergraphs that spreads both features and labels following the hypergraph structure, which can be interpreted as a hypergraph equilibrium network. Even though the process is nonlinear, we show global convergence to a unique limiting point for a broad class of nonlinearities, which is the global optimum of a interpretable, regularized semi-supervised learning loss function. The limiting point serves as a node embedding from which we make predictions with a linear model. Our approach is much more accurate than several hypergraph neural networks, and also takes less time to train.

Homophily is the seemingly ubiquitous tendency for people to connect and interact with other individuals who are similar to them. This is a well-documented principle and is fundamental for how society organizes. Although many social interactions occur in groups, homophily has traditionally been measured using a graph model, which only accounts for pairwise interactions involving two individuals. Here, we develop a framework using hypergraphs to quantify homophily from group interactions. This reveals natural patterns of group homophily that appear with gender in scientific collaboration and political affiliation in legislative bill co-sponsorship, and also reveals distinctive gender distributions in group photographs, all of which cannot be fully captured by pairwise measures. At the same time, we show that seemingly natural ways to define group homophily are combinatorially impossible. This reveals important pitfalls to avoid when defining and interpreting notions of group homophily, as higher-order homophily patterns are governed by combinatorial constraints that are independent of human behavior but are easily overlooked.

Higher-order network analysis uses the ideas of hypergraphs, simplicial complexes, multilinear and tensor algebra, and more, to study complex systems. These are by now well established mathematical abstractions. What's new is that the ideas can be tested and refined on the type of large-scale data arising in today's digital world. This research area therefore is making an impact across many applications. Here, we provide a brief history, guide, and survey., Comment: Based on the SIAM News online article https://sinews.siam.org/Details-Page/higher-order-network-analysis-takes-off-fueled-by-old-ideas-and-new-data

The race to meet the challenges of the global pandemic has served as a reminder that the existing drug discovery process is expensive, inefficient and slow. There is a major bottleneck screening the vast number of potential small molecules to shortlist lead compounds for antiviral drug development. New opportunities to accelerate drug discovery lie at the interface between machine learning methods, in this case developed for linear accelerators, and physics-based methods. The two in silico methods, each have their own advantages and limitations which, interestingly, complement each other. Here, we present an innovative infrastructural development that combines both approaches to accelerate drug discovery. The scale of the potential resulting workflow is such that it is dependent on supercomputing to achieve extremely high throughput. We have demonstrated the viability of this workflow for the study of inhibitors for four COVID-19 target proteins and our ability to perform the required large-scale calculations to identify lead antiviral compounds through repurposing on a variety of supercomputers.

In the analysis of large-scale network data, a fundamental operation is the comparison of observed phenomena to the predictions provided by null models: when we find an interesting structure in a family of real networks, it is important to ask whether this structure is also likely to arise in random networks with similar characteristics to the real ones. A long-standing challenge in network analysis has been the relative scarcity of reasonable null models for networks; arguably the most common such model has been the configuration model, which starts with a graph $G$ and produces a random graph with the same node degrees as $G$. This leads to a very weak form of null model, since fixing the node degrees does not preserve many of the crucial properties of the network, including the structure of its subgraphs. Guided by this challenge, we propose a new family of network null models that operate on the $k$-core decomposition. For a graph $G$, the $k$-core is its maximal subgraph of minimum degree $k$; and the core number of a node $v$ in $G$ is the largest $k$ such that $v$ belongs to the $k$-core of $G$. We provide the first efficient sampling algorithm to solve the following basic combinatorial problem: given a graph $G$, produce a random graph sampled nearly uniformly from among all graphs with the same sequence of core numbers as $G$. This opens the opportunity to compare observed networks $G$ with random graphs that exhibit the same core numbers, a comparison that preserves aspects of the structure of $G$ that are not captured by more local measures like the degree sequence. We illustrate the power of this core-based null model on some fundamental tasks in network analysis, including the enumeration of networks motifs.

Hypergraphs are a natural modeling paradigm for a wide range of complex relational systems. A standard analysis task is to identify clusters of closely related or densely interconnected nodes. Many graph algorithms for this task are based on variants of the stochastic blockmodel, a random graph with flexible cluster structure. However, there are few models and algorithms for hypergraph clustering. Here, we propose a Poisson degree-corrected hypergraph stochastic blockmodel (DCHSBM), a generative model of clustered hypergraphs with heterogeneous node degrees and edge sizes. Approximate maximum-likelihood inference in the DCHSBM naturally leads to a clustering objective that generalizes the popular modularity objective for graphs. We derive a general Louvain-type algorithm for this objective, as well as a a faster, specialized "All-Or-Nothing" (AON) variant in which edges are expected to lie fully within clusters. This special case encompasses a recent proposal for modularity in hypergraphs, while also incorporating flexible resolution and edge-size parameters. We show that AON hypergraph Louvain is highly scalable, including as an example an experiment on a synthetic hypergraph of one million nodes. We also demonstrate through synthetic experiments that the detectability regimes for hypergraph community detection differ from methods based on dyadic graph projections. We use our generative model to analyze different patterns of higher-order structure in school contact networks, U.S. congressional bill cosponsorship, U.S. congressional committees, product categories in co-purchasing behavior, and hotel locations from web browsing sessions, finding interpretable higher-order structure. We then study the behavior of our AON hypergraph Louvain algorithm, finding that it is able to recover ground truth clusters in empirical data sets exhibiting the corresponding higher-order structure., Comment: 23 pages + 7 pages of supplementary information, 3 tables, 4 figures

Semi-supervised learning on graphs is a widely applicable problem in network science and machine learning. Two standard algorithms -- label propagation and graph neural networks -- both operate by repeatedly passing information along edges, the former by passing labels and the latter by passing node features, modulated by neural networks. These two types of algorithms have largely developed separately, and there is little understanding about the structure of network data that would make one of these approaches work particularly well compared to the other or when the approaches can be meaningfully combined. Here, we develop a Markov random field model for the data generation process of node attributes, based on correlations of attributes on and between vertices, that motivates and unifies these algorithmic approaches. We show that label propagation, a linearized graph convolutional network, and their combination can all be derived as conditional expectations under our model, when conditioning on different attributes. In addition, the data model highlights deficiencies in existing graph neural networks (while producing new algorithmic solutions), serves as a rigorous statistical framework for understanding graph learning issues such as over-smoothing, creates a testbed for evaluating inductive learning performance, and provides a way to sample graphs attributes that resemble empirical data. We also find that a new algorithm derived from our data generation model, which we call a Linear Graph Convolution, performs extremely well in practice on empirical data, and provide theoretical justification for why this is the case.

We present a new, stable, mixed finite element (FE) method for linear elastostatics of nearly incompressible solids. The method is the automatic variationally stable FE (AVS-FE) method of Calo, Romkes and Valseth, in which we consider a Petrov-Galerkin weak formulation where the stress and displacement variables are in the space H(div)xH1, respectively. This allows us to employ a fully conforming FE discretization for any elastic solid using classical FE subspaces of H(div) and H1. Hence, the resulting FE approximation yields both continuous stresses and displacements. To ensure stability of the method, we employ the philosophy of the discontinuous Petrov-Galerkin (DPG) method of Demkowicz and Gopalakrishnan and use optimal test spaces. Thus, the resulting FE discretization is stable even as the Poisson ratio approaches 0.5, and the system of linear algebraic equations is symmetric and positive definite. Our method also comes with a built-in a posteriori error estimator as well as well as indicators which are used to drive mesh adaptive refinements. We present several numerical verifications of our method including comparisons to existing FE technologies.

We demonstrate that deep learning techniques can be used to predict motility induced phase separation (MIPS) in suspensions of active Brownian particles (ABPs) by creating a notion of phase at the particle level. Using a fully connected network in conjunction with a graph neural network we use individual particle features to predict to which phase a particle belongs. From this, we are able to compute the fraction of dilute particles to determine if the system is in the homogeneous dilute, dense, or coexistence region. Our predictions are compared against the MIPS binodal computed from simulation. The strong agreement between the two suggests that machine learning provides an effective way to determine the phase behavior of ABPs and could prove useful for determining more complex phase diagrams.

We draw connections between simple neural networks and under-determined linear systems to comprehensively explore several interesting theoretical questions in the study of neural networks. First, we emphatically show that it is unsurprising such networks can achieve zero training loss. More specifically, we provide lower bounds on the width of a single hidden layer neural network such that only training the last linear layer suffices to reach zero training loss. Our lower bounds grow more slowly with data set size than existing work that trains the hidden layer weights. Second, we show that kernels typically associated with the ReLU activation function have fundamental flaws -- there are simple data sets where it is impossible for widely studied bias-free models to achieve zero training loss irrespective of how the parameters are chosen or trained. Lastly, our analysis of gradient descent clearly illustrates how spectral properties of certain matrices impact both the early iteration and long-term training behavior. We propose new activation functions that avoid the pitfalls of ReLU in that they admit zero training loss solutions for any set of distinct data points and experimentally exhibit favorable spectral properties., Comment: 25 pages, 4 figures

Graph Neural Networks (GNNs) are the predominant technique for learning over graphs. However, there is relatively little understanding of why GNNs are successful in practice and whether they are necessary for good performance. Here, we show that for many standard transductive node classification benchmarks, we can exceed or match the performance of state-of-the-art GNNs by combining shallow models that ignore the graph structure with two simple post-processing steps that exploit correlation in the label structure: (i) an "error correlation" that spreads residual errors in training data to correct errors in test data and (ii) a "prediction correlation" that smooths the predictions on the test data. We call this overall procedure Correct and Smooth (C&S), and the post-processing steps are implemented via simple modifications to standard label propagation techniques from early graph-based semi-supervised learning methods. Our approach exceeds or nearly matches the performance of state-of-the-art GNNs on a wide variety of benchmarks, with just a small fraction of the parameters and orders of magnitude faster runtime. For instance, we exceed the best known GNN performance on the OGB-Products dataset with 137 times fewer parameters and greater than 100 times less training time. The performance of our methods highlights how directly incorporating label information into the learning algorithm (as was done in traditional techniques) yields easy and substantial performance gains. We can also incorporate our techniques into big GNN models, providing modest gains. Our code for the OGB results is at https://github.com/Chillee/CorrectAndSmooth.

Flexible loads are a resource for the Balancing Authority (BA) of the future to aid in the balance of power supply and demand. In order to be used as a resource, the BA must know the capacity of the flexible loads to vary their power demand over a baseline without violating consumers' quality of service (QoS). Existing work on capacity characterization is model-based: They need models relating power consumption to variables that dictate QoS, such as temperature in case of an air conditioning system. However, in many cases the model parameters are not known or difficult to obtain. In this work, we pose a data driven capacity characterization method that does not require model information, it only needs access to a simulator. The capacity is characterized as the set of feasible spectral densities (SDs) of the demand deviation. The proposed method is an extension of our recent work on SD-based capacity characterization that was limited to linear time invariant (LTI) dynamics of loads. The method proposed here is applicable to nonlinear dynamics. Numerical evaluation of the method is provided, including a comparison with the model-based solution for the LTI case., Comment: 8 pages. arXiv admin note: text overlap with arXiv:2005.01591

Thermostatically controlled loads (TCLs) have the potential to be a valuable resource for the Balancing Authority (BA) of the future. Examples of TCLs include household appliances such as air conditioners, water heaters, and refrigerators. Since the rated power of each TCL is on the order of kilowatts, to provide meaningful service for the BA, it is necessary to control large collections of TCLs. To perform design of a distributed coordination/control algorithm, the BA requires a control oriented model that describes the relevant dynamics of an ensemble. Works focusing on solely modeling the ensemble date back to the 1980's, while works focusing on control oriented modeling are more recent. In this work, we contribute to the control oriented modeling literature. We leverage techniques from computational fluid dynamics (CFD) to discretize a pair of Fokker-Planck equations derived in earlier work [1]. The discretized equations are shown to admit a certain factorization, which makes the developed model useful for control design. In particular, the effects of weather and control are shown to independently effect the system dynamics., Comment: 9 pages, 5 figures

We demonstrate that the mechanically-defined "isothermal" compressibility behaves as a thermodynamic-like response function for suspensions of active Brownian particles. The compressibility computed from the active pressure - a combination of the collision and unique swim pressures - is capable of predicting the critical point for motility induced phase separation, as expected from the mechanical stability criterion. We relate this mechanical definition to the static structure factor via an active form of the thermodynamic compressibility equation and find the two to be equivalent, as would be the case for equilibrium systems. This equivalence indicates that compressibility behaves like a thermodynamic response function, even when activity is large. Finally, we discuss the importance of the phase interface when defining an active chemical potential. Previous definitions of the active chemical potential are shown to be accurate above the critical point but breakdown in the coexistence region. Inclusion of the swim pressure in the mechanical compressibility definition suggests that the interface is essential for determining phase behavior.

The outcomes of elections, product sales, and the structure of social connections are all determined by the choices individuals make when presented with a set of options, so understanding the factors that contribute to choice is crucial. Of particular interest are context effects, which occur when the set of available options influences a chooser's relative preferences, as they violate traditional rationality assumptions yet are widespread in practice. However, identifying these effects from observed choices is challenging, often requiring foreknowledge of the effect to be measured. In contrast, we provide a method for the automatic discovery of a broad class of context effects from observed choice data. Our models are easier to train and more flexible than existing models and also yield intuitive, interpretable, and statistically testable context effects. Using our models, we identify new context effects in widely used choice datasets and provide the first analysis of choice set context effects in social network growth., Comment: 20 pages, 4 figures; updated results after bug fix

Distributed computing is a standard way to scale up machine learning and data science algorithms to process large amounts of data. In such settings, avoiding communication amongst machines is paramount for achieving high performance. Rather than distribute the computation of existing algorithms, a common practice for avoiding communication is to compute local solutions or parameter estimates on each machine and then combine the results; in many convex optimization problems, even simple averaging of local solutions can work well. However, these schemes do not work when the local solutions are not unique. Spectral methods are a collection of such problems, where solutions are orthonormal bases of the leading invariant subspace of an associated data matrix, which are only unique up to rotation and reflections. Here, we develop a communication-efficient distributed algorithm for computing the leading invariant subspace of a data matrix. Our algorithm uses a novel alignment scheme that minimizes the Procrustean distance between local solutions and a reference solution, and only requires a single round of communication. For the important case of principal component analysis (PCA), we show that our algorithm achieves a similar error rate to that of a centralized estimator. We present numerical experiments demonstrating the efficacy of our proposed algorithm for distributed PCA, as well as other problems where solutions exhibit rotational symmetry, such as node embeddings for graph data and spectral initialization for quadratic sensing., Comment: v2: Removes unnecessary assumption, fixes typo in Theorem 3. 39 pages, 10 figures

Background: Neutron-rich nuclei around neutron number N = 60 show a dramatic shape transition from spherical ground states to prolate deformation in 98Sr and heavier nuclei. Purpose: The purpose of this study is to investigate the single-particle structure approaching the shape transitional region. Method: The level structures of neutron-rich 93,94,95Sr were studied via the d(94,95,96Sr,t) one-neutron stripping reactions at TRIUMF using a beam energy of 5.5 AMeV. {\gamma}-rays emitted from excited states and recoiling charged particles were detected by using the TIGRESS and SHARC arrays, respectively. States were identified by gating on the excitation energy and, if possible, the coincident {\gamma} radiation. Results: Triton angular distributions for the reactions populating states in ejectile nuclei 93,94,95Sr were compared with distorted wave Born approximation calculations to assign and revise spin and parity quantum numbers and extract spectroscopic factors. The results were compared with shell model calculations and the reverse (d,p) reactions and good agreement was obtained. Conclusions: The results for the d(94Sr,t)93Sr and d(95Sr,t)94Sr reactions are in good agreement with shell model calculations. A two level mixing analysis for the 0+ states in 94Sr suggest strong mixing of two shapes. For the d(96Sr,t)95Sr reaction the agreement with the shell model is less good. The configuration of the ground state of 96Sr is already more complex than predicted, and therefore indications for the shape transition can already be observed before N = 60., Comment: accepted for publication in PRC

In recent years, hypergraph generalizations of many graph cut problems have been introduced and analyzed as a way to better explore and understand complex systems and datasets characterized by multiway relationships. Recent work has made use of a generalized hypergraph cut function which for a hypergraph $\mathcal{H} = (V,E)$ can be defined by associating each hyperedge $e \in E$ with a splitting function ${\bf w}_e$, which assigns a penalty to each way of separating the nodes of $e$. When each ${\bf w}_e$ is a submodular cardinality-based splitting function, meaning that ${\bf w}_e(S) = g(|S|)$ for some concave function $g$, previous work has shown that a generalized hypergraph cut problem can be reduced to a directed graph cut problem on an augmented node set. However, existing reduction procedures often result in a dense graph, even when the hypergraph is sparse, which leads to slow runtimes for algorithms that run on the reduced graph. We introduce a new framework of sparsifying hypergraph-to-graph reductions, where a hypergraph cut defined by submodular cardinality-based splitting functions is $(1+\varepsilon)$-approximated by a cut on a directed graph. Our techniques are based on approximating concave functions using piecewise linear curves. For $\varepsilon > 0$ we need at most $O(\varepsilon^{-1}|e| \log |e|)$ edges to reduce any hyperedge $e$, which leads to faster runtimes for approximating generalized hypergraph $s$-$t$ cut problems. For the machine learning heuristic of a clique splitting function, our approach requires only $O(|e| \varepsilon^{-1/2} \log \log \frac{1}{\varepsilon})$ edges. This sparsification leads to faster approximate min $s$-$t$ graph cut algorithms for certain classes of co-occurrence graphs. Finally, we apply our sparsification techniques to develop approximation algorithms for minimizing sums of cardinality-based submodular functions.

Graph datasets are frequently constructed by a projection of a bipartite graph, where two nodes are connected in the projection if they share a common neighbor in the bipartite graph; for example, a coauthorship graph is a projection of an author-publication bipartite graph. Analyzing the structure of the projected graph is common, but we do not have a good understanding of the consequences of the projection on such analyses. Here, we propose and analyze a random graph model to study what properties we can expect from the projection step. Our model is based on a Chung-Lu random graph for constructing the bipartite representation, which enables us to rigorously analyze the projected graph. We show that common network properties such as sparsity, heavy-tailed degree distributions, local clustering at nodes, the inverse relationship between node degree, and global transitivity can be explained and analyzed through this simple model. We also develop a fast sampling algorithm for our model, which we show is provably optimal for certain input distributions. Numerical simulations where model parameters come from real-world datasets show that much of the clustering behavior in some datasets can just be explained by the projection step.

Loads that can vary their power consumption without violating their Quality of service (QoS), that is flexible loads, are an invaluable resource for grid operators. Utilizing flexible loads as a resource requires the grid operator to incorporate them into a resource allocation problem. Since flexible loads are often consumers, for concerns of privacy it is desirable for this problem to have a distributed implementation. Technically, this distributed implementation manifests itself as a time varying convex optimization problem constrained by the QoS of each load. In the literature, a time invariant form of this problem without all of the necessary QoS metrics for the flexible loads is often considered. Moving to a more realistic setup introduces additional technical challenges, due to the problems' time-varying nature. In this work, we develop an algorithm to account for the challenges introduced when considering a time varying setup with appropriate QoS metrics., Comment: 8 pages, 3 figures

Many platforms collect crowdsourced information primarily from volunteers. As this type of knowledge curation has become widespread, contribution formats vary substantially and are driven by diverse processes across differing platforms. Thus, models for one platform are not necessarily applicable to others. Here, we study the temporal dynamics of Genius, a platform primarily designed for user-contributed annotations of song lyrics. A unique aspect of Genius is that the annotations are extremely local -- an annotated lyric may just be a few lines of a song -- but also highly related, e.g., by song, album, artist, or genre. We analyze several dynamical processes associated with lyric annotations and their edits, which differ substantially from models for other platforms. For example, expertise on song annotations follows a "U shape" where experts are both early and late contributors with non-experts contributing intermediately; we develop a user utility model that captures such behavior. We also find several contribution traits appearing early in a user's lifespan of contributions that distinguish (eventual) experts from non-experts. Combining our findings, we develop a model for early prediction of user expertise., Comment: 12 pages. 10 figures

When forming a team or group of individuals, we often seek a balance of expertise in a particular task while at the same time maintaining diversity of skills within each group. Here, we view the problem of finding diverse and experienced groups as clustering in hypergraphs with multiple edge types. The input data is a hypergraph with multiple hyperedge types -- representing information about past experiences of groups of individuals -- and the output is groups of nodes. In contrast to related problems on fair or balanced clustering, we model diversity in terms of variety of past experience (instead of, e.g., protected attributes), with a goal of forming groups that have both experience and diversity with respect to participation in edge types. In other words, both diversity and experience are measured from the types of the hyperedges. Our clustering model is based on a regularized version of an edge-based hypergraph clustering objective, and we also show how naive objectives actually have no diversity-experience tradeoff. Although our objective function is NP-hard to optimize, we design an efficient 2-approximation algorithm and also show how to compute bounds for the regularization hyperparameter that lead to meaningful diversity-experience tradeoffs. We demonstrate an application of this framework in online review platforms, where the goal is to curate sets of user reviews for a product type. In this context, "experience" corresponds to users familiar with the type of product, and "diversity" to users that have reviewed related products., Comment: Added new experiments and refocused around diversity

Label spreading is a general technique for semi-supervised learning with point cloud or network data, which can be interpreted as a diffusion of labels on a graph. While there are many variants of label spreading, nearly all of them are linear models, where the incoming information to a node is a weighted sum of information from neighboring nodes. Here, we add nonlinearity to label spreading through nonlinear functions of higher-order structure in the graph, namely triangles in the graph. For a broad class of nonlinear functions, we prove convergence of our nonlinear higher-order label spreading algorithm to the global solution of a constrained semi-supervised loss function. We demonstrate the efficiency and efficacy of our approach on a variety of point cloud and network datasets, where the nonlinear higher-order model compares favorably to classical label spreading, as well as hypergraph models and graph neural networks.

In its application to the modeling of a mineral separation process, we propose the numerical analysis of the Cahn-Hilliard equation by employing spacetime discretizations of the automatic variationally stable finite element (AVS-FE) method. The AVS-FE method is a Petrov-Galerkin method which employs the concept of optimal discontinuous test functions of the discontinuous Petrov-Galerkin (DPG) method by Demkowicz and Gopalakrishnan. The trial space, however, consists of globally continuous Hilbert spaces such as H1 and H(div). Hence, the AVS-FE approximations employ classical C0 or Raviart-Thomas FE basis functions. The optimal test functions guarantee the numerical stability of the AVS-FE method and lead to discrete systems that are symmetric and positive definite. Hence, the AVS-FE method can solve the Cahn-Hilliard equation in both space and time without a restrictive CFL condition to dictate the space-time element size. We present numerical verifications of both one and two dimensional problems in space. The verifications show optimal rates of convergence in L2 and H1 norms. Results for mesh adaptive refinements using a built-in error estimator of the AVS-FE method are also presented.

Flexible loads are a resource for the Balancing Authority (BA) of the future to aid in the balance of supply and demand in the power grid. Consequently, it is of interest for a BA to know how much flexibility a collection of loads has, so to successfully incorporate flexible loads into grid level resource allocation. Loads' flexibility is limited by all their Quality of Service (QoS) requirements. In this work we present a characterization of capacity for a collection of flexible loads. This characterization is in terms of the Power Spectral Density (PSD) of the reference signal. Two advantages of our characterization are: (i) it easily allows for a BA to use the characterization for resource allocation of flexible loads and (ii) it allows for precise definitions of the power and energy capacity for a collection of flexible loads., Comment: 9 pages, 11 figures

There is inherent information captured in the order in which we write words in a list. The orderings of binomials --- lists of two words separated by `and' or `or' --- has been studied for more than a century. These binomials are common across many areas of speech, in both formal and informal text. In the last century, numerous explanations have been given to describe what order people use for these binomials, from differences in semantics to differences in phonology. These rules describe primarily `frozen' binomials that exist in exactly one ordering and have lacked large-scale trials to determine efficacy. Online text provides a unique opportunity to study these lists in the context of informal text at a very large scale. In this work, we expand the view of binomials to include a large-scale analysis of both frozen and non-frozen binomials in a quantitative way. Using this data, we then demonstrate that most previously proposed rules are ineffective at predicting binomial ordering. By tracking the order of these binomials across time and communities we are able to establish additional, unexplored dimensions central to these predictions. Expanding beyond the question of individual binomials, we also explore the global structure of binomials in various communities, establishing a new model for these lists and analyzing this structure for non-frozen and frozen binomials. Additionally, novel analysis of trinomials --- lists of length three --- suggests that none of the binomials analysis applies in these cases. Finally, we demonstrate how large data sets gleaned from the web can be used in conjunction with older theories to expand and improve on old questions., Comment: 12 pages, 10 figures

Hypergraphs are a useful abstraction for modeling multiway relationships in data, and hypergraph clustering is the task of detecting groups of closely related nodes in such data. Graph clustering has been studied extensively, and there are numerous methods for detecting small, localized clusters without having to explore an entire input graph. However, there are only a few specialized approaches for localized clustering in hypergraphs. Here we present a framework for local hypergraph clustering based on minimizing localized ratio cut objectives. Our framework takes an input set of reference nodes in a hypergraph and solves a sequence of hypergraph minimum $s$-$t$ cut problems in order to identify a nearby well-connected cluster of nodes that overlaps substantially with the input set. Our methods extend graph-based techniques but are significantly more general and have new output quality guarantees. First, our methods can minimize new generalized notions of hypergraph cuts, which depend on specific configurations of nodes within each hyperedge, rather than just on the number of cut hyperedges. Second, our framework has several attractive theoretical properties in terms of output cluster quality. Most importantly, our algorithm is strongly-local, meaning that its runtime depends only on the size of the input set, and does not need to explore the entire hypergraph to find good local clusters. We use our methodology to effectively identify clusters in hypergraphs of real-world data with millions of nodes, millions of hyperedges, and large average hyperedge size with runtimes ranging between a few seconds and a few minutes.

A graph neural network transforms features in each vertex's neighborhood into a vector representation of the vertex. Afterward, each vertex's representation is used independently for predicting its label. This standard pipeline implicitly assumes that vertex labels are conditionally independent given their neighborhood features. However, this is a strong assumption, and we show that it is far from true on many real-world graph datasets. Focusing on regression tasks, we find that this conditional independence assumption severely limits predictive power. This should not be that surprising, given that traditional graph-based semi-supervised learning methods such as label propagation work in the opposite fashion by explicitly modeling the correlation in predicted outcomes. Here, we address this problem with an interpretable and efficient framework that can improve any graph neural network architecture simply by exploiting correlation structure in the regression residuals. In particular, we model the joint distribution of residuals on vertices with a parameterized multivariate Gaussian, and estimate the parameters by maximizing the marginal likelihood of the observed labels. Our framework achieves substantially higher accuracy than competing baselines, and the learned parameters can be interpreted as the strength of correlation among connected vertices. Furthermore, we develop linear time algorithms for low-variance, unbiased model parameter estimates, allowing us to scale to large networks. We also provide a basic version of our method that makes stronger assumptions on correlation structure but is painless to implement, often leading to great practical performance with minimal overhead.

Several problems in machine learning, statistics, and other fields rely on computing eigenvectors. For large scale problems, the computation of these eigenvectors is typically performed via iterative schemes such as subspace iteration or Krylov methods. While there is classical and comprehensive analysis for subspace convergence guarantees with respect to the spectral norm, in many modern applications other notions of subspace distance are more appropriate. Recent theoretical work has focused on perturbations of subspaces measured in the $\ell_{2 \to \infty}$ norm, but does not consider the actual computation of eigenvectors. Here we address the convergence of subspace iteration when distances are measured in the $\ell_{2 \to \infty}$ norm and provide deterministic bounds. We complement our analysis with a practical stopping criterion and demonstrate its applicability via numerical experiments. Our results show that one can get comparable performance on downstream tasks while requiring fewer iterations, thereby saving substantial computational time., Comment: 21 pages, 8 figures. To appear in the 34th Conference on Neural Information Processing Systems (NeurIPS 2020)

The way that people make choices or exhibit preferences can be strongly affected by the set of available alternatives, often called the choice set. Furthermore, there are usually heterogeneous preferences, either at an individual level within small groups or within sub-populations of large groups. Given the availability of choice data, there are now many models that capture this behavior in order to make effective predictions--however, there is little work in understanding how directly changing the choice set can be used to influence the preferences of a collection of decision-makers. Here, we use discrete choice modeling to develop an optimization framework of such interventions for several problems of group influence, namely maximizing agreement or disagreement and promoting a particular choice. We show that these problems are NP-hard in general, but imposing restrictions reveals a fundamental boundary: promoting a choice can be easier than encouraging consensus or sowing discord. We design approximation algorithms for the hard problems and show that they work well on real-world choice data., Comment: 19 pages, 7 figures. ICML 2020. This is an updated version after reviews

An aggregate model is a single-zone equivalent of a multi-zone building, and is useful for many purposes, including model based control of large heating, ventilation and air conditioning (HVAC) equipment. This paper deals with the problem of simultaneously identifying an aggregate thermal dynamic model and unknown disturbances from input-output data. The unknown disturbance is a key challenge since it is not measurable but non-negligible. We first present a principled method to aggregate a multi-zone building model into a single zone model, and show the aggregation is not as trivial as it has been assumed in the prior art. We then provide a method to identify the parameters of the model and the unknown disturbance for this aggregate (single-zone) model. Finally, we test our proposed identification algorithm to data collected from a multi-zone building testbed in Oak Ridge National Laboratory. A key insight provided by the aggregation method allows us to recognize under what conditions the estimation of the disturbance signal will be necessarily poor and uncertain, even in the case of a specially designed test in which the disturbances affecting each zone are known (as the case of our experimental testbed). This insight is used to provide a heuristic that can be used to assess when the identification results are likely to have high or low accuracy., Comment: 10 pages, 15 figures

The minimum $s$-$t$ cut problem in graphs is one of the most fundamental problems in combinatorial optimization, and graph cuts underlie algorithms throughout discrete mathematics, theoretical computer science, operations research, and data science. While graphs are a standard model for pairwise relationships, hypergraphs provide the flexibility to model multi-way relationships, and are now a standard model for complex data and systems. However, when generalizing from graphs to hypergraphs, the notion of a "cut hyperedge" is less clear, as a hyperedge's nodes can be split in several ways. Here, we develop a framework for hypergraph cuts by considering the problem of separating two terminal nodes in a hypergraph in a way that minimizes a sum of penalties at split hyperedges. In our setup, different ways of splitting the same hyperedge have different penalties, and the penalty is encoded by what we call a splitting function. Our framework opens a rich space on the foundations of hypergraph cuts. We first identify a natural class of cardinality-based hyperedge splitting functions that depend only on the number of nodes on each side of the split. In this case, we show that the general hypergraph $s$-$t$ cut problem can be reduced to a tractable graph $s$-$t$ cut problem if and only if the splitting functions are submodular. We also identify a wide regime of non-submodular splitting functions for which the problem is NP-hard. We also analyze extensions to multiway cuts with at least three terminal nodes and identify a natural class of splitting functions for which the problem can be reduced in an approximation-preserving way to the node-weighted multiway cut problem in graphs, again subject to a submodularity property. Finally, we outline several open questions on general hypergraph cut problems.