מגרעות של אלגוריתם Louvain למציאת קהילות

כתבתי כמה פוסטים על אלגוריתם Louvain. הגיעה העת לדון במגרעותיו.

בשנת 2007 פרסמו החוקרים סנטו פורטונטו ומארק ברטלמי בכתב העת היוקרתי PNAS מחקר שמכה גלים עד היום, בו הם הוכיחו מתמטית שמדד המודולריות סובל מפגם מבני חמור שנקרא מגבלת הרזולוציה. הבעיה גורסת כי בהינתן רשת גדולה מספיק, אלגוריתמים שממקסמים מודולריות, לא רק Louviain אבל כמובן גם הוא, יכשלו באופן שיטתי ומוחלט בזיהוי קהילות קטנות ואמיתיות, ויאחדו אותן לקהילות-על מלאכותיות שמספקות מצג שווא על אודות המבנה הטופולוגי של המערכת.

נוסחת המודולריות מנרמלת את הסטייה המקומית, באמצעות גורם גלובלי של הסכום הכולל 1/2m או חלוקה במספר הקשתות הכולל ברשת, שנסמנו L. פורטונטו וברטלמי פיתחו משוואה שבוחנת מצב בו ישנן שתי קהילות ברורות, מופרדות היטב, C₁ ו-C₂. לקהילות אלו יש מספר מועט של קשתות פנימיות l₁ ו-l₂, והן מקושרות ביניהן בקשר זעום של קשתות חיצוניות l₁₂. התנאי המתמטי שקובע שהמודולריות הגלובלית תיפגע מאיחוד קהילות אלו ולכן האלגוריתם יצדק וישאיר אותן נפרדות מנוסח כך: 

l₁l₂ > L/2 [ l₁₂ - 1/2L (d₁d₂) ] 

מה קורה במקרה של קהילות קטנות אך מובהקות לחלוטין? החוקרים בחנו מקרה קיצון שבו C₁ ו-C₂ הן שתי קליקות, קבוצות שכל הצמתים בתוכן מחוברים אלו לאלו, הקשורות זו לזו אך ורק דרך קשת אחת בודדת. על פי כל הגדרה חברתית או סמנטית, מדובר בשתי קהילות נפרדות. אולם, כאשר הזינו את הנתונים למשוואה גילו כי אם מספר הקשתות הפנימיות l בתוך הקליקות מקיים את אי-השוויון הבא:

l < √(L/2)

אזי המודולריות הגלובלית, Qᵦ של שתי הקהילות כגוף מאוחד, תהיה גדולה יותר מהמודולריות של החלוקה ההגיונית Qₐ של שתי קהילות נפרדות.

המשמעות של חסם הרזולוציה היא שאם רשת מכילה מיליארדי קשתות, הביטוי √(L/2) יהיה שווה למיליונים. כתוצאה מכך, קהילות סגורות לחלוטין שכוללות אלפי צמתים, ייבלעו בעיוורון מוחלט אל תוך מבני ענק, מאחר ולמודולריות משתלם יותר סטטיסטית לקבל את הקשת המקשרת הבודדת כקשת פנימית, בעוד שהעונש על איחוד אלפי הצמתים המיותרים נעלם מול ים הקשתות הכללי של הרשת.

קהילות במציאות הן לרוב אינן קליקות סגורות אלא עמומות, מה שמגדיל את מגבלת הרזולוציה והופך את נקודת העיוורון לעד רבע מגודל הרשת הכוללת L/4. בשל עיוות זה, חוקרים ממליצים לבחון בספקנות קהילות קטנות שמתגלות בגרפים גדולים.

בנוסף למגבלת הרזולוציה, ה-Louvain יוצר הילות מנותקות במידה שרירותית. הבעיה נעוצה שוב במנגנון החמדני שלוחץ למקסם את 𝑸 בשלב האגרגציה והפיכתן לצמתי-על. מכיוון שמעבר למחזור השני והלאה האלגוריתם רואה רק צמתי-על, פעמים רבות הוא נאלץ לשייך צומת א' או תת-קהילה מבודדת לתוך מגה-קהילה גדולה במיוחד. הצירוף אמנם מעלה את המודולריות הכללית, אך בפועל לצומת א' אין ולו קשת אחת המחברת אותו למי ממאות אלפי הצמתים שקיימים בתוך המגה-קהילה. התוצאה הסופית הבלתי מתקבלת על הדעת היא שלקהילות הסופיות יהיו מספר רכיבי קשירות לא-מחוברים כלל.

יתר על כן, הנטייה ל-Overfitting הוכחה באופן עקבי בניסויים. בגרפים אקראיים לחלוטין, האלגוריתם מנצל סטיות תקן מזעריות ואקראיות כדי לאסוף קבוצות נטולות הקשר, מייצר במודע קהילות מזויפות בעלות ערכי מודולריות גבוהים לכאורה, ומקשה על הפרדה בין אות לבין רעש.

תוסיפו לכך את בעיית הניוון, שמאופיינת בכך שכל הרצה מפיקה תוצאות חלוקה שונות, והאלגוריתם נתפס בקרב גורמים תיאורטיים כבעייתי לאשרור מחקרים קליניים שמצפים לחזרתיות עקבית ומוחלטת.

מגרעות של אלגוריתם Louvain למציאת קהילות

צריכים עזרה עם אלגוריתמים בגרפים? שיפורי אלגוריתמים? מחקר אלגוריתמי יישומי? צריכים עזרה עם גילוי ומניעת הונאות? דברו איתי:

שלמה יונה

מייסד ומדען ראשי, מתמטיקאי מחקר ופיתוח בע"מ

053-7326360

shlomo.yona@mathematic.ai 

https://mathematic.ai

פודקאסט על החברה ועליי, שלמה יונה, ואופן העבודה שלנו ואיתנו: A technical deep dive about Mathematic.ai