Approximating Eigenvectors with Fixed-Point Arithmetic

A Step Towards Secure Spectral Clustering

Conference Paper (2021)
Author(s)

Lisa Steverink (Student TU Delft)

Thijs Veugen (TNO, Centrum Wiskunde & Informatica (CWI))

Martin van Gijzen (TU Delft - Numerical Analysis)

Research Group
Numerical Analysis
Copyright
© 2021 Lisa Steverink, Thijs Veugen, M.B. van Gijzen
DOI related publication
https://doi.org/10.1007/978-3-030-55874-1_112
More Info
expand_more
Publication Year
2021
Language
English
Copyright
© 2021 Lisa Steverink, Thijs Veugen, M.B. van Gijzen
Research Group
Numerical Analysis
Bibliographical Note
Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public. @en
Pages (from-to)
1129-1136
ISBN (print)
978-3-0305-5873-4
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

We investigate the adaptation of the spectral clustering algorithm to the privacy preserving domain. Spectral clustering is a data mining technique that divides points according to a measure of connectivity in a data graph. When the matrix data are privacy sensitive, cryptographic techniques can be applied to protect the data. A pivotal part of spectral clustering is the partial eigendecomposition of the graph Laplacian. The Lanczos algorithm is used to approximate the eigenvectors of the Laplacian. Many cryptographic techniques are designed to work with positive integers, whereas the numerical algorithms are generally applied in the real domain. To overcome this problem, the Lanczos algorithm is adapted to be performed with fixed-point arithmetic. Square roots are eliminated and floating-point computations are transformed to fixed-point computations. The effects of these adaptations on the accuracy and stability of the algorithm are investigated using standard datasets. The performance of the original and the adapted algorithm is similar when few eigenvectors are needed. For a large number of eigenvectors loss of orthogonality affects the results.

Files

Steverink2021_Chapter_Approxim... (pdf)
(pdf | 0.276 Mb)
- Embargo expired in 24-01-2022
License info not available