Federated Classification in Hyperbolic Spaces via Secure Aggregation of Convex Hulls
Authors: Saurav Prakash
Jin Sima
Chao Pan
Eli Chien
Olgica Milenkovic
Venue: Accepted by TMLR ()

Abstract: Hierarchical and tree-like data sets arise in many relevant applications, including language processing, graph data mining, phylogeny and genomics. It is known that tree-like data cannot be embedded into Euclidean spaces of finite dimension with small distortion, and that this problem can be mitigated through the use of hyperbolic spaces. When such data also has to be processed in a distributed and privatized setting, it becomes necessary to work with new federated learning methods tailored to hyperbolic spaces. As an initial step towards the development of the field of federated learning in hyperbolic spaces, we propose the first known approach to federated classification in hyperbolic spaces. Our contributions are as follows. First, we develop distributed versions of convex SVM classifiers for Poincar\'e discs. In this setting, the information conveyed from clients to the global classifier are convex hulls of clusters present in individual client data. Second, to avoid label switching issues, we introduce a number-theoretic approach for label recovery based on the so-called integer $B_h$ sequences. Third, we compute the complexity of the convex hulls in hyperbolic spaces to assess the extent of data leakage; at the same time, in order to limit the communication cost for the hulls, we propose a new quantization method for the Poincar\'e disc coupled with Reed-Solomon-like encoding. Fourth, at the server level, we introduce a new approach for aggregating convex hulls of the clients based on balanced graph partitioning. We test our method on a collection of diverse data sets, including hierarchical single-cell RNA-seq data from different patients distributed across different repositories that have stringent privacy constraints. The classification accuracy of our method is up to $\sim11\%$ better than its Euclidean counterpart, demonstrating the importance of privacy-preserving learning in hyperbolic spaces. Our implementation for the proposed method is
available at \url{https://github.com/sauravpr/hyperbolic_federated_classification}.

Published in Transactions on Machine Learning Research (01/2024)
Federated Classification in Hyperbolic Spaces via Secure Ag- gregation of Convex Hulls
Saurav Prakash
swwnop2@@illnoossco edu
Department of Electrical and Computer Engineering University of Ilinois Urbona Champoign
Jin Sima
jsimathilknois. edu
Department of Electricnl and Computer Engineering University of Blinois Urbana Champoign
Chao Pan
chaopan2@ilinoiss.com
Depariment of Electrical and Computer Engineering University of Illmois Urbana Champaign
Eli Chien
ichien3@rllinoii.. edu
Department of Electrical and Computer Engineering University of Illinois Urbana Champaign
Olgica Milenkovic
mälenkon@illinois.oomm edu
Department of Electrical and Computer Engineering University of Blinois Urbena Champoign
Reviewed on OpenReview: https: // openreview. net/ forum? id= fMgggDfMhha
Abstract
Hicrarchical and tree-like data sets arise in many relevant applications, including language processing, graph data mining, phylogeny and genomics. cannot be embedded into Euclidean spaces of finite dimension with small distortion, and that this problem can be mitigated through the use of hyperbolic spaces. When such data also has to be processed in distributed and privatized setting, it becomes necessary to work with new federated learning methods tailored to hyperbolic spaces. As an initial step towards the development of the field of federated learning hyperbolic spaces, we propose the first known approach to federated classification in hyperbolic spaces. Our contributions are follows. First, we develop distributed versions of convex SVM classifiers for Poincaré discs. In this setting, the information conveyed from clients to the global classifier are convex hulls of clusters present individual client data. Second, to avoid label switching issues, we introduce a number-theoretic approach for label recovery based the so-called integer B₁ sequences. Third, we compute the complexity of the convex hulls in hyperbolic spaces to assess the extent of data leakage; at the same time, in order to limit the communication cost for the hulls, we propose a new quantization mothod for the Poincaré disc coupled with Keedd-Sloomn--ikee encoding. Fourth, at the server level, we roduce new approach for aggregating convex hulls of the clients based on balanced graph partitioning. We test method on collection of diverse data sets, including hierarchical single-cell RNA-seq data from different patients distributed across different repositories that have stringent privacy constraints. The classification accuracy of our method is up to ~ 11% better than its Euclidean counterpart, demonstrating the importance of privacy-preserving learning in hyperbolic spaces. Our implementation for the proposed method is available at attps://gg htwggtttu..... com comm///uuraayr//rrprbbllccc ftl.eerttdddlllsssfiiiiaalaa.a classificationn
known that tree-like data
"Sauray Jin, and Chao contributed equally this work.

---

Published in Transactions on Machine Learning Research (01/2024)
1 Introduction
Learning in hyperbolic spaces, which unlike flat Euclidean spaces are negatively curved. is a topic of significant
interest in many application domains (Ungar 2001
Vermeer 2005 Hitchman 2009
Nickel & Kiela 2017
2018: Cho et al. 2019 Liu et al. 2019 Chami et al, Pan et al., 2023a]. j. In particular, data embedding and lcarning in hyperbolic spaces has been investigated in the context of natural language processing (Dhingra ct al. 2018), graph mining (Chen et al. 2022] : phylogeny (Hughes et al. 2004 JJiag et al. (0022), and genomic data studies (Raimundo et al.] 2021 Pan et al. 2023a). The fundamental reason behind the use of negatively curved spaces is that hierarchical data sets and tree-like metrics can be embedded into small- dimensional hyperbolic spaces with small distortion. This is a property not shared by Euclidean spaces, for which the distortion of embedding N points sampled from a tree-metric is known to be (loggN) (Bourgain 1985 Linial et al.) 1995
Tifrea et al. 2019: Ganea et al. 2018 Sala et al.
2020b; Tabaghi& & Dokmanić, 2021] Chien et al., 2021
In the context of genomic data learning and visualization, of special importance are methods for hyper- bolic single-cell (sc) RNA-seq (scRNA-seg) data analysis (Luecken Theis, 2019; Ding & Regev 2021;
Klimovskaia et al.] 2020 Tian et al. 2023). Since individual cells give rise to progeny cells of similar prop- erties, scRNA-scq data tends to be hicrarchical; this implies that for accurate and scalable analysis, it is desirable to embed it into hyperbolic spaces (Ding & Regev] 2021] Klimovskaia et al. 2020 Tian et al. 2023). Furthermore, since scRNA-seq data reports gene activity levels of individual cells that are used in medical research, it is the subject of stringent privacy constraints sharing data distributed across different institutions is challenging and often outright prohibited. This application domain makes compelling case for designing novel federated learning techniques in hyperbolic spaces.
Federated learning (FL) is a class of approaches that combine distributed machine learning methods with data privacy mechanisms (McMahan et al., 2017; Bonawitz et al., 2017 Sheller et al. 2020 Kairouz et al,, 2021 Pichai 2019 Li ct al. 2020b). FL models are trained across multiple decentralized edge devices (clients) that hold local data samples that are not allowed to be exchanged with other communicating entities. The task of interest is to construct a global model using single- or multi-round exchanges of secured information with a centralized server.
We take steps towards establishing the field of FL in hyperbolic spaces by developing the first known mech- anism for federated classification on the Poincaré disc, a two-dimensional hyperbolic space model (Ungar 2001 Sarkar 2012). The goal of our approach is to securely transmit low-complexity information from the clients to the server one round to construct a global classifier at the server side. In addition to privacy concerns, "label switching" is another major bottleneck in federated settings. Switching arises when local labels are not aligned across clients. Our FL solution combines, for the first time, learning methods with specialized number-thcoretie approaches to address label switching issues. It also describes novel quantiza- tion methods and sparse coding protocols for hyperbolic spaces that enable low-complexity communication based on convex hulls of data clusters. More specifically, our main contributions are as follows.
We describe a distributed version of centralized convex SVM classifiers for Poincaré discs CChien et al. 2021) which relies on the use of convex hulls of data classes for selection of biases of the classifiers In our solution, the convex hulls are transmitted in commuuicationn-fficienn manner to the server that aggregates the convex hulls and computes an estimate of the bias to be used on the aggregated (global) data.
We perform the first known analysis of the expected complexity of random convex hulls of data sets in hyperbolic spaces. The results allow us to determine the communication complexity of the scheme and to assess its privacy features which depend on the size of the transmitted convex hulls. Although convex hull complexity has been studied in-depth for Euclidean spaces (see Peled 2011) and references therein), counterparts are currently known for negatively curved spaces.
We introduce a new quantization method for the Poincaré disc that can be coupled with Reed-Solomon- like centroid encoding (Pan et al., 2023b) to exploit data sparsity in the private communication sctting, This component of our FL scheme required because the extreme points of the convex hulls have to be quantized before transmission due privacy considerations.
2

---

Published in Transactions on Machine Learning Research (01/2024)
Clients
(b)
fel
(d)
Labeling
(4)
Convor
Nonempty Bins
Hirwcchcal Data
Codees
Server
(+)
Secure Bewd-Sllaman- Like Codling & Transmission
Labeling Kovempty Bies
Correce
Codees
Acpregation Label Resolution via Bh decoding
Graph Based Grouping Pointsets Computation Global Hyperbalic Classiffer
Diagram of the hyperbolic federated classification framework in the Poincaré model of a hyperbolic space. For simplicity, only binary classificrs for two clients are considcrod. (a) The clients embed their hierarchical data sets into the Poincaré disc. (b) The clients compute the convex hulls of their data to convey the extreme points to the server. (c) To efficiently communicate the extreme points, the Poincaré disc is uniformly quantized (due to distance skewing on the disc, the regions do not appear to be of the same size). (d) As part of the secure transmission module, only the information about the corresponding quantization bins containing extreme points transmitted via Reed-Solomon coding, along with the unique labels of clusters held by the clients, selected from integer B₁ sequences (in this case, h = since there are two classes). (e) The server securely resolves the label switching issuc via Bz-decoding. (f) Upon label disambiguation, the server constructs complete weighted graph in which the convex hulls represent the nodes while the edge weights equal w(:;) = 1/d(;-"), where d(:,:) denoles the average pairwise hyperbolic distance between points in the hulls. The server then performs balanced graph partitioning to aggregate the convex hulls and arrive at "proxies" for the original, global clusters. (g) Once the global clusters are reconstructed, reference point (i.c., "bias" of the hyperbolic classifier), p, is computed as the midpoint of the shortest geodesic between the convex hulls, and subsequently used for learning the "normal" vector w of the hyperbolic classifier.
Figure 1:
Another important contribution pertains a number-theoretic scheme for dealing with the challenging label switching problem. Label switching occurs due to inconsistent class labeling the clients and prevents global reconciliation of the client data sets at the server side. We address this problem through the use of B₁, sequences (Halberstam & Roth 2012), with integer parameter h 2 2. Each client is assigned labels selected from the sequence of B2 integers which ensures that any possible collection confusable labels can be resolved due to the unique h-sum property of B₁, integers. The proposed approach is not restricted to hyperbolic spaces and can be applied in other settings as well.
To facilitate classification at the server level after label disambiguation, propose new approach for (secure) aggregation of convex hulls of the clients based on balanced graph partitioning (Kernighan & Lin 1970
An illustration of the various components of our model is shown in Figure 1
The performance of the new FL classification method is tested on a collection of diverse data sets, including scRNA-seq data for which we report the classification accuracy of both the FL and global (centralized) models. The results reveal that our proposed framework offers excellent classification accuracy, consistently exceeding that of Euclidean FL learners.
It is also relevant to point out that our results constitute the first known solution for FL of hierarchical biological data sets in hyperbolic spaces and only one of a handful of solutions for FL of biomedical data
(with almost all prior work focusing on imaging data (Dayan al. 2021 Ricke al. 2020 Mushtaq al.
2022 Gazula al.] 2022
Saha et al. 2022
3

---

Published in Transactions on Machine Learning Research (01/2024)
2 Related Works
Learning in Hyperbolic Spaces. There has been significant interest in developing theoretical and algo-
rithmic methods for data analysis in negatively curved spaces, with representative (but not exhaustive)
sampling of results pertaining to hyperbolic neural networks (Ganea et al. 2018 Peng et al. 2021
Liu
let al. 2019 Zhang et al. 2021 embedding and visualization in hyperbolic spaces (Nickel & Kiela 2017)
learning hierarchical models in hyperbolic spaces (Nickel & Kiela, 2018 Chami et al.]
2020a);
Lree- metri
denoising (Chien et al., 2022; computer vision (Khrulkov et al. 2020 Klimovskaia et al.)
2020 Fang et al,
2021); Procrustes analysis (Tabaghi & Dokmanne (021); and most relevant to this work,
single-cell expres-
sion data analysis (Klimovskaia et al.) 2020; Ding & Regev 2021). hyperbolic clustering
(Xavier 2010) and
classification (Cho et al., 2019 Chen et al. 2020 Chien et al. 2021 Tabaghi et al., 2021 Pan et al. 2023a
With regards to classification in hyperbolic spaces, the work (Cho et al.) 2019) initiated the study of large- margin classifiers, but resulted in nonconvex formulation for SVMs. This issue was addressed in (Chien et al. 2021) by leveraging tangent spaces; however, the method necessitates careful selection of the bias of classifiers, which is a nontrivial issue in the federated setting. In our work we also introduce novel quantization scheme that is specially designed for Poincaré disc, which is distinct from the "tiling-base based models" proposed in (Yu & De Sa, 2019).
Federated Classification. Classification has emerged an important problem for FL. Several strategies
were reported in (McMahan et al. 2017; Zhao et al.) 2018 Li et al.) 2020c;
Karimireddy et al. 2020 Kairouz
itt al.
2021 Niu et al.] 2023 Elkordy et al.) 2022 Prakash et al., 2020b a Babakniya et al. 2023 Prakash
ct al. 2020c with the aim to address the pressing concerns of privacy protection, non-identically distributod
data, and system heterogeneity inherent in FL. In order to further alleviate the communication complexily
of the training procedure, one-shot federated classífication (Zhou et al. 2020 Li et al. 2020a; Salehkaleybar
ltt al. 2021) was introduced to enable the central server to learn a global model over a network of federated devices within a single round of communication, thus streamlining the process. Despite these advances in federated classification, the intricate nature of hyperbolic spaces presents a unique challenge for the direct application of off-the-shelf FL methods. To the best of our knowledge, our work is the first one to explore specialized federated classification techniques for learning within this specific embedding domain. Notably, there are two recent papers on Riemannian manifold learning in FL setting (Li & Ma 2022; Wu el al. 2023 While hyperbolic spaces are Riemannian manifolds, our work aims to formulate the hyperbolic SVM classification problem as a conver optimization problem that solvable through Euclidean optimization methods. In contrast, Li & Ma 2022) and Wu et al. (2023) emphasize the extension of traditional Euclidean optimization algorithms, such as SVRG, to Riemannian manifolds within the FL framework. Thus, our focus is more on a new problem formulation, while Li & Ma (2022) and Wu et al. (2023) primarily address the optimization procodures. Furthermore, due to label switching, these optimization procodures are not directly applicable to our problems.
FL for Biomedical Data Analysis. Biomedical data is subject to stringent privacy constraints and it is imperative to mitigate user information leakage and data breaches (Cheng & Hung 2006; Avancha et al. 2012). FL has emerged as a promising solution to address these challenges (Dayan et al. 2021: Mushtag et al. 2022 Gazula et al. 2022; Saha et al. 2022). especially in the context of genomic (e.g., cancer genomic and transcriptomic) data analysis (Rieke et al. 2020 Chowdhury et al. 2022), and it is an essential step towards realizing a more secure and efficient approach for biological data processing. For FL techniques in computational biology, instead of the classical notions of (local) diffcrential privacy (Dwork et al., 2014),, more adequate notions of privacy constraints are needed to not compromise utility. We describe one such new notion of data privacy based on quantized minimal convex hulls in Section
In what follows, we first provide review of basic notions pertaining to hyperbolic spaces and the corre- sponding SVM classification task.
3 Classification in Hyperbolic Spaces
The Poincaré ball model RRtcliffe et al., 1994) of hyperbolic spaces is widely used in machine learning and data mining research. In particular, the Poincaré ball model has been extensively used to address classification problems in the hyperbolic space (aanea et al. 2018 Pan et al. 2023a
4

---

Published in Transactions on Machine Learning Research (01/2024)
We start by providing the relevant mathematical background for hyperbolic classification in the Poincaré ball model. Formally, the Poincaré ball By is a Riemannian manifold of curvature -k (where k > 0), defined as BE = fx E R k|| < 1}. Here and elsewhere, ||-I| and (:-)) stand for the &2 norm and the standard inner product, respoctively. For simplicity, we consider lincar binary classification tasks in the two-dimensional Poincaré disc model BBg where the input data set consists of N data points {( Wy)] with features B E K and labels yj [-1,+1),5 1,...,,, N. Our analysis can be easily extended to the multi-class classification problem and for the general Poincaré ball model in straightforward manner.
To enable linear classification generalizes the notion of a hyperplane in Euclidean space. It has been shown in (Ganea et al. 2018) that such a generalization can be obtained via the tangent space T, which is the first order approximation of the Poincaré disc at point p E B- The point p is commonly termed the "reference point" for the langent space Tp Any point æ E B2 can be mapped to the tangent space Tp as tangent vector v logp via the logarithmic map (-) B + T, Conversely, the inverse mapping is given by the exponential map expp()) B - B. These two mappings are formally defined as follows:
the Poincaré disc, one needs to first define a Poincaré hyperplane, which
v logp(a)) 1 - k||p|12
(-p) 3k P E B x B
tanh (anh"((kl((ppp @x æll) [1(-p) p) Bn æil
(1)
Vk
/ l: p|? Vkllu p E R2 v E 7.
cxpp(v)= =p + tannh
(2)
Here, O₁ stands for Möbius addition in the Poincaré ball model, defined as
(1 + 2x, 8) + k| y 12 )ax (1 k: b||=|1?)
x D
Vz, y E B
(3)
2k y) + k. 1| 12
Furthermore, the distance between x E B and y E B is given by
2
da d tanh (VK[((-) @x yll).
(4)
The notions of reference point p and tangent space T allow one to define Poincaré hyperplane as Hw,p (ar B ((-p Dg æ), w) = 0) 0)=(2: x E B (log,(x), (x)) w) 0),
where w E TB denotes the normal vector of this hyperplane, resembling the normal vector for Euclidean hyperplanc. Furthermore, as cvident from the first of the two cquivalent definitions of a Poincaró hyperplanc, the reference point p E Hw,p resembles the "bias term" for Euclidean hyperplane.
SVM in Hyperbolic Spaces: Given Poincaré hyperplane as defined in (5) one can formulate linear classification problems in the Poincaré disc model analogous to their counterparts in Euclidean spaces. Our locus is on hyperbolic SVMs, since they have convex formulations and broad applicability (Pan et al. 2023a As shown in (Pan et al.] 2023a), solving the SVM problem over B2 equivalent to solving the following convex problem:
min wER2
|/1 s.l. yy (logp (z,,), w) 2 Vj E [N].
(6)
The hyperbolic SVM formulation in 66 is well-suited to two well-separated clusters of data points. However, in practice, clusters may not be well-separated,, which case one needs to solve the convex soft-margin SVM problem
N + A
min 3
20
Σ
max (0. yy (x,) w)).
For solving the optimization problems and one requires the reference point p. However, the reference point is not known beforehand. Hence, one needs to estimate "good" p for given data set before solving
5

---

Published in Transactions on Machine Learning Research (01/2024)
the optimization problem that leads to the normal vector w. To this end, for linearly separable data sets with binary labels, it can be shown that the optimal Poincaré hyperplane that can correctly classifier all data points must correspond to a reference point p that does not fall within either of the two convex hulls of data classes, since the hyperplanc always passes through p. Convex hulls in Poincaré disc can be defined by replacing lines with geodesics in the definition of Euclidean convex hulls (Ratclifle et al. 2006).
To estimate the reference point p in practice, a heuristic adaptation of the Graham scan algorithm Graham 1972) for finding convex hulls of points in the Poincaré disc has been proposed in (Pan et al. 2023a
Specifically, the reference point is generated by first constructing the Poincaré convex hulls of the classes labeled by +1 and 11, and then choosing as the geodesic midpoint of the closest pair of extreme points (wrt the hyperbolic distance) in the two convex hulls. The normal vector w is then determined using (6) or (7)
Next, we proceed to introduce the problem of federated hyperbolic SVM classification, and describe an end-to-end solution for the problem.
4 Federated Classification in Hyperbolic Spaces: Problem Formulations and Solutions
As described in Soction 1 our proposed approach is motivated by canomic/multionii data analysis, since such data often exhibits hierarchical structure and is traditionally stored in a distributed manner. Genomic data repositories are subject to stringent patient privacy constraints and due to the sheer volune of the data, they also face problems due to significant communication and computational complexity overheads.
Therefore, in the federated learning setting corresponding to such scenarios, one has to devise a distributed classification method for hyperbolic spaces that is privacy-pin prenecciipeervinggg and allows for efficient client-server communication protocols. Moreover, due to certain limitations of (local) differential privacy (DP), particu- larly with regards to biological data, new privacy constraints are required. DP is standardly ensured through addition of privacy noise, which is problematic because biological data is already highly noisy and adding noise significantly reduces the utility of the inference pipelines. Furthermore, the proposed privacy method needs to be able to accommodate potential "label switching" problems, which arise due to inconsistent class labeling at the clients, preventing global reconciliation of the clients' data sets at the server side.
More formally, for the federated model at hand, we assume that there are L 2 2 clients in possession of private hierarchical data sets. The problem of interest is to perform hyperbolic SVM classification over the union of the clients' data sets at the FL server via selection of suitable reference point and the corresponding normal vector. For communication efficiency, we also require that the classifier be learned in a single round of communccttin from the clients to the server. We enforce this requirement since one-round transmission ensures a good trade-off between communication complexity and accuracy, given that the SVM classifiers only use quantized convex hulls.
In what follows, we present the main challenges in addressing the aforementioned problem of interest, along- side an overview of our proposed solutions.
1. Data Model and Poincaré Embeddings. We denote the data set of client i which is of size Mj by tuples z = {zigs بر for i E (1, (1...., L}. Here, for E (1.....), žijj E Rd stands for the data points of client i, while Viy denotes the corresponding labels. For simplicity, we assume the data sets to be nonintersecting (i.e., ( n Z = 0, vi # j. meaning that no two clients share the same data with the same label) and generated by sampling without replacement from an underlying global data set Z.
Client first embeds ( into B& (sce Figure (a)) to obtain ( = { B2L 1=1 To perform
the embedding, one can use any of the available methods described in (Sarkar 2012 Sala et al.) 2018 Skopek et al. 2020 Klimovskaia et al. 2020 Khrulkov el al., 2020 Sonthalia. & Gilbert, 2020 Lin el al. 2023). However, an independent procedure for embedding data points at each client can lead to geometric misalignment across clients, as the embeddings are rotationally invariant in the Poincaré disc. To resolve this problem, one can perform a Procrustes- based matching of the point sets X(1,, (0,ie E {1...., L} in the hyperbolic space (Tabaghi & Dokmanić 2021). Since Poincaré embedding procedures are not the focus of this work, we make the simplifying modelling assumption that the point sets x = = E B B i e (1,....I.) I.) are sampled from global embedding over 2 Although such an embedding uses the
6

---

Published in Transactions on Machine Learning Research (01/2024)
whole data set and may hence not be private, it mitigates the need to include the Procrustes processing into the learning pipeline.
2. Classification at the Client Level.
When performing federated SVM classification in Euclidean spaces, each client. trains its own SVM classifier over its local data set; the server then "averages" the local models to obtain the global classifier (McMahan et al. 2017). It is not straightforward to extend such a solution to hyperbolic spaces. Particularly, the averaging procedure of local models is not as simple as FedAvg in Euclidean spaces due to the nonalline operations involved in the definition of Poincaré hyperplane 5
We remedy the problem of aggregating classifier models at the server side by sending minimal convex hulls of classes instead of classifier models. A minimal convex hull is defined as follows.
Desinition 1. (Minimal Poincaré convex hull) Given a point set D of N points in the Poincaré disc, the minimal convex hull CD( S D is the smallest nonredundant collection of data points whose convex hull contains all points in D.
In this setting, client i, for E 4}, computes the minimal convex hulls CHς and ( of x and x respectively, as illustrated in Figure (b). Here, x and x denote the point sets of the client's local classes with labels +1 and - respectively. To find such convex hulls, we devise a new form of the Poincaré Graham scan algorithm and prove its correctness, and in the process establish computational complexity guarantees as well. For detailed result statements, see Section 5.1 This approach is motivated by the fact that for the server to compute& a suitable global reference point, it only needs to construct the convex hulls of the global clusters.
(0)
In the ideal scenario where all local labels are in agreement with the global labels and where no additional processing is performed at the client's side (such as quantization), the minimal convex hulls of the global clusters equals CH(U x()) and CH(UL x()). Furthermore, the minimal con- vex hulls of the global and local clusters are related as C = CH(L[CC(X(()) and As a result, each client can simply communicate the extreme points of the local convex hulls to the server; the server can then find the union of the point sets belong- ing to the same global class, construct the global minimal convex hulls and find a global reference point p.
CH(U,
x(0)
This ideal setting does not capture the constraints encountered in practice since a) the extreme points of the convex hulls have to be quantized to ensure efficient transmission; b) the issue of label switching across clients has to be resolved; and c) secure aggregation and privacy protocols have be put in place before the transmission of local client information.
Poincaré Quantization. To reduce the communication complexity, extreme points of local convex hulls are quantized before transmission to the server. In Euclidean spaces, one can perform grid based quantization, which ensures that the distance between pairs of points from arbitrary quantization bins are uniformly bounded. To meet a similar constraint, we describe next the quantization criterion for B..
Definition 2. (e-Poincaré quantization) For e <> O, quantization scheme for B2 is said to be a e- Poincaré quantization scheme for any pair of points æ and y that lie in the same quantization bin, their hyperbolic distance dy (x. y) as defined in (4) satisfies dy (2. y) S c.
To facilitate the transmission of extreme points, we develop a novel e-Poincaré quantization scheme, which we subsequently refer to as PQc(-) (for a mathematical analysis of the quantization scheme, see Section 5.2p. The P-)(-) method uses radial and angular information (akin to polar coordinates in Euclidean spaces). To bound the bins in the angular domain, we partition the circunference such that the hyperbolic length of any quantization bin along the circumference is bounded from above by e/2. Similarly, we choose to partition the radial length so that all bins have hyperbolic radial length equal to c/2. This ensures that the quantization criteria in Definition 2 is satisfied. The parameter e determines the total number of the quantization bins, and thus can be chosen to trade the quantization error with the number of bits needed for transmitting the convex hulls. Furthermore, we choose the "bin centroids (centers)" accordingly. Using the PQ.()) protocol, each client quantizes its minimal Poincaré convex hulls (() and ( to create two quantized convex hull point sets Q(6 (PQc(x) x CH(
7

---

Published in Transactions on Machine Learning Research (01/2024)
and Q (P). : x E "
The quantized convex hulls (i.e., extreme points) are also used for measuring the information leakage of the hyperbolic classification approach, as outlined in what follows.
FL is to protect the privacy of individual client data (Bonawitz et al. 2017 One of the most frequently used privacy guarantees are that the server cannol learn the local data statistics and/or identity of client based on the received information (for other related privacy criteria in federated clustering, please refer to (Pan et al. 2023b)). However, such privacy criteria is quite restrictive for classification tasks using Q and Q for E [4], as the server needs to reconstruct the hulls for subsequent processing. Hence, we consider different notion of pri- vacy, where some restricted information pertaining to local data statistics (specifically, Q! and Q for E [4], is allowed to be revealed to the server, while retaining full client anonymity.
Privacy Leakage.
major requirement
More precisely, to quantify the information leakage introduced by our scheme, we make use of the so-called e-minimal Poincaré convex hull, defined next.
Definition 3. (c-Minimal Poincaré convex hull) Given c > 0, quantization scheme (-r(-) for B and a set D of N points in the Poincaré disc, let Q = (x): æ E CH(D)) be the point set obtained by quantizing the extreme points of the convex hull of D. The e-minimal Poincaré convex hull (D) S Q is the smallest nonredundant collection of points whose convex hull contains all points in Q
To avoid notational clutter, we henceforth use "quantized convex hull" of a given point set D to refer the e-minimal Poincaré convex hull of D. Client i computes two quantized convex hulls (x{)) and (x)) by finding the minimal convex hulls of Qf" and Q respectively. We use the number of extreme points of the quantized convex hull (i.e., the complexity of the convex hull), defined next, as a surrogate function that measures privacy leakage.
Definition 4. (e-Convex hull complexity) Given E E> 0, a e-Poincaré quantization scheme (Q,(), and a set D of N points in the Poincaré disc, let Q = {+) x E CD) be the point set obtained by quantizing the extreme points in the convex hull of D. The e-convex hull complexity is the number of extreme points in the convex hull of Q, i.e., the size of (D)
We would like to point out that our notion of privacy does not rely on (local) differential privacy (DP) or information theoretic privacy. Instead, it may be viewed as a new form of "combinatorial privacy," " enhanced by controlled data quantization-type obfuscation. This approach to privacy is suitable for computational biology applications, where DP noise may be undesirable as it significantly reduces the utility of learning methods.
In addition to compromising accuracy, DP has practical drawbacks for other practical applications (Kifer & Machanavaajhalll 2011 Bagdasaryan al. 2019 Zhang al., 2022 Kan 2023). The work Bagdasaryan et al. 2019) established that DP models are more remmentl for underrepresented classes. More precisely, fairness disparity is significantly pronounced in DP models, as the accuracy drop for minority (outlier) classes is more significant than for other classes. Additionally, in many practical scenarios, meeting requirements for DP, which rely on particular assumptions about the data probability distribution, might prove challenging (Kifer & Machanavajjhalaa 2011 Zhang et. al., 2022: Kan, 2023). For instance, when database records exhibit strong correlations, ensuring robust privacy protection becomes difficult. All of the above properties that cause issues are inherent to biological (genomic) data. First, genomic data is imbalanced across classes. Second, as it derives from human patients, it is highly correlated due to controlled and synchronized activities of genes within cells of members of the same species.
To overcome the aforementioned concerns, we require that 1) the clients reveal a small as possible number of data points that are quantized (both for the purpose of reducing communication complexity and further obfuscating information about the data); 2) the server collects data without knowing its provenance or the identity of the individual clients that contribute the data through the use of secure aggregation of the quantized minimal convex hulls of the client information. To address the first requirement, we introduce a new notion of privacy leakage in Definition 4 If the number of quantized extreme points is small and the quantization regions are large, the e-convex hull complexity is small and consoquentially the privacy leakage is "small" (i.e, the number of points whose information is leaked is small). For bounds the
8

---

Published in Transactions on Machine Learning Research (01/2024)
e-convex hull complexity in hyperbolic spaces (and, consequently, the privacy leakage), the reader is referred to Section 5.3
To address the second requirement, we adapt standard secure aggregation protocols prevent the server from inferring which convex hull points belong to which client, thus hiding the origin of the data.
Clients
Nonempiy
Server
Data
Sparse Secure Reed-Solomon- Like Coding
ih Geooding
Labeling Nonempty Bins Codles
Figure 2: Proposed solution for the label switching problem. Each client has its own data set with its own set of binary labels. Upon obtaining the convex hull, the extreme points are quantized to their nearest bin-centers, and the corresponding bins are labeled with one of two integers from the B₂ sequence assigned to each client. At the server side, the values in the nonemply bins are first aggregated. Next, by the property of the B, sequence that the sum of any subset of size < h of elements in the sequence is unique, all individual labels for the bins that are shared across multiple convex hulls (such as the bins colored in purple and brown) are decoded. Therefore, the server is able to recover individual (quantized) local convex hulls, which are further processed for global labeling and reference point computation (see Figure
Label Switching. Another major challenge faced by the clients is "label switching." When performing classification in distributed manner, unlike for the centralized case, one has to resolve the problem of local client labels being potentially switched compared to each other and/or the ground truth. Clearly, the mapping from the local labels at the client level to the global ground truth labels is unknown both to the client and the server.
The label switching problem is illustrated in Figure 2 where clients use mismatched choices for assigning the binary labels {-1, }1} to their local data points. To enable federated classification, the label switching problem has to be addressed in private and communication efficient manner, which is challenging, Our proposed solution shown in Figure [] and it is based on so-called B₁ sequences. In a mutshell, B, sequences are sequences of positive integers with the defining property that any sum of S possibly repeated terms of the sequence uniquely identifies the summands (sce Scction5..4 5.4 a rigorous exposition). Each client is assigned two different integers from the B, sequence to be used as labels of their classes so that neither the server nor the other clients have access to this information. Since secure aggregation is typically performed on sums of labels, and the sum uniquely identifies the constituent labels that are associated with the client classes, all labels can be matched up with the two ground truth classes. As an illustrative example, the integers 3, 12, 20, 30, 44... form Bg sequence, since two (not necessarily distinct) integers in the sequence produce the same sum Now, if one client is assigned labels 1 (red) and 3 (green), while another is assigned 7 (bluc) and 12 (pink), then a securely aggregated label 1 + 7 = 8 (purple) for points in the intersection of their convex hulls uniquely indicates that these points belonged to both the cluster labeled 1 at one client, and the cluster labeled 7 another client (see Figure 2 right panel). Note that there are many different choices for B, sequences to be used, which prevents potential adversaries to infer information about label values and assignments.
Note that a different notion of label misalignment termed "concept shift" has been considered in prior works, including (Sattler al. 2020 Bao et al. 2023) In the referenced settings, label misalignment is result of client-specific global conditional data distributions (i.e., distributions of global labels given local feature). Label misalignments are therefore handled by grouping clients based on the similarity of thoir conditional data distributions; furthermore, different global model trained for each group of clients. In contrast, actually align labels of clients in the presence of switched labels, since for our problem,
9

---

Published in Transactions on Machine Learning Research (01/2024)
the conditional global ground truth distributions the same. Another related line of works is that of "label noise" Petety et al. (2020); Song et al. (2022), where effectively, the global label for each individual data point is assumed to be noisy, thus differing from our setting with misalignments across clients.
3. Secure Transmission. As shown in Figure (d), the number of nonempty quantization bins labeled by Bn integers is typically significantly smaller than the total number of quantization bins. As the client only needs to communicate to the server the number of extreme points in nonempty quantization bins, sparse coding protocols and secure aggregation protocols are desirable. In particular, the server should be able to collect data without knowing its provenance or the individual clients/ /users that contributed the data through the use of secure aggregation of the quantized minimal convex hulls of the client data, while ensuring that the secure transmission method is also communcattion efficient. We address this problem by leveraging a method proposed in (Pan et al. 2023b) termed Secure Compressed Multiset Aggregation (SCMA). The key idea is to use Sced-Solomoonlike codes encode information about. the identity of nonempty quantization bins and the number of extreme points in them through evaluations of low-degree polynomials over prime finite field. The bin indices represent distinct elements of the finile field (since all bins are different), while the number of extreme points in a bin represents the coefficient of the term corresponding to the element of the finite field encoding the bin (the number points in different bins may be the same).
In our FL method, we follow a similar idca, with the difference that we use the local labels (encoded using B₁ sequences) associated with the clusters to represent the coefficients of the terms, instead of using the number of extreme points. For this, we first index the quantization bins as 1, 3.... starting from the innermost angular bins and moving counter-clockwise (the first bin being at angle 0). For the quantization bins in Figure 2 the bins are indexed 1..... 64. For example, the four nonempty bins corresponding to label are indexed by 18, 21, 53, while the five non-empty green bins are indexed by 37, 44, 46, 59, The SCMA secure transmission procedure is depicted in Figure where the clients send the weighted sum of bin indices to the server so that the weights are labels of the clusters and the server aggregates the weighted sums. From the weighted sums, the server decodes the labels of all nonemply bins. The underlying field size is chosen to be greater than the number of bins. A mathematically rigorous exposition of the results provided in Section 5.5
5/ (1
+ 3 31 6) 25
5/" (1 18" +1 + 27 + 9) mod 67 = 36
S1 [5. 1. mod 67 40
2 (1-16 +1 2122 +... 3 2723 3 3125 +..+ mod
Sg (5 " mod
Encoding
Soo = (S + mod 67
(0) (0, ... L,
Decoding
5 (7 (7+219+
23* + 12 12
mod
29 (7 221 +7
12 43'
= (0, 1,0,0,8,0,7,...33 3,1,,,
(7 21 23
28
5)
Encoding
90) = 7,0, 12,,1.2.... 7, 12.
Figure 3: The encoding and decoding procedure used in SCMA for transmitting the data sets shown in Figure 2
4.
Classification at the Server. Upon receiving the information about quantized extreme points of the data classes commmicated by the clients, the server performs the following steps to construct global SVM classifier.
Label Decoding. The server uses the B₁ labels of nonempty quantization bins, which equal the aggregate (sum) of the corresponding local labels used by clients that contain data points in that quantization bin (sce Figure 2 where shared nonempty bins are indexed by aggregated labels 8(= 11=1+ 1177 and 15(= 3 12) (purple and brown respectively)). The sums of the labels for each bin are acquired during the secure transmission step. By the defining property of Bd sequences, the server correctly identifies the individual
10

---

Published in Transactions on Machine Learning Research (01/2024)
local labels that contribute to nonempty bin from their sum, as long the parameter h is larger than or equal to the number of different local labels that contribute to the bin. Therefore, h should be selected as the maximum number of classes across all clients that have at least one extreme point in the same bin. Therefore, h I 2L in the worst case since there are most 2L local classes in total. In practice, is significantly smaller (see an example for h in Figure 2 Thus, through Ba decoding, each extreme point in each quantized convex hull can be recovered; this implies that each individual convex hull can also be mmmbiguuusly recovered at the server side, as shown in Figure (e).
Remark 4.1. The above steps allow the server to recover the quantized conver hulls of the local classes at each client, without learning anything about the data provenance. More precisely, the server cannot associale the identities of the clients to the recovered conver hulls. Furthermore, the server receives only a very small number of quontized extreme points of the convex hull of the data sets at the client side, and the quantization noise may be roughly viewed as noise-privacy mechanism.
Balanced Grouping of Convex Hulls. After label decoding, the next server task involves clustering the 2T. convex hulls into groups, where each group corresponds to a global ground truth label. To solve this problem, we propose a graph-theoretic approach using information about distances between pairs of point sets in the Poincaré disc. More precisely, let the convex hulls be labeled by {l...., 2L}, and let CH() denote the ith convex hull for i E {I....,2L] 2L.. We construct a weighted complete graph GVV) with V {I...., 2L) representing the 2L convex hulls. For pair of nodes u, V, the edge- weight w(fu,e) = (d 2),, where de(u, u) is the average pairwise hyperbolic distance between points in the convex hulls (H) and CH()), i.c.,
dg(u, v) EmIecHow EmECHHo de(21,
(8)
|CHW||CH
Using the Kernighan-Lin balanced graph partitioning algorithm [Kernigann & Lin 1970), we arrive at two groups of aggregated local convex hulls. Particularly, V is partitioned into two parts, each of size L, so as to minimize the sum of the edge-weights between the two parts (i.e., the weight of the balanced cut). This in turn results in two global groups of convex hulls. These steps are shown in Figure [t). The formal description of our approach is provided in Section 5.6
Learning the Global SVM Classifier. Upon completion of the graph partitioning step, the server assigns global binary labels to the two global point sets. Then, following the procedure described in Section 8 the server constructs the global reference point Due to quantization, the server treats the reconstructed global point sets as approxinatioons/uurrgggl
for the true global ground truth clusters, and solves the optimization problem (6) or to obtain the normal vector w of the classifier. This step is shown in Figure (g). Due to the distortions in the local hulls caused by Poincaré quantization, the estimated global hulls are also distorted, as shown in Figure [gg. Hence, the performance of the trained classifier depends on the quantization size e: A smaller value of e leads to smaller convex hull distortions but larger communication overhead. In Section D we demonnstrtt through extensive simulations that the the global classifier learned using our framework performs well in practice for a relatively large range of values, both for synthetic and real data sets.
5 Detailed Explanations and Main Results
In what follows, provide rigorous algorithmic results and performance guarantees for every learning and computational step of the proposed one-shot federated SVM classification algorithm for hyperbolic spaces.
5.1 Poincaré Convex Hulls
The first step of the end-to-end solution is to construct (H()) and ( the sets of extreme points in the convex hulls of local clusters at the clients i E {1,..., L}, with local labels +1 and -1, respectively. For this purpose, we adapt the Graham scan algorithm (Graham
1972) widely used for computing convex hulls in Euclidean space. Our Graham scan is described in Alg. while the performance guarantees and complexity of the method are summarized in the next theorem.
11

---

Published in Transactions on Machine Learning Research (01/2024)
Algorithm Poincaré Graham Scan
Input: Points D (- ØN) in the Poincaré disc B b + the point in D at largest distance from the origin of B ie., [0,0].
3: Normal vector n + [ogg(o]]] log,(o) is logarithmic map in
log
Tangent vector Rn, where 0 -1] denotes the counter- clnter-clockwise rotation matrix.
Sorted data V +- for j E [N], arrange points in D based the principle angle of logo with respect to t, in ascending order. For points with the same principle angle, keep only the one with the largest norm (a;)( -. m + [). STACK [b].
for j E im] do
10: while 1en(STACK)>> and CCW(STACK]-2) STACK[-1), VD))s do
11: STACK.pop()
12: end while
13:
aTACKaapeen((V1))
14: end for
15: Return STACK
Algorithm CCW
1: Input: Points σ, t, 2 in B log,,t)) (t)
U1
log_(t]]
log (=)
3: U2 +
Iog, [=]]
Return u1 () U2 [1] u1 [1]
Theorem 5.1. Given a set D of N points in the Poincaré disc, Alg. returns CH(D) in O(N log N) time, where CD) denotes the set of extreme points the minimal conver hull of D.
Based on this result, it is easy to see that Alg. 1 has the same complexity as the Graham Scan algorithm for Euclidean spaces. The proof of Theorem 5.1 can be found in Appendix
5.2 Poincaré Quantization
Quantization is standardly used to trade-off communication overhead and accuracy of point representations. In our FL setting, quantization also enables the new label encoding and decoding procedures that resolve label switching, as well as secure aggregation during transmission.
The quantization approach for Poincaré discs exploits radial symmetry of the space. Furthermore, for a given quantization parameter > 0, it ensures that the hyperbolic distance between any two points in a quantization bin is bounded by e.
We assume that the data points are confined to region with Euclidean radius of R on the Poincaré disc, and correspondingly within hyperbolic radius of Rg- Given the curvature constant k, we let s 1/Vk. We can then relate R and Ry as follows Hitchman 2009
BH
RH in (s+ R
and R Ry
5 R
Furthermore, since the Poincaré disc is conformal, it preserves angles. Hence, we directly perform quanti- zation in the hyperbolic plane, and then map the points back to the Poincaré disc. Towards this end, we start by observing that the circumference of circle centered at origin and with hyperbolic radius ra equals
12

---

Published in Transactions on Machine Learning Research (01/2024)
Hitchman 2009
Cir(rH) = 2rs (*x)
(10)
We first partition the Poincaré disc in terms of concentric circles around the origin, and then for each such partition, we perform further radial partition.
Let Ne denote the number of angular quantization bins. Consider two points at the outer boundary of the outermost quantization bin. Then, by (10), the length along the outer boundary equals Cir(RH)) (Re)/Ne. Bounding this length by c/2, we have Ne = 2Cir (Rx)/. Clearly, the inner boundaries of the radial bins will have a length I e/2.
Next, let NRw denote the number of radial bins for any given angle. We create radial bins in such a way that their hyperbolic lengths are upper-bounded by c/2. Hence, the total number of quantization bins equals NR. nnn/e. We write On, = No 2n, where n, EiN[e,, and for f2 E [Nvml] set
122 RH-
hna =
(11)
NR
Given this notation, a quantization bin B(n, n2) is completely characterized by pn.-1 and on, in the angular domain, and h2,-1 and hn, in the radial domain, where Φo=0 and hg=0. Furthermore, any point in the bin B(ni, n2) is mapped to the bin-center n2), defined as the point that partitions the bin into four parts of the same hyperbolic radial length and angularly symmetric. As result, the angular (be(ns.22) and radial hbc(n1.m2) coordinates of the bin-center equal
Pm 1 + Uni
and hbo(ni Mmn--1 + 1tzz
Obe(n1 m2))
(12)
2
To map the results from the hyperbolic plane to the Poincaré disc, the Euclidean radius of the corresponding bin-center is obtained using (9) and its 2D projection is obtained using (bc(m),a))
As an example, consider a point æ E B% within a bin B(n1,n2). It is quantized to
c = (a cos((), a sin(
(13)
where Ç= mb)( a s(e 1)/(ei + 1) and r (0)()))2))
Using Alg. I client i E [ } quantizes the extreme points in the minimal convex hulls CH and ( to obtain the quantized point sets Q and Q Finally, to obtain the quantized convex hulls c'u and CH
(6)
(f) (sce Definition 3), the client applics Alg. on Q and Q This ensures that the quantizod convex hulls remain convex.
5.3 Convex Hull Complexity
Since the convex hull complexity depends on the distribution of the data and characterizing convex hulls in hyperbolic space is complicated, we do not have general complexity analysis for arbitrary (quantized) data distribution. Instead, we analyze the convex hull complexity assuming that the data is uniformly distributed on the Poincaré disc. It can be shown that the expected convex hull complexity, i.c., the expected number of extreme points in the convex hull of any collection of N points sampled independently and uniformly at random from the Poincaré disc equals O(N3) (see Appendix Dj. In comparison, for a two-dimensional Euclidean space, the expected convex hull complexity also equals O(NE), provided that the points are sampled independently and uniformly at random Har-Peled (2011). Furthermore, note that our scheme uses quantized extreme points of the convex hull, so that we need to find an upper bound on the e-convex hull complexity (see Definition 4 assuming that the data is uniformly distributed over the Poincaré disc. Yet, rather than directly analyzing the e-convex hull complexity, which result of constructing convex hulls, quantizing, constructing convex hulls, we have the following result that characterizes the average number of points in the minimal convex hull of N quantized points sampled independently and uniformly at random from the Poincaré disc. This result serves as an upper bound on the c-convex hull complexity. The proof of the theorem is available Appendix E Recall that this complexity value also captures the privacy leakage of each client.
13

---

Published in Transactions on Machine Learning Research (01/2024)
Theorem 5.2. Let 21,...,2N be N points uniformly distributed over Poincaré disc of radius R 8, where N is sufficiently large. Let æ1....,āy, 2n be quantized values of æ1..... .N,, obtained using the quantization rule described in (13), with parameter c c= -( for some constant c. > 0. Then, the expected number of extreme points of the minimal conver hull of ,1...., is most ((N)) when < at most O(NI-9)
when } S c S 3; and at most O( when < c.
2
5.4 Label Encoding
Due to the problem of label switching, different classes at different clients may have the same label and be confused at the server. To avoid this issue, propose encoding the class labels using B₁ sequences, defined as follows.
Definition 5. B₁ sequences (or Sidon sets of order h) are sets (sequences) of nonnegative integers such that the sums of any h (with repetitions allowed) integers from the set are all different. Formally, a sequence A {al,..., 3m 0 S 01 < 02 <... . < am: is a Bn sequence for any ii...., in E ml,...,m), the multiset (f......ipp in} can be uniquely determined based on the sum at +... + asa.
Bp sequences for h (Milenkovie et al. 2006 Kovačević & Tan 2018). For B, sequences, the question of interests is how small the mth term, am: can be, conversely, how large m can be given bound 0m It can be shown that am is at least n² since there are m possible sums of h integers in and the maximum sum 100--++-0mm--++- is at least m², Therefore, we have ham 2 m². This simple lower bound on am shows that am scales as O(m²) for fixed h. On the other hand, the work in (Bose & Chowla, 1960) provides constructions for Ba sets A where am is at most m², and this is asymptotically optimal based the lower bound on am
(Sidon sequences) have found numerous applications error-correction coding
Note that for any B₁ sequence A = {ai,..., am.. the set A' = {az - al,...,am - -ai} is also a BN set Kovacevic & Tan 2017p. Moreover, the sums a', +al, +.,,, are different for any h' S h and ii,.... iw: .......,. where d, i E (1,..., m - 1} is an element in A'. Therefore, in the following, we refer to B, sequences as a nonnegative integer set A' in which the sums of any collection of at most h elements are different.
Let F. be finite field, where q 2 max ((T+ 1)", B) is prime and B is the number of quantized bins. We construct B3 sequence A' C 1822 {ai...., )2L} over the field Ff using the approach in (Bose & Chowla, 1960) (see Appendix Gb. To encode the data, we label the quantized bins applied on the quantized convex
hull of the data with unique elements from A' As before, let CH and cHHL (1) be the quantized convex
hulls of the local data at client i, and Section 5.2
Define label vector (3) E ZB based on the sets CH4 and CH according to
02ir
if there is a/d CH but #0d c'H
within the jth bin,
(
02i-1:
if there a CHH but no /0ح c'H
within the jth bin,
a2i + a2i-1
if there is a a: E cH and a a:d E cH
within the jth bin,
0,
otherwise.
Note that there one-to-one mapping between the vector (0) and the sets CH and " To calculate a in a foderated setting, the clients need an agreement on the client labels (so that the ith client uses a2--1 or azi to label the convex hull). Note that this agreement on the client labels is not revealed to the server. Hence, the server cannot. infer the identity of the client that uses labels 02:-1 or dgs- The agreement can be performed using our decentralized agreement protocol described in Appendix
(9)
5.5 Secure Transmission
To securely communicate the quantized extreme points C and CH (6) we leverage the SCMA scheme described in (Pan et al.) (023b),, where the clients transmit the encoded version of their data such that the server only gets the aggregated data distribution of the union of local
at each client i E [L] to the server,
14

---

Published in Transactions on Machine Learning Research (01/2024)
data sets, without leaking information about the identity of individual data. The SCMA scheme encodes data into heed-Solomon type codes (Reed-Solones codes are a class of rate-optimal error- coror-correctig codes) and can be shown to be efficient both communication- and computation-wise (Pan et al. 2023b).
Recall that the labels of data class at each server are described by vector ol6) based on B,, soquences. The SCMA scheme is used to communicate the vectors v(0) I....,L. More specifically, each client
mm. to the server, where Kmar m ( "D and 5 = je D3 - + = mod 9 E [2KmanL), and zi"
EE {1, .......,.. [} communicates (5 ................................ ((i)
(() is random key uniformly distributed
over the prime field F, and hidden from the server. The keys {=) (3) Dee[))eepLLKaml are generated offline using standard secure model aggregation so that (Eie(z) ={") mod q = 0.
To decode, the server uses a Reod-Solomon-type decoder to recover the sum of the label vectors v0,, i E [L]. The server first computes the sum S = (EveLy) ) mod q. Given St, for E [2LKmar]: the server computes
the sum of labels H, = EieLz u for cach bin index [B] as follows. Since there are at most L non-zero entries Ho, the server computes the polynomial g(2) = Io.. 6.66..2. 2) using the Berlekamp- Massey algorithm (Berlekamp) 1968 Massey] 1969). Then, the server factorizes g(z) using the algorithm in (Kedlaya & Umans 2011). and linds the set (b: H3 + 0}. Finally, the server solves the system of linear
(6)
equations SJ Hi Hab for I E [2KmooL]; by viewing the H&s as unknown variables and 6'-1, where Hs + O, as known coefficients.
Once the values Hs Eiery vb ii...., dw,, N' I h such that H₂ = ai +... + aiy. using brute force, which can be done since a1..... 02L
[B], are obtained, the server retrieves the unique set of indices
is Bn sequence. Finally, the server includes the bin centroid of the bth bin into cH (i)
or CH+ if
(6)
2i 11-1 E (i1,..., inc or 2i E (61,-..,ww) .w respectively. Therefore, the server recovers the convex hulls C'H + and CH (t) for e [L] without knowing the exact identity of the clients that contributed the points.
Remark 5.3. In the proposed framework, the server can determine the points in CH and CH for E [L]. While this constitutes data privacy leakage, we emphasize again that the associated client identities for the recovered quantized boundary sets are hidden from the FL server, thus protecting the client identily. Furthermore, these shared conver hull sets contain quantized versions of the original extreme points, further reducing data privacy leakage. Additionally, as observed in Theorem 5.2 and observed from our woal-world experiments, the convex hull complerity is small.
Communication Complexity. Using the SCMA transmission protocol from Pan et al. 2023b cach client i E [Z]] communicates O max (h log L, log B)) bits to the server, where K denoles the total number of extreme points in the quantized convex hulls CH and CH (convex hull complexity) of the two local clusters at client i, h denotes the number of point collisions (the number of clients that share the same quantized point in the convex hulls of their local clusters), and B, as before, equals the total number of quantization bins. Note that the convex hull complexity (00 tends to be small in practice (which is also corroborated by our experiments on different data sets). In addition, from our experiments we observe that small values of h suffice to avoid collisions and guarantee successful decoding of the local clusters CH(i) and ( ( i [Z]. at the server side.
Computational Complexity. The encoding algorithm for the convex hulls using the SCMA protocol has complexity Log
where, as before, M, denotes the number of data points at client i.
The decoding of the aggregated labels Σie(2) (1)) in the SCMA scheme has complexity ((max,ety|(((1)) L) logg + L 4)), where q max h log L}. The brute-force decoding al- gorithm of the By labels of the convex hulls of each cluster has complexity O(T.)).
15

---

Published in Transactions on Machine Learning Research (01/2024)
5.6 Balanced Grouping of Convex Hulls at the Server
After the label decoding phase, the FL server can correctly recover the quantized convex hulls {cH @
hel and {CH" he(r], betr), albeit without knowing the global ground truth labels of these point sets. The convex hulls have to be grouped correctly to match the ground truth labels. For notational convenience, we denote the set of all quantized convex hulls by {CH hezzz), where each CH for i E [2L] is one of (CH heu or {CH(() he[[]] We construct a weighted complete undirected graph over {CH here as follows. Let G(V) be complete undirected graph with node set = (4....,2L,, where for simplicity, to represents the convex hull CH("), For a pair of nodes u, E V, the edge-weight where dg(u, v) is the average pairwise hyperbolic distance between points in the convex hulls CH() and CH as described in (8). The grouping of the clusters hE(R)) is determined by finding the minimum balanced cut on the weighted graph G, i.e.;
(3)
use v E V
v}) = 1/dg(u, vu,
S = arg min Σ SCV, WES vEV',S
3> w((u,v)),
(14)
for which we use the algorithm in Kernighan & Lin 1970 The point sets PS = Uses CH and PS2 Uiepra,s- CH are treated as the two global data point sets, and are assigned, without loss of generality, the global ground truth labels +1 and -1.
The grouping method for the convex hulls of different clusters by their global labels has complexity max,,, 51 K(hh) K(()) for the graph G construction and complexity O L) for comput- ing the balanced minimum cut on G, where denotes the number of iterations of the partitioning procedure (Keriighan & Lin 1970). We note that due to distortions introduced in the local convex hulls due to quantization, and the heuristic graph partitioning procedure used in obtaining the global clusters, provable guarantecs for the correctness of the grouping procodure are not casy to derive. Nevertheless, our proposed solution works well in practice, as demonstrated by our simulation studies of SVM classifier, Section b
5.7 Learning the SVM Classifier at the Server
As the final step, the server learns a hyperbolic SVM classifier over the labelled global point sets PSI and PS2, using the procedure described in Section 3. The global reference point p is computed the geodesic mid-point of the closest pair of extreme points in the convex hulls. The normal vector w is obtained by solving the optimization problem in 6 or as applicable.
We remark that we primarily focus on the linear SVM model. While numerous non-linear kernel SVM models have been thoroughly investigated for Euclidean classification tasks, and adapting the centralized hyperbolic SVM algorithm CChien et al. 2021 Pan et al., 2023a) to accommodate non-linear kernels is straightforward, since we have access to all data points; in the federated setting, the problem becomes significantly more complex. Here, the server is restricted from directly accessing individual data points. Instead, the server only receives aggregated local convex hulls from clients. While kernel SVM remains feasible at the server, relying solely on convex hulls might compromise the performance of the kernel SVM algorithms. Therefore, effectively integrating non-linear kernels within our current framework that relies on convex hull approaches may be challenging. On the other hand, if one could dispose of the use of convex hulls, then potentially non-linear kernels could be potentially be used, but then we would not know how to resolve the underlying data privacy issues. We believe that the combination of convex hulls and SVM represents the best current option in terms of the trade-off between privacy and the model utility.
6 Experiments
We present in what follows results from numerical studies involving multiple data sets. First, we describe the baseline algorithms used for comparative simulations. Then, we consider binary classification with synthotic data sets that are generated using a newly proposed procodure for sampling uniformly at random from the Poincaré hyperbolic disc. The most important part of the study is to demonstrate how our proposed framework can be applied for multi-label classification tasks on three real-world biological data
16

---

Published in Transactions on Machine Learning Research (01/2024)
sets. The procedure for extending our proposed framework to multi-label scenario is described in Appendix Additionally, we provide insights into the impact of quantization bin size on classification accuracy and convex hull complexity. Due to space constraints, some of the details are delegated to Appendix !
6.1 Baselines
We consider the following centralized schemes for comparative simulations. (a) Centralized Poincaré (CP)
SVM: We train the linear Poincaré SVM classifier 3 from (Pan et al.) 2023a) in a centralized way; (b)
Centralized Euclidean (CE): We train the SVM classilier in a centralized way. We also consider the following federated classification baselines: (c) Federated Poincaré (FLP): We use method from Section (d)
Federated Euclidean (FLE); We perform at the server side Euclidean SVM classification over the aggregated global convex hulls.
6.2 Synthetic Data Sets
Data generation. Our proposed pipeline comprises three main steps. First, N data points are obtained using our proposed Poincaré (radius R) uniform sampling procedure described Alg. 3 Appendix F Second, a separating hyperplane is constructed by first sampling a reference point p uniformly random at a Euclidean distance of ||p|| μf from the origin, and then sampling the normal vector w. Here, 0 < 1 denotes a scaling paramcter. Any point that is within given hyperbolic distance of y > 0 from the hyperplane removed from the data set. Third, points are labeled as positive (+) or negative (-), depending on which side of the sampled hyperplane they are on. One such example synthetic data set is shown in Figure 4
0.95.||pp| R5.
0=9.55 3R/)
0.0
0.0
-1.0
-1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
(a)
(b)
Figure 4: Synthetic data classes constructed as described in the Data generation subsection. The red point denotes the sampled reference point p. The geodesic through the red point is the ground truth hyperplane that corresponds to the sampled normal vector. In (a), set N = 20, 000, while in (b), we set N 60, 000.
Results. The results are shown in Figure 5 In the first row, we consider the impact of the choice of reference point used to generate the synthetic data on classification accuracy. As ||p|| increases, ie., as the reference point further away from the origin, the ground truth separating hyperplane is more curved in the Euclidean sense (sec the ground truth hyperplanes in Figure A for comparison). Hence, by increasing [|p]]. the performance of both CE and FLE degrades, while the Poincaré baselines achieve near 100% accuracy consistently. In the second row, we report the impact of varying the margin parameter on classification accuracy. As the margin increases, it becomes easier to learn a Euclidean classifier as the data points corresponding to different labels gradually become linearly separable in the Euclidean sense well. Hence, the performance of CE well as FLE improves with increasing 7. Furthermore, federated baselines are almost as good as their centralized counterparts, both for the settings in the first and the second row, demonstrating the offectiveness of our global hulls aggregation method, and supporting the intuition that for SVM classification, extrene points are highly informative. Finally, the third row, we report the impact of the quantization parameter classification accuracy. As expected, when is
observe that the
17

---

Published in Transactions on Machine Learning Research (01/2024)
0.001.
v=0.1,==00.
y=1.0,6
100
100.0
100.00
98.5
98.95
Assuary (80
99
Accuracy (56)
89
88.0
98
88.5
Acorany
98.85
96.0
CE
87
97.5
99.75
FLP
86
97.0
98.70
96
FLE
85
96.5
R/5
2R/5
3R/5
4R/5
R/5
2R/5
3R/5
4R/5
R/5
28/5
3A/5
4R/5
R/5
2R/5
3R/5
||lll
|p
||lll
[|]||
(a)
(b)
(c)
(d)
||||| 1R/5,
Iloli
||o||
||
100.0
100
88.5
Ansunaty (%)
99.5
99
Ascuracy (96)
88.0
Accurety
98.5
88.5
98.0
97
96
67.0
96
10
10
10
10
10"
10
10
10
10
10"
10
10"
10
(g)
(h)
||p|| 3R/S, y O. 0.01
I|ll| 3R/S, y 0.1
[P]| - 4R/S. y 0.0 01
[|]]| - 4R/5. Y 0.1
100
100
100
100
Accuracy (%6
Accunay (%6
98
Accuracy (16)
96
96
82
84
94
80
10"
10"
10"
10"
(1)
(i)
(k)
(l)
Figure 5: Classification accuracy results for the synthetic data sets. The shaded areas represent the 95% confidence interval for 10 independent trials. (a)-(d) Influence of the parameter ||p|| on the classification accuracy. (e)-(h) Influence of the margin parameter y on the classification accuracy. (i)-(1) Influence of the
Poincaré quantization parameter on classification accuracy.
small, the quantization regions are small, and hence the local quantized convex hulls that are sent from each client closely approximate the true local convex hulls, resulting in low quantization distortion and no impact on the utility. As increases, the increased distortion of the convex hulls affects the classification accuracy significantly, for both FLE and FLP schemes. In particular, the overlap between the quantized convex hulls corresponding to different labels increases as increases, making it difficult for the server learn an SVM classifier, even in the FLP mode.
Table 1: Results for biological data sets, including mean accuracy (%) and 95% confidence interval of the baselines for different data sets. The results based on 10 independent trials for each setting. The FL method with better mean accuracy is plotted in bold-faced letters.
Data aet
Labels
CP (%)
CE (%)
FLP (%)
FLE (%)
Olsson
D-7
79.17 +: 0.00
68.75 + 0.00
88.04 :: 1.41
75.00 1: 3.51
0-1
72.11 + 0.00
65.99 + 0.00
69.52 + 2.82
63.54 + 2.21
[0, 2, 3]
61.94
- 0.00
61.94
0.00
61.42
3.19
60.22
3.34
Lung-Humat
0. 1, 2,
78.52
- 0.00
70.37
# 0.00
71.15 # 5
67.19
5.98
[0, 1, 3, 4]
70.99
1 0.00
61.07
0.00
66.87
8.42
60.99
6.96
0, 2, 3,
73.33
- 0.00
67.41
# 0.00
75.19 = 1.44
71.70
3.86
1, 2, 3, 4]
69.64
1 0.00
66.07
0.00
2.10 65.00
64.11
3.73
0-3
73. 20
+ 0.00
73.51
0.00
70.23 4 4.88 4.88
68.21
+ 1.83
74.65
0.00
73.94
0.00
63.96 - 4.66
64.24
4.92
UC-Stroms]
[0, 1, 3
88. 17 - 0.00
87.39
2 0.00
87.77 - 1.51
87.57
1.24
0.00
82.29
79.67 2.64
77.86
[1, 2, 3
80.33 1 0.00
80.33
1 0.00
4.80 79.71
79.46
1. 5.18
18

---

Published in Transactions on Machine Learning Research (01/2024)
6.3 Biological Data Sets
Data sets. We consider multi-label SVM classification for three biological data sets: Olsson's scRNA A- seq data set (Olsson et al. 2016). UC-Stromal data set (Smillie et al.
data set (Vieira Braga et al., 2019) Our simulations are performed on the Poincaré embeddings of these data
2019), and
sets, which can be obtained using methods described in (Klimovskaia et al. 2020 Skopek et al., 2020). We illustrate the embeddings in Figure g which is also included in Appendix
For simulating the FL multi- label classification tasks, use subsets of data corresponding to different combinations of labels, for both the UC-Stromad and the Lung-Human Human data sets. Since the Olsson data set is quite small (it contains only 319 points from 8 classes), we consider the entire data set for multi-label classification. Detailed information about the data sets and experimental settings available in Appendix
Results. We present our results in Table | which reports mean accuracy (%) and the 95% confidence interval over 10 independent trials for all baseline setlings. We observe that FLP almost always outperforms FLE up to ~ 11%, demonstrating that learning a hyperbolic SVM classifier is preferred to simply learning a Euclidean SVM classifier. However, for UC-Stromal (Labels: [0. 1, 2.) data, FLE performs slightly better than FLP. This may be attributed to the distortion of the convex hull or particular selection of the reference point. We also observe that for the Olsson (Labels: 0- 7) and hung-Humat (Labels: [0, 2, 3, 3.) data sets, the federated baselines have better mean accuracy than their centralized counterparts D Furthermore, the performance of the federated basclines demonstrates that our convex hulls aggregation and label resolution methods indeed perform well in practice, although some of the steps do not have analytical performance guarantees. Finally, we note that for UC-Stromal (Labels: [0, 2, data, federated baselines have large gap in accuracy compared to their centralized counterparts. This is because the points lying near the decision boundarics of SVM classifiers are not well represented through the local quantized convex hulls.
2.0
2.0
2.0
2.0
1.5
1.5
1.5
1.5
1.0
1.0
1.0
0.5
0.5
0.5
0.0
0.0
0.0
-0.5
-0.5
-0.5
-1.0
-1.0
-1.0
-1.0
-0.5
0.0
0.5
-1.0
-0.5
0.0
0.5
-1.5
-1.0
-0.5
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
Figure 6: Analysis of the impact of the quantization parameter c on the convex hull distortion and complexity. The blue and green points correspond to labels O and 3 in the UC-Stromal data set. The solid lines denote the quantized convex hulls, while the dotted lines denote the actual convex hulls without quantization.
Choosing the quantization parameter c. We use UC-Stromal data set as an example to illustrate the impact of the choice of on the performance of the global classifier. In Figure t we show how quantization alfects the shape of the quantized convex hulls by considering all the data points corresponding to labels O and 3. As expected, when e increases, the shapes of the quantized convex hulls are increasingly distorted with respect to the original convex hulls. To more precisely examine the impact of quantization, we consider our prior experimental setup for labels 0 - and analyze how the accuracy and convex hull complexity changes with The results are shown in Figure 7 In (a), observe that federated schemes can suffer drop in performance when c increases above 0.1. In (b), we consider the complexity of the quantized convex hulls at the clicnts corresponding to all the four labels, and plot the average and maximum convex hull complexitics across all clients and labels. As expected, the convex hull complexity decreases when increasing e. In (c), we present the ratio of the convex hull complexity and the class size across clients and labels for different. choices of the quantization parameter E.
We find that training SVM classifiers on extremee points the convex hulls of the classes instead of the entire classes improves the performance of centralized training, both for Euclidean and Poincaré methods. We believe this be due quantization, which may act like a denoising step and improve the performance compared to centralized benchmarks. The results are included in Appendix !
19

---

Published in Transactions on Machine Learning Research (01/2024)
Accuracy 0%
60
|[Local
8
3
40
CE
FLP
6
Max Size
2
Max
Average Size
Average
10"
10
10"
10
10
10
10
10
10'
10
10"
10
10
10'
(a)
(b)
(c)
Figure 7: Impact of quantization parameter the accuracy and convex hull complexity of the UC-Stromal data set for the multi-label classification setting with labels 0-3). Here, as before, C.H denoles the quant ized convex hull of a client. Average as well as maximum complexities are calculated over all clients and across all local quantized convex hulls. The shaded areas represent the 95% confidence interval from 10 independent trials.
7 Conclusion
We introduced a novel approach to federated learning in hyperbolic spaces, thereby addressing challenges in processing hierarchical and tree-like data distributed and privacy-preserving settings. Specifically, we de- veloped an end-to-end framework for federated learning of SVM classifiers in the Poincaré disc. The key idea behind the approach it to leverage socurely aggregated convex hulls for information transfer from the clients to the server. The complexity of convex hulls is analyzed to assess data leakage, and simple quantization method is proposed for efficient data communication. We also considered detrimental label switching issues and resolved them with a new method based on mumber-theoretic and coding-theoretin ideas. Additionally, we introduced novel approach for aggregating client convex hulls using balanced graph partitioning. Ex- perimental results on multiple single-cell RNA-seq data show improved classification accuracy compared to Euclidean counterparts, establishing the utility of privacy-presee preservii learning in hyperbolic spaces.
Our work also introduced many potentially important new research questions. While information sharing via quantized convex hulls is efficient and secure, extreme points of the quantized convex hulls can contain important identifiable information about outliers, and addressing this limitation is an important problem for future work. Characterizing the impact of quantization on privacy Icakage and generalizing the privacy- preserving and communication efficient fodcrated learning protocols to other ML tasks are other questions of interest.
Acknowledgments
This work was supported by NSF CIF grant 1956384 and the CZI grant DAF2022-249217.
References
Sasikanth Avancha, Amit Baxi, and David Kotz. Privacy in mobile technology for personal healthcare. ACM Computing Surveys (CSUR), 45(1):1 54, 2012.
Sara Babakniya, Souvik Kundu, Saurav Prakash, Yue Niu, and Salman Avestimchr. Revisiting sparsity hunting in federated learning: Why does sparsity consensus matter? Transactions on Machine Learning Research, 2023.
Eugene Bagdasaryan, Omid Poursaced, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. Advonces in neural information processing systems, 32, 2019.
Wenxuan Bao, Haohan Wang, Jun Wu, and Jingrui He. Optimizing the collaboration structure in cross-silo federated learning. In International Conference on Machine Learning. PMLR, 2023.
Elwyn R. Berlekamp. Algebraic coding theory. In McGraw-Hii Hill series in systems science, 1968.
20

---

Published in Transactions on Machine Learning Research (01/2024)
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, machine
Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175-1191, 2017.
Raj Chandra Bose and Sarvadaman Chowla. Theorems in the additive theory of numbers. Technical report, North Carolina State University. Dept. of Statistics, 1960.
Jean Bourgain. On lipschitz embedding of finite metric spaces in hilbert space. Israel Journal of Mathematics, 52:46-52, 1985.
Ines Chami, Albert Gu, Vaggos Chatziafratis, and Christopher Ré. From trees continuous embeddings and back: Hyperbolic hierarchical clustering. Advances in Newral Information Processing Systems, 33: 2020a.
Tnes Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low-dimensional hyperbolic knowledge graph embeddings. arXiv preprint arXic:2005.005: 00545, 2020b.
Boli Chen, Xin Huang, Lin Xiao, Zixin Cai, and Liping Jing. Hyperbolic interaction model for hierarchical multi-label classification. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 7496 7503, 2020.
Yankai Chen, Menglin Yang, Yingxue Zhang, Mengehen Zhao, Ziqiao Meng, Jianye Hao, and Irwin King. Modeling free graphs with hyperbolic geometry for knowledge-aware recommendation. In Proceedings of the Fifteenth ACM International Conference Web Search and Data Mining, pp. 94-102, 2022.
Vivying SY Cheng and Patrick CK Hung. Health insurance portability and accountability act (hippa) compliant access control model for web services. International Journal of Healtheare Information Systems and Informatics (IJHISI), 1(1):22 39, 2006.
Eli Chien, Chao Pan, Puoya Tabaghi, and Olgica Milenkovic. Highly scalable and provably accurate clas- sification in poincaré balls. In 2021 IEEE International Conference on Data Mining (ICDM), pp. 61 70. IEEE, 2021.
Eli Chien, Puoya Tabaghi, and Olgica Milenkovic. Hyperaid: Denoising in hyperbolic spaces for trco-fitting and hierarchical clustering. arXiv preprinl arXiv:2205.0977 2022.
Hyunghoon Cho, Benjamin DeMeo, Jian Peng, and Bonnie Berger. Large-margin classification in hyperbolic space. In International Conference on Artificial Intelligence and Statistics, pp. 1832-1840. PMLR, 2019.
Alexander Chowdhury, Hasan Kassem, Nicolas Padoy, Renato Umeton, and Alexandros Karargyris. A review of medical federated learning: Applications in oncology and cancer research. In Brainlesion: Glioma, Multiple Sclerosis, Stroke, and Traumatic Brain Injuries: 7th International Workshop, BrainLes 2021, Held in Conjunction with MICCAI 2021, Virtual Event, September 27, 2021, Revised Selected Popers, Part I, pp. 3 24. Springer, 2022.
Ittai Dayan, Holger R Roth, Aoxiao Zhong, Ahmed Harouni, Amilcare Gentili, Anas Z Abidin, Andrew Liu, Anthony Beardsworth Costa, Bradford J Wood, Chien-Sung Tsai, et al. Federated learning for predicting clinical outcomes in patients with covid-19. Nature medicine, 27(10): 2021.
Bhuwan Dhingra, Christopher Shallue, Mohammad Norouzi, Andrew Dai, and George Dahl. Fmbedding text in hyperbolic spaces. In Proceedings of the Twelfth Workshop on Graph-Based Methods for Natural Lan- guage Processing (TextCraphs-12), pp. 59 69, New Orleans, Louisiana, USA, June 2018. Association for Computational Linguistics. doi: 10. 10.18653/v1, /1//://11/11111// 1708. URL
W Diffie and ME Hellman. new directions in cryptography' ieee transactions on information theory, v. il-22, n. 6. 1976.
Jiarui Ding and Aviv Regev. Deep generative model embedding of single-cell rna-seq profiles on hyperspheres and hyperbolic spaces. Nature commemications, 12(1):255: 2021.
21

---

Published in Transactions on Machine Learning Research (01/2024)
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3-4):211-40)) 2014.
Bradley Efron. The convex hull of a random set of points. Biometrika, 52 52(3-4):331-343 1965.
Ahmed Roushdy Elkordy, Saurav Prakash, and Salman Avestimchr. Basil: A fast and byssitin approach for decentralized training. IEEE Journal Selected Areas in Communications, 40(9):2694 -716, 2022.
Penglei Fang, Mehrtash Harandi, and Lars Petersson. Kernel methods in hyperbolic spaces. In Proceedings of the TERE/CVF International Conference on Compuler Vision, pp. 10665-10674, 2021.
Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. Advances in newral information processing systems, 31, 2018.
Harshvardhan Gazula, Kelly Rootes Murdy, Bharath Holla, Sunitha Basodi, Zuo Zhang, Eric Verner, Ross Kelly, Pratima Murthy, Amit Chakrabarti, Debasish Basu, et al. Federated analysis in coinstac reveals functional network connectivity and spectral links to smoking and alcohol consumption in nearly 2,000 adolescont brains. Neuroinformaties, pp. 1-15, 2022.
Ronald L. Graham. An efficient algorithm for determining the convex hull of finite planar set. Info Proc. Lett., 1:132 133, 1972.
Aric Hagberg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008.
Heini Halberstam and Klaus Friedrich Roth. Sequences. Springer Science & Business Media, 2012.
Sariel Har-Peled. On the expected complexity of random convex hulls. arXiv preprint arXiv:1111.53: 2011.
Michael P Hitchman. Geometry with an introduction to cosmic topology. Jones Bartlett Learning, 2009.
Timothy Hughes, Young Hyun, and David A Liberles. Visualising very large phylogenetic trees in three dimensional hyperbolic space. BMC bioinformatics, 5:1-6, 2004.
Yueyu Jiang, Puoya Tabaghi, and Siavash Mirarab. Learning hyperbolic embedding for phy tree placement and updates. Biology, 19):12256, 2022.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and Trends0 in Machine Learning, 14(1 2):1 210, 2021.
Kazutoshi Kan. Seeking the ideal privacy protection: Strengths and limitations of differential privacy.
Monetary and Economic Studies, 41:49-80, 2023.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for foderated learning. In International conference on machine learning, pp. 5132 5143. PMLR, 2020.
Kiran S Kedlaya and Christopher Umans. Fast polynomial factorization and modular composition. SIAM
Journal on Computing, 40(6):1767 1802, 2011.
Brian W Kernighan and Shen Lin. An efficient heuristic procedure for partitioning graphs. The Bell system lechnical journal, 49(2):291 307, 1970.
Valentin Khrulkov, Leyla Mirvakhabova, Evgeniya Ustinova, Ivan Oseledets, and Victor Lempitsky. Hyper- bolic image embeddings. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6418 6418-6428, 2020.
Daniel Kifer and Ashwin Machanavajjhala, No free lunch in data privacy. In Proceedings of the 2011 ACM SIGMOD International Conference Management of data, pp. 193 204, 2011.
22

---

Published in Transactions on Machine Learning Research (01/2024)
Anna Klimovskaia, David Lopez-Paz, Léon Bottou, and Maximilian Nickel. Poincaré maps for analyzing complex hierarchies in single-cell data. Nature communicaatins, 11(1):2966, 2020.
Mladen Kovacevic and Vincent YF Tan. Improved bounds on sidon sets via lattice packings of simplices. SIAM Journal on Discrete Mathematics, (1)3:2269-2211 2017.
Mladen Kovačević and Vincent YF Tann Codes in the space of multisets coding for permutation channels with impairments. IEEE Transactions on Information Theory, 64(7):5156-5169, 2018.
Jiaxiang Li and Shiqian Ma. Federated learning on riemannian manifolds. arXiv preprint arXiv:2206.05666 2022.
Qinbin Li, Bingsheng He, and Dawn Song. Practical one-shot federated learning for cross-silo setting. arXiv preprint xrXi::2010.01017, 2020a.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, mothods, and future directions. IEEE signal processing magazine, 37(3):50-60, 2020b.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in beterogeneous networks. Proceedings of Machine learning and systems, 2:429 450, 2020c.
la-Wei Eileen Lin, Ronald R Coifman, Gal Mishne, and Ronen Talmon. Hyperbolic diffusion embedding and distance for hicrarchical representation learning. arXiv preprint XXNi:2305518962 2023.
Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinalorica, 15:215 245, 1995.
Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. In Advances in Neural Information Processing Systems, pp. 8230 1200-8241,--1 2019.
Malte D Luecken and Fabian J Theis. Current best practices in single-cell rna-seq analysis: tutorial. Molecular systems biology, 15(6):88746, 2019.
James Massey, Shift-register synthesis and bch decoding, IEEE transactions on Information Theory, 15(1):
122-127, 1969.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communicttion-effiienn learning of deep networks from decentralized data. Tn Artificial intelligence and statistics, pp. 1273-1282. PMLR, 2017.
Olgica Milenkovic, Navin Kashyap, and David Leyba Shortened array codes of large girth. IEEE Transac- tions on Information Theory, (873 2006.
Erum Mushtaq, Jie Ding, and Salman Avestimehr. What if kidney tumor segmentation challenge (kits19) never happened. Tn 2022 21st IEFE International Conference on Machine Learning and Applications (ICMLA), pp. 1740-1747. IEEE, 2022.
Andrew Ng, Michael Jordan, and Yair Weiss, On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14, 2001.
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. In Advances in Neural Information Processing Systems, pp. 6338-6347, 2017.
Maximillian Nickel and Douwe Kiela. Learning continuous hierarchies in the lorentz model of hyperbolic geometry, In International conference on machine learning, pp. 3779 3788. PMLR, 2018.
Yue Niu, Saurav Prakash, Souvik Kundu, Sunwoo Lee, and Salman Avestimchr. Overcoming resource constraints in federated learning: Large models can be trained with only weak clients. Transactions on Machine Learning Research, 2023.
23

---

Published in Transactions on Machine Learning Research (01/2024)
Andre Olsson, Meenakshi Venkatasubraamniin, Viren K Chaudhri, Bruce J Aronow, Nathan Salomonis, Harinder Singh, and H Leighton Grimes. Single-cell analysis of mixed- mixed-lineage states leading to a binary cell fate choice. Nature, (37(7762) 702, 2016.
Chao Pan, Eli Chien, Puoya Tabaghi, Jianhao Peng, and Olgica Milenkovic. Provably accurate and scalable linear classifiers in hyperbolic spaces. Knowleddge and Information Systems, pp. 34, 2023a.
Chao Pan, Jin Sima, Saurav Prakash, Vishal Rana, and Olgica Milenkovic. Machine unlearning of federated clusters. In International Conference on Learning Representations, 2023b. URL https://openreevies. het//forummdd--extfffyyyy.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825 2830, 2011.
Wei Peng, Thomas Varanka, Abdelrahman Mostafa, Henglin Shi, and Guoying Zhao. Hyperbolic deep neural networks: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(12): 10023-10044, 2021.
Aditya Petety, Sandhya Tripathi, and N Hemachandra. Attribute noise robust binary classification (student abstract). In Proceedings of the AAAT Conference on Arlificial Intelligence, volume 34, pp- 13897-13896 2020.
Sundar Pichai. Google's Sundar Pichai: Privacy Should Not Be Luxury Good. In New York Times, 2019.
John Platt et al. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in Large Margin Classifiers, 10(3):61-74, 1999.
Saurav Prakash, Sagar Dhakal, Mustafa Riza Akdeniz, Yair Yona, Shilpa Talwar, Salman Avestimehr, and Nageen Himayat. Coded computing for low-latency federated learning over wireless edge networks. IEEE Journal on Selected Areas in Comsmumications, 39(1):233 250, 2020a.
Saurav Prakash, Hanich Hashemi, Yongqin Wang, Murali Annavaram, and Salman Avestimehr. Secure and fault tolerant decentralized learning. arXiv preprint arXiv:2010.0754 07541, 2020b.
Sauray Prakash, Amirhossein Reisizadeh, Ramtin Pedarsani, and Amir Salman Avestimehr. Hierarchical coded gradient aggregation for learning at the edge. In 2020 IEFE International Symposium on Informa- tion Theory (ISIT), pp. 2616 2621. IEEE, 2020c.
Félix Raimundo, Laetitia Meng-Papaxxatee Papaxanthos, Céline Vallot, and Jean-Philippe Vert. Machine learning for single-cell genomics data analysis. Current Opinion in Systems Biology, 26:64-71, 2021.
John G Ratcllifce, S Axler, and KA Ribet. Foundations of hyperbolic manifolds, volume 149. Springer, 1994.
John G Ratcliffe, S Axler, and KA Ribet. Foundations of hyperbolic manifolds, volume 149. Springer, 2006.
Nicola Rieke, Jonny Hancox, Wenqi Li, Fausto Milletari, Holger R Roth, Shadi Albarqouni, Spyridon Bakas, Mathieu N Galtier, Bennett A Landman, Klaus Maier-Hein, et al. The future of digital health with federated learning. NPJ digital medicine, 3(1):119, 2020.
Debbrata K Saha, Vince D Calhoun, Yuhui Du, Zening Fu, Soo Min Kwon, Anand D Sarwate, Sandeep R. Panta, and Sergey M Plis. Privacy-preserving quality control of neuroimaging datasets in federated envi- ronments. Human Brain Mapping, 43(7) (2:29299922333 2022.
Frederic Sala, Chris De Sa, Albert Gu, and Christopher Ré. Representation tradeoffs for hyperbolic embed- dings. In International conference on machine learning, pp. 4460 4469. PMLR, 2018.
Saber Salchkalcybar, Arsalan Sharifnassab, and S Jamaloddin Golestani. Ono-shot foderated learning: theo- retical limits and algorithms to achieve them. The Journal of Machine Learning Research, 22(1):8485-8531 2021.
24

---

Published in Transactions on Machine Learning Research (01/2024)
Rik Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. In Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers 19, pp. 355-366- Springer, 2012.
Felix Sattler, Robert Müller, and Wojeiech Samek. Clustered federated learning: Modcl-agnostic distributed multitask optimization under privacy constraints. IEEE transactions on neural networks and learning systems, 32(8):3710 3722, 2020.
Micah Sheller, Brandon Edwards, G Anthony Reina, Jason Martin, Sarthak Pati, Aikaterini Kotrolsou, Mikhail Milchenko, Weilin Xu, Daniel Marcus, Rivka R Colen, et al. Federated learning in medicine: facilitating multi-institutional collaborations without sharing patient data. Scientific reports, 10(1):1 12, 2020.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888-900) 2000.
Ondrej Skopek, Octavian-Fugen Ganea, and Gary Bécigneul. Mixed-curvature variational autoencoders. In 8th International Conference on Learning Representations (ICLR (020)(viruaa)) International Conference on Learning Reprosentations, 2020.
Christopher S Smillie, Moshe Biton, Jose Trdovas-Montanne Keri M Sullivan, Grace Burgin, Daniel B Graham, Rebecca H Herbst, Noga Rogel, Michal Slyper, Julia Waldman, al. Intra-and inter-cellular rewiring of the human colon during ulcerative colitis. Cell, 178(3):714 730- 2019.
Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: A survey. IEFE Transactions on Neural Networks and Learning Systems, 2022.
Rishi Sonthalia and Anna Gilbert. Treo! am no tree! i am a low dimensional hyperbolic embodding. Advances in Newral Information Processing Systems, 33:845-856, 2020.
Puoya Tabaghi and Ivan Dokmanić. On procrustes analysis in hyperbolic space. IEEE Signal Processing Lellers, 28:1120- 11:1124-124, 2021.
Puoya Tabaghi, Chao Pan, Eli Chien, Jianhao Peng, and Olgica Milenkovie. Linear classifiers product space forms. arXiv preprint arXiv:2102. 10204, 2021.
Tian Tian, Cheng Zhong, Xiang Lin, Zhi Wei, and Hakon Hakonarson. Complex hierarchical structures in single-cell genomics data unveiled by deep hyperbolic manifold learning. Genome Research, 33(2):232 246, 2023.
Alexandru Tifrea, Gary Beeigneul, and Iilavian-Euger Ganea. Poincaré glove: hyperbolic word embeddings. In International Conference on Learning Representations, 2019. URL https:://oenrrevie: http:///pppnneeiieeeeee//rrrrrr net/forum? id=Skebr3Aq77
Abraham Ungar. Hyperbolic trigonometry and its application in the poincaré ball model of hyperbolic geometry. Computers & Mathematics with Applications, 11(4-))1335-177, 2001.
J Vermeer. A geometric interpretation of ungar's addition and of gyration in the hyperbolic plane. Topology and its Applications, 152(3):226-244) 2005.
Felipe A Vieira Braga, Gozde Kar, Marijn Berg, Orestes Carpaij, Krzysztof Polanski, Lukas Simon, Sharon Brouwer, Tomás Gomes, Laura Hesse, Jian Jiang, et al. A cellular census of human lungs identifies novel cell states in health and in asthma. Nature medicine, 25(7):1153-1166) 2019.
Xidong WI, Zhengmian Hu, and Heng Huang. Decentralized riemannian algorithm for nonconvex minimax problems. arXiu preprint arXiv:2302. 03822,, 2023.
Adilson Elias Xavier. The hyperbolic smoothing clustering method. Pattern Recognétion, 43(3):731-737, 2010.
25

---

Published in Transactions on Machine Learning Research (01/2024)
Tao Yu and Christopher M De Sa. Numerically accurate hyperbolic embeddings using tiling- tiling-based models. Advances in Neural Information Processing Systems, 32, 2019.
Tao Zhang, Tianqing Zhu, Remping Liu, and Wanlei Zhou. Correlated data in differential privacy: definition and analysis. Concurvency and Compulation: Practice and Experience, 34(16):e6015, 2022.
Yiding Zhang, Xiao Wang, Chuan Shi, Xunqiang Jiang, and Yanfang Ye. Hyperbolic graph attention network. IEEE Transactions on Big Data, 8(6):1690-117) 17010, 2021.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint Xrxi::1866.0 00582, 2018.
Yanlin Zhou, George Pu, Xiyao Ma, Xiaolin Li, and Dapeng Wu. Distilled one-shot federated learning. arXiv preprint Xrx::2000.00 07999, 2020.
A Poincaré Graham Scan
A.1 Proof of Correctness
Theorem A.1. Given set of N points D in the Poincaré disc, Alg. returns CH(DD in Oogoog time.
The proof follows the steps of the proof of the Graham Scan algorithm for Euclidean spaces. However, one has to adapt several steps, such as the initial sorting procedure to accommodate the Poincaré disc as presented in Alg. [ Before we proceed with the proof, we need the following lemmas. The results use the same definitions and notation as stated in Alg. [I
Lemma A.2. Let lo be the geodesic starting at b with tangent vector t. All points in and the origin o lie on the same side of lb.
Proof- Since b is the point of largest norm (at the largest distance from the origin), all points in D and the origin o lie or inside the circle centered at and of radius ||o- no--bo bll2- Denote this circle by O. By the definition of a geodesic in the Poincaré disc, it is either a circle are orthogonal to the boundary of the disc or a Euclidean line going through o. Clearly, for b & o, to a geodesic of the first type. Also, since lo starts at b by definition, b is the midpoint of the circle arc. As a result, lb is tangent to O and only intersects it at b. Therefore, all points in D and the origin lic the same side of is.
]
Lemma A.3. Let an a2 0g be points in the Poincaré disc forming a triangle Aajazaz (i.e, not all three points lie on the same geodesic). Then, sign(CCW(an x)) = sign(CCW(a2, az, x)) = sign (agn,, x)) ) if and only if there exists another point x E Aa a203.
Proof. Note that a point x E Dajazas if and only if it is "on the same side" (i.c. clockwise or counter- clockwise) with respect to all three geodesics la -agy lag-aa and lag-ai This is equivalent to the condition (ign(CC((a)
SiignCCW((ng 03, x)) sign(CCW((a,) a1 a)), as claimed.
We are now ready to prove the correctness of Alg.
Proof. By Lemma A.2 all points in D, well as the origin o the same side of the geodesic 4o- As result, they are in the same half-plane in the langent space To with a boundary (which is a straight line) corresponding to 4-- By definition, n is the normal vector of that boundary pointing outward (i.e., towards the side that does not contain any data points). Therefore, the principal angles between each of the log,(z;) and lic in [0, T).
Next, we show that retaining only V {b} is correct during the initial sorting step (i.e., showing that CH(D)= = (H))) This is true due to the following reasons. First, note that b must be in the convex hull CD) Second, let us assume that e is another point in CH(DD but it is not in V. Based on our initial sorting step, this can only happen when there is some E V such that e is on b- That is, the principal angles for log,(v). (c) are the same with respect to but |oog (v))l > || (c)]l Now there
26

---

Published in Transactions on Machine Learning Research (01/2024)
are two possible scenarios: 1) v E CH(D); 2) v & CH(D). For case 1), it is clear that none of the points on vo- belong to (D), as to-v either lies inside (D) or is the boundary of (D).. In either case, c & (D). For case 2), v & (D),), which means that v is strictly contained within the convex hull CH(D). Thus, all points on 16->0 (excluding the starting point b) are also strictly contained in the convex hull (D). As a result, we have established by contradiction that e o& CH(D) if c & V. This immediately implies CH(D)= CH(UU(b))
Next, we focus on showing that the output of Alg. 1 is indeed CH(V U {b]) and thus is equal to CH(D). We prove this result similarly to what is done for the Graham sean in Euclidean space via induction. Without loss of generality, let V 01. u2..... Um- Let C₁ = CH(V; j]U{b}) (i.e., the convex hull of the first points of V and b). The induction hypothesis is as follows. After the jth iteration of the for loop in Alg, [ points in STACK are points of C2 in a counter-clockwie order. The base case can be established casily, as C2 contains points of (H((,, U1, 22]) = (b, v1. 22} (a triangle). Since we start at b and sort V according to the principal angle (counter-clockwise)) the claim obviously true. For the inductive step, assume the hypothesis holds for j 1. Since the principal angle of log,(1;) is greater than log, (15-1) due to the initial sorting procedure, Ab is not contained in Cj-1. Thus, Vy E Cj. Now, let a, C be the two topmost points of STACK. If CCW(c, a, w3)> O or equivalently CCW(e, Vj, a)< 0, the algorithm will not pop a. This is correct since due to the initial sorting, we know that CCW(b, c, a)> 0 and CCW a, 0,)> 0 and thus CCW b, a)> O. By Lemma A.3 we know that & Abcu, and thus a E Cj. In this case, all points in Cz-1 also belong to C by the same argument (since their principal angles are sorted). For the case that CCW(c, a, v2){ O, again by Lemma A.3 we know that a E Abcu, and thus & Cj. As result, it is correct to pop out a. Note that the while loop will correctly keep outputting points. Assume that the while loop stops popping at Vj. Then by the same argument, we know that it is correct to include the entire set Cj-1 in Cz. Thus our hypothesis is true. Finally, by setting = m we arrive the conclusion that the output of Alg. is Cm = CH(VU (b)) CD)) This completes the proof.
Finally, we prove that Alg. produces minimal convex hull.
Proof. Suppose we obtained the (possibly nonminimal) convex hull C = b, C1, .2. Ca. Note that due to the initial sorting, we know that the "principal angles" of Cj with respect. to are listed in increasing order and that they lie in z). As a result, in each Graham Scan check-step (line 10), CJ+1 is outside the triangle of Abe,ez-1- Thus, even if Cj+1, C,-11 lie on the same geodesic (i.e., CCW(C--I,,,.c-)) = 0), the algorithm will remove Cj (and is allowed to do so). The only two additional cases to consider are for b, C1, C2 and Cn-1, b to be on the same geodesic. Due to initial sorting, from a set of points with the same principal angle, we will only keep the furthest one (line 5). Therefore, the Poincaré Graham Scan indeed returns the minimal convex hull.
B Decentralized Order Agreement for B, Label Assignments
We describe next how the participating clients can agree upon an ordering of themselves while keeping it hidden from the FL server - the ordering has to be protected only from the server, and not the clients themselves as they do not have information about the convex hulls of other clients.
Clients participate in key exchange protocol, such as the Hellie-ellman key agreement method, that enables any pair of clients to securely exchange secret information over an insecure communication channel (Diffie & Hellman 1976: Bonawitz et al. 2017). In essence, the key agreement protocol allows any pair of clients to establish a common secret key that can be used for secure communication, even in the presence of potential eavesdroppers, thus ensuring the confidentiality and integrity of their communication. Particularly, in the first step of the key agreement protocol, each client E [L] independently generates pair of keys: A public key KU.Pk) and secret key K((.SK), As the names suggest, the public key K((,PK) of client i is accessible to other clients and the server, while the private key is not. In the next step of the key agreement protocol, each pair of clients i,,12 E [T.] agrees on a random secret. key Rx (1:12)) known only to clients in and i2, where Rx (1.22) = Rxx (f2111 is a function of the public key PK) and secret key (K) Thus, at the end of the key agreement process, each pair of clients shares a common secret key, not known to other clients or the server.
27

---

Published in Transactions on Machine Learning Research (01/2024)
For decentralized order agreement, we further assume that clients have access to public pseudo- random number generator PRG(-). Each client i uses PRG(-) and obtains a private random number (() Thereafter, each pair of clients in and i2 secretly exchange their private random num- bers m( and (+22) using their common secret key Rx (h1.22 for incryption/dett /decryption. Notably, this ensures that the private numbers (n(*) ]E((L] remain hidden from the server. Next, the clients sort the list of the random numbers [n()) Each client i then determines its position in the shared random ordering by finding the position of its number n in the sorted list. Let II(i) denote the corresponding position of client in the shared random ordering. Then, the client picks the numbers 02i-1 211(2) 1 and dz 211(i) from the Bn sequence for labeling of points in their quantized convex hulls C'H + and c'H respectively.
C Uniform Poincaré Quantization
We describe another approach for Poincaré disc quantization, using ideas that are similar to those described in the Poincaré Quantization, Section 5.2 We once exploit radial symmelry and form the quantization bins by intersecting straight lines passing through the origin and concentric circles around the origin. However, in this new setting, our goal to quantize the bounded region within the cirele of hyperbolic radius Ry so that each guantization bin has the same area. With this constraint, we can use finely-grained quantization bins to perform uniformly at random sampling of points on the Poincaré disc.
First, observe that the area of a circle with the hyperbolic radius of rn is given by the following formula (Hitchman 2009)
A(r#) 4 sinh? (2x))
[T
(15)
where s = 1/vk and k is curvature constant. Let No denote the mumber of angular quantization bins. Additionally, let Nug denote the number of radial quantization bins for a hyperbolic radius Rµ and any given angle. The total number of quantization bins therefore equals B=NęN and the area of each bin is A(Rx) Thus, the boundaries for the bins in the angular direction can be denoted by on, 82 Ne 2T, where ni [[N]. In what follows, we characterize the radial boundaries hag for the quantization bins, where [ and hNng =Ru-
B
Consider the circle with hyperbolic radius hag. Since each quantization bin has same area in the hyperbolic plane, we have the following relationship between the circles with hyperbolic radii hng and RH:
A(haa) = n12 A(RB),
(16)
NRH
which results in the following relationship between lina and RH:
hnz 2s - (V 112
RH
sinh
(17)
New
2s
Therefore, a quantization bin B(ni, n2) is well-defined via its angular boundaries 60,-1 and Φn., and radial boundarics hn and hag, where o0=0 and hg=0. Furthermore, any point in the quantization bin B(n,, n2) is mapped to the bin-center be(ni, n2), which we define the point in the bin which partitions it into four parts of equal area. Based on similar arguments as above, the angular distance (bc(n1.m2) and radial hyperbolic distance hoo())n))) for the bin-center are as follows:
-n--1+ on, and mb)(n)m2)) 2s sinh
ssttha |
0.5
RH
(bo(n).m2)
sinh
(18)
2
NRw
2s
To map the results from the hyperbolic plane to the Poincaré disc, the Euclidean radius of the corresponding bin-center is obtained using (9) and its 2D projection is obtained using (be(n).n))
As an example, consider a point x E B within a bin m2)),22). It is quantized to
a (a ainn()))))))))
(19)
28

---

Published in Transactions on Machine Learning Research (01/2024)
where Ç Obe(ns ma]: = s(e 1)/(e² + and 7 hbo(ns,me) This approach of uniform area quantization
is key to implementing the Poincaré uniform sampling process used in Alg. as well as for proving the convex hull complexity result of Theorem 5.2
D Proof for the Convex Hull Complexity
We show that the expected number of extreme points of the convex hull of N points uniformly sampled from a Poincaré disc is al most ((N+). The proof follows similar ideas as those used for the convex hull complexity results in Euclidean spaces (Har-Peled 2011), which are adapted to the hyperbolic setting and involve some technical arguments unique to hyperbolic spaces. We start with a lemma showing that the expected fraction of points that are extreme points of the convex hull is upper bounded by the expected fraction of the area in the Poincaré disc not covered by the convex hull. The lemma appears in Peled 2011 for the Euclidean space, and in this setting, it is known as Efron's 's theorem (Efron 1965
Lemma D.1. Let C' be a Poincaré disc of radius R < Let S(N) E [0. be function of an integer N 2 0 such that the expected area of the conver hull of N points distributed independently and uniformly at random over C is al least (1 - Area()) Then, the expected wamber of extreme points of the conver hull of the N points is at most )
Proof. The proof is the same that for the Euclidean space (Ha--Peled 2011 and is presented for completeness. Uniformly at random partition the N points into two subsets, S and S2, both of cardinality N.
2. Let V1 and V/2 be the sets extreme points of the convex hull of S₁ S1US₂ that are in S₁ and S2, respectively. Denote the convex hull of S2 as (S2).
It follows from definition that the expected number of extreme points of the convex hull of S U So is E[[]]] + E[[V]]] Moreover, we have that
N Area(C)= - Area(CH((S)))
E V
S2
2
ACea(C)
since the probability of point in S lying in (S2),,, and thus not in Vi (because a point strictly inside the convex hull is not an extreme point) is at least Area(CH(S.)), Then, it follows that Area(C)
B| = =ES, F. [[]vil(s)]
$ N ( f( (( {())a))() Area(C)
N N 10 2
Similarly, we have that E[[V/] < N ((W) Therefore, the expected number of extreme points of the convex hull of S, U.S22 is at most ).
Lemma D.I implies that if the area of the convex hull of the independently and uniformly at random sampled N points approaches the area the Poincaré disc, then the expected fraction the points that are extreme points of the convex hull goes zero. In what follows, we show that the area of the convex hull is at least (1- ((-O(N)) times the area of the Poincaré disc, i.c., f(N) < O(v3). Then, it follows from Lemma D.1 that the expected convex hull complexity is most 5.
Partition the Poincaré disc into m = sectors Ti...., Tm, each having an angle 2n Let Di...., Dm= be m m² discs such that Dj the disc C and the area of D, minus the area of D441 is the same for 1 [m?]. where the area of Dm is O. Let subscctor Tı = T, n D,, I E [m], E [m²] be the intersection of sector Ti and disc Dj. The subsectors Ti, have equal area. This partition is the same as the one for the quantization
AAl that is needed for uniform sampling construct quantizer with sufficiently large number of bins, and then select points uniformly at random from discrete collection of bin labels. The sampled point is the centroid of the bin. For more details, see Section
29

---

Published in Transactions on Machine Learning Research (01/2024)
bins described in Section in this section since this is required for formal analysis.
C where Ne and NR, m² We use specific notation for the sectors only
For any sector Ti, let X E m_ be the smallest integer such that at least one of the N points lies in the subsector Xi,x, Then Pr(X; t) S (1- W S <e-(1=1,, since the probability on the lent-han- is at
most the probability that the subsectors Ti. Ti do not contain any of the N points. Hence, we have
m
E|X| = Σ t) 1=1
(20)
Let Ko be the convex hull of the union of the N points and the origin We show that K. completely covers at least m² - (Xi-1 + X ((1) subsectors + Timm² in sector Ti. Let P and Q be the points that lic in the subsectors TI- and T441XX441 respectively, where Tm+1, = Tı,5 and To. T for E [1. m²]. We show that the convex hull of the origin and the points P and Q covers at least m² (X++1 XI-1 + O(1)) subsectors +xx
Timz in sector Ti.
Without loss of generality, assume that the length of the geodesic oP (which is straight line in the Poincaré disc) is larger than the geodesic oQ. Pick a point P' on oP such that the length of oP' equals the length of oQ. Then, P' lies in the subsector Ti-1, Consider the geodesic between p and Q, denoted by P'Q. We have the following lemma.
Lemma D.2. The minimum distance from the origin o to point on the geodesic P'Q is at least (Xuu1+X-1++11) where R2, E m²] is the smallest radius of a disc centered at the origin that com- pletely covers Tig for 1 E [].
By virtue of Lemma D.2 the subsectors Ti,5 j E [X++1 + + m²| are covered by the convex hull of o, P' and Q, and thus covered by K.. Hence, the total number of subsectors Th, covered by Ko is at least Dm (X1+1 X O())). This implies that the expected area of K, is at least
Em [m2 (E[X441] + E[Xi-1]+ + +ODM 11- 3(
m3
times the area of the Poincaré disc. Note that the probability that the origin o lies outside the convex hull of the N points the probability that there exists a point æ among the N points such that the remaining N - points lie on the same side of the geodesic passing through and æ. This probability N equals 24-T. Therefore, we conclude that the expected area of the convex hull of the N points is at least O(N (OON--)Aree Areaa(()) where is the Poincaré disc + Pr(o & K)0 = 1 1
(1-PP Pr E and K is the convex hull of the N points.
To complete the proof, we now prove Lemma D.2 disc, P'Q is part of a circle of centered at a point o' that is orthogonal to the Poincaré disc centered at o with radius 8, in the Euclidean space. The distance from o to the geodesic P'Q is the difference between the length of oo' and the radius of the circle o'. Let R' be the radius of the circle o'.
By the geometric property of a geodesic on a Poincaré
Let the length of oP" be and let the line oP" intersect the circle o' at another point P", Let the length of oP" be r'. Then, we have that rT' s² since the circle o' is orthogonal to the unit Poincaré disc centered at o. Let M be the midpoint of the chord p'p". Then o'M is perpendicular to oM and the length of oM is r+r' 2- + =. Let the angle between oP" and oQ be 0P'Q which is at most Ga Since the lengths of oP" m
s²
and oQ are equal, the angle between oM and oo' is 9pe. Honce, the length of oo' is 2
+
0ro 2
2 cos
On the other hand, the length of oo' equals (RR22 + s?. Therefore, we have
2
r
/ (B') +5. 5².
2 cos
30

---

Published in Transactions on Machine Learning Research (01/2024)
Then, the distance from to the geodesic P'Q can be written as
(RR222 82 =r=r- (r² + (0prQ)2 2( 2 -r)
+0((pr0))) =r 0 m
It is left to be shown that this distance mz) is at least Rx +xi where R& the radius of the disc Di, I m1. Note that by assumption, the length of oP equals the length of oQ. Hence, [xx,11 Rx141-1)- Moreover, R₁ be obtained from 17 by reversing the indexing order and then
from 99, I.c.,
(V
m2 + -1-1
sinh RH
))
h4 28 sssinn~
m²
Rí
(21)
+
where RØ = In (##
R
and R is the radius of the Poincaré disc C. Since
1
0
Rx
1
m2
m
-0( h
m
*x++1 -0(
and
hx
-O(
sinh hx111) cosh
1xx1
sinh
)0
28
28
2s
m
sinh xx(1)+0(11,
2s
have hx.+1
0 0(1))) hx hx41+0(1) +x++X1+++0(1) and thus
Ax N141 1011
r 0
2
Rxi+X
m
1x,+N1
+1
E Proof of Theorem 5.2
We now present the expected convex hull complexity when the data points in the Poincaré disc are quantized, following the algorithm in Section 5.2
Specifically, let e be the distance margin of the quantization algorithm in Section 5.2 We first restate Theorem
5.2 in the following.
Theorem. Let 01....,, NN W be N points uniformly distributed over a Poincaré disc of radius R < 8, where N is sufficiently large. Lei &I,...,&N be quantized versions of æ1,..., obtained using the quantization rule in (11) and (12), with distance margin e = ONN-)) and some constant e 0. Then, the expected number of extreme points the minimal convex hull of 21...., & is at most O(Ne) when }22 at most O(N1-c) when 1 $ c 2, and ot most O(Nb) when <c
Before proving Theorem 5.2 we first state the following lemma, which is a modification of Lemma quantized data points.
D.1 for
Lemma E. Let C be a Poincaré disc of radius R < and let fi(N) E [0. 1] be a function of an integer N 2 0 such that the expected area of the conven hull of f1.... &. least (1 Are))rea(C): Then the expected namber of extreme points of the connex hull of ..,..., &N is al most N (
31

---

Published in Transactions on Machine Learning Research (01/2024)
The proof of Lemma E.1 follows along the same lines of that for Lemma In what follows, we prove Theorem
D.1
5.2
Proof. (of Theorem 5.20 We first prove the theorem for < 2. Similar to what was done in Appendix D we partition the Poincaré disc into Ne = 22irr((iRr) Rn)/c= ( (See Section 5.2 for definition Ne) sectors Ti...., TNo and define No discs Dı...., Dx= such that D1 the Poincaré disc C' and the difference between the area of Dj and the area of D1+1 the same for [N Then we define subsectors Tig Ti n Dj. E [Ne), j E [N9), of the same area.
Then, the probability that given subsector Tig is emply is at most (1- NNNN) S E-0(N--2) By the union bound, the probability that there exists at least one emply subsector is al most Ng -
We now show that when every subsector contains at least one point, the number of extreme points of the convex hull of , is Ne = O(N*). This follows from the fact that in each sector, each subsector Ti. E [No]. that on the boundary of the Poincaré disc is contained in the quantization bin given by (11) and [2]. that is on the boundary of the Poincaré disc C. Moreover, each centroid in the quantization bin that is the boundary of the Poincaré disc is extreme point of the convex hull when every quantization bin has at least one data point.
Let Q denote the event that there exists an empty quantization bin and the number of extreme points of the convex hull of f1....,Nx. Then, we have
V Pr(Q)E(VIQ) + Pr(QS) No + o O
We now consider an upper bound for the case when c We partition the Poincaré disc into Ni-c sectors Tı, ...... Ty--e, and subpartition each sector Ti into No subsectors Ti,,..., Ti,vo of equal area, separated by N - circles. The distance between the origin and the subsector Ti, decreases with j E [No) for every 1 E [N1-9]. Similar to what was done in Section D let X₁ be the smallest integer such that one of æf..... F lies the subsector Tix Let Yú be the smallest integer such that .,, &y lies the subsector T,,. The difference between the distance between the origin and æ and the distance between and á is at most Hence,
Ry: c Rx, S Ry, +
(22)
where Rí, 1 [No] is the radius of Dj in the Poincaré disc. Similarly to 21 Rd can be obtained by
Ne + sinh
28 2ssinh -1
No
2s
e
R
(23)
e +1
From e O(
23 and
22
have
X 2 Yi 0(1).
(24)
and
RS - 0( (012) R(+0(1):
(25)
No
Since E[Xi] O(1) according to 20), we have E|M (1). Let e and Q be two points among ......, Z that are the subsector Ti-1, and T1+1.144. respectively. Following the same argument as in the proof of Lemma D.2 we can establish that the minimum Euclidean distance between the origin and the geodesic PỘ is at least. Ry B ( 2 Ry,1+Yin 0(xt)) Ry By Then following the same
32

---

Published in Transactions on Machine Learning Research (01/2024)
can prove that fi in Lemma E.1 can be upper bounded by O( which by Lemma E.1 implies that the expected number of extreme points on the convex hull of 21.... EN is at most O(N1-9)
argument as in Section
D
The proof of the upper bound for the case <> similar to that for the case 1/2 < 3: partitioning the Poincaré disc into N equal-sized sectors and partitioning each sector into N subsectors, we equally partition the Poincaré disc into N sectors and partition each sector into N subsectors. The remaining steps are similar.
2 where instead of
F Poincaré Uniform Sampling
Our sampling method based on the intuition that the probability of sampling a point from a region in the Poincaré disc should be proportional the hyperbolic area of the region. Based on this idea, we adapt the sampling procedure from our proposed Poincaré uniform quantization method in Appendix [C taking the limit of both the number of angular quantization bins (Ne) and the number of radial quantization bins (Nrw) to infinity. The sampling procodure described in Alg.
Algorithm Poincaré Uniform Sampling
Input: number of points N, bound on the Poincaré radius R, constant curvature Compute s = 1/V1, RH sln ++RR
3: Sample N iid points 7h..... ....... NN from the uniform 44(0, 1] distribution.
4: Sample N iid points fi...., CN from the uniform 21 2x] distribution.
Compute Tj = sishnh (VTT sinh( Rx )) Vj E [N].
Compute a; = s(e 1)/(e= + 1) Vj E [N]. Obtain sample z; B by computing zj (a, cos Cj. aj sjn( Vj [M]
8: Return point set [
G
Construction of B₁ Sequences
We now describe how construct Bn sequence used for label switching resolution. We start with the construction (with proof of correctness) in (Bosc & Chowla 1960 that presents sct of numbers ,f...., , on+1 such that: (1) + pf, where p a prime; (2) fi....,am+t
10. (m + 1)ah 1}; (3) for all 1 S ... < in m + 1, the sums d', + a/ +... + dh, are distinct.
Let an = 0, o2, Om be the elements of a Galois field Fm+1. Let 3 be primitive root of the extension field F(m+1) which implies that 89, ,t.,,,..,,,, 3(m+1)*-1 constitute all the nonzero elements in F(m+1) 1m) and that B is not the root of any irreducible polynomial over the ground field of degree smaller than h.
Let
gol = 3-3+0 aq, I [m + 1]. S (m + 1)ah
We show next that the sums of, + +... af, are all distinct, for s 4 ... S l S m + 1. Supposc on the contrary that
af, + d/ +... + dl = =,y, + alp +... + a'y,
Then, by definition, we have
gds.. ... ghhn = 8e's golz ... ,
which implies that
(8 + 18+a an, aa.).... (). (3 118+a,,10 (3 (B. a.,).
Then 33 is the root of a polynomial with degrec less than h and cocfficients from the ground field, contradicting the fact that 3 primitive element of F(m+1ja. Therefore, the sums of elements in oh, are all distinct.
33

---

Published in Transactions on Machine Learning Research (01/2024)
Finally, as described in Section 5.4 the differences = d/=1 - di.
we can construct B,, sequence set with elements by simply taking
H Extension to Multi-Label Classification
We now describe how our proposed framework extends settings with J global ground truth labels. The process of computing the quantized convex hull for each local cluster remains same. For secure communication of quantized convex hulls, cach client simply nceds J unique numbers from the B,, sequence instead of just 2, while all other system components remain unaffected. For graph based grouping, the FL server obtains the representative graph with JL nodes and partitions into groups of nodes using spectral clustering (Shi & Malik, 2000 Ng et al., 2001). The J global clusters then assigned J different labels, and J-class hyperbolic SVM classifier is trained as follows. For J(> 2) labels, one use the common approach of training a J-class classifier by using J independently trained binary classifiers. In particular, each of the J binary classifiers corresponds to one of the training labels, and is trained independently on the same training set with the task of scparating one chosen class from the remaining classes in the training data set. Thereafter, for each of the binary classifiers, the resulting prediction scores are computed for every data point and are transformed into probabilities using the Platt scaling technique (Platt et al. 1999). The predicted label for a given data point is obtained by using a maximum a posteriori criteria involving probabilities of the classes.
Experimental Setup and Additional Results
1.1 Data Sets
Synthetic Data Sets. We consider R = 0.95 and curvature constant à for all synthetic data sets, and choose N = Js- 100, 000, for μ E (0.2, 0.6, 0.8). Each setting is tested via 10 independent trials. We use a 90%/10% random split for each data set to obtain training and test points.
Biological data sets. We consider the following data sets:
Olsson's acRNA-seed data set OOssonn et al. 2016 containing single-cell (sc) RNA--eq expression data. It comprises 319 points from 8 classes (cell types). We use the Poincaré embeddings provided 1.
by (Chien el al. 2021 in their public code repository
The curvature of the embedding
UC-Stromal data set from (Smillic et al.) 2019), comprising cells from 68 colon mucosa biopsies from 18 ulcerative colitis patients and 12 healthy individuals. The cells were sequenced using 10X Chromium (either v1 or v2) and filtered to remove low-quality cells. We used total of 26, 678 stromal and glia cells of dimension 1,307, corresponding to the number of (highly) variable genes. We obtain the embeddings using mixed-curratuur ure variational aulo-encoders (m-VAE) (Skopek et al., 2020) with 1 MLP layer and 300 hidden dimensions. The curvature for the embeddings is set to h 0.0071. The labels 0 3 used in our results in Section correspond to labels Myofibroblasts, Pericytes, Inflammatory Fibroblasts, and Glia, respectively.
Lung-Human- ASKn-0 data set from (Vicira Braga et al. 2019 comprising human lung colls from asthma patients and healthy controls. A total of 3, 314 cells from the parenchymal lung tissue were sequenced using Drop-seq protocol. The total dimension of the data points, corresponding to the number of genes, is 3.7 Similar to UC-Stromal, we use m- VAE with MLP layer and 300 hidden dimensions to obtain the Poincaré emboddings. The curvature constant for the embeddings is set to k 0.0015. Furthermore, the labels 0 - correspond to labels Type-2, Type-1, T cell, NK cell, and Mast cell, respectively.
http://wwweeellllaaaaatttttttitp http:///ww..natteolelel/sssa//// /scphere. Registration is required access the content.
Accessed GEO: GSET30148.
34

---

Published in Transactions on Machine Learning Research (01/2024)
For each biological data set, we consider a 85%/15% random split for the training and test points, and keep it fixed for all trials. Our implementation for the m- VAE is provided at https://ggihhub com/ woom/thupccct thupchnsky/ sc tevae/tree/ee
2.0
1.5
2.0
0.5
1.0
0.0
1.5
0.5
0.0
-0.5
1.0
-0.5
-1.0
-1.0
-1.0
-0.5
0.0
0.5
1.0
0.5
1.0
1.5
2.0
-1.0
-0.5
0.0
0.5
(a)
(b)
(c)
Figure 8: Visualization of the Poincaré embeddings for the three considered biological data sets (a) Olsson's 's single-cell RNA expression. (b) for the Poincaré disc has been omitted for better scaling for visualization purposes.
(c) UC-Stromal. In (b) and (c), the boundary circle
1.2 Simulation Details
Label Switching. As the FL server applies our proposed graph partitioning based approach to aggregate the local convex hulls after recovering them, does not need to know the ground truth labels or the exact local labels at cach client (i.c., the B, labels suffice to recover the individual quantized convex hulls without knowing the exact identity of the clients from which they came). Hence, we did not simulate label switching in our code at any client because it does not affect the grouping procedure in our algorithm. After grouping the local convex hulls, the FL server assigns to each group a different label of its own choice. In our simulations, the ground truth training label associated with the majority of the local convex hulls in given group is assigned as the label of the data points in that group before training the SVM classifiers on the recovered convex hulls. This is done FL server on the test data set in each setting.
to enable the computation of the accuracy of the trained classifiers at the
Graph-Based Hull Aggregation. For binary classification, we use the kernighan lin bisection() module from the NetworkX library (Hagberg et al. 2008) in Python to group the convex hulls. For multi-label classification, we use the SpectralClustering/) module from Scikit-learn (Pedregosa et al. 2011). Unlike kernighan lin bisection() which produces balanced partitions of nodes for the case of binary classification, SpectralChssterng() based graph partitioning is not guaranteed to provide balanced partitioning for multi- label scenarios. To improve the partioning performance, we observe that the local hulls that belong to the same client should ideally be in separate groups. After B₁, decoding, the server can identify which of the local hulls come from the same client, albeit without knowing the identity of the specific client. Hence, in our simulations, we use a heuristic by which we assign very small weights to edges between each pair of local convex hulls from the same client, forcing SpecttaalClsttrrnggl to assign them to separate groups. This simple heuristic works very well in practice, as witnessed by our simulation results.
Synthetic Data Sets. For both Euclidean and Poincaré SVMs, we set the regularization hyperparameter in 7 to À = 20, 000, which essentially forces the solver to solve the hard margin SVM problem ( For federated baselines, we consider = 10, and partition the training data uniformly across clients.
Biological Data Sets. For both Euclidean and Poincaré SVMs, we consider a regularization term A = 0.1. For federated baselines, we set L 3, and partition the training data uniformly across clients. The default value for the quantization parameter (i.e., distance margin) is e = 0.01. For obtaining the reference points, we find that using the approach proposed in CChicn et al. 2021) (described in Section 3 may be unstable in some settings. Therefore, instead of selecting just the minimum distance pair, we select three pairs of points with lowest pairwise distances, and choose the one pair which produces the best training accuracy.
35

---

Published in Transactions on Machine Learning Research (01/2024)
Table 2: Mean accuracy (%) and 95% confidence interval of the baselines for different data sets. The results are based on 10 independent trials for each setting.
Data set
Labels
CP (%)
CH-CP (%)
CE (%)
CH-CE (%)
Olsson
0-7
79.17 0.00
83.33 0.00
[8.75 0.00
77.08 + 0.00
Lung- Human
[0, 3, 4]
0.00
74.07
67.41 0.00
d: 0.00
1.3 Additional Results
Federated Baselines Outperforming Centralized Ones. For the rows in Table where federated baselines offer better accuracy than their centralized counterparis, we carry out further analysis to examine the reasons behind the findings. For this, we consider additional centralized baselines where before training the SVM classifier (both for the Euclidean and Poincaré methods), we find the minimal convex hull for each class using Alg. [ The SVM classifiers entire classes. The results are presented in Table - where we denote the baselines with minimal convex hulls by CH (Convex Hull). We can observe that training on minimal convex hulls indeed provides better performance than training on original points sets in this case.
then trained the minimal convex hulls instead of the
Table 3: Mean accuracy (%) and 95% confidence interval of the baselines for different data sets. The results are based on 10 independent trials for each setting. The FL method with best mean accuracy is written in boldcase letters.
Data set
Labels
CP (%)
CE (%)
FLP (%)
FLE (%)
0-3
73.20 + 0.00
73.54 = 0.00
68.61 = 3.36
65.98 1008::30 3.63 3.63
0, 1, 2]
74.65 = 0.00
73.94 0.00
65.92 6.11
67.14
5.67
UC-Stromal
0. 1.
88.47 = 0.00
87.39
0.00
89.71 = 1.26
88.59 + 1.04
0. 2,
80.64
= 0.00
82.29
0.00
79.85
2.24
78.14
3.41
1, 2,
80.33
+ 0.00
0.00 80.33
83.45 0.66
82.42 1.61
09 6
12
[CH| |Local clase) (%)
Accuracy (%)
60
CP
40
GE
6
4
Max Average Size
5
Max
FLE
Average
2
10
10
10
E 10
10
10
10
10"
10
10
10"
10"
10"
10
10'
E
(a)
(b)
(c)
Figure 9: Impact of the quantization parameter on accuracy and convex hull complexity for UC-Stromal for the multi-label classification setting with labels - 3) and 5. Here, CHl denotes the quantized convex hull for arbitrary class at arbitrary client. The average as well the max calculated over all clients across all local quantized convex hulls. The shaded areas represent the 95% confidence interval from 10 independent trials.
Results for - 5. Due to requiring the consent of patients for their data to be used for biological analyses, it is usually hard compile large biological data sets. This also the reason why the real-world data sets considered in this paper (relatively) small. Furthermore, the number of participating clients with private biological data sets is expected to be small. Hence, in all our experiments from Section 6 we considered
L = 3. Here, we provide additional results for = 5 and the UC-Stromal data set, with c = 0.01. The accuracy results for various labels are presented in Table 3 while the results illustrating the impact of e on the accuracy and the convex hull complexities for the setting with [0 0--3 3] are shown in Figure 9 We observe
36

---

Published in Transactions on Machine Learning Research (01/2024)
similar trends as for L 3, except that the relative convex hull size increases notably, while the max still remains under 10%.
37


Reviews:
[{"review_id": "iUFK1gzIzb", "reviewer": "Reviewer_Hxr3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n---\n\nThe procedure here consists of many different steps. Each step by itself is interesting and the authors have interesting results for each step. \n\n**Weaknesses**\n---\n\n1) The primary weakness for me is that the paper is not clear. I do not mean that the sentence to sentence writing is not clear, but the message of the paper is not clear. \n\n    a) The first point that is really not clear to me is - what is the actual problem? The problem seems to be that we have distributed information and want a way to learn a classifier. However, I do not understand why we can't collect the data as is and then train a standard classifier. The paper mentions issues related to privacy and computational complexity, but I have two issues with this. 1) privacy is never formally defined. Hence it is very hard to see how privacy is preserved. 2) The authors quantize to reduce complexity, but I think the additional extra computations in relation to the having to recompute the extreme points, as well as the intricate label decoding might defeat this benefit. \n\n    b) Following form this, I think each step in the process could also be better motivated. I understand the authors have tried to provide diagrams for the sequence of events taking place, but it is still quite difficult to follow. It wasn't until I got to the balanced grouping part did I understand why it was ok to encode the labels. \n\n    c) The final bit that is confusing to me is why are we training an SVM. As far as I understand it, we have a fixed data. We do one round of communications and then we classify the data. Hence the grouping could be the classification. Why do we then need to train an SVM on top of that? Is there a test set that is recommunicated in the same way? \n\n**Questions**\n---\n\nI have a few questions\n\n1) Do we think of Z as a collection of tuples? Specifically, I wanted clarification on the non-intersecting assumptions? Can we have two clients with the $z_{I,j}$ but if they have different labels? From the rest of the paper I think so. \n\n2) How did you make the choice of embedding algorithms? Have you tried any of the hierarchical embedding techniques such as Sarkar 2013, De Sa, Gu, Re, Sala 2018, Sonthalia, Gilbert 2020, and Lin, Coifman, Mishne, Talmon 2023? \n\n3) I don't think the quantization scheme is the first one. Please see Yu and De Sa, 2019\n\n4) I am confused as to why we need to recompute the convex hull. I assume this has to do with this fact that the reference point has to be outside this true convex hull. But it is unclear to me whether recomputing the convex hull fixes this.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "For context for my review, I am knowledgeable on hyperbolic spaces and their use in machine learning, I have some prior experience with differential privacy, but I do not know too much about federated learning.\n\nThis paper looks at federated learning in hyperbolic space. Concretely, suppose we want to train a classifier on data, but we cannot do this in a centralized manner. Instead, our data is distributed among $L$ different *clients*. Hence we want to collect data from the clients and do the computations but do so in a \"private\" manner. \n\nThe paper then presents a protocol whereby each client encodes their data, then sends this data to the centralized server. The server then learns a classifier on the data received by the server. The contributions of the paper are\n\n0) The framework for federated learning\n1) An algorithm for finding the extreme points of convex hulls in Hyperbolic space\n2) A way of tiling Hyperbolic space\n3) The theory result on the number on the expected number of extreme points of a convex hull in Hyperbolic space\n4) Experiments showing reasonable results.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "My primary request is could you please clarify the setting and the goal? Specifically, I would really appreciate a definition of privacy to help motivate some of the steps in the pipeline.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1jUZDmhXVg", "reviewer": "Reviewer_a9cx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1) The paper presents a compelling motivation for working with RNAseq data, which is hierarchical in nature and where strong privacy constraints exist.\n2) Several techniques, such as Poincare Quantization, are discussed that could be of independent interest.\n\n\n**Questions/Weakenesses**\n\n1) Paper considers *linear* SVM classifiers on Poincare disks. Did the authors try different non-linear kernels ? If it is non-trivial there should be discussion about this. \n2) Why did authors not consider Riemannian Federated methods (Riemannian Optimization in Federated setup) as potential baselines ? For example see works like  [1,2]\n3) Supposed improvement (11%) is modest when compared to Euclidean FL, especially given the increased complexity in the overall procedure. However, this minor remark holds true for all solutions operating in a Riemannian setting.\n\n\n**Refs**:\n\n[1] Li, J. and Ma, S., 2022. Federated Learning on Riemannian Manifolds.\n\n[2] Wu, X., Hu, Z., & Huang, H. (2023). Decentralized riemannian algorithm for nonconvex minimax problems.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a novel federated learning (FL) method tailored for hyperbolic spaces, specifically for the Poincaré disc model, to handle tree-like data sets more efficiently than traditional Euclidean methods. This approach is crucial for hierarchical data like single-cell RNAseq data, which often comes with privacy constraints. The new method combines convex support vector machine (SVM) classifiers, number-theoretic techniques for label alignment, and quantization methods for efficient data communication. Tests show the hyperbolic FL method outperforms its Euclidean counterpart in classification accuracy, especially in biomedical data scenarios.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iACJXmDzJM", "reviewer": "Reviewer_Ce8E", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n1. A communication-efficient federated classification algorithm for analyzing hierarchical and tree-like data with theoretical analysis is proposed. \n\n2. The numerical studies show the effectiveness of the proposed algorithm by comparing it with the state of the art (including its centralized version). \n\n3. The paper is well-written and the expression is clear. It's easy to follow the main idea of the paper. \n\nWeakness\n\n1. It would be better to compare the communication cost and the computational cost with the state of the art in the experiments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a one-shot federated SVM classification algorithm for hyperbolic spaces for analyzing hierarchical and tree-like data which cannot be embedded into Euclidean spaces of finite dimension with small distortion. Specifically, a distributed version of centralized convex SVM classifiers for Poincaré discs is proposed. Furthermore, the theoretical analysis of the expected complexity of random convex hulls of data sets in hyperbolic spaces is given. Experiments on synthetic data sets and biological data sets verify the effectiveness of the proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I am not familiar with this literature, and hence please weight other experts' opinion higher. The following are more high-level questions:\n\n1. How exactly is privacy defined in the paper? What counts as a privacy leakage? Usually, we consider any form of access to raw data (not limited to accessing the data itself) to be a privacy leakage.\n\n2. In Figure 5, the third row, it is interesting that when $\\epsilon$ is relatively small, as $\\epsilon$ increases, the accuracy rate does not change significantly. Can the author give some discussion?\n\n\n3. Def 3 introduces $\\epsilon>0$ as a parameter which is a little bit confusing to me since it does not appear in the definitions.", "broader_impact_concerns": "The study of this type of algorithm is a very interesting direction for the federated learning community", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new approach for federated classification in hyperbolic space, which necessitates new mechanisms for communicating information from server to client, accounting for label switching, and aggregating information at the server. 

The initial reviews found the paper to address an interesting problem, with a number of novel technical contributions. There were also some concerns raised, primarily on the following points:

(1) comparison to Riemannian FL methods

(2) clarity on the precise problem setting and constraints, to help motivate the need for the various components of the proposed solution

(3) the precise notion of privacy used in the paper, how and why it deviates from DP

For (1), the response clarified the differences between the paper's setting and those of recent Riemannian FL works (which focus on the optimisation procedure), and the non-triviality of applying such techniques to federated classification in hyperbolic spaces.

For (2), the response gave a more detailed explanation of the problem setting.

For (3), the response gave more clarity on the paper's notion of privacy. However, there is scope for the manuscript to more clearly discuss some points:

- the paper does not use (Local) DP. In the response, the authors explain the rationale for this in the context of biological applications. Such discussion would be useful to include in the text.

- the proposed scheme requires transmitting certain extreme points of quantised convex hulls from client to server. The privacy leakage is taken to be the total number of transmitted points. Typically, communicating even a few individual records is not favoured in privacy settings. Perhaps this is a fundamental challenge in hyperbolic FL (owing to the requirement of knowledge of convex hulls) that could be important to study in future work; but at the least, there could be more discussion of this point. e.g., there is not much discussion on the what such extreme points might plausibly correspond to in the setting of interest (anomalous patient records, which might be sensitive?).

- the paper's notion of privacy appears entwined with the communication protocol. e.g., it is not clear whether there might be other strategies that are also private under the paper's definition.


Overall the paper makes a number of technical contributions that could be of interest to the community. Some edits to clarify the notion of privacy could help better contextualise the work, qualify potential limitations of the approach, and suggest directions for future work.



**Suggested changes**

We suggest the following changes prior to publication. Most of these involve incorporating text from the authors' response.

- the response in https://openreview.net/forum?id=umggDfMHha&noteId=sWngboaJXb included a detailed discussion of the problem that paper seeks to solve. It would be useful to have at least some part of this in the paper, e.g., in Section 1 or Section 3.2.

- include a clear statement of the paper's notion of privacy and how the proposals satisfy this. e.g., in Section 1 or Section 3.2, based on the response in https://openreview.net/forum?id=umggDfMHha&noteId=P4Pdjew51N.

- include discussion of why (Local) DP is not favoured in the specific problem setting, e.g., at end of Section 2 or in "Privacy leakage" paragraph.

- include a comment on whether, in different applications where federated hyperbolic classification may be natural, there are still reasons to favour the paper's notion of privacy compared to (Local) DP. [The title refers to FL for generic hyperbolic classification, so it would be good to clarify whether the paper's notion of privacy is suggested to be used in _all_ such applications.]

- include discussion of the potential issues (or lack thereof) with transmitting extreme points of the quantised convex hulls, e.g., whether there is a risk they might correspond to transmitting patients with easily identifiable records. If there is no issue here, that is ideal; if there is a potential issue, it would be good to mention and note as a challenge in hyperbolic FL for future work to study.

- include discussion of whether there might be other ways of achieving privacy beyond the paper's proposal.

- (*Optional*) consider whether Section 3.2 should belong under "Preliminaries": it is 4.5 pages, and gives quite a lot of detail about the individual steps in the procedure. Indeed, the sub-section is about as long as Section 4. It might be nice to consider re-arranging material across Section 3.2 and Section 4.

- (*Optional*) consider having an explicit concluding section to discuss future work.
Decision: Accept (poster)