Огляд алгоритмів стиснення графів

Дана робота описує способи стиснення насамперед соціальних(графи зв'язків між користувачами в соціальних мережах) і Web-графів(графи посилань між сайтами).

Більшість алгоритмів на графах добре вивчені і спроектовані з розрахунку того, що можливий довільний доступ до елементів графа, на даний момент розміри соціальних графів перевершують RAM середньостатистичної машини за розміром, але в теж час легко вміщаються на жорсткому диску. Компромисным варіантом є стиск даних з можливістю швидкого доступу до них певних запитів. Ми сконцентруємося на двох:
а) отримати список ребер для певної вершини
б) дізнатися з'єднуються чи 2 вершини.

Сучасні алгоритми дозволяють стискати дані до 1-5 біт на посилання, що робить можливим роботу з подібною базою на середньостатистичної машині. Мене спонукало написати цю статтю саме бажання вмістити базу друзів vkontakte в 32GB оперативної пам'яті, що з урахуванням того, що зараз там близько 300M акаунтів з середнім ступенем вершини близько 100 уявляється цілком реалістичним. Саме на цій базі я буду проводити свої експерименти.

Загальними властивостями, що нас цікавлять графів є
а) те що вони великі, 1е6 — 1е9 і більше верхин і порядку 1е9 ребер — що унеможливлює роботу з ними безпосередньо у пам'яті, але дозволяє без проблем зберігати їх навіть на одному жорсткому диску. На сайті law.di.unimi.it/datasets.php представлений весь широкий спектр подібних баз.
б) рапредление ступенів(degree) вершин, та й взагалі всі важливі частотые характеристики описується степеневою залежністю(Power-Law) як мінімум асимптотично.
в) вони зріджені. Середня ступінь вершини ~ 100-1000.
г) вершини схожі — ймовірність того що у вас спільний друг більше для пов'язаних вершин.

Boldi і Vigna.
В даній роботі граф в «природному», стислому вигляді буде представлятся масивом списків:

node1 -> link11,link12,link13...
node2 -> link21,link22,link23....
....

Де link[i,j] < link[i,j+1].


Node Node Node
15 11 13,15,16,17,18,19,23,24,203,315,1034
16 10 15,16,17,22,23,24,315,316,317,3041
17 0
18 5 13,15,16,17,50
Таблиця 1. Природне кодування графа. (Приклад взято з роботи [2])

Назвемо різницю між індексами двох посилань «гепом».

Gap[i,j] = link[i,j-1] - link[i,j] 


Першою з сімей алгоритмів компресії є методи, що використовують наступні 2 основних підходи:
а) Експлуатація локальності вершин. Вершини частіше посилаються на «близькі» вершини, ніж на «далекі».
б) Експлуатація схожості вершин. «Близькі» вершини посилаються на одні і ті ж вершини.

У цих двох твердженнях криється парадокс — термін «близькості» вершин можна описати так само через схожість, тоді наші затвердження перетворяться в трюїзм. Саме в роз'ясненні поняття «близькості» і є основна відмінність між випробуваними мною алгоритмами.

Перша робота на цю тему-це очевидно K. Randall [1]. В ній був досліджений веб-граф ще здорової Altavista, і було виявлено, що більшість посилань ( 80% ) на графі локальні і мають велику кількість загальних посилань і було запропоновано використовувати наступне референтне кодування:
— нова вершина кодується як посилання на «схожу» + список додавань і вилучень, який, у свою чергу, кодується гепами + nibble coding.
Хлопці скрутили альтависту до 5бит за посилання ( я буду намагатися наводити найгірші результати стиснення в роботах ). Даний підхід отримав великий розвиток в роботах Paolo Boldi і Sebastiano Vigna.

Ними було запропоновано більш складний метод референтного кодування, представлений в таблиці 1. Кожна вершина може мати одну посилання на «схожу», RefNr кодує різниця між поточною вершиною і нею, якщо RefNr дорівнює нулю означає вершина не має посилання. Copy list являє з себе біт-лист, який кодує які вершини необхідно забрати за посиланням — якщо відповідний біт Copy list дорівнює 1, то дана вершина так само належить і кодованої. Потім Copylist так само кодується RLE подібним алгоритмом і перетворюється в CopyBlocks:
01110011010 -> 0,0,2,1,1,0,0

Ми записуємо довжину — 1 для кожного повторюваного блоку значення першого блоку ( 1 або 0 ), а решта в кінці нулі можна відкинути.

Залишок вершин перетворюється в гепи, окремо кодирются інтервали нулів (тут експлуатується особливу властивість веб-графів, мова про який піде нижче) а решта гепи(Residuals) записуються кодировнными одним з цифрових кодів (Golomb,Elias Gamma і як екстремум Huffman).

Як видно з таблиці 2, дане кодування може бути багаторівневим — ступінь цієї багаторівневості є одним з параметром кодувальника L, при великому L швидкість кодування, а також розкодування падає, але ступінь компресії, збільшується.

Вершина Ступінь вершини RefNr copy-блоків Copy blocks Кількість інтервалів інтервали(відносний лівий індекс) довжини інтервалів залишок(Residual)
... ... ... ... ... ... ... ... ...
15 11 0 2 0,2 3,0 5,189,11,718
16 10 1 7 0,0,2,1,1,0,0 1 600 0 12,3018
17 0
18 5 3 1 4 0 50
... ... ... ... ... ... ... ... ...
Таблиця 2. Спосіб референтного кодування, запропонованого Boldi і Vigna для даних з таблиці 1. [2]

Розподіл Гепів у базах краулеров так само підкоряється Power-Law законом.


Малюнок 1. Розподіл «Гепів» в снапшоти .uk сайтів — 18.5 М сторінок.

Що дозволило сказати «близькі» облікові записи даються нам згори у вигляді впорядкованих даних від вебкраулеров. І далі вже розвивати роботу по зазначеним вище двом напрямкам: кодувати список ребер як модифікацію однієї з попередньої вершини (референтне кодування), зберігати список ребер у вигляді «Гепів» ( Gap[i,0] = Node[i] — link[i,0] ) — і, використовуючи частотну характеристику, виявлену вище — кодувати даний список одним з численних цілочисельних кодів. Треба сказати, що вийшло у них непогано: 2-5 bit посилання [4]. В [2] і [3] запропоновано навіть більш прості методи референтного кодування LM і SSL які кодують дані невеликими блоками. Результат перевершує або скоріше можна порівняти з BV алгоритмом. Від себе хочу додати, що навіть просте кодування гепами дає сумірний результат на Web — базах і одночасно всі методи використовують локальну «схожість» помітно пасують на соціальних базах.

У соціальних графах — даний ефект, схоже не спостерігається — на рисунку 2 представлено розподілу гепів за різними шматками бази даних vkontakte. Цікаво, що для першого мільйона акаунтів log/log закон для Гепів насправді виконується. Але зі збільшенням кількості даних. Розподіл гепів стає все більш і більш «білим».




Вибірка 50к. Вибірка 100к. Вибірка 2М.
Малюнок 2. Розподіл гепів по базі друзів vkontakte.


Малюнок 3. Матриця суміжності графа, vkontakte.


Малюнок 4. Матриця суміжності до та після кластеризації. 100к користувачів.

На малюнку 3 предтавлена матриця суміжності графа друзів, у логарифмічному вигляді. Вона теж не вселяє особливих надій на компресію такого роду. Набагато цікавіше виглядають дані, якщо якимось чином, попередньо кластеризовать наш граф. Малюнок 4 показує матрицю суміжності після проходу MCL ( Markov Cluster Algorithm) кластеризатора. Матриця відповідності стає майже діагональної (карта кольорів логарифмічна, тому яскравий жовтий означає на декілька порядків більша кількість зв'язків між елементами) — і для компресії таких даних вже відмінно підходить і WebGraph і багато інші алгоритми. (Asano [7] — на даний момент є найкращим наскільки мені відомо по компресії але і самим повільним щодо доступу до даних).

Але проблема в тому, що MCL в гіршому випадку кубичен по часу і квадратичен по пам'яті (http://micans.org/mcl/man/mclfaq.html#howfast). У житті все не так погано для симетричних графів ( яким соціальний граф майже є ) — але до лінійності йому всерівно далеко. Ще більшу проблему становить те, що граф не вміщується в пам'яті і треба придумувати розподілені техніки кластеризації — а це вже зовсім інша історія. Проміжне рішення даної проблеми придумали Alberto Apostolico і Guido Drovandi [1] — перенумерацію графа просто проходиа за нього пошуком в ширину (BFS-search). Таким чином гарантується, що деяка частина посилаються один на одного вершин буде мати близькі індекси. У своїй роботі вони пішли від GAP кодування і замінили його на досить складну модель посилального кодування, отримавши при цьому 1-3 біт на кодовану посилання. Насправді не дуже зрозуміла інтуїція за якою BFS повинен правильно компонувати вершини, але даний метод працює — я виконав дане кодування для вконтактовской бази і подивився хистограмму за гепам (Малюнок 5) — вона виглядає дуже багатообіцяюче. Є також пропозиції, використовувати Deep First Search замість BFS, а так само більш складні схеми переіндексації наприклад shingle reordering [7] — вони дають схожий приріст. Є ще один аргумент, чому BFS переіндексація має/може працювати — WebArchive бази добре кодуються, а вони отримані як раз послідовної індексацією живого інтернет графа.


Малюнок 5. Розподіл гепів по базі друзів vkontakte після BFS індексації. 100k вибірка

Gap Частка
1 83812263 7.69%
2 12872795 1.18%
3 10643810 0.98%
4 9097025 0.83%
5 7938058 0.73%
6 7032620 0.65%
7 6322451 0.58%
8 5733866 0.53%
9 5230160 0.48%
10 4837242 0.44%
top10 153520290 14.09%
Таблиця 2. Розподіл гепів по базі друзів vkontakte після BFS індексації. 1M вибірка



Друга робота Boldi і Vigna [5] присвячена теоретичному обґрунтуванню кодування списку гепів різними цифровими кодами а так само порівняння їх з Хафмман кодуванням як можливим upper bound. За основу береться те, що кодується величина розподілена за закону Ципфа. Верхня межа стиснення для різних параметрів альфа вийшла у них 4-13 біт на посилання. Для бази вконтакте даний спосіб кодування дав 18 біт на посилання. Що, звісно, вже не погано і дозволяє вмістити всю базу в RAMе, але дуже далеко від терретических оцінок, наведених в роботах. На малюнку 5 показано порівняння розподілу гепів після BFS індексації, з розподілом ципфа, максимально близьким до практичним даними ( альфа = 1.15). На малюнку 6 показано матриця суміжності для графа після BFS переіндексації — вона добре відображає причину поганого стиснення — діагональ прокреслена добре але загальний шум ще дуже великий у порівнянні з кластеризованой матрицьою. Дані «погані» результати також підтверджуються роботою [6].


Малюнок 6. Матриця суміжності бази vkontakte. Після BFS переиндексирования.

Бікліки
в) Експлуатація властивостей графа. Тут я знаю лише один вартий опису метод. А саме виділення дводольних подграфов (Bipartite graph) і генерація віртуальної вершини з'єднує 2 частини подграфа. Це дозволяє зменшити довжину списків вершин для кожної сторони двудольного графа. Ця задача в загальному випадку NP-повна але існує безліч хороших евристик для знаходження дводольних подграфов. Цей метод запропонований в [9], як і BV алгоритм породив безліч інших[10-11] і заслуговує більш детального розгляду. На рисунку 6 описана лише основна його ідея.
А1 -> А2 B2 C2 D3
B1 -> А2 B2 C2 D4
C1 -> А2 B2 C2 D5
А1 -> V D3
B1 -> V D4
C1 -> V D5
V -> A2 B2 C2
Малюнок 6. Кодування бикликами.

  1. A. Alberto and G. Drovandi: Graph compression by BFS.
  2. Sz. Grabowski and W. Bieniecki: Tight and simple Web graph compression.
  3. Sz. Grabowski and W. Bieniecki Merging adjacency lists for efficient Web graph compression
  4. P. Boldi and S. Vigna: The webgraph framework I: Compression techniques.
  5. P. Boldi and S. Vigna: The webgraph framework II: Codes for the World-Wide-Web. WebGraphII.pdf
  6. P. Boldi and S. Vigna. Permuting Web and Social Graphs.
  7. Flavio Chierichetti, Ravi Kumar. On Compressing Social Networks.
  8. Y. Asano, Y. Miyawaki, and T. Nishizeki: Efficient compression of web graphs.
  9. Gregory Buehrer, Kumar Chellapilla. A Scalable Pattern Mining Approach to Web Graph Compression with Communities
  10. Cecilia Hernandez, Gonzalo Navarro. Compressed Representations for Web and Social Graphs.
  11. F. Claude and G. Navarro: Fast and compact web graph representations.


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.