Source-linked AI summary
Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks
Paolo Boldi, Marco Rosa, Massimo Santini, Sebastiano Vigna
TL;DR
Large social networks lack the URL ordering that supports effective web-graph compression, creating a need for scalable coordinate-free reordering. The paper introduces Layered Label Propagation, which mixes clustering and ordering for very large graphs. Combined with WebGraph, it substantially improves compression across web and social networks while supporting graphs with hundreds of millions to billions of nodes.
Problem
Web-graph compression relies on URL-based node ordering, but extending that ordering to general social networks is not straightforward.
Method
Layered Label Propagation mixes clusterings and orders to produce a scalable, parameter-free coordinate-free reordering.
Results
Layered Label Propagation with WebGraph provides major compression gains over known approaches across web graphs and social networks, averaging 25% over BFS.
Takeaways & Limitations
The resulting compressed data structure is coordinate-free and can support analysis of substantially larger graphs in main memory.
Takeaways & Limitations
The underlying optimization problem is NP-hard, so the approach relies on heuristics for practical cases; modularity-based variants also face a resolution limit on very large graphs.
Abstract
from arXiv · showhide
We continue the line of research on graph compression started with WebGraph, but we move our focus to the compression of social networks in a proper sense (e.g., LiveJournal): the approaches that have been used for a long time to compress web graphs rely on a specific ordering of the nodes (lexicographical URL ordering) whose extension to general social networks is not trivial. In this paper, we propose a solution that mixes clusterings and orders, and devise a new algorithm, called Layered Label Propagation, that builds on previous work on scalable clustering and can be used to reorder very large graphs (billions of nodes). Our implementation uses overdecomposition to perform aggressively on multi-core architecture, making it possible to reorder graphs of more than 600 millions nodes in a few hours. Experiments performed on a wide array of web graphs and social networks show that combining the order produced by the proposed algorithm with the WebGraph compression framework provides a major increase in compression with respect to all currently known techniques, both on web graphs and on social networks. These improvements make it possible to analyse in main memory significantly larger graphs.
1 Introduction
Large social and web graphs contain useful structural information for graph mining, but their size makes main-memory storage difficult. The paper frames compression and ordering as a way to support fast graph access while exploiting network regularities.
- Graph mining tasks such as outlier detection, interest-group identification, and centrality estimation can use a network’s acquaintance structure.
- Web and social graphs can require hundreds of terabytes of memory when represented through successor lists.The motivating examples include a web graph with at least 23.59 billion pages and Facebook with more than 500 million users and 65 billion friendship relations.
- Compressed data structures target fast amortised random access to edges, unlike compression schemes evaluated only by bits per link.The paper describes access in the order of a few hundred nanoseconds and excludes methods requiring large graph scans.
- WebGraph achieved less than 3 bits per link by exploiting neighbour similarity and link locality under lexicographic URL ordering.
- Because compression depends strongly on node order, the paper asks whether intrinsic orderings can replace URL-based information for non-web social networks.Intrinsic orderings use graph information rather than external information.
2 Problem Definition and Related Works
The paper formulates graph compression as finding a node permutation that minimizes bits per link for a chosen compression algorithm. It reviews intrinsic and extrinsic orderings, emphasizing their dependence on initial numbering, scalability, and access guarantees.
- Problem definition: For compression algorithm A, the objective is to find a node numbering π̂ minimizing ρ_A(G, π̂), the bits per link required to store graph G.
- Compression framework: The study focuses on WebGraph’s BV scheme, which relies on neighbour similarity and link locality and is treated as a de facto standard for large web-like graphs.
- Intrinsic methods: The optimization problem is NP-hard even in a mild version, so practical methods must rely on heuristics that use graph structure alone or external knowledge.
- Related work: Existing alternatives include lexicographic and Gray row orderings, shingle-based methods, multiscale arrangements, BFS-based methods, and Eulerian data structures.The Eulerian approach supports predecessor and successor queries but does not meet the paper’s compressed-data-structure access standard.
- Extrinsic orderings: URL ordering compresses web graphs effectively but cannot directly provide useful external information for non-web social networks.
- Coordinate-free orderings: Intrinsic reorderings can produce worse compression from random numbering than from URL ordering, motivating coordinate-free algorithms that are robust to initial order.
3 Our Contribution
The paper contributes scalable coordinate-free ordering techniques and evaluates them with WebGraph across web graphs and social networks. Layered Label Propagation is designed for billion-node graphs and yields major compression improvements over existing approaches.
- Contributions: The paper identifies two fitness measures for recovering web host structure and links successful coordinate-free orderings to their ability to guess that structure.
- Contributions: Layered Label Propagation combines clustering with ordering, scales to billions of nodes, and is parameter-free compared with previous coordinate-free orderings.
- Experimental results: Experiments combining Layered Label Propagation with WebGraph produce major compression gains across a wide array of web graphs and social networks.
- Experimental results: The largest evaluated graph contains more than 600 million nodes, one order of magnitude beyond any previously published result in this area.
- Additional application: The algorithm was also applied with excellent results to the Minimum Logarithmic Arrangement Problem.
4 Recovering Host information from a Random Permutation
The section evaluates whether intrinsic node orderings can recover host structure from randomly ordered web graphs, using host transitions and partition similarity. The experiment finds that recovering host structure from random order is the key property for coordinate-free compression, with BFS as the strong baseline.
- Host recovery: The study measures how well intrinsic orderings preserve the partition induced by web hosts.The motivation is that keeping nodes from the same host close supports compression.
- Measures: Host transition measures the fraction of adjacent nodes in an ordering that belong to different hosts.Lower host-transition values indicate fewer breaks between host-local runs.
- Measures: The ordering also induces a refinement of the host partition, whose appropriateness is compared with the original partition using Variation of Information.The refinement groups same-host nodes connected through adjacent same-host nodes in the ordering.
- Compared orderings: The evaluated orderings are Random, Natural, Gray, Shingle, BFS, and LLP.Natural means URL order for web graphs but presentation order for non-web social networks.
- Findings: Recovering host structure from random order is identified as the key property required for a coordinate-free algorithm.BFS is used as a strong baseline because it is the only previously proposed ordering reported to achieve this.
5 Label Propagation Algorithms
The section frames clustering as a route to reconstructing host information, then reviews scalable label-propagation methods and their limitations. APM is selected as a candidate, but its resolution parameter and heavy-tailed cluster sizes complicate producing a compression-friendly ordering.
- Motivation: Most existing intrinsic orderings compress poorly on randomly permuted graphs because they fail to reconstruct host information.The section therefore approaches host recovery as a clustering problem.
- Label propagation: Label propagation uses network structure alone, requires no predefined objective or prior community information, and runs locally in a few passes over the edges.Each node updates a cluster label over successive rounds using a local rule.
- Label propagation: Standard label propagation assigns each node the most frequent label in its neighborhood, allowing dense groups to reach consensus and expand.The update order is randomized at the beginning of each round.
- Limitations: Standard label propagation can produce one giant cluster containing most nodes, while modularity-based variants suffer from a resolution limit on very large graphs.These observations motivate testing additional constraints and alternative clustering algorithms.
- APM: APM introduces a resolution parameter γ that discounts large communities when selecting a node’s label, and guarantees a minimum final community density of γ/(γ + 1).When γ = 0, APM degenerates to standard label propagation.
- APM limitations: APM has no theoretical rule for choosing γ and produces a heavy-tailed cluster-size distribution, creating both many clusters and very large clusters.Good compression therefore requires ordering both the clusters and the nodes within each cluster.
6 Layered Label Propagation
Layered Label Propagation constructs compression-friendly node orderings by iteratively combining clusterings at multiple resolutions with prior orderings. The resulting multiresolution ordering improves compression and is largely independent of the graph’s initial permutation.
- Algorithm: LLP is an iterative label-propagation algorithm that produces a sequence of graph orderings.At each iteration, clustering labels are converted into an ordering.
- Multiresolution strategy: Different γ values expose graph structure at different resolutions, from coarse sparse clusters to fine dense clusters.The method uses this range of resolutions rather than selecting one universally optimal γ.
- Ordering rule: Nodes sharing a cluster label are kept close, while their previous relative order is preserved within each cluster.Clusters are ordered according to the prior order of their leader nodes.
- Parameterization: The output depends on the initial ordering and iteration parameters, but the multiresolution strategy chooses γk uniformly from {0} ∪ {2^-i, i = 0, . . . , K}.This parameter sequence mixes clusterings obtained at multiple resolutions.
- Results: The final multiresolution ordering outperforms fixed-γ alternatives and is essentially independent of the initial node permutation.Iterating Gray, lexicographic, or BFS orderings does not produce a significant improvement.
7 Parallel Implementation
The LLP implementation uses task decomposition and randomized updates to parallelize node processing on multicore architectures. Its design targets scalable execution while retaining efficient graph access through shared WebGraph data.
- Parallelization: Randomized update order allows many nodes to be updated in parallel without an ordering obstacle.LLP therefore fits the task-decomposition parallel-programming paradigm.
- Task decomposition: The implementation decomposes nodes into thousands of tasks that threads process dynamically.A thread picks up the first available task and solves it.
- Parameter boundary: Choosing γ greater than 1 is practically useless on large networks because it produces complete graph fragmentation.The practical parameter range consequently excludes such values.
- Scalability: Performance improves linearly with the number of cores under the task-based implementation.WebGraph supplies lightweight per-thread graph copies sharing the bitstream and associated information.
8 Experiments
Experiments evaluate LLP with WebGraph’s BV format on social and web graphs of varied sizes and characteristics. LLP+BV outperforms the compared coordinate-free method, while experimental settings trade compression quality against decompression speed.
- Dataset caveat: The altavista-nd dataset is considered poor because crawler-frontier nodes may be included and its giant component contains less than 4% of all nodes.This dataset characteristic constrains interpretation of results involving altavista-nd.
- Evaluation: The graphs are compressed in BV format using WebGraph, with performance measured in bits per link occupied by the graph file.The experiments focus on compression under different node orderings.
- Compression results: LLP+BV outperforms Apostolico–Drovandi at level 8 in all compared cases, significantly so on social networks and large web graphs.The comparison starts from randomly permuted graphs and uses the full BV compression power for this table.
- Implementation settings: Disabling intervalisation and limiting reference chains deteriorate compression results but make decompression extremely efficient for random access.These settings explain why the reported bits-per-link values differ from other tables.
- Comparison caveat: Apostolico–Drovandi performs badly on altavista-nd after random permutation, apparently because the dataset size leads to a poor node naming despite the initial BFS visit.The authors note that this issue requires further investigation.
9 Results
The experiments show that LLP achieves the strongest compression while remaining scalable, robust to initial ordering, and effective across web and social networks. Its gains reflect different roles for locality and similarity across graph types.
- LLP is extremely robust to the initial ordering of nodes, producing a coordinate-free compressed data structure with BV.
- Social networks are harder to compress than web graphs, suggesting an unexplained topological difference between the two graph types.
- The implementation scales linearly in arcs at approximately 80,000,000 arcs/s per iteration and approximately 800,000 arcs/s overall in the typical setting.
- Applying LLP to a web graph with 1 billion nodes and 50 billions arcs would require few hours, using 3n integers plus graph space.
- The combination of clusterings is linear in the number of nodes rather than arcs and has little impact on overall runtime.
- For LLP+BV, bits per link correlate more strongly with average gap cost than average distance cost, with coefficients 0.9681 and 0.1742, respectively.
- LLP uses locality and similarity differently: web-graph compression is driven by copied arcs, whereas social-network compression is established by average gap cost.
10 Conclusions and Future Work
The paper concludes that scalable coordinate-free techniques substantially improve compressed graph representations across web and social networks. It also identifies maximum-compression analysis without fast access as future work.
- The proposed techniques improve compressed data structures for web graphs and social networks significantly beyond the current state of the art.
- The techniques are scalable to billions of nodes because they require only a few linear passes over the graphs.
- 1.8 bits per link is achieved for the uk dataset relative to a BFS baseline.
- Without requiring fast access, uk compressed by LLP+BV reaches 1.21 bits per link, compared with 1.44 for Apostolico–Drovandi at maximum compression.
- The experiments required several thousands of hours of computation, with results planned for release as WebGraph property files and graphical representations.