Robust node classification on graphs: Jointly from bayesian label transition and topology-based label propagation
J Zhuang, M Al Hasan - Proceedings of the 31st ACM International …, 2022 - dl.acm.org
Node classification using Graph Neural Networks (GNNs) has been widely applied in
various real-world scenarios. However, in recent years, compelling evidence emerges that …
various real-world scenarios. However, in recent years, compelling evidence emerges that …
Hamiltonicity of random subgraphs of the hypercube
We study Hamiltonicity in random subgraphs of the hypercube $\mathcal {Q}^ n $. Our first
main theorem is an optimal hitting time result. Consider the random process which includes …
main theorem is an optimal hitting time result. Consider the random process which includes …
Smoothed analysis for graph isomorphism
There is no known polynomial-time algorithm for graph isomorphism testing, but elementary
combinatorial" refinement" algorithms seem to be very efficient in practice. Some …
combinatorial" refinement" algorithms seem to be very efficient in practice. Some …
Rainbow trees in uniformly edge‐colored graphs
E Aigner‐Horev, D Hefetz… - Random Structures & …, 2023 - Wiley Online Library
We obtain sufficient conditions for the emergence of spanning and almost‐spanning
bounded‐degree rainbow trees in various host graphs, having their edges colored …
bounded‐degree rainbow trees in various host graphs, having their edges colored …
On oriented cycles in randomly perturbed digraphs
On oriented cycles in randomly perturbed digraphs Page 1 Combinatorics, Probability and
Computing (2023), 1–22 doi:10.1017/S0963548323000391 ARTICLE On oriented cycles in …
Computing (2023), 1–22 doi:10.1017/S0963548323000391 ARTICLE On oriented cycles in …
Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
E Aigner-Horev, D Hefetz - SIAM Journal on Discrete Mathematics, 2021 - SIAM
Given an n-vertex graph H with minimum degree at least dn for some fixed d>0, the
distribution H∪G(n,p) over the supergraphs of H is referred to as a (random) perturbation of …
distribution H∪G(n,p) over the supergraphs of H is referred to as a (random) perturbation of …
[HTML][HTML] Schur properties of randomly perturbed sets
A set A of integers is said to be Schur if any two-colouring of A results in monochromatic x, y
and z with x+ y= z. We study the following problem: how many random integers from [n] need …
and z with x+ y= z. We study the following problem: how many random integers from [n] need …
Enhancing the Resilience of Graph Neural Networks to Topological Perturbations in Sparse Graphs
S He, J Zhuang, D Wang, L Peng, J Song - arXiv preprint arXiv …, 2024 - arxiv.org
Graph neural networks (GNNs) have been extensively employed in node classification.
Nevertheless, recent studies indicate that GNNs are vulnerable to topological perturbations …
Nevertheless, recent studies indicate that GNNs are vulnerable to topological perturbations …
Hamiltonicity of graphs perturbed by a random geometric graph
A Espuny Díaz - Journal of Graph Theory, 2023 - Wiley Online Library
We study Hamiltonicity in graphs obtained as the union of a deterministic nn‐vertex graph
HH with linear degrees and ad d‐dimensional random geometric graph G d (n, r) G^d(n,r) …
HH with linear degrees and ad d‐dimensional random geometric graph G d (n, r) G^d(n,r) …
Hamiltonicity of graphs perturbed by a random regular graph
A Espuny Díaz, A Girão - Random Structures & Algorithms, 2023 - Wiley Online Library
We study Hamiltonicity and pancyclicity in the graph obtained as the union of a deterministic
nn‐vertex graph HH with δ (H)≥ α n δ (H) ≥ α n and a random dd‐regular graph GG, for d∈ …
nn‐vertex graph HH with δ (H)≥ α n δ (H) ≥ α n and a random dd‐regular graph GG, for d∈ …