Higher order learning with graphs

By Sameer Agarwal, Kristin Branson, Serge J. Belongie. International Conference on Machine Learning, 2006

455 citations recorded by the source corpus.

Recently there has been considerable interest in learning with higher order relations (i.e., three-way or higher) in the unsupervised and semi-supervised settings. Hypergraphs and tensors have been proposed as the natural way of representing these relations and their corresponding algebra as the natural tools for operating on them. In this paper we argue that hypergraphs are not a natural representation for higher order relations, indeed pairwise as well as higher order relations can be handled using graphs. We show that various formulations of the semi-supervised and the unsupervised learning problem on hypergraphs result in the same graph theoretic problem and can be analyzed using existing tools.

Subfields: Artificial Intelligence, Computational Mathematics

View Paper: https://www.semanticscholar.org/paper/75ba42e0df0731fcd7a1578a3b16e800f02786e5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mathematics

Citations in the corpus

Hypergraph spectral learning for multi-label classification (2008, methodology): “Results also show that three different similarity matrices S lead to the similar performance, which is consistent with the theoretical analysis in [1].”
Hypergraph Convolution and Hypergraph Attention (2019, background): “It is easy to prove that the maximum eigenvalue of D − 1 / 2 HWB − 1 H T D − 1 / 2 is no larger than 1 , which stems from a fact (Agarwal et al., 2006) that I − D − 1 / 2 HWB − 1 H T D − 1 / 2 is a positive semi-deﬁnite matrix.”
Learning on Weighted Hypergraphs to Integrate Protein Interactions and Gene Expressions for Cancer Outcome Prediction (2008, unknown): “The HyperGene algorithm is a natural extension of label propagation algorithms on hypergraphs [2, 1, 22].”
Spectral Curvature Clustering (SCC) (2009, methodology): “…address the clustering part and then use its output to estimate the parameters of the underlying flats (see e.g., Multi-way Clustering algorithms (Agarwal et al. 2005, 2006; Govindu 2005; Shashua et al. 2006), Tensor Voting (Medioni et al. 2000), k-Manifolds (Souvenir and Pless 2005), Grassmann…”
Next-item Recommendation with Sequential Hypergraphs (2020, methodology): “To capture these changes in item semantics, we propose to model such short-term item correlations in a hypergraph [1, 11], in which each hyperedge can connect multiple nodes on a single edge.”
Music recommendation by unified hypergraph: combining social media information and music content (2010, methodology): “Our work is also related to graph-based ranking and hypergraph learning [45, 2, 3, 44, 12, 35, 7].”
HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs (2018, methodology): “We compared HyperGCN, 1-HyperGCN and FastHyperGCN against the following baselines: • Hypergraph neural networks (HGNN) [17] uses the clique expansion [52, 1] to approximate the hypergraph.”
Spectral Graph Reduction for Efficient Image and Streaming Video Segmentation (2014, background): “Clique expansion [1] yields a possible mathematical formulation:”
Networks beyond pairwise interactions: structure and dynamics (2020, background): “This generalizes a result already found in [327] for k-uniform hypergraphs.”
HGNN+: General Hypergraph Neural Networks (2022, methodology): “…the hyper-graph incidence matrix cannot being directly handled by the graph neural network [2], two commonly used hyper-graph expansion methods [33], [45], i.e., unweighted clique expansion and weighted clique expansion, are employed to transfer the hypergraph structure into the simple graph…”
Adaptive Hypergraph Learning and its Application in Image Classification (2012, unknown): “It has been verified in [19] that the aforementioned methods are close to each other.”
Laplacian Sparse Coding, Hypergraph Laplacian Sparse Coding, and Applications (2013, background): “Then, the unnormalized Hyperlaplacian matrix [38], [37] is defined as follows:”