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

Struc2vec+k: Structural Graph Embedding with Layer Aggregation

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

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.