More Like this

1. When Sets Can and Cannot Have MSTD Subsets

   Chu, Hung ; McNew, Nathan ; Miller, Steven J ; Xu, Victor ; Zhang, Sean ( January 2018 , Journal of integer sequences)

   A finite set of integers A is a sum-dominant (also called a More Sums Than Differences or MSTD) set if |A+A| > |A−A|. While almost all subsets of {0, . . . , n} are not sum-dominant, interestingly a small positive percentage are. We explore sufficient conditions on infinite sets of positive integers such that there are either no sum-dominant subsets, at most finitely many sum-dominant subsets, or infinitely many sum-dominant subsets. In particular, we prove no subset of the Fibonacci numbers is a sum-dominant set, establish conditions such that solutions to a recurrence relation have only finitely many sum-dominant subsets, and show there are infinitely many sum-dominant subsets of the primes. 

   more » « less
2. Can Graph Neural Networks Count Substructures?

   Zhengdao, Chen ; Lei, Chen ; Soledad, Villar ; Bruna, Joan ( December 2020 , Advances in neural information processing systems)

   null (Ed.)

   The ability to detect and count certain substructures in graphs is important for solving many tasks on graph-structured data, especially in the contexts of computa- tional chemistry and biology as well as social network analysis. Inspired by this, we propose to study the expressive power of graph neural networks (GNNs) via their ability to count attributed graph substructures, extending recent works that examine their power in graph isomorphism testing and function approximation. We distinguish between two types of substructure counting: induced-subgraph-count and subgraph-count, and establish both positive and negative answers for popular GNN architectures. Specifically, we prove that Message Passing Neural Networks (MPNNs), 2-Weisfeiler-Lehman (2-WL) and 2-Invariant Graph Networks (2-IGNs) cannot perform induced-subgraph-count of any connected substructure consisting of 3 or more nodes, while they can perform subgraph-count of star-shaped sub- structures. As an intermediary step, we prove that 2-WL and 2-IGNs are equivalent in distinguishing non-isomorphic graphs, partly answering an open problem raised in [38]. We also prove positive results for k-WL and k-IGNs as well as negative results for k-WL with a finite number of iterations. We then conduct experiments that support the theoretical results for MPNNs and 2-IGNs. Moreover, motivated by substructure counting and inspired by [45], we propose the Local Relational Pooling model and demonstrate that it is not only effective for substructure counting but also able to achieve competitive performance on molecular prediction tasks. 

   more » « less
3. Domain Adaptation in Physical Systems via Graph Kernel

   https://doi.org/10.1145/3534678.3539380  

   Li, Haoran ; Tong, Hanghang ; Weng, Yang ( August 2022 , KDD)

   Physical systems are extending their monitoring capacities to edge areas with low-cost, low-power sensors and advanced data mining and machine learning techniques. However, new systems often have limited data for training the model, calling for effective knowledge transfer from other relevant grids. Specifically, Domain Adaptation (DA) seeks domain-invariant features to boost the model performance in the target domain. Nonetheless, existing DA techniques face significant challenges due to the unique characteristics of physical datasets: (1) complex spatial-temporal correlations, (2) diverse data sources including node/edge measurements and labels, and (3) large-scale data sizes. In this paper, we propose a novel cross-graph DA based on two core designs of graph kernels and graph coarsening. The former design handles spatial-temporal correlations and can incorporate networked measurements and labels conveniently. The spatial structures, temporal trends, measurement similarity, and label information together determine the similarity of two graphs, guiding the DA to find domain-invariant features. Mathematically, we construct a Graph kerNel-based distribution Adaptation (GNA) with a specifically-designed graph kernel. Then, we prove the proposed kernel is positive definite and universal, which strictly guarantees the feasibility of the used DA measure. However, the computation cost of the kernel is prohibitive for large systems. In response, we propose a novel coarsening process to obtain much smaller graphs for GNA. Finally, we report the superiority of GNA in diversified systems, including power systems, mass-damper systems, and human-activity sensing systems. 

   more » « less
4. Invariant measures in simple and in small theories

   https://doi.org/10.1142/S0219061322500258  

   Chernikov, Artem ; Hrushovski, Ehud ; Kruckman, Alex ; Krupiński, Krzysztof ; Moconja, Slavko ; Pillay, Anand ; Ramsey, Nicholas ( August 2023 , Journal of Mathematical Logic)

   We give examples of (i) a simple theory with a formula (with parameters) which does not fork over [Formula: see text] but has [Formula: see text]-measure 0 for every automorphism invariant Keisler measure [Formula: see text] and (ii) a definable group [Formula: see text] in a simple theory such that [Formula: see text] is not definably amenable, i.e. there is no translation invariant Keisler measure on [Formula: see text]. We also discuss paradoxical decompositions both in the setting of discrete groups and of definable groups, and prove some positive results about small theories, including the definable amenability of definable groups. 

   more » « less
5. Landscape complexity beyond invariance and the elastic manifold

   https://doi.org/10.1002/cpa.22146  

   Ben Arous, Gérard ; Bourgade, Paul ; McKenna, Benjamin ( September 2023 , Communications on Pure and Applied Mathematics)

   This paper characterizes the annealed, topological complexity (both of total critical points and of local minima) of the elastic manifold. This classical model of a disordered elastic system captures point configurations with self‐interactions in a random medium. We establish the simple versus glassy phase diagram in the model parameters, with these phases separated by a physical boundary known as the Larkin mass, confirming formulas of Fyodorov and Le Doussal. One essential, dynamical, step of the proof also applies to a general signal‐to‐noise model of soft spins in an anisotropic well, for which we prove a negative‐second‐moment threshold distinguishing positive from zero complexity. A universal near‐critical behavior appears within this phase portrait, namely quadratic near‐critical vanishing of the complexity of total critical points, and cubic near‐critical vanishing of the complexity of local minima. These two models serve as a paradigm of complexity calculations for Gaussian landscapes exhibiting few distributional symmetries, that is, beyond the invariant setting. The two main inputs for the proof are determinant asymptotics for non‐invariant random matrices from our companion paper (Ben Arous, Bourgade, McKenna 2022), and the atypical convexity and integrability of the limiting variational problems.

    

   more » « less