زیرگراف القایی یا Induced sub-graph چیست؟

در نظریه گراف، اصطلاح “induce” به معنای ایجاد یک زیرگراف با انتخاب یک زیرمجموعه از راس‌ها و یال‌های یک گراف بزرگتر است. یک زیرگراف القایی یا Induced sub-graph، گرافی است که مجموعه رئوس آن، زیر مجموعه‌ای از مجموعه رئوس گرافی دیگر باشد با این ویژگی که این زیر گراف دارای تمامی یال‌هایی است که بین رئوس نظیر خود در مجموعه رئوس گراف اولیه موجود هستند.

فرض می‌کنیم گراف (G = (V, E گرافی دلخواه باشد و مجموعه S باشرط S ⊂ V هر زیر مجموعه دلخواهی از مجموعه رئوس گراف G یعنی V باشد؛ لذا زیرگراف القایی [G[S گرافی است متشکل از رئوس موجود در زیر مجموعه S و یال‌های آن، تمامی یال‌های موجود در E است به شرطی که رئوس هر دوسر یال مذکور در S موجود باشد. این تعریف از زیر گراف القایی در مورد گراف‌های غیر جهت دار، جهت دار و گراف چندگانه نیز صادق است.

زیر گراف القایی G[S] را «زیرگراف القا شده از S در G» یا (در صورتی که در انتخاب مجموعه G ابهامی وجود نداشته باشد) «زیرگراف القا شده S» نیز می‌نامند.

در شبکه‌های عصبی گرافی نیز در مقاله Cluster-GCN، اصطلاح “induce”  به کار رفته است. در این  الگوریتم induced sub-graph به معنی انتخاب یک زیرمجموعه از رئوس و یال‌های یک گراف بزرگتر، برای ساخت یک زیرگراف جدید استفاده شده است. از آنجایی که زیرگراف جدید حاصل، شامل خصوصیات و ویژگی‌های خود است که ممکن است با ویژگی‌های گراف اصلی متفاوت باشند. با ایجاد یک زیرگراف، می‌توانیم پیچیدگی محاسباتی GCN خود را کاهش داده بدون اینکه اطلاعات زیادی از گراف اصلی را از دست بدهیم به جای گراف بزرگ عملیات را روی زیرگراف کوچکتر انجام بدهیم و ویژگیهای هر راس را به روز کنیم.

کلمه “induce” در واقع یک اصطلاح رایج برای توصیف فرایند ایجاد یک زیرگراف است و در بسیاری از زمینه‌های نظریه گراف و تحلیل شبکه مورد استفاده قرار می‌گیرد.