21 May 2024 in IEEE Transactions on Information Theory
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.
8 January 2024 in IEEE Transactions on Information Theory
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 in IEEE Transactions on Information Theory
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.
8 July 2024 in IEEE Transactions on Information Theory
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.
26 March 2025 in IEEE Transactions on Information Theory
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.
6 May 2024 in IEEE Journal on Selected Areas in Information Theory
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.