HyperANF

Overview

The HyperANF (Hyper-Approximate Neighborhood Function) algorithm estimates the average graph distance and the number of reachable nodes from each node using HyperLogLog counters. It provides a balance between accuracy and computational efficiency, making it well-suited for large-scale graphs where calculating exact distances is infeasible.

Related material of the algorithm:

• P. Boldi, M. Rosa, S. Vigna, HyperANF: Approximating the Neighbourhood Function of Very Large Graphs on a Budget (2011)

Concepts

Average Graph Distance

The average graph distance is a metric used to measure the average number of steps or edges required to traverse between any two nodes in a graph. It quantifies the overall connectivity or closeness of the nodes in the graph.

As described above, the average graph distance is typically calculated by performing graph traversals to find the shortest path between every pair of nodes, summing these distances, and dividing by the total number of node pairs to get the average.

Approximate Neighborhood Function (ANF)

Graph traversals can be computationally expensive and memory-intensive, especially for large-scale graphs. In such cases, approximate neighborhood function (ANF) algorithms are commonly used to estimate the average graph distance more efficiently.

ANF algorithms aim to estimate the neighborhood function (NF):

• The neighborhood function (NF) of a graph, denoted as N(t), returns the number of node pairs such that the two nodes can reach each other with t or fewer steps.
• The individual neighborhood function (INF) of a node x in a graph, denoted as N(x,t), returns the number of nodes that can be reached from x with t or fewer steps.
• In an undirected graph G = (V, E), the relationship between NF and INF is:

The NF can help to reveal some features of graphs, including the average graph distance:

The calculation of the above example graph is shown below:

However, it is very expensive to compute the NF exactly on large graphs. By approximating the neighborhood function, ANF algorithms can estimate the average graph distance without traversing the entire graph.

HyperLogLog Counter

HyperLogLog counter is used to count approximately the number of distinct elements (i.e., the cardinality) in a large set or stream of elements. Calculating the exact cardinality often requires an amount of memory proportional to the cardinality, which is impractical for very large data sets. HyperLoglog uses significantly less memory, with the space complexity as O(log(log n)) (this is the reason why these counters are called HyperLogLog).

A HyperLogLog counter can be viewed as an array of m = 2b registers, and each register is initialized to -∞. For example, b = 3, then M[0] = M[1] = ... = M[7] = -∞.

NOTE

The number of registers depends on the desired precision of the estimation. More registers can provide a more accurate estimation, but also require more memory.

First, each element x in the set is mapped into a fixed-size binary sequence by a hash function h(). For example, h(x) = 0100001110101....

Then, update the registers. For each element x in the set:

• Calculate the index i of the register by the integer value of the leftmost b bits of h(x), i.e., hb(x). In the example, i = hb(x) = 010 = 0*22 + 1*21 + 0*20 = 2.
• Let hb(x) be the sequence of remaining bits of h(x), and ρ(hb(x)) be the position of the leftmost 1 of hb(x). In the example, ρ(hb(x)) = ρ(0001110101...) = 4.
• Update register M[i] = max(M[i], ρ(hb(x))). In the example, M[2] = max(-∞, 4) = 4.

After reading all elements, the cardinality is calculated by the HyperLogLog counter as:

It is actually a normalized version of the harmonic mean of the 2M[i], where αm is a constant calculated by m as:

HyperANF

HyperANF is one popular ANF algorithm, it is a breakthrough improvement in terms of speed and scalability.

The algorithm is based on the observation that B(x,t), the set of reachable nodes from node x with distance t or less, satisfies

In the example graph below, node a has 3 adjacent edges (a,b), (a,c) and (a,d), so B(a,3) = B(b,2) ∪ B(c,2) ∪ B(d,2).

Instead of keeping track of B(x,t), the HyperANF algorithm employs HyperLogLog counters to simplify the computation process, as illustrated by the example graph above:

• Each node x is mapped to a binary representation h(x), and is assigned a HyperLogLog counter Cx(t). Set b = 2, so each counter has m = 2b = 4 registers.
• Cx(0) is then computed by the value of i and ρ. Note: we use 0 instead of -∞ for the calculation, the result is the same.
• In the t-th iteration, for each node x, the union of B(y,t-1) ((x,y)∈E) is implemented by combining the counters of all neighbors of node x, that is, maximizing the values of the counter of node x register by register.
• The values of all counters remain unchanged after 6 iterations because the diameter of the graph is 6.
• |B(x,t)| is computed in each iteration by the cardinality equation with the constant αm = 0.53243.

Since B(x,0) = {x}, then |N(x,t)| = |B(x,t)| - 1. In this example, the average graph distance computed by the algorithm is 3.2041. The exact average graph distance of this example is 3.

Considerations

• The HyperANF algorithm is typically best suited for connected graphs. For disconnected graphs, the algorithm may not provide accurate results.
• The algorithm treats all edges as undirected.
• Results are approximate due to the HyperLogLog estimation.

Example Graph

GQL
INSERT (A:default {_id: "A"}), (B:default {_id: "B"}),
       (C:default {_id: "C"}), (D:default {_id: "D"}),
       (E:default {_id: "E"}), (F:default {_id: "F"}),
       (G:default {_id: "G"}), (H:default {_id: "H"}),
       (I:default {_id: "I"}), (J:default {_id: "J"}),
       (G)-[:default]->(H), (H)-[:default]->(I),
       (I)-[:default]->(J), (J)-[:default]->(A),
       (A)-[:default]->(B), (A)-[:default]->(E),
       (E)-[:default]->(F), (B)-[:default]->(E),
       (B)-[:default]->(C), (C)-[:default]->(D)

Parameters

Run Mode

Returns:

GQL
CALL algo.hyperanf({
  maxIterations: 5,
  precision: 4
}) YIELD nodeId, reachable, closeness

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.hyperanf.stream({
  maxIterations: 10,
  precision: 10
}) YIELD nodeId, reachable, closeness
RETURN nodeId, reachable, closeness

Result:

Stats Mode

Returns:

GQL
CALL algo.hyperanf.stats({
  maxIterations: 10,
  precision: 10
}) YIELD nodeCount, avgGraphDistance, avgReachable, estimatedDiameter

Result: