Archive for the ‘Spectral Graph Theory’ Category

Faster Graph Processing [Almost Linear Time Construction Of Spectral Sparsifier For Any Graph]

Tuesday, October 20th, 2015

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time by Yin Tat Lee, He Sun.


We present the first almost-linear time algorithm for constructing linear-sized spectral sparsification for graphs. This improves all previous constructions of linear-sized spectral sparsification, which requires \Omega(n^2) time.

A key ingredient in our algorithm is a novel combination of two techniques used in literature for constructing spectral sparsification: Random sampling by effective resistance, and adaptive constructions based on barrier functions.

Apologies to the paper authors for my liberties with their title: Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time but I wanted to capture eyes that might glaze past their more formal title.

The PR release where I saw this article reads as follows:

In the second paper, Constructing linear-sized spectral sparsification in almost-linear time, Dr He Sun, Lecturer in Computer Science in the University’s Department of Computer Science and Yin Tat Lee, a PhD student from MIT, have presented the first algorithm for constructing linear-sized spectral sparsifiers that runs in almost-linear time.

More and more applications from today’s big data scenario need to deal with graphs of millions of vertices. While traditional algorithms can be applied directly in these massive graphs, these algorithms are usually too slow to be practical when the graph contains millions of vertices. Also, storing these practical massive graphs are very expensive.

Dr He Sun said: “Over the past decade, there have been intensive studies in order to overcome these two bottlenecks. One notable approach is through the intermediate step called spectral sparsification, which is the approximation of any input graph by a very sparse graph that inherits many properties of the input graph. Since most algorithms run faster in sparse graphs, spectral sparsification is used as a key intermediate step in speeding up the runtime of many practical graph algorithms, including finding approximate maximum flows in an undirected graph, and approximately solving linear systems, among many others.”

Using spectral sparsification, the researchers ran many algorithms in a sparse graph, and obtained approximately the correct results as well. This general framework allowed them to speed up the runtime of a wide range of algorithms by a magnitude. However, to make the overall approach practical, a key issue was to find faster constructions of spectral sparsification with fewer edges in the resulting sparsifiers. There have been many studies looking at this area in the past decade.

The researchers have proved that, for any graph, they can construct in almost-linear time its spectral sparsifier, and in the output sparsifier every vertex has only constant number of vertices. This result is almost optimal respect to time complexity of the algorithm, and the number of edges in the spectral sparsifier.

Very heavy sledding in the paper but you don’t have to be able to originate the insight in order to take advantage of the technique.



Thursday, April 5th, 2012


I mentioned Pegasus on September 28th of 2010. It was at version 2.0 at that time.

It is at version 2.0 today.

With all the development, including in graph projects, over the last eighteen months, I expect to be reading about new capabilities and features.

There have been new publications, Spectral Analysis for Billion-Scale Graphs: Discoveries and Implementation, but it isn’t clear to what degree those have been incorporated into Pegasus.

New Techniques Turbo-Charge Data Mining

Wednesday, January 11th, 2012

New Techniques Turbo-Charge Data Mining by Nicole Hemsoth.

From the post:

While the phrase “spectral feature selection” may sound cryptic (if not ghostly) this concept is finding a welcome home in the realm of high performance data mining.

We talked with an expert in the spectral feature selection for data mining arena, Zheng Zhao from the SAS Institute, about how trends like this, as well as a host of other new developments, are reshaping data mining for both researchers and industry users.

Zhao says that when it comes to major trends in data mining, cloud and Hadoop represent the key to the future. These developments, he says, offer the high performance data mining tools required to tackle the types of large-scale problems that are becoming more prevalent.

In an interview this week, Zhao predicted that over the next few years, large-scale analytics will be at the forefront of both academic research and industry R&D efforts. On one side, industry has strong requirements for new techniques, software and hardware for solving their real problems at the large scale, while on the other hand, academics find this to be an area laden with interesting new challenges to pursue.

For more details, you may want to see our earlier posts:

Spectral Feature Selection for Data Mining

Spectral Graph Theory

Spectral Graph Theory

Friday, December 30th, 2011

Spectral Graph Theory by Fan R K Chung.

A developing area of mathematics that may be important for high dimensional data mining. Relevant to the spectral feature selection post from yesterday.

You can see the first four revised chapters and the bibliography at: Spectral Graph Theory (revised and improved)