HnwsGraph creates disconnected components

[nitirajrathore]

Description

I work for Amazon Retail Product search and we are using Lucene KNN for
semantic search of products.
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. I saw we have
   at most 3 to 4 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(EP) in zeroth level graph was disconnected
   from rest of the graph making the %age disconnected as high as 99.9% (only 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.

Reproduciability

Although it is fairly easy to be reproduced with Amazon's internal data, but I found it really hard to reproduce it with random vectors. I will attached a simple main class of my test and the parameters that I tried. I only got some disconnectedness as listed in below table. For higher number of vectors, the execution becomes painfully slow because of hnsw graph creation. I will continue to work to find some parameters for reproducibilty and also explore open source datasets for the same.

DIS-L0 means: %age of disconnected nodes in graph at level-0 of HNSW graph.

randomness seed	dimension	no of doc vectors	Max-conn	Beam-width	dis-l0	dis-l1	dis-l2	dis-l3	dis-l4
-219343918	256	100_000	16	100	0	0.0158 (1 node disconnected)	0	0	0
-245556271	256	100_000	16	100	0	0.0158 (1 node disconnected)	0	0	0
-766887769	256	1_000_000	16	100	0.0003	0.04166	0	0	0

No direct solution comes to my mind but as per my discussion in this email thread. I will look into the part where some connections are removed to maintain the Max-Conn property (diversity check etc.).

Version and environment details

Lucene version : 9.7

[nitirajrathore]

I was able to run tests on wiki dataset using the luceneutils package. The results shows that even with a single segment index and no updates, around 1% nodes gets disconnected for about 1M vectors. It would be great if someone else can have a look at the CheckHNSWConnectedness for correctness.

This may or may not be an issue for different system given that this is 'approximate' nearest neighbour search. But in my opinion it is worth exploring more and if possible some fix.

Next I will try to reproduce with multiple segments and try to find the cause and fix for it.

[msokolov]

Have you any results how connectivity varies with maxconn? I found this article that talks about connectivity when filtering; anyway it shows a suggestive graph that made me think maybe there is a non-linear behavior and we should try to fit maxconn to the dataset better. I also believe that this GloVe data is somewhat pathological - it doesn't have the best numerical properties. Maybe try re-running your test with some of the other wikipedia-based datasets we generated for luceneutil like the one using the minilm model?

Also - can you think of some way to preserve global connectivity while removing links? It seems somewhat intractable to me, but maybe there is some way?

[msokolov]

I'm thinking of something like this: first build a fully-connected graph (no link removal, no enforcement of maxconns). Then apply a global pruning algorithm of some sort that attempts to preserve connectivity. For example, you could iterate over all the vectors in the graph, searching for each one using a consistent entry point (node 0 in the graph say, since it will probably be maximally-connected), and "coloring" the visited nodes and edges during the searches. Stop once every node has been visited. Some of the edges will not have been visited, and we could prune those from nodes with large numbers of edges.

[nitirajrathore]

Thanks @msokolov : These are really good suggestions. I will try to incorporate these ideas in solutions. I think in the end there can be multiple ways to allow more connectivity.

I was also worried about how the connections are made and pruned. I checked these lines in our algorithm. Here we connect a node to the neighbour list only if is not closer to any of the current neighbour. Think of a situaion where for some nodes (say a) if the first neighbour connected (say b) has a good score but the rest of the candidate nodes have higher score with b than a. Then the rest of the candidates will NOT get connected to a AT ALL. Later if because of some other connection of b, say the non diverse connection of b -> a is removed then the a will get completely disconnected from graph. Basically we should have more nodes connected in the begining itself so that if some nodes are removed we do not run danger of disconnected graphs.

To check this I added lot of code to collect the events (like add, connect, disconnect) and was able to reproduce it with just 10K graph size itself with max-conn 16. Example below. But the same is not reproduced with max-conn 32 or max-conn 64. Although, increasing max-conn in this case helped but the basic algorithm for connections does not seem very good to me.

To fix this I checked that the original paper proposes the concept of keepPrunedConnections. I implemented that in my local and ran tests. But something is not right, I will keep checking if I did something wrong in the implementation etc. Will submit "draft" PR soon for others comments.

I think there is another issue in current implementation. Look at this code where we finally connected edge from b ---> a and now if b has more connections then max-conn then we are removing one of the non diverse connection of b Say we remove the b ---> c. So we are removing this half of the undirected connection but I don't think we are removing the other half c ---> b anywhere. This will leave inconsistent Graph. I tried fixing this as well, but I am getting some errors. I will try to fix and submit the draft PR.

Note that adding the concept of keepPrunedConnections will not just impact these disconnected nodes but in general the connections of all the nodes will increase and will become close to 'max-conn'. I think this is a good property without much additional cost at the time of graph creation. But the search time may increase a bit since there will be more connections to explore for the same max-conn. But I think this will also increase the Recall with ExactKNN. I will run the performance tests once code complete to find those numbers.

---

• Real example of disconnectedness
  In one of the 10K vector runs, I found 3 nodes were disconnected. namely 297, 298, 5601
  I checked that 297 was initially connected to 293. After that it was compared to a lot of candidates but was not connected to any because their score with 293 was higher than their score with 297. For example here 297 was compared with 43 and 197 but was NOT connected to either because their score with 293 was higher. In this case 297 was left with just one connection (with 293). Later on the connection of 293 ---> 297 also got deleted because of diversity checked triggered for other nodes connection with 293.

level=0,node=297,type=CONNECT,source=297,dest=293,otherdata=score=0.9578
level=0,node=297,type=COMPARE,source=297,dest=43,otherdata=score=0.9541
level=0,node=297,type=COMPARE,source=43,dest=293,otherdata=neighborSimilarity=0.9816,  score=0.9541
level=0,node=297,type=COMPARE,source=297,dest=197,otherdata=score=0.9539
level=0,node=297,type=COMPARE,source=197,dest=293,otherdata=neighborSimilarity=0.9868,  score=0.9539
......
level=0,node=298,type=CONNECT,source=298,dest=297,otherdata=score=0.9854
....

Final connections were, full 2-way connection 297 <---> 298 and one sided connection of 297---> 293 (left over connection).
But there was no path to 297 and 298 from any other node as the other way connection from 293 ---> 297 got deleted.

[msokolov]

So we are removing this half of the undirected connection but I don't think we are removing the other half c ---> b anywhere. This will leave inconsistent Graph

This is by design; the resultant graph is not expected to be symmetric (ie undirected, bidirectional). It is allowed to have a->b with no corresponding b->a

[nitirajrathore]

Hi @msokolov ! Thanks for clarifying. But I think it can help to remove the 'less important' edge from both sides, since it frees up a degree of "other" node to accept a new connection without indulging into diversity check. Most of the time the problem that I saw with diversity check is that, the most recently added connection to the node itself turns out to be non-diverse and gets removed immediately. Because of this the new incoming node does not even get enough connections to begin with in the graph. Even in the case where I removed the diversity check while connecting incoming node (a) to neighbours (say b,c) and allow full max-conn number of connections, most of the connections from neighbours (b->a) to the nodes are removed because of diversity check, leaving mostly half connections from (a->b). Now when a new node say x tries to connect to a even that is kicked off by a because of diversity check. So keeping half connections sometimes acts against the connectedness nature of hnsw.
I have come up with a new huristic which seems to work well against disconnectedness, but I am yet to optimize it and conduct performance test on it. Will still update the algorithm here and post numbers later.

[nitirajrathore]

I was able to conduct some perf-test as well. I would like to propose following changes
With example of adding node a to 'b, c, d'

node	neighbours
b	c, d, e
c	b, d
e	b, x, y, z

Proposed heuristic

1. At the time of adding a node always add all (upto maxConn) edges to highest scoring neighbours (disregarding the diversity check) eg. adding edges a-->b, a-->c etc. Currently we check for diverse connections at this time also.
2. At the time of adding reverse edges from neighbours to the node, if the given neighbour has more than maxConn number of connections then use new diversity check formula to calculate the edge that can be removed. For example at the time of adding edge b --> a if we see that b has more than maxConn connections then apply new hiuristic and try to remove one edge.
3. Check for diversity only between the common neighbours of candidate node and the node. Example, if b has more than maxConn connections then we iterate over b's neighbours (which now includes 'a' as well) considering each one as a possible candidate for disconnection. When deciding if we should disconnect an edge say b-->c or not. We will consider the only the common neighbours of c and b for diversity check, so we will compare the score(c,b) with only score(c,d) and not with score(c,e) as only d is the common neighbour of c and b. If we find a non diverse node we return that, otherwise
4. we return a node which has highest number of common neighbours with b, otherwise
5. we return a node with maximum number of edges (eg. e in above case).
6. If none of the above condition exists, then we return -1, meaning we should not remove any connection.
7. If we receive a valid node for removal, we remove that and the other half of the connection i.e. we remove both bi-directional connections. so if c is returned as non-diverse node, then we remove both b---> c and c ---> b connections.

Performance number:

Branch	recall	avgCpuTime	numDocs	reindexTimeMsec	fanout	maxConn	beamWidth	totalVisited	selectivity	prefilter
Baseline	0.451	17.78	1000000	370916	0	16	100	10	1.00	post-filter
Candidate	0.599 (33% increase)	21.63 (22% increase)	1000000	624797 (68% increase)	0	16	100	10	1.00	post-filter

Since now we are increasing the number of connections per node, we also see a good increase in the recall for same max-conn. For the same reason we do expect the avgCpuTime to increase at query time. I can work a little bit on improving the indexing time as the my current implementation is very naive and finds common nodes by two for loops and some other places recalculates the scores where not needed. But overall the indexing time will increase for sure.

Another data that I will post next is the number of (histogram) number of edges each node has. Expect it to increase from lower number to max-conn on average.

I will upload my (rough) draft PR now.

How I reached this heuristic:

Before coming up with this heuristic I tried quite some simpler ones, but in those cases I was either getting much much higher disconnections than the mainline or if very less and even just 1 disconnection, but some disconnection was happening. I am open for removing or adding any other condition which is considered for edge removal.

Initially, I tried with just (1) and left the rest of the algorithm same as in mainline. This "increased" the disconnections by large factor instead of decreasing it. The issue was that say 0 to 32 nodes are added with star kind of formation, now if 33rd node comes in, it will form connections with 1-32 nodes and each may find 0 as the non diverse node, so each one removes 0 leaving it disconnected from the graph. Other than this extreme case there were others too.
That is where (3) came in handy where we don't check diverseness of an edge unless we are sure that there is an alternate path to the disconnecting node via a neighbouring node. This coupled with (7) reduced the disconnectedness from few thousand nodes to just couple of nodes at level-1 and only occassional disconnected node at level-0.
Then to achieve no disconnection at all, I initially tried (1, 2, 3) with (6) to remove even slightest chance of creating disconnectedness, but with this we end up not removing any connection a large number of times and the number of connections per node increased from max-conn of 32 at level-0 to upwards of 250 for more than 5% of nodes.
To control the number of connections I added (4) and (5) mostly to remove at least some connection without affecting the graph geometry by much.
One might wonder if (7) is actually required, so I will run some test without (7). But I think it plays an important by freeing up some of the edges and allowing those nodes to accept un-conditional connections from other incoming node.

[benwtrent]

68% increase in index time is untenable, I would be a hard no on a change that slows things down this much. Maybe we can find something better.

@nitirajrathore i know https://github.com/nmslib/nmslib/blob/master/similarity_search/src/method/hnsw.cc has various heuristics, have you explored those to see how they can be modified or added here?

[nitirajrathore]

@benwtrent : I have added draft PR. The code is not at all optimized right now for performance and I am hoping to fix some obvious stuff and will post perf results here.

have you explored those to see how they can be modified or added here?

No, I haven't checked those. Thanks for pointing it out. I will check and revert.

[benwtrent]

@nitirajrathore @msokolov I had an idea around this, and it will cost an extra 4bytes per node on each layer its a member (maybe we only need this on the bottom layer...)

What if we added an "incoming connection" count for every node? Then when disconnecting non-diverse neighbors, we enforce that we can never disconnect the last connection to a node.

[msokolov]

Is the problem primarily to do with single isolated nodes or do we also see disconnected subgraphs containing multiple nodes? I think this idea would prevent the isolated nodes, but not fix the other case.