struc2vec+k: تعبیه ساختاری گراف با تجمیع لایه‌ها

هدف از بازنمایی گراف، استخراج بردار تعبیه برای گره‌های گراف است به طوری‌که بردار گره‌های مشابه، به هم نزدیک‌تر باشد (یعنی در فضای برداری تعبیه، به هم نزدیک باشند). روش‌های موجود، معمولاً مشابهت دو گره را براساس همسایگی مشترک محاسبه می‌کنند که ممکن است منجر به نادیده گرفتن گره‌هایی با ساختار مشابه در بخش‌های مختلف گراف شود؛ می‌خواهیم بردار تعبیه گره‌های مشابه که در گراف کنار همدیگر نیستند، در فضای برداری تعبیه به هم نزدیک باشد. بدین منظور، در این مقاله رویکرد جدید struc2vec+k پیشنهاد شده که تعمیم روش پایه struct2vec است. در روش پایه، دو گره به همدیگر شباهت ساختاری دارند اگر اطلاعات گره‌های موجود در لایه اول (همسایه‌ها)، لایه دوم (همسایه‌های همسایه)، لایه سوم و لایه های بعدی آن دو گره با هم شبیه باشد. در رویکرد پیشنهادی، اتصال میان لایه‌ها نیز لحاظ شده است. به بیان دیگر اطلاعات میان دو لایه متوالی تجمیع می‌شود. مثلاً برای لایه دوم، اطلاعات گره‌های لایه اول و اطلاعات گره‌های لایه دوم با هم تجمیع می‌شوند. این تجمیع بر اساس اتصالات میان لایه‌ها است. تجمیع لایه‌ها می‌تواند تا سطح k پیش برود (دلیل وجود k در اسم رویکرد پیشنهادی). آزمایش‌های عددی نشان می‌دهند که روش پیشنهادی دارای دقت مناسبی است.

struc2vec+k: structural graph embedding with layer aggregation

graph representation learning aims to extract embedding vectors for graph nodes, such that similar nodes have close vectors in the embedding space. existing methods often measure node similarity based on their common neighbors, which may overlook nodes with similar structures in different parts of the graph. we want to capture the structural similarity of nodes that are not adjacent in the graph. to this end, we propose struc2vec+k, a new method that extends the basic struc2vec method. the basic method considers two nodes to be structurally similar if their nodes in the first, second, third, and subsequent layers are similar. the proposed method also takes into account the connection between layers, and aggregates the information of two consecutive layers. for instance, for the second layer, the information of the first- and second-layer nodes are aggregated. this aggregation is based on the inter-layer connections. the aggregation can be done up to the k-th layer, which explains the name of the method. we show that the proposed method achieves good accuracy in numerical experiments.