A connectedness constraint for learning sparse graphs. Sundin, M., Venkitaraman, A., Jansson, M., & Chatterjee, S. In *2017 25th European Signal Processing Conference (EUSIPCO)*, pages 151-155, Aug, 2017.

Paper doi abstract bibtex

Paper doi abstract bibtex

Graphs are naturally sparse objects that are used to study many problems involving networks, for example, distributed learning and graph signal processing. In some cases, the graph is not given, but must be learned from the problem and available data. Often it is desirable to learn sparse graphs. However, making a graph highly sparse can split the graph into several disconnected components, leading to several separate networks. The main difficulty is that connectedness is often treated as a combinatorial property, making it hard to enforce in e.g. convex optimization problems. In this article, we show how connectedness of undirected graphs can be formulated as an analytical property and can be enforced as a convex constraint. We especially show how the constraint relates to the distributed consensus problem and graph Laplacian learning. Using simulated and real data, we perform experiments to learn sparse and connected graphs from data.

@InProceedings{8081187, author = {M. Sundin and A. Venkitaraman and M. Jansson and S. Chatterjee}, booktitle = {2017 25th European Signal Processing Conference (EUSIPCO)}, title = {A connectedness constraint for learning sparse graphs}, year = {2017}, pages = {151-155}, abstract = {Graphs are naturally sparse objects that are used to study many problems involving networks, for example, distributed learning and graph signal processing. In some cases, the graph is not given, but must be learned from the problem and available data. Often it is desirable to learn sparse graphs. However, making a graph highly sparse can split the graph into several disconnected components, leading to several separate networks. The main difficulty is that connectedness is often treated as a combinatorial property, making it hard to enforce in e.g. convex optimization problems. In this article, we show how connectedness of undirected graphs can be formulated as an analytical property and can be enforced as a convex constraint. We especially show how the constraint relates to the distributed consensus problem and graph Laplacian learning. Using simulated and real data, we perform experiments to learn sparse and connected graphs from data.}, keywords = {convex programming;graph theory;learning (artificial intelligence);connectedness constraint;naturally sparse objects;distributed learning;convex optimization problems;undirected graphs;convex constraint;distributed consensus problem;graph Laplacian learning;sparse graph learning;graph signal processing;Laplace equations;Signal processing;Symmetric matrices;Sparse matrices;Optimization;Europe;Eigenvalues and eigenfunctions}, doi = {10.23919/EUSIPCO.2017.8081187}, issn = {2076-1465}, month = {Aug}, url = {https://www.eurasip.org/proceedings/eusipco/eusipco2017/papers/1570345277.pdf}, }

Downloads: 0

{"_id":"7atNQWAY9ebptq3zd","bibbaseid":"sundin-venkitaraman-jansson-chatterjee-aconnectednessconstraintforlearningsparsegraphs-2017","authorIDs":[],"author_short":["Sundin, M.","Venkitaraman, A.","Jansson, M.","Chatterjee, S."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["M."],"propositions":[],"lastnames":["Sundin"],"suffixes":[]},{"firstnames":["A."],"propositions":[],"lastnames":["Venkitaraman"],"suffixes":[]},{"firstnames":["M."],"propositions":[],"lastnames":["Jansson"],"suffixes":[]},{"firstnames":["S."],"propositions":[],"lastnames":["Chatterjee"],"suffixes":[]}],"booktitle":"2017 25th European Signal Processing Conference (EUSIPCO)","title":"A connectedness constraint for learning sparse graphs","year":"2017","pages":"151-155","abstract":"Graphs are naturally sparse objects that are used to study many problems involving networks, for example, distributed learning and graph signal processing. In some cases, the graph is not given, but must be learned from the problem and available data. Often it is desirable to learn sparse graphs. However, making a graph highly sparse can split the graph into several disconnected components, leading to several separate networks. The main difficulty is that connectedness is often treated as a combinatorial property, making it hard to enforce in e.g. convex optimization problems. In this article, we show how connectedness of undirected graphs can be formulated as an analytical property and can be enforced as a convex constraint. We especially show how the constraint relates to the distributed consensus problem and graph Laplacian learning. Using simulated and real data, we perform experiments to learn sparse and connected graphs from data.","keywords":"convex programming;graph theory;learning (artificial intelligence);connectedness constraint;naturally sparse objects;distributed learning;convex optimization problems;undirected graphs;convex constraint;distributed consensus problem;graph Laplacian learning;sparse graph learning;graph signal processing;Laplace equations;Signal processing;Symmetric matrices;Sparse matrices;Optimization;Europe;Eigenvalues and eigenfunctions","doi":"10.23919/EUSIPCO.2017.8081187","issn":"2076-1465","month":"Aug","url":"https://www.eurasip.org/proceedings/eusipco/eusipco2017/papers/1570345277.pdf","bibtex":"@InProceedings{8081187,\n author = {M. Sundin and A. Venkitaraman and M. Jansson and S. Chatterjee},\n booktitle = {2017 25th European Signal Processing Conference (EUSIPCO)},\n title = {A connectedness constraint for learning sparse graphs},\n year = {2017},\n pages = {151-155},\n abstract = {Graphs are naturally sparse objects that are used to study many problems involving networks, for example, distributed learning and graph signal processing. In some cases, the graph is not given, but must be learned from the problem and available data. Often it is desirable to learn sparse graphs. However, making a graph highly sparse can split the graph into several disconnected components, leading to several separate networks. The main difficulty is that connectedness is often treated as a combinatorial property, making it hard to enforce in e.g. convex optimization problems. In this article, we show how connectedness of undirected graphs can be formulated as an analytical property and can be enforced as a convex constraint. We especially show how the constraint relates to the distributed consensus problem and graph Laplacian learning. Using simulated and real data, we perform experiments to learn sparse and connected graphs from data.},\n keywords = {convex programming;graph theory;learning (artificial intelligence);connectedness constraint;naturally sparse objects;distributed learning;convex optimization problems;undirected graphs;convex constraint;distributed consensus problem;graph Laplacian learning;sparse graph learning;graph signal processing;Laplace equations;Signal processing;Symmetric matrices;Sparse matrices;Optimization;Europe;Eigenvalues and eigenfunctions},\n doi = {10.23919/EUSIPCO.2017.8081187},\n issn = {2076-1465},\n month = {Aug},\n url = {https://www.eurasip.org/proceedings/eusipco/eusipco2017/papers/1570345277.pdf},\n}\n\n","author_short":["Sundin, M.","Venkitaraman, A.","Jansson, M.","Chatterjee, S."],"key":"8081187","id":"8081187","bibbaseid":"sundin-venkitaraman-jansson-chatterjee-aconnectednessconstraintforlearningsparsegraphs-2017","role":"author","urls":{"Paper":"https://www.eurasip.org/proceedings/eusipco/eusipco2017/papers/1570345277.pdf"},"keyword":["convex programming;graph theory;learning (artificial intelligence);connectedness constraint;naturally sparse objects;distributed learning;convex optimization problems;undirected graphs;convex constraint;distributed consensus problem;graph Laplacian learning;sparse graph learning;graph signal processing;Laplace equations;Signal processing;Symmetric matrices;Sparse matrices;Optimization;Europe;Eigenvalues and eigenfunctions"],"metadata":{"authorlinks":{}},"downloads":0},"bibtype":"inproceedings","biburl":"https://raw.githubusercontent.com/Roznn/EUSIPCO/main/eusipco2017url.bib","creationDate":"2021-02-13T16:38:25.510Z","downloads":0,"keywords":["convex programming;graph theory;learning (artificial intelligence);connectedness constraint;naturally sparse objects;distributed learning;convex optimization problems;undirected graphs;convex constraint;distributed consensus problem;graph laplacian learning;sparse graph learning;graph signal processing;laplace equations;signal processing;symmetric matrices;sparse matrices;optimization;europe;eigenvalues and eigenfunctions"],"search_terms":["connectedness","constraint","learning","sparse","graphs","sundin","venkitaraman","jansson","chatterjee"],"title":"A connectedness constraint for learning sparse graphs","year":2017,"dataSources":["2MNbFYjMYTD6z7ExY","uP2aT6Qs8sfZJ6s8b"]}