skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Barriers for the performance of graph neural networks (GNN) in discrete random structures
Recently, graph neural network (GNN)-based algorithms were proposed to solve a variety of combinatorial optimization problems [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber,Nat. Mach. Intell.4, 367–377 (2022)]. GNN was tested in particular on randomly generated instances of these problems. The publication [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber,Nat. Mach. Intell.4, 367–377 (2022)] stirred a debate whether the GNN-based method was adequately benchmarked against best prior methods. In particular, critical commentaries [M. C. Angelini, F. Ricci-Tersenghi,Nat. Mach. Intell.5, 29–31 (2023)] and [S. Boettcher,Nat. Mach. Intell.5, 24–25 (2023)] point out that a simple greedy algorithm performs better than the GNN. We do not intend to discuss the merits of arguments and counterarguments in these papers. Rather, in this note, we establish a fundamental limitation for running GNN on random instances considered in these references, for a broad range of choices of GNN architecture. Specifically, these barriers hold when the depth of GNN does not scale with graph size (we note that depth 2 was used in experiments in [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber,Nat. Mach. Intell.4, 367–377 (2022)]), and importantly, these barriers hold regardless of any other parameters of GNN architecture. These limitations arise from the presence of the overlap gap property (OGP) phase transition, which is a barrier for many algorithms, including importantly local algorithms, of which GNN is an example. At the same time, some algorithms known prior to the introduction of GNN provide best results for these problems up to the OGP phase transition. This leaves very little space for GNN to outperform the known algorithms, and based on this, we side with the conclusions made in [M. C. Angelini, F. Ricci-Tersenghi,Nat. Mach. Intell.5, 29–31 (2023)] and [S. Boettcher,Nat. Mach. Intell.5, 24–25 (2023)].  more » « less
Award ID(s):
2233897
PAR ID:
10495061
Author(s) / Creator(s):
Publisher / Repository:
National Academy of Science
Date Published:
Journal Name:
Proceedings of the National Academy of Sciences
Volume:
120
Issue:
46
ISSN:
0027-8424
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, ECS Meeting Abstracts)
    It has been challenging to synthesize p-type SnOx(1≤x<2) and engineer the electrical properties such as carrier density and mobility due to the narrow processing window and the localized oxygen 2p orbitals near the valence band. We recently reported on the processing of p-type SnOx and an oxide-based p-n heterostructures, demonstrating high on/off rectification ratio (>103), small turn-on voltage (<0.5 V), and low saturation current (~1×10-10A)1. In order to further understand the p-type oxide and engineer the properties for various electronic device applications, it is important to identify (or establish) the dominating doping and transport mechanisms. The low dopability in p-type SnOx, of which the causation is also closely related to the narrow processing window, needs to be mitigated so that the electrical properties of the material are to be adequately engineered2, 3. Herein, we report on the multifunctional encapsulation of p-SnOxto limit the surface adsorption of oxygen and selectively permeate hydrogen into the p-SnOxchannel for thin film transistor (TFT) applications. Time-of-flight secondary ion mass spectrometry measurements identified that ultra-thin SiO2as a multifunctional encapsulation layer effectively suppressed the oxygen adsorption on the back channel surface of p-SnOxand augmented hydrogen density across the entire thickness of the channel. Encapsulated p-SnOx-based TFTs demonstrated much-enhanced channel conductance modulation in response to the gate bias applied, featuring higher on-state current and lower off-state current. The relevance between the TFT performance and the effects of oxygen suppression and hydrogen permeation is discussed in regard to the intrinsic and extrinsic doping mechanisms. These results are supported by density-functional-theory calculations. Acknowledgement This work was supported by the U.S. National Science Foundation (NSF) Award No. ECCS-1931088. S.L. and H.W.S. acknowledge the support from the Improvement of Measurement Standards and Technology for Mechanical Metrology (Grant No. 20011028) by KRISS. K.N. was supported by Basic Science Research Program (NRF-2021R11A1A01051246) through the NRF Korea funded by the Ministry of Education. ReferencesLee, D. H.; Park, H.; Clevenger, M.; Kim, H.; Kim, C. S.; Liu, M.; Kim, G.; Song, H. W.; No, K.; Kim, S. Y.; Ko, D.-K.; Lucietto, A.; Park, H.; Lee, S., High-Performance Oxide-Based p–n Heterojunctions Integrating p-SnOx and n-InGaZnO.ACS Applied Materials & Interfaces2021,13(46), 55676-55686.Hautier, G.; Miglio, A.; Ceder, G.; Rignanese, G.-M.; Gonze, X., Identification and design principles of low hole effective mass p-type transparent conducting oxides.Nat Commun2013,4.Yim, K.; Youn, Y.; Lee, M.; Yoo, D.; Lee, J.; Cho, S. H.; Han, S., Computational discovery of p-type transparent oxide semiconductors using hydrogen descriptor.npj Computational Materials2018,4(1), 17. Figure 1 
    more » « less
  2. ; ; ; (, ECS Meeting Abstracts)
    Neurotransmitters are small molecules involved in neuronal signaling and can also serve as stress biomarkers.1Their abnormal levels have been also proposed to be indicative of several neurological diseases such as Alzheimer’s disease, Parkinson’s disease, Huntington disease, among others. Hence, measuring their levels is highly important for early diagnosis, therapy, and disease prognosis. In this work, we investigate facile functionalization methods to tune and enhance sensitivity of printed graphene sensors to neurotransmitters. Sensors based on direct laser scribing and screen-printed graphene ink are studied. These printing methods offer ease of prototyping and scalable fabrication at low cost. The effect of functionalization of laser induced graphene (LIG) by electrodeposition and solution-based deposition of TMDs (molybdenum disulfide2and tungsten disulfide) and metal nanoparticles is studied. For different processing methods, electrochemical characteristics (such as electrochemically active surface area: ECSA and heterogenous electron transfer rate: k0) are extracted and correlated to surface chemistry and defect density obtained respectively using X-ray photoelectron spectroscopy (XPS) and Raman spectroscopy. These functionalization methods are observed to directly impact the sensitivity and limit of detection (LOD) of the graphene sensors for the studied neurotransmitters. For example, as compared to bare LIG, it is observed that electrodeposition of MoS2on LIG improves ECSA by 3 times and k0by 1.5 times.3Electrodeposition of MoS2also significantly reduces LOD of serotonin and dopamine in saliva, enabling detection of their physiologically relevant concentrations (in pM-nM range). In addition, chemical treatment of LIG sensors is carried out in the form of acetic acid treatment. Acetic acid treatment has been shown previously to improve C-C bonds improving the conductivity of LIG sensors.4In our work, in particular, acetic acid treatment leads to larger improvement of LOD of norepinephrine compared to MoS2electrodeposition. In addition, we investigate the effect of plasma treatment to tune the sensor response by modifying the defect density and chemistry. For example, we find that oxygen plasma treatment of screen-printed graphene ink greatly improves LOD of norepinephrine up to three orders of magnitude, which may be attributed to the increased defects and oxygen functional groups on the surface as evident by XPS measurements. Defects are known to play a key role in enhancing the sensitivity of 2D materials to surface interactions, and have been explored in tuning/enhancing the sensor sensitivity.5Building on our previous work,3we apply a custom machine learning-based data processing method to further improve that sensitivity and LOD, and also to automatically benchmark different molecule-material pairs. Future work includes expanding the plasma chemistry and conditions, studying the effect of precursor mixture in laser-induced solution-based functionalization, and understanding the interplay between molecule-material system. Work is also underway to improve the machine learning model by using nonlinear learning models such as neural networks to improve the sensor sensitivity, selectivity, and robustness. ReferencesA. J. Steckl, P. Ray, (2018), doi:10.1021/acssensors.8b00726.Y. Lei, D. Butler, M. C. Lucking, F. Zhang, T. Xia, K. Fujisawa, T. Granzier-Nakajima, R. Cruz-Silva, M. Endo, H. Terrones, M. Terrones, A. Ebrahimi,Sci. Adv.6, 4250–4257 (2020).V. Kammarchedu, D. Butler, A. Ebrahimi,Anal. Chim. Acta.1232, 340447 (2022).H. Yoon, J. Nah, H. Kim, S. Ko, M. Sharifuzzaman, S. C. Barman, X. Xuan, J. Kim, J. Y. Park,Sensors Actuators B Chem.311, 127866 (2020).T. Wu, A. Alharbi, R. Kiani, D. Shahrjerdi,Adv. Mater.31, 1–12 (2019). 
    more » « less
  3. ; ; ; ; ; ; ; ; ; ; et al (, Monthly Notices of the Royal Astronomical Society: Letters)
    ABSTRACT Long-period comets are planetesimal remnants constraining the environment and volatiles of the protoplanetary disc. We report the discovery of hyperbolic long-period comet C/2022 E3 Zwicky Transient Facility (ZTF), which has a perihelion ∼1.11 au, an eccentricity ≳1 and an inclination ∼109°, from images taken with the Palomar 48-inch telescope during morning twilight on 2022 March 2. Additionally, we report the characterization of C/2022 E3 (ZTF) from observations taken with the Palomar 200-inch, the Palomar 60-inch, and the NASA Infrared Telescope Facility in early 2023 February to 2023 March when the comet passed within ∼0.28 au of the Earth and reached a visible magnitude of ∼5. We measure g–r = 0.70 ± 0.01, r–i = 0.20 ± 0.01, i–z = 0.06 ± 0.01, z–J = 0.90 ± 0.01, J–H = 0.38 ± 0.01, and H–K = 0.15 ± 0.01 colours for the comet from observations. We measure the A(0°)fρ (0.8 μm) in a 6500 km radius from the nucleus of 1483 ± 40 cm, and CN, C3, and C2 production of 5.43 ± 0.11 × 1025, 2.01 ± 0.04 × 1024, and 3.08 ± 0.5 × 1025 mol s−1, similar to other long-period comets. We additionally observe the appearance of jet-like structures at a scale of ∼4000 km in wide-field g-band images, which may be caused by the presence of CN gas in the near-nucleus coma. 
    more » « less
  4. ; ; ; (, Nonlinearity)
    Abstract Kröncke has shown that the Fubini–Study metric is an unstable generalised stationary solution of Ricci flow (Kröncke 2020Commun. Anal. Geom.2835–394). In this paper, we carry out numerical simulations which indicate that Ricci flow solutions originating at unstable perturbations of the Fubini–Study metric develop local singularities modelled by the blowdown soliton discovered in (Feldmanet al2003J. Differ. Geom.65169–209). 
    more » « less
  5. ; ; ; ; ; ; (, Proceedings of the National Academy of Sciences)
    Removing CO2from the atmosphere is emerging as a viable strategy to mitigate global warming, yet the responses of the climate system to CO2reduction remain uncertain. One of the most uncertain aspects of El Niño behavior is the change in periodicity in response to CO2forcing [O. Alizadeh,Earth-Sci. Rev.235, 104246 (2022)]. In this study, we show that climate models consistently project an abrupt shortening of El Niño periodicity once CO2reductions commence in ramp-up and ramp-down CO2experiments. Besides the contribution of slow mean state changes, this phenomenon is shown to be driven by a southward shift of the Intertropical Convergence Zone (ITCZ) [J.-S. Kug,et al.,Nat. Clim. Chang.12, 47–53 (2022)] and the consequent narrowing of El Niño’s spatial pattern, which enhances the effectiveness of ocean heat recharge/discharge processes, thereby shortening its periodicity. This suggests that the abrupt shift in El Niño periodicity results from a cascading reaction involving ITCZ dynamics and El Niño’s spatial configuration. These findings highlight the critical role of the global energy balance in shaping El Niño characteristics. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email