On the trade-off between expressivity and privacy in graph representation learning
Authors: Patrick Indri
Tamara Drucks
Thomas Gärtner
Venue: ICLR 2026 Poster (2026)
Keywords: graph representation learning
privacy
expressivity
Primary area: learning on graphs and other geometries & topologies
TL;DR: We study the trade-off between provably expressive and private representations in graph learning

Abstract: We investigate the trade-off between expressive power and privacy guarantees in graph representation learning. Privacy-preserving machine learning faces growing regulatory demands that pose a fundamental challenge: safeguarding sensitive data while maintaining expressive power. To address this challenge, we leverage homomorphism density vectors to obtain graph embeddings that are private and expressive.
Homomorphism densities are provably highly discriminative and offer a powerful tool for distinguishing non-isomorphic graphs. By adding noise calibrated to each density’s sensitivity, we ensure that the resulting embeddings satisfy formal differential privacy guarantees. Our theoretical construction preserves expressivity in expectation, as each private embedding remains unbiased with respect to the true homomorphism densities. We demonstrate the usefulness of our embeddings through experiments on molecular and social network datasets.

Published as a conference paper at ICLR 2026
ON THE TRADE-OFF BETWEEN EXPRESSIVITY AND PRIVACY IN GRAPH REPRESENTATION LEARNING
Patrick Indri', Tamara Drucks' & Thomas Gärtner
Research Unit Machine Learning
TU Wien
Vienna, Austria
{patrick. indri, tamara. drucks, thomas gewtteerrrertrtteeeeccc
ABSTRACT
We investigate the trade-off between expressive power and privacy guarantees graph representation learning. sewacc-preserving machine learning faces grow- ing regulatory demands that pose a fundamental challenge: safeguarding sensitive data while maintaining expressive power. To address this challenge, leverage homomorphism density vectors to obtain graph embeddings that are private and expressive. Homomorphism densities are provably highly discriminative and of- fer powerful tool for distinguishing non-isomorphic graphs. By adding noise calibrated to each density's 's sensitivity, we ensure that the resulting embeddings satisfy formal differential privacy guarantees. Our theoretical construction pre- serves expressivity in expectation, as each private embedding remains unbiased with respect to the true homomorphism densities. We demonstrate the usefulness our embeddings through experiments on molecular and social network datasets.
INTRODUCTION
We study the interplay between expressivity and privacy for learning graph representations and show how to obtain expressive and private representations. Our investigation addresses the need for privacy-preserving machine learning and our formal guarantees align with the increasing regulatory pressure this direction (European Parliament and Council of the European Union, 2016; 2024; National Institute of Standards and Technology, 2023). In graph representation learning, expressiv- ity analysis studies the ability of algorithms to distinguish pairs of non-isomorphic graphs. Private algorithms, the other hand, generally ensure that similar graphs yield similar outputs. Consider for instance graphs G1 and G2 in Figure that differ by exactly one edge. As the two graphs are non- isomorphic, an expressive algorithm produces distinct embeddings ((G1) # ppG2) it captures their structural differences. An edge-private algorithm. instead, protects the presence or absence
G1
G2
G3
((G1) p((2)
op (Gs)
Figure 1: G1 and G2 are two non-isomorphic graphs that differ in exactly one edge. An expres- sive graph algorithm should distinguish between these graphs and provide different embeddings (p(G) + (G2); a differentially private algorithm instead ensures that sp(G) R ((G2).
"Equal contribution, order randomized. First authors free swap the order for professional purposes.

---

Published as a conference paper at ICLR 2026
of individual edges and thus produces similar embeddings (((1)) ((G2). Therefore, requiring algorithms to be both expressive and private is challenging. So far, there has been little investigation towards better theoretical understanding of this tension and characterization of the trade-offs between privacy, expressivity, and utility, i.e., predictive performance. We fill this research gap and investigate which degree embeddings with provable expressivity and privacy guarantees can be obtained. We focus on graph-level learning tasks while providing edge-level privacy guarantees. This setting allows us study the effect of the minimal possible structural modifications, i.e. edge changes, on embeddings which are obtained from the graph structure only to isolate the effect of the graph structure itself on expressivity and privacy. Specifically, we consider the notions of expressiv- ity in expeciation and of disferential privacy. We propose graph embeddings with carefully scaled random noise, such that their distributions sufficiently overlap for graphs that differ by one edge (see G1 and G2), while remaining distinguishable for graphs with larger edge edit distance (e.g.. C11 and Gg). We build upon existing work that relies on homomorphism counts, either as standalone graph representations to increase the expressive power of graph neural networks (GNNs) (Nguyen & Maehara, 2020; Welke et al., 2023; Jin et al., 2024; Maehara & NT, 2024). Homomorphism counts a powerful theoretical tool to investigate expressivity, as they can be used to distinguish any pair of non-isomorphic graphs (Lovász, 1967; 2012). We introduce noisy homomorphism densities, i.e., normalized homomorphism counts with additive noise, to obtain representations which are expres- sive in expectation and differentially private. Our method allows for the private release of the graph embeddings, which can be then used for any further downstream analysis.
Main contributions.
(i) We propose homomorphism densities as theoretical tool to investigate the trade-off be- tween expressivity and privacy in graph representation learning.
(ii) We show that the choice of the pattern class used to compute the homomorphism densities determines the required level of noise needed for privacy guarantees: pattern classes that provide more expressive power require more noise, which can decrease their utility.
(iii) We provide a general framework to obtain graph embeddings that satisfy specified pri- vacy guarantee and level of expressivity in expectation, and can be used for downstream tasks such as graph classification or regression. Our embeddings match, in expectation, the expressive power of various GNN architectures such as message-passing GNNs and subgraph GNNs, while also satisfying differential privacy.
(iv) We empirically demonstrate the synthetic as well as real-world benchmark datasets. We show that our private embeddings retain good performance with increased resilience to privacy attacks.
trade-off and perform experiments on
2 RELATED WORK
Recent work graph representation learning has studied the exprexsive power of learning algo- rithms, i.e., their ability to learn different representations for non-isomorphic graphs. A large body of work analyzed the expressive power of GNNs through the lens of k- &-eisscciler-Leman (k-WL) tests, a hierarchy of increasingly expressive color refinement algorithms (Xu et al., 2019; Morris et al., 2019). An alternative approach is to rely on graph representations built using homomorphism counts (Böker, 2021; Lovász, 2012; Jin et al., 2024; Maehara & NT, 2024; Beaujean et al., 2021; Wolf et al., 2023) to obtain arbitrarily expressive representations, at least in expectation (Nguyen & Maehara, 2020; Welke al., 2023). Recently, Zhang et al. (2024a) and Xu (2025) have for- malized a connection between homomorphism counts and the expressive power of many popular GNN architectures. While expressivity analysis can identify the theoretical limitations of learning algorithms, there is little research on how expressive power affects other properties such as. e.g., generalization, as recently pointed out by Morris et al. (2024), robustness (Campi et al., 2023; Kum- mer et al., 2025), or privacy. The lack of research on the interplay between expressivity and privacy has also been recently highlighted by Sajadmanesh et al. (2023), who call for more investigation on the expressive power of differentially private graph learning algorithms. A line of research in graph privacy focuses specifically on protecting the structural information in graphs, which is of- ten of sensitive nature. Privacy attacks can target the edges (Raskhodnikova & Smith, 2016) or the nodes (Kasiviswanathan et al., 2013; Xiang et al., 2024) of a graph, which can encode sensitive information (Mueller et al., 2022; Li et al., 2023; Zhang al., 2024b; Fu et al., 2023). Graph
2

---

Published as a conference paper at ICLR 2026
construction attacks can effectively recover private information from trained models (Zhang al., 2022: Wu et al., 2024; Zhou et al., 2023; Olatunji et al., 2023) and a number of differentially pri- vate graph learning approaches have therefore been proposed (Sajadmanesh & Gatica-Perez, 2024; 2021; Sajadmanesh et al., 2023; Pei et al., 2024; Olatunji et al., 2024; Joshi et al., 2024). To address the protection of the edges of graphs, Hidano & Murakami (2024), Xie et al. (2025), and Xu et al. (2024) focus on edge-level privacy. In particular, Hidano & Murakami (2024) consider edge-level privacy for graph-level tasks, which matches the problem setting we focus on. Furthermore, recent work has considered the problem of private subgraph counting, with focus on triangle counting (Ding et al., 2018; Imola al., 2022; Nguyen al., 2023). Although expressivity and privacy have been independently studied extensively for graph learning algorithms, their interplay has not been formally investigated so far. The cited differentially private graph learning algorithms, in fact, aim to obtain the best utility under privacy constraints but do not provide expressivity guarantees. We initiate the joint study of expressivity and privacy in graph representation learning to provide a better thcoretical and practical understanding of the trade-off between the two.
PRELIMINARIES
In this section, we introduce the relevant preliminaries on graph theory, expressivity, and differential privacy. More details can be found in Appendix A.
3.1 GRAPH THEORY AND EXPRESSIVITY IN GRAPH LEARNING
Let 9 denote the set of finite, simple graphs. A graph G = (V, E) E G consists of node set V(G) with n = IV(G) and edge set E(G) with e(G) = |E(G)] With a slight abuse of notation, let G U denote the graph obtained by deleting the nodes in U S VG).. For two sets S, T S V(G), let (S( denote the number of edges with one endpoint in S and one endpoint in T. For a Σi, |Ay denote the 4 norm of Ag. A tree decomposition of a graph G consists of tree T and a family B {b; I E V of subsets of V such that (i) U, b, V(G). (ii) for every edge
graph G with adjacency matrix Ag. let |Aall]
E(G), 3b, E B such that E b, and v E b, and (ziz) Vog by. by such that by lies on the path from b, to bg. then if node V E b, and u E by this implies that E by. The treewidth of tree decomposition is max, |6,| 1. The treewidth of a graph G is the minimum treewidth among all possible tree decompositions of G. Intuitively, the treewidth of a graph measures how tree-like graph is, e.g., trees have treewidth 1 and cycles have treewidth 2. Given two graphs F; G. a homomorphism from F' to G is an edge-preserving map and bijective. For
w : VFF) V(G). We call vi an isomorphism in case it is two graphs G, G' E G, let G ~ G¹ denote that the two graphs are isomorphic.
Definition 3.1 (Homomorphism density). Let hom G) denote the number of homomorphisms from F to G. Then, we define the homomorphism density as
hom F, G)
t(F, G)
[VFF)
We refer to a graph F E F C G as a pattern of the graph class F when we count the homomor- phisms from F to some graph G. For given vector of patterns F = -Fi,..., Fa) we consider the homomorphism density vector t(F, G) = (t(F1, G)..... t( Fa, G)). We now present two common distance notions for graphs, the edge edit distance and the cut distance.
Definition 3.2 (Edge edit distance and cut distance, Lovász 2012: Grohe 2020). For graphs G, G with the same number of nodes, the edge distance dedge and the cut distance du are defined
lea(S, T) e (S.T))
dedge GG, = 2 ||AG - AG do(G, = max S,TCV(G)
n²
It holds that (G, G') 2degge G') /n² (Lovász, 2012). The counting lemma upper bounds the absolute difference in the homomorphism densities of two graphs with respect to a pattern F.
Lemma 3.1 (Counting Lemma, Lovász 2012). For any three simple graphs F, G, and G with [V) = (G'),, it holds that [(F, G) - ((F.G)) & ((F)) G))
3

---

Published as a conference paper at ICLR 2026
As presented by Lovász (2012, Lemma 10.22), the counting lemma relies slightly different notion of the cut distance which allows to consider graphs with node sets of different cardinalities, which are not relevant for our discussion. We provide further details in Appendix A.
The expressive power of graph learning algorithms is commonly measured as their ability to distin- guish between pairs of non-isomorphic graphs. Let (p 9 + Rd be a graph embedding. We assume to be permutation-invariant i.e., for all G. G' E G. G = G' implies ((G) = ((""). This is trivially true for homomorphism counts and homomorphism densities.
The ability of an embedding to distinguish non-isomorphic graphs is referred to as completeness, which we introduce as follows.
Definition 3.3 (Completeness). An embedding 9 G Rd is complete if for all G, G, G cz G' and only if (pG)) = (G')..
A seminal result by Lovász asserts that homomorphism counts enjoy strong distinguishing proper- ties, as any pair of non- -oomisomooppicc graphs can be distinguished by counting homomorphisms.
Theorem 3.4 (Expressivity of homomorphism counts, Lovász 1967). For any two graphs G, G" it holds that G G' if and only if hommmF G) = hom G") for all simple graphs F.
The embedding built from the homomorphism counts for all patterns F E 9 is therefore complete. For patterns restricted to some specific graph class F S 9, we introduce the following notion.
Definition 3.5 (F-expressivity). An emhedding yp 9 TRdd is F-expressive if, for all G, E g and for all F E F, homm F, G) = hom(F, F, G') if and only if (G)) ((G').
Consider now a random embedding, parametrized by a random variable X D for some distribu- tion D and denote it by yx G + RR We introduce notions of completeness and expressivity in expectation as follows.
Definition 3.6 (Expectation compeeoeesssmleeeesssss.ss Welke al. 2023). An embedding px : g -> Rd is expectation-complett if the embedding Ex [px] is complete.
Definition 3.7 Feeexpectation-xxpeessiiiiiig expressive if the embedding Ex [px] is F-expressive.
An embedding Px g + Rd is F-expectation-
3.2 DIFFERENTIAL PRIVACY
Differential privacy (DP) is a formal notion of privacy that protects individual training points. DP is defined in terms of neighboring databases. database is a collection of points, where a point in a database may be, e.g., row in table an edge in a graph. Two databases x, x' are neighboring if they differ in a single point, that is, if one single point is present in one database but not in the other. ~1 z². DP guarantees that an attacker cannot confidently determine from which
We denote this of two neighboring databases the output of a DP mechanism has been obtained from. We introduce two notions of DP and briefly describe how achieve DP according these notions.
Definition 3.8 ((c, 8)-DP, Dwork et al. 2006). Let > 0 and å E [o. 1). A randomized mechanism M : X + y satisfies 5-approximate e-indistinguishabiitty differential privacy, denoted as (c, DP, if, for all neighboring x, x' X' and for all S C Range(M) it holds that Pr[M(x)) S] S e PP[M((z)) E S] + 6, where probabilities are taken over the randomness of M.
In DP, we refer to e as the privacy budget of mechanism, with larger values of providing less privacy, and value of c= 0 providing perfect privacy. To make given function f DP, one can add noise proportional
f(=')ll: II: see Appendix A.2 for more details. A distributional flavor of DP can be formalized in terms of the divergence of randomized mechanism when applied to two neighboring databases.
its global sensitivity GS max [z) (fe)))((())
Definition 3.9 ((,w)) w)PDPP Bun et al. 2018). Letp > 0 and w > Let D. denote the Rényi divergence of order (Rényi, 1961; Van Erven & Harremos, 2014). A randomized mechanism M : X - y satisfies t-tunncated p-concentrated differential privacy, denoted as (CCP), if, for all neighboring x E X, for all (1,w) it holds that (M(()) M(xx)) pa.
Definition 3.8 and Definition 3.9 can be formally related as tCDP implies (c. 5) (see Lemma A.2 in Appendix A.2). It is convenient consider tCDP as, in contrast to the standard mechanisms
4

---

Published as a conference paper at ICLR 2026
described in Appendix A.2, it allows to achieve DP while considering local notion of sensitivity for a function f at a point x.
Theorem 3.10. (1CDP with Gaussian noise, Bun et al. 2018) Let f.g : X + R satisfy, for every pair of neighboring databases x, E X and for yj Ag 2 0,
If(x) f(x') s A e0)2)2 [g(z) g(2²)] ) Ag.
X + R be the randomized mechanism defined as M(x) = f()) + N( co(s)). Then, M satisfies (A} A 4. 25g J-CDP..
Let M:
In Theorem 3.10, A e0())/2 is a smooth upper bound on the local sensitivity of f at r. This is con- sistent with the smooth sensitivity framework introduced by Nissim et al. (2007), which we describe in more detail in Section 4.2 and Appendix A.2. We extend Theorem 3.10 to the d-dimensional case in Theorem B.6 in Appendix B.3.
4 EXPRESSIVITY-PRIVER TRADE-OFF
In this section, we study the interplay between expressivity and privacy from theoretical perspec- tive. As previously discussed (see Figure 1), expressive embeddings can, by definition, not be private with respect neighboring graphs. In the other direction, DP requires to add enough noise to mix the representations of neighboring graphs so that they may not be distinguishable, hindering expres- sivity. Despite this tension, we can rely on the simple observation that DP noise has mean zero to note that DP preserves embeddings in expectation. In this context, we take advantage of the fact that homomorphism counts can be used to obtain embeddings which are, in expectation, complete (Lovász, 2012; Nguyen & Maehara, 2020; Welke et al., 2023). Exppectation-complete embeddings are a prime candidate for our analysis as they have, in expectation, arbitrary expressive power which can surpass the limits of, e.g., the WL hierarchy. We show that the noisy homomorphism densities, ie.. a private version of the normalized homomorphism counts, retain expressivity in expectation. To obtain embeddings which are not only private and expressive in theory but also useful in prac- tice, we then discuss a smooth sensitivity bound and use this to provide formal tCDP guarantees for the embeddings. Our analysis identifies key trade-off between expressivity and privacy: homo- morphism densities obtained from patterns which are sampled from a graph class F that provides stronger distinguishing power require larger amounts of noise to be DP, which may practically result in worse utility for the embeddings. The graph embeddings can then be used for any downstream graph learning task without incurring further privacy cost, thanks to the post-processe property of DP (Dwork et al., 2014). We defer all missing proofs to Appendix B.
4.1 EXPRESSIVITY IN EXPECTATION
In this section, we show that homomorphism density vectors with DP noise are, in expectation, expressive. For now we consider a generic noise term A with mean zero, condition that DP noise satisfies, and defer the precise expression for the DP noise to the next section (Section 4.2). For some graph G and pattern F, we define the noisy homomorphism density embedding as [(F, G) t(F, + N.. We define the noisy homomorphism density embedding t(F, G) for a vector of patterns F analogously. Note that i(F, G) is not germutation-invariann due to the added noise, a necessary consequence of the fact that DP requires randomized mechanism. This observation does not, however, affect the possibility to obtain expressive or even complete graph embeddings in expectation.' For our results, similarly to Welke et al. (2023), we assume that each pattern is sampled from appropriate distribution 'D with full support on the graph class F of interest.
We first show that for any fixed graph and single sampled pattern, the noisy homomorphism density embedding is expressive in expectation.
Theorem 4.1. For any G G, i(F, G) is F--exppctation-eeprssieeeeeeeeee F ~ D D has full support on F S G. If = G, then i(F, G) is expectation-compler
Note that homomorphism densities, in contrast to homomorphism counts, do not distinguish G and blowup of G. We discuss this issue and simple solution to it at the end of this section well as in Appendix B.
5

---

Published as a conference paper at ICLR 2026
As we often interested in homomorphism density vector obtained from number of sampled patterns, we extend Theorem 4. to the vector case. We show that the resulting noisy homomorphism density embedding is not only expressive in expectation, but also remains expressive with high probability for a large enough number of sampled patterns.
Theorem 4.2. Let D be a distribution on F S 9 with full support. Let G E g, F ~ Ddd and 0 E [0, 1]. For large enough d, t(F, G) is F-expressive with probability at least 1 0. If G, then, for large enough d, t(F, G) is complete with probability at least 1 0.
Theorem 4.1 and Theorem 4.2 demonstrate that, despite the noise required for DP, our homomor- phism density embeddings retain full discriminative power in expectation and, with enough patterns, with high probability.
4.2 PRIVACY GUARANTEES
In this section, we provide DP guarantees for the homomorphism density embeddings. To calibrate an appropriate amount of noise to be added the homomorphism densities to guarantee DP, we discuss how to bound the sensitivity of ((F, G). In particular, we choose 1CDP as our formal notion of privacy since it allows us consider local notion of sensitivity with Gaussian noise, which often requires less noise to be added in practical settings, In most of the following discussion, we consider the pattern F' be fixed, but we remark that achieve expressivity in expectation (see Section 4.1) the patterns are sampled from a distribution F ~ D. We focus on edge-level privacy and strive to protect the presence/absence of individual edges in a graph. We thus interpret neighboring graphs, according to the following definition, two neighboring databases.
Definition 4.3 (Neighboring graphs). Two graphs G, G' with the same number of nodes are neigh- boring graphs, written G ~ب G', if dedge (G,
Based notion of neighboring graphs,
leverage the counting lemma to obtain bound
on the global sensitivity of the homomorphism densities: For any two neighboring graphs G mvg G' with n nodes and for any pattern F get that GSS.F |((F, G) ((F, G')l d(F)du(GG G')
2e(F)/n² (see Corollary B. Since G.S,.F considers the worst case behavior of t around any graph G. using it in the standard DP mechanism (Appendix A.2) is likely to result in poor performance?. In contrast, local sensitivity, defined as (G) = EG:day(C [t(F, G) - ((F, G')l provides an upper bound on the sensitivity around specific graph G, and is often much smaller than G., Additive noise proportional to the local sensitivity, however, does not guarantee DP. A crucial step in our analysis is therefore to consider noise calibration under the smooth sensitivity framework (Nissim et al., 2007), which provides a smooth upper bound to the local sensitivity. For some B > 0 and pattern F. the 3-smooth sensitivity of t(F, G) at G defined as
(c- (e-Bduue (G.G') (.S).
(G)
max G'EG
As we consider homomorphism density vectors, we show in our next proposition how to provide an upper bound the smooth sensitivity of t(F (F,G) G) by considering the individual Sy. (G) for F; e F.
Proposition 4.4. Let (G) = 1|Sr., (G), Se. (G))l2 and B > O. Let
(G = max
e (G.H)
max H' (H)
||(FHH H) ((F,H')lb
(2)
HES
be the 3-smooth sensitivity of G) at G. Then, it holds that St, 2 S.)
In many cases, domain knowledge allows to assume that the degree of the graphs is bounded. We thus derive an even smaller bound the sensitivity of the homomorphism densities.
Theorem 4.5 (Sensitivity of homomorphism density for bounded degree graphs). Let G ~ G' be two neighboring graphs with n nodes and maximum degree Amax- For any pattern F with m > nodes, it holds that
2e(F) ( (Amas max m-2
((F,G) - ((F,
(3)
n?
n
"ee the ablation study in Appendix D.3 for empirical evidence supporting this claim.

---

Published as a conference paper at ICLR 2026
For large graphs and large patterns ( is often tighter in practice than the one we could directly obtain from the counting lemma. For domains where no meaningful public degree bound is available, one could either estimate Amax privately simply, set maax n. to recover the counting lemma. For a private estimate, one may add, c.g., Laplacian noise to the empirical maximum degree under a small additional privacy budget. For given density vector ((F, G), we can now use Theorem 4.5 to upper bound the smooth sensitivity of each t(F, G) individually and obtain an upper bound St, (G) for the entire vector as shown in Proposition 4.4. With this, present the main result of this section: private mechanism for homomorphism density vectors. More specifically, we derive a tCDP version of ((.G),
m2 < 1. Therefore, the bound provided by Equation (3) n
Theorem 4.6. Let F(F, G) be the homomorphism density vector for graph G and pattern set F with F| = d, p' > O, and let (G, be B-smooth upper bound to the local sensitivity as per Proposition 4.4. Then, the mechanism
((F.)) ((G))=(FFGG++))) (0, [G),
Ld
(4)
2p'
is (20' + d- 1.2,,, 49) 1CDP for neighboring graphs as per Definition 4.3.
Theorem 4.6 enables us to determine the amount of noise needed to guarantee tCDP for the ho- momorphism densities. The additive noise has mean zero, and thus our results expectation- expressivity of the previous section apply: in expectation, the noisy, private homomorphism densi- ties unbiased with respect the non- non-private densities. As smooth sensitivities upper-bounded by the global sensitivity, we expect the mechanism described in Theorem 4.6 to yield a significantly better privacy-utility trade-off compared to the standard Gaussian mechanism; see Table 6 in Ap- pendix D.3 for supporting empirical evidence.
4.3 PRIVATE AND EXPRESSIVE GRAPH REPRESENTATIONS
We are now able combine the results of the previous two sections to (1) show how to obtain provably expressive and private graph representations (Theorem 4.8), and (ii) formally quantify the expressivity-privccy trade-off (Proposition 4.9). First, we highlight a technicality on how to distinguish blowup graphs, which we also discuss more thoroughly in Remark B.1 in Appendix B. Remark 4.7 (Completeness of homomorphism density embeddings). A p-blowup of G can be ob- tained by replacing each node of G by 2 1 twin copies (Lovász, 2012). Two graphs G, G", where G' is blowup of G, have the same homomorphism density for any pattern F (Lovász, 2012, The- orem 5.32). Therefore, homomorphism densities cannot be used to distinguish all non-isomorphic graphs. To resolve this, append the node count [V(G) to the homomorphism density embed- ding of G to distinguish it from all its blowups. This operation is trivially DP with respect to the neighboring graph notion in Definition 4.3, as any two neighboring graphs have the same number of nodes, and thus costs no further privacy budget.
Our first result in this section states that we can generate graph embeddings which are provably private and expressive. We show that for chosen privacy budget and a chosen graph class F, we guarantee that our homomorphism density embeddings are tCDP and F-eexeectation-exprestt
Theorem 4.8. Let D be a distribution on F S 9 with full support. Let G E G be a graph and F (Fi...., Fa) ~ Ddd be vector of patterns. Then, the graph representation t(F, G) I(F, G) + N (0, [S,( Ta is [F-expectationeepprsstt and (24/ + d 4,32, T3 )CCDP, where p' > and Si,, (G) is a 8-smooth upper-bound on the local sensitivity of (FF G). I = G. then E G) is also especlation-compleee.
Theorem 4.8 allows us to characterize the expressive power of our embeddings more precisely by sampling patterns from graph class F that determines a certain level of expressivity in expectation (Nguyen & Maehara, 2020). For instance, it is well known that 1-WL serves as upper bound for the expressive power of large class of message-passing graph neural networks (MPNNs) (Xu et al., 2019; Morris et al., 2019). The expressive power of 1-WL, in turn, is equivalent to counting tree homomorphisms. In other words, two graphs have the same 1-WL color multiset (Xu et al., 2019) if and only if they have the same homomorphism counts for all trees. This equivalence can be general- ized for many popular GNN architectures by determining their homomorphissmmdiiingggiitto
closed
7

---

Published as a conference paper at ICLR 2026
graph class (Neuen, 2024), which corresponds to the pattern graph class in setting. For instance, the expressive power k-GNNN (Morris et al., 2019; 2023) corresponds to the homomorphism- distinguishing closed graph classes of treewidth & (Neuen, 2024). We refer to Zhang et al. (2024a) and Xu (2025) for a more in-depth discussion of homomorphism expressivity and general techniques closed graph classes for given GNN architectures.
to obtain aamommmphisn-diiiiggiiiinn
Table Common GNNs and their homomorphism distgigiinniistniiiiiiiiinn closed graph classes. See Paolino et al. (2024) for r-MMPNNs, Gai et al. (2025) for spectral invariant GNNs, and Zhang et al. (2022) for the remaining GNNs. For details on the maximum numbers of edges refer to Appendix B.2.
GNN
Graph class F
mI F=FF.===.((V) e(F)
MPNNs (1-WL)
Trees
m
r-MMPNN (r-EWL)
Fan-cactus graphs
2m 3
Spectral invariant GNNs
Parallel trees
2m -
{F EU c V(F) s.t.
Subgraph k-GNNs
m(k + 1) -
43k
UU] S k and F U is forest)
k-FGNNs (k-WL)
{F : (W(F) < k}
km k(+++))
Based on our theoretical investigation, we now present our second result and quantify the trade-off between expressivity and privacy: the choice of the graph class F does not only affect expressivity, but also the amount of noise that needs to be added to the embeddings to obtain privacy guarantees.
Proposition 4.9. Consider a graph G with n nodes and let F be class of patterns. For a chosen privacy parameter p' > O, the Gaussian noise necessary obtain a specific privacy guarantee in Theorem 4.8 has variance o² = ((maxre) e(F))² /n²).
Table provides the commomopphisn-diiinnggiiiiiin closed graph class F as well as its maximum number of edges for some well-known GNN architectures with expressive power precisely charac- terized by i.e., that can distinguish all non-isomorphic graphs F. With this information, we are able to generate private graph embeddings that, in expectation, match the expressive power of many GNN architectures. In general, more expressive GNN architectures often have greater bounds on e(F) for F E F. From Proposition 4.9 can therefore conclude that with patterns sampled from more expressive graph classes, more noise is required to achieve given privacy guarantee. Thus, we have identified an explicit trade-off between expressivity and privacy.
EXPERIMENTS
We complement our theoretical investigation with a compact empirical study that can be run on single commercial GPU. Our goal is not compete with state-of-the--e approaches, but rather to probe the trade-off between the desiderata of expressivity and privacy in practice, as well as assess the utility, i.e., the performance, of our private embeddings real-world and synthetic datasets. We organize our experimental evaluation around the following research questions:
Q1. For fixed privacy budget, do embeddings obtained from more expressive graph classes offer better performance?
Q2. For fixed class of patterns, how does performance degrade when we require stronger privacy guarantees?
Q3. Are the expressive and private embeddings we obtain practically useful?
Experimental setup. We evaluate the private and expressive homomorphism density vectors for graph-level tasks real-world as well as synthetic datasets. We run experiments on four commonly used OGBG molecular benchmark datasets (MOLHIV, MOLBACE, MCLBB3P, and MOLLIPO (Hu et al., 2020)) and on three network datasets (REDDIT BENIIT-BINARR BINARY and REDDIT-MULTY 5K (Xiang et al., 2024), and GitHub STARCAZERS (Rozemberczki et al., 2020)). Additionally, we perform experiments synthetic stochastic block model (SBM, Appendix C.2). As we focus how the graph structure can be privately leveraged to have expressive representations, the core of our experiments relies the graph structure only encoded by the homomorphism density vectors
8

---

Published as a conference paper at ICLR 2026
and does not consider any node edge features. We experiment with different privacy parameters p' E 8.0_ To make results more interpretable, we convert our tCDP guarantees into (c, 5) DP guarantees using Lemma A.2 in Appendix A.2; (e, 6)-DP guarantees are casier interpret as privacy budgets roughly in the range E (0, 10 are generally understood to provide meaningful privacy protection in graph machine learning (Wu al., 2022; Sajadmanesh & Gatica-Peres 2021). To evaluate privacy protection empirically, we run the privacy attacks detailed in Appendix D to try and recover the original graphs. We consider sampled vectors of patterns F with d 50 for all experiments. We compare the performance of our embeddings against the Randomized Response (RR) and the degree-presse preserving Randomized Response (DPRR, Hidano & Murakami, 2024) GNN baselines. For details on the experimental setup, baselines, and additional results, see Appendix D.
Time complexity. While counting homomorphisms is intractable in general, there exist efficient algorithms for certain graph classes. For instance, homomorphism counts for cycle patterns can be computed efficiently via powers of the adjacency matrix, see Proposition C.2 in Appendix C. For bounded treewidth patterss, Díaz et al. (2002) introduced polynomial- computes hom F, G) in ((I(F)) (F))),)()) where tw( (F) denotes the treewidth of pattern F. Based on this result, Welke et al. (2023) devise a sampling strategy with polynomial runtime in expectation by decreasing the probability mass of patterns with higher treewidth. The key idea behind their approach is to construct a probability distribution and ensure that every pattern has nonzero, but potentially very small probability to be sampled. We refer to Welke al. (2023, Theorem 15, Appendix C) for a more in-depth discussion on the construction such a distribution and details the sampling strategy. We remark that the computation and addition of DP noise does not introduce any noticeable computational overhead. Furthermore, the computation of our embeddings can be regarded as one-time pre-processing step and they can subsequently be used for any downstream analysis. In practice, counting homomorphisms from bounded treewidth patterns, which matches the expressive power of highly expressive GNNs, can be done on standard consumer- grade hardware; see Table 7 in Appendix D.4 for detailed runtimes for MOLHIV with increasing maximum treewidth of tw {1, 2, 3} and for REDDIT-BINARY with tw
algorithm that
SBM accuracy
MVL AUC and attack accuracy vs maximum treewidth
1.0
3.75
0.70
350
Top Allocks Accunacy
0.65
Accuracy
3,25
0.6
0.60
3.00
0.55
2775
0.50
250
AJC
0.2
0.45
2.25
10a
10
2
10a 1
10P
10a
10a
Maximum treewidth
(a) Classification accuracy vs privacy budget e on
(b) Classification AUC and attack accuracy vs max treewidth on MOLHIV with A-NN for c = 1.
SBM with I--N for tree and cycle patterns.
Figure 2:
Visualizations for two of our experiments SRM and MOLHIV. We report average results with error bars of standard deviations across 9 runs.
Results. To answer questions Q1 and Q2 we perform two sets of experiments: In the first set of experiments (a), we consider a learning task where one pattern class is provably more expressive than another pattern class. the second set of experiments (b), we instead consider learning task where more expressive patterns are not expected to improve performance. For (a), we construct an SBM dataset, for which cycle patterns have provably stronger distinguishing properties than tree patterns (see Lemma C.1 in Appendix C.2). We observe in Figure 2a that cycle homomorphism densities, a pattern class that ensures expressivity expectation, result in drastically better practical performance compared to tree homomorphism densities. We can further see that the performance for cycles remains good for reasonable privacy budgets around e = 1. For (b), we use patterns with increasing maximum treewidth of 2,,,, and therefore increasing expressive power, MOLHIV. On this dataset, patterns with maximum treewidth of 1 achieve good performance. In this case, choosing patterns from more expressive graph classes may not offer a benefit in performance: to

---

Published as a conference paper at ICLR 2026
Table 2: Utility and attack accuracy for our experiments on OGBG datasets. As utility metric, we use the regression RMSE for MOLLIPO and the classification AUC for MOLHIV, MOLBBBP, and MOLBACE. We report average results and standard deviations across runs. Bold marks best results for the private runs.
((F
MOLHIV 1
MOLBBBP 1
MOLBACE f
MOLLIPO +
Utility 0.692 (0.020)
0.602 (0.005)
0.652 (0.069)
1.086 (0.0D4)
Private (c 1)
Attack
0.003 (< 0.001)
0.025 (0.003)
0.027 (0.002)
0.011 (0.002)
Utility
0.745 (< 0.001)
0.644 (0.008)
0.752 (0.002)
1.055 (0.002)
Non private (e 00)
Attack
0.955 (0.020)
1.000 (< 0.001)
0.990 (< 0.001)
0.992 (0.006)
GNN Baseline
Private (e 1) RR
Utility 0.488 (0.008)
0.440 (0.005)
0.457 (0.024)
1.568 (0.248)
Private (c 1) DPRR
Utility 0.595 (0.155)
0.539 (0.019)
0.648 (0.043)
1.499 (0.333)
Non private (e = oo)
Utility
0.672 (0.022)
0.586 (0.027)
0.768 (0.033)
1.033 (0.021)
obtain the same privacy guarantee and comparable resilience privacy attacks, we expect add more noise to more expressive patterns according to Proposition 4.9. In fact, in Figure 2b, we ob- serve downward trend in the AUC as we increase the maximum treewidth. This confirms that there is indeed a practical trade-off between expressivity and privacy. Finally, our results in Table 2 and Table 4 (in Appendix D.2) positively answer Q3: overall, our private and expressive homomorphism density vectors are useful embeddings for graph classification and regression tasks. Moreover, the private embeddings offer significantly better resilience to privacy attacks compared to their non- private counterparts. For reasonable privacy budget of e = 1, we always outperform the baselines on the OGBG datasets and MCLHTV, MOLBBBP, and MOLLIPO stay within 90% of the performance of the non-private homomorphism density embeddings. For the network datasets, we obtain perfor- mances comparable to those in Hidano & Murakami (2024), despite relying on significantly simpler classifiers, which further confirms the practical usefulness of our embeddings; see Appendix for more in-depth discussion. Indeed, we emphasize that for all our experiments we use basic machine learning algorithms such as k-nearest neighbor (k-NN) classifiers, support vector machines, and random forests (see Appendix D.1). This suggests that the private embeddings we obtain are them- selves highly informative. We report further experiments and ablation studies in Appendix D, where we verify the impact of node features on utility, and we confirm that a straightforward implemen- tation of DP with global sensitivity yields unusably noisy embeddings. This further highlights the necessity for the more refined bounds on sensitivity we discuss in Section 4.2 to obtain practically useful private embeddings.
CONCLUSION
We study the trade-off between expressivity and privacy in graph representation learning. Our results first address an existing research gap on the interplay between the desiderata of expressivity and pri- vacy. We propose a noisy version of homomorphism densities as graph embeddings, and show that our embeddings satisfy formal expressivity and differential privacy guarantees. Our expressive and private embeddings can be used for any downstream task and with any machine learning algorithm without incurring further privacy costs. In our experiments, we show that our embeddings are useful in practice and retain high performance with practical protection against privacy attacks.
Limitations. A natural limitation of our approach is that it inherits all the limitations of homo- morphism counts and densities. As discussed, homomorphism counts can be expensive to compute. Moreover, homomorphism counts alone may not be sufficient for good practical performance, espe- cially node features and their topological arrangements are crucial for the task at hand.
Future work. A promising direction for future work is refine the noise calibration by more precisely analyzing the sensitivity of specific graph classes, and to privately encode edge features to further improve the iivaac-uuiliity trade-off.
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
Our work provides formal guarantees that align with the increasing regulatory push toward privacy- preserving machine learning models. We next detail our usage of LLMs. We use LLMs for the following use cases: (i) as coding assistant, (ii) for discussion and suggestions on the experimental setup, (tii) for retrieval and discovery of related work, and (iv) for feedback the final draft of our submission. In all cases, we, the authors, were the last ones to check and modify the content accordingly. Furthermore,
ensured that the content of this submission not used for further training of LLMs to not bias the reviewing process.
REPRODUCIBILITY STATEMENT
All theoretical statements supported by proofs, which can be found in Appendix B, and/or pointers to existing literature. Our experimental setup is detailed in Appendix D and the code used produce empirical results can be found here: https: / / thub. com/ tama comaramay rmaagdr Silvate-hhocountss
AUTHOR CONTRIBUTIONS
The idea conceived and developed jointly by Pl and TD, who wrote and proofread the theoretical contribution, the code, and the manuscript under the supervision of TG.
ACKNOWLEDGMENTS
We would like to thank Maximilian Thiessen, Pascal Welke, and Fabian Jogl for helpful discussions and feedback. We would also like to thank Flaviano De Santis and Christoph Sandrock for proof- reading our submission. This work was funded in part by the Vienna Science and Technology Fund (WWTF), project StruDL (ICT22-059); by the Austrian Science Fund (FWF), project NanOX-MI (6728); by the TU Wien DK SecInt and by the European Unions Horizon Europe Doctoral Network programme under the systems chemistry (101072930).
grant, project Training Alliance for Computational
REFERENCES
Paul Beaujean, Florian Sikora, and Florian Yger. Scaling up graph homomorphism features with ef- ficient data structures. In ICLR Workshop on Geometrical and Topological Representation Learn- ing, 2021.
Jan Böker. Graph similarity and homomorphism densities. In 48th International Colloquium Automata, Languages, and Programming, pp. 32-1. Schloss Degstuhh-Leibbiiz-Zenttnn für In- formatik, 2021.
Mark Bun, Cynthia Dwork, Guy Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated CDP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 74 86, 2018.
Francesco Campi, Lukas Gosch, Tom Wollschläger, Yan Scholten, and Stephan Günnemann. Ex- pressivity of graph neural networks through the lens of adversarial robustness. In ICML Workshop on New Frontiers in Adversarial Machine Learning, 2023.
Josep Díaz, Maria Semna, and Dimitrios M Thilikos. Counting h-colorings of partial k-trees. Theo- retical Computer Science, (81()))929,,3,9 2002.
Xiaofeng Ding, Xiaodong Zhang, Zhifeng Bao, and Hai Jin. in large graphs. In Proceedings of the 27th ACM international conference information and knowledge management, pp. 1283-1292, 2018.
triangle counting
Cynthia Dwork. Differential privacy. In International Colloquium on Automata, Languages, and Programming, pp. 1-12. Springer, 2006.

---

Published as a conference paper at ICLR 2026
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Anmual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 486-503. Springer, 2006.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):3))))
(3--4)211 10:2111220 1-007, 2014.
European Parliament and Council of the European Union. Regulation (EU) 2016/679 of the Euro- pean Parliament and of the Council of 27 April 2016 on the protection natural persons with regard to the processing of personal data and on the free movement of such data, and repealing Directive 95/46/EC (General Data Protection Regulation). Official Journal of the European Union I. 119, 2016.
European Parliament and Council of the European Union. Regulation (EU) 2024/168 of the Euro- pean Parliament and of the Council of 13 June 2024 laying down harmonised rules on artificial in- telligence and amending Regulations (EC) No 300/2008, (EU) No 167/2013, (EU) No 168/2013, (EU) 201 8018/858, (EU) 2018/1139 and (EU) 2019/2144 and Directives 2014/90/EU, (EU) 2016/797 and (EU) 2016/798 (Artificial Intelligence Act). Official Journal of the European Union 1689, 2024.
Dongqi Fu, Wenxuan Bao, Ross Maciejewski, Hanghang Tong, and Jingrui He. Privacy-preserving graph machine learning from data to computation: A survey. ACM SIGKDD Explorations Newsletter, 25(1):54-72, 2023.
Jingchu Gai, Yiheng Du, Bohang Zhang, Haggai Maron, and Liwei Wang. Homomorphism expres- sivity of spectral invariant graph neural networks. In The Thirteenth International Conference Learning Representations, 2025.
Manuel Gil, Fady Alajaji, and Tamas Linder. Rényi divergence measures for commonly used uni- variate continuous distributions. Information Sciences, 149:124-131 2013.
Martin Grohe. word2vec, node2vec, graph2vec, x2vec: Towards a theory of vector embeddings of structured data. In Proceedings of the 39th ACM SIGMOD -AMOD-SIGACT-SSGAI Symposium Principles of Database Systems, pp. 1-16, 2020.
Seira Hidano and Takao Murakami.
randomized response for graph neural net- works under local differential privacy. Transactions on Data Privacy, 17(2):89 1228,9111,,111 2024.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Informatinn Processing Systems, 33:22118 01222118-22133 22133, 2020.
Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. ing under local differential privacy. In 31st USENIX Security Symposium, pp- 537-554, 2022.
ciammunication-Effiiiiin triangle count-
Emily Jin, Michael Bronstein, ismail Îlkan Ceylan, and Matthias Lanzinger. Homomorphism counts for graph neural networks: all about that basis. In Proceedings of the 41 International Confer- ence on Machine Learning, pp.
2024.
Rucha Bhalchandra Joshi, Patrick Indri, and Subhankar Mishra. Graphprivatizer: Improved struc- tural differential privacy for graph neural networks. Transactions on Machine Learning Research, 2024.
Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyzing graphs with node differential privacy. In Theory of Cryptography: 10th Theory of Cryptography Conference, pp. 457-476. Springer, 2013.
Lorenz Kummer, Wilfried N. Gansterer, and Nils Morten Kriege. On the relationship between robustness and expressivity of graph neural networks. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
Yang Li, Michael Purcell, Thierry Rakotoarivelo, David Smith, Thilina Ranbaduge, and Kee Siong Ng. Private graph data release: A survey. ACM Computing Surveys, 55(11):1-39, 2023.
12

---

Published as a conference paper at ICLR 2026
László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-4):321-325, 1967.
László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
Takanori Maehara and Hoang NT. Deep homomorphism networks. Advances in Neural Information Processing Systems, 37:56076-56107, 2024.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Pruceedings of the AAAl conference on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. Journal of Machine Learning Research, 24(333):1-59) 2023.
Christopher Morris, Fabrizio Frasca, Nadav Dym, Haggai Maron, Ismail IIkan Ceylan, Ron Levie, Derek Lim, Michael M. Bronstein, Martin Grohe, and Stefanie Jegelka. Position: Future direc- tions in the theory of graph machine learning. In Proceedings of the 41st International Conference Machine Learning, pp. 36294 36294-36307, 2024.
Tamara T Mueller, Dmitrii Usynin, Johannes C Pactzold, Daniel Rueckert, and Georgios Kaissis. SoK: Differcntial privacy on graph-structure data. arXiv preprint arXiv:2203.09220. 2022.
National Institute of Standards and Technology. Artificial Intelligence Risk Management Frame- work (AI RMF 1.0). Technical Report NIST AI 100-1, U.S. Department of Commerce, 2023.
Daniel Neuen. Homomorphism--diiingiuus
closedness for graphs of bounded tree-width. In 41 International Symposium on Theoretical Aspects of Computer Science, pp. 53-1. Schloss Dagstuhl- Seastull-LiibnizZZeeturr für Informatik, 2024.
Dung Nguyen, Mahantesh Halappanavar, Venkatesh Srinivasan, and Anil Vullikanti. Faster approx- imate subgraph counts with privacy. Advances in Neural Information Processing Systems, 36: 70402-70432, 2023.
Hoang Nguyen and Takanori Machara. Graph homomorphism convolution. In Proceedings of the 37th International Conference on Machine Learning, pp. 7306-7316, 2020.
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling private data analysis. In Proceedings of the thirty-ninth annual ACM symposium Theory of computing, pp. 75- 84, 2007.
Iyiola E Olatunji, Mandeep Rathee, Thorben Funke, and Megha Khosla. Private graph extraction via feature explanations. Proceedings Privacy Enhancing Technologies, 2023.
Iyiola E Olatunji, Thorben Funke, and Megha Khosla. Releasing graph neural networks with differ- ential privacy guarantees. Transactions on Machine Learning Research, 2024.
Raffaele Paolino, Sohir Maskey, Pascal Welke, and Gitta Kutyniok. Weisfeiler and Leman go loopy:
A new hierarchy for graph representational learning. Advances in Neural Information Processing Systems, 177:12070-120833 2024.
Xinjun Pei, Xiaoheng Deng, Shengwei Tian, Jianqing Liu, and Kaiping Xue. Privacy-enhanced graph neural network for decentralized local graphs. IEEE Transactions Information Forensies and Security, 19:1614-1629, 2024.
Sofya Raskhodnikova and Adam Smith. Differentially private analysis graphs. Encyclopedia of Algorithms, 2016.
Alfréd Rényi On measures of entropy and information. In Proceedings of the fourth Berkeley symposium on mathematical statistics and probability, volume 1: contributions to the theory of statistics, volume 4, pp. 547-562, 1961.
Benedek Rozemberezki, Oliver Kiss, and Rik Sarkar. Karate Club: API oriented open-source python framework for unsupervised learning on graphs. In Proceedings of the 29th ACM Inter- national Conference Information & Knowledge Management, pp. 3125-3132, 2020.
13

---

Published as a conference paper at ICLR 2026
Sina Sajadmanesh and Daniel Gatica-Pert Perez. Locally private graph neural networks. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, pp. 2130- 1130-2145, 2021.
Sina Sajadmanesh and Daniel Gatica-Perez. ProGAP: Progressive graph neural networks with dif- ferential privacy guarantees. In Proceedings of the 17th ACM International Conference Web Search and Data Mining, pp. 596-605, 2024.
Sina Sajadmanesh, Ali Shahin Shamsabadi, Aurélien Bellet, and Daniel Gatica-Perez. GAP: Differ- entially private graph neural networks with aggregation perturbation. In 32nd USENIX Security Symposium, pp. 3223-3240, 2023.
Till Schulz and Pascal Welke. On the necessity of graph kernel baselines. In ECML-PKDD, GEM workshop, volume pp. 6, 2019.
Tim Van Erven and Peter Harremos. Rényi divergence and Kullback-Leibler divergence. 1EEE Transactions on Information Theory, 60(7):3797-3820, 2014.
Yue Wang, Xintao Wu, and Donghui Hu. Using randomized response for differential privacy pre- serving data collection. In EDBT/ICTT Workshops, volume 1558, pp- 0090-6778, 2016.
Pascal Welke, Maximilian Thiessen, Fabian Jogl, and Thomas Gärtner. Expectation-complete graph representations with homomorphisms. In Proceedings of the 40th International Conference on Machine Learning, pp. 36910-36925, 2023.
Hinrikus Wolf, Luca Ocljeklaus, Pascal Kühner, and Martin Grohe. Structural node embeddings with homomorphism counts. arXiv preprint arXiv:2308. 2023.
Fan Wu, Yunhui Long, Ce Zhang, and Bo Li. LinkTeller: Recovering private edges from graph neural networks via influence analysis. In IEEE Symposium on Security and Privacy, pp. 2005- 2024. IEEE, 2022.
Ruofan Wu, Guanhua Fang, Mingyang Zhang. Qiying Pan, Tengfei Liu, and Weiqiang Wang. On provable privacy vulnerabilities of graph representations. In Advances in Neural Information Processing Systems, volume 37, pp. 90891-90933, 2024.
Zihang Xiang, Tianhao Wang, and Di Wang. Preserving node-level privacy in graph neural networks. In IEEE Symposium on Security and Privacy, pp. 4714-4732, 2024.
Yule Xie, Jiaxin Ding, Pengyu Xue, Xin Ding, Haochen Han, Luoyi Fu, and Xinbin Wang. Lever- aging homophily under local differential privacy for effective graph neural networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 380- 396, 2025.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? 7th International Conference on Learning Representations, 2019.
Tuo Xu. Towards a complete logical framework for GNN expressiveness. In The Thirleenth Inter- national Conference on Learning Representations, 2025.
Wanghan Xu, Bin Shi, Ao Liu, Jiqiang Zhang, and Bo Dong. GraphPub: Generation of differential privacy graph with high availability. arXiv preprint arXiv:2403.000300 2024.
Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond Weisfeiler- Lehman: quantitative framework for GNN expressiveness. In The Twelfth International Con- ference Learning Representations, 2024a.
Yi Zhang, Yuying Zhao, Zhaoqing Li, Xueqi Cheng, Yu Wang, Olivera Kotevska, Philip S Yu, and Tyler Derr. A survey on privacy in graph neural networks: Attacks, preservation, and applications. IEEE Transactions on Knowledge and Data Engineering, 2024b.
Zhikun Zhang, Min Chen, Michael Backes, Yun Shen, and Yang Zhang. Inference attacks against graph neural networks. In 31st USENIX Security Symposium, pp. 4543-4560, 2022.
Zhanke Zhou, Chenyu Zhou, Xuan Li. Jiangchao Yao, Quamming Yao, and Bo Han. On strengthen- ing and defending graph reconstruction attack with markov chain approximation. In Proceedings of the 40th International Conference on Machine Learning, pp. 42843 42877, 2023.
14

---

Published as a conference paper at ICLR 2026
A ADDITIONAL PRELIMINARIES
In this section we provide additional details on the preliminaries.
A.1 CUT NORM
In our preliminaries have implicitly assumed that G and G" are defined the same node set, i.e., the nodes of G and G" have some fixed labeling which minimizes the cut distance. If two graphs G and G" have the same cardinality but different node sets, their distance is defined
Gn(G,C) min d-(G, &,G'
(5)
with & and G' ranging over all possible labelings of the nodes of G and G".
For two graphs G and G" with different cardinalities, we define the cut distance using fractional overlays. fractional overlay of two graphs G of order n and G' of order n' is a nonnegative n X n' matrix X = [Xiuluxn' such that Σ Xiu = and E Xix = x If n n', let V(G) V(G") be bijection. Then, Xia =))== is fractional overlay. For fixed fractional overlay X, we define the labeled cut distance as
do G)
Σ
Xiu - LuvE
max Q.RC"
iuEQ joER
The cut distance between G and G' is defined over all overlays X'G, G'):
(G) min XEX(G,G)
do G', X).
(6)
Note that, in general, for two graphs with the same cardinality d may not coincide with d and it holds that 6D G*) < 8G G") (Lovász, 2012). We can now re-state the counting lemma with more precise notation.
Lemma A.1 (Counting Lemma Lovász 2012, Lemma 10.22). For any three simple graphs F, G, and G', it holds that:
((F.G)-((R)) G*) s e(F))u(G,G')
As in our setting we consider pairs of graphs G, G' with the same number of nodes which share the same node set, have that dg(G, G") (G G') and we thus do not need consider the distance defined over fractional overlays.
A.2 DIFFERENTIAL PRIVACY
We provide here additional preliminaries on DP, with focus on how to achieve DP with additive noise scaled to the global sensitivity of a function.
Definition A.1 (e-DP, Dwork 2006). Let 2 0. A randomized mechanism M: X + y satisfies e-idistinguishabiiity differential privacy, denoted as e-DP, if, for all neighboring 2, x' e X and all C Range(Me (M) it holds that
Pr[M(z) E S Pr(((')) e),
S
(8)
where probabilities are taken over the randomness of M.
Definition A.2 ((c, DDDP, Dwork et al. 2006). Let 2 0 and 5 E [0, 1). A randomized mechanism M X + y satisfies 5-approximate c-indisinguishabiiity differential privacy, denoted as (c, 8D- if, for all neighboring x, r E X' and all S C Range(M) it holds that
Pr[M(z) E 8] < et Pr[M(z') E S] 6,
(9)
where probabilities are taken the randomness of M.
15

---

Published as a conference paper at ICLR 2026
In the literature, c-DP also referred to pure DP while (c, 8)-DP is also referred to approximate DP. Given a deterministic function f. one can build private mechanism from f by means of additive noise calibrated to its global sensitivity GS max (z) - f(z')llp where I1-1lp is lp- norm. When p is omitted, we consider lg norms.
Theorem A.3 (Laplace mechanism for pure DP, Dwork 2006; Dwork et al. 2014), Let f: : + R
have & sensifivity G. The randomized mechanism M(x) (x) + Lap GS
satisfies
e-D,, where Lap(b) denotes Laplacian noise with mean 0 and scale b.
Theorem A.4 (Gaussian mechanism for approximate DP, Dwork et al. 2006; Dwork 2006). Let
f X 7 E. have l2 sensitivity f.2 The randomized mechanism M(x) f(x) + (0(000')
satisfies (e, DD for o 2 (S5..2222nii
Lemma A.2 (ICDP implies (e,P)-DP, Bun et al. 2018). Suppose mechanism M satisfies (p, w)) 1CDP with a Rényi divergence of order a. Then, for all E [0,1), < a S w. M satisfies (e, 8) with
p 2 p1n(1/5) ps + Lm(1/0)/(w 1) if In(1/0) 2 (w 11
if In(1/6) S (w- 1)2p
E
Definition A.5 (Smooth Sensitivity, Nissim et al. 2007). For function X' measure the distance between x and x', where d(x, x') = 1 indicates that x ~ x'. Define the local sensitivity of f at
f - R. let d(z, x')
max (S ='Xx:((=.')
If(x) - f(x').
(10)
For B > 0, the 8-smooth sensitivity of f at x is then defined as
Sy(x) max yEX
8 (d(()))) LS
(11)
It is immediate to see that for all x E X, it holds that (1) I GS Therefore, we expect method that relies on smooth sensitivities to provide better utility, compared to one that relics on global sensitivities.
B MISSING PROOFS
In this section, we restate our theoretical results and provide proofs that we omitted in the main part.
B.1 EXPRESSIVITY
Remark B.1 (On graph blowups). For the following proofs, it is necessary to address the fact that two graphs G.G', where G' is a blowup of G, have the same homomorphism density for any pattern F (Lovász, 2012, Theorem 5.32). p-blowup of G can be obtained by replacing each node of G by p 2 1 twin copies (Lovász, 2012). Therefore, homomorphism densities cannot be used to distinguish all non-isomorphic graphs. This subtlety is not addressed in Welke et al. (2023) who, in fact, rely on the wrong assumption that homomorphism densities are complete for some of their results. We can address this two ways. We can (i) rely on homomorphism counts, which do not present the same problem and can be used to obtain a complete embedding (Lovász, 1967; Welke et al., 2023). As our DP statements consider pairs of graphs with the same number of nodes, this only requires to rescale the definitions of sensitivity and leads to equivalent statements about the privacy of the embeddings. This does not affect the utility of our embeddings which are, simply, rescaled. Alternatively, we can (ii) append the node count [V(G) the homomorphism density embedding of G' to distinguish it from all its blowups. This operation is trivially DP with respect to the neighboring graph notion in Definition 4.3 and costs no further privacy budget. As we rely on the counting lemma to derive our sensitivity bounds, we choose to present our results in terms of homomorphism densities. Therefore, we will assume that, necessary, the node count is appended to the embedding so that the following statements hold'. We stress that this is simply choice of presentation, as all our expressivity and privacy statements could be easily rephrased in terms of homomorphism counts.
Nnte that this can also be used to recover the results presented in Welke et al. (2023) that rely on the completeness of homomorphism densities.
16

---

Published as a conference paper at ICLR 2026
Theorem 4.1. For any G E G. ((F G) F-expectation-eeprssstteeeeeeeee F D if has full support on F - G. = then i(F, G) is expectation-compleee.
Proof. Consider
T= =
Σ Pr( P(F(F=F)d(F F'EF
(12)
where ep R| is standard basis unit vector of IR!F1. We can write ((F,G) ((F + where Y ~ NNay 0, 2)) for some variance o². Note that Y and F are independent random
variables. It then holds that
B[((F,G) = (|( + [E[((FF + By EF|((E, G)] + By
+ Yerl
(13)
(14)
= [F[t(F,G)] =
(15)
remains to show that 7 is F-expressive. Let G, G' be two graphs for which there exists F E
such that hom(F G) * "homm"","') and let 7' be the corresponding vector representations. If [V)G) * IV(G") and G" is blowup of G or vice-versa, simply append the node counts to T, get (G))) +
[V())), then hom(F", G) + hom(F", G") has full support on F, then Pr(F = F') 0 and therefore Pr(F (F G) * Pr(F F'F((FF, G'), which implies * T'. This shows that F- expressive. I = G, then + T' for any two G * G², with analogous argument. Therefore, is this case complete.
[V (G')). If
implies that t(F', G) }0)
Theorem 4.2. Let D be distribution on F C 9 with full support. Let G E G, F ~ Dd. and 0 E [0, 1]. For large enough d, t(F, G) is F-expressive with probability at least 1 0. If G, then, for large enough d, t(F, G) is complete with probability at least 1 0.
Proof. Let G, G' be any two graphs for which there exists F' E F such that hom FF', G) + hom FV, G.). First, we consider the noise-free homomorphism density vectors and want to show that
t(F,G) (t(F), G), ((Fa, G)) * (t(F), G'), t(F,, (F,,,..,,,...GGGG) t(F.G')
(16)
with probability at least 1 - 0, where F1. Fi..... ~ D iid. To show this, we adapt the proof of Lemma 3 by Welke al. (2023). Since t(F,G) is F-expressivee for F ~ D. then Ef[t(F,G)) # Er(t(P G')). In particular, there exists a set &G.G of outcomes of F with Pr(F E 3G. such that for all F E $a. it holds that 1(F", G) # 1(F", G'). We want that Pr[ E (1 (1....,d)
F; 3G.G 2 1 - 6, and thus must hold that 1 - (1 p)d 2 1- 0. Solving for d, we obtain that 1n(1 (0) 1. then t(F,G) G) is F-expressive with probability at least 1 -
if
Considering now {(F, G), note that if G) t(F*, G'), then, for any variance 0², it also holds that E(F* G) t(F', + (N0, # t(F G') + N 8(F G') with probability 1. That is, the patterns for which the noise-free bomomorphism densities will distinguish G and G', also work with additive noise. Therefore, i(F, G) is F-expressive with probability at least
If F G, then G(F + i(F, G') for any two G G', with analogous argument. Therefore, E( F, G*) is in this case complete with probability at least - 0.
B.2 COMMMMORPHISM-DDSTTINGUUSSSSSSSS
CLOSED GRAPH CLASSES
In Table 1, we report homomorphism hisphiiiiim-istiinnnsiinn closed graph classes for known GNN architec- tures (Zhang et al., 2024a). For r-MMPNNs, we upper bound the number of edges by the maximum number edges outerplanar graphs since fan-cactus graphs are outerplanar (Paolino et al., 2024). For k-FGNNs, we upper bound the number of edges for graphs of bounded treewidth & by considering the number of edges a le-tree, as formalized in the following proposition.
Proposition B.2. Let F {F tw(F) < k}. Then, any F E F with V(F) = m nodes has at most km k(k 1) edges.
17

---

Published as a conference paper at ICLR 2026
Proof. A k-tree is an edge-maxts dige-maximal graph of treewidth i and can be constructed by starting with a (k + 1)-clique and adding new nodes such that each new node is connected to exactly existing nodes. The initial (k + 1)-ciique has } + 1) edges. We add m (k + 1) new nodes, where each new node is connected to exactly & existing nodes, thus introducing k(m - (k: + 1)) new edges. Thus, any F F has at most km [k 1) edges.
Remark B.3. Maximal outerplanar graphs are 2-trees. Indeed, if we set & = 2, we recover our upper bound on the number of edges for outerplanar graphs.
Proposition B.4. Let F = {F EU C ((F) such that [0] S k and F F\U U is a forest). Then, any F E F with [V(F) = m has at most m(k + +) - 1 - [ + 3k) edges.
Proof. F A U is forest and has thus at most m k edges. Let FlU] denote the subgraph induced by vertex set U. FIU] has at most {(((k 1)) edges. Every node in FIU] is connected to at most every node FV U. Thus, any F E F has at most m -11 (k(k - 1)) + k(m k)
m(k + 1) - ] (3k + k²) many edges.
Proposition B.5. Let F denote the class of parallel trees defined in Gai et al. (2025). Then, any F E F with [V(F) = m nodes has at most 2m 3 edges.
Proof. Parallel trees, as defined in Gai et al. (2025), can be obtained by considering a tree T and replacing any edge uv E E(T) with parallel edges, that is, simple paths that share the endpoints {u, v). Assume that T has ny leaves, and denote by F a parallel tree obtained from it. If 7 (fu,v), fun]) P2. then F is a parallel edge which is a series pariallparaalel graph. Therefore, ny E [1, i.e., T is a path, F is series-parallel graph as it is obtained via series composition of series-parallel graphs; then e(F) S 2m 3. The bound can be matched by picking 7 Pr and adding leaf I and add edges (1142....,4144 I,,,, from 4 to each of the other leaves. The resulting graph is a series parallel graph with m nodes. To show this, let
2 nodes, each of them with an edge to and one v. If m4 > 2, then pick
{1....., ] and consider the ny root-leaf paths Poy of T, and each of the ny subgraphs F(J). of F that have heen obtained by replacing edges in this path with parallel edges. Each of the Fi)) is series parilllla graph. With the added edges, is now sink of F (V(F), E(F) U (1122,..., 11 }). With the root the source, F" is series parallel graph. The resulting graph has therefore at most 2m 3 edges.
B.3 PRIVACY
Corollary B.1. For any two neighboring graphs G ~ G with n nodes and for any pattern F it holds that
[tF.G) (0)))((FFF'))))) e (F)) 2c(F) n²
(17)
Proof. We consider dG,G, G*) = (G, G') discussed in Appendix A. The proof then follows
from Lemma 3.1 and Definition 3.2 by direct computation, with the reminder that ea S) = 2e(() for any S C V(G).
Proposition 4.4. Let (G) = F|
and 3 > O. Let
max S,
e -Bdoig (G.H)
m&8 H'SSsday H)
||((F. H) (FFHH')
(2)
HEG
be the B-smooth sensitivity of U(F, G) at G. Then, it holds that St,- 2 S.
Proof. Let a(H) be the vector with entries a, (H) defined by a(H)= = (HI(H),.... aa())),
a,(H) =
max H" H":dease H
[t(F,, H) - t(Fi, H.)
(18)
For any H' with dedge (H, H') < 1,
[FF H) t(F, H')l < ||(()))
(19)
18

---

Published as a conference paper at ICLR 2026
Thus, it holds that
S.(G)
max (G,H)
[t[F, H) ((FH)) +(F. H2)
(20)
HEG
H' H' HS1
max e (G, ||a(H)]l HEG
(21)
maxe ( ((H) HCG
(22)
2
||S St,r, (G),
(23)
which concludes the proof.
Theorem 4.5 (Sensitivity of homomorphism density for bounded degree graphs). Let G ~ G' be two neighboring graphs with n nodes and maximum degree Amax. For any pattern F with m nodes, it holds that
2c(F) n²
( (A max
m-2
B(F,G) ((F,))
11
Proof. Without loss of generality, let Ny E(G) and an upper bound on
E(G'). We explicitly compute t(F, G')l by counting how many homomorphisms involve wv. Note that we do not need consider homomorphisms that do not involve ue their count equal for both G and G". First, we can pick any edge of F' and map it onto wr. For this first step, we have total of 2e(F) choices, as take into account either order of the endpoints of each edge of F. We now map the remaining
2 nodes of F. A third node of F can now be mapped in a total of at most Amax ways, as most Amax nodes are adjacent to either or v. We can proceed similarly with the remaining nodes. After the first two nodes of F have been mapped, there are then a total of (Amax) ) n- ways map the remaining m nodes of F. total, there are therefore at most max) n-- counts which differ for G' and G². Taking the normalization into account, get 2e(F) max)
|((F, G) - ((F.G') <
2e( (A ym
2e(F)) (Amos) m-
For the next theorem (Theorem B.6), we first require the following lemma.
Lemma B.1. Consider multivariate Gaussian distributions N (ua, Σn) and N E1), where Σn o² and E = Then, if E (1-a) is positive definite,
Do(NuuO En) |1 [1,, E1)
(24)
a 1100 - 2 2 2 + - (1-a))or 02 2(a 1) Jas In(ae" + - a)]
(25)
Proof. Let, for shortness, (Ea)* = aEi + (1 - a) Eo. From Gil et al. (2013, Table 2), it holds that
Da(N(mo En) || [[11, Σn)) = a
(26)
det (Ea)
2 (m0 - -11 - [Ea)' (no - m1)
2(a - 1) In (det E 2-a (cet E
(27)
(**)
Note that (Ea)* = lae" + a:] 2 and therefore
a ||k00 - 11l12
(*) 2 2 + (1 (1-a]]ar 02
and
(28)
In (16* (1 a))² g2d
[ae + (1 (1-a))
(**) 2(a - 1)
2(a - 1) In
(29)
(d2dja
eoda
d
2(a 1) Jas In(ac* + - a))
(30)
which concludes the derivation.
19

---

Published as a conference paper at ICLR 2026
As our embeddings are in IR,, need to derive d-dimensional version of Theorem 3.10 for the proof of Theorem 4.6.
Theorem B.6 (tCDP with Gaussian noise in R Let f: X x R and g X - satisfy, for every pair of neighboring databases x, x, E X and for 1 Ag 2 0.
llf(x)) - f(a')ll2 ) lø(x) g(x') Ag.
(31)
Let M :2 + R.d. be the randomized mechanism defined as M(x) f(x) +N (0, e0xx) Ta). Then, M satisfies (A² d Ag 22. -ICDP.
Proof. We bound the Rényi divergence of two neighboring databases following Lemma B.1, under the conditions in Theorem B.6. Similarly to Bun et al. (2018), we consider a, S E with a<c"
1) + 2 Note first that = g(x') -xx),, as Σ = e0(t) Ia = e )-9()))((()))))))) e Ia = e'Eo. Due to the -i-iisscssszesss of g. > -Ag. We can ensure a(e" - 1) + 2 y by noting that 2 -- و N -g.. Following Bun et al. (2018), we choose y and can therefore set to get a(e" 1) + 2 a²,- 2 2 = 7.
S 2
The first term in Equation (25) is bounded as
10 p1 12 ax) 02
a
1 m1ll aA) 2
(32)
2 1ac
The second term in Equation (25) can be bounded via a Taylor expansion of the function h(s) = In lac" (1 a)). First, compute
ae
a(1 - aa)e
h(0)= = 0, h1(s) = ae + a1 N'(0) a, (s(s) = [ae" + (1 - =))
(33)
As in Bun et al. (2018), for a > 1 and a(e" - 1) + 2 it holds that 0 < (s) S a(a-1)
Considering a Taylor expansion s = 0, h(s) = as + s() for some ( E [0, 8]. and so
1 (() v a(a 1)s²
08 h(s) =
(34)
2
2y2
Thus, for = 1/2 the second term in Equation (25) reduces
d
adss
2(a (e-1) Jas h(s)] < 422
I ad
(35)
9
Equation (32) and Equation (35) together complete the proof.
Theorem 4.6. Let t(F,C G) be the homomorphism density vector for graph G and pattern set F with FF = d, o' > O, and let (G) be B-smooth upper bound to the local sensitivity per Proposition 4.4. Then, the mechanism
8(F.G) = -((F,G)+N [G).
18
(4)
2p'
(20' d- 452, 4B) -xCDP for neighboring graphs as per Definition 4.3.
Proof. Following the notation Theorem B.6, let eo(G) [St (G) and thus g(G)
2p¹
In (S]) In,,, (G)) - In(2p'). Therefore, for two adjacent graphs G G². A,
20
(g(G) - g(G') = 2 (G) - In (G.') < 23 as S., is f-smooth (Definition A.5). Setting
||t(F, G) -(,,,FFF G2) < (G) = Afea(C)/2 = As [G)1 1/2
A /20"
(G)(G) it follows
2p
that A, /2p'.
From Theorem B.6, i F, G) is thus (2p + d. 4,2 -CCDP.
20

---

C TECHNICAL DETAILS Published as a conference paper at ICLR 2026
B.4 EXPRESSIVE AND PRIVATE GRAPH REPRESENTATIONS
Theorem 4.8. Let D be a distribution on F C 9 with full support. Lel G E 9 be a graph and F (F1...., Fa) D'd be a vector of patterns. Then, the graph representation t(F.G. .) t(F, G) +N (o. [0) is rexpectation-exppesstiee and (2d + d -52,, ( )CDDP where
20'
p' > 0 and St,, (G) is ( B-smooth upper-bound on the local sensitivity of (SF If G. then E(F, G) is also expectation-compleee.
Proof. From Theorem 4.6, E(F,G) is (2p' + 46² 4.3 ).PPP.DP. From Theorem 4.1, E(F G) is F- F-expectation-expresssi and expectation-complee FG
Proposition 4.9. Consider a graph G with n nodes and let F be class of patterns. For a chosen privacy parameter p' > O, the Gaussian noise necessary to obtuin a specific privacy guarantee in Theorem 4.8 has variance o² OO ([maxFer e(F)))/n(t).
Proof. From Theorem 4.5, the local sensitivity of each pattern ((e(F)/n²). The vector-wise smooth sensitivity in Proposition 4.4 is not smaller than the largest local sensitivity and therefore (G) = O (maxFeFee(F) (n))/)). For a fixed p', the variance of the noise Theorem 4.6 is x² = ((maxFer (()eeer(((FF()))))))) e(F)))/n()
C.I EXPECTED BEHAVIOR OF AUC UNDER GAUSSIAN NOISE
For subset of our experiments, we can describe the expected behavior of the AUC for increasing amounts of additive Gaussian noise as follows.
Proposition C.I. In a binary classification setting with separable classes, the AUC curve follows the error function erf for embeddings perturbed with additive Gaussian noise.
Proof. In binary classification setting, let Co and Ci be the classes with means p4 and pi- Assume one-dimensional setting and that the classes are separated by μu points in each class are perturbed by additive noise (0, o²). the distance B between points from the two classes is B ~ (a, 20²). With these assumptions, the AUC is the probability that points are
= a > 0. If the
A not misranked and thus AUC = Pr[B > 0 (a 20 > 0] + oov where & is the Gaussian cumulative density function.
erf
20
As the private mechanism we rely on uses additive Gaussian noise, Proposition C.I applies, In practical setting, even though we may not have perfectly separated classes, we thus expect the AUC curve to roughly follow the erf function for increasing amounts of noise.
C.2 STOCHASTIC BLOCK MODEL
To highlight how different pattern classes can heavily influence classification performance, we use simple two-block stochastic block model (SBM) generate a dataset where certain pattern classes are informative while others are not. In the SBM, graphs are sampled according to a fixed, class- independent mean edge probability 9 [0, 1] and class parameter Çor which controls the bias towards same-block edges. In this dataset, up to (L1nn) factor, tree densities are unaffected by Ço and do not discriminate between classes. Instead, cycle densities depend on <T1 for a cycle with m edges and are thus able to effectively distinguish between classes. We thus expect cycles to perform significantly better than trees on this dataset, as for trees the class signal is carried only by a term that scales with 1 1/n. In fact, in the large graph limit, the result holds with no ((1nn) term: for graphons on this SBM dataset, cycles can discriminate between classes while trees cannot (see Lemma C.2).
Lemma C.1 (Homomorphism densities for SBM), Consider a graph G E G sampled from the stochastic block model (SBM) on nodes defined follows. To define the blocks, draw labels
21

---

Published as a conference paper at ICLR 2026
1/2. The probability of an edge on distinct, unordered pairs of nodes {u, u) E ((G) is defined as
8(0) E {1,-1} iid with probabilities Pr(3(u) 1 Pr(3(u) =
Pr[uv= E E(G) [] = (c)( (with u #v)).
(36)
where q [0, 1] and [cll S min(g, 1- q). We consider the class of to determined by the value of Se- For any pattern F F F with e(F) edges and [V(F) nodes it holds that
Et((F,))
Σ
(1F)-1s(!!9) O
(37)
72
SCE(F)
(s(w) even YWEV(F)
where As(w) denotes the number of edges in S that are incident to In particular, if T is tree it holds that B[t(T, G)] go(T)) ((/n)) and if Cm is cycle with m edges it holds that
Elt(Cm: G)] = n" + Se + O (1/n), where expectations are taken over the SBM sampling.
Proof. Let di (F) + V(G). Then, the homomorphism density t(F, G) can be written
t(F, G)
Z
where Z
II 1 1(())E)))E
(38)
abE
The probability of an edge in G is a function of the random variable 3. Thus, using the linearity of expectation and the law of total expectation we can write the expected homomorphism density as Eft(F, G)] = Eg pl
En Eg [5]-
Case 1: If vb is injective on nodes, then for every edge ab E(F) the nodes and are mapped distinct unordered pair {e)(), (b)} V(G.. For all pairs of nodes of G the probabilities that (b) E E(G) are then conditionally independent and can be factorized as follows.
E Z [8]
II abe a(EE(F)
Pr(()(a)b(()))) E E(G) ()
II g (+((((()))))) obE
(39)
By the distributive property, we can rewrite
2 [] = II a ((( = obEE(F)
Σ
181
II (( (40)
SCE(F)
abES
For each node w E ((F) the term NabES 3 (()()) appears exactly (s( times in each summand. It then holds that ILaees (()()))(()())) = II WeF ((b(w)))s(w)) As &b is injec- tive nodes, the random variables ((b((w)) independent and the expectation over B can be factorized as
B
Es
Σ
II WEV(F)
((v(w))
(41)
(CE(F)
(e(P)- 181
II wEV(F)
Eg ((b(w))))s())
(42)
SCE(F)
For any (()(w)) it holds that (v ss(w)] is equal to if As(w) is odd, and to otherwise. Therefore, each term in the sum is 1 if and only if As(w) is even for every node in the graph SV) If di is injective on nodes, it therefore holds that
E E[Zy]
Σ SCE(F)
qe (F))
(43)
(s(w) (WEV(F)
Case 2: If eb is not injective, some edges of F are mapped to the same unordered pair in G. There- fore, the conditional independence necessary to obtain Equation (39) does not hold. In this case, need to consider the image graph H₂ with node set (F))) < <V(F) and edge set E(H,) induced by the set of distinct, unordered pairs to which ta maps to. A similar derivation as above shows that in this case
E Z
Σ
(
(44)
SCE(H
(s(w) is (H)V(HH)
22

---

Published as a conference paper at ICLR 2026
Of the possible n² mappings v, there are n(n 11)... + 1) injective mappings. After normalization by 1/n"*, there is therefore at most a fraction of n(n 1)--((mm++ -
(2) /n +
n.
0(1/n²) - (1//n) non-injective maps. Summing over all yb leads then to the stated expected value for the homomorphism density.
The results for cycles and trees can be obtained by noting that, except for the empty set, a cycle with nodes has a single subset where every node has even degree (itself), while tree has no other subsets where every node has even degree.
Lemma C.2 (Homomorphism densities for SBM on graphons). Consider a two-block graphon de- fined in accordance to the SBM setting in Lemma C.I. Let therefore W be a graphon W : [0, 1]2 + [0, 1] defined as W (z, y) = + (es(2) (sy). with s = 1 - (1/2,1)- For a cycle Cm with m edges holds that I(Cm: W) 9" C.¹ For free T it holds that ((T, W) = =
Proof. Consider the operator associated the graphon Tw [2 1] L 1] defined as (Tw = So (xx, (y)(d From Lovász (2012, Section 7.5), this is a Hilbert-Schmide obtain that Tw
operator and thus has discrete spectrum. By direct computation, q(1, f)1 + (e(s, s's,, where 1 denotes the constant function x + 1 and (.,-) ) is the inner product on [o 1]. Thus the range of the operator is spanned by {1, 8): Tw has rank most 2 and thus most two non-zero eigenvalues. The eigenfunctions of Tw are 1 and 8 with eigenvalues & and Ce. respec- tively. As the homomorphism density for cycle C. is t(C W) E. Ag. where 2 is the k-th eigenvalue of the graphon operator (Lovász, 2012, Equation 7. 7.22). we get t(Cm, W) = q" + C." For the result for trees, we proceed by induction. Given tree T, consider leaf node with neighbor u. and denote the leaf and neighbor variables with ze and Zu- The homomorphism density of T W can be computed as (TT W) = Jp.ujwerr HabER(T) W ((xa; I[nEv(T) dx, (Lovász, 2012, Section 7.2). We can rewrite this as
Jexiveenten Lo W (are,
((T,W) W)
II W(Ta E()
II dr (45)
VEV(TM
By direct computation, we obtain for W ((z,, = lo + (Gs(a))s( = + (os(xu) Io' s(zz)dæz = q, since Io' s(x)dz = Therefore, t(T, W) = qt(T") \ {e), W) and, taking the induction step and integrating over the remaining nodes gives the result for trees, (TT, W) ((T))
Proposition C.2 (Homomorphism counts for cycles, Lovász 1967, Example 5.11). For cycle C. on m nodes, hom (Cm, G) is the trace of the m-th power the adjacency matrix of G, and therefore hom (Oms G) Ei Xp, where \1:-.., An are the eigenvalues of the adjacency matrix of G.
D EXPERIMENTS
In this section, we provide details for our experimental evaluation and present additional results.
D.1 SETUP AND DETAILS ON EXPERIMENTS
Setup and hyperparameters. In our experiments, consider different privacy budgets by choosing different values of /' E {10-8 10-5 10-5 10-1, 10-3,,5 10-3, 10-2.5 10-2,1] and set
p'/5. We upper bound the smooth sensitivities by evaluating Equation (1) up to dedge (G.G") = 6. For visualization purposes, we convert our iCDP guarantees into Oe guarantees using Lemma A.2 in Appendix A.2; (c,8)-DP guarantees are easier to interpret. We use 0 = 10-6 for all our guarantees. This choice respects the standard requirement 5 < 1/e(G) (Sajadmanesh et al., 2023) and is common choice in related literature. Our choice of 8, together with the choice of B, and the range of values of p' we experiment with allow us to obtain meaningful privacy protection and good performance for reasonable privacy budgets. In fact, privacy budgets roughly in the range (0. 10] generally understood to provide meaningful privacy protection in graph machine learning (Wu et al., 2022; Sajadmanesh & Gatica-Perez 2021), l). If not differently specified, for each dataset sample three pattern vectors F of size d 50, with the sampling
23

---

Published as a conference paper at ICLR 2026
strategy described in Welke et al. (2023). For each value of p', we perform three runs for each of the sampled pattern vectors with three different seeds, leading to a total of 9 runs. We train our models on the noisy homomorphism density embeddings, and test unseen, not noisy embeddings.
Experiments on OGBG data. For the molecular datasets, we take Amax 10 for MOLHIV, and Amax = for MOLBACE, MOL3BBP, and MOLLIPO, For each dataset we sample patterns of treewidth 1. For our classification tasks, we train on the private homomorphism densities to predict the class of unseen graphs. We consider the 1000 and 100 nearest neighbors in a nearest neighbors classifier for MOLHIV and MOLBACE, respectively. We consider 200 estimators in a random forest classifier for MOLBBBP. We evaluate the performance of our classifiers and report the classification AUC for different privacy budgets. For the regression task on MOLLIPO, we use an SVR with linear kernel and default hyperparameters from scikit-lear,, except for epsilon 0.2.
Experiments on network data. For the network datasets, we take Amax n, as there is no upper bound on the maximum degree that we can infer from domain knowledge. For each dataset we sample patterns of treewidth 1 and append node counts. We train on the private homomorphism densities to predict the class of unseen graphs. We consider the 300 nearest neighbors in nearest neighbors classifier for REDD -IADDDTT--BIAAR We consider 200 and 50 estimators in a random forest classifier for REDD ITDMI.T--T.--5- and S STARGAZERS, respectively. We evaluate the performance of our classifiers and report the classification AUC and accuracy for different privacy budgets.
Experiments on synthetic data. For the SBM dataset, we consider graphs with n = 200 nodes, and classes defined by < E f0.08, 0.16, 0.24, 0.32) described in Appendix C.2 generate 100 graphs per class. We use a Chernoff bound to estimate Amax with probability = 0.995. We use a nearest neighbors classifier and consider the 5 nearest neighbors. For cycle patterns, the homomorphism densities for graph G can be quickly computed using the eigenvalues of G' as in Proposition C.2. To consider a distribution with full support on the cycle graph patterns, one can, e.g., sample the number of nodes m with Poisson distribution and then consider all cycles with number of nodes up to m. In our experiments, we consider cycles up to m 10 nodes for total of d = 8 patterns.
Treewidth trade-off. On MOLHIV we additionally consider patterns with maximum treewidths of 2 and 3. For these results, we ensure that at least 25% of the patterns match the maximum treewidth.
Privacy attacks. To empirically test our privacy guarantees, we consider the following attack scenario. We assume a strong attacker that has access to the vector of patterns F and the original set of graphs {G]...., G. For each G2 E [GI,.... Gv J. the attacker can compute the true homomorphism density vector t(F, G.). The attacker has access to the private homomorphism densities and their goal is recover an unknown graph G from the private É(F, G)) by matching it with one of the computed t(F, G,). Concretely, we train a nearest neighbors classifier on the (noise-free) homomorphism densities and use this classifier to perform the attack. We compute the Top-1 I attack accuracy by recording whether the nearest neighbor of &( F, G) is the true graph's 's density t(F, G), which allows the attacker to identify G. We compute the Top- 10 attack accuracy by recording whether the true graph appears in the 10 nearest neighbors. This provides an empirical lower bound to the attacker's abilities, but the possibility a stronger attacker is not excluded.
Node features. To evaluate whether the inclusion of node features can be beneficial, we consider aggregated node features which do not consider the structure of the graph (i.e., which are edge- private). More specifically, we consider the following statistics on node features: mean, standard deviation, median, maximum, minimum, and sum. We evaluate both the performance of node fea- tures used as embeddings alone, and appended to the private homomorphism densities, to establish whether using the private homomorphism densities with node features leads to performance gains.
Ablation experiments. To probe the effectiveness of the homomorphisms density embeddings we conduct two ablation studies. First. to further justify choice to rely on smooth sensitivities, consider noise scaled to global sensitivities and investigate the performance of the resulting noisy homomorphisms densities the OGRG datasets. Second, we consider different values for the num-
24

---

Published as a conference paper at ICLR 2026
ber of sampled homomorphisms densities d, to investigate wether smaller larger homomorphisms density vectors can provide better performance.
Comparison with GNN baselines. We compare results with common approaches achieve edge-level DP for graph classification. As a first baseline, we use Randomized Response (RR) (Wang et al., 2016) perturb the structures of graphs and train GNN on the perturbed graphs. RR perturbs each entry of the (undirected) adjacency matrix A of a graph as follows: each entry (and vice-versa) with probability and flips it with probability 1-p. p. p e' /1 + E²) the resulting perturbed graph e-edge-DP (Wang et al., 2016). As an additional baseline, we also use the begree-preserving variant of RR (DPRR), recently proposed by Hidano & Murakami (2024). With DPRR, the nodes of the perturbed graphs keep approximately the same degree the nodes of the unperturbed graphs, which results in better performance, as well as more efficient training (Hidano & Murakami, 2024) when compared to RR. For both the RR and the DPRR baselines, we thus perturb the training graphs for our OGBG experiments and test the performance of a GIN (Xu et al., 2019) architecture for c = 1. For these experiments, rely the hyperparameters in Welke et al. (2023), not including dropout layers. Note that the notion of c-edge-DP obtained via RR/DPRR does not perfectly coincide with the smooth sensitivity framework we leverage. In addition, homomorphism density embeddings guarantee expressivity in expectation, while DP GNNs offer no formal expressivity guarantees.
Ayj is independently perturbed from a
p. That is, RR
leaves an entry in the adjacency matrix unchanged with probability
D.2 ADDITIONAL, RESULTS
In this section we present additional experimental results.
Results for OGBG data. Our experiments on MOLHIV and MOLBACE, which we display in Fig- ure show that our approach successfully obtains a private embedding which retains discrimination abilities that are comparable to that of non-private embedding (e = o.). At the same time, the at- tacker performance drastically decreases for reasonable values e, while being close to I for = co. The classification AUC follows the eπror function, empirically confirming the formal connection be- tween privacy and AUC discussed in Proposition C.I. This result is of great practical utility, as it allows to determine the maximum privacy budget for given desired AUC, and vice-versa the predicted AUC for a given privacy budget.
MOLHIV AUC and sttack accuracy
MOLBACE AUC and allack
0.75
10P
Top Accumcy
Top-10 and Top-1 Attoki Accurscy
0.70
10a4
0.7
10a0
10%
0.60
10-3
AUG
0.6
10
0.58
10a
AUG wh
AJD Riwkl
0.50
AUC
To 10 ABkAcc Tro Anc
10-4
Top-10
0.4
AJC
Top-20 AlCA
10-1
0.45
Top KS
10-3
10-2
10-3
100
10a
10a
10-2
10:2
10-1
10
(a) Classification AUC and attack accuracy vs pri- vacy budget MOLHIV with N-NN
(b) Classification AUC and attack accuracy vs pri-
vacy budget on MOLBACE with A-NN.
Figure 3: Visualizations for two of our experiments on MOLHIV and MOLBACE, We report average results with error bars of 2 standard deviations across 9 runs.
Node features. In Table 3, we can see that node features overall achieve reasonable performance. However, combining the node features with our private embeddings with 1 provides better performance. Therefore, we can render the homomorphism density embeddings more informative by additionally considering node features.
Results on network data. We also perform experiments on the network datasets BEDDAR,,,, REDDIT-MULTT--5 (Xiang al., 2024), and GitHub STARGAZERS
25

---

Published as a conference paper at ICLR 2026
Table 3: Utility and attack accuracy for our experiments on OGBG datasets. As utility metric, we use the regression RMSE for MOLLIPO and the classification AUC for MOLHIV, MOLBEBP, and MOLBACE. We include results where we concatenate node features (NF) to the private homomor- phism density embeddings. We report average results and standard deviations across 9 runs.
MOLHIV 1
MOLBBBP f
MOLBACE
MOLLIPO V
Private
Utility 0.692 (0.020)
0.602 (0.005)
0,652
(0.069)
1.086 (0.004)
(e 1)
Attack
0,003 (< 0.001)
0.025 (0.0033
0.027 (0.002)
0.011 (0.002)
Non private (e = xo)
Utility
0.745 (< 0.001)
0.644
(0.008)
0.752 (0.002)
1.055 (0.002)
Attack
0.955 (0.020)
1.000 (< 0.001)
0,990 (< 0.001)
0.992 (0.006)
Private + NF (c 1)
Utility 0.731
(< 0.001)
0.604
(0.005)
0.739 (0.005)
1.086 (0.004)
Attack 0.003
(< 0.001)
0.025 (0.003)
0.027 (0.002)
0.011 (0.002)
Non private + NF
Utility 0.750
(0.003)
0.644
(0.010)
0.739
(0.003)
1.053 (0.002)
(E= oo)
Attack
0.970 (0.024)
1.000
(< 0.001)
0.990
(< 0.001)
0.992 (0.006)
Features only
Utility 0.721 (< 0.001)
0.603 (0.002)
0.730 (< 0.001)
1.085 (< 0.001)
Table 4: Utility and attack accuracy for experiments network datasets. As utility metric, use the classification accuracy and the classification AUC for all datasets. We report average results and standard deviations across 9 runs.
REDDIT-MOLTI-51
STARGAZERS
Accuracy
0.758 0.001)
0.416 (0.021)
0,590 (0.015)
Private 1)
AUC
0.775 (0.009)
0.749 (0.014)
0.609 (0.026)
Attack
0.046 (0.016)
0.018 (0.004)
0.004 (0.001)
Accuracy
0.771 (0.031)
0.508 (0.007)
0.670 (0.003)
Non private 00)
AUC
0.844 (0.039)
0,805 (0.002)
0.729 (0.002)
Attack
0.999 0.001)
1.000 0.001)
0.959 (< 0.001)
(Rozemberczki et al., 2020), presented in Table 4. We obtain accuracy and classification AUC com- parable to those in Hidano Murakami (2024, Figure 5), showing that the noisy homomorphism density embeddings also provide good performance on larger network graphs. We remark that our embeddings include node counts and that on REDDIT-BINARY and REDDIT-MOLTI-SK node and edge counts alone achieve good performance (Schulz & Welke, 2019, Figure 1). Compared Hidano & Murakami (2024), we rely on significantly simpler and less resource-expensive classifiers. We could not reproduce the results in Hidano & Murakami (2024) due to out-of-memory errors, and we thus refer to Hidano Murakami (2024) for comparison.
D.3 ABLATIONS AND COMPARISONS WITH BASELINES
In this section, we perform additional experiments to evaluate the performance of our embeddings for different values of d, i.e., the number homomorphism densities we sample. Next, we compare our results with those obtained considering global sensitivity notion, to further motivate our choice to rely on the smaller smooth sensitivities.
Ablation on d. In Table 5, we observe that smaller embeddings. i.e., embeddings which consider fewer patterns, tend to perform worse. In particular, smaller embeddings have much higher vari- ance, their performance more heavily depends on having sampled patterns which are informative for the task.
Ablation with global sensitivity. In Table 6, we observe that private embeddings obtained by relying on global sensitivity perform significantly worse than the ones obtained relying on local sensitivity.
26

---

Published as a conference paper at ICLR 2026
Table 5: Utility for our experiments on OGBG using private homomorphisms density embeddings with varying sizes for d. Results are for 1. We report average results and standard deviations across 9 runs.
d
MOLHIV
MOLBBBP
MOLBACE 1
MOLLIPC 4
10 0.556 (0.153)
0.503 (0.070)
0.552 (0.156)
1.099 (0.001)
20
0.572 (0.129)
0,547 (0.074)
0.617
(0.134)
1.097 (0.001)
30
0.540 (0.171)
0.554 (0.036)
0.544 (0.098)
1.099 (0.001)
40
0.592 (0.089)
0.570 (0.067)
0.498 (0. 134)
1.098 (0:001)
50
0.692 (0.020)
0.602 (0.005)
0.652 (0.069)
1.086 (0.001)
Table 6: Utility for our experiments on OGBG using private homomorphism densities obtained with noise scaled using the global sensitivity of the homomorphism densities, compared that obtained with noise scaled with smooth sensitivity. We report average results and standard deviations across 9 runs for
Bold marks the best results.
MOLHIV 1
MOLBBBP t
MOLBACE t
MOLLIPO
Global sensitivity
0.492 (0.023)
0.500 (< 0.001)
0.520 (0.)33)
1.199 (< 0.001)
Smooth sensitivity
0.692 (0.020)
0.602 (0.005)
0.652 (0.069)
1.086 (0.004)
D.4 RUNTIMES
We measured the time to compute homomorphism density embeddings for MOLHIV with increasing maximum treewidth of tw = 2, and REDDIT-BINAR with tw 1. The results presented in Table 7 are averaged over seeds. The runtime of the homomorphism density computation for Iw = 1 for MOLETV is comparable to training GIN on MOLHIV for 200 epochs with the RR or DPRR baselines. The runtime of our homomorphism density computation is therefore comparable to that of existing methods, showing that approach is also competitive from a runtime perspec- tive. Once the homomorphism density vectors are computed. the training runtime itself is negligible; the embeddings are informative and provide competitive performance with simple and efficient ap- proaches such as k--N or Random Forest. We also remark that the homomorphism density approach provides expressivity guarantees which are not provided by the RR/DPRR+GIN baselines.
Table 7: Runtimes for the computation of the homomorphism density embeddings t t(F, G). and for the training of the GNN baselines for 100 epochs with 6 =1 =1. Values reported with a star (*) for RR/DPRR are obtained from Hidano & Murakami (2024). Values are reported in seconds.
Method MOLHIV
REDDIT-BINARY
tw 1
tw < 2
tw < 3 3916 (1088)
t G(F,G)
2369 (0)
2432 (52)
602 (136)
MOLHIV
REDDIT-BINALE
RR
1153 (159)
800*
DPRR
1214 (101)
200*
27


Reviews:
[{"review_id": "bu9jVy8Bni", "reviewer": "Reviewer_C4Rx", "summary": "The paper investigates the trade-off between expressivity (ability to distinguish non-isomorphic graphs) and privacy (edge-level differential privacy) in graph representation learning. It proposes using homomorphism density vectors as embeddings, adding Gaussian noise calibrated via smooth sensitivity to achieve truncated concentrated DP (tCDP) guarantees. The authors argue that expectation-expressivity is preserved because the noise is mean-zero. Experiments on OGB molecular datasets and a synthetic SBM illustrate privacy–utility trade-offs and compare against a randomized-response baseline.", "questions": "Given the strengths, I have the following concerns:\n\n1. The authors claims that \"Our embeddings match, in expectation, the expressive power of a broad range of graph neural networks (GNNs), such as\nmessage-passing and subgraph GNNs, while providing formal privacy guarantees.\" but there is no comparison with GNN-based privacy methods like ProGAP or [1]. These are widely cited and provide edge-level DP guarantees. Can the authors include these baselines?\n\n2. The paper evaluates privacy via nearest‑neighbor graph re‑identification on embeddings, ignoring stronger edge inference attacks. Why restrict to nearest-neighbor re-identification? Stronger attacks (e.g., LinkTeller) has shown non‑trivial leakage even against DP defenses for modest $\\epsilon$ or modern membership/link inference analyses for GNNs; the empirical privacy validation thus seems under‑powered. \n\n3. The sensitivity bound with degree dependence (Theorem 4.5) assumes a known max degree Δmax (e.g., fixed per dataset) or estimated (Chernoff) on synthetic data. Using estimated Δmax can itself leak information unless privatized or externally bounded, and the paper sets Δmax from data or heuristics in experiments, which is not privacy‑preserving if used to calibrate noise. This critical point is not addressed. Can the authors clarify this?\n\n4. This is subtle but very important, does the method allow private release of embedding?\n\n5. Most OGB experiments use tree patterns (tw=1), which undermines the empirical claim that “more expressive pattern classes” help under fixed privacy budgets. The brief MOLHIV experiment with small treewidth still tops out at tw=3; no cycles/graphlets on large graphs, no runtime/memory profiling of homomorphism computations, despite #P‑hardness beyond bounded treewidth. \n\n6. Blow‑up invariance of densities is acknowledged in the appendix, but because densities cannot distinguish graph blow‑ups, the completeness claims require appending |V(G)| or switching to counts; this subtle but important caveat should be explicit in the main text where expressivity claims are made.\n\n\n\n**Missing references:**\n\n*On DP graph learning:*\n\n[1]Olatunji et al. Releasing graph neural networks with differential privacy guarantees\n\n[2]Xiang et al. Preserving Node-level Privacy in Graph Neural Networks\n\n*On graph reconstruction attack:*\n\n[3]Olatunji et al. Private graph extraction via feature explanations\n\n[4]Zhou et al. On Strengthening and Defending Graph Reconstruction Attack with Markov Chain Approximation", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper addresses an underexplored intersection of privacy and expressivity in graph learning.\n- Formalizes expectation-expressivity and privacy guarantees using established DP frameworks.\n- Demonstrates basic privacy–utility trade-offs and sanity-checks the insufficiency of global sensitivity.", "weaknesses": "- Experiments mostly use tree patterns; higher treewidth and complex pattern classes are barely explored. The empirical section lacks depth: pattern classes beyond treewidth 1 are barely tested, and runtime implications of homomorphism counting (#P-hard) are not addressed.\n- No comparison to state-of-the-art DP-GNNs (e.g., ProGAP) or strong inference attacks like LinkTeller. \n- Non-private use of degree bounds ($\\Delta max$) for sensitivity calibration undermines DP guarantees. Furthermore, Δmax is estimated from data without privatization, which violates DP assumptions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "zPiqT1WiCK", "reviewer": "Reviewer_WKpZ", "summary": "This paper investigates the trade-off between expressivity and privacy in graph representation learning. The authors propose using noisy homomorphism density vectors to achieve both distinguishability and differential privacy guarantees. The theoretical part derives upper bounds on sensitivity and smooth sensitivity, while the experimental section validates the privacy–utility trade-off on the OGBG and SBM datasets.", "questions": "See weakness above.\n\n\nSince only edge-level privacy is considered, can this analysis be extended to node-level or subgraph-level differential privacy in the future?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper demonstrates rigorous logical consistency from definitions and lemmas to theorem derivations, with solid mathematical details.\n2. The proposed framework can be mapped to different GNN architectures (e.g., message-passing and subgraph-based GNNs) and allows for quantitative analysis of the trade-off.\n3. The experiments show clear performance differences across pattern classes, validating the theoretical trends.", "weaknesses": "1. It only considers edge-level DP.\n2. Experiments are conducted only on small-scale, toy-level datasets and do not demonstrate the feasibility of the approach on real-world large graphs or complex tasks.\n3. The paper lacks comparison with established DP-GNN methods such as edge-level GAP, using only a randomly perturbed GNN as the baseline.\n4. Computing homomorphism densities is computationally expensive. Please provide a detailed analysis of computational overhead.\n5. The paper is clearly written, but it appears that the authors used last year’s ICLR template.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "YBsYpGO3qZ", "reviewer": "Reviewer_hgq5", "summary": "This paper investigates the theoretical trade-off between expressivity and privacy in graph representation learning. The authors propose constructing graph embeddings using noisy homomorphism densities, where homomorphism counts are perturbed with Gaussian noise calibrated via smooth sensitivity to ensure tCDP. Experiments are conducted on several OGB molecular datasets and synthetic graphs, showing that the proposed method maintains competitive predictive performance and effectively resists privacy attacks under reasonable privacy budgets.", "questions": "see weaknesses.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. Graph privacy is an important and practically relevant research direction.\n2. The paper is relatively well-organized and logically coherent.", "weaknesses": "1. The paper emphasizes the use of homomorphism density vectors as a key tool. However, while it claims to fill the gap in understanding the interplay between expressivity and privacy in graph representation learning, it does not clearly define what this gap uniquely refers to. Prior studies (Sajadmanesh et al. 2021, 2023, 2024, as well as others) have already explored expressivity under differential privacy and aimed to design utility-preserving private graph learning frameworks.\n2. The paper focuses on edge-level privacy and graph-level tasks without explaining why this specific setting was chosen. In practice, graph privacy leakage often involves node attributes, and for edge-level privacy, link prediction tasks are crucial for comprehensive evaluation. The current setup limits the practical relevance of the work.\n3. The paper cites Lovász’s theorem (1967), which states that homomorphism counts can distinguish all non-isomorphic graphs. However, it later uses homomorphism densities, and in Remark B.1 admits that these cannot distinguish a graph from its blow-up. Although the authors propose adding “node counts” as a correction, they provide no theoretical proof that this modification preserves differential privacy guarantees or avoids leaking information about graph size. Moreover, the proposed fix only applies when graphs have different node counts—what about when they are the same?\n4. Experimental details are incomplete. For instance, the paper sets $δ=10^{-6}$, $β=ρ'/5$, and $d=50$, but does not justify these choices or explain their sensitivity.\n5. Experiments are limited to OGB molecular graphs and synthetic graphs, lacking evaluation on other types of graph data such as social networks (large, sparse) or medical graphs (sensitive node attributes). Since molecular graphs are relatively regular, the effectiveness of the proposed method on structurally complex graphs remains unverified, reducing generalizability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "rPifNmXuru", "reviewer": "Reviewer_dNzD", "summary": "The paper studies the trade-off between privacy and expressivity in graph representation learning. It proposes using homomorphism density vectors as graph embeddings to achieve both expressive power and formal privacy guarantees. The paper derives the trade-off in two parts: firstly, if homomorphism density vectors are used as graph embeddings, then with any noise added to them, in expectation, they will achieve expressiveness. Secondly, it proposed to use a $\\beta$-smoothing sensitivity bound and leverage Gaussian noise to achieve tCDP. Extensive theoretical and experimental results are conducted to highlight and illustrate the advantage of using homomorphism density vectors as embeddings.", "questions": "- In line 206, why is the sensitivity of Theorem 3.10 a local sensitivity if the neighboring database is considered across the input domain?\n- By the definition of F-expectation-expressivity and Expectation-completeness, what are the $X$ for your analysis and proposed method?\n- By expectation w.r.t $X$, the F-expectation-expressivity and Expectation-completeness have to consider all of the possible inputs of the input space? Then, can you elaborate on how to use this expectation in your expressivity guarantee?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Provide a strong theoretical guarantee for the expressivity and privacy of graph representation learning.\n- The experimental results highlight the validity and soundness of the theoretical claims.\n- The proposed method has been proven to be useful through experimental results and is robust against attacks.", "weaknesses": "- The privacy guarantee is provided for local sensitivity. Although it is demonstrated that very similar graphs can still be distinguished by the noisy homomorphism density vectors, the privacy guarantee does not meet the DP standard. \n- The expressivity guarantee is analyzed in expectation, which is orthogonal to the privacy analysis. Since the DP noise is only added once, the expressivity will be biased to that sampled noise, leading to the degradation of the guarantee.\n- Some of the critical theoretical annotations are provided in the Appendix, making it hard to follow the flow of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)