Слияние кода завершено, страница обновится автоматически
Python-пакет graphkit-learn: описание и использование
graphkit-learn — это пакет Python для работы с графовыми ядрами, расстояниями редактирования графов и задачей прообраза графа.
Требования:
Как использовать?
Установка библиотеки:
$ pip install graphkit-learn
$ git clone https://github.com/jajupmochi/graphkit-learn.git
$ cd graphkit-learn/
$ python setup.py install
Запуск теста: Для проверки корректности работы библиотеки выполните серию тестов:
$ pip install -U pip pytest codecov coverage pytest-cov
$ pytest -v --cov-config=.coveragerc --cov-report term --cov=gklearn gklearn/tests/
Проверка примеров:
Примеры использования библиотеки доступны на Google Colab и в папке example.
Другие демонстрации:
В каталоге notebooks можно найти дополнительные демонстрации:
notebooks представлены тестовые коды графовых ядер на основе линейных паттернов;notebooks/tests находятся коды, проверяющие некоторые библиотеки и функции;notebooks/utils содержатся полезные инструменты, такие как проверка матрицы Грамма и функция для получения свойств наборов данных;notebooks/else содержит другие коды, используемые для экспериментов.Документация: Документация по библиотеке доступна здесь.
Основное содержание: Пакет предоставляет список графовых ядер:
kernel [4]
Структурное ядро кратчайшего пути The structural shortest path kernel [5].
Ядро пути до длины h The path kernel up to length h [6]:
Нелинейные ядра:
ядро treelet The treelet kernel [10];
ядро Weisfeiler-Lehman The Weisfeiler-Lehman kernel [11]:
Демонстрация расчёта ядер графа доступна на Google Colab и в папке examples.
2. Расстояния редактирования графа
3. Методы пред-образа графа
Демонстрацию генерации пред-образов графа можно найти на Google Colab и в папке examples.
4. Интерфейс к GEDLIB
GEDLIB — это легко расширяемая библиотека C++ для (субоптимального) вычисления расстояния редактирования графа между атрибутированными графами. В этой библиотеке интегрирован интерфейс Python для GEDLIB, основанный на библиотеке gedlibpy.
5. Методы оптимизации вычислений
multiprocessing.Pool применяется для распараллеливания вычислений всех ядер, а также выбора модели.Эта библиотека использует функцию multiprocessing.Pool.imap_unordered для распараллеливания, которая может не работать корректно в системе Windows. На данный момент пользователям Windows может потребоваться закомментировать параллельные коды и раскомментировать коды ниже них, которые выполняются последовательно. Мы рассмотрим возможность добавления параметра для управления последовательными или параллельными вычислениями по мере необходимости.
Некоторые модули (например, Numpy, Scipy, sklearn) применяют OpenBLAS для выполнения параллельных вычислений по умолчанию, что вызывает конфликты с другими модулями распараллеливания, такими как multiprossing.Pool, значительно увеличивая время вычислений. Установив его поток равным 1, OpenBLAS вынужден использовать один поток/CPU, что позволяет избежать конфликтов. На данный момент эту процедуру необходимо выполнять вручную. В Linux введите эту команду в терминале перед запуском кода:
$ export OPENBLAS_NUM_THREADS=1
Или добавьте export OPENBLAS_NUM_THREADS=1 в конец вашего файла ~/.bashrc, затем выполните:
$ source ~/.bashrc
чтобы сделать это эффективным навсегда.
Подробное описание ядер графа и экспериментальных результатов см. в статье:
Linlin Jia, Benoit Gaüzère, and Paul Honeine. Graph Kernels Based on Linear Patterns: Theoretical and Experimental Comparisons. working paper or preprint, March 2019. URL https://hal-normandie-univ.archives-ouvertes.fr/hal-02053946.
Сравнение производительности ядер графа на эталонных наборах данных можно найти здесь.
Разветвите библиотеку и откройте запрос на вытягивание! Сделайте свой собственный вклад в сообщество!
Если вы использовали graphkit-learn в своей публикации, пожалуйста, процитируйте следующую статью:
@article{JIA2021,
title = "graphkit-learn: A Python Library for Graph Kernels Based on Linear Patterns",
journal = "Pattern Recognition Letters",
year = "2021",
issn = "0167-8655",
doi = "https://doi.org/10.1016/j.patrec.2021.01.003",
url = "http://www.sciencedirect.com/science/article/pii/S0167865521000131",
author = "Linlin Jia and Benoit Gaüzère and Paul Honeine",
keywords = "Графовые ядра, линейные паттерны, реализация на Python",
abstract = "В данной статье представлена graphkit-learn — первая библиотека Python для эффективного вычисления графовых ядер на основе линейных паттернов, способная работать с различными типами графов. Графовые ядра на основе линейных паттернов тщательно реализованы, каждое со своими специфическими методами вычислений, а также представлены два хорошо известных графовых ядра на основе нелинейных паттернов для сравнительного анализа. Поскольку вычислительная сложность является ахиллесовой пятой графовых ядер, мы предлагаем несколько стратегий для решения этой критической проблемы, включая параллелизацию, структуру данных trie и метод FCSP, который мы расширяем для других ядер и сравнения рёбер. Все предложенные стратегии экономят порядки величин времени вычислений и использования памяти. Более того, все графовые ядра можно просто вычислить с помощью одного оператора Python, что делает их привлекательными для исследователей и практиков. Для удобства использования предоставляется усовершенствованная процедура выбора модели как для задач регрессии, так и для классификации. Эксперименты на синтезированных наборах данных и 11 реальных наборах данных показывают актуальность предложенной библиотеки."
}
БЛАГОДАРНОСТИ
Это исследование было поддержано CSC (China Scholarship Council) и французским национальным исследовательским агентством (ANR) в рамках гранта APi (ANR-18-CE23-0014). Авторы хотели бы поблагодарить CRIANN (Le Centre Régional Informatique et d’Applications Numériques de Normandie) за предоставление вычислительных ресурсов.
ЛИТЕРАТУРА
[1] Thomas Gärtner, Peter Flach, и Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. Learning Theory and Kernel Machines, страницы 129–143, 2003.
[2] H. Kashima, K. Tsuda, и A. Inokuchi. Marginalized kernels between labeled graphs. В Proceedings of the 20th International Conference on Machine Learning, Вашингтон, округ Колумбия, США, 2003 г.
[3] Vishwanathan, S.V.N., Schraudolph, N.N., Kondor, R., Borgwardt, K.M., 2010. Graph kernels. Journal of Machine Learning Research 11, 1201–1242.
[4] K. M. Borgwardt и H.-P. Kriegel. Shortest-path kernels on graphs. В Proceedings of the International Conference on Data Mining, страницы 74–81, 2005.
[5] Liva Ralaivola, Sanjay J Swamidass, Hiroto Saigo, и Pierre Baldi. Graph kernels for chemical informatics. Neural networks, 18(8):1093–1110, 2005.
[6] Suard F, Rakotomamonjy A, Bensrhair A. Kernel on Bag of Paths For Measuring Similarity of Shapes. В ESANN 2007 Apr 25 (стр. 355–360).
[7] Mahé, P., Ueda, N., Akutsu, T., Perret, J.L., Vert, J.P., 2004. Extensions of marginalized graph kernels, в: Proc. the twenty-first international conference on Machine learning, ACM. стр. 70.
[8] Lifan Xu, Wei Wang, M Alvarez, John Cavazos, и Dongping Zhang. Parallelization of shortest path graph kernels on multi-core cpus and gpus. Proceedings of the Programmability Issues for Heterogeneous Multicores (MultiProg), Вена, Австрия, 2014 г.
[9] Edward Fredkin. Trie memory. Communications of the ACM, 3(9):490–499, 1960.
[10] Gaüzere, B., Brun, L., Villemin, D., 2012. Two new graphs kernels in chemoinformatics. Pattern Recognition Letters 33, 2038–2047.
[11] Shervashidze, N., Schweitzer, P., Leeuwen, E.J.v., Mehlhorn, K., Borgwardt, K.M., 2011. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research 12, 2539–2561.
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Комментарии ( 0 )