Entropic Spectral Learning for Large-Scale Graphs
Graph spectra have been successfully used to classify network types, compute the similarity between graphs, and determine the number of communities in a network. For large graphs, where an eigen-decomposition is infeasible, iterative moment matched approximations to the spectra and kernel smoothing are typically used. We show that the underlying moment information is lost when using kernel smoothing. We further propose a spectral density approximation based on the method of Maximum Entropy, for which we develop a new algorithm. This method matches moments exactly and is everywhere positive. We demonstrate its effectiveness and superiority over existing approaches in learning graph spectra, via experiments on both synthetic networks, such as the Erd\H{o}s-R\'{e}nyi and Barab\'{a}si-Albert random graphs, and real-world networks, such as the social networks for Orkut, YouTube, and Amazon from the SNAP dataset.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionSimilar Papers 제목 키워드 기반
Entropic Optimal Transport in Random Graphs
In graph analysis, a classic task consists in computing similarity measures between (groups of) nodes. In latent space random graphs, nodes are associated to unknown latent variables. One may then seek to compute distanc…
Entropic Causal Inference: Graph Identifiability
Entropic causal inference is a recent framework for learning the causal graph between two variables from observational data by finding the information-theoretically simplest structural explanation of the data, i.e., the …
Causal InferenceAn Entropic Optimal Transport Loss for Learning Deep Neural Networks under Label Noise in Remote Sensing Images
Deep neural networks have established as a powerful tool for large scale supervised classification tasks. The state-of-the-art performances of deep neural networks are conditioned to the availability of large number of a…
ClassificationGeneral ClassificationFaster Computation of Entropic Optimal Transport via Stable Low Frequency Modes
In this paper, we propose an accelerated version for the Sinkhorn algorithm, which is the reference method for computing the solution to Entropic Optimal Transport. Its main draw-back is the exponential slow-down of conv…
Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs
Graph comparison is a fundamental operation in data mining and information retrieval. Due to the combinatorial nature of graphs, it is hard to balance the expressiveness of the similarity measure and its scalability. Spe…
Information RetrievalRetrieval