K-Nearest Neighbor Graph Testing Library
C++ Python library that is able to import exisiting NN-structures; Implements Property Testing Algorithm that rejects with high probability if queries to given structure are epsilon-far from giving a K-Nearest Neighbor Graph
Usage

Usage

import numpy as np
import KNNTest as kt
import sklearn.neighbors as sk                     # Import Scikit-Learn (Example)
import pykgraph as kg

n = 100                                            # 100 points
k = 10                                             # 10-NN
epsilon = 0.5                                      # at least half of all queries should return exact k-nearest neighbors
d = 4                                              # 4 dimensions
delta = k                                          # average degree of graph should be k for most NN-libs
c1 = 2                                             # tuning parameter 1
c2 = 1                                             # tuning parameter 2

V = kt.Uniform_Random_Tuple_Generator(n, d).get()  # Generate n tuples of dimension d uniformly at random
                                                   # utilizing mersenne-twister algorithm

Vn = u.numpy_array()                               # get as numpy nd-array

Vn1 = np.random.rand(n, d)                         # random data from numpy
V1 = kt.Relation(Vn1)                              # make KNNTest relation, so a KNN_Graph can be build from the data

#
# Build adjacency-matrix of exact 10-NN Graph efficiently with scikit
#
sk_E = np.matrix(sk.NearestNeighbors(metric='euclidean', algorithm='ball_tree', n_neighbors=k).fit(Vn).kneighbors_graph(Vn, mode='connectivity').toarray().astype('bool'))
knng_sk = kt.KNN_Graph(k)
knng_sk.build(V)
knng_sk.set_edges(sk_E)

#
# Build exact 10-NN Graph with brute-force algorithm in O(n^2)
#
knng_kt = kt.KNN_Graph_Exact(k)
knng_kt.build(V)                       

#
# Build KNN-Index with KGraph
#
kg_index = pk.KGraph(Vn, 'euclidean')
kg_index.build(reverse=-1)
knng_kg = kt.KNN_Graph(k)
knng_kg.build(V)                                   # dummy build

#
# Wrap KGraph-Index in sampling-function
#
def query_kg(Vn, kg_index, k, i):
    neighbors = kg_index.search(Vn[i].reshape(1, Vn[i].shape[0]), K=k)
    return Vn[neighbors,:][0]
    
q_kg = lambda i: query_kg(Vn, kg_index, k, i)

#
# Property Tester for Graphs
#
pt_g = kt.KNN_Tester()

#
# Property Tester for Query-Oracle
#
pt_o = kt.KNN_Tester_Oracle(kg.Query_Oracle(q_kg))

#
# Test Graphs
#
kt_graph_is_far = pt_g.test(knng_kt, delta, d, epsilon, c1, c2)
sk_graph_is_far = pt_g.test(knng_sk, delta, d, epsilon, c1, c2)

#
# Test Oracle
#
kg_oracle_is_far = pt_o.test(knng_kg, delta, d, epsilon, c1, c2)