# Quickly pruning edges below average weight for a membership-based weighting

I have points represented as sparse high-dimensional binary vectors, or put another way, I have a list of groups that each point belongs to. For two points, the edge weight between them is $\sum_i 1/|B_i|$ where $|B_i|$ is the number of points that belong to group $i$, and the summation is over all shared groups that both points belong to.

My distribution on group size is very skewed where there are a few large groups that contain about 5 million points and many small groups that contain 2-10 points. Each point belongs to about 5 groups on average and there are roughly a million groups. Also there are roughly 10 million points total. The goal is to identify all edges that have weight above some pretty high threshold, e.g. the mean edge weight.

Currently the best algorithm I have in hand is to check all pairs of points within each group and compute the edge weight between them. However there are groups that give rise to on the order of $10^{13}$ pairs, which is too high. I was thinking of maybe going through groups from smallest to largest and somehow eliminating a lot of pairs to check once the larger groups are reached, since after all the overall edge weight has to be above a pretty high threshold. But I'm not 100% sure how to formalize that, or whether it would really help. Any help would be greatly appreciated, either advice on how to make my pruning idea effective, or even completely fresh ways to approach the problem.

• Well, if you have read a couple of hundred posts, the conclusion path "bad formatting --> little effort/care --> bad question" becomes ingrained. Unfairly though, but you can read only so much.
– Raphael
May 21 '14 at 16:16

Yes, we can make your idea work. I'll show how below, and prove that it is correct (it does not miss any edges).

The first step will be to sort the groups by decreasing size. Say their sizes are $s_1 \ge s_2 \ge s_3 \ge \dots$. Say $t$ is your threshold. Find the smallest $k$ such that

$$1/s_1 + 1/s_2 + \dots + 1/s_k \ge t.$$

Lemma. No edge can have weight above the threshold $t$ based only upon membership in groups $1,2,\dots,k-1$. In other words, every edge with above-threshold weight must be in at least one of the groups $k,k+1,k+2,\dots$.

This observation lets you apply your idea, to optimize the performance of the algorithm.

Algorithm. Sort the groups by decreasing size and find $k$, as above. For each of groups $k,k+1,k+2,\dots$, look at all pairs of points within the same group, and compute the edge weight of each such edge. Output the ones whose edge weight is above the threshold $t$.

This algorithm can be proven to output all above-threshold edges, thanks to the lemma above.