Authors:
(1) Junwei Su, Department of Computer Science, the University of Hong Kong and jwsu@cs.hku.hk;
(2) Chuan Wu, Department of Computer Science, the University of Hong Kong and cwu@cs.hku.hk. Table of Links Abstract and 1 Introduction 2 Related Work 3 Framework 4 Main Results 5 A Case Study on Shortest-Path Distance 6 Conclusion and Discussion, and References 7 Proof of Theorem 1 8 Proof of Theorem 2 9 Procedure for Solving Eq. (6) 10 Additional Experiments Details and Results 11 Other Potential Applications 9 Procedure for Solving Eq. (6) First recall that the optimization problem we want to solve is as follows. where k is the given initial set size and Ds(.) is given in Def. 2 with shortest path distance as the metric. Eq. 6 amounts to the well-known k-center problem [14] in graph theory and is NP-hard. For our experiment, we use Eq. 6 as guidance and modify the simple greedy algorithm, farthest-first traversal, to be a sampling method for obtaining a solution. We now describe how we modified the standard greedy algorithm into a sampling algorithm. We start with describing the standard greedy algorithm. The procedure described above is a standard 2-approximation greedy algorithm for k-center problem. Next, we describe its sampling variant which use the distance as the chance of being sampled. 9.1 Running Time Complexity It is obvious that the procedure above runs in O(k) if the distance between any pair of vertices is given and runs in O(kn) if the distance needed to be computed for each step, where n is the number of vertice. This paper is available on arxiv under CC BY 4.0 DEED license. Authors: (1) Junwei Su, Department of Computer Science, the University of Hong Kong and jwsu@cs.hku.hk; (2) Chuan Wu, Department of Computer Science, the University of Hong Kong and cwu@cs.hku.hk. Authors: Authors: (1) Junwei Su, Department of Computer Science, the University of Hong Kong and jwsu@cs.hku.hk; (2) Chuan Wu, Department of Computer Science, the University of Hong Kong and cwu@cs.hku.hk. Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Related Work 2 Related Work 3 Framework 3 Framework 4 Main Results 4 Main Results 5 A Case Study on Shortest-Path Distance 5 A Case Study on Shortest-Path Distance 6 Conclusion and Discussion, and References 6 Conclusion and Discussion, and References 7 Proof of Theorem 1 7 Proof of Theorem 1 8 Proof of Theorem 2 8 Proof of Theorem 2 9 Procedure for Solving Eq. (6) 9 Procedure for Solving Eq. (6) 10 Additional Experiments Details and Results 10 Additional Experiments Details and Results 11 Other Potential Applications 11 Other Potential Applications 9 Procedure for Solving Eq. (6) First recall that the optimization problem we want to solve is as follows. where k is the given initial set size and Ds(.) is given in Def. 2 with shortest path distance as the metric. Eq. 6 amounts to the well-known k-center problem [14] in graph theory and is NP-hard. For our experiment, we use Eq. 6 as guidance and modify the simple greedy algorithm, farthest-first traversal, to be a sampling method for obtaining a solution. We now describe how we modified the standard greedy algorithm into a sampling algorithm. We start with describing the standard greedy algorithm. The procedure described above is a standard 2-approximation greedy algorithm for k-center problem. Next, we describe its sampling variant which use the distance as the chance of being sampled. 9.1 Running Time Complexity It is obvious that the procedure above runs in O(k) if the distance between any pair of vertices is given and runs in O(kn) if the distance needed to be computed for each step, where n is the number of vertice. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Optimizing GNNs: A Sampling-Based Solution to the k-Center Problem

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Data-centric Approach to Class-specific Bias in Image Data Augmentation: Abstract and Intro

An Introduction to Active Learning

Unleash Your Potential: Weaponizing Active Learning with David Novak

Understanding Topology Awareness in Graph Neural Networks

Exploring Topology Awareness, Generalization, and Active Learning in Graph Neural Networks

Framework for Analyzing Topology Awareness and Generalization in Graph Neural Networks

A Data-centric Approach to Class-specific Bias in Image Data Augmentation: Abstract and Intro

An Introduction to Active Learning

Unleash Your Potential: Weaponizing Active Learning with David Novak

Understanding Topology Awareness in Graph Neural Networks

Exploring Topology Awareness, Generalization, and Active Learning in Graph Neural Networks

Framework for Analyzing Topology Awareness and Generalization in Graph Neural Networks

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps