One-Hot Graph Encoder Embedding
| Author(s) | Shen, Cencheng | |
| Author(s) | Wang, Qizhe | |
| Author(s) | Priebe, Carey E. | |
| Date Accessioned | 2023-02-02T18:19:28Z | |
| Date Available | 2023-02-02T18:19:28Z | |
| Publication Date | 2022-11-28 | |
| Description | © 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. This article was originally published in IEEE Transactions on Pattern Analysis and Machine Intelligence. The version of record is available at: https://doi.org/10.1109/TPAMI.2022.3225073 | |
| Abstract | In this paper we propose a lightning fast graph embedding method called one-hot graph encoder embedding. It has a linear computational complexity and the capacity to process billions of edges within minutes on standard PC — making it an ideal candidate for huge graph processing. It is applicable to either adjacency matrix or graph Laplacian, and can be viewed as a transformation of the spectral embedding. Under random graph models, the graph encoder embedding is approximately normally distributed per vertex, and asymptotically converges to its mean. We showcase three applications: vertex classification, vertex clustering, and graph bootstrap. In every case, the graph encoder embedding exhibits unrivalled computational advantages. | |
| Sponsor | This work was supported in part by the Defense Advanced Research Projects Agency under the D3M program administered through contract FA8750-17-2-0112, the National Science Foundation HDR TRIPODS 1934979, the National Science Foundation DMS-2113099, the University of Delaware Data Science Institute Seed Funding Grant, and by funding from Microsoft Research. We thank the editor and reviewers for their excellent suggestions to improve the paper. We thank Jonathan Larson and Ha Trinh from Microsoft Research for test running our code. | |
| Citation | C. Shen, Q. Wang and C. E. Priebe, "One-Hot Graph Encoder Embedding," in IEEE Transactions on Pattern Analysis and Machine Intelligence, doi: 10.1109/TPAMI.2022.3225073. | |
| ISSN | 1939-3539 | |
| URL | https://udspace.udel.edu/handle/19716/32202 | |
| Language | en_US | |
| Publisher | IEEE Transactions on Pattern Analysis and Machine Intelligence | |
| Keywords | Central limit theorem | |
| Keywords | community detection | |
| Keywords | graph embedding | |
| Keywords | one-hot encoding | |
| Keywords | vertex classification | |
| Title | One-Hot Graph Encoder Embedding | |
| Type | Article |