Nitiraj,
Good experimentation! Connectedness within layers is indeed important. The
algorithm itself should ensure connectedness of disjoint NSWs as it
mutually connects nodes (selected over diversity).
However, if the data is extremely clustered, this can cause connectedness
to drop (few densely packed clusters may not connect to other densely
packed clusters).
For your extreme examples, is the data densely clustered?
What would you suggest as an improvement in Lucene regarding the algorithm
implementation?
An interesting experiment would be to see if `hnswlib` has the same
connected issues if it indexes the same vectors in the same order.
Thanks!
Ben Trent
On Wed, Aug 23, 2023 at 5:07 AM Nitiraj Singh Rathore <
nitiraj.rath...@gmail.com> wrote:
> Hi Lucene developers,
>
> I work for Amazon Retail Product search and we are using Lucene KNN for
> semantic search of products. We index product embeddings (vectors) into
> lucene (hnsw graph) and search them by generating query embedding at
> runtime. The product embeddings also receive regular updates and the index
> geometry keeps changing because of merges.
> We recently noticed that the hnsw graphs generated are not always strongly
> connected and in worst case scenario some products may be undiscoverable.
> Connectedness of Hierarchical graph can be complicated, so below I am
> mentioning my experiment details.
>
> - Experiment:
> I took the Lucene indexes from our production servers and for each segment
> (hnsw graph) I did following test.
> At each level graph I took the same entry point, the entry point of HNSW
> graph, checked how many nodes are reachable from this entrypoint. Note that
> connectedness at each level was checked independently of other levels.
> Sample code attached. My observations are as below.
>
> - Observation :
> 1. Of all the graphs across all the segments, across 100s of indexes
> that I considered, one graph for each "level" of HNSW, almost 18% of the
> graphs had some disconnectedness.
> 2. Disconnectedness was observed at all the levels of HNSW graphs. We have
> at most 3 levels in HNSW graphs.
> 3. percentage disconnectedness ranged from small fractions 0.000386% (1
> disconnected out of 259342) to 3.7% (eg. 87 disconnected out of 2308).
> In some extreme case the entry-point in zeroth level graph was
> disconnected from rest of the graph making the %age disconnected as high as
> 99.9%
> (65 reachable nodes from EP out of 252275). But this does not necessarily
> mean that the 99.9% of nodes were not discoverable, it just means that if
> unluckily we end up on EP in the 0th level graph for a query, there can at
> max be 65 nodes that can be reached. But had we diverted our path from EP
> to some other node in the upper level graphs then may be more nodes be
> discoverable via that node.
>
> - What I Not Checked :
> What I have not checked till now is the connectedness for the whole HNSW
> graph including edges of all the levels.
> Also, I have not checked the number of disconnected components in a graph.
> I have just checked the number of connected nodes to the entry-point.
>
> But irrespective of that, I think graphs should be strongly connected at
> each level and disconnectedness if at all should be very very rare.
>
> Thanks Kaival Parikh for discovering the issue in the first place and the
> script for checking connectedness.
>
> What do others think about this?
>
> public class CheckHNSWConnectedness {
> private static int getReachableNodes(HnswGraph graph, int level) throws
> IOException {
> Set<Integer> visited = new HashSet<>();
> Stack<Integer> candidates = new Stack<>();
> candidates.push(graph.entryNode());
>
> while (!candidates.isEmpty()) {
> int node = candidates.pop();
>
> if (visited.contains(node)) {
> continue;
> }
>
> visited.add(node);
> graph.seek(level, node);
>
> int friendOrd;
> while ((friendOrd = graph.nextNeighbor()) != NO_MORE_DOCS) {
> candidates.push(friendOrd);
> }
> }
> return visited.size();
> }
>
> public static void checkConnected(String index, String hnswField) throws
> IOException, NoSuchFieldException, IllegalAccessException {
> try (FSDirectory dir = FSDirectory.open(Paths.get(index));
> IndexReader indexReader = DirectoryReader.open(dir)) {
> for (LeafReaderContext ctx : indexReader.leaves() ) {
> KnnVectorsReader reader =
> ((PerFieldKnnVectorsFormat.FieldsReader) ((SegmentReader)
> ctx.reader()).getVectorReader()).getFieldReader(hnswField);
>
> if (reader != null) {
> HnswGraph graph = ((Lucene95HnswVectorsReader)
> reader).getGraph(hnswField);
> for (int l = 0; l < graph.numLevels(); l++){
> int reachableNodes = getReachableNodes(graph, l);
> // int graphSize = graph.size(); // this gives nodes
> at 0th level
> int graphSize = graph.getNodesOnLevel(l).size();
> System.out.printf("Level: %d, Actual Size: %d,
> Reachable: %d, Not Reachable : %d\n", l, graphSize, reachableNodes,
> (graphSize - reachableNodes));
> }
> }
> }
> }
> }
>
> public static void main(String[] args) throws IOException,
> NoSuchFieldException, IllegalAccessException {
> String index = args[0];
> String field = args[1];
> System.out.println("For index " + index + " field : " + field);
> checkConnected(index, field);
> }
>
>
>
>
> --
> Regards,
> Nitiraj
>
