Ziao Wang
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Ziao Wang has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Lele Wang
Department of Electrical and Computer Engineering, The University of British Columbia, Vancouver, BC, Canada
7 shared publications - Nadim Ghaddar
Department of Electrical and Computer Engineering, University of Toronto, Toronto, ON, Canada
3 shared publications - Weina Wang
Carnegie Mellon University, Pittsburgh, USA
3 shared publications - Banghua Zhu
Department of Electrical Engineering and Computer Sciences UC Berkeley
2 shared publications Ning Zhang
Department of Electrical and Computer Engineering, The University of British Columbia, Vancouver, BC, Canada
2 shared publicationsAlankrita Bhatt
California Institute of Technology (Caltech), Pasadena, CA, USA
1 shared publication
Latest Publications
- 1 October 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (10) , 7686-7708
Noisy Computing of the Threshold Function
- 1 October 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (10) , 7686-7708
Noisy Computing of the Threshold Function
- 26 March 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (6) , 4556-4580
Efficient Algorithms for Attributed Graph Alignment With Vanishing Edge Correlation
Graph alignment refers to the task of finding the vertex correspondence between two correlated graphs of n vertices. Extensive study has been done on polynomial-time algorithms for the graph alignment problem under the Erdős–Rényi graph pair model, where the two graphs are Erdős–Rényi graphs with edge probability$q_{\mathrm {u}}$ , correlated under certain vertex correspondence. To achieve exact recovery of the correspondence, all existing algorithms at least require the edge correlation coefficient$\rho _{\mathrm {u}}$ between the two graphs to be non-vanishing as$n\rightarrow \infty $ . Moreover, it is conjectured that no polynomial-time algorithm can achieve exact recovery under vanishing edge correlation${\rho _{\mathrm {u}}}\lt 1/\mathrm {polylog}(n)$ . In this paper, we show that with a vanishing amount of additional attribute information, exact recovery is polynomial-time feasible under vanishing edge correlation${\rho _{\mathrm {u}}}\ge n^{-\Theta (1)}$ . We identify a local tree structure, which incorporates one layer of user information and one layer of attribute information, and apply the subgraph counting technique to such structures. A polynomial-time algorithm is proposed that recovers the vertex correspondence for most of the vertices, and then refines the output to achieve exact recovery. The consideration of attribute information is motivated by real-world applications like LinkedIn and Twitter, where user attributes like birthplace and education background can aid alignment.- 26 March 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (6) , 4556-4580
Efficient Algorithms for Attributed Graph Alignment With Vanishing Edge Correlation
Graph alignment refers to the task of finding the vertex correspondence between two correlated graphs of n vertices. Extensive study has been done on polynomial-time algorithms for the graph alignment problem under the Erdős–Rényi graph pair model, where the two graphs are Erdős–Rényi graphs with edge probability$q_{\mathrm {u}}$ , correlated under certain vertex correspondence. To achieve exact recovery of the correspondence, all existing algorithms at least require the edge correlation coefficient$\rho _{\mathrm {u}}$ between the two graphs to be non-vanishing as$n\rightarrow \infty $ . Moreover, it is conjectured that no polynomial-time algorithm can achieve exact recovery under vanishing edge correlation${\rho _{\mathrm {u}}}\lt 1/\mathrm {polylog}(n)$ . In this paper, we show that with a vanishing amount of additional attribute information, exact recovery is polynomial-time feasible under vanishing edge correlation${\rho _{\mathrm {u}}}\ge n^{-\Theta (1)}$ . We identify a local tree structure, which incorporates one layer of user information and one layer of attribute information, and apply the subgraph counting technique to such structures. A polynomial-time algorithm is proposed that recovers the vertex correspondence for most of the vertices, and then refines the output to achieve exact recovery. The consideration of attribute information is motivated by real-world applications like LinkedIn and Twitter, where user attributes like birthplace and education background can aid alignment.- 8 July 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (9) , 6121-6138
Noisy Sorting Capacity
Sorting is the task of ordering n elements using pairwise comparisons. It is well known that $m=\Theta (n\log n)$ comparisons are both necessary and sufficient when the outcomes of the comparisons are observed with no noise. In this paper, we study the sorting problem when each comparison is incorrect with some fixed yet unknown probability p. Unlike the common approach in the literature which aims to minimize the number of pairwise comparisons m to achieve a given desired error probability, we consider randomized algorithms with expected number of queries $\textsf {E}[M]$ and aim at characterizing the maximal sorting rate $\frac {n\log n}{\mathop {\mathrm {\textsf {E}}}\nolimits [M]}$ such that the ordering of the elements can be estimated with a vanishing error probability asymptotically. The maximal rate is referred to as the noisy sorting capacity. In this work, we derive upper and lower bounds on the noisy sorting capacity. The two lower bounds — one for fixed-length algorithms and one for variable-length algorithms — are established by combining the insertion sort algorithm with the well-known Burnashev-Zigangirov algorithm for channel coding with feedback. Compared with existing methods, the proposed algorithms are universal in the sense that they do not require the knowledge of p, while maintaining a strictly positive sorting rate. Moreover, we derive a general upper bound on the noisy sorting capacity, along with an upper bound on the maximal rate that can be achieved by sorting algorithms that are based on insertion sort.
- 8 July 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (9) , 6121-6138
Noisy Sorting Capacity
Sorting is the task of ordering n elements using pairwise comparisons. It is well known that $m=\Theta (n\log n)$ comparisons are both necessary and sufficient when the outcomes of the comparisons are observed with no noise. In this paper, we study the sorting problem when each comparison is incorrect with some fixed yet unknown probability p. Unlike the common approach in the literature which aims to minimize the number of pairwise comparisons m to achieve a given desired error probability, we consider randomized algorithms with expected number of queries $\textsf {E}[M]$ and aim at characterizing the maximal sorting rate $\frac {n\log n}{\mathop {\mathrm {\textsf {E}}}\nolimits [M]}$ such that the ordering of the elements can be estimated with a vanishing error probability asymptotically. The maximal rate is referred to as the noisy sorting capacity. In this work, we derive upper and lower bounds on the noisy sorting capacity. The two lower bounds — one for fixed-length algorithms and one for variable-length algorithms — are established by combining the insertion sort algorithm with the well-known Burnashev-Zigangirov algorithm for channel coding with feedback. Compared with existing methods, the proposed algorithms are universal in the sense that they do not require the knowledge of p, while maintaining a strictly positive sorting rate. Moreover, we derive a general upper bound on the noisy sorting capacity, along with an upper bound on the maximal rate that can be achieved by sorting algorithms that are based on insertion sort.
- 21 May 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (8) , 5910-5934
Attributed Graph Alignment
Motivated by various data science applications including de-anonymizing user identities in social networks, we consider the graph alignment problem, where the goal is to identify the vertex/user correspondence between two correlated graphs. Existing work mostly recovers the correspondence by exploiting the user-user connections. However, in many real-world applications, additional information about the users, such as user profiles, might be publicly available. In this paper, we introduce the attributed graph alignment problem, where additional user information, referred to as attributes, is incorporated to assist graph alignment. We establish both the achievability and converse results on recovering vertex correspondence exactly, where the conditions match for certain parameter regimes. Our results span the full spectrum between models that only consider user-user connections and models where only attribute information is available.
- 21 May 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (8) , 5910-5934
Attributed Graph Alignment
Motivated by various data science applications including de-anonymizing user identities in social networks, we consider the graph alignment problem, where the goal is to identify the vertex/user correspondence between two correlated graphs. Existing work mostly recovers the correspondence by exploiting the user-user connections. However, in many real-world applications, additional information about the users, such as user profiles, might be publicly available. In this paper, we introduce the attributed graph alignment problem, where additional user information, referred to as attributes, is incorporated to assist graph alignment. We establish both the achievability and converse results on recovering vertex correspondence exactly, where the conditions match for certain parameter regimes. Our results span the full spectrum between models that only consider user-user connections and models where only attribute information is available.
- 6 May 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 5, 302-313
Noisy Computing of the OR and MAX Functions
We consider the problem of computing a function of n variables using noisy queries, where each query is incorrect with some fixed and known probability $p \in (0,1/2)$ . Specifically, we consider the computation of the $\textsf {OR}$ function of n bits (where queries correspond to noisy readings of the bits) and the $\textsf {MAX}$ function of n real numbers (where queries correspond to noisy pairwise comparisons). We show that an expected number of queries of $(1 \pm o(1)) {}\frac {n\log {}\frac {1}{\delta }}{D_{\textsf {KL}}(p \| 1-p)}$ is both sufficient and necessary to compute both functions with a vanishing error probability $\delta = o(1)$ , where $D_{\textsf {KL}}(p \| 1-p)$ denotes the Kullback-Leibler divergence between $\textsf {Bern}(p)$ and $\textsf {Bern}(1-p)$ distributions. Compared to previous work, our results tighten the dependence on p in both the upper and lower bounds for the two functions.
- 6 May 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 5, 302-313
Noisy Computing of the OR and MAX Functions
We consider the problem of computing a function of n variables using noisy queries, where each query is incorrect with some fixed and known probability $p \in (0,1/2)$ . Specifically, we consider the computation of the $\textsf {OR}$ function of n bits (where queries correspond to noisy readings of the bits) and the $\textsf {MAX}$ function of n real numbers (where queries correspond to noisy pairwise comparisons). We show that an expected number of queries of $(1 \pm o(1)) {}\frac {n\log {}\frac {1}{\delta }}{D_{\textsf {KL}}(p \| 1-p)}$ is both sufficient and necessary to compute both functions with a vanishing error probability $\delta = o(1)$ , where $D_{\textsf {KL}}(p \| 1-p)$ denotes the Kullback-Leibler divergence between $\textsf {Bern}(p)$ and $\textsf {Bern}(1-p)$ distributions. Compared to previous work, our results tighten the dependence on p in both the upper and lower bounds for the two functions.
- 8 January 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (5) , 3622-3639
On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment
Graph alignment aims at finding the vertex correspondence between two correlated graphs, a task that frequently occurs in graph mining applications such as social network analysis. Attributed graph alignment is a variant of graph alignment, in which publicly available side information or attributes are exploited to assist graph alignment. Existing studies on attributed graph alignment focus on either theoretical performance without computational constraints or empirical performance of efficient algorithms. This motivates us to investigate efficient algorithms with theoretical performance guarantee. In this paper, we propose two polynomial-time algorithms that exactly recover the vertex correspondence with high probability. The feasible region of the proposed algorithms is near optimal compared to the information-theoretic limits. When specialized to the seeded graph alignment problem under the seeded Erdős-Rényi graph pair model, the proposed algorithms extends the best known feasible region for exact alignment by polynomial-time algorithms.
- 8 January 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (5) , 3622-3639
On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment
Graph alignment aims at finding the vertex correspondence between two correlated graphs, a task that frequently occurs in graph mining applications such as social network analysis. Attributed graph alignment is a variant of graph alignment, in which publicly available side information or attributes are exploited to assist graph alignment. Existing studies on attributed graph alignment focus on either theoretical performance without computational constraints or empirical performance of efficient algorithms. This motivates us to investigate efficient algorithms with theoretical performance guarantee. In this paper, we propose two polynomial-time algorithms that exactly recover the vertex correspondence with high probability. The feasible region of the proposed algorithms is near optimal compared to the information-theoretic limits. When specialized to the seeded graph alignment problem under the seeded Erdős-Rényi graph pair model, the proposed algorithms extends the best known feasible region for exact alignment by polynomial-time algorithms.
- 12 September 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (2) , 1473-1497
Universal Graph Compression: Stochastic Block Models
Motivated by the prevalent data science applications of processing large-scale graph data such as social networks and biological networks, this paper investigates lossless compression of data in the form of a labeled graph. Particularly, we consider a widely used random graph model, stochastic block model (SBM), which captures the clustering effects in social networks. An information-theoretic universal compression framework is applied, in which one aims to design a single compressor that achieves the asymptotically optimal compression rate, for every SBM distribution, without knowing the parameters of the SBM. Such a graph compressor is proposed in this paper, which universally achieves the optimal compression rate with polynomial time complexity for a wide class of SBMs. Existing universal compression techniques are developed mostly for stationary ergodic one-dimensional sequences. However, the adjacency matrix of SBM has complex two-dimensional correlations. The challenge is alleviated through a carefully designed transform that converts two-dimensional correlated data into almost i.i.d. submatrices. The sequence of submatrices is then compressed by a Krichevsky–Trofimov compressor, whose length analysis is generalized to identically distributed but arbitrarily correlated sequences. In four benchmark graph datasets, the compressed files from competing algorithms take 2.4 to 27 times the space needed by the proposed scheme.
- 12 September 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (2) , 1473-1497
Universal Graph Compression: Stochastic Block Models
Motivated by the prevalent data science applications of processing large-scale graph data such as social networks and biological networks, this paper investigates lossless compression of data in the form of a labeled graph. Particularly, we consider a widely used random graph model, stochastic block model (SBM), which captures the clustering effects in social networks. An information-theoretic universal compression framework is applied, in which one aims to design a single compressor that achieves the asymptotically optimal compression rate, for every SBM distribution, without knowing the parameters of the SBM. Such a graph compressor is proposed in this paper, which universally achieves the optimal compression rate with polynomial time complexity for a wide class of SBMs. Existing universal compression techniques are developed mostly for stationary ergodic one-dimensional sequences. However, the adjacency matrix of SBM has complex two-dimensional correlations. The challenge is alleviated through a carefully designed transform that converts two-dimensional correlated data into almost i.i.d. submatrices. The sequence of submatrices is then compressed by a Krichevsky–Trofimov compressor, whose length analysis is generalized to identically distributed but arbitrarily correlated sequences. In four benchmark graph datasets, the compressed files from competing algorithms take 2.4 to 27 times the space needed by the proposed scheme.