Category Research

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, […]

k-clique densest subgraph problem

Motivation: Suppose you are given a large “who-calls-whom” network. This is a network where each vertex represents a human and we have an (undirected) edge between two humans if and only if they exchanged a phone call. An important problem that comes up in anomaly detection is finding sets of vertices that “look like” cliques. […]