توصيفگر ها :
يادگيري عميق , خوشه بندي عميق , يادگيري بازنمايي گراف , خوشه بندي گراف , يادگيري تقابلي
چكيده فارسي :
خوشه¬بندي گراف يا تشخيص اجتماع يكي از مسائل مهم در تحليل گراف است. خوشه¬بندي گراف به معني انتساب گره¬هاي يك گراف به خوشه¬هاي ناهمپوشان يا همپوشان است. روش¬هاي يادگيري بازنمايي گراف، به عنوان پايه¬ي روش¬هاي خوشه¬بندي، به دو دسته¬ الگوريتم¬هاي مبتني بر بازسازي و يادگيري تقابلي دسته¬بندي مي¬شوند. بسياري از روش¬هاي موجود مبتني بر بازسازي هستند. اين روش¬ها بيش از حد بر روي اطلاعات محلي مجاورت تاكيد داشته و اطلاعات ساختاري كلي را تا حد زيادي از دست مي¬دهند. اين موضوع در مسئله¬ي خوشه¬بندي كه بدون ناظر و وابسته به اطلاعات ساختاري كلي گراف است، اهميت زيادي دارد. يادگيري تقابلي گرافي با الهام از روش¬هاي تقابلي در حوزه¬ي بينايي ماشين، به نتايج چشمگيري در حوزه¬ي گراف دست يافته است. ولي نسخه هاي اصلي روش هاي تقابلي گرافي، مبتني بر خوشه بندي نيستند. به اين معني كه بسياري از الگوريتم¬هاي تقابلي موجود براي خوشه¬بندي گراف، در دو مرحله¬ي مجزا به يادگيري بازنمايي گره¬ها و خوشه¬بندي مي¬پردازند. به اين ترتيب، يادگيري بازنمايي مستقل از خوشه-بندي صورت گرفته، از اطلاعات خوشه¬بندي بهره نمي¬برد و در نتيجه، فضاي بازنمايي حاصل براي خوشه¬بندي بهينه نيست. براي مقابله با اين مسئله، در اين رساله راهكاري جهت يادگيري تقابلي گرافي آگاه از اجتماع معرفي مي¬گردد كه از يادگيري تقابلي براي يادگيري بازنمايي بهره گرفته و به طور همزمان، ساختار خوشه¬هاي گراف را نيز براي بهينه¬سازي بازنمايي گره¬ها مدنظر قرار مي¬دهد. به اين ترتيب يادگيري بازنمايي به گونه¬اي انجام مي¬شود كه به صورت توام نه تنها اهداف يادگيري تقابلي را دنبال كند بلكه سازگار با خوشه¬بندي نيز باشد. براي اين كار، روش پيشنهادي فضاي بازنمايي حاصل از يك چارچوب تقابلي را ناچار به تبعيت از يك توزيع مخلوط گاوسي مي¬نمايد. به اين ترتيب فضاي تعبيه¬ي نهايي، سازگاري مناسبي با الگوريتم خوشه¬بندي¬اي كه در ادامه بر روي آن اعمال مي¬شود خواهد داشت. مسئله¬ي موجود ديگر آن است كه مستقل از روش يادگيري، شبكه¬هاي عصبي گرافي محدود به پيام¬هاي محلي هستند كه امر مطلوبي در تعبيه¬ و خوشه¬بندي گراف نيست. جهت تعديل اين مسئله، روش پيشنهادي به منظور دستيابي به يك منظر جهاني¬تر از گراف، از انتشار گراف بهره مي¬گيرد. استفاده از گراف انتشار به جاي گراف مجاورت در مورد بسياري از گراف¬ها به بهبود نتيجه¬ي خوشه¬بندي مي¬انجامد. روش پيشنهادي قادر است به صورت خودكار درباره استفاده يا عدم استفاده از گراف انتشار تصميم¬گيري نمايد. نتايج به دست آمده بر روي داده¬هاي حقيقي نشان¬ مي¬دهد عملكرد روش پيشنهادي به طور قابل ملاحظه¬اي نسبت به روش¬هاي اخير، به¬ويژه روش¬هاي مبتني بر يادگيري تقابلي براي خوشه¬بندي گراف، بيشتر است.
چكيده انگليسي :
Graph clustering or community detection is a challenging task in graph analysis. Graph clustering refers to the assignment of graph nodes into either non-overlapping or overlapping clusters. Methods for graph representation learning, serving as the foundation for clustering techniques, are classified into two main categories: reconstruction-based and contrastive learning algorithms. Most existing methods are reconstruction-based, which over-emphasize local neighborhood information while largely neglecting overall structural information. This drawback is particularly significant in clustering tasks that are unsupervised and dependent on the global structural information of the graph. Graph contrastive learning, inspired by contrastive approaches in computer vision, has achieved remarkable results in the field of graph analysis. However, the original versions of contrastive graph methods are not cluster-based, meaning that many contrastive algorithms for graph clustering operate in two separate phases: node representation learning and clustering. In this way, the representation learning and clustering stage are performed independently, thereby not leveraging clustering information, which leads to a suboptimal representation space for clustering. To address this issue, this thesis introduces a community-aware contrastive graph learning approach, which utilizes contrastive learning for representation learning and simultaneously considers the structure of graph clusters to optimize node representations. Thus, the representation learning process not only aligns with contrastive learning objectives but also remains compatible with clustering. To achieve this, the proposed method constrains the representation space from a contrastive framework to follow a Gaussian mixture distribution. As a result, the final embedding space is better aligned with the clustering algorithm that is subsequently applied to it. Another issue is that, independent of the learning method, graph neural networks are limited to local messages, which is suboptimal for graph embedding and clustering. To mitigate this, the proposed method leverages graph diffusion to obtain a more global view of the graph. The use of graph diffusion instead of adjacency graphs in many cases enhances clustering results. The proposed method is capable of automatically deciding whether to use graph diffusion. The results obtained on real datasets demonstrate that the performance of the proposed method significantly surpasses recent methods, especially contrastive learning-based methods for graph clustering.
