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: Edge Sampling Using Local Network Information
Edge sampling is an important topic in network analysis. It provides a natural way to reduce network size while retaining desired features of the original network. Sampling methods that only use local information are common in practice as they do not require access to the entire network and can be easily parallelized. Despite promising empirical performances, most of these methods are derived from heuristic considerations and lack theoretical justification. In this paper, we study a simple and efficient edge sampling method that uses local network information. We show that when the local connectivity is sufficiently strong, the sampled network satisfies a strong spectral property. We measure the strength of local connectivity by a global parameter and relate it to more common network statistics such as the clustering coefficient and network curvature. Based on this result, we also provide sufficient conditions under which random networks and hypergraphs can be efficiently sampled. Keywords: Network analysis, edge sampling, local information, network curvature, clustering coefficient  more » « less
Award ID(s):
1934568
PAR ID:
10281988
Author(s) / Creator(s):
Date Published:
Journal Name:
Journal of machine learning research
Volume:
22
ISSN:
1533-7928
Page Range / eLocation ID:
1-29
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, 2021 IEEE International Conference on Robotics and Automation (ICRA))
    null (Ed.)
    Using sampling to estimate the connectivity of high-dimensional configuration spaces has been the theoretical underpinning for effective sampling-based motion planners. Typical strategies either build a roadmap, or a tree as the underlying search structure that connects sampled configurations, with a focus on guaranteeing completeness and optimality as the number of samples tends to infinity. Roadmap-based planners allow preprocessing the space, and can solve multiple kinematic motion planning problems, but need a steering function to connect pairwise-states. Such steering functions are difficult to define for kinodynamic systems, and limit the applicability of roadmaps to motion planning problems with dynamical systems. Recent advances in the analysis of single query tree-based planners has shown that forward search trees based on random propagations are asymptotically optimal. The current work leverages these recent results and proposes a multi-query framework for kinodynamic planning. Bundles of kinodynamic edges can be sampled to cover the state space before the query arrives. Then, given a motion planning query, the connectivity of the state space reachable from the start can be recovered from a forward search tree reasoning about a local neighborhood of the edge bundle from each tree node. The work demonstrates theoretically that considering any constant radial neighborhood during this process is sufficient to guarantee asymptotic optimality. Experimental validation in five and twelve dimensional simulated systems also highlights the ability of the proposed edge bundles to express high-quality kinodynamic solutions. Our approach consistently finds higher quality solutions compared to SST, and RRT, often with faster initial solution times. The strategy of sampling kinodynamic edges is demonstrated to be a promising new paradigm. 
    more » « less
  2. ; ; ; ; ; (, International Conference on Machine Learning (ICML))
    Federated Averaging (FedAvg) and its variants are the most popular optimization algorithms in federated learning (FL). Previous convergence analyses of FedAvg either assume full client participation or partial client participation where the clients can be uniformly sampled. However, in practical cross-device FL systems, only a subset of clients that satisfy local criteria such as battery status, network connectivity, and maximum participation frequency requirements (to ensure privacy) are available for training at a given time. As a result, client availability follows a natural cyclic pattern. We provide (to our knowledge) the first theoretical framework to analyze the convergence of FedAvg with cyclic client participation with several different client optimizers such as GD, SGD, and shuffled SGD. Our analysis discovers that cyclic client participation can achieve a faster asymptotic convergence rate than vanilla FedAvg with uniform client participation under suitable conditions, providing valuable insights into the design of client sampling protocols. 
    more » « less
  3. ; ; ; (, Journal of Neural Engineering)
    Abstract Objective. Spontaneous fluctuations of cerebral hemodynamics measured by functional magnetic resonance imaging (fMRI) are widely used to study the network organization of the brain. The temporal correlations among the ultra-slow, <0.1 Hz fluctuations across the brain regions are interpreted as functional connectivity maps and used for diagnostics of neurological disorders. However, despite the interest narrowed in the ultra-slow fluctuations, hemodynamic activity that exists beyond the ultra-slow frequency range could contribute to the functional connectivity, which remains unclear.Approach. In the present study, we have measured the brain-wide hemodynamics in the human participants with functional near-infrared spectroscopy (fNIRS) in a whole-head, cap-based and high-density montage at a sampling rate of 6.25 Hz. In addition, we have acquired resting state fMRI scans in the same group of participants for cross-modal evaluation of the connectivity maps. Then fNIRS data were deliberately down-sampled to a typical fMRI sampling rate of ∼0.5 Hz and the resulted differential connectivity maps were subject to a k-means clustering.Main results. Our diffuse optical topographical analysis of fNIRS data have revealed a default mode network (DMN) in the spontaneous deoxygenated and oxygenated hemoglobin changes, which remarkably resemble the same fMRI network derived from participants. Moreover, we have shown that the aliased activities in the down-sampled optical signals have altered the connectivity patterns, resulting in a network organization of aliased functional connectivity in the cerebral hemodynamics.Significance.The results have for the first time demonstrated that fNIRS as a broadly accessible modality can image the resting-state functional connectivity in the posterior midline, prefrontal and parietal structures of the DMN in the human brain, in a consistent pattern with fMRI. Further empowered by the fast sampling rate of fNIRS, our findings suggest the presence of aliased connectivity in the current understanding of the human brain organization. 
    more » « less
  4. ; ; (, Neuroinformatics)
    This article seeks to investigate the impact of aging on functional connectivity across different cognitive control scenarios, particularly emphasizing the identification of brain regions significantly associated with early aging. By conceptualizing functional connectivity within each cognitive control scenario as a graph, with brain regions as nodes, the statistical challenge revolves around devising a regression framework to predict a binary scalar outcome (aging or normal) using multiple graph predictors. Popular regression methods utilizing multiplex graph predictors often face limitations in effectively harnessing information within and across graph layers, leading to potentially less accurate inference and predictive accuracy, especially for smaller sample sizes. To address this challenge, we propose the Bayesian Multiplex Graph Classifier (BMGC). Accounting for multiplex graph topology, our method models edge coefficients at each graph layer using bilinear interactions between the latent effects associated with the two nodes connected by the edge. This approach also employs a variable selection framework on node-specific latent effects from all graph layers to identify influential nodes linked to observed outcomes. Crucially, the proposed framework is computationally efficient and quantifies the uncertainty in node identification, coefficient estimation, and binary outcome prediction. BMGC outperforms alternative methods in terms of the aforementioned metrics in simulation studies. An additional BMGC validation was completed using an fMRI study of brain networks in adults. The proposed BMGC technique identified that sensory motor brain network obeys certain lateral symmetries, whereas the default mode network exhibits significant brain asymmetries associated with early aging. 
    more » « less
  5. ; ; ; ; ; ; ; ; (, Journal of Materials Chemistry B)
    Glycine, the simplest amino acid, is considered a promising functional biomaterial owing to its excellent biocompatibility and strong out-of-plane piezoelectricity. Practical applications require glycine films to be manufactured with their strong piezoelectric polar 〈001〉 direction aligned with the film thickness. Based on the recently-developed solidification approach of a polyvinyl alcohol (PVA) and glycine aqueous solution, in this work, we demonstrate that the crystal orientation of the as-synthesized film is determined by the orientation of glycine crystal nuclei. By controlling the local nucleation kinetics via surface curvature tuning, we shifted the nucleation site from the edge to the middle of the liquid film, and thereby aligned the 〈001〉 direction vertically. As a result, the PVA–glycine–PVA sandwich film exhibits the highest aver-age piezoelectric coefficient d 33 of 6.13 ± 1.13 pC N −1 . This work demonstrates a promising kinetic approach to achieve crystallization and property control in a scalable biocrystal manufacturing process. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email