Java implementation of various algorithms that build and proces k-nearest neighbors graph (k-nn graph).
Graph building algorithms:
- (Multi-threaded) Brute-force: works with any similarity measure;
- (Multi-threaded) NN-Descent: works with any similarity measure;
- Online graph building, as published in "Fast Online k-nn Graph Building";
- NNCTPH, as published in "Building k-nn graphs from large text data", for text datasets;
Implemented processing algorithms:
- Dijkstra algorithm to compute the shortest path between two nodes;
- Improved Graph based Nearest Neighbor Search (iGNNS) algorithm, as published in "Fast Online k-nn Graph Building";
- Pruning (remove all edges for which the similarity is less than a threshold);
- Tarjan's algorithm to compute strongly connected subgraphs (where every node is reachable from every other node);
- Weakly connected components.
For the complete list, check the documentation or the examples.
Using maven:
<dependency>
<groupId>info.debatty</groupId>
<artifactId>java-graphs</artifactId>
<version>RELEASE</version>
</dependency>
Or from the releases page.
Most of the time, all you have to do is:
- Create the nodes
- Choose and configure the graph builder (mainly the similarity to use)
- Compute the graph
- Process the graph...
import info.debatty.java.graphs.*;
import info.debatty.java.graphs.build.NNDescent;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;
public class NNDescentExample {
public static void main(String[] args) {
Random r = new Random();
int count = 1000;
int k = 10;
// 1. Create the nodes
ArrayList<Node> nodes = new ArrayList<Node>(count);
for (int i = 0; i < count; i++) {
// The value of our nodes will be an int
nodes.add(new Node<Integer>(String.valueOf(i), r.nextInt(10 * count)));
}
// 2. Instantiate and configure the build algorithm
NNDescent builder = new NNDescent();
builder.setK(k);
// early termination coefficient
builder.setDelta(0.1);
// sampling coefficient
builder.setRho(0.2);
builder.setMaxIterations(10);
builder.setSimilarity(new SimilarityInterface<Integer>() {
@Override
public double similarity(Integer v1, Integer v2) {
return 1.0 / (1.0 + Math.abs(v1 - v2));
}
});
// Optionnallly, define a callback to get some feedback...
builder.setCallback(new CallbackInterface() {
@Override
public void call(HashMap<String, Object> data) {
System.out.println(data);
}
});
// 3. Run the algorithm and get computed graph
Graph<Integer> graph = builder.computeGraph(nodes);
// Display neighborlists
for (Node n : nodes) {
NeighborList nl = graph.get(n);
System.out.print(n);
System.out.println(nl);
}
// Optionnally, we can test the builder
// This will compute the approximate graph, and then the exact graph
// and compare results...
builder.test(nodes);
// 4. Analyze the graph:
// Count number of connected components
System.out.println(graph.connectedComponents().size());
// Search a query (fast approximative algorithm)
System.out.println(graph.search(r.nextInt(10 * count), 1));
// Count number of strongly connected components
System.out.println(graph.stronglyConnectedComponents().size());
// Convert the graph to an online graph (to which we can add new nodes)
OnlineGraph<Integer> online_graph = new OnlineGraph<Integer>(graph);
// Now we can add a node to the graph (using a fast approximate algorithm)
online_graph.addNode(
new Node<Integer>("my new node 1", r.nextInt(10 * count)));
}
}
This will produce something like:
{computed_similarities=64361, c=4542, iterations=6, computed_similarities_ratio=0.12885085085085085}
{computed_similarities=75008, c=4031, iterations=7, computed_similarities_ratio=0.15016616616616615}
{computed_similarities=86254, c=3201, iterations=8, computed_similarities_ratio=0.17268068068068068}
{computed_similarities=97291, c=2302, iterations=9, computed_similarities_ratio=0.19477677677677677}
{computed_similarities=108458, c=1634, iterations=10, computed_similarities_ratio=0.21713313313313312}
Theoretical speedup: 1.0
Computed similarities: 108458
Speedup ratio: 4.605469398292427
Correct edges: 8180 (81.8%)
Quality-equivalent speedup: 3.767273967803205
6
[(523,9520,0.08333333333333333)]
12
Check the documentation or the examples for other building and processing possibilities...