کاوش الگوهای گراف یکی از ابزارهای بنیادین در تحلیل داده‌های گرافی است که در حوزه‌های گوناگونی مانند زیست‌فناوری، شیمی، مهندسی، تشخیص تقلب، تحلیل شبکه‌های اجتماعی و سیستم‌های پیشنهاددهنده کاربرد دارد. در این فرایند، الگوهای کوچک و معنادار مانند مثلث‌ها، حلقه‌ها، مسیرها و ساختارهای ستاره‌ای درون یک گراف بزرگ جستجو می‌شوند تا ساختارها و روابط پنهان آشکار گردند. این الگوها که به آن‌ها «موتیف» یا «نقش» نیز گفته می‌شود، به‌عنوان امضای ساختاری شبکه عمل می‌کنند و می‌توانند ویژگی‌های مهمی از شبکه را نمایان سازند. برای نمونه، در شبکه‌های اجتماعی، وجود تعداد زیادی مثلث نشان‌دهنده همبستگی و خوشه‌بندی بالاست، در حالی که در شبکه‌های زیستی، الگوهای خاص می‌توانند به عملکردهای مولکولی مشخصی اشاره کنند. با این حال، انجام دقیق این کار روی گراف‌های عظیم بسیار پرهزینه و زمان‌بر است، زیرا پیچیدگی محاسباتی آن با اندازه الگو به‌صورت نمایی رشد می‌کند. به بیان ساده، اگر اندازه الگو یک واحد افزایش یابد، حجم محاسبات ممکن است چندین برابر شود و این امر برای گراف‌هایی با میلیاردها گره و یال، عملاً غیرقابل تحمل می‌گردد. از این‌رو، در بسیاری از کاربردهای واقعی، تخمین تقریبی تعداد الگوها کافی است و نیازی به شمارش دقیق وجود ندارد. این رویکرد که «کاوش تقریبی الگوهای گراف» نامیده می‌شود، دقت را فدای سرعت می‌کند تا در زمان معقول و با خطای قابل‌قبول به نتیجه برسد. سیستم‌های خودکار مانند ASAP و Arya برای ساده‌سازی این فرایند ساخته شده‌اند و امکان استفاده از روش‌های نمونه‌گیری تعمیم‌یافته برای الگوهای مختلف را فراهم می‌کنند. این سیستم‌ها به کاربران اجازه می‌دهند بدون پیاده‌سازی دستی الگوریتم‌های پیچیده، به تحلیل گراف بپردازند و پارامترهای کلیدی مانند تعداد نمونه را به‌صورت خودکار تعیین کنند. با این وجود، این سیستم‌ها دو محدودیت اساسی دارند که مانع از پذیرش گسترده آن‌ها در عمل می‌شود و باعث می‌گردد که در بسیاری از سناریوهای واقعی، کارایی مطلوبی نداشته باشند.

نخستین محدودیت، سازوکار تعیین زمان توقف نمونه‌گیری است. سیستم‌های پیشین از روشی به نام «پروفایل خطا-تأخیر» استفاده می‌کنند که پیش از اجرای نمونه‌گیری، تعداد نمونه‌های موردنیاز را تخمین می‌زند. اما این تخمین به تعداد واقعی الگوها وابسته است، در حالی که همان تعداد واقعی قرار است از روی نمونه‌ها محاسبه شود. این وابستگی دوری باعث می‌شود که تضمین نظری محکمی برای دقت و اطمینان وجود نداشته باشد. به عبارت دیگر، سیستم برای تعیین تعداد نمونه به تخمینی از پاسخ نیاز دارد، اما همان پاسخ قرار است از روی نمونه‌ها به دست آید و این چرخه باطل، پایه نظری روش را سست می‌کند. در عمل نیز این روش بسیار ناپایدار است؛ به‌گونه‌ای که در اجراهای مختلف، تعداد نمونه‌های پیش‌بینی‌شده می‌تواند تفاوت‌های چشمگیری داشته باشد و حتی در برخی موارد به کلی شکست بخورد. برای مثال، در یک آزمایش مشخص، سه اجرای مختلف این روش برای یک گراف و الگوی یکسان، سه عدد کاملاً متفاوت را پیش‌بینی کردند که تفاوت میان آن‌ها تا ۲۵ برابر می‌رسید. این ناپایداری منجر به کندی شدید و اتلاف منابع محاسباتی می‌شود، زیرا ممکن است تعداد بسیار بیشتری نمونه از حد لازم کشیده شود و زمان اجرا به‌طور غیرضروری طولانی گردد. در برخی موارد حتی مشاهده شده که این روش در مدت ده ساعت به همگرایی نرسیده و عملاً بی‌نتیجه مانده است. محدودیت دوم، عملکرد ضعیف در مواردی است که الگوی موردجستجو بسیار کمیاب است و تنها تعداد اندکی از آن در گراف بزرگ وجود دارد. در چنین حالتی که به «سوزن در انبار کاه» تشبیه می‌شود، روش نمونه‌گیری همسایگی که در سیستم‌های پیشین به کار می‌رفت، در بیشتر نمونه‌ها موفق به یافتن الگو نمی‌شد و نرخ برخورد به شدت پایین می‌آمد. برای نمونه، در یک گراف بزرگ با الگوی چهار-کلیک، از میان صد میلیون نمونه‌برداری، تنها پنج نمونه موفق به یافتن الگو شدند که نرخ برخوردی در حدود پنج در صد میلیون را نشان می‌دهد. این امر باعث می‌شد که برای رسیدن به خطای قابل‌قبول، تعداد فوق‌العاده زیادی نمونه لازم باشد و در برخی موارد حتی از روش‌های دقیق نیز کندتر عمل کند. این مشکل به‌ویژه برای الگوهای متراکم و پیچیده که تجزیه آن‌ها دشوار است، شدیدتر می‌شود و کارایی سیستم را به‌شدت کاهش می‌دهد.

برای رفع مشکل ناپایداری در تعیین زمان توقف، پژوهش حاضر یک روش نوین «تشخیص همگرایی برخط» پیشنهاد می‌کند. برخلاف روش پیشین که پیش از اجرا اقدام به پیش‌بینی می‌کرد، این روش به‌صورت زنده و در حین اجرای نمونه‌گیری، آمار مربوط به نمونه‌ها را جمع‌آوری کرده و خطای تخمین را به‌طور پویا محاسبه می‌نماید. نمونه‌گیری زمانی متوقف می‌شود که خطای پیش‌بینی‌شده به زیر حد خطای تعیین‌شده توسط کاربر برسد. این روش تنها به نگهداری دو کمیت ساده نیاز دارد: مجموع مقادیر نمونه‌ها و مجموع مربعات آن‌ها. در پایان هر بازه مشخص، انحراف معیار محاسبه شده و خطای نسبی پیش‌بینی می‌شود. اگر این خطا کمتر از حد مجاز باشد، نمونه‌گیری متوقف و میانگین به‌عنوان تخمین نهایی گزارش می‌شود. اثبات ریاضی بر پایه قضیه حد مرکزی و قضیه اسلاتسکی نشان می‌دهد که احتمال قرار گرفتن خطای واقعی در محدوده خطای پیش‌بینی‌شده برابر با سطح اطمینان موردنظر است. این بدان معناست که روش پیشنهادی، برخلاف روش‌های پیشین، تضمین نظری محکمی برای اطمینان فراهم می‌کند. علاوه بر این، نقاط توقف تشخیص‌داده‌شده در اجراهای مختلف بسیار پایدار هستند و سربار محاسباتی آن‌ها ناچیز است، زیرا تنها جمع ساده و مجموع مربعات نمونه‌ها باید نگهداری شود. در نتیجه، این روش می‌تواند با تعداد نمونه‌های بسیار کمتر، به همان دقت برسد و سرعت اجرا را به‌طور چشمگیری افزایش دهد. آزمایش‌ها نشان می‌دهد که این روش در مقایسه با روش پیشین، تعداد نمونه‌های موردنیاز را تا چند مرتبه بزرگی کاهش می‌دهد و در عین حال دقت تخمین را حفظ می‌کند.

دومین نوآوری این پژوهش، مکانیزم «تأیید مشتاقانه» است که برای بهبود نرخ برخورد در نمونه‌گیری همسایگی طراحی شده است. ریشه مشکل نرخ پایین برخورد در سیستم‌های پیشین، بررسی دیرهنگام شرایط تکمیل الگو بود. در آن سیستم‌ها، نمونه‌گیری تا مراحل پایانی ادامه می‌یافت و تنها در آخرین گام مشخص می‌شد که آیا نمونه با الگو مطابقت دارد یا خیر. اما بسیاری از نمونه‌ها از همان مراحل ابتدایی قابل حذف بودند، زیرا زیرساختار اولیه آن‌ها با الگو همخوانی نداشت. برای مثال، اگر الگوی موردجستجو یک شش-کلیک باشد و چهار گره اول نمونه تشکیل چهار-کلیک ندهند، آن نمونه هرگز نمی‌تواند به شش-کلیک تبدیل شود و ادامه کار بیهوده است. ایده «تأیید مشتاقانه» آن است که شرایط اتصال و محدودیت‌های الگو در همان مراحل اولیه نمونه‌گیری بررسی شوند و نامزدهای نامیدکننده هرچه زودتر حذف گردند. این کار دو مزیت دارد: نخست اینکه هر نمونه از میان نامزدهای امیدبخش انتخاب می‌شود و بنابراین احتمال موفقیت آن به‌شدت افزایش می‌یابد؛ دوم اینکه اگر نمونه‌ای از ابتدا نامیدکننده باشد، در همان مراحل اولیه شکست می‌خورد و کار اضافی انجام نمی‌شود. برای پیاده‌سازی این ایده، از تکنیک‌های هرس کردن مانند ترتیب تطبیق و شکست تقارن استفاده شده است که در الگوریتم‌های دقیق کاوش گراف رایج هستند. اثبات شده است که این روش سوگیری ایجاد نمی‌کند و تخمین حاصل همچنان بدون‌غرض است. نتایج تجربی نشان می‌دهد که نرخ برخورد با این روش در برخی گراف‌ها تا چند برابر بهبود می‌یابد؛ برای مثال، در یک گراف خاص، نرخ برخورد از حدود پنج درصد به بیش از سی درصد افزایش یافته است که نشان‌دهنده تأثیر چشمگیر این مکانیزم است.

برای موارد بسیار کمیاب که حتی روش نمونه‌گیری همسایگی بهبودیافته نیز از عهده آن‌ها برنمی‌آید، پژوهش حاضر روش «نمونه‌گیری ترکیبی» را معرفی می‌کند. در این روش، دو طرح نمونه‌گیری مکمل با یکدیگر مقایسه می‌شوند: نمونه‌گیری همسایگی که دانه‌دانه و دقیق عمل می‌کند و نمونه‌گیری از طریق «تنک‌سازی گراف» که درشتی بیشتری دارد و هر نمونه آن می‌تواند شامل چندین تطابق باشد. نمونه‌گیری همسایگی برای گراف‌های متراکم و الگوهای ساده مناسب است، در حالی که تنک‌سازی گراف برای موارد کمیاب و الگوهای پیچیده عملکرد بهتری دارد. در تنک‌سازی گراف، بخشی از یال‌های گراف به‌صورت تصادفی حذف می‌شوند تا گرافی کوچک‌تر و سبک‌تر ساخته شود، سپس شمارش دقیق روی این گراف کوچک انجام شده و نتیجه بر اساس احتمال حفظ شدن یال‌ها مقیاس‌بندی می‌گردد. برای انتخاب خودکار میان این دو، مدل‌های هزینه‌ای ساخته شده است که زمان اجرای هر روش را بر اساس ویژگی‌های گراف و الگو تخمین می‌زند. این مدل‌ها با استفاده از پروفایل‌گیری سریع، پارامترهای کلیدی مانند تعداد نمونه برای نمونه‌گیری همسایگی و تعداد رنگ‌ها برای تنک‌سازی را تعیین می‌کنند. سیستم به‌طور پویا روشی را انتخاب می‌کند که زمان کمتری را پیش‌بینی می‌کند. در مواردی که یکی از روش‌ها به‌وضوح برتری دارد، انتخاب قاطعی انجام می‌شود و در غیر این صورت، روش نمونه‌گیری همسایگی ترجیح داده می‌شود تا اطمینان بالاتر تضمین گردد. این رویکرد ترکیبی به‌ویژه در مواردی که الگوی موردجستجو بسیار کمیاب است، بهبود چشمگیری در سرعت ایجاد می‌کند؛ برای نمونه، در یک مورد خاص که الگوی نه-کلیک در گرافی بسیار تنک جستجو می‌شد، انتخاب خودکار روش تنک‌سازی به‌جای نمونه‌گیری همسایگی، سرعت را تا ۶۱ برابر افزایش داد.

بر پایه این سه نوآوری—تشخیص همگرایی برخط، تأیید مشتاقانه و نمونه‌گیری ترکیبی—سیستمی به نام SCALEGPM ساخته شده است. این سیستم از پردازش موازی روی چند هسته پردازنده بهره می‌برد و دو حالت اجرایی ارائه می‌دهد: حالت سخت‌گیرانه که تنها از نمونه‌گیری همسایگی با تشخیص همگرایی برخط استفاده می‌کند و اطمینان بالا را تضمین می‌نماید، و حالت آزاد که از روش ترکیبی بهره می‌گیرد. در حالت سخت‌گیرانه، پروفایل‌گیری سریع و مدل‌های هزینه نادیده گرفته می‌شوند و تمرکز بر ارائه تضمین نظری برای دقت است. در حالت آزاد، سیستم ابتدا با پروفایل‌گیری سریع پارامترهای ورودی را تخمین می‌زند، سپس با مدل‌های هزینه کارایی هر دو روش را پیش‌بینی کرده و روش برتر را انتخاب می‌کند. پیاده‌سازی این سیستم با زبان C++ و کتابخانه OpenMP انجام شده و آزمایش‌ها روی پردازنده‌ای با ۴۸ هسته و حافظه‌ای تا یک ترابایت اجرا شده است. گراف‌های موردآزمایش شامل شبکه‌های واقعی با اندازه‌های گوناگون از چند میلیون تا نزدیک به یک میلیارد گره و تا ۷۵ میلیارد یال هستند. این گراف‌ها از منابع گوناگونی مانند شبکه‌های اجتماعی، شبکه‌های استنادی و گراف‌های وب گردآوری شده‌اند و ویژگی‌های متنوعی از نظر چگالی و توزیع درجه دارند. الگوهای مورد بررسی شامل انواع کلیک، مسیر، خانه، دمبل و نقوش سه‌تایی و چهارتایی است. معیار مقایسه، زمان اجرا با خطای ۱۰ درصد و اطمینان ۹۹ درصد در نظر گرفته شده است که رویه رایج در سیستم‌های پیشین است.

نتایج ارزیابی نشان می‌دهد که سیستم پیشنهادی به‌طور میانگین ۵۶۵ برابر سریع‌تر از سیستم Arya، که پیشرفته‌ترین سیستم تقریبی موجود است، عمل می‌کند و در برخی موارد این سرعت تا ۶۱۰,۱۶۹ برابر می‌رسد. همچنین در مقایسه با سیستم دقیق GraphZero، سرعت آن چهار مرتبه بزرگی (ده‌هزار برابر) بیشتر است. به‌طور خاص، سیستم پیشنهادی قادر است گراف‌هایی با مقیاس میلیاردی را در عرض چند ثانیه پردازش کند، در حالی که سیستم‌های پیشین یا با کمبود حافظه مواجه می‌شوند یا ساعات طولانی نمی‌توانند کار را به پایان برسانند. برای نمونه، در یک گراف با نزدیک به یک میلیارد گره و ۷۵ میلیارد یال، سیستم پیشنهادی توانست الگوی مثلث را در کمتر از یک ثانیه شمارش کند، در حالی که سیستم Arya با کمبود حافظه مواجه شد و سیستم دقیق GraphZero نتوانست در مدت ده ساعت کار را به اتمام برساند. آزمایش‌های جداگانه نشان می‌دهد که مکانیزم تشخیص همگرایی برخط، خطا را با دقت بالایی پیش‌بینی می‌کند و توقف پایدار و سریعی را ممکن می‌سازد. در نمودارهای مقایسه خطای پیش‌بینی‌شده با خطای واقعی، مشاهده می‌شود که منحنی‌های خطای پیش‌بینی‌شده در اجراهای مختلف تقریباً بر یکدیگر منطبق هستند و این نشان‌دهنده پایداری بالای روش است. همچنین تأیید مشتاقانه به‌طور مؤثر نرخ برخورد را افزایش می‌دهد و مدل‌های هزینه به‌درستی روش برتر را در موارد مختلف انتخاب می‌کنند. در مجموع، این پژوهش با ارائه راهکارهایی نوین برای دو چالش اساسی کاوش تقریبی الگوهای گراف، گامی مهم در جهت کاربردپذیری این ابزار در مقیاس‌های عظیم برداشته است و می‌تواند زمینه‌ساز پیشرفت‌های بیشتر در تحلیل داده‌های گرافی در حوزه‌های گوناگون گردد. کارهای آینده می‌تواند شامل گسترش طرح‌های نمونه‌گیری، توزیع‌شده کردن سیستم و بهره‌گیری از توان پردازنده‌های گرافیکی باشد تا سرعت و مقیاس‌پذیری بیش از پیش بهبود یابد.