93 citations · 244 across the 16 of their papers we have counts for
17 papers
Improved large-scale graph learning through ridge spectral sparsification
Daniele Calandriello, Ioannis Koutis, Alessandro Lazaric +1
Graph-based techniques and spectral graph theory have enriched the field of machine learning with a variety of critical advances. A central object in the analysis is the graph Lapl…
Neural Network Pruning as Spectrum Preserving Process
Shibo Yao, Dantong Yu, Ioannis Koutis
Neural networks have achieved remarkable performance in various application domains. Nevertheless, a large number of weights in pre-trained deep neural networks prohibit them from…
K-SpecPart: Supervised embedding algorithms and cut overlay for improved hypergraph partitioning
Ismail Bustany, Andrew B. Kahng, Ioannis Koutis +2
State-of-the-art hypergraph partitioners follow the multilevel paradigm that constructs multiple levels of progressively coarser hypergraphs that are used to drive cut refinement o…
Spectrally Robust Graph Isomorphism
Alexandra Kolla, Ioannis Koutis, Vivek Madan +1
We initiate the study of spectral generalizations of the graph isomorphism problem. (a)The Spectral Graph Dominance (SGD) problem: On input of two graphs and does there exi…
Directed Hamiltonicity and Out-Branchings via Generalized Laplacians
Andreas Björklund, Petteri Kaski, Ioannis Koutis
We are motivated by a tantalizing open question in exact algorithms: can we detect whether an -vertex directed graph has a Hamiltonian cycle in time significantly less than…
On Fully Dynamic Graph Sparsifiers
Ittai Abraham, David Durfee, Ioannis Koutis +2
We initiate the study of dynamic algorithms for graph sparsification problems and obtain fully dynamic algorithms, allowing both edge insertions and edge deletions, that take polyl…
Incremental Spectral Sparsification for Large-Scale Graph-Based Semi-Supervised Learning
Daniele Calandriello, Alessandro Lazaric, Michal Valko +1
While the harmonic function solution performs well in many semi-supervised learning (SSL) tasks, it is known to scale poorly with the number of samples. Recent successful and scala…
Scalable Constrained Clustering: A Generalized Spectral Method
Mihai Cucuringu, Ioannis Koutis, Sanjay Chawla +2
We present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem with graph Laplacia…
Scalable Constrained Clustering: A Generalized Spectral Method
Mihai Cucuringu, Ioannis Koutis, Sanjay Chawla
We present a principled spectral approach to the well-studied constrained clustering problem. It reduces clustering to a generalized eigenvalue problem on Laplacians. The method wo…
A Generalized Cheeger Inequality
Ioannis Koutis, Gary Miller, Richard Peng
The generalized conductance between two graphs and on the same vertex set is defined as the ratio $$ ϕ(G,H) = \min_{S\subseteq V} \frac{cap_G(S,\bar{S})}{ cap_…
Simple parallel and distributed algorithms for spectral graph sparsification
Ioannis Koutis
We describe a simple algorithm for spectral graph sparsification, based on iterative computations of weighted spanners and uniform sampling. Leveraging the algorithms of Baswana an…
Faster spectral sparsification and numerical algorithms for SDD matrices
Ioannis Koutis, Alex Levin, Richard Peng
We study algorithms for spectral graph sparsification. The input is a graph with vertices and edges, and the output is a sparse graph that approximates …
Constrained multilinear detection for faster functional motif discovery
Ioannis Koutis
The GRAPH MOTIF problem asks whether a given multiset of colors appears on a connected subgraph of a vertex-colored graph. The fastest known parameterized algorithm for this proble…
Near Linear-Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs
Guy E. Blelloch, Anupam Gupta, Ioannis Koutis +3
We present the design and analysis of a near linear-work parallel algorithm for solving symmetric diagonally dominant (SDD) linear systems. On input of a SDD -by- matrix …
A nearly-mlogn time solver for SDD linear systems
Ioannis Koutis, Gary Miller, Richard Peng
We present an improved algorithm for solving symmetrically diagonally dominant linear systems. On input of an symmetric diagonally dominant matrix with non-zero…
Approaching optimality for solving SDD systems
Ioannis Koutis, Gary L. Miller, Richard Peng
We present an algorithm that on input of an -vertex -edge weighted graph and a value , produces an {\em incremental sparsifier} with edges, such…
Spectrum through pseudospectrum
Ioannis Koutis
We present an iteration for the computation of simple eigenvalues using a pseudospectrum approach. The most appealing characteristic of the proposed iteration is that it reduces th…