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

:::info Authors:

(1) Junwei Su, Department of Computer Science, the University of Hong Kong and [email protected];

(2) Chuan Wu, Department of Computer Science, the University of Hong Kong and [email protected].

:::

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

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.

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.

\

:::info This paper is available on arxiv under CC BY 4.0 DEED license.

:::

\