In online advertising, finding the right audience is critical for the success of a campaign. One common way of finding the right audience is to find users with traits similar to the users who have responded positively to the campaign in the past. The small pool of users who have responded positively to the campaign is known as the seed set and the goal here is to reach a bigger audience with traits very similar to that of the seed set. This technique, popularly known as look-alike audience extension, gets increasingly challenging with the scale and high sparsity of data commonly encountered in the advertising domain. In this paper, we present a novel multigraph-based audience extension and scoring system, which works well with high-dimensional sparse data and can be scaled easily to millions of users. Our experimental results on large real-world data demonstrate significant improvement in the perfor-mance of our approach over the existing architectures.