Differentially Private and Scalable Estimation of the Network Principal Component

Alireza Khayatian [email protected], Anil Vullikanti [email protected], Aritra Konar [email protected] · 2025

Read Differentially Private and Scalable Estimation of the Network Principal Component by Alireza Khayatian [email protected], Anil Vullikanti [email protected], Aritra Konar [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-03858.txt.

Introduction

Alireza Khayatian, Anil Vullikanti, and Aritra Konar present a 2025 method for finding the main pattern in a network without exposing private links. The pattern, called the principal component, helps spot key nodes and dense groups, but network data is often sensitive. Standard privacy methods add so much noise that the answer becomes useless, or they run too slowly on big graphs.

Their method first checks, in a private way, whether a given graph is well behaved, and only then releases an answer with light noise. It runs about as fast as the non-private calculation. On real networks with up to three million nodes, it ran about 180 times faster than a leading older method. The work also yields a private method for finding the densest small subgraph.

Catalog record

CREATORAlireza Khayatian [email protected], Anil Vullikanti [email protected], Aritra Konar [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE106 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-03858

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Differentially Private and Scalable Estimation of the Network Principal Component Alireza Khayatian [email protected], Anil Vullikanti [email protected], Aritra Konar [email protected] Abstract Computing the principal component (PC) of the adjacency matrix of an undirected graph has several applications ranging from identifying key vertices for influence maximization and controlling diffusion processes, to discovering densely interconnected vertex subsets. However, many networked datasets are sensitive, which necessitates private computation of the PC for use in the aforementioned applications. Differential privacy has emerged as the gold standard in privacy-preserving data analysis, but existing DP algorithms for private PC suffer from low accuracy due to large noise injection or high complexity. Motivated by the large gap between the local and global sensitivities of the PC on real-graphs, we consider instance-specific mechanisms for privately computing the PC under edge-DP. These mechanisms guarantee privacy for all datasets, but provide good utility on “well-behaved” datasets by injecting smaller amounts of noise. More specifically, we consider the Propose-Test-Release (PTR) framework. Although computationally expensive in general, we design a novel approach for implementing a PTR variant in the same time as computation of a non-private PC, while offering good utility. Our framework tests in a differentially-private manner whether a given graph is “well-behaved” or not, and then tests whether its private to release a noisy PC with small noise. As a consequence, this also leads to the first DP algorithm for the Densest- k k -subgraph problem, a key graph mining primitive. We run our method on diverse real-world networks, with the largest having 3 million vertices, and compare its utility to a pre-existing baseline based on the private power method (PPM). Although PTR requires a slightly larger privacy budget, on average, it achieves a 180-fold improvement in runtime over PPM. 1 Introduction Background: The principal component {\mathbf{v}} of a network, i.e., the eigen-vector corresponding to the largest eigen-value of the graph adjacency matrix (and more generally, the other principal components), has been found useful in diverse tasks in graph mining Bonacich (2007) ; Das et al. (2018) ; Le et al. (2015) . The component v_{i} corresponding to node i , is commonly referred to as its eigen-vector centrality. This notion has been used to identify critical nodes in many types of networks, e.g., social and biological networks Lohmann et al. (2010) ; Jalili et al. (2016) ; Das et al. (2018) . It has been shown that nodes with high eigen-vector centrality are good solutions for influence maximization Dey et al. (2019) ; Maharani et al. (2014) ; Deng et al. (2017) . Interestingly, vaccination of high eigen-vector centrality nodes has also been found to be effective in reducing diffusion processes Van Mieghem et al. (2011) ; Saha et al. (2015) ; Doostmohammadian et al. (2020) . More generally, eigen-vector centrality is used as a standard baseline in most analyses where a set of well connected nodes need to be selected. Another application of the principal component is in identifying highly interconnected subsets of vertices in a graph, which is a fundamental problem in graph mining with wide-ranging applications spanning bioinformatics, social network analysis, and fraud detection (see Lanciano et al. (2024) and references therein). The densest- k -subgraph (D k S) Feige et al. (2001) corresponds to a vertex subset of pre-specified size k with the largest (induced) edge density in a graph. The D k S problem falls within the broader class of density-based subgraph detection techniques, which include popular measures such as the core decomposition Seidman (1983) and the densest subgraph problem Charikar (2000) ; Goldberg (1984) . In contrast to these approaches, the D k S formulation possesses the built-in feature of explicit control over the size of the selected subgraph. This is an important advantage enjoyed by D k S, as the lack of size control causes the latter approaches to output large subgraphs that are sparsely interconnected in real-world graphs Tsourakakis et al. (2013) ; Shin et al. (2016) . On the flip-side, the D k S problem is computationally intractable in then worst-case, and achieving good approximation guarantees is provably hard under standard complexity-theoretic assumptions Manurangsi (2017) ; Jones et al. (2023) . Notwithstanding these negative results, the work of Papailiopoulos et al. (2014) demonstrated that employing a low-rank approximation of the adjacency matrix based on its principal components can work well in practice, and also provides data dependent approximation guarantees. In particular, it was demonstrated that simply using a rank- 1 approximation based on the principal component {\mathbf{v}} can provide effective approximation for D k S. Differential privacy: In many applications such as public health, social networks, and finance, network datasets comprise sensitive information, and re-identification and other kinds of privacy risks are serious issues Yuan et al. (2024) ; Peng et al. (2012) . For instance, consider a social network where the identities of the vertices (i.e., individuals) are public, but the edges (i.e., personal contacts) are private. However, merely concealing the link structure is insufficient to ensure privacy, as an adversary can still infer the presence or absence of specific edges by analyzing query outputs from the dataset Jiang et al. (2021) . Although several privacy models have been proposed, Differential Privacy (DP) Dwork et al. (2014a) ; Dwork et al. (2006b) has emerged as a powerful and broadly adopted framework for developing algorithms that offer rigorous, quantifiable privacy guarantees without making assumptions about the adversary’s knowledge or capabilities. In the context of graphs, there are two standard notions of privacy - edge privacy, where vertices are public and edges are private. In this case, the objective is to prevent the disclosure of the existence/non-existence of an arbitrary edge in the input graph. On the other hand, in node privacy Kasiviswanathan et al. (2013) ; Blocki et al. (2013) , vertices are also private, and the goal is to protect any arbitrary vertex and its incident edges. DP algorithms have been developed for many graph problems, ranging from clustering and community detection, Epasto et al. (2022a) ; Mohamed et al. (2022) ; Nguyen and Vullikanti (2024) , to personalized PageRank Epasto et al. (2022b) ; Wei et al. (2024) , and computing different kinds of graph statistics Karwa et al. (2014) ; Gupta et al. (2012) ; Blocki et al. (2013) . There has also been work on computing principal components under edge DP Kapralov and Talwar (2013) ; Chaudhuri et al. (2012) ; Hardt and Roth (2013) ; Hardt and Price (2014) ; Balcan et al. (2016) ; Gonem and Gilad-Bachrach (2018) . However, as we discuss in Section 2 , prior methods either do not have adequate accuracy, or do not scale well even to networks of moderate size. This is the main motivation of our work. We also note that the D k S problem has not been studied under DP. Contributions: In this paper, we develop a scalable algorithm for differentially private computation of the principal component (PC) of the graph adjacency matrix under edge-DP. This also results in the first edge-DP algorithm for the D k S, leveraging the non-private low-rank approximation approach of Papailiopoulos et al. (2014) . DP algorithms achieve their privacy guarantees by adding controlled amounts of noise to non-private computations. While

Read the complete text