Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAssessing Centrality Without Knowing Connections
268
0
0.0
(
0
)
Added by
Leyla Roohi
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider the privacy-preserving computation of node influence in distributed social networks, as measured by egocentric betweenness centrality (EBC). Motivated by modern communication networks spanning multiple providers, we show for the first time how multiple mutually-distrusting parties can successfully compute node EBC while revealing only differentially-private information about their internal network connections. A theoretical utility analysis upper bounds a primary source of private EBC error---private release of ego networks---with high probability. Empirical results demonstrate practical applicability with a low 1.07 relative error achievable at strong privacy budget $epsilon=0.1$ on a Facebook graph, and insignificant performance degradation as the number of network provider parties grows.
rate research
Read More
We give query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs. Our oracle model is inspired by the submodular function minimization problem: on query $S subset V$, the oracle returns the size of the cut between $S$ and $V setminus S$. We provide algorithms computing an exact minimum $s$-$t$ cut in $G$ with $tilde{O}(n^{5/3})$ queries, and computing an exact global minimum cut of $G$ with only $tilde{O}(n)$ queries (while learning the graph requires $tilde{Theta}(n^2)$ queries).
We consider training models with differential privacy (DP) using mini-batch gradients. The existing state-of-the-art, Differentially Private Stochastic Gradient Descent (DP-SGD), requires privacy amplification by sampling or shuffling to obtain the best privacy/accuracy/computation trade-offs. Unfortunately, the precise requirements on exact sampling and shuffling can be hard to obtain in important practical scenarios, particularly federated learning (FL). We design and analyze a DP variant of Follow-The-Regularized-Leader (DP-FTRL) that compares favorably (both theoretically and empirically) to amplified DP-SGD, while allowing for much more flexible data access patterns. DP-FTRL does not use any form of privacy amplification. The code is available at https://github.com/google-research/federated/tree/master/dp_ftrl and https://github.com/google-research/DP-FTRL .
In Generalized Zero-Shot Learning (GZSL), unseen categories (for which no visual data are available at training time) can be predicted by leveraging their class embeddings (e.g., a list of attributes describing them) together with a complementary pool of seen classes (paired with both visual data and class embeddings). Despite GZSL is arguably challenging, we posit that knowing in advance the class embeddings, especially for unseen categories, is an actual limit of the applicability of GZSL towards real-world scenarios. To relax this assumption, we propose Open Zero-Shot Learning (OZSL) to extend GZSL towards the open-world settings. We formalize OZSL as the problem of recognizing seen and unseen classes (as in GZSL) while also rejecting instances from unknown categories, for which neither visual data nor class embeddings are provided. We formalize the OZSL problem introducing evaluation protocols, error metrics and benchmark datasets. We also suggest to tackle the OZSL problem by proposing the idea of performing unknown feature generation (instead of only unseen features generation as done in GZSL). We achieve this by optimizing a generative process to sample unknown class embeddings as complementary to the seen and the unseen. We intend these results to be the ground to foster future research, extending the standard closed-world zero-shot learning (GZSL) with the novel open-world counterpart (OZSL).
In this paper, we consider a transfer Reinforcement Learning (RL) problem in continuous state and action spaces, under unobserved contextual information. For example, the context can represent the mental view of the world that an expert agent has formed through past interactions with this world. We assume that this context is not accessible to a learner agent who can only observe the expert data. Then, our goal is to use the context-aware expert data to learn an optimal context-unaware policy for the learner using only a few new data samples. Such problems are typically solved using imitation learning that assumes that both the expert and learner agents have access to the same information. However, if the learner does not know the expert context, using the expert data alone will result in a biased learner policy and will require many new data samples to improve. To address this challenge, in this paper, we formulate the learning problem as a causal bound-constrained Multi-Armed-Bandit (MAB) problem. The arms of this MAB correspond to a set of basis policy functions that can be initialized in an unsupervised way using the expert data and represent the different expert behaviors affected by the unobserved context. On the other hand, the MAB constraints correspond to causal bounds on the accumulated rewards of these basis policy functions that we also compute from the expert data. The solution to this MAB allows the learner agent to select the best basis policy and improve it online. And the use of causal bounds reduces the exploration variance and, therefore, improves the learning rate. We provide numerical experiments on an autonomous driving example that show that our proposed transfer RL method improves the learners policy faster compared to existing imitation learning methods and enjoys much lower variance during training.
Cooperation played a significant role in the self-organization and evolution of living organisms. Both network topology and the initial position of cooperators heavily affect the cooperation of social dilemma games. We developed a novel simulation program package, called NetworGame, which is able to simulate any type of social dilemma games on any model, or real world networks with any assignment of initial cooperation or defection strategies to network nodes. The ability of initially defecting single nodes to break overall cooperation was called as game centrality. The efficiency of this measure was verified on well-known social networks, and was extended to protein games, i.e. the simulation of cooperation between proteins, or their amino acids. Hubs and in particular, party hubs of yeast protein-protein interaction networks had a large influence to convert the cooperation of other nodes to defection. Simulations on methionyl-tRNA synthetase protein structure network indicated an increased influence of nodes belonging to intra-protein signaling pathways on breaking cooperation. The efficiency of single, initially defecting nodes to convert the cooperation of other nodes to defection in social dilemma games may be an important measure to predict the importance of nodes in the integration and regulation of complex systems. Game centrality may help to design more efficient interventions to cellular networks (in forms of drugs), to ecosystems and social networks. The NetworGame algorithm is downloadable from here: www.NetworGame.linkgroup.hu
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
