An Integer Programming Approach Reinforced by a Message-passing Procedure for Detecting Dense Attributed Subgraphs

Due to the growing reliance of various scientific and industrial problems on graphs, one of the recent challenging tasks, especially when dealing with graphs equipped with a set of nodal attributes, is discovering subgraphs consisting of highly interacting nodes with respect to the number of edges and the attributes' similarities. This paper proposes an approach based on integer programming modeling and the graph neural network message-passing manner for efficiently extracting these subgraphs. The experiments illustrate the proposed method's privilege over some alternative algorithms known so far, utilizing several well-known instances.