Project Details
Funding Scheme : General Research Fund
Project Number : 17200817
Project Title(English) : Spectral Analysis and Optimization Problems in Directed Hypergraph Diffusion Processes 
Project Title(Chinese) : 有向超圖擴散過程的譜分析和優化問題 
Principal Investigator(English) : Dr Chan, Hubert Tsz Hong 
Principal Investigator(Chinese) :  
Department : Department of Computer Science
Institution : The University of Hong Kong
Co - Investigator(s) :
Panel : Engineering
Subject Area : Computing Science & Information Technology
Exercise Year : 2017 / 18
Fund Approved : 700,000
Project Status : On-going
Completion Date : 31-12-2020
Abstract as per original application
This project will investigate diffusion processes on hypergraphs, in which each vertex has some measure and an arbitrary number of vertices can be contained in a hyperedge. Among vertices in the same hyperedge, measure will flow from vertices with maximum measure to those with minimum measure, at a rate proportional to the difference in measure. We will study new diffusion models for more general classes of hypergraphs, which will not only bring theoretical advances in spectral (hyper)graph theory and convex optimization, but also make practical impacts on applications such as semi-supervised learning and market modeling. Classical spectral graph theory relates the edge expansion properties of a normal graph, such as convergence rates of random walks with the spectral properties of its corresponding Laplacian operator. Our preliminary work completes the framework in a recent groundbreaking STOC 2015 paper that studies a diffusion process on (undirected) hypergraphs, from which a hypergraph Laplacian can be defined. Analogous to the classical results, the spectral properties of a Laplacian can be related to hypergraph edge expansion and the convergence rate of the diffusion process. We will explore diffusion processes for more general models such as directed hypergraphs, in which each hyperedge consists of a tail subset of vertices pointing to a head subset of vertices. A directed hyperedge can therefore capture a causal relationship between multiple agents. For instance, in a coauthorship network , each hyperedge contains the coauthors of a paper and its direction models how senior coauthors can influence the research direction of junior coauthors. With our recent advances in hypergraph spectral techniques, we are in an excellent position to pursue the following directions. (1) Investigate the mathematical properties of more general diffusion models. For instance, a formal framework on directed hypergraph diffusion process will shed light on how the directed version of the Laplacian can capture the underlying combinatorial properties. (2) Develop related optimization and approximation algorithms. A hypergraph induces a convex quadratic form, which is the objective to be minimized in mathematical programs for approximating eigenvalues of the Laplacian operator or assigning labels in semi-supervised learning. (3) Employ our framework for practical applications. We will test our models and optimization algorithms on real-world datasets, and compare them with existing methods.
本項目將對超圖(hypergraph)中的擴散過程進行研究,其中每個頂點有權值,且超邊(hyperedge)可以包含任意數量的頂點。在包含於同一個超邊的頂點中,權值將從最大權頂點流向最小權頂點,其速率與權值的差值成正比。我們將研究更通用的超圖擴散模型。這不僅將在譜(超)圖論和凸優化中帶來理論進展,而且還將對半監督學習和市場建模等應用產生實際影響。經典譜圖論把圖的邊擴展性,例如隨機遊走的收斂速度,與拉普拉斯算子的譜特性相關聯。我們的初步研究完善了一篇開創性的STOC 2015論文。該論文研究了(無向)超圖上的擴散過程並定義了超圖拉普拉斯算子。類似於經典結果,拉普拉斯算子的譜特性與超圖的邊擴展性以及擴散過程的收斂速度有關。我們將探索更通用的模型(例如有向超圖)的擴散過程,其中有向超邊由頂點的頭子集指向頂點的尾子集組成。因此,有向超邊可以表達多個元素之間的因果影響關係。例如,在共同作者網絡中,每個有向超邊包含論文的作者們,而超邊的方向表達了資深作者如何影響初級作者的研究方向。憑藉我們在超圖譜方面的最新進展,我們非常適合探求以下方向。 (1)研究更通用的擴散模型的數學性質。例如,關於有向超圖擴散過程的理論框架將揭示有向拉普拉斯算子如何刻劃超圖的潛在組合屬性。 (2)開發相關的優化和近似算法。超圖的凸二次公式作為數學規劃問題中的最小化目標被用於近似拉普拉斯算符的特徵值以及半監督學習中的標籤分配問題。 (3)在實際中應用我們的框架。我們將用現實世界的數據集對我們的模型和優化算法進行測試,並將其與現有方法進行比較。
Research Outcome
Layman's Summary of
Completion Report:
Not yet submitted