HyperANF: Approximating the Neighbourhood Function of Very Large Graphs on a Budget

1 Introduction

• The neighbourhood function counts ordered node pairs ⟨x, y⟩ for which y is reachable from x in fewer than t steps.It describes how quickly the average ball around each node expands and can be used to estimate effective diameter.Source: §1 · p. 1
• HyperANF combines HyperLogLog counters using broadword programming, improving ANF’s speed and scalability.The register size is doubly logarithmic in the number of graph nodes, giving O(n log log n) memory at fixed precision, compared with ANF’s O(n log n).Source: §1 · p. 1
• HyperANF computes neighbourhood functions for graphs with more than one billion nodes in a few hours, with small error and good confidence, on a standard workstation.The reported workstation had 128 GB of RAM.Source: §1 · pp. 1–2
• The index of dispersion of shortest-path distances distinguishes proper social networks from web graphs in a natural way.The paper names this statistic the SPID.Source: §1 · p. 2

2 Related work

• ANF, implemented in snap, approximates neighbourhood functions on medium-sized graphs, but its large memory footprint prevents its use on large graphs.The authors therefore limit timing comparisons with snap to relatively small networks.Source: §2 · p. 2
• HyperANF computes the neighbourhood function of HADI’s 2-billion-link Kronecker graph in less than fifteen minutes on a laptop; HADI took half an hour on 90 machines.The paper notes that this is the only published HADI performance result it could compare against.Source: §2 · p. 2
• Before ANF, most published results relied on a few breadth-first visits from uniformly sampled nodes, without provable statistical accuracy or precision.The paper contrasts these methods with Cohen’s work, which has strong theoretical guarantees but was experimentally less scalable than ANF.Source: §2 · p. 2

3.1 HyperLogLog counters

• HyperLogLog estimates distinct stream items with relative standard deviation at most 1.06/√m and uses about (1 + o(1)) · m log log(n/m) bits of space.The paper assumes m ≥ 64 and registers of ⌈log log n⌉ bits.Source: §3.1 · p. 3

3.2 The HyperANF algorithm

• HyperANF keeps one HyperLogLog counter per node; at iteration t, the counter represents the radius-t ball, and summing counter estimates gives an almost unbiased estimate of NG(t).Counter union is implemented by taking register-wise maxima.Source: §3.2 · pp. 3–4

3.3 HyperANF at hyper speed

• About 13× faster register maximization produced a sixfold overall speed improvement in typical web-graph cases with b=8.The maximization speedup applies to graphs of up to 2^32 nodes; maximization accounts for about 90% of computation time in the cited cases.Source: §3.3 · p. 5
• Task decomposition parallelizes node segments across threads, while systolic mode skips nodes not signalled by changing counters.Task decomposition is reported to improve performance linearly with the number of cores; systolic mode begins when fewer than one quarter of counters change.Source: §3.3 · pp. 5–6
• Tracking modified counters skips maximization with unchanged counters, which cannot change downstream results and yields speedup as most counters stabilize.The optimization also avoids writing unchanged counters to disk.Source: §3.3 · p. 5

3.4 Correctness, errors and memory usage

• The neighbourhood-function estimate is asymptotically almost unbiased and has the same relative standard deviation as the individual counters.For each point, the paper gives a relative-error bound of kηm with confidence 1 − 4/(9k²).Source: §3.4 · pp. 6–7
• For a one-billion-node graph, a 9.37% relative standard deviation in every iteration requires 74.5 GB for registers, compared with 550 GB for snap.The registers are the only significant memory requirement in this setup; the graph can be kept on disk and mapped into memory.Source: §3.4 · p. 7

4 Deriving useful data

• The distance cdf H_G(t) is N_G(t) divided by its maximum; its estimator is almost unbiased with error 2ε and confidence 1−(k+1)δ over a fixed sequence of k points.The cdf expresses the fraction of reachable pairs at distance at most t.Source: §4 · pp. 7–8
• Precise statements across all t require very high initial precision; in practice, only a small finite set of cdf points supports direct statements.The authors say direct confidence intervals for average distance and higher moments are impractical.Source: §4 · p. 8
• 1 instead of ℓ+1 is reported as the effective diameter after one-step-early stopping in the two-clique bridge example, where the last cross-clique increment is ≈k².At the final step, nodes in the right clique become reachable from the first clique, sharply increasing the normalization factor.Source: §4 · p. 8, Figure 2 · p. 9
• After the 90th percentile, distance-cdf flatness makes good effective-diameter upper bounds almost impossible without very high precision; interval bracketing yields confidence 1−3δ.The interval procedure brackets α using error-adjusted cdf estimates.Source: §4 · pp. 9–10
• 2εn² is the relative error bound for a density point under the stated generic lower bound; variance-estimation bounds are likewise unusable.The variance result establishes that precision and confidence are possible in principle, but the resulting bounds are unusable.Source: §4 · pp. 10–11
• For moments, many lower-precision neighbourhood-function samples are more useful than a few high-precision samples, because derived-value distributions can be estimated by averaging.The authors report that this sampling approach works well.Source: §4 · p. 11

5 SPID

• The proposed index addresses the search for a property distinguishing human-interaction social networks from web-based graphs that share several social-network properties.The section frames average distance and effective diameter as examples of indices derived from aggregated distance data.Source: §5 · p. 11
• SPID is the distance distribution’s variance-to-mean ratio; values above 1 indicate web-like networks, while values below 1 indicate properly social networks.The classification follows the usual distinction between over-dispersed and under-dispersed distributions.Source: §5 · p. 11
• The intuition is that properly social networks favor short connections, whereas long connections are not uncommon on the web.Figure 3 plots the cumulative distribution of 100 HyperANF SPID values for cnr-2000 alongside normal samples of sizes 100 and 10,000.Source: §5 · p. 12, Figure 3 · p. 12
• 2.49 is the SPID inferred from cnr-2000’s exact neighbourhood function; 100 HyperANF estimates had mean 2.489 and standard deviation 0.9.The estimates approximately followed a normal distribution, though some pathological cases were non-Gaussian but unimodal.Source: §5 · p. 12

6 Experiments

• HyperANF is two orders of magnitude faster than snap on the tested hardware; its Kronecker-graph comparison with HADI is explicitly described as unfair.The HADI comparison is unfair because HADI can scale across arbitrarily many machines, whereas HyperANF is limited by available memory.Source: Table 1 · p. 13, §6 · p. 15
• The experiments study a wide and diverse dataset, computing effective diameter or average path length on very large graphs with precise statistical guarantees.The authors identify the Altavista dataset as poor: 53.74% of its nodes are dangling, and its giant component is less than 4% of the graph.Source: §6 · pp. 12–13
• Table 2 reports SPID, average distance, and interpolated effective diameter with empirical statistics for web, proper social, and host-quotient graphs.The uk@10E6 and uk@10E7 datasets simulate smaller crawls of uk-2007-05.Source: Table 2 · p. 14
• Across 100 runs, relative standard deviation was 9.37% for all graphs except Altavista, at 13.25%; the authors suggest low-precision runs when termination is by stabilisation.The experiments ran to stabilisation; computations for SPID usually required an order of magnitude more iterations than effective-diameter computations.Source: §6 · p. 15
• Effective diameter and average distance are essentially linearly correlated, approximately following 2x/3 + 1 across social and web networks.Average distance is parameter-free and had lower empirical standard deviation than effective diameter in a posteriori computations.Source: §6 · p. 15, Figure 4 · p. 15
• SPID values are mostly below 1 for social networks and above 1 for web graphs; host graphs resemble social networks, and this pattern holds for directed and undirected graphs.SPID shows no correlation with graph size or density, and the authors report that it distinguishes the dataset’s graph types where average distance does not.Source: §6 · p. 16
• Symmetrising graphs lowers average distance and SPID and loses structural information; its stated advantage is fewer iterations to compute the neighbourhood function.The authors note that available web snapshots come from breadth-first crawls, so symmetrisation cannot be expected to produce an average distance greater than twice the crawl’s radius.Source: §6 · p. 16

7 Future work

• A Pregel implementation would send changed counters to predecessors and combine incoming counters, with small communication volumes due to HyperLogLog counters.The authors describe synchronous node-to-node messaging as the appropriate framework for this diffusing computation.Source: §7 · p. 17
• HyperANF can also build radius distributions and related closeness-centrality measures, beyond the paper’s focus on SPID.Source: §7 · p. 17

• HyperANF can run very large graphs to stabilisation, computing data with statistical guarantees.Source: §8 · p. 18
• HyperANF improves on original ANF techniques through HyperLogLog counters, fast broadword combination, and systolic computation.Source: §8 · p. 18
• The paper identifies spid as its main conceptual contribution, requiring an order of magnitude more iterations than an effective-diameter estimate.Source: §8 · p. 18