Category Research

The densest subgraph problem with negative weights

Few days ago I uploaded on Arxiv our preprint “Novel Dense Subgraph Discovery Primitives: Risk Aversion and Exclusion Queries”.  This is joint work with Tianyi, Nao, and Jakub. In this paper we study the following extension of the densest subgraph problem (DSP) that is known to be solvable exactly in polynomial time on graphs with […]

Graph mining with a faulty oracle

Pythia was a powerful and respected woman in Ancient Greece. She was the high priestess of the Temple of Apollo at Delphi. I was surprised to read in the Wikipedia article that the name Pythia is derived from the verb πύθειν (púthein) which means “to rot”; I find this to be unlikely. An etymology that sounds […]

Risk aversion and uncertain graphs

     Let’s say that you have 100$ and you want to invest your money wisely. There are two hedge funds that interest you, both of which have the same expected return. How should you invest your 100$? Does it matter if you split it in half, or if you invest all of your money […]

Privacy and 1d Histograms

Suppose there is an underlying 1 dimensional histogram stored in the cloud. As a concrete example, consider the distribution of bank deposits (x-axis is the amount of dollars, and the y-axis is the count of accounts). For simplicity let’s assume that all the amounts of money deposited are integers within the range . The histogram is queried by […]

Dense subgraph discovery applications

Recently, I compiled a collection of applications that rely on dense subgraph discovery for my KDD’15 tutorial with Aris Gionis. In general, dense subgraph discovery is a key graph mining primitive. While by “dense” we generally mean subgraphs which are large enough and contain many edges, the exact notion of dense is application dependent.  The […]

Provably Fast Inference of Latent Features from Networks

Latent feature learning: where overlapping communities, correlation clustering, binary matrix factorization and extremal graph theory meet Motivation: Suppose we are given the following. Agents: Five agents, represented by . Binary vertex features. An agent can either be interested or not in each out of three news categories business, entertainment, sports.  Each interest is represented by a […]

Maintaining a random sample of edges on a dynamic graph

Suppose that we have a sample of edges, sampled uniformly at random from the edge set of a graph . Also, let . Now the graph changes, in particular, either a non-existing edge (if the graph is not complete) is inserted or an existing edge is deleted. Do we need to sample edges from scratch?More generally, […]