This content will become publicly available on December 1, 2024
 Award ID(s):
 1954351
 NSFPAR ID:
 10478863
 Publisher / Repository:
 Springer
 Date Published:
 Journal Name:
 Probability Theory and Related Fields
 Volume:
 187
 Issue:
 34
 ISSN:
 01788051
 Page Range / eLocation ID:
 817 to 884
 Subject(s) / Keyword(s):
 Interacting diffusions · Sparse graphs · Random graphs · Local weak convergence · Meanfield limits · Nonlinear Markov processes · Erdo ̋s–Rényi graphs · Configuration model · Unimodularity · Markov random fields
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

In social network, a person located at the periphery region (marginal node) is likely to be treated unfairly when compared with the persons at the center. While existing fairness works on graphs mainly focus on protecting sensitive attributes (e.g., age and gender), the fairness incurred by the graph structure should also be given attention. On the other hand, the information aggregation mechanism of graph neural networks amplifies such structure unfairness, as marginal nodes are often far away from other nodes. In this paper, we focus on novel fairness incurred by the graph structure on graph neural networks, named structure fairness. Specifically, we first analyzed multiple graphs and observed that marginal nodes in graphs have a worse performance of downstream tasks than others in graph neural networks. Motivated by the observation, we propose Structural Fair Graph Neural Network (SFairGNN), which combines neighborhood expansion based structure debiasing with hopaware attentive information aggregation to achieve structure fairness. Our experiments show SFairGNN can significantly improve structure fairness while maintaining overall performance in the downstream tasks.more » « less

Abstract We define a bridge node to be a node whose neighbor nodes are sparsely connected to each other and are likely to be part of different components if the node is removed from the network. We propose a computationally light neighborhoodbased bridge node centrality (NBNC) tuple that could be used to identify the bridge nodes of a network as well as rank the nodes in a network on the basis of their topological position to function as bridge nodes. The NBNC tuple for a node is asynchronously computed on the basis of the neighborhood graph of the node that comprises of the neighbors of the node as vertices and the links connecting the neighbors as edges. The NBNC tuple for a node has three entries: the number of components in the neighborhood graph of the node, the algebraic connectivity ratio of the neighborhood graph of the node and the number of neighbors of the node. We analyze a suite of 60 complex realworld networks and evaluate the computational lightness, effectiveness, efficiency/accuracy and uniqueness of the NBNC tuple visavis the existing bridgeness related centrality metrics and the Louvain community detection algorithm.more » « less

Recent progress in the study of the contact process (see Shankar Bhamidi, Danny Nam, Oanh Nguyen, and Allan Sly [Ann. Probab. 49 (2021), pp. 244–286]) has verified that the extinctionsurvival threshold λ 1 \lambda _1 on a GaltonWatson tree is strictly positive if and only if the offspring distribution ξ \xi has an exponential tail. In this paper, we derive the firstorder asymptotics of λ 1 \lambda _1 for the contact process on GaltonWatson trees and its corresponding analog for random graphs. In particular, if ξ \xi is appropriately concentrated around its mean, we demonstrate that λ 1 ( ξ ) ∼ 1 / E ξ \lambda _1(\xi ) \sim 1/\mathbb {E} \xi as E ξ → ∞ \mathbb {E}\xi \rightarrow \infty , which matches with the known asymptotics on d d regular trees. The same results for the shortlong survival threshold on the ErdősRényi and other random graphs are shown as well.more » « less

SUMMARY We propose a theoretical modelling framework for earthquake occurrence and clustering based on a family of invariant Galton–Watson (IGW) stochastic branching processes. The IGW process is a rigorously defined approximation to imprecisely observed or incorrectly estimated earthquake clusters modelled by Galton–Watson branching processes, including the Epidemic Type Aftershock Sequence (ETAS) model. The theory of IGW processes yields explicit distributions for multiple cluster attributes, including magnitudedependent and magnitudeindependent offspring number, cluster size and cluster combinatorial depth. Analysis of the observed seismicity in southern California demonstrates that the IGW model provides a close fit to the observed earthquake clusters. The estimated IGW parameters and derived statistics are robust with respect to the catalogue lower cutoff magnitude. The proposed model facilitates analyses of multiple quantities of seismicity based on selfsimilar tree attributes, and may be used to assess the proximity of seismicity to criticality.

Given a sequence of possibly correlated randomly generated graphs, we address the problem of detecting changes on their underlying distribution. To this end, we will consider Random Dot Product Graphs (RDPGs), a simple yet rich family of random graphs that subsume ErdösRényi and Stochastic Block Model ensembles as particular cases. In RDPGs each node has an associated latent vector and inner products between these vectors dictate the edge existence probabilities. Previous works have mostly focused on the undirected and unweighted graph case, a gap we aim to close here. We first extend the RDPG model to accommodate directed and weighted graphs, a contribution whose interest transcends changepoint detection (CPD). A statistic derived from the nodes' estimated latent vectors (i.e., embeddings) facilitates adoption of scalable geometric CPD techniques. The resulting algorithm yields interpretable results and facilitates pinpointing which (and when) nodes are acting differently. Numerical tests on simulated data as well as on a real dataset of graphs stemming from a WiFi network corroborate the effectiveness of the proposed CPD method.more » « less