Source author record

Ali Kemal Sinop

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics Machine Learning math.SP

Catalog footprint

Research overview

11works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Affinity-Aware Graph Networks

Graph Neural Networks (GNNs) have emerged as a powerful technique for learning on relational data. Owing to the relatively limited number of message passing steps they perform -- and hence a smaller receptive field -- there has been significant interest in improving their expressivity by incorporating structural aspects of the underlying graph. In this paper, we explore the use of affinity measures as features in graph neural networks, in particular measures arising from random walks, including effective resistance, hitting and commute times. We propose message passing networks based on these features and evaluate their performance on a variety of node and graph property prediction tasks. Our architecture has lower computational complexity, while our features are invariant to the permutations of the underlying graph. The measures we compute allow the network to exploit the connectivity properties of the graph, thereby allowing us to outperform relevant benchmarks for a wide variety of tasks, often with significantly fewer message passing steps. On one of the largest publicly available graph regression datasets, OGB-LSC-PCQM4Mv1, we obtain the best known single-model validation MAE at the time of writing.

preprint2015arXiv

How to Round Subspaces: A New Spectral Clustering Algorithm

A basic problem in spectral clustering is the following. If a solution obtained from the spectral relaxation is close to an integral solution, is it possible to find this integral solution even though they might be in completely different basis? In this paper, we propose a new spectral clustering algorithm. It can recover a $k$ -partition such that the subspace corresponding to the span of its indicator vectors is $O(\sqrt{opt})$ close to the original subspace in spectral norm with $opt$ being the minimum possible ( $opt \le 1$ always). Moreover our algorithm does not impose any restriction on the cluster sizes. Previously, no algorithm was known which could find a $k$ -partition closer than $o(k \cdot opt)$ . We present two applications for our algorithm. First one finds a disjoint union of bounded degree expanders which approximate a given graph in spectral norm. The second one is for approximating the sparsest $k$ -partition in a graph where each cluster have expansion at most $ϕ_k$ provided $ϕ_k \le O(λ_{k+1})$ where $λ_{k+1}$ is the $(k+1)^{st}$ eigenvalue of Laplacian matrix. This significantly improves upon the previous algorithms, which required $ϕ_k \le O(λ_{k+1}/k)$ .

preprint2015arXiv

The Hardness of Approximation of Euclidean k-means

The Euclidean $k$ -means problem is a classical problem that has been extensively studied in the theoretical computer science, machine learning and the computational geometry communities. In this problem, we are given a set of $n$ points in Euclidean space $R^d$ , and the goal is to choose $k$ centers in $R^d$ so that the sum of squared distances of each point to its nearest center is minimized. The best approximation algorithms for this problem include a polynomial time constant factor approximation for general $k$ and a $(1+ε)$ -approximation which runs in time $poly(n) 2^{O(k/ε)}$ . At the other extreme, the only known computational complexity result for this problem is NP-hardness [ADHP'09]. The main difficulty in obtaining hardness results stems from the Euclidean nature of the problem, and the fact that any point in $R^d$ can be a potential center. This gap in understanding left open the intriguing possibility that the problem might admit a PTAS for all $k,d$ . In this paper we provide the first hardness of approximation for the Euclidean $k$ -means problem. Concretely, we show that there exists a constant $ε> 0$ such that it is NP-hard to approximate the $k$ -means objective to within a factor of $(1+ε)$ . We show this via an efficient reduction from the vertex cover problem on triangle-free graphs: given a triangle-free graph, the goal is to choose the fewest number of vertices which are incident on all the edges. Additionally, we give a proof that the current best hardness results for vertex cover can be carried over to triangle-free graphs. To show this we transform $G$ , a known hard vertex cover instance, by taking a graph product with a suitably chosen graph $H$ , and showing that the size of the (normalized) maximum independent set is almost exactly preserved in the product graph using a spectral analysis, which might be of independent interest.

preprint2014arXiv

Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems

Partitioning the vertices of a graph into two roughly equal parts while minimizing the number of edges crossing the cut is a fundamental problem (called Balanced Separator) that arises in many settings. For this problem, and variants such as the Uniform Sparsest Cut problem where the goal is to minimize the fraction of pairs on opposite sides of the cut that are connected by an edge, there are large gaps between the known approximation algorithms and non-approximability results. While no constant factor approximation algorithms are known, even APX-hardness is not known either. In this work we prove that for balanced separator and uniform sparsest cut, semidefinite programs from the Lasserre hierarchy (which are the most powerful relaxations studied in the literature) have an integrality gap bounded away from $1$ , even for $Ω(n)$ levels of the hierarchy. This complements recent algorithmic results in Guruswami and Sinop (2011) which used the Lasserre hierarchy to give an approximation scheme for these problems (with runtime depending on the spectrum of the graph). Along the way, we make an observation that simplifies the task of lifting "polynomial constraints" (such as the global balance constraint in balanced separator) to higher levels of the Lasserre hierarchy.

preprint2013arXiv

Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs

We present an approximation scheme for minimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Sparsest Cut, and Small Set expansion, as well as the Unique Games problem. These problems are notorious for the existence of huge gaps between the known algorithmic results and NP-hardness results. Our algorithm is based on rounding semidefinite programs from the Lasserre hierarchy, and the analysis uses bounds for low-rank approximations of a matrix in Frobenius norm using columns of the matrix. For all the above graph problems, we give an algorithm running in time $n^{O(r/ε^2)}$ with approximation ratio $\frac{1+ε}{\min\{1,λ_r\}}$ , where $λ_r$ is the $r$ 'th smallest eigenvalue of the normalized graph Laplacian $\mathcal{L}$ . In the case of graph bisection and small set expansion, the number of vertices in the cut is within lower-order terms of the stipulated bound. Our results imply $(1+O(ε))$ factor approximation in time $n^{O(r^\ast/ε^2)}$ where is the number of eigenvalues of $\mathcal{L}$ smaller than $1-ε$ (for variants of sparsest cut, $λ_{r^\ast} \ge \mathrm{OPT}/ε$ also suffices, and as $\mathrm{OPT}$ is usually $o(1)$ on interesting instances of these problems, this requirement on $r^\ast$ is typically weaker). For Unique Games, we give a factor $(1+\frac{2+ε}{λ_r})$ approximation for minimizing the number of unsatisfied constraints in $n^{O(r/ε)}$ time, improving upon an earlier bound for solving Unique Games on expanders. We also give an algorithm for independent sets in graphs that performs well when the Laplacian does not have too many eigenvalues bigger than $1+o(1)$ .

preprint2013arXiv

Towards a better approximation for sparsest cut?

We give a new $(1+ε)$ -approximation for sparsest cut problem on graphs where small sets expand significantly more than the sparsest cut (sets of size $n/r$ expand by a factor $\sqrt{\log n\log r}$ bigger, for some small $r$ ; this condition holds for many natural graph families). We give two different algorithms. One involves Guruswami-Sinop rounding on the level- $r$ Lasserre relaxation. The other is combinatorial and involves a new notion called {\em Small Set Expander Flows} (inspired by the {\em expander flows} of ARV) which we show exists in the input graph. Both algorithms run in time $2^{O(r)} \mathrm{poly}(n)$ . We also show similar approximation algorithms in graphs with genus $g$ with an analogous local expansion condition. This is the first algorithm we know of that achieves $(1+ε)$ -approximation on such general family of graphs.

preprint2012arXiv

Approximating Non-Uniform Sparsest Cut via Generalized Spectra

We give an approximation algorithm for non-uniform sparsest cut with the following guarantee: For any $ε,δ\in (0,1)$ , given cost and demand graphs with edge weights $C, D$ respectively, we can find a set $T\subseteq V$ with $\frac{C(T,V\setminus T)}{D(T,V\setminus T)}$ at most $\frac{1+ε}δ$ times the optimal non-uniform sparsest cut value, in time $2^{r/(δε)}\poly(n)$ provided $λ_r \ge Φ^*/(1-δ)$ . Here $λ_r$ is the $r$ 'th smallest generalized eigenvalue of the Laplacian matrices of cost and demand graphs; $C(T,V\setminus T)$ (resp. $D(T,V\setminus T)$ ) is the weight of edges crossing the $(T,V\setminus T)$ cut in cost (resp. demand) graph and $Φ^*$ is the sparsity of the optimal cut. In words, we show that the non-uniform sparsest cut problem is easy when the generalized spectrum grows moderately fast. To the best of our knowledge, there were no results based on higher order spectra for non-uniform sparsest cut prior to this work. Even for uniform sparsest cut, the quantitative aspects of our result are somewhat stronger than previous methods. Similar results hold for other expansion measures like edge expansion, normalized cut, and conductance, with the $r$ 'th smallest eigenvalue of the normalized Laplacian playing the role of $λ_r$ in the latter two cases. Our proof is based on an l1-embedding of vectors from a semi-definite program from the Lasserre hierarchy. The embedded vectors are then rounded to a cut using standard threshold rounding. We hope that the ideas connecting $\ell_1$ -embeddings to Lasserre SDPs will find other applications. Another aspect of the analysis is the adaptation of the column selection paradigm from our earlier work on rounding Lasserre SDPs [GS11] to pick a set of edges rather than vertices. This feature is important in order to extend the algorithms to non-uniform sparsest cut.

preprint2012arXiv

Faster SDP hierarchy solvers for local rounding algorithms

Convex relaxations based on different hierarchies of linear/semi-definite programs have been used recently to devise approximation algorithms for various optimization problems. The approximation guarantee of these algorithms improves with the number of {\em rounds} $r$ in the hierarchy, though the complexity of solving (or even writing down the solution for) the $r$ 'th level program grows as $n^{Ω(r)}$ where $n$ is the input size. In this work, we observe that many of these algorithms are based on {\em local} rounding procedures that only use a small part of the SDP solution (of size $n^{O(1)} 2^{O(r)}$ instead of $n^{Ω(r)}$ ). We give an algorithm to find the requisite portion in time polynomial in its size. The challenge in achieving this is that the required portion of the solution is not fixed a priori but depends on other parts of the solution, sometimes in a complicated iterative manner. Our solver leads to $n^{O(1)} 2^{O(r)}$ time algorithms to obtain the same guarantees in many cases as the earlier $n^{O(r)}$ time algorithms based on $r$ rounds of the Lasserre hierarchy. In particular, guarantees based on $O(\log n)$ rounds can be realized in polynomial time. We develop and describe our algorithm in a fairly general abstract framework. The main technical tool in our work, which might be of independent interest in convex optimization, is an efficient ellipsoid algorithm based separation oracle for convex programs that can output a {\em certificate of infeasibility with restricted support}. This is used in a recursive manner to find a sequence of consistent points in nested convex bodies that "fools" local rounding algorithms.

preprint2012arXiv

Optimal Column-Based Low-Rank Matrix Reconstruction

We prove that for any real-valued matrix $X \in \R^{m \times n}$ , and positive integers $r \ge k$ , there is a subset of $r$ columns of $X$ such that projecting $X$ onto their span gives a $\sqrt{\frac{r+1}{r-k+1}}$ -approximation to best rank- $k$ approximation of $X$ in Frobenius norm. We show that the trade-off we achieve between the number of columns and the approximation ratio is optimal up to lower order terms. Furthermore, there is a deterministic algorithm to find such a subset of columns that runs in $O(r n m^ω \log m)$ arithmetic operations where $ω$ is the exponent of matrix multiplication. We also give a faster randomized algorithm that runs in $O(r n m^2)$ arithmetic operations.

preprint2011arXiv

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives

We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These problems are notorious for the existence of huge gaps between the known algorithmic results and NP-hardness results. Our algorithm is based on rounding semidefinite programs from the Lasserre hierarchy, and the analysis uses bounds for low-rank approximations of a matrix in Frobenius norm using columns of the matrix. For all the above graph problems, we give an algorithm running in time $n^{O(r/ε^2)}$ with approximation ratio $\frac{1+ε}{\min\{1,λ_r\}}$ , where $λ_r$ is the $r$ 'th smallest eigenvalue of the normalized graph Laplacian $\mathcal{L}$ . In the case of graph bisection and small set expansion, the number of vertices in the cut is within lower-order terms of the stipulated bound. Our results imply $(1+O(ε))$ factor approximation in time $n^{O(r^\ast/ε^2)}$ where $r^\ast$ is the number of eigenvalues of $\mathcal{L}$ smaller than $1-ε$ . For Unique Games, we give a factor $(1+\frac{2+ε}{λ_r})$ approximation for minimizing the number of unsatisfied constraints in $n^{O(r/ε)}$ time. This improves an earlier bound for solving Unique Games on expanders, and also shows that Lasserre SDPs are powerful enough to solve well-known integrality gap instances for the basic SDP. We also give an algorithm for independent sets in graphs that performs well when the Laplacian does not have too many eigenvalues bigger than $1+o(1)$ .

preprint2009arXiv

Improved Inapproximability Results for Maximum k-Colorable Subgraph

We study the maximization version of the fundamental graph coloring problem. Here the goal is to color the vertices of a k-colorable graph with k colors so that a maximum fraction of edges are properly colored (i.e. their endpoints receive different colors). A random k-coloring properly colors an expected fraction 1-1/k of edges. We prove that given a graph promised to be k-colorable, it is NP-hard to find a k-coloring that properly colors more than a fraction ~1-O(1/k} of edges. Previously, only a hardness factor of 1-O(1/k^2) was known. Our result pins down the correct asymptotic dependence of the approximation factor on k. Along the way, we prove that approximating the Maximum 3-colorable subgraph problem within a factor greater than 32/33 is NP-hard. Using semidefinite programming, it is known that one can do better than a random coloring and properly color a fraction 1-1/k +2 ln k/k^2 of edges in polynomial time. We show that, assuming the 2-to-1 conjecture, it is hard to properly color (using k colors) more than a fraction 1-1/k + O(ln k/ k^2) of edges of a k-colorable graph.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ali Kemal Sinop

Research overview

Is this your work?

11 publications

Affinity-Aware Graph Networks

How to Round Subspaces: A New Spectral Clustering Algorithm

The Hardness of Approximation of Euclidean k-means

Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems

Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs

Towards a better approximation for sparsest cut?

Approximating Non-Uniform Sparsest Cut via Generalized Spectra

Faster SDP hierarchy solvers for local rounding algorithms

Optimal Column-Based Low-Rank Matrix Reconstruction

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives

Improved Inapproximability Results for Maximum k-Colorable Subgraph

See the researcher in context

Building this map preview