Differentially Private and Scalable Estimation of the Network Principal Component
Authors: Alireza Khayatian
Anil Vullikanti
Aritra Konar
Venue: Accepted by TMLR ()

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$-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.

Published in Transactions on Machine Learning Research (04/2026)
Differentially Private and Scalable Estimation of the Network Principal Component
Alireza Khayatian
olireza Chreaa,kheyttannGkakeeennn
ESAT-STADIUS
KU Leuven
Anil Vullikanti
asu9otavirginia.c edu
Department of Computer Science University of Virginia
Aritra Konar
arüno.konar@Bullwwen...
ESAT-STADIUS
KU Leuven
Reviewed on OpenReview: /t opt.r/veew..eeee.eompoe net/ forum9 WOByWorAYG
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 privale 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-specifie mechanisms for privately computing the PC under ePge-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- Reesstteeeeseeee (PTR) framework. Although computationally expensive in general, design novel approach for implementing PTR variant in the same time computation of non-private PC, while offering good utility. Our framework tests in differentiallyy-riieeee given graph is "well-behaved" or not, and then tests whether its private to release noisy PC with small noise. As a consequence, this also leads to the first DP algorithm for the Sensest-k-subgrayy problem, a key graph mining primitive. We run our method on diverse real-world networks, with the largest having million vertices, and compare utility a pre-existing bascline based on the private power method (PPM). Although PTR requires slightly larger privacy budget, average, it achieves 180-fold improvement in runtime over PPM.
manner whether
1 Introduction
Background: The principal component of a network, i.e, the eigen-vector corresponding to the largest cigen-valuc of the graph adjacency matrix (and more generally, the other principal components). has been found useful in diverse (asks in graph mining Bonacich] (2007); Das et al. (2018) Le et al. (201)). The component 24 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, c.g., social and biological networks [ohmann et al. (2010); Jalili et al. (2016); Das al. (2018). It has been shown that nodes with high eigen-vector centrality good solutions for influence maximization Dey et. al. (2019); Maharani et al. (2014): Deng et al.

---

Published in Transactions on Machine Learning Research (04/2026)
2017). Interestingly, vaccination of high eigen-vector centrality nodes has also been found to be effective in
reducing diffuuson processes Van Mieghem et al. (2011): Saha et al. (2015); Doostmohammadian et al. (2020).
More generally, eigen-vector centrality is used as 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 bioinformaties, social network analysis, and fraud detection (see Lanciano et al. (2024) and references therein).
The densest-k-subgraph (DAS) Feige et al. (2001) corresponds to vertex subset of pre-specified size & with the largest (induced) edge density in graph. The D&S problem falls within the broader class of density-based
subgraph detection techniques, which include popular measures such as the core decomposition Seidman 19883 and the densest subgraph problem Charikar (2000); Goldberg [1984). In contrast to these approaches, the DKS formulation possesses the built-in feature of explicit control over the size of the selected subgraph. This an important advantage enjoyed by D&S, as the lack of size control causes the latter approaches to output large subgraphs that are sparsely interconnected in real-world graphs Tsourakakis el al. (2013); Shin el al. (2016) On the flip-side, the D&S problem is computationally intractable in then worst-case, and achieving good approximation guarantees is provably hard under standard complexity-
assumptions |Manurnnsii
(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, was demonstrated that simply using a rank-1 1 approximation based on the principal component can provide effective approximation for D&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 verticos (i.c., individuals) are public, but the edges (i.c., personal contacts) are private. However, mercly 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. (202I). Although several privacy models have been proposed, Differential Privacy (DP) Dwork et al. (2014a; 2006b has emerged as powerful and broadly adopted framework for developing algorithms that offer rigorous, quantifiable privacy guarantees without making assumptions about the adversary's '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 provent the disclosure of the existence existence/nonn-cxieeee cxiieeetenccccccccceeeec of an arbitrary edge in the input graph. On the other hand, in node privacy Kasiviswanathan el al. (2013); Blocki et al. (2013), vertices are also private, and the goal is to protect any arbitrary vertex and its incident edges. DP a algorithms have been developed for many graph problems, ranging from clustering and community detection,
Epasto et al. 2022a); Mohamed et al. (2022): ; Nguyen & Vullikanti (2024), to personalized PageRank Epasto
et al.)
2022bb:
:
Wei et al. (2024), and computing different kinds of graph statistics Karwa et al. (2014)
Gupta
ct al.
2012): Blocki et al. (2013).
There has also been work on computing principal components under edge DP Kapralov & Talwar 2013 :
Chaudhuri et al. (2012); : Hardt & Roth (2013); Hardt & Price (2014h; Balcan et al. (2016); Gonem &
Gilad Bachrrch (2018). However, as we discuss in Scction 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&S problem has not been studied under DP.
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&S, leveraging the non-private low-rank approximation approach of Paaailiopoulos et al. (2014). DP algorithms achieve their privacy guarantees by adding controlled amounts of noise to non- non-private computations. While algorithms for privately computing PCs of (general) matrices are known, as mentioned above, one issue is that the DP guarantees provided by these methods are based worst-case outcomes across all possible datasets. This can result in adding excessive noise, which has a detrimental effect utility, since given dataset need not be representative of the worst-case. To address this problem, the work of Gonem & Gilad- Bachrach (2018) developed a technique for privately computing PCs for "well-behaved" datasets
Contributions:
2

---

Published in Transactions on Machine Learning Research (04/2026)
that inject smaller amounts of noise via the smooth sensitivity framework of Nissim et al. (2007 Such instance-specific mechanisms are appealing since they are private for every dataset, but can offer improved accuracy on "well-behaved" datasets. Our work also concerns the use of instance-specific mechanisms for computing the PC under edge-DP, albeit we use the Tespose-Test-Rleanna (PTR) framework Dwork & Lei (2009), since smooth sensitivity gives poor results in our context (see further below). In general, PTR is not "user-friendly" as it involves computations which are often challenging to implement in polynomial-time. Hence, the main contribution of our work is to develop a scalable and practical variant of PTR for private PC. Our contributions can be further summarized below.
(1) Our approach is based on output perturbation, where the principal component (PC) of the adjacency matrix is first computed non-privately followed by a one-shot noise addition step to provide DP. First, we derive a new l local sensitivity bound under edge DP (Theorem [ which we then use to highlight the large gap between the local and global sensitivities of the PC on real-world graphs. This implics that the standard approach of calibrating noise to global sensitivity Dwork et al. (2014a) leads to poor accuracy see figure D motivating the application of sestance-based mechanisms such smooth sensitivity Nissim al. 20077 or Propose-Teste Tesss-eeasse Dwork & Lei (2009). These mechanisms calibrate noise to local sensitivity- bassd estimates to provide DP, thereby offering improved privacy-utility trade-offs. However, a key challenge is that they are difficult to implement in practice, as they need not involve polynomial-time computations in general.
(2) We then derive a tight analysis of prior bounds on computing private PC via smooth sensitivity Gonem & Gilad-Bachraad (2018) (developed to address the high computational complexity of Nissim et al. (007 and show that these are very close to the global sensitivity value, in general (see Appendix Dj.
(3) Given the unsuitability of smooth sensitivity, we shift our focus to using the Propose-Test-Releee (PTR) framework Dwork & Lei (2009); Li et al. (2024). At high level, PTR requires proposing bound B for the local sensitivity of the PC on the given dataset, followed by differentially private test to see if adding noise to the PC calibrated to f would violate privacy. However, PTR is computationally very expensive in general, and the only prior work for implementing PTR for graph problems in polynomial time was [L et al.] (2023) for an unrelated problem of computing epidemic metrics. Our main contribution to introduce a computationally efficient and practical PTR variant for private PC (See Figure 2 for a flow diagram). The algorithm proceeds in three phases. In the first phase, it features a differentiillly-rriaate test to filter out graphs which are not "well-behaved" (i.e., exceed a fixed spectral gap threshold) without resulting in false positives via application of the Truncated Biased Laplace (TBL) mechanism Xiao et al. (2025). In the second phase, a private test is performed to compute test statistic ((G) that constitutes a lower bound on the distance to instances with local sensitivity exceeding proposed bound B8 based on novel technique (see Theorem 2) and more efficient procedure for selecting the parameter / (see Theorem 5 and Proposition 1. In the third and final phase, @(G) is compared against a threshold to decide privately whether the noisy principal component should be released or not.
Our methods reduce the complezity of PTR for private PC to basically the same as computation of the PC, which gives us significunt improvement in lerms of runsing lime.
We also employ the iterative private power method (PPM) ofrdardt & Price (2014) as a baseline for comparison. Through experiments real graphs, we provide compare and contrast the efficacy of these two approaches for two applications: (A1) privately extracting the subset with the top-k eigenscores, and (A2) private approximate D&S. A representative example for D&S is provided in Figure [ which depicts the edge-density (whihc measures utility) versus size trade-off on a social network with 3 million vertices and 120 million edges. The yellow line is the rank-1 1 non-private algorithm of PPapalliopoulos et al. (2014), whereas the red and blue lines depict PTR and PPM respectively. Both algorithms perform comparably to the non-private version (PPM offers slightly better privacy and accuracy). However, PTR is 700 times faster than PPM as it's one-shot noise addition mechanism.
3

---

Published in Transactions on Machine Learning Research (04/2026)
Orkut
1.0
0.9
0.8
0.7
Edge Density
0.6
0.4
0.3
Upper bound
Non-private
0.2
20, 10-9)
0.1
(e- 3,0-10--)
0.0
PTR PTR =2 3,6 10-
10a
10a
10a
Size
Figure 1: Comparison of the edge-density (y-axis) versus subgraph size (x-axis) trade-off on the Orkut social network with 3M vertices and 120M edges. PPM (blue) and PTR (red) ((eo, = (1, 7e-") attain performance comparable with their non-private counterpart (yellow). However, PTR is s 700 times faster than PPM. The standard Gaussian mechanism with noise calibrated to global sensitivity (purple) yields poor results.
2
Related Work
We briefly summarize relevant related work here. We first discuss the use of nodes with high eigen-vector centrality in different applications, and the D&S problem, and then the problems of differential privacy for graph problems and private principal component analysis (PCA).
Eigen-vector centrality and applications: Centrality metrics are common tools used network analysis. The eigen-vector centrality (also referred to eigenscore) of node i is defined the ith component of the principal component v of G Bonacich (2007): Das et al. (2018 : Le et al. (2015); this notion has been found very elfective in a number of applications. For instance, nodes with high eigen-vector centrality have been found to be effective for controlling diffusion processes on networks, both for maximizing influence or information spread Dey et al. (2019): Maharani et al. (0014; Deng et al. (2017) and for controlling the spread of epidemic processes by choosing such nodes for vaccination interventions Van Mieghem al. (2011) Saha
et al. (2015); Doostmohammadian et al.] (2020). Figen-vector centrality has also been used other domains such biological networks for identifying essential proteins and critical components Lohmann et al. (2010
Jalili et al. (0166)
The D&S problem: The D&S problem is computationally very hard, and it has been shown that an O/1og /logglog approximation is not possible under certain complexity theoretic assumptions Manurangsi
2017 (see other discussion on its complexity in Khot (2006); Manurangsi (2017): Bhaskara et al. (2012)
Efficient algorithms which work well for practical instances of DÍS range from low-rank approximat tioss ions Pa
pailiopoulos al. (2014) and the convex and non-convex relaxations of Konar & Sidiropoulos (2021) and Lu
et al. (2025). We mention in passing that there are variants of D&S, such as the Densest. at-least-k Subgraph
problem (DalkS), the Densest at-most-k Subgraph problem (DamkS) Andersen & Chellapill (2009); Khuller
& Saha (2009), and the f-densest subgraph problem Kawase & Miyauchi (2018). Although these variants impose size constraints on the extracted subgraph, these formulations do not guarantee that the entire spectrum of densest subgraphs (i.e., of every size) can be explored.
Differential Privacy for Graphs: In the context of graph datasets, there are two standard notions of privacy edge privacy Blocki et al. (2013), where vertices are public and edges are private. In this case, the objective to prevent the disclosure of the existence/non no--xxitence of an arbitrary edge in the input graph.
4

---

Published in Transactions on Machine Learning Research (04/2026)
On the other hand, in node privacy Kasiviswanathan et al. 2013 vertices are also private, and the goal is to protect any arbitrary vertex and its incident edges.
Early work on differentially private graph algorithms focused on computing basic statisties. Nissim et al. introduced DP for graph computations, providing methods to privately release the cost of minimum spanning trees and triangle counts using smooth sensitivity Nissim et al. (2007). Karwa et al. Karwa et al. (2014)
extended these techniques to other subgraph structures, such as k-stars and k-triangles. Hay et al. Hay et al.
(2009) explored DP mechanisms for releasing degree distributions, while Gupta et al. Gupta et al. (2012)
developed methods for privately answering cut queries. Node privacy, being more sensitive, is more challenging
to ensure. Kasiviswanathan et al. Kasiviswanathan et al. (2013) and Blocki et al. [Blocki et al. (2013)
addressed this issue by developing node-DP algorithms using Lipschitz extensions for subgraph counting.
Recently, two concurrent works Farhadi et al. 2022 : Nguyen & Vullikanti (2021) introduced edge DP algorithms for computing the densost subgraph (DSG), which aims to find the subgraph that maximizes the average induced degree Goldberg (1984). Building on the non-private greedy peeling algorithm of Charikar
(2000) for DSG, Nguyen et al. Nguyen & Vullikanti (2021) employed the exponential mechanism Dwork et al. 4014a) to design an (e, DDP algorithm which can be executed in both sequential and parallel versions. Mcanwhile, Farhadi et al. Farhadi et al. (2022) applied the Prefix Sum Mechanism CCan et al. (2011) to privatize Charikar's 's greedy peeling algorithm for DSG, resulting in a pure (c, O)-DP algorithm that runs in linear time. Most recently, the work of Dinitz et al. (2025) proposed an (e, 8DP algorithm that is based on using a private variant of the multiplicative weights framework [Arora et al. (2012) for solving a tight linear programming relaxation of DSG proposed in Chekuri et al. [022).. In a separate but related work, Dhulipala et al. Dhulipala et al. )022) develop algorithms for releasing core numbers with DP, which are generated using a variant of the greedy peeling algorithm. At present, we are unaware of any DP algorithm for the D&S problem.
Private Principal Component Analysis (PCA): The topic of differentially private PCA has been explored previously in various studies, including Chaudhuri et al. (2012); Hardt & Roth 2013 Kapralov & Talwar )2013); Blum et al. (2005); Dwork et al. (2014b). Initially, Blum et al. (2005): Dwork et al. (2014)) 4b) considered an general input perturbation approach for providing DP by adding random Gaussian noise to the empirical covariance matrix constructed from the data points. However, this method requires access to the covariance malrix, which is computationallyy expensive in both space and lime. Although graph adjacency matrices are not covariances (as they may not be positive semi-definite), the classic randomized response technique of Warner Warner (1655) can be applied to generate DP adjacency matrices, with the caveat that it can result in injection of large amount of noise, which manifests in creating dense graphs with very different properties from the actual dataset. This can result in poor utility for node subset selection problems (see Farhadi et al. 2022 Appendix A)).
An alternative approach based output perturbation that utilizes the exponential mechanism to output principal components with (c, DDP was explored in Kapralov & Talwar (2013): Chaudhuri et al. (2012). However, the theoretical analysis of this method shows that it incurs a high time complexity of O(n") (here n represents the dimension), which renders it impractical for application on even moderately sized datasets. Meanwhile, the work of Hardt & Roth (2013); Hardt & Price (2014); Balcan et al. (2016) consider privatizing power itcrations for computing private subspaces with DP. This itcrative approach comprises of interleaved steps of matrix vector multiplication followed by noise injection and re-normalization to provide (c, DD-P. While it can perform well in practice, selecting its parameters requires some trial-and-error and its iterative nature can result in high-complexity when applied to large datasets. Closest to our present work is the approach of Gonem& & Gilad- Bachrrch (2018), which considered using the smooth sensitivity framework of Nissim el al. (2007) to privately compute principal components via output perturbation. However, in practice, smooth sensitivity often fails to reduce the noise sufficiently. We address this issue by designing a method to siguificantly reduce the noise level in output perturbation using the propose-test-reles (PTR) framework.
3 Preliminaries
Differential Privacy on Graphs: Let G denote a collection of undirected graphs on a fixed set V of nodes. This paper focuses on the notion of edge privacy Blocki et al. (2013), where two graphs G,g' G
5

---

Published in Transactions on Machine Learning Research (04/2026)
are considered neighbors, denoted g ~ G', if they have the same vertex set and differ in exactly one edge, meaning |E(G) - -E(G') =1.
Definition 1. (c, 6)---fferrenli Privacy (DP) Dwork et al. 2014a). Let O and 5 E [0, 1]. A randoized
algorithm A(-): G + g is (e, if:
Pr(A(G) E S) & exp(c) ES) +
(1)
for any outcome S C RR* and for any pair of neighboring datasets (G, g") that differ in a single edge.
Function Sensitivity: Dwork et al. (2014a). Consider a function f: G - R*. The local by sensitivity of I exhibited by a dataset 9 E G is defined as LS,(G) = gaxg'.g~g' [l] - ((9')ll,, where the maximum is taken over all neighboring datasots g' which differ in one edge from G. The global lg sensitivity of f is then GS maxges LG). If we computed the sensitivily calculations w.r.l. the E norm instead, we would obtain the & local and global sensitivities of f. Adding ii.d. Gaussian noise to f()) with variance appropriately calibrated to global lg sensitivity is guaranteed to satisfy (c, ()DD) Dwork et al. (2014a). By adding Laplacian noise calibrated to global & sensitivity, the output is guaranteed to be (c, D>-DPDDork et al. 2014 An important property of DP is that applying post-processing on the output of a (e,6)-DP mechanism does not weaken the privacy guarantee.
Private principal components: Consider an unweighted, undirected simple graph G (V,E) with vertex set V = [1,...,n] n and edge set & C V V. The x symmetric adjacency matrix of g is denoted as A. The eigen-values of A are arranged in non-increasing order of their magnitudes; i.e. we have |^il 122 2 ... |An]- The principal tigen-gap of G is defined as GAP(G)= == |Ail - [Aal, while the principal component v of A is the eigen-vector associated with [Ail- Tf the graph 9 represented by A is connected, the
Theorem Meyer (2023) asserts that v is element-wise positive and A > O. Following our earlier notation, we consider the function f()) = v, and (g) = max [|v--'l v'Il2 In this paper, we develop new techniques for privatizing v under edge-Di DP; with the following two applications.
(A1) Eigen-vector centrality: For a node its component e; in the principal component v is referred to as its eigen-vector centrality eigenscore. Nodes with high eigen-vector centrality (i.e., the k-largest entries of v) have been used in number of applications, such as identifying influential users in social networks and for targeted interventions for controlling epidemic processes, e.g., Maharani et al. (2014); Van Mieghem et al. (2011) Saha et al. (0055). Here we study how to find the k-largest entries of v with edge-DP.
(A2) Densest-k--uugraphh: Consider a vertex subset S C V which induces a subgraph Gs- = ES, where Es- = ffu, u) E & u, v E S). The edge density of the subgraph Gs is defined as d(Gs) = |Esl/ which measures what fraction of edges in 9s are connected. Note that larger values correspond to dense quasi-cliques, with a maximum value of for cliques. The --uusest--Subgraph (DKS) problem FFige et al. (2001) seeks to find subset of k vertices S C V that maximizes the edge density. Formally, the problem can be expressed as follows
x A'
dr = max X
(2)
where Xx= = fx E (0, : eTxx = k}} represents the combinatorial selection constraints. Here, each binary vector x E {0, 13" represents a vertex subset S V, with x; = 1 S and x; = 0 otherwise.
4 Analyzing sensitivity of principal components
In order to compute the principal component of A under edge-DP, straighttorward idea. is to apply the technique of output perturbation. This can be achieved by computing the global sensitivity of v and then applying the Gaussian mechanism to provide (c, 8) DP Dwork et al. (0006a). Since output perturbation is a one-shot noise addition scheme, it is computationally fast, as it incurs only O(n) complexity. However, the global le sensitivity of v is large; at most v2 (Gonem & Gilad Bachrach, 2018 Theorem 5). This implies that large amount of noise has to be injected to achiove a target privacy requirement, which can result in a severe degradation in utility. On the other hand, the local lg sensitivity can be substantially smaller on many graphs. Note that adding noise calibrated to the local sensitivity is not guaranteed to be privacy preserving
6

---

Published in Transactions on Machine Learning Research (04/2026)
Table Comparison between local and global sensitivity for real-world datasets.
Graph
π
GAP
LSv
GSv/LSv
FACEBOOK
4k
36.9
7e-3
202
PPI-HUMAN
21k
70.8
4e-4
3535
SOC-BI.OGCATALOO
89k
335.9
7e-4
2035
FLICKR
105k
101.3
1c-3
1414
TwIroH-GAMER
168k
148.4
2e-3
539
ORKUT
3M
225.4
1e-2
141
Nissim et al. (2007). However, if we observe that the local lg sensitivity of v is much smaller than v2 on given graph, we can employ instance-specifie noise addition schemes Nissim et al. (2007) ; Dwork & Lei (2009), which provide DP by injecting noise calibrated noise to local sensitivity calculations. We demonstrate that under mild requirement on the spectral gap of 9, the following bound on the local sensitivity can be derived.
Theorem 1. If GAP(G) v2(V2+ + 1), then the local &a sensitivity of under edge-DP is at most
/ + +
2 "000
20, LSv(G) GAP(g) GAP(G))
where Cx = /22000 + u and U=(1) and 0x(2) denote the largest and lecond-largest entries of respectively.
Proof. Please refer to Appendix B
Note that the numerator term in the above upper bound is at most 2v2/|v/loo. We conclude that for graphs whose eigen-gap GAP(G) exceeds v2(v2= + 1), the local fz sensitivity of the principal component v is small when the entries of v are "spread out" in magnitude (i.c., || is small) ) and the cigen-gap is large.
The value of this estimate for various real-world graph datasets presented in Table and contrasted with the global sensitivity upper bound of /2. It is evident that the local sensitivity of on real graphs can be least 2 orders of magnitude smaller compared to the global scnsitivity estimate of v2. This motivates the application of instance-speciffe noise-addition mechanisms for providing DP on such "good" instances, the first of which we consider is the smooth sensitivity framework of Nissim et al. (2007). However, practical application of this framework challenging, as entails computations which need not be polynomial-time. The prior work of Gonem & Gilad-Bachradd Bachrach (2018) developed tractable smooth upper bounds on the smooth sensitivity for computing principal components of general datasets; albeit not for graphs under edge-DP. In Appendix [ we provide rigorous analysis which shows that in our graph setting under edge-DP, the obtained smooth upper bound is very close to the global sensitivity estimate of v2.
5 The Propose- Rele-Re Mechanism
Since adopting the smooth sensitivity-based approach of Gonem & Gilad-Bachrach (2018) does not yield tangible improvements over the global sensitivity, we explore the application of an alternative instanco-speeific noise injection mechanism; namely, the Propose-Test-Relee (2009). While PTR and smooth sensitivity share common aim (i.e., exploiting local sensitivity to add instanco-specific noise while preserving DP), PTR is distinct paradigm, which presents its own unique challenges.
(PTR) framework introduced in Dwork & Lei
a high level, the PTR framework comprises the following steps. Given an upper bound / on the local & sensitivity (g), test (in a differentially private manner) whether the current dataset is "close" to another with high sensitivity. If so, the algorithm can refuse to yield response; otherwise, it can release a private principal component with small amount of noise (scaled to (3). The main difficulty in implementing PTR
7

---

Published in Transactions on Machine Learning Research (04/2026)
lies in the "test" component, which requires computing the Hamming distance to the nearest dataset G whose local sensitivity (g') exceeds B. Computing such sensitivity-1 statistic requires solving the following problem
(G) = min d(G.g) s.to LS.(G") )
(4)
which is difficult in general. In a recent. breakthrough, it was shown in Li et al. (2024) that the PTR framework can still be successfully applied if (()) is replaced by any non-negative, sensitivity-1 statistic ((G) that is a global lower bound on 7()); i.c., we have
(9) 2 (()) 2 0,V g.
(5)
This results in the following modified PTR framework; first introduced in Li ct al. (0024)
1. Propose upper bound / on the local l sensitivity LG).
2. Compute lower bound (G) on the distance (G) defined in problem equation 4
3. Release ((g) == ((g) + Lap
4. If ((g) - lm(1/6), return no response.
5. If ((G)= Z ln(1/5) return + N (0,0² II),, where o² = -2,3 log((/8)//{
The upshot is that if we can find suitable surrogate function o6-) which satisfies equation 5 and is simpler to compute compared to solving equation 4 for 7()), then we can apply the framework successfully. It is important note that | need not be private for the correctness of the above technique to go through. The work Li et al. (2024) shows that the output of the modified-PTRR algorithm is (E1 + 6). However, it does not provide general recipe for computing such requisite surrogates. Hence, major contribution of our work lies in constructing a suitable o(-) for the given problem. Below, we provide an overview of our approach (see Figure 2 for a flow-diagram).
Overview of Algorithm [ At a high level, our algorithm privately releases the principal component of graph using a one-shot output perturbation scheme, while avoiding the excessive noise required by worst-case global sensitivity bounds. The main idea is to test whether the input graph is sufficiently distant from other instances with high local sensitivity in differentially private manner, and to use local sensitivity-baser calculations to release a noisy eigenvector only if this test succeeds. Concretely, the algorithm can be broken down into three phases, as illustrated in Figure 2
Phase I: A private gap test is carried out to determine whether the graph lies in a "well-behaved" regime with sufficiently large spectral gap.
test is performed check whether the graph is far from instances with large local sensitivity. If the gap test fails, (i.c., the algorithm determines that the graph lies in the small-gap regime), then it treats the graph unstable, with O distance to instability. On the other hand, if the gap test succeeds, the algorithm performs conservative, but tractable test to lower bound the true distance to unstable instances.
Phase 11: Depending on the outcome of Phase 1, a follow-up ciltance-t--instabile
Phase III: A private check is performed via the Laplace mechanism to determine whether the computed distance exceeds a fixed threshold. Tf the test fails, the algorithm does not release a response w.h.p. Otherwise, relcases a private estimate of the principal component by adding Gaussian noise calibrated to a data-dependent sensitivity bound.
Next, formalize the main ideas underpinning our approach.
Construction of o(-): Our goal is to construct surrogate o(-) which satisfics equation 5 for every graph G. For this task, we consider two regimes: (a) regime where the eigen-gap of G is "large enough" and (b) a complementary regime where the eigen-gap is "small", We consider each regime separately, and make these notions concrete. First, we show that for case (a), the local & scnsitivity of on g' can be appropriately upper bounded in "simple" terms. Formally, we have the following claim.
Theorem 2. Assume that the following two conditions hold:
(A1) GAP(G) > 2(V2+1) (A2) M(G.9") < (1 (1-12) GAP(G).
8

---

Published in Transactions on Machine Learning Research (04/2026)
B
(( (equ. 17)
((C)
(n(1/)
(equ,
Gauss
Phase
No
Yes
(w.p
8t
Release
2.
No response
No
GS
Phase
Yes
(w:p
Yes
No
(())
(()
> 0.
((G)
O(g)
Inf3/91
Phase
TBLM
Phase
Figure 2: Flow diagram of the proposed PTR algorithm Input: Undirected graph G. Under edge-DP, the edges are private but the identities of the vertices are public. The algorithm proceeds in 3 phases, starting from bottom left. Phase The truncated biased Laplace mechanism (TBLM) used privatize the spectral threshold function f()) == GAP(G) t, where the threshold t == 2(v2 1). The output f(g) is then used to test G lies in the large-gap or small-gap regime. Phase II: Depending on the outcome of Phase I, the distance to instability oG)) is computed and privatized via the Laplace mechanism to obtain @(G). Phase III: The output ((G) is compared against threshold to decide privately whether the noisy principal component Vptr should be released or not.
Then, the local l sensitivity of g' can be upper bounded by
2d(G.
= GAP(g) d(9.g))
+ ca GAP(S)
(6)
Proof. Please refer to Appendix C
Consequently, we can replace (S' in equation 4 with the upper bound 0(G'). Doing so yields the problem
o( min d(G,g") s.t. 0(g') 2 8
Since O(G') upper bounds (G'), replacing (G) 2 8 with O(G') enlarges the feasible set of equation Hence, it follows that that equation is relaxation of equation whose solution ((G) yields lower bound on the true PTR distance 7(),, as desired. Furthermore, by design, o(G) is non-negative and has & scnsitivity equal to 1. Hence, ((G) is suitable candidate for implementing the PTR framework, as it guarantees that equation is satisfied for all graphs for which GAP(G) 2(v2 + 1), which corresponds to the "sufficiently large" gap regime.
Next, we consider the complementary the small gap regime (b), where GAP(g) S 2(V2 1). Devising a suitable surrogate that. obeys equation 5 is more challenging compared to the previous case, since even the local sensitivity bound of Theorem I need not apply here. Hence, goal is to make the algorithm reject such "unfavorable" datasets w.h.p. To this end, we devise surrogate for 7(9) which outputs 0 for such datasets. Clearly, such a surrogate satisfies equation 5 A valid choice is the following optimization problem
min d(g,g')
(8)
s.t. 0(g") 2 0.
9

---

Published in Transactions on Machine Learning Research (04/2026)
Compared to equation 7 the proposed bound B is replaced by 0 in the RHS of the constraint. Regarding the above problem, we have the following claim. Lemma 1. For every graph 9, the oplimal value of problem is 0.
Proof. See Appendix
We would like to use equation 8 in PTR only for graphs belonging in the small gap regime GAP(g) S 2(v2+1). For other "well-behaved graphs whose gap exceeds the aforementioned threshold, we would like to employ the surrogate equation For this task, we can combine problems equation 7 and equation g into the single optimization problem
( == min d(G,g')
(9)
s.t. 0(G') 2 B ((GA(()) - t),
where 6: : 2(v2+ 1) is the gap threshold, and w(.) is the indicator function u(æ)) : [=>0). In the large gap regime, problem g reduces to 7 Otherwise, it boils down to 8 with value O. In Appendix H we show that for graphs whose spectral gap is below the threshold t = 2(v2+ + 1), the PTR algorithm is designed to return No RESPONSE with probability at least 1- 6, as intended. An issue that instantiating equation first requires checking whether the gap of G exceeds the threshold L or not, which need not be privacy-preserving Our proposed solution is to first privatize the function f(g) GAP(g) - and then employ it in equation Next, describe how to perform such operation.
Privatizing (() via the Truncated Biased Laplace Mechanism (TBLM): In order to privatize (g), we first need to compute the global & sensitivity of f(.) under edge-DP. A calculation reveals that
gSy = max (S(G) - f(g') max (GAP(g) GAP(G")) S 1. 9~96
(10)
9~9
Hence, it suffices to add Laplacian noise Z ~ Lap(O, 1/co) to f(9) to guarantee (co, 0)-DP Dwork et al. (201 4a) Denote the noisy output f(G) == (G) + Z. However, the standard Laplace mechanism adds two-sided symmetric noise to f()), which can result in the outcome that f(g) S 0, but f(g) > 0. This give rise to
undesirable false- calse-positives where we incorrectly employ the surrogate equation 7 instead of equation g To
prevent such an occurrence, we apply the truncated biased Laplace mechanism (TBLM) Xiao et al. (0025 )
which adds one-sided noise to provide (5o, do)- Formally, given parameters ja > 0, X > 0, and 0, the density of TBL noise is given by
Pr(Z = =) Zn.A.R
- 1(0g:gm]:
(11)
where [(og=< the indicator function of the interval [0, RJ,, and Zn,ARR = Pr(O S = S R) is the normalization parameter. Note that the samples from the TBL distribution are guaranteed to be positive and bounded. Furthermore, generating such samples can be accomplished efficiently (see Appendix F.
Fact 1. Xiao et al., 2025 Lemma 1) Let the scale parameter x= =//E,, the range parameler R R= 2p and the
mean parameler is al least J. 2 1 + 1 log I (1- (1-e))))). Then, adding such (1,, X, R) TBL noise to a
t0
26g
1-sensitivity function provides (co. DD.
Stated differently, for a given pair (1, eo), the smallest achievable 8n given by
8, 1 e 10-0(111)) (1 (1-e- -aso).
(12)
It is evident that for fixed c0, larger values of p allow smaller values of on to be chosen. Let 7 > be drawn from (u, X, Rt) TBL distribution. We propose to privatize f()) via f(G) f(G) Z. If the parameters of the TBL distribution are chosen according to Fact 1 then f(-) is (Co. DD)
Analyzing the sensitivity of ((-): After privatizing (()), we finally consider the optimization problem
(())= min d(G, )')
(13)
s.t. 0(g') 2 3 ul ((())
10

---

Published in Transactions on Machine Learning Research (04/2026)
In order to perform PTR with <(-), need to compute its éi-sensitivity under edge-DP. Let GS denote the global sensitivity of ((.). In our framework, it turns out that GSş can be larger than 1, unlike the modified PTR framework of Li et al. (2024). This is showcased by the following result.
Lemma 2. The & global sensitivity of Φ(-) satisfies
S = 2+ 22H,, -1k <1,
G
(14)
S2 : 1,
otherwise.
Proof. Please refer to Appendix
G
After having described the construction of 6(-) and analyzing its sensitivity, we are ready to establish the privacy properties the PTR algorithm.
Theorem 3. For every graph G, the PTR algorithm is (eo + te + E2, 60 + 8) snfferentially-priodde where ón is computed based on equation 12
Proof. Please refer to Appendix
Taking a step back, its worthwhile to contrast our modified PTR algorithm with that Li et al. (2024) Although we adopt the same idea as Li al. (002)), the main difference that we need to perform an extra differentially private check to test if the given dataset lies in the large graph regime not. If the latter case arises, the algorithm will stop w-p. 1 5. The second difference is that the sensitivily of <(-) depends on the parameter μ used in the TBL, which is consequence of the fact that the proposed bound used in problem equation 9 depends on the outcome of u(f(G)). These modifications necessitate a larger privacy budget compared to the PTR algorithm proposed in Li el al. 2024). Nexl, we turn to the practical considerations of selecting 3 and evaluating Φ.
Valid choices of Sclecting the parameter 3 is a key component of implementing PTR. The following theorem specifies the range of 3 values that valid for the PTR algorithm.
Theorem 4. For any choice of B E (Bi, Bu), the statistic Φ(-) can be computed according to equation 17 where the lower and upper limits are given by
3r = 2
22 =()
22 :B:== = GAP(E) 2 v2+ 1 1/211)
2/2
22
(15)
GAP(G)
(2)
Proof. Please refer Appendix
Computing (()): Given (3t, Bu), the tractability of the PTR framework hinges on ability to solve problem 7 in efficient manner in order to compute o(.). By construction, the problem asks to find the smallest value of ((G,9") such that the inequality
2
2d(G. GAP(G) + 2 + v2
2
(16)
GAP(C) d(
is valid. Observe that for a given value of B, all the involved parameters can be readily computed from G. Furthermore, the fact that 0(G") (i.e., the LHS of the above inequality) monotonically increasing with d(g, G'), facilitates simple solution. In fact, for given 3, the statistic Φ(-) can be computed closed form according to the formula
B GAP? 2GAP(9) /22 (1) + 22
((
(17)
4 4 B. GAP(G)
11

---

Published in Transactions on Machine Learning Research (04/2026)
Policy for selecting 3 Finally, we need to have policy for selecting suitable B E (Bi, Bu). From equation 17 it is evident that (()) increases monotonically with / E (3), Bu). Hence, for fixed set of privacy parameters 6), larger values of B correspond to higher likelihood of the noisy statistic å(g) exccoding the threshold (GS, ln(1/o))/ei; which in lurn increases the odds of the PTR algorithm yielding a response. However, larger values of / also lead to increased noise injection in the release step of PTR. Hence, suitable f should strike the "sweet spot" between minimizing noise injoction and maximizing the odds of a succossful response. Next, we demonstrate how the choice of 3 impacts these two conflicting objectives.
For a given 3, the PTR algorithm succeeds if the value of the noisy statistic ((g) exceeds the threshold (GS, ln(1/6))/e1, which implies that the algorithm responds with an output according to step Hence, the success probability of PTR corresponds to the event Prob(e(g) 2 (GS& log Log(1/6))/Ei), where the randomness is w.r.t. the Laplace random variable Lap(0, 1/a). We now reveal how the success probability is affected by the choice of B. To this end, it will be convenient express & as ((G) = [T)]] where 7(9) is the fraction in equation 17 Note that by design, we have [=(9)] + 2 (GG) 2 TG)) Since T(.) increases monotonically with B, increasing T(.) also increases Φ(-), which in turn, directly influences the outcome of the threshold test. Next, we demonstrate that controlling the value of r() through 3 is sufficient to derive lower bounds on the success probability of PTR.
Theorem 5. Let (9)) = [T())] where r(9) is the fraction in equation 17
If 3 is selected to satisfy
T()) = (p GSa) log(1/8) V p (0.
(18)
61
then the success probability of PTR ot least 8" 2
Proof. Please refer to Appendix
Intuitively, the smaller the value of p, the closer the value of ((-) is to the threshold (GSg log(1/8))/ei); and hence the lower the probability of success. This is captured by the above theorem, which shows that as p decreases, the success probability diminishes at the rate 1- ((80--1). As p 1, the lower bound on the success probability shrinks to 1/2.
The value of 3 which satisfies equation 18 is given by
2(p + log(// GAP(S) /22 (2())) + =2(22)
2 GAP
8
(19)
GAP(G) (p GS,)) log()) (1/0)/E
We can obtain the following insights from the above formula. First, fixing all parameters in equation 19 except P; we see that diminishes as p is reduced. We conclude that smaller values of p result in the injection of smaller amounts of noise, but this comes at the expense of reduced odds of the algorithm succeeding. Hence, the parameter p directly controls the trade-off between noise-injection levels and the success probability. Second, fixing all parameters except the graph dependent quantities GAP(G) and / VoZ.0) + 2 we observe
V v + (a) GAP(g)
that B 0
which implics that graphs with large spectral gap and small spread in the
energy of the entries of v are amenable to smaller levels of noise injection. In Appendix K we show that the family of expander graphs Hoory et al. (2006), which mimic several properties of social networks Malliaros & Megalooikonomouu (2011), fulfill both conditions.
We conclude with a final sanity check to ensure that 3 computed according to equation 19 lies in the interval (3),
Proposition 1. For fixed graph with spectral gap GAP(G), and parameters 61, S.p, the condition
log(1/0) (1 1/v2) (p+ GS.)
GAP(G)
3 (B,, Ba))
61
Proof. Please refer to Appendix L
12

---

Published in Transactions on Machine Learning Research (04/2026)
Algorithm 1: PPC via PTR (1,
Input: Symmetric A E R P. V. H. privacy parameters eo, 61,61,22 62, 6 > 0.
Output: Private PC Vptr.
Compute ón based on equation
Compute based on equation
// Phase I: Private gap test: check whether the graph well-behaved Sample TBL(,, = 2/s).
Compute f(G)= = f(G) 2. if f(G) then Compute ((G) based on equation 17
else
(( 0.
end
// Phase II: Private distance computation
if
1 f(C) then
Set G = (2 v2)u.
else
Set G = 1.
end
Compute ((G) o(g) + Lap
GSc
// Phase III: Private release via output perturbation if d(G) > G5 (o(1/8) then
Compute Vptr N
20 log(2/8))
In)
Return: Vpsr
Vptc
else
Return: No Response.
end
The final proposed solution to approximate D&S via PTR is presented in Algorithm Note that the steps of the algorithm are closed-form, and hence it can be executed extremely quickly.
6 The Private Power Method
We consider the Private Power Method (PPM) of Hardt & Price (2014) as bascline for computing private principal components under edge-DP. In essence, PPM is a "noisy" variant of the classic (non-private) power method which computes the principal component of a matrix an iterative fashion. Executing each step entails performing a matrix-vector multiplication, followed by normalization. In Hardt & Price (2014), this algorithm made DP by adding Gaussian noise each matrix-vector multiplication, followed by normalization. By calibrating the variance of the Gaussian noise added in each iteration to the &z-sensitivity of vector multiplication, the final iterate of PPM (after pre-determined number of iterations have been carried out) can be shown to satisfy (c, D)D.. Hence, in contrast to PTR, PPM is not one-shot noise addition scheme. Furthermore, its output set is a singleton a noisy principal component satisfying (e, DP, which can reflect a smaller privacy budget compared to PTR. The privacy model considered in Hardt & Price 2014)) defines a pair matrices and A' to be neighboring if they differ in one entry by at-inost 1. As per the authors of Hardt & Price (2014), this is most meaningful when the entries of the data matrix A lie in [0, 1]. Note that when A and A' correspond to pair of neighboring adjacency matricos, this naturally coincides with the notion of edge-DP for undirected graphs.
The complete algorithm is described in Algorithm
2 According to Hardt & Price 2014 Theorem 1.3), after GAP(C) iterations, the output V.. of PPM satisfies (D and with probability at least 9/10, it holds that
I. = of
logn
maxxe(r) llvz vn GAP(G)
- (I-viVZ)vll S s0
(20)
13

---

Published in Transactions on Machine Learning Research (04/2026)
In terms of computational complexity, each step of PPM requires computing sparse matrix-vector mul- tiplication, which incurs ((m) complexity, followed by noise addition and re-normalization, which incurs an additional ((n) time. Hence, each step has complexity order O(n + m). After L iterations, the overall is choson according to (Hardt & Prico 2014 Theorem 1.3), this results in complexity of order ((()1 (m + m) logn)/GAP(G))
complexity is O((n + m).
Algorithm 2: PPC via PPM (A, L, c,
Inpuu: Symmetric A E RRxx, no. of iterations L, privacy parameters O.
Output: Private PC Vppma-
Initialize: Let Vo be random unit direction and set c-1 V 4L log (1/6).
for f= to L do
Generate ge ~ NO, live-1 o") c R Avi-1 + Normalize V: we/l wella
Compute
end
Return: Vppm VL
7 Applications
Let Vpriv denote a (c, edge-DP estimate of v. In this section, we explain how Viriv can be utilized for the following applications.
(A1) Private top-k eigenscore subset extraction: In the non-private scenario, computing the subset with the largest eigenscores equivalent to solving the problem
X arg maxv' x, XEXx
(21)
since v is wlement-wise non negatieee The solution is given by the support of the k-largest entries v, and can be accomplished O(n log k) time. the private sctting, Vpriv need not be clement wise non-negative general. Hence, in this case, we solve the problem
K arg max VV X xE N'.
(22)
Note that the poot-procossing property of DP implics that & also obeys (c. In order to solve the above problem, define the pair of candidate solutions
arg x
priv
X
(2)
T arg min Vprivx xeXx
(23)
Note that x Between these two candidates, the one which attains the larger objective value corresponds to the solution of
(2) (1) and x correspond to the support of the k-largest and k-smallest entries of Vpriv respectively.
equation 22 i.e., we have
& max |v x (E()2)
(1)
(24)
Thus, the post-processing step remains computationally efficient, as only requires examining an additional candidate solution compared to its non-private counterpart 21
(A2) Private DAS: Problem equation 2 is NP-hard and difficult to approximate Manurangsi (2017]
Jones et al. (2023). As a result, resort to the low-rank approximation scheme of Papailiopoulos et al. (2014), which uses the principal component to approximate D&S. The best rank-one approximation of the adjacency matrix A is denoted as == Aiv Applying the rank-one approximation of A to the objective function problem equation problem 21 and be solved (n log k) time. The work of Papaalliopouss et al. (2014) showed that such a subset of nodes constitute dense subgraphs in real-datasets, and provide a data-dependent approximation guarantee for D (see A Appendix M.
equivalent to solving the problem x; = maxxex. vTx x, which is the same as
14

---

Published in Transactions on Machine Learning Research (04/2026)
Table 2: Summary of network statistics: the number vertices (n), the number of edges (m), the eigen-gap, and the network type.
Graph
7
m
Eigen-gap
Network Type
FACEBOOK
4K
88K
36.9
Social
PPI-HUMAN
21K
342K
70.8
Biological
SOC-BLOGCATALOG
89K
2.1M
335.9
Social
FLICKR
106K
2.32M
101.3
Image ronshio
TWITCH-GAME
168K
6.8M
148.4
Social
ORKUT
3.07M
117.19M
225.4
Social
In the private setting, we now solve the following rank-1 approximation problem
& arg max V Xr XEXL
(25)
to obtain the final output &R- Since priv may not be element-wisc non-negative, as argued previously, it suffices to examine the top-k and bottom-k support of Vpriv, and then output the candidate that achieves a larger objective value.
8 Experimental Results
Here, we test the efficacy of the proposed DP algorithus on real graph datasets in terms of their privacy-utility trade-off for applications (A1) and (A2) and their runtime.
8.1 Setup
provides a summary of the datasets, which were sourced from standard repositories Kunegis (2033; : Jure 2014). All experiments were performed in Python on Linux work-station with 132GB RAM and Intel 17 processor. We used the following settings.
Datascts: Table
2
(1) PTR:
For the TBLM, we set 6o) = (e and = 3t ~ 14.48. We also set the other privacy budget parameters as (6 = 62 = = 3), while we set 5 5= log(m)/mm mm, where m is the number edges in each graph. We set the lower bound on the success probability of obtaining a response in Algorithm to be 0.95, and then, based on Theorem 5 set p ==1 (1/ (o)).
Handling No responses: A potential issue with PTR mechanisms is the frequency of returning No RESPONSE. In our framework, this can happen due to (a): the dataset not clcaring the private gap test in phase I or (b): the dalaset clearing the gap Lest but failing the threshold test for release in Phase III. For the latter case, Theorem 5 provides an explicit lower bound on the success probability, which allows end-users to directly control the probability of successful private relcase via specification the parameter In all experiments, the datasets we used successfully cleared the gap test, and we selected p so that the probability of release is least 0.95. We empirically observed that PTR returns a valid output the vast majority of trial runs across all datasets (see Table 4 For general datasets, if a "no response" is obtained, one could repeat the PTR mechanism (since it is very fast) or increase the lower bound on the success probability to improve the odds of response. However, this also increases 3 and results in addition of greater levels of noise to the principal component. In the event that the mechanism repeatedly returns "no response", then one could fall back to using PPM.
(2) PPM:
We set (e = 3) and the parameter was fixed to be (6 = log(m)/m) across all datasets. An open question with practical implementation of PPM how to seloct the number iterations L, which has to be specified beforehand. The main issue is that (Hardt & Price. 2014] Theorem 1.3) only provides the order of iterations required to achieve certain utility bound, which scales like O A logn)). We experimentally observed that simply setting L
A logn provides good empirical performance across the different datasets. GAP(O)
15

---

Published in Transactions on Machine Learning Research (04/2026)
Table 3: Execution time to privatize the PC.
Graph
PPM (ms)
PTR (ms)
Speedup
FACEBOOK
13.6
0.07
194
PPI-HUMAN
58.6
0.32
183
AOC-BI.GCCATALOG
283
1.64
172
FLICKR
587
1.83
320
GAMERS
7781
2.25
3458
ORKUT
29660
43.14
688
Performing more iterations typically degraded the performance of the algorithm, in addition to also increasing the run-time complexity.
Further results for more detailed investigation of the proposed solutions across different values of the privacy parameters can be found in Appendix
FACEBOOK
PPI-HUMAN
SOc- BOC-BLLGCAATALG
FLICKR
GAMERS
ORKUT
98%
99.6%
98.6%
96.9%
99.6%
98.5%
Table 4: Empirical success rates the PTR algorithm across different datasets with (eo, 6n) (1, 10 10-7),er = 62 = 3, log(m)/m,, (m)) the number of edges.
8.2 Results
Timing: As shown in Table 3 PTR significantly outperforms PPM in terms of execution time required to output a private PC. We obtain at least a 170-fold speedup across all datasets, and on the TWITCH-GAMERT dataset we obtain a 3500-fold speedup. This is because the steps of the PTR algorithm can be computed in closed form, and it adds noise once, which makes it fast. On the other hand, PPM incurs O(n + m) complexity with every iteration, which makes the overall algorithm slower. These results underscore the practical benefits of our PTR algorithm. Given that the original PTR algorithm Dwork & Lei (0099 is not known to be polynomial-time, fast algorithm.
modifications and insightful parameter selection come together to result in
(A1) Private Top-k eigenscore subset extraction: In order to measure utility, for each private subset extracted via Algorithms | and 2 we compute its Jaccard similarity with the non-private subset. The results for the 4 datasets with the largest eigen-gaps are depicted in Figure 3 Each sub-figure plots the Jaccard similarity versus subset size & for both private algorithms specific dataset (averaged across 200 Monte- Carlo trials). For these datasets, the two algorithms offer comparable utility under a modest privacy budget- in fact, the private top-k subsets exhibit high similarity with their non-private counterpart. PTR incurs a larger overall privacy budget compared to PPM (roughly twice more in terms of the parameter) to attain the same utility. This can be attributed to the fact that PTR outputs 3 noisy parameters privately, whereas PPM only outputs only one. As explained before, from a utility-time complexity perspective, PTR performs better in general.
(A2) Private D&S; The empirical performance of Algorithms and 2 across different datasets is depicted in Figure 4 Each sub-figure plots the edge-density versus size curve obtained using the two different algorithms. As a bascline, we consider the non-private algorithm as described in Papailiopollos et al. (2014). In addition, we also include an upper bound for the edge density of the D&S (See appendix M. To generate each plot, we executed Algorithm| [ and and Algorithm [ for 100 different realizations, with each private PC used to generate a different edge donsity-size curve. For cach subgraph size k, we depict the average odge density attained by each method across all realizations, within one standard deviation (vertical lines). From Figure it is evident. that both PTR and PPM output subgraphs whose edge-density closely matches that of
16

---

Published in Transactions on Machine Learning Research (04/2026)
BegGoldnn
Tweter
Onal
Top4
Taps
Figure 3: Results for private top-k eigenscore subset detection. Jaccard similarity (y-axis) vs. subset size k (x-axis): PTR (red) (co, 60) = 7 x 10-7), 61 62 = 3, 61 = log(m)/m, PPM (blue) = 3, ō = log(m))m)
non-private (yellow), (m): the number of edges.
Pacebook
06
66
Size
Twitch
Orbut
3.5
14c
12
121
1P Siee
35
Figure 4: Results for private D&S. Edge density (y-axis) vs. subgraph size k (x-axis): PTR (red) (co. 60) = x1,7x 10-7), PPM (blue), non-private (yellow), and the upper bound on the maximum attainable edge density (black). (m): the number of edges. Higher densities are better.
the non-private solution, again for a modest privacy budget of E 2 3. Again, PTR is faster in extracting highly-quality private dense subsets, at the expense of a larger privacy budget.
Based on our findings, we conclude that both PTR and PPM offer good utility in the applications considered compared to the non-private baselines. The advantage of PTR its transparent parameter selection and its computational efficiency, allowing it to scale to large networks much more casily, at the cost of slightly higher privacy budget.
9 Conclusions
In this paper, we considered the problem of privately computing the principal component of the graph adjacency matrix under edge-DP. Motivated by the large gap between the local and global sensitivity on real-world datasets, we employed the Tropose-Test-RReeen (PTR) framework. Owing to its instance specific nature, PTR can offer good utility on well-behaved datasets by injecting small amounts of noise to provide DP. However, it is computationally expensive. To overcome this challenge, we develop a new practical and powerful PTR framework which obviates the computational complexity issues inherent in the standard framework, while facilitating simple selection of the algorithm parameters. As a consoquence, our PTR algorithm also results in the first DP algorithm for the kesseat---uubgraph (DKS) problem, a key graph mining primitive. We test approach on real-world graphs, and demonstrate that it attain performance
17

---

Published in Transactions on Machine Learning Research (04/2026)
comparable to the non-private solution while adhering to modest privacy budget. Compared to an iterative baseline based on the private power method (PPM), PTR requires a slightly larger privacy budget, but is more than two orders of magnitude faster on average. DP techniques need to be scalable to larger datasets, for privacy practices and guarantces to become more commonplace. Our paper makes advances towards this goal.
10 Acknowledgments
A Alireza Khayatian and Aritra Konar were supported by the KU Leuven Special Research Fund BOF/STG-22- 040. Anil Vullikanti was partially supported by NSF grants CCF-1918656 and CNS-2317193, DTRA award HDTRA1-24---00222 and the Commonwealth Cyber Initiative Cybersecurity Research Award.
References
Reid Andersen and Kumar Chellapilla. Finding dense subgraphs with size bounds. In International Workshop on Algorithms and Models for the Web- Web-Gruph Gruph, pp. 25 37. Springer, 2009.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: meta-algorithm and applications. Theory of computing, 8(1):121-164, 2012.
Maria-Florina Balcan, Simon Shaolci Du, Yining Wang, and Adams Wei Yu. improved gap-dependency analysis of the noisy power method. In Conference on Learning Theory, pp. 284 309. PMLR, 2016.
Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, and Yuan Zhou. Polynomial integrality gaps for strong sdp relaxations of densest k-subgraph. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pp. 388 405. SIAM, 2012.
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Proceedings of the 4th conference on Innovations in Theoretical Compuler Science, pp. 87 96, 2013.
Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq framework. In Proceedings of the twenty-fourth ACM SIGMOD-STGACT-SSIAART symposium Principles of dalabase systems, pp. 128 138, 2005.
Phillip Bonacich. Some unique properties of eigenvector centrality. Social networks, 29(4):555 564,5664444 2007.
T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions Information and System Security (TISSEC), 14(3):1 24, 2011.
M. Charikar, Greedy approximation algorithms for finding dense components a graph. In Intern. Workshop on AACO, pp. 84-95. Springer, 2000.
Kamalika Chaudhuri, Anand Sarwate, and Kaushik Sinha. Ncar-optimal differentially private principal components. Advances in neural information processing systems, 25, 2012.
Chandra Chekuri, Kent Quanrud, and Manuel R Torres. Densest subgraph: Supermodularity, iterative peeling, and flow. In Proccedings of the 2022 Annual ACM-STAM Symposium on Discrete Algorithms (SODA), pp. 1531 1555. SIAM, 2022.
Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, et al. Spectral methods for data science: statistical perspective. Foundations and Trends& in Machine Learning, 14(5):566 806, 2021.
Kousik Das, Sovan Samanta, and Madhumangal Pal. Study on contrality measures in social networks: a survey. Social network analysis and mining, 8(1):13, 2018.
Chandler Davis and William Morton Kahan. The rotation of eigenvectors by perturbation. iii. SIAM Journal Numerical Analysis, 7(1):1-46, 1970.
18

---

Published in Transactions on Machine Learning Research (04/2026)
Xiaolong Deng, Yingtong Dou, Tiejun Lv, and Quoc Viet Hung Nguyen. A novel centrality cascading based edge parameter evaluation method for robust influence maximization. IEEF Access, 0922119222133 2017.
Paramita Dey, Agneet Chaterjee, and Sarbani Roy. Inftuence maximization in online social network using different centrality measures as seed node of information propagation. Sädhana, 44(9):205, 2019.
Laxman Dhulipala, Quanquan C Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. Differential privacy from locally adjustable graph algorithms: k-core decomposition, low out-degrce ordering, and densest subgraphs. In 2022 IEEE 63rd Annual Symposium on Foundations of Compuler Science (FOCS), pp.
IEEE, 2022.
Michael Dinitz, Satyen Kale, Silvio Lattanzi, and Sergei Vassilvitskii. Almost tight bounds for differentially private densest subgraph. In Proceedings of the 2025 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 2908-2950. SIAM, 2025.
Mohammadreza Doostnohammadian, Hamid Rabiee, and Usman A Khan. Centrality- epidemic control in complex social networks. Social Network Analysis and Mining, 10(1):32, 2020.
Cynthia Dwork and Jing Lei. Differential privacy and robust statistios. In Proceedings of the forly-forst annual ACM symposium on Theory of computing, pp. 371-380, 2009.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Tlya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advonces in Craptolog--BRROCRYP EUROCRYPP 2006: 24th Arnual International Conference on the Theory and Applications of Cryplographic Techniques, St. Pelersburg, Russia, May 28-June 1, 2006. Proceedings 25, pp. 486 5063. Springer, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265 284. Springer, 2006b.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, (13-4):211-407 2014a.
Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: optimal bounds for principal component analysis. In Proceedings of the forty-siath annual ACM symposium Theory of computing, pp. 11-20, 2014b.
Alessandro Epasto, Andres Munoz Medina, Chris Schwiegelshohn, David Saulpic, Sergei Vassilvitskii, Silvio Lattanzi, Vahab Mirrokni, and Vincent Pierre Cohen-addad. Scalable differentially private clustering via hierarchically separated trees. In Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining, 2022a.
Alessandro Epasto, Vahab Mirrokni, Bryan Perozzi, Anton Tsitsulin, and Peilin Zhong. Differentially private graph learning via sensitivity-bounded bounded personalized pagerank. Advonces in Neural Information Processing Systems, 25:22617-22627, 2022b.
Alireza Farhadi, MohammadTaaghi Hajiaghayi, and Elaine Shi. Differentially private densest subgraph. In International Conference on Artificial Intelligence and Statistics, pp. 11581-11597. PMLR, 2022.
U. Feige, D. Peleg, and G. Kortsarz. The dense k-subgraph problem. Algorithmico, 29(3):410 421, 2001.
A. Goldberg. Finding mazimum density subgraph. Tech. report, Univ. of California, Berkeley, 1984.
Alon Gonem and Ram Gilad-Bachrach Smooth sensitivity based approach for differrntially private pea. Tn Algorithmic Learning Theory, pp. 438-450. PMLR, 2018.
Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data relcase. In Theory of Cryptography: 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings 9, pp. 339 356. Springer, 2012.
19

---

Published in Transactions on Machine Learning Research (04/2026)
Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applications. Advances in neural informalion processing systems, 27, 2014.
Moritz Hardt and Aaron Roth. Beyond worst-case analysis in privale singular vector computation. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 331-33333 251-340, 2013.
Michael Hay, Chao Li, Gerome Miklau, and David Jensen. Accurate estimation of the degree distribution of private networks. In 2009 Ninth IEEE International Conference on Data Mining, pp. 169 178. IEEE, 2009.
Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-56) 561, 2006.
Mahdi Jalili, Ali Salehzadeh- Yazdi, Shailendra Gupta, Olaf Wolkenhauer, Marjan Yaghmaie, Osbaldo Aasendis-Antonie and Kamran Alimoghaddam. Evolution of centrality measurements for the detection of essential proteins biological networks. Frontiers in physiology, 7:375, 2016.
Honglu Jiang, Jian Pei, Dongxiao Yu, Jiguo Yu, Bei Gong, and Xiuzhen Cheng, Applications of differential privacy in social network analysis: A survey. IEEE transactions on knowledge and data engineering. 35(1): 108-127, 2021.
Chris Jones, Aaron Potechin, Goutham Rajendran, and Jell Xu. Sun-of-squares lower bounds for densest. k-subgraph. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 84-95, 2023.
Leskovec Jure. Snap datasets: Stanford large network dataset collection. Relrieved December 2021 from http://snap. stanford. edu/dato, 2014.
Michael Kapralov and Kunal Talwar. On differentially private low rank approximation. In Proceedings of the twenty-fourth amnual ACM-STAM symposium on Discrete algorithms, pp. 1395-1414. STAM, 2013.
Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev. Private analysis of graph structure. ACM Transactions Database Systems (TODS), 39(3):1-33, 2014.
Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodníkova, and Adam Smith. Analyzing graphs with node differential privacy. In Theory of Cryptography: 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Jopan, March 3-6, 2013. Proceedings, pp. 457-476. Springer, 2013.
Yasushi Kawase and Atsushi Miyauchi. The densest subgraph problem with a convex/concave size function. Algorithmico, 80:3461-3490 3480, 2018.
Subhash Khot. Ruling out ptas for graph min-bisection, donse k-subgraph, and bipartite clique. SIAM Journal on Compuling, 36(4):1025 1007,1, 2006.
Samir Khuller and Barna Saha. On finding dense subgraphs. In International Colloquium on Aulomala, Languages, and Programming, pp. 597-608 608. Springer, 2009.
Aritra Konar and Nicholas D. Sidiropoulos. Exploring the subgraph density-size trade-off via the Lovašz extension. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp. 743-751. ACM, 2021.
Jérôme Kunegis. Konect: the koblenz network collection. In Proceedings of the 22nd international conference on world wide web, pp. 1343-1350, 2013.
Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, and Francesco Bonchi. A survey on the densest. subgraph problem and its variants. ACM Computing Surveys, 56(8):1 40, 2024.
Long T Le, Tina Eliassi-Rad Rad, and Hanghang Tong. Met: A fast algorithm for minimizing propagation in large graphs with small cigen-gaps. In Proceedings of the 2015 SIAM International Conference Data Mining, pp. 694-700 702. SIAM, 2015.
George Z Li, Dung Nguyen, and Anil Vullikanti. Computing epidemic metrics with edge differential privacy. In International Conference on Artificial Intelligence and Statistics, pp. 4303 -4311, 1. PMI.R, 2024.
20

---

Published in Transactions on Machine Learning Research (04/2026)
Yang Li, Michael Purcell, Thierry Rakotoarivelo, David Smith, Thilina Ranbaduge, and Kee Siong Ng. Private graph data release: A survey. ACM Compuling Surveys, 55(11):1-385 2023.
Gabriele Lohmann, Daniel Margulies, Annette Horstmann, Burkhard Pleger, Joeran Lepsien, Dirk Goldhahn, Haíko Schloogl, Michael Stumvoll, Arno Villringer, and Robert Turner. Eigenvector contrality mapping for analyzing connectivity patterns in fmrr data of the human brain. PloS one, 5(4):c1023, 2010.
Qiheng Lu, Nicholas Sidiropoulos, and Aritra Konar. Densest k-subgraph mining via provably tight relaxation. In Proceedings of the AAAI Conference on Artificial Intelligence, 2025.
Warih Maharani, Alfian Akbar Gozali, et al. Degree centrality and eigenvector centrality in twitter. 2014 8th international conference on telecommanication systems services and applications (TSSA), pp. 1-5. IEEE, 2014.
Fragkiskos D Malliaros and Vasilcios Megalooikonomou. Expansion properties of large social graphs. In International Conference on Database Systems for Advanced Applications, pp. 311-322. Springer, 2011.
Pasin Manurangsi. Almost-polynomial ratio ath-hardness approximating densest k-subgraph. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 954 954-961, 2017.
Carl D Meyer. Matris analysis and applied linear algebra. SIAM, 2023.
Mohamed S Mohamed, Dung Nguyen, Anil Vullikanti, and Ravi Tandon. Differentially private community detection for stochastic block models. In International Conference on Machine Learning, pp. 15858 15894. PMLR, 2022.
Dung Nguyen and Anil Vullikanti. Differentially private densest subgraph detection. In International Conference on Machine Learnöng, pp. 8140-8155 PMLR, 2021.
Dung Nguyen and Anil Vullikanti. Differentially private exact recovery for stochastic block models. arXiv preprint 2rX6:24006 02644, 2024.
Kobbi Nissim, Sofya Raskhodníkova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thitty-ninth annual ACM symposium on Theory of computing, pp. 75 84, 2007.
Dimitris Papailiopoulos, Ioannis Mitliagkas, Alexandros Dimakis, and Constantine Caramanis. Finding dense subgraphs via low-rank bilinear optimization. International Conference on Machine Learning, pp- 1890 1898. PMLR, 2014.
Wei Peng, Feng Li, Xukai Zou, and Jie Wu. A two-stage deanonymization attack against anonymized social networks. IEEE Transactions on computers, 63(2):290-33) 2012.
Sudip Saha, Abhijin Adiga, Aditya Prakash, and Anil Kumar Vullikanti. Approximation algorithms for reducing the spectral radius control epidemic spread. In Proceedings of the 2015 SIAM International Conference on Data Mining, pp. 568-576. SIAM, 2015.
Stephen B Scidman. Network structure and minimum degree. Social networks, 5(3):269-28) 1983.
Kijung Shin, Tina Eliassi-Rad, and Christos Faloutsos. Corescope: Graph mining using k-core analy- sis pattteess anomalies and algorithms. In 2016 IEEE 16th international conference on data mining (ICDM), pp. 469 478. IEEE, 2016.
GW Stewart. Matrix perturbation theory. Computer Science and Scientifiic Compuding/Acaderee Press, Inc, 1990.
Charalampos Tsourakakis, Francesco Bonchi, Aristides Gionis, Franccsco Gullo, and Maria Tsiarli. Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantoes. In Proceedings of the 19th ACM SIGKDD international conference Knowledge discovery and dala mining, pp. 104-112, 2013.
21

---

Published in Transactions on Machine Learning Research (04/2026)
Piet Van Mieghem, Dragan Stevanovié, Fernando Kuipers, Cong Li, Ruud Van De Bovenkamp, Daijie Liu, and Huijuan Wang. Decreasing the spectral radius of graph by link removals. Physical Review E Statistionl, Nonlinear, and Soft Matter Physics, 84(1):016101, 2011.
Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American statistical association, 60(309):63 69, 1965.
Rongzhe Wei, Eli Chien, and Pan Li. Differentially private graph diffusion with applications in personalized pageranks. Xive preprind or orXi:22407.00077 2024.
Hanshen Xiao, Jun Wan, Elaine Shi, and Srinivas Devadas. One-sided bounded noise: Theory optimization algorithms and applications. In Proceedings of the 2025 ACM SIGSAC Conference on Compuler and Communications Security, pp. 4214 4228, 2025.
Hanyang Yuan, Jiarong Xu, Cong Wang, Ziqi Yang, Chunping Wang, Keting Yin, and Yang Yang. Unveiling privacy vulnerabilities: Investigating the role structure in graph data. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 4059-4070, 2024.
A Supporting Lemmata
A.1 The Davis- Kahan-sin Theorem
Consider the symmetric matrix M with eigen-decomposition M -"= Yu where |iil >
|>]] 2 ... 2 |사 denote the cigen-values of M' sorted in descending order and {u, he(m) are the corresponding eigen-vectors. Let M be x symmetric matrix obtained by perturbing M; i.e., we have
M = M + E
(26)
In an analogous manner, the cigen-decomposition of M is defined as M M- M AuauT. Let U= [u,,... ... u and U .. [ denote the principal-r eigen-spaces associated with M and M respectively. The distance between the principal eigen-spaces U and U can be defined as
(a,(U
min QEOeXP
JUQ-U"I
where Oux denotes the set of rolation matrices. The classic result of Davis- Davis & Kahan (970)) provides eigen-space perturbation bounds in terms of the strength of the perturbation E and the eigen-gap of M While there are many variations of this result (Stwwart (1990). we utilize one variant which will prove particularly useful in our context (Chen et al. 2021 Corollary 2.8).
Theorem 6. If the perturbation sotisfies |E||2 S (1 2222) (1;+1)), then the distance between the principal eigen-spaces U and U obeys
EU 122
dist U, U*)
(27)
M
In particular, when r= 1, we obtain the following bound on the distance between the principal components of M and M as a corollary.
Corollary 1. Under the conditions of Theorem 6. the distance between the principal components in and u is bounded by
2 Eu
dist(u,, uf) <
(28)
A
22

---

Published in Transactions on Machine Learning Research (04/2026)
B Proof of Theorem
Consider a pair of neighboring graphs 9.9' and let A' denote their adjacency matrices respectively. Under odge-DP, we can view A' as a perturbation of A; i.c., we have
A E.
(29)
where models the affect of deleting an edge G. Such an action can be formally expressed as e.ee te,e, (eeee) +eje(), (1,))
(i.. E
E
(30)
where e; denotes the tth canonical basis vector. When (i,j) & E, the perturbation E models an edge addition to 9, whereas for (i,j) E E E models edge deletion. Note that by construction, E is sparse matrix with pair of symmetric non-zero entries F.j = F.j: = +1, and satisfies |Bl| 1. We denote the set of all such possible perturbations E obtained by edge addition/removal remooll as P.
Let and v' denote the principal components of A and A' respectively. Since A and A' have non-negative entries, the Ferron-Frobenius theorem implies that v and v' are also element-wise non-negative. Hence, the distance between them can be expressed as
dist(v, v') = min aE(-1,+1)
||v av'll2 ||v v/1l2
(31)
We will invoke the Davis Kahan perturbation bound stated in Corollary 1 in order to upper bound the local lo sensitivity of v. This is valid provided the perturbation E defined in equation 30 satisfies
E - (1 1/v2) 1151)
|E|2
|
1/v2
(32)
V2
GAP(g) 2 1/v2
V2
11
Hence, for graphs whose eigen-gap exceeds v2/(V22 - 1)) we can estimate the local sensitivity via the following chain of inqqualities.
LG)
max ||v
v'Il2
9':8~6'
Ev
S max EEP
A1 - A22
2 o8
(33)
max iEV.EV,
GAP(g) f
$
2cr
GAP(G)
where in the final step, (r(1) and (2(() are the largest and sccond-largee elements of v, respectively. The first inequality follows from Corollary [ the second equality is a consequence of the structured sparsity exhibited
by E, and the final inequality follows since Vohc + ( of Wi
C Proof of Theorem 2
Let v' and v" denote the principal components of the adjacency matrices A' and A" associated with g' and neighboring dataset g", respectively; i,e, we have A" = A' E', where E' models the addition/removal of edge. Applying the Davis-Kahannsin è Theorem, we obtain
2 maxe E'v'll2 GAP(G")
LS(g") = max V g"
2 <
(34)
23

---

Published in Transactions on Machine Learning Research (04/2026)
We have implicitly made the assumption that GAP(G') > | 1-1/v2 T-1/V2 since |E'||a 1. Later, we will show that this assumption is satisfied under conditions (A1) and (A2).
To establish the desired result, we individually upper and lower bound the numerator and denominator terms of the above bound on LS(g"). First, consider the numerator term. Then, we have
max EPEP
EEv'l12
max
E |E'(v' - v2
E'EP
max E'EP
E'(v' - v)ll2 +
max E'EP
|E'v|l2
$ | v|12
max E'EP
max E'EE
|
(35)
< V v|12 + V V²(11 + v2
dist(v', .v / (1)))) + v2 (22
Viewing A' as perturbation of A, we can apply the sin θ theorem of Davis-Kahan to bound dist(v', v) in terms of v and GS) Let E A' A denote the perturbation that transforms A to A'. Note that we have E 2 & d'). Applying the sin θ theorem then yields
2 Evll2 GAP(G)
2 2d(g.9") GAP(C)
dist(v',
(36)
GAP(G)
provided E le < (1-1/ 1/v2). GAP(S), which is assumption (A1). Combining equation 35 and equation 36 we obtain
GAP(g). Since
| I d(G,g', this condition is satisfied if d(G, g')
<
2d(G, g') GAP
E'
Vi (222))
(37)
B'EP
provided the condition listed in assumption (a1) holds.
Next, consider the denominator term of equation 34 prove useful.
To obtain a lower bound, the following lemma will
Lemma 3. [Gonem & Gilad-Bachrach 2018 Lemma 11) Let G and G' be a pair of grophs with d(), k,
and suppose GAP(G) 0. Then
max (GAP(G))))B K,0 - GAP(G)) S GAP(g) + K.
(38)
If we wish to apply the non-trivial version of the lower bound GAP(S'), then require d(G,g') < GAP(GG. Note that under assumption (A1), this condition is already satisfied. Hence, we obtain
GAP(g") 2 GAP - (')
(39)
On combining equation 37 and equation 39
we obtain the upper bound
2 max E'v'l2
22(9. g") GAP(G)
+ +
22 2())
22
(40)
GAP(G")
GAP d()
It only remains to chain the above incquality with equation 34 However, the incqualities equation 34 and equation 40 were derived under different assumptions, and little care must be taken to ensure that they hold simultaneously. Note that equation 34 requires that GAP( > v2/(V2 - 1). If assumption (A1) is satisfied, we know that the lower bound equation 39 applics. Hence, if GAP(g) - d(g, g') V2/(V2 - 1), it implies that GAP(g') > v2/(V2 1). It remains to work out what the minimum value of GAP(G) required that (A1) and GAP(G) d(G,g') /2/ 1) are both valid. Under (A1), we have
GAP(G) dlG. g') > GAP(2)
(41)
If (AV(2) > V2/(V2-11 1), implies the desired condition GAP(G)-d(g.9')) > V2/(V2 - 1). The former condition is satisfied by GAP(g) 2/(V2 1), which is assumption (A2).
24

---

Published in Transactions on Machine Learning Research (04/2026)
To conclude, under assumptions (A1) and (A2), free to chain together the incqualities equation 34 and equation 40 Doing so yields the claimed bound
LS(g') S GAP(g) d(G,9))
2
2d(G) GAP(g)
+ VoZ(1) + 222))
This concludes the proof.
D The difficulty with smooth sensitivity
Smooth sensitivity Nissim et al. (007) is framework for obtaining DP guarantees while relying local sensitivity based quantities to calibrate the level of injected noise, as opposed to using the global sensitivity. To be specific, the smooth sensilinily, for a graph dataset 9 is defined as
{
S9 = max (xx)))))xxp(Ba(0000) 8'
(42)
Here, f:g - R" denotes the target function to be privatized, 8 > 0 is parameter, and d(),g") denotes the Hamming distance between 9 and g'. By adding i.i.d. Gaussian noise to that is calibrated to S/ (9), it can be shown that the resulting output satisfies DP (with 3 reflecting the desired privacy parameters (e, The smooth sensitivity value S (g) can be viewed as the tightest upper bound on the local sensitivity that provides DP. However, the catch that solving the optimization problem equation 12 is non-trivial in general, which renders iractical application of the smooth sensitivity framework challenging. The prior work of Gonemi & Gilad-Bachrade (2018) employed the smooth sensitivity framework for computing principal components of general datasets; albeit not for graphs under edge-DP. Using the local scnsitivity estimate in (Gonem & Gilad-Bach 2018 Theorem 5), the authors developed tractable smooth upper bounds (9),,, which can then be used to provide DP. However, successfully adapting this approach to present context presents several difficulties. In D we provide a rigorous analysis which shows that under mild conditions, the obtained smooth upper bound is very close to the global sensitivity estimate of /2.
In this section, we illustrate the difficulties associated with adopting the smooth sensitivity framework of Nissim et al. (2007) for computing principal components of under edge
Gonem & Gilad-Bachrach 2018): DP.
Following Nissim et al. (2007 for graph G, the 3-smooth sensitivity of the principal component with
smoothness parameter 8 > 0 can be defined as
SC(
max tE(0.1,- (2))
e -Bt 10) (g) (0)
(43)
where
(9) =
max ("g
(g'
(44)
is the local éz-sensitivity of v Hamming distance t from
Since computing (G) exactly can prove to be challenging, adopt the approach of Gonem & Gilad
Bachrach (2018) to obtain smooth upper bounds on its value. To this end, the following result of (Nissim
et al. 2007 Claim 3.2) is useful.
Lemma 4. For an admissible to E (0.1.-...
b let
(C( == max
max fe fe- -8 (0)( GS, e -8t) [Ef0, 1o
(45)
where GS, denotes the global Ez-sensitivity of v. Then, (Q( is a B-smooth upper bound.
In order to compute the above smooth upper bound, we will utilize the local ee-sensitivity estimate of v derived in Theorem 1. which is valid for all graphs with spectral gap of at least == v2/(V2 1). The
25

---

Published in Transactions on Machine Learning Research (04/2026)
main idea is now to modify the proof technique of Gonem & can be incorporated. To this end, define the following "gap-restricted" analogue of equation 44
(2018) that this condition
max g'= Lg)
(46)
GAP(D")>>
Note that in general, we have (g) < 7 (g). However, from the lower bound in Lemma 2, we know that for t < GAP v, have GAP(g') > We conclude that
(g) = (9), <GP(S))
(47)
Next, invoke
Theorem which asserts that
2
21 GAP(() + VoR(0 + (012)
LS(g') S
(48)
GAP(g)
subject the conditions < (1 (1-1/v2) GAP(S) GAP(G)/V and GAP(g) V2-1 = V2v. Furthermore,
a little calculation reveals that the assumption
GAP(g) < GAP(G) -V,
GAP(G) > V2v=
(49)
which will prove useful. In particular, from equation 47 and equation 49 spectral gap at least V2v
obtain that for graphs with
N (() GAP(G)
(50)
We are now free to use equation 48
to upper bound 7v (g). Doing so yields
2
2t
(G) <
22 (()) + V
GAP
G))
2
2
u² T11)
+ +==((2)
(51)
GAP
2/2
2
2 GAP(9)
GAP(G)
+ V
(())
2
x2))
v
We are now ready to apply Lemma
Let t0 = GAP
Then, we have
2v 2 + V 2 +
1 Vt<to
e 0t (9) < (G) -
22 22
to
(52)
GAP
This yields the following smooth sensitivity bound for the principal component of graphs with eigen-gap larger than 2v.
(C( = max GAP(C)
2v 2 +
v 2 + 2
/2e- g
GAP(C)
(53)
Let. us examine the obtained smooth upper bound. In order to apply this bound to obtain approximate (e, 5)-DP via the Gaussian mechanism, Nissim et al. 2007 Lemma 2.7) asserts that
8 4(n + ln(2/
(54)
This reveals the primary drawback namely the dependence of 3 on the dimension n. Since 3 O(e/n) (discounting 5 for the moment), for even moderately sized graphs vertices, the value of 3 can be very
26

---

Published in Transactions on Machine Learning Research (04/2026)
small (i.e., < 1) for reasonable choices of privacy parameters (c, 8). We conclude that the smooth upper bound
(-0 (GAP(G)
() /2exp
n
(55)
<GAP(G)
22 1
where the approximation the last step holds when n > <GAP(G). For the datasets considered this paper, observed that computing the smooth upper bound with the same privacy budget allotted PTR yields values close to v2, which is the global sensitivity value.
E Proof of Lemma i
The function 0(g') is monotonically increasing in d(g, g') for all feasible datasets g' for which ((g') 2 0. Hence, the minimum is attained by selecting = G', from which it follows that vbG) 0.
F Sampling noise from the TBL distribution
Let F be the CDF the untruncated Laplace(μ, A):
1 (c-u)//
x 14
2
F(x)
(w--)//
x x> μ.
Truncating to [0, R) means conditioning that interval. The truncated CDF G' is
F(x) F(0) F(R) F(0) (x [).
G(x) Pr(X < 0 x
Hence the inverse truncated CDF is
G (u) = ( F(O)) (u (),
Sampling algorithm:
1. Draw u 1n), 1), set u' F(0) + (F(R) - F(O)).
2. Invert the untruncated Laplace CDF at n':
Mr. Ar. In (2u'), =
w' S 1
1r. In(( u')), w'
Note the branch test must be against u' (the untrancated CDF value), not u, unless the truncation is symmetric (R = 2p), in which special case the branch also happens al 1/2.
Closed forms for F(0) and F(R). For 0 and R 2 μ.
F(0)
J/e-n/A n/A
F(R) 1 1ee -R--n/))/
so the truncated interval mass is Z,,AAR = F(R) F(0) = 1 2 e (RR-1)A 1 2
n/d and R = 2/ we get
Zu,AA u/A
27

---

Published in Transactions on Machine Learning Research (04/2026)
G Proof of Lemma 2
Contrary to the standard PTR and modified PTR Li et al. (2024), here GS is not necessarily equal to 1. To compute the global sensitivity of (G), it is essential to account for the slep preceding this part of the algorithm. In the previous stage, we obtained the private function f(G), whose value directly influences the computation of (G)). Since f(G) is produced in an earlier step; we can treat it a constant when analyzing the global sensitivity of d(G). In other words, the value of f(G) is regarded as prior knowledge in the sensitivity analysis of (GG).
Let G ~ g" be a pair of neighboring instances. Then, for a fixed draw of 2 = 2, we consider the following two cases.
The value equals either 0 or 1. In the case of the former, from Lemma 1, we obtain (()) - 009") 0, and the sensitivity is O. Otherwise, the sensitivity is 1 by a standard argument.
Case 1: =
O but u(f(g")) 1. Then, we have (()) 0 and o(g") 2 0. Hence, the sonsitivity of á is ((g"). In order to determine how large this quantity can be, we use the following facts: (1) f(g) s 0 and f(g") > 0, and (2) [GAP(g) - GAP(g")I I 1. From the first fact, we obtain GAP(G) I (+2, 2, whereas the second fact toget her with GAP(G") > L 1+ z yield the boundary condition GAP(G) > + 2- 1. Hence, this condition arises when the gap of G lies in the interval (t - 1, 2], which is oquivalent to F(G) E (-1.0). Since GAP(g") >t+> 2 > t, g" lies in the large gap regime and thus from [Theorem 2 (A2)], it holds that.
Case 2: u(f(G)) # u(f()")). Suppose that u(f(G)
- (1-7 GAP(G") (1- 21 (GAP(G))1) 1
(1- 1
1
1 -22 (1-
(++2(+++)))
(1-
1 v2
((g")
(t+ 2p
(56)
where in the final incquality, we have used the fact that 2 E 2p]
Now consider the opposite case when u(f(g)) = but u(f(g")) = 0. Then, ((9) 2 0 and o(g") = 0. Hence, the sensitivity is determined by how large ((g) can be. To upper-bound this quantity, we proceed as before. Since f(g)= > O, we obtain GAP(G) > + z. Mcanwhile, from f(g") I and the fact that the gap has sensitivity 1, we obtain the boundary condition GAP(G) < ++ Hence, this scenario arises when the gap of G lies in the interval (t + z,t + + 1], which is equivalent to f(G) (0, 1]. Since G lies in the large gap
regime, from [Thcormm 2 (A2)), we obtain
(()) < (1 (1-
1 22
1 -122/ - (t + 2p + 1) GAP(G) - (1-)2)= (t+2+1) (1=+))(t+2++))) 1 (1-
(57)
v2)
All in all, to determine the sensitivity of ((G), we first check whether -1 f(G) < 1. If this condition holds, then G = (1 )1+ 2μ + 1). Otherwise, GS I.
H Proof of Theorem 3
The key step is to establish that the computation of 6(g) is private for all for graphs. Note that (()) can be viewed as the output of an adaptive composition mechanism. The first mechanism is the TBLM for privatizing (()), whose output f(9) (co. DD, as established by Fact 1. Furthermore, f(9) then applied as an input to problem 13 whose solution ((g) is then privatized via the standard Laplace mechanism. In order to invoke adaptive composition, we need to show that conditioned on the input f(G), 8(9) is DP. To this end, note that if one replaces the private output of TBLM f(9) with its non-private counterpart f(g) in Lemma 2, then the scale parameters S2 in equation 14 correspond to the local sensitivity of ((-). Clearly, adding Laplacian noise scaled to these parameters is not guaranteed to preserve ePge-D.. However, if we select the scale parameter GS on the basis of f(G), as in equation
13 then we have that
GS S 1(1</(()))) + S2 - ((11))-
(58)
By the post- prsc-processig property of DP, it follows that GS also ōc), edge-DP. Hence, using GS in the Laplace mechanism to privatize ((-) is guaranteed to be (co, O)- Direct application of adaptive composition
28

---

Published in Transactions on Machine Learning Research (04/2026)
then guarantees that the total privacy budget needed to privatize <(-) is (co + (1,00) We are ready to state the privacy of the overall algorithm.
Depending on the value of f(G), the following outcomes are possible.
Case 1: f(G) < 0: The proposed bound in problem 13 is O, and o( = 0. From Lemma 2, ((9) Lap(GSa//1). By properlies of the Laplace distribution, the probability that ((G) S (GS, In(1/8)) in the test stage of PTR is at least 1 - 8, and the algorithm refuses to yield a response for such a dataset. Otherwise, with probability at most 6, the algorithm is not private. We conclude that the output the test stage of the algorithm is (0,8)-DP. From basic composition, the overall privacy offered by the algorithm totals (Eo 6,, 60 + 5).
Case 2: f(G) > 0: The proposed bound in problem 13 is 3. The remainder of the analysis broken down into two further two sub-cases which depend on B. First, let B (g). Then 7()) = 0, which implics that k(G) = 0, since (()) ((G) 2 By the same argument as the previous case, the probability that ((g) < (GSg ln(1/5))/e, and the algorithm stops at least 1 Hence the overall privacy privacy totals (co + (1, 60 + 5). In the other sub-case, 3 2 LS) and the overall output is (eo + E1 + -2, do + +6) DP, being the composition of and (E2, 0)-DP Gaussian mechanism.
Proof of Theorem 4
Selecting the parameter / is key component of implementing PTR. First, specify interval of values of B which will be considered. We start from verifying the following condition; namely, whether for given value of B, the solution of problem equation 16 satisfies (() < <1 1/12) GAP(G), as this assumption is required in 2 to establish that O(g') a valid upper bound on LS(g"). As we show next, cnsuring that this condition is met translates into a maximum allowable value of B.
Since (()) is monotonically increasing with ((G,9') the largest value of 3 which can be satisfied occurs when d(g, G¹) - (1 -1-1111100 1/V2) GAP(G) 1. From equation 16. this corresponds to the following upper bound on B.
Bu = GAP
2
V2 v / + vz (2))
(59)
By the same principle, the largest value of B for which d'G,g') 0 in problem equation 16 occurs for
Bi 2 122 (2 + 12(2:
(60)
GAP(g)
which corresponds to the upper bound on the local & sensitivity of v on G. Hence, for any choice of B E (.), the statistic o(-) can be computed according to equation 17
J Proof of Theorem
We will utilize the following fact regarding the Laplace distribution. Fact Let Lap(0, b). Then, Prob(|Z] 2 (b) exp(-t).
(61
In particular, if b GSg/ and c. log(1/8) (where >>0), then
Prob / 2 c log(1/5)/c) = 5.
In the PTR algorithm, after computing Φ(-) in step 2, we add noise Z ~ Lap(0, GS,ec) to obtain the noisy statistic و(g) = (()) Z. Thereafter, we test whether I exceeds the threshold GS, log(1/6)/e to yield a response. Since Φ(G) 2 r(G), the probability of successful response is at least
Prob( 2 (og()//e))) = Prob(Z 2 2 GS log (1/0)/1 - x(G))
(62)
2 Prob(Z Z 2 GS log(1 (100// (())).
29

---

Published in Transactions on Machine Learning Research (04/2026)
Suppose we adjust B that
((9) (p GS log(L/0)/e (0,1).
(63)
Then, the success probability of obtaining a response is at least
Prob()(g) 2 GS logg(10)//))) 2 Prob Z 2 GSS log( (
Prob(2 2 2 p plog(1/8)/ei)
Prob Z & - plog(1/0))
(64)
exp( (xp(-plog(1/0))
2
8P
2
where in the second-last step we have invoked Fact 1 and utilized the fact that the distribution of Z is symmetric about the origin.
K
Expander graphs
From equation equation 19 it can be seen that for fixed privacy budget and other algorithm parameters, the proposed bound 3 behaves like
2 B ( ((1) + (2))
GAP(G)
where (x(1), (x(2) are the two largest entries of the eigen-vector vector V. This is in line with the local sensitivity bound derived in Theorem 1. Hence, 3 being small depends on (1) the gap being large, and (2) the "energy spread" in the entries v being small.
We now show that there exists a family of graphs for which both conditions are fulfilled specifically, the class of expander graphs Hoory et al. (2006). Following the terminology of Hoory et al. (2006). we designate graph as being (n, d, expanderr if it fulfills the following conditions.
Cl: G has n vertices.
C2: Every vertex has degree d, i.c., G is d-regular.
C3: The second largest eigen-value of the adjacency matrix (in magnitude) is Aa2 S ad, where E (0,1), and 1 - a represents the expansion coefficient. Hence, smaller values of a correspond to higher expansion.
For such family of graphs, the following facts are known.
F1: The principal eigen-vector == vn 1n-
F2: The largest cigen-vales of the adjacency matrix of G is a d.
F3: For fixed d, as > oo holds that P22 2 2 - (1)
From these facts, obtain that (a): x2 ( terms of energy. In addition, (b): the spectral gap GAP = X |>2l satisfics
22 (7(2) 1/n, i.e., the entries of v are uniformly spread out in
d(1 (1-a) a) s GAP(G) < 2 1 (1)
+o can be sandwiched GAP(g)
Hence, the main figure of merit
(1 + +
/2
V2 /nd(1 a)
(65)
Vn|2vd + 0% (1)
GAP
30

---

Published in Transactions on Machine Learning Research (04/2026)
Suppose that d(1 a) exceeds the threshold t quick calculation reveals that d d2 12 is sufficient for every admissible E (0, 1). As consequence, GAP 2 t. Then, for large n and a fixed d, B ((1/v)) and the algorithm will release outputs with small level of noise. Although real-world graphs do not conform precisely to such model, empirical studics reveal that they can possess good expansion properties Malliaros & Megalooikononouu (2011), 1, which makes them a good candidate for our PTR algorithm.
L Proof of Proposition 1
Recall the value of B employed in equation 19
2(p + GS loogo///////////// + GAP(g),
/22 (0)) + o 27(2)
2 GAP
B
(66)
GAP(G) - (p + GS&) log(1/6)/E1
In order to reduce the burden of notation, we refer to the following terms in short-hane
a GAP(g)
b = V (2 + =(2) := (1+ GSp log(1/0)/e)
(67)
Then, B, 3, Bu can be compactly expressed
2
2pm + ab
8
pm
2b
31
(68)
2
8, (2
v2+b).
respectively.
In order to verify for what choices of problem parameters a, b, 17, p the value B lies the interval (3r, Bw), we consider two cases.
Case 1: >> Br. This condition is equivalent to
2pm + ab
pn > 2h
(69)
2pm + ab b(a - p7)
(2 + b)pn > 0,
which is always satisfied provided
2d > ++<>>1 a
(70)
P
Note that this corresponds to the necessary condition
(p + GS&)) log(1/6/er < GAP(g)
(71)
for 3 being positive.
31

---

Published in Transactions on Machine Learning Research (04/2026)
Case 2: B < Bu. This condition is equivalent to
2
2pm + ab)
2v2
(2 v2 +2+
a - pT
a
2pm + ab
V2 v2+
pd
+ppm ab
(2(v2 + /2b pn)
(2 + 2 -) 1)) v2b) < (2(V2 1) + (v2 1)b)a
(72)
69< [2(v2 (V2
+ 26)
(v2 1)(2 + b)a
PV 2(2 + b)
1 a
SM
/2 p
which is the condition
log(1/6)
1 GAP(G)
(1-12)
1
GAP(S),
(73)
E1
V2
(p
GS
V2
which exactly corresponds to the assumption (A2) in Thcorem 2 This completes the proof.
M Upper bound of Non-private solution
In terms of the quality of the approximate solution, the following result is known.
Proposition 2 (Adapted from Papailiopoulos et al. 2014)). For any unweighted graph 9, the optimal size-k edge densily is no more than
dr s min
1 k(k - 1)
& A& M2l 11
(74)
N Additional Experimental Results
In this section, additional results for each of the proposed algorithms are provided individually. The performance of algorithh for D&S and top-k eigenscore subset extraction is evaluated in Figure and Figure 7 on real-world datasets for different privacy budgets. Similarly, the performance of algorithm 2 is
depicted in Figure 6 and P Figure 8
32

---

Published in Transactions on Machine Learning Research (04/2026)
Facebook
PTB (Pmm-))
FTR (so.- (loc-alogCatalog)
100
0.
Size
Size
SIN
(Tuibch)
1.0
50g
Edge
0.1
0.1
101
Size
Figure 5: Edge density versus subgraph size (k) for Algorithm 1 under (cu, = (1,7x x 1) and varying
el 62 = =e/2 values across real-world datasets. The privacy parameter is set. to 6 = llg(m)) /m, where
denotes the number of edges in each network.
PPM (Pacebook)
PPM (PPI-Human)
FPM (soc BlogCaaloo
1o
02
03
DP Size
Size
Stac
PPM (Flickr)
(Twitch)
PPM (Orkut)
0.5
0.
Egye
Size
Size
Figure 6: Edge density versus subgraph size (k) for Algorithm 2 across real-world datasets under varying e values with o = log(m) m.
33

---

Published in Transactions on Machine Learning Research (04/2026)
Human
Bloa
Tap-
Toge
Tope
(FTR)
Twitcsh (P7))
09
100
120
144
150
180
20
100
120
142
300
Figure 7: Jaacard similarity versus subset size (k) for Algorithm 1 under (Cu, 5g) (1, 10-?) and varying 62 values across real-world datasets. The privacy parameter set to 5 log(m)/m, where m denotes the number of edges in each network.
Facobook
Human- PM
BlogCataiog
Neccurc Skenlcity
Abccard Sterbattyy
Subgraph 9:20
Subgraph
Meccar: Omdarty
Subgr $220
Subproph 5220
Figure 8: Jaccard similarity subset size (k) for Algorithm under varying values with 8 = log(m)/m
across real-world datasets.
34


Reviews:
[{"review_id": "j96wZwEnyW", "reviewer": "Reviewer_zSQ1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of DP computation of the principal eigenvector of a graph adjacency matrix under edge privacy. It first analyzes why existing instance-specific mechanisms based on smooth sensitivity fail to significantly improve utility. It shows in this setting, smooth sensitivity bounds remain close to the global sensitivity despite large spectral gaps in graphs. Motivated by this limitation, the paper develops a practical and scalable implementation of the Propose-Test-Release framework tailored to principal component estimation. By deriving tractable sensitivity surrogates and closed-form parameter selection rules, the proposed method achieves one-shot noise addition with computational complexity comparable to non-private eigenvector computation. The resulting algorithm is applied to private eigenvector centrality extraction and private approximation of the densest k-subgraph problem.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper clearly states their contributions and relevance to the exitisng works.", "audience_yn": "Yes", "audience_explanation": "Privacy and graph related topics are popular among machine learning and signal processing communities.", "requested_changes": "1. My main technical concern is the reliance on the spectral gap assumption. The proposed method depends critically on the presence of a sufficiently large eigen-gap, and its behavior outside this regime is not well characterized. The paper should more clearly identify classes of graphs for which this assumption is likely to fail and discuss the expected performance in such settings. If a quantitative characterization is not feasible, a qualitative discussion would still be valuable.\n\n2. Additionally, I am also concerned about the frequency with which the PTR mechanism returns \"no response\" across different datasets and privacy budgets, and how such outcomes impact downstream applications. Reporting empirical rejection rates or providing guidance on handling these cases would strengthen the practical relevance of the method.", "broader_impact_concerns": "NA", "additional_comments": "Aside from the weaknesses stated in the Requested Changes section, this paper has several strengths. The paper is well written and easy to follow, with a clear logical structure. Although the contributions are incremental and confined to a specific setting, the connections to and motivations from existing work are well constructed and clearly articulated. In addition, the theoretical quantifications provided throughout the paper are helpful for understanding the paper. In particular, the paper offers a convincing analysis explaining why global sensitivity based output perturbation and smooth sensitivity fail to provide meaningful utility improvements for graph principal component estimation.", "extra_scores": {}, "extra_text": {}}, {"review_id": "voc9pDZnRn", "reviewer": "Reviewer_GbSi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies how to privately compute the top eigenvector (principal component) of a graph’s adjacency matrix under edge-DP and applied to tasks like eigenvector centrality and approximating densest-k-subgraph. The paper proposed an instance-specific Propose–Test–Release method that (i) privately tests whether the graph is “well-behaved” (using a truncated biased Laplace mechanism to avoid false positives), (ii) privately tests whether it’s safe to release, and then (iii) releases a one-shot noisy principal component with noise scaled to an upper bound on the local sensitivity. Experimental results, comparing to the iterative private power method baseline, shows that PTR can maintain comparable utility but achieve large speedups.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The claims are well supported by the theoretical analysis and the experiments show the improved performance over existing baselines. I went through the proofs briefly and did not find mistakes.", "audience_yn": "Yes", "audience_explanation": "The paper leverages local sensitivity to reduce the noise scale and introduces a surrogate lower bound in the PTR test. This lower bound depends on the gap regime, and the required gap regime is also DP-guaranteed.\n\nThe method reduces PTR overhead to essentially computing a principal component plus a small number of private tests, enabling scalability to graphs with millions of nodes and large runtime improvements over iterative DP baselines.\n\nIt provides (to the best of my knowledge) the first edge-DP algorithm for DkS, which can potentially support a broader range of downstream tasks.\n\nThe resulting closed-form solution is elegant and easy to implement.\n\nOverall, this is a solid paper with interesting results.", "requested_changes": "The empirical results appear not stable and general across datasets (e.g., Figure 3 for Facebook and Figure 2).\n\nThe writing could be more polished and consistent; for example, citation commands are sometimes used incorrectly (e.g., `\\citet`, `\\citealt`, `\\cite`).\n\nPlease also check notation consistency, especially the use of \\Phi(\\cdot) and \\Phi(\\dot).\n\nHow does replacing the \"true bad set\" condition $L S_v\\left(G^{\\prime}\\right) \\geq \\beta$ with the relaxed surrogate $\\theta\\left(G^{\\prime}\\right) \\geq \\beta$ guarantee that $\\phi(G)$ is a valid lower bound on the true PTR distance $\\gamma(G)$, and what intuition explains why this makes the PTR test conservative (i.e., less likely to mistakenly release)?\n\nWhy does using $\\tilde{f}(G)=f(G)-\\tilde{Z}$ with $\\tilde{Z} \\geq 0$ (TBL) eliminate false positives in the gap test compared to symmetric Laplace noise, and what is the tradeoff (in terms of false negatives / increased rejection probability) introduced by this one-sided, truncated noise?", "broader_impact_concerns": "This is mainly a theory paper.  No obvious concerns on the ethical implications", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SCN09FlixZ", "reviewer": "Reviewer_xXLJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies edge-differentially private estimation of the principal eigenvector of a graph adjacency matrix and its use for two tasks: (A1) selecting top-k eigenvector-central nodes and (A2) approximating the densest-k-subgraph (DkS). The main technical contributions are:\n\nA scalable Propose-Test-Release (PTR) variant for private PC: they construct a tractable sensitivity-1 surrogate ϕ(G), handle “large-gap” and “small-gap” regimes, and use the truncated biased Laplace mechanism to privately test whether the instance is well-behaved. The overall complexity is essentially that of computing a non-private PC.\n\nAn empirical comparison with the private power method (PPM) on several real graphs up to 3M nodes, showing that PTR achieves comparable utility to PPM, while being 2–3.5 orders of magnitude faster (Table 3, Figs. 2–3).", "claims_and_evidence_yn": "Yes", "claims_explanation": "For the theoretical claims, the paper gives precise statements and sketches of the main arguments in the body, with detailed proofs deferred to the appendices.\n\nWhile I did not check all proofs in full detail, the chain “local sensitivity → PTR surrogate → privacy guarantee → success probability” is logically consistent and uses standard DP tools, so the DP and sensitivity claims are reasonably convincing.\n\n**Some concerns on empirical results.** The paper uses different $\\delta$ for PTR and PPM, such as $\\frac{1}{m}$ for PTR while $10^{-12}$ for PPM, this will make the utility favor PTR. Moreover, usually it requires $\\delta$ at least $\\frac{1}{m}\\log m$ for $(\\epsilon, \\delta)$ DP.", "audience_yn": "Yes", "audience_explanation": "This paper sits at the intersection of several active areas:\n\nDifferential privacy for structured data: Edge-DP on graphs, especially at scale, is a central topic for privacy-preserving social network.\n\nSpectral methods and graph mining: Eigenvector centrality and densest-subgraph-type problems are widely used in influence maximization, fraud detection, etc.\n\nReaders interested in DP, graph algorithms will find the theoretical construction (PTR with a tractable surrogate) and the empirical evidence on million-node graphs relevant.", "requested_changes": "Regarding the empirical results, please compare the algorithm under the same privacy budget, i.e., using the same and valid $\\delta$s.\n\nMy main request is to explain the approach more accessibly and systematically in the main text, so that readers who are not already experts in PTR and sensitivity-based DP can follow the design choices. \n\nHigh-level pipeline overview. Add a short “algorithm overview” subsection early. A small flow diagram or pseudo-code emphasizing data flow (what depends on the graph, where noise is added, what’s public) would help.\n\n**Requested clarification on Eq. (7), Eq. (8), and Lemma 1**\n\nOne technical part that I found hard to follow is the derivation and role of Eq. (7). In the large-gap regime, you replace the constraint $LS_v(G') \\ge \\beta$ in (4) with $\\theta(G') \\ge \\beta$ in (7). Some intuitive discussion is required on what $\\theta(G')$ represents in both regimes (large-gap vs. small-gap) and how these choices of surrogate $\\phi$ are used by PTR, which would make this part of the paper considerably easier to follow.", "broader_impact_concerns": "I do not see major negative broader-impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)