Table of Links Abstract and 1. Introduction Abstract and 1. Introduction Abstract and 1. Introduction Related Work


Preliminaries and Notations


Differentiable Structural Information
4.1. A New Formulation
4.2. Properties
4.3. Differentiability & Deep Graph Clustering


LSEnet
5.1. Embedding Leaf Nodes
5.2. Learning Parent Nodes
5.3. Hyperbolic Partitioning Tree


Experiments
6.1. Graph Clustering
6.2. Discussion on Structural Entropy


Conclusion, Broader Impact, and References Appendix Related Work Related Work Related Work Related Work Preliminaries and Notations Preliminaries and Notations Preliminaries and Notations Preliminaries and Notations Differentiable Structural Information
4.1. A New Formulation
4.2. Properties
4.3. Differentiability & Deep Graph Clustering Differentiable Structural Information Differentiable Structural Information Differentiable Structural Information 4.1. A New Formulation 4.1. A New Formulation 4.2. Properties 4.2. Properties 4.3. Differentiability & Deep Graph Clustering 4.3. Differentiability & Deep Graph Clustering LSEnet
5.1. Embedding Leaf Nodes
5.2. Learning Parent Nodes
5.3. Hyperbolic Partitioning Tree LSEnet LSEnet LSEnet 5.1. Embedding Leaf Nodes 5.1. Embedding Leaf Nodes 5.2. Learning Parent Nodes 5.2. Learning Parent Nodes 5.3. Hyperbolic Partitioning Tree 5.3. Hyperbolic Partitioning Tree Experiments
6.1. Graph Clustering
6.2. Discussion on Structural Entropy Experiments Experiments 6.1. Graph Clustering 6.1. Graph Clustering 6.2. Discussion on Structural Entropy 6.2. Discussion on Structural Entropy Conclusion, Broader Impact, and References Appendix Conclusion, Broader Impact, and References Appendix Conclusion, Broader Impact, and References Appendix Conclusion, Broader Impact, and References Appendix A. Proofs A. Proofs B. Hyperbolic Space B. Hyperbolic Space C. Technical Details C. Technical Details D. Additional Results D. Additional Results Appendix The appendix is structured in four sections. A. Proofs on differential structural information, B. Hyperbolic Space, including important notions and facts in hyperbolic geometry, C. Technical Details on algorithms, datasets, baselines, etc., and D. Additional Results on real datasets. A. Proofs B. Hyperbolic Space C. Technical Details D. Additional Results A. Proofs Here, we detail lemmas and theorems on the proposed Differential Structural Information. In particular, we prove the equivalence, additivity, flexibility, bound and the connection to graph clustering, and show the supporting lemmas. Differential Structural Information A.1. Proof of Theorem 4.4 A.1. Proof of Theorem 4.4 Utilizing the equations above, we have completed the proof. A.2. Proof of Theorem 4.7 A.2. Proof of Theorem 4.7 Then we have the following lemma Lemma A.1. For a weighted Graph G = (V, E) with a weight function w, and a partitioning tree T of G with height H, we can rewrite the formula of H-dimensional structural information of G w.r.t T as follows: Lemma A.1. For a weighted Graph G = (V, E) with a weight function w, and a partitioning tree T of G with height H, we can rewrite the formula of H-dimensional structural information of G w.r.t T as follows: where I(·) is the indicator function. where I is the indicator function. Proof. We leave the proof of Lemma A.1 in Appendix A.5. Proof Now we start our proof of Theorem 4.7. A.3. Proof of Lemma 4.5 A.3. Proof of Lemma 4.5 A.4. Proof of Theorem 4.6 A.4. Proof of Theorem 4.6 A.5. Proof of Lemma A.1 A.5. Proof of Lemma A.1 Lemma A.1 For a weighted Graph G = (V, E) with a weight function w, and a partitioning tree T of G with height H, we can rewrite the formula of H-dimensional structural information of G w.r.t T as follows: Lemma A.1 For a weighted Graph G = (V, E) with a weight function w, and a partitioning tree T of G with height H, we can rewrite the formula of H-dimensional structural information of G w.r.t T as follows: where I(·) is the indicator function. where I is the indicator function. Proof. From Equation.1, we can rewrite structural information of G w.r.t all nodes of T at height h as follows: Proof G T h Then the H-dimensional structural information of G can be written as H G Utilizing the equations above, we have completed the proof. A.6. Proof of Theorem 4.8 A.6. Proof of Theorem 4.8 Authors:
(1) Li Sun, North China Electric Power University, Beijing 102206, China (ccesunli@ncepu.edu);
(2) Zhenhao Huang, North China Electric Power University, Beijing 102206, China;
(3) Hao Peng, Beihang University, Beijing 100191, China;
(4) Yujie Wang, North China Electric Power University, Beijing 102206, China;
(5) Chunyang Liu, Didi Chuxing, Beijing, China;
(6) Philip S. Yu, University of Illinois at Chicago, IL, USA. Authors: Authors: (1) Li Sun, North China Electric Power University, Beijing 102206, China (ccesunli@ncepu.edu); (2) Zhenhao Huang, North China Electric Power University, Beijing 102206, China; (3) Hao Peng, Beihang University, Beijing 100191, China; (4) Yujie Wang, North China Electric Power University, Beijing 102206, China; (5) Chunyang Liu, Didi Chuxing, Beijing, China; (6) Philip S. Yu, University of Illinois at Chicago, IL, USA. This paper is available on arxiv under CC BY-NC-SA 4.0 Deed (Attribution-Noncommercial-Sharelike 4.0 International) license. This paper is available on arxiv under CC BY-NC-SA 4.0 Deed (Attribution-Noncommercial-Sharelike 4.0 International) license. available on arxiv available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Graph Information Theory: The Mathematical Proofs Behind LSEnet and DSI

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Comparative Performance Analysis of SymTax on Five Citation Recommendation Datasets

It Is Okay If You Don't Know What You Like. We Do (feat. Deep Recommendation Algorithms)

10 Machine Learning, Data Science, and Deep Learning Courses for Programmers in 2020

10 Computer Vision Startups on Product Hunt with the Most Upvotes

10 Best Entry Level Machine Learning Tutorials

10 Best + Free Machine Learning Courses Collection

A Comparative Performance Analysis of SymTax on Five Citation Recommendation Datasets

It Is Okay If You Don't Know What You Like. We Do (feat. Deep Recommendation Algorithms)

10 Machine Learning, Data Science, and Deep Learning Courses for Programmers in 2020

10 Computer Vision Startups on Product Hunt with the Most Upvotes

10 Best Entry Level Machine Learning Tutorials

10 Best + Free Machine Learning Courses Collection

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps