Planted hitting set recovery in hypergraphs

First let us suppose that we are given G and asked to find C, where we know that C is minimal and |C| ⩽ k. We ask the following question: is it possible to find a small set H ⊂ G, whose size is independent of G, such that C ⊂ H? In this section, we answer the question in the affirmative.

We at least know that the union of all minimal hitting sets of size at most k, denoted U(k) (definition 1), must contain C. But how large can this set be? The following result says that U(k) actually cannot be too large.

Lemma 2. In a hypergraph of rank r, U(k) has size Θ(k^r ) in the worst case.

Damaschke and Molokov established most parts of this result using sophisticated techniques from parameterized complexity theory [18, 19]. Chitnis et al independently established similar (albeit looser) results for streaming data applications [14]. Here, we provide a concrete, complete characterization and proof that should be accessible to anyone familiar with basic graph theory by using the celebrated sunflower lemma of Erdös and Rado [25]. A consequence of lemma 2 is the following theorem about how small of a set we can find that is guaranteed to contain the core:

Theorem 3. Let C be a planted minimal hitting set with |C| ⩽ k in a hypergraph of rank r. Then we can find a set D of size O(k^r ) that is guaranteed to contain C.

We begin by providing a self-contained proof of the upper bound in lemma 2 and theorem 3. Namely, let G be a hypergraph of rank r, and let U(k) be the union of all minimal hitting sets in G of size at most k. We will find a function g(r, k) = O(k^r ) so that |U(k)| ⩽ g(r, k). To find such a function, we use a combinatorial structure called a sunflower [10]. A collection of r sets {X₁, X₂, ..., X_r } is an r-sunflower if for all pairs of distinct sets X_i , X_j , the pairwise intersection X_i ∩ X_j is equal to the mutual intersection . The term comes from the fact that we can think of the X_i as the 'petals' of the sunflower: they share a 'center' and are otherwise pairwise disjoint from each other. A famous theorem of Erdös and Rado asserts that every sufficiently large collection of sets must contain a large sunflower.

Lemma 4  (sunflower lemma [ 25 ]). Define the function σ(r, k) = r!(k − 1)^r . Any collection of more than σ(r, k) sets, each of size at most r, must contain a k-sunflower.

We use this result to find the desired function g(r, k) = O(k^r ). Later, we will establish an asymptotically matching lower bound. We now state and prove the upper bound.

Lemma 5. Let G be a hypergraph of rank r. Then |U(k)| = O(k^r ).

Proof. We assume that G has at least one hitting set of size at most k, as otherwise the statement of lemma 5 holds with U(k) equal to the empty set. We modify G according to the following iterative procedure, which operates in discrete phases. We start by defining H₀ = G, and produce a succession of hypergraphs H₁, H₂, ..., with H_t the hypergraph at the end of phase t. For each hypergraph H_t , let C(H_t ) denote the set of all hitting sets of size at most k in H_t , and let denote the set of all minimal hitting sets of size at most k in H_t . We will establish by induction that each hypergraph H_t has at least one hitting set of size at most k.

At the start of phase t, we ask whether H_t−1 has more than σ(r, k + 1) hyperedges, where σ is the function from lemma 4. If it does not, we declare the procedure to be over. If it does, then we find a (k + 1)-sunflower in the set of hyperedges, consisting of hyperedges X_t,1, X_t,2, ..., X_t,k+1.

Now, the core of the sunflower found in phase t, which we will denote by must be non-empty, for if it were empty, then H_t−1 would contain k + 1 pairwise disjoint hyperedges, and hence could not have a hitting of size at most k. We define H_t as follows: starting from H_t−1, we remove the hyperedges X_t,1, X_t,2, ..., X_t,k+1 and add the hyperedge Y_t . We observe the following properties.

• (a)  
  Every hitting set in H_t−1 of size at most k must intersect Y_t .
• (b)  
  C(H_t−1) = C(H_t ), and hence .

To see property (a), by the definition of a sunflower, the sets X_t,i \Y_t are pairwise disjoint for i = 1, 2, ..., k + 1. Thus, if C is a set of size at most k that does not contain any nodes of Y_t , then it must be disjoint from at least one of the sets X_t,i , and hence it cannot be a hitting set for H_t−1. The definition of H_t is as follows: starting from H_t−1, we remove the hyperedges X_t,1, X_t,2, ..., X_t,k+1 and add the hyperedge Y_t . Since H_t−1 and H_t are hypergraphs on the same node sets, their respective collections of hitting sets C(H_t−1) and C(H_t ) are also over the same sets of elements.

Now, let . Then by property (a), it must intersect Y_t . Since Y_t is the only hyperedge in H_t but not H_t−1, it follows that C is a hitting set for H_t , and hence . Conversely, let . Since Y_t ⊂ X_t,i for i = 1, 2, ..., k + 1, it must be that C₀ intersects each X_t,i . Since X_t,1, X_t,2, ..., X_t,k+1 are the only hyperedges in H_t−1 but not H_t , it follows that . Thus, , and so they are equal as sets.

We apply the same process in each phase, producing H₁ from G = H₀, then producing H₂ from H₁ and so forth. By induction using property (b), since H_t−1 contains at least one hitting set of size at most k, so does H_t , as required. Since the procedure reduces the number of hyperedges in each phase, it must eventually terminate, in some phase t*. We write and by applying property (b) transitively,

We say that a node is isolated if it does not belong to any hyperedge. Let T* be the set of non-isolated nodes of H*. Since the procedure stopped when faced with H*, H* had at most σ(r, k + 1) hyperedges. Since each hyperedge has most r elements, we have

and hence |T*| is bounded by O(k^r ). Finally, recall that U(k) is the union of all minimal hitting sets in G of size at most k. We can write , and by equation (1), . No minimal hitting set C in H* can contain an isolated node v, since then C − {v} would also be a hitting set in H*. From this, U(k) ⊂ T*, and |U(k)| ⩽ |T*| = O(k^r ) by equation (2). □

Next, we show asymptotic tightness for constant hypergraph rank r, by constructing a family of hypergraphs for which |U(k)| = Ω(k^r ). The following lemma combined with lemma 5 proves theorem 3.

Lemma 6. For each constant r ⩾ 2, there exists an infinite family of rank-r hypergraphs G and parameters k, with both the number of nodes in G and k going to infinity, for which |U(k)| = Ω(k^r ).

Proof. For a parameter b, consider a graph Γ_b that consists of b disjoint complete b-ary trees of depth r. We will refer to the roots of the b trees in Γ_b as the root nodes of Γ_b , and to the leaves of the trees in Γ_b as leaf nodes. Let T_b be the hypergraph on the node set of Γ_b whose hyperedges consist of all root-to-leaf paths in Γ_b , from the root of one of the b trees in Γ_b to a leaf of the corresponding tree (the example of T₂ for r = 3 is in figure 2). All edges in G have size r. Let λ be any function that maps nodes of Γ_b to numbers in {1, 2, ..., b} with the following properties: (i) λ is a bijection from the roots of Γ_b to {1, 2, ..., b}; and (ii) for each non-leaf node v in Γ_b , λ is a bijection from the children of v to {1, 2, ..., b}. For each node v, we will call λ(v) its label (with respect to λ), and we will say that λ is a consistent labeling if it satisfies (i) and (ii). Let be unique leaf node for which all the nodes on the root-to-leaf path have the label b.

For a consistent labeling λ, let C_λ be the set of all nodes v satisfying two properties: (i) λ(u) = b for all nodes u on the unique path from a root of Γ_b to v (other than v itself), and (ii) λ(v) ≠ b. Let . We observe the following two facts.

• (a)  
  For every consistent labeling λ, the set is a minimal hitting set for T_b .
• (b)  
  Every node v of T_b belongs to at least one set of the form for some consistent labeling λ.

To prove (a), we claim that is a hitting set. Consider any hyperedge X of T_b , consisting of a root-to-leaf path P in Γ_b . If all nodes on P have label b, then the leaf node of P is , and hence X intersects . Otherwise, consider the first node v on the path P that has a label unequal to b. Thus, , and again X intersects and is a hitting set. We now argue that it is minimal. If we delete from , then would be disjoint from the hyperedge X consisting of the root-to-leaf path to . If we delete some other , then a hyperedge X that passes through v does not pass through any other node of on its way from root to leaf, and so would be disjoint from X.

To prove (b), we simply choose any consistent labeling λ such that λ(u) = b for all nodes u on the unique path from a root of Γ_b to v (other than v itself), and λ(v) ≠ b.

Now, we consider the size of a set of the form . Since contains b − 1 nodes from each of the first r − 1 levels of the trees in Γ_b , and b from the lowest level, we have

We define k = (r − 1)(b − 1) + b. Since each set is a minimal hitting set of size k, from (b) we see that the union U(k) of all minimal hitting sets of size k is the entire node set of T_b .

The number of nodes in T_b is greater than b^r , and hence |U(k)| > b^r . Since k ⩽ br, we have that |U(k)| > b^r ⩾ (k/r)^r = r^−r k^r . □

Zoom In Zoom Out Reset image size

These theoretical result establish justification for why a set of core nodes might be identifiable—if the core is a minimal hitting set, it is certainly contained in a set that has size independent of the graph. Next, we consider the case when the core may not be a minimal hitting set.

Here we present results on which types of nodes in a planted hitting set C must be contained in U(|C|) when the hitting set is itself not minimal. This matters in practice, when C may not be minimal.

2.2.1. Greedy matchings intersect the planted hitting set

One first results are based on finding hitting sets with a greedy algorithm for the set cover problem. The classical algorithm is simple (algorithm 1): loop through each hyperedge and if no vertex in the current hyperedge is in the current cover S, add all of the nodes in the hyperedge to S. The greedy algorithm produces a set that is both a hitting set and a maximal matching. To see that it is a hitting set, suppose that all nodes in a hyperedge h were not added. Then h would have been added to S at the time the algorithm processed it. The output is a maximal matching because if we could append another hyperedge h to S, then h would have already been added to S when the algorithm processed it.

Algorithm 1. Maximal matching r-approximation to the minimum hitting set that intersects the core.

1: Input: hypergraph G = (V, E) of rank r

2: Output: set cover S with |S| ⩽ rk*.

3: S ← ∅

4: for (u1, ..., ui ) ∈ E do

5:  if u1, ..., ui ∉ S then

6: S ← S ∪ {u1, ..., ui }

7:  end if

8: end for

9: return S

Let k* be the minimum hitting set size (the smallest size of all minimal hitting sets). The output of algorithm 1 is an r-approximation if the hypergraph G is an r-uniform hypergraph: in the worst case, any hitting set contains at least one of r nodes from each hyperedge, and we therefore have k* ⩾ |S|/r. It turns out that this greedy algorithm must also partially overlap with the planted hitting set. We formalize this in the following lemma.

Lemma 7. Let |B| ⩽ bk* for some hitting set B. If the input to algorithm 1 is a rank-r hypergraph, then the output S satisfies

Proof. Let r₁ be the number of vertices in the hyperedge containing the least vertices. The set S contains within itself all vertices from h hyperedges where h satisfies h ⩽ |S|/r₁ ⩽ rk*/r₁. Since B is a hitting set, it must contain at least one vertex from each of the h hyperedges in S. From this, we obtain . □

Lemma 7 guarantees that the greedy algorithm will output a result that overlaps any hitting set, including the planted one. Thus, we immediately get the following corollary.

Corollary 8. If the planted hitting set C has size |C| ⩽ ck* then the output of algorithm 1 is a set S with , i.e., S intersects at least a fraction of of C.

We can process the hyperedges in any order within algorithm 1, and this will be important for our practical recovery algorithm that we develop later. Another immediate corollary of lemma 7 says that regardless of the processing, the outputs must be fairly similar.

Corollary 9. Any two outputs S₁ and S₂ of algorithm 1 satisfy .

2.2.2. Classes of nodes that must be in U(|C|)

In this section we show that if we make additional assumptions on the structure of the problem, it becomes much easier. Most research that studies guarantees on planted structure recovery in graphs (e.g., community detection or planted clique detection) already makes these types of assumptions in order to make the problem feasible. The fact that we can do anything without such assumptions is quite remarkable.

More specifically, we show here that under certain stochastic-block-model-like assumptions for three-uniform hypergraphs laid out in this section—which would already be standard in other graph recovery problems—we can reduce the size of the UMHS (and hence of the upper bound of the size of the output of our algorithm) from O(k³) in the general case to O(k² log k) in this special structured case.

We emphasize that our main results and the algorithms we use for analyzing data are purely combinatorial, making no assumption on this type of probabilistic structure. And the algorithms we develop later perform extremely well even when no such structure is assumed. Instead, we simply wish to highlight that some of our bounds can be improved under random hypergraph models. We also have an additional goal of introducing our problem to the rich literature on finding planted structure in random graphs.

Let us assume that the hyperedges are generated according to a SBM for hypergraphs [28]. One block will be the core C and the other the fringe nodes F. We assume that there is zero probability of a hyperedge containing only nodes in F. Explicitly, we will state that the probability of a hyperedge between nodes in C is p while the probability of a hyperedge containing at least one node in C and at least one node in F is q.

We first provide a lemma on the independence number of hypergraphs drawn from the hypergraph SBM. This will help us control the size of |U(|C|)|.

Lemma 12. Let α(G) be the independence number of an r-uniform hypergraph G drawn from the SBM on n vertices. Then

Proof. We follow a proof technique common in the combinatorics literature [41]. Let , S₁, ..., S_z the size-k subsets of vertices of G, and X_i an indicator random variable for S_i being an independent set of G, so X_i = 1 only happens when all possible hyperedges among the vertices of S_i do not appear in the hyperedge set of G. Note that this happens with probability . Thus,

so that , as desired. □

This lemma helps us prove a result for three-uniform hypergraphs.

Theorem 13. For three-uniform hypergraphs,

with x as defined in [19].

Proof. First, α(G) = |G| − k* [34, theorem 3.15], so α(C) = |C| − k* and k* = |C| − α(C) ⩾ |C| − 9 ln |C|/p − 2, where the inequality follows from lemma 12 and the inequality holds with probability at least . For three-uniform hypergraphs, [19, theorem 18]. □

Theorem 13 enables us to find a small set J that contains the core C with high probability.

Theorem 14. Let C with |C| = k be a planted hitting set in a three-uniform hypergraph drawn from the SBM parameterized by p and q with ck nodes for some c ⩾ 1. Then with high probability in k, we can find a set J with |J| ⩽ O(k² ln k + k² x) + o(k³) that is guaranteed to contain C.

Proof. The number of ways to link a vertex in the core to two nodes outside the core is so that the probability of a node having at least one hyperedge to two nodes outside the core is . Thus w^k is the probability of each of the nodes in the core having at least one hyperedge to two nodes outside the core. This probability tends to 1 as k → ∞, so by using lemma 10, C ⊆ U(|C|) with probability tending to 1. Setting J = U(|C|) and using theorem 13 gives the result. □

Of course, the above theorem is only useful if we have a bound on the quantity x since only in that case are we able to improve our bound on the size of J from O(k³) to O(k² log k). Absent any additional information, x ⩽ k* [19].

In the following section, we build a practical algorithm for recovery of planted hitting sets based on the UMHS, the theory for which has been examined so far.

The five datasets we use broadly fall into three broad classes based on the types of planted hitting problems we derive from them. The first group is three email datasets (Enron, Avocado, and W3C), where the planted hitting set is a group of people at an organization, and hyperedges come from emails involving multiple addresses. Next, in the Digital Bibliography & Library Project (DBLP) dataset, a planted hitting set is a set of authors who publish at the same conference in a given year, and we consider several such conferences. Finally, in the Math Stack Exchange tagging dataset, the core is a one-hop neighborhood of a node, which is a hitting set for the two-hop neighborhood of the node; again, we consider several hitting sets. In this sense, the DBLP and tagging datasets are collections of hypergraphs with core-fringe structure. We now provide additional details, and table 1 lists summary statistics of the datasets.

Enron [ 39 ], Avocado ¹ , and W3C [ 16 ]. The hyperedges in these datasets are emails, where the nodes are the sender and all receivers (more specifically, their email addresses). Repeated hyperedges are discarded. In the Enron data, the core is a set of 150 employees whose email was made public when the company was under United States federal investigation. The Avocado corpus comes from a now-defunct technology company, where the core are employee email accounts (we exclude email accounts associated with conference rooms or mailing lists from the core). Finally, the W3C dataset comes from emails on mailing lists related to W3C; the core is all email addresses with a w3c.org domain.

DBLP. DBLP is an online computer science bibliography. We construct a hyperedges from coauthorship data in conference proceedings. We randomly sampled 50 conferences and constructed a set of core nodes C from the authors of a given conference in a randomly selected year. We then took the core-fringe hypergraph to be all hyperedges involving at least one of these authors. In total, we have 50 core-fringe hypergraphs.

Math tags [ 5 ]. This dataset comes from tags applied to questions on the Math Stack Exchange web site ² . Hyperedges are sets of tags that have been applied to the same question. We sampled 50 tags with relatively small cores and then formed a core set of nodes C from the one-hop neighborhood of that tag, i.e., from the tag and all tags that appear as co-tags with the tag. The set C is then a planted hitting set for the two-hop neighborhood of that tag (i.e., all hyperedges containing at least one tag from the planted hitting set C). In total, we again have 50 core-fringe hypergraphs.

We constructed two types of filtered hypergraph datasets. First, we constructed three-, four-, and five-uniform hypergraphs (derived as sub-hypergraphs). By imposing uniformity, we can facilitate comparison of UMHS performance to that of other centrality-based algorithms which work on only uniform hypergraphs (in particular, H- and Z-eigenvector centrality). This also lets us study the performance of our algorithm as we change the rank of the hypergraph. In addition, since our algorithm naturally handles nonuniform hypergraphs, we also constructed nonuniform sub-hypergraphs of rank 25 (in the Stack Exchange data, posts have at most five tags, so we include the entire hypergraph for this data). Limiting the rank to 25 cuts out outliers. In particular, it removes large mailing lists in email data and specialized papers with many authors. This subsampling omits a relatively small fraction of hyperedges—11% for the Enron dataset, 1% for the Avocado dataset, and 0.2% for the W3C dataset.

We tested the UMHS algorithm on several datasets, and it outperforms other algorithms consistently. For baselines, we use two techniques. First, we use notions of network centrality developed for hypergraphs with the idea that nodes in the core could be identified via large centrality scores. Specifically, we compare against

• (a)  
  hypergraph degree centrality (the number of hyperedges in which a node appears) [38];
• (b)  
  clique graph eigenvector (eigenvector centrality on the weighted clique graph, where w_ij is the number of hyperedges containing i and j) [4];
• (c)  
  PageRank on the weighted clique graph [47];
• (d)  
  Z-eigenvector hypergraph centrality [4]; and
• (e)  
  H-eigenvector hypergraph centrality [4].

Second, we use notions of network core-periphery decompositions, where we expect that nodes in C will be identified as 'core' in this sense. We use two algorithms:

• (a)  
  Borgatti–Everett network core-periphery scores [12] in the weighted clique graph; and
• (b)  
  the k-core decomposition [52] based on hypergraph degree.

All of these methods work equally well for uniform and non-uniform hypergraphs, except for Z-eigenvector and H-eigenvector eigenvector centrality, which are only designed for uniform hypergraphs. All of these methods also induce an ordering on the nodes. We induce an ordering on the output of algorithm 2 by degree and then sort the remaining nodes (those not in the output of algorithm 2) in order by degree. With an ordering on the nodes, we measure performance in terms of precision at core size, i.e., the fraction of the first |C| in the ordering that are in C, as well as area under the precision-recall curve (AUPRC). We use AUPRC as opposed to area under the receiver operating characteristic (ROC) curve due to class imbalance [20]; namely, most nodes are not in the core.

Table 2 reports the results of all methods on all datasets. In the case of nonuniform hypergraphs, UMHS is superior to all other baselines in terms of both precision at core size and AUPRC by substantial margins. With regards to the uniform sub-hypergraphs, UMHS out-performs the baselines by wide margins on the Enron, Avocado, and Math tags datasets for all uniformities r in terms of precision at core size. UMHS also does well for the three-regular W3C hypergraphs. On DBLP and the other W3C hypergraphs, projected PageRank and the simple degree heuristic seem to perform well, although our algorithm still outperforms them on a large share of samples. There are similar trends in terms of AUPRC, with UMHS performing the best on the same set of datasets from above; and in this case, UMHS is more competitive even for the datasets where it is weakest—the four-uniform and five-uniform W3C hypergraphs, and even the DBLP hypergraphs.

Overall, the performance of many algorithms degrades as we increase the uniformity of the hypergraph. This makes sense in general, as the core nodes are increasingly hidden in larger hyperedges. In the case of UMHS, we have a more specific interpretation of what this means. As the hyperedges get larger, there may be cases of hyperedges that contain just one node in the core C, and the rest in the fringe. However, by the greedy structure of algorithm 1, we would put all nodes in the hitting set. Furthermore, the bounds in corollaries 8 and 9 also degrade as we increase the uniformity r. Nevertheless, our proposed UMHS algorithm still outperforms the baselines at an aggregate level.

Our UMHS algorithm (algorithm 2) has a single tuning parameter, which is the number of iterations N, i.e., the number of calls to the sub-routine for greedy maximal matching (algorithm 1). Here we examine performance of UMHS as a function of N. Specifically, we analyze:

• (a)  
  the fraction of core nodes in the planted hitting set that are recovered and
• (b)  
  the output size of algorithm 2 as a function of the number of iterations

Figure 3 shows these statistics for the three email datasets.

Zoom In Zoom Out Reset image size

We highlight a couple of important findings. First, we only need around 50 iterations to achieve high recovery rates. Each iteration is fast, and the entirety of the algorithm's running time takes at most a few minutes on the larger datasets. Second, the UMHS size tends to increase sharply with a few iterations and then levels off sharply. These results are consistent with our theory: theorem 3 and corollary 8 both provide theoretical justification for why the output should not grow too large.

The data that support the findings of this study are openly available at the following URL/DOI: https://github. com/ilyaamburg/Hypergraph-Planted-Hitting-Set-Recovery.