更改

By augmenting a class of hypergraphs with replacement rules, [[graph grammar]]s can be generalised to allow hyperedges.

By augmenting a class of hypergraphs with replacement rules, [[graph grammar]]s can be generalised to allow hyperedges.

==Generalizations==  刘世康

== Generalizations ==   

One possible generalization of a hypergraph is to allow edges to point at other edges. There are two variations of this generalization. In one, the edges consist not only of a set of vertices, but may also contain subsets of vertices, subsets of subsets of vertices and so on ''ad infinitum''. In essence, every edge is just an internal node of a tree or [[directed acyclic graph]], and vertices are the leaf nodes. A hypergraph is then just a collection of trees with common, shared nodes (that is, a given internal node or leaf may occur in several different trees). Conversely, every collection of trees can be understood as this generalized hypergraph. Since trees are widely used throughout [[computer science]] and many other branches of mathematics, one could say that hypergraphs appear naturally as well. So, for example, this generalization arises naturally as a model of [[term algebra]]; edges correspond to [[term (logic)|terms]] and vertices correspond to constants or variables.

One possible generalization of a hypergraph is to allow edges to point at other edges. There are two variations of this generalization. In one, the edges consist not only of a set of vertices, but may also contain subsets of vertices, subsets of subsets of vertices and so on ''ad infinitum''. In essence, every edge is just an internal node of a tree or [[directed acyclic graph]], and vertices are the leaf nodes. A hypergraph is then just a collection of trees with common, shared nodes (that is, a given internal node or leaf may occur in several different trees). Conversely, every collection of trees can be understood as this generalized hypergraph. Since trees are widely used throughout [[computer science]] and many other branches of mathematics, one could say that hypergraphs appear naturally as well. So, for example, this generalization arises naturally as a model of [[term algebra]]; edges correspond to [[term (logic)|terms]] and vertices correspond to constants or variables.

:<math>\left[ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right].</math>

:<math>\left[ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right].</math>

==Hypergraph learning==  刘世康

==Hypergraph learning==   

 

Hypergraphs have been extensively used in [[machine learning]] tasks as the data model and classifier [[regularization (mathematics)]].<ref>{{citation| last1 = Zhou | first1 = Dengyong| last2 = Huang | first2 = Jiayuan | last3=Scholkopf | first3=Bernhard| issue = 2| journal = Advances in Neural Information Processing Systems| pages = 1601–1608| title = Learning with hypergraphs: clustering, classification, and embedding| year = 2006}}</ref> The applications include [[recommender system]] (communities as hyperedges),<ref>{{citation|last1=Tan | first1=Shulong | last2=Bu | first2=Jiajun | last3=Chen | first3=Chun | last4=Xu | first4=Bin | last5=Wang | first5=Can | last6=He | first6=Xiaofei|issue = 1| journal = ACM Transactions on Multimedia Computing, Communications, and Applications| title = Using rich social media information for music recommendation via hypergraph model| year = 2013|url=https://www.researchgate.net/publication/226075153| bibcode=2011smma.book..213T }}</ref> [[image retrieval]] (correlations as hyperedges),<ref>{{citation|last1=Liu | first1=Qingshan | last2=Huang | first2=Yuchi | last3=Metaxas | first3=Dimitris N. |issue = 10–11| journal = Pattern Recognition| title = Hypergraph with sampling for image retrieval| pages=2255–2262| year = 2013| doi=10.1016/j.patcog.2010.07.014 | volume=44}}</ref> and [[bioinformatics]] (biochemical interactions as hyperedges).<ref>{{citation|last1=Patro |first1=Rob | last2=Kingsoford | first2=Carl| issue = 10–11| journal = Bioinformatics| title = Predicting protein interactions via parsimonious network history inference| year = 2013| pages=237–246|doi=10.1093/bioinformatics/btt224 |pmid=23812989 |pmc=3694678 | volume=29}}</ref> Representative hypergraph learning techniques include hypergraph [[spectral clustering]] that extends the [[spectral graph theory]] with hypergraph Laplacian,<ref>{{citation|last1=Gao | first1=Tue | last2=Wang | first2=Meng | last3=Zha|first3=Zheng-Jun|last4=Shen|first4=Jialie|last5=Li|first5=Xuelong|last6=Wu|first6=Xindong|issue = 1| journal = IEEE Transactions on Image Processing| volume=22 | title = Visual-textual joint relevance learning for tag-based social image search| year = 2013| pages=363–376|url=http://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=2510&context=sis_research | doi=10.1109/tip.2012.2202676| pmid=22692911 | bibcode=2013ITIP...22..363Y }}</ref> and hypergraph [[semi-supervised learning]] that introduces extra hypergraph structural cost to restrict the learning results.<ref>{{citation|last1=Tian|first1=Ze|last2=Hwang|first2=TaeHyun|last3=Kuang|first3=Rui|issue = 21| journal = Bioinformatics| title = A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge| year = 2009| pages=2831–2838|doi=10.1093/bioinformatics/btp467|pmid=19648139| volume=25|doi-access=free}}</ref> For large scale hypergraphs, a distributed framework<ref name=hyperx /> built using [[Apache Spark]] is also available.

Hypergraphs have been extensively used in [[machine learning]] tasks as the data model and classifier [[regularization (mathematics)]].<ref>{{citation| last1 = Zhou | first1 = Dengyong| last2 = Huang | first2 = Jiayuan | last3=Scholkopf | first3=Bernhard| issue = 2| journal = Advances in Neural Information Processing Systems| pages = 1601–1608| title = Learning with hypergraphs: clustering, classification, and embedding| year = 2006}}</ref> The applications include [[recommender system]] (communities as hyperedges),<ref>{{citation|last1=Tan | first1=Shulong | last2=Bu | first2=Jiajun | last3=Chen | first3=Chun | last4=Xu | first4=Bin | last5=Wang | first5=Can | last6=He | first6=Xiaofei|issue = 1| journal = ACM Transactions on Multimedia Computing, Communications, and Applications| title = Using rich social media information for music recommendation via hypergraph model| year = 2013|url=https://www.researchgate.net/publication/226075153| bibcode=2011smma.book..213T }}</ref> [[image retrieval]] (correlations as hyperedges),<ref>{{citation|last1=Liu | first1=Qingshan | last2=Huang | first2=Yuchi | last3=Metaxas | first3=Dimitris N. |issue = 10–11| journal = Pattern Recognition| title = Hypergraph with sampling for image retrieval| pages=2255–2262| year = 2013| doi=10.1016/j.patcog.2010.07.014 | volume=44}}</ref> and [[bioinformatics]] (biochemical interactions as hyperedges).<ref>{{citation|last1=Patro |first1=Rob | last2=Kingsoford | first2=Carl| issue = 10–11| journal = Bioinformatics| title = Predicting protein interactions via parsimonious network history inference| year = 2013| pages=237–246|doi=10.1093/bioinformatics/btt224 |pmid=23812989 |pmc=3694678 | volume=29}}</ref> Representative hypergraph learning techniques include hypergraph [[spectral clustering]] that extends the [[spectral graph theory]] with hypergraph Laplacian,<ref>{{citation|last1=Gao | first1=Tue | last2=Wang | first2=Meng | last3=Zha|first3=Zheng-Jun|last4=Shen|first4=Jialie|last5=Li|first5=Xuelong|last6=Wu|first6=Xindong|issue = 1| journal = IEEE Transactions on Image Processing| volume=22 | title = Visual-textual joint relevance learning for tag-based social image search| year = 2013| pages=363–376|url=http://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=2510&context=sis_research | doi=10.1109/tip.2012.2202676| pmid=22692911 | bibcode=2013ITIP...22..363Y }}</ref> and hypergraph [[semi-supervised learning]] that introduces extra hypergraph structural cost to restrict the learning results.<ref>{{citation|last1=Tian|first1=Ze|last2=Hwang|first2=TaeHyun|last3=Kuang|first3=Rui|issue = 21| journal = Bioinformatics| title = A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge| year = 2009| pages=2831–2838|doi=10.1093/bioinformatics/btp467|pmid=19648139| volume=25|doi-access=free}}</ref> For large scale hypergraphs, a distributed framework<ref name=hyperx /> built using [[Apache Spark]] is also available.