Lale Özkahya

Ali Baran Taşdemir, Tuna Karacan, Emir Kaan Kırmacı et al.

Approximate solutions to various NP-hard combinatorial optimization problems have been found by learned heuristics using complex learning models. In particular, vertex (node) classification in graphs has been a helpful method towards finding the decision boundary to distinguish vertices in an optimal set from the rest. By following this approach, we use a learning framework for a pruning process of the input graph towards reducing the runtime of the maximum clique enumeration problem. We extensively study the role of using different vertex representations on the performance of this heuristic method, using graph embedding algorithms, such as Node2vec and DeepWalk, and representations using higher-order graph features comprising local subgraph counts. Our results show that Node2Vec and DeepWalk are promising embedding methods in representing nodes towards classification purposes. We observe that using local graph features in the classification process produce more accurate results when combined with a feature elimination process. Finally, we provide tests on random graphs to show the robustness and scalability of our method.

Murat Çelik, Ali Baran Taşdemir, Lale Özkahya

Complex networks representing social interactions, brain activities, molecular structures have been studied widely to be able to understand and predict their characteristics as graphs. Models and algorithms for these networks are used in real-life applications, such as search engines, and recommender systems. In general, such networks are modelled by constructing a low-dimensional Euclidean embedding of the vertices of the network, where proximity of the vertices in the Euclidean space hints the likelihood of an edge (link). In this work, we study the performance of such low-rank representations of real-life networks on a network classification problem.

Derman Keskinkilic, Lale Ozkahya

The star chromatic number on a graph is the minimum number of colors in a proper vertex coloring forbidding any $P_4$ with two colors (bicolored). This problem was introduced by Grünbaum (1973) together with the acyclic coloring of graphs, where bicolored cycles are avoided. In this paper, we study a generalization of this problem, by considering proper vertex coloring on graphs forbidding bicolored paths of a fixed length, which was initially discussed by Alon, McDiarmid, and Reed (1991). Here, we study this problem on products of two paths. We show that at least 4 colors are needed to properly color the product of paths, $P_m\square P_n$, avoiding a bicolored $P_k,$ unless $n<k-2$ or $m<k-2.$ With this result, the above question is settled for all $k$ on 2-dimensional grids.