Author name cluster

Konstantin Kutzkov

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

AAAI Conference 2023 Conference Paper

LoNe Sampler: Graph Node Embeddings by Coordinated Local Neighborhood Sampling

Konstantin Kutzkov

Local graph neighborhood sampling is a fundamental computational problem that is at the heart of algorithms for node representation learning. Several works have presented algorithms for learning discrete node embeddings where graph nodes are represented by discrete features such as attributes of neighborhood nodes. Discrete embeddings offer several advantages compared to continuous word2vec-like node embeddings: ease of computation, scalability, and interpretability. We present LoNe Sampler, a suite of algorithms for generating discrete node embeddings by Local Neighborhood Sampling, and address two shortcomings of previous work. First, our algorithms have rigorously understood theoretical properties. Second, we show how to generate approximate explicit vector maps that avoid the expensive computation of a Gram matrix for the training of a kernel model. Experiments on benchmark datasets confirm the theoretical findings and demonstrate the advantages of the proposed methods.

PDF Details DOI

NeurIPS Conference 2018 Conference Paper

KONG: Kernels for ordered-neighborhood graphs

Moez Draief
Konstantin Kutzkov
Kevin Scaman
Milan Vojnovic

We present novel graph kernels for graphs with node and edge labels that have ordered neighborhoods, i. e. when neighbor nodes follow an order. Graphs with ordered neighborhoods are a natural data representation for evolving graphs where edges are created over time, which induces an order. Combining convolutional subgraph kernels and string kernels, we design new scalable algorithms for generation of explicit graph feature maps using sketching techniques. We obtain precise bounds for the approximation accuracy and computational complexity of the proposed approaches and demonstrate their applicability on real datasets. In particular, our experiments demonstrate that neighborhood ordering results in more informative features. For the special case of general graphs, i. e. graphs without ordered neighborhoods, the new graph kernels yield efficient and simple algorithms for the comparison of label distributions between graphs.

PDF Details

ICML Conference 2016 Conference Paper

Learning Convolutional Neural Networks for Graphs

Mathias Niepert
Mohamed Ahmed 0001
Konstantin Kutzkov

Numerous important problems can be framed as learning from graph data. We propose a framework for learning convolutional neural networks for arbitrary graphs. These graphs may be undirected, directed, and with both discrete and continuous node and edge attributes. Analogous to image-based convolutional networks that operate on locally connected regions of the input, we present a general approach to extracting locally connected regions from graphs. Using established benchmark data sets, we demonstrate that the learned feature representations are competitive with state of the art graph kernels and that their computation is highly efficient.

Details

TCS Journal 2014 Journal Article

New exact algorithms for the 2-constraint satisfaction problem

Alexander Golovnev
Konstantin Kutzkov

Many optimization problems can be phrased in terms of constraint satisfaction. In particular MAX-2-SAT and MAX-2-CSP are known to generalize many hard combinatorial problems on graphs. Algorithms solving the problem exactly have been designed but the running time is improved over trivial brute-force solutions only for very sparse instances. Despite many efforts, the only known algorithm [28] solving MAX-2-CSP over n variables in less than O ⁎ ( 2 n ) steps uses exponential space. Several authors have designed algorithms with running time O ⁎ ( 2 n f ( d ) ) where f: R + → ( 0, 1 ) is a slowly growing function and d is the average variable degree of the input formula. The current best known algorithm for MAX-2-CSP [25] runs in time O ⁎ ( 2 n ( 1 − 2 d + 1 ) ) and polynomial space. In this paper we continue this line of research and design new algorithms for the MAX-2-SAT and MAX-2-CSP problems. First, we present a general technique for obtaining new bounds on the running time of a simple algorithm for MAX-2-CSP analyzed with respect to the number of vertices from algorithms that are analyzed with respect to the number of constraints. The best known bound for the problem is improved to O ⁎ ( 2 n ( 1 − 3 d + 1 ) ) for d ⩾ 3. We further improve the bound for MAX-2-SAT, in particular for d ⩾ 6 we achieve O ⁎ ( 2 n ( 1 − 3. 677 d + 1 ) ). As a second result we present an algorithm with asymptotically better running time for the case when the input instance is not very sparse. Building on recent work of Feige and Kogan we derive an upper bound on the size of a vertex separator for graphs in terms of the average degree of the graph. We then design a simple algorithm solving MAX-2-CSP in time O ⁎ ( 2 c d n ), c d = 1 − 2 α ln d d for some α < 1 and d = o ( n ).

Details DOI