More Like this

1. 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
2. Capture of field stars by dark substructures

   https://doi.org/10.1093/mnras/stae1961  

   Peñarrubia, Jorge; Errani, Raphaël; Walker, Matthew G; Gieles, Mark; Boekholt, Tjarda_C N (August 2024, Monthly Notices of the Royal Astronomical Society)

   ABSTRACT We use analytical and N-body methods to study the capture of field stars by gravitating substructures moving across a galactic environment. The majority of stars captured by a substructure move on temporarily bound orbits that are lost to galactic tides after a few orbital revolutions. In numerical experiments where a substructure model is immersed into a sea of field particles on a circular orbit, we find a population of particles that remain bound to the substructure potential for indefinitely long times. This population is absent from substructure models, initially placed outside the galaxy on an eccentric orbit. We show that gravitational capture is most efficient in dwarf spheroidal galaxies (dSphs) on account of their low velocity dispersions and high stellar phase-space densities. In these galaxies, ‘dark’ sub-subhaloes, which do not experience in situ star formation, may capture field stars and become visible as stellar overdensities with unusual properties: (i) they would have a large size for their luminosity, (ii) contain stellar populations indistinguishable from the host galaxy, and (iii) exhibit dark matter (DM)-dominated mass-to-light ratios. We discuss the nature of several ‘anomalous’ stellar systems reported as star clusters in the Fornax and Eridanus II dSphs that exhibit some of these characteristics. DM sub-subhaloes with a mass function $${\rm d}N/{\rm d}M_\bullet \sim M_\bullet ^{-\alpha }$$ are expected to generate stellar systems with a luminosity function, $${\rm d}N/{\rm d}M_\star \sim M_\star ^{-\beta }$$, where $$\beta =(2\alpha +1)/3=1.6$$ for $$\alpha =1.9$$. Detecting and characterizing these objects in dSphs would provide unprecedented constraints on the particle mass and cross-section of a large range of DM particle candidates. 

   more » « less
3. Finding Substructures in Protostellar Disks in Ophiuchus

   https://doi.org/10.3847/1538-3881/acf653  

   Michel, Arnaud; Sadavoy, Sarah I; Sheehan, Patrick D; Looney, Leslie W; Cox, Erin G; Tobin, John J; van_der_Marel, Nienke; Segura-Cox, Dominique M (October 2023, The Astronomical Journal)

   Abstract High-resolution, millimeter observations of disks at the protoplanetary stage reveal substructures such as gaps, rings, arcs, spirals, and cavities. While many protoplanetary disks host such substructures, only a few at the younger protostellar stage have shown similar features. We present a detailed search for early disk substructures in Atacama Large Millimeter/submillimeter Array 1.3 and 0.87 mm observations of ten protostellar disks in the Ophiuchus star-forming region. Of this sample, four disks have identified substructure, two appear to be smooth disks, and four are considered ambiguous. The structured disks have wide Gaussian-like rings (σ_R/R_disk∼ 0.26) with low contrasts (C< 0.2) above a smooth disk profile, in comparison to protoplanetary disks where rings tend to be narrow and have a wide variety of contrasts (σ_R/R_disk∼ 0.08 andCranges from 0 to 1). The four protostellar disks with the identified substructures are among the brightest sources in the Ophiuchus sample, in agreement with trends observed for protoplanetary disks. These observations indicate that substructures in protostellar disks may be common in brighter disks. The presence of substructures at the earliest stages suggests an early start for dust grain growth and, subsequently, planet formation. The evolution of these protostellar substructures is hypothesized in two potential pathways: (1) the rings are the sites of early planet formation, and the later observed protoplanetary disk ring–gap pairs are secondary features, or (2) the rings evolve over the disk lifetime to become those observed at the protoplanetary disk stage. 

   more » « less
4. Factorization for substructures of boosted Higgs jets

   https://doi.org/10.1016/j.physletb.2017.05.089  

   Isaacson, Joshua; Li, Hsiang-nan; Li, Zhao; Yuan, C.-P. (August 2017, Physics Letters B)
5. Multi-Objective Molecule Generation using Interpretable Substructures

   Jin, Wengong; Barzilay, Regina; Jaakkola, Tommi (January 2020, Proceedings of the 37th International Conference on Machine Learning)