Ядро графа
В анализе структур ядро графа — это функция ядра , которая вычисляет внутренний продукт на графах . [1] Ядра графов можно интуитивно понимать как функции, измеряющие сходство пар графов. Они позволяют алгоритмам обучения с использованием ядра, таким как машины опорных векторов , работать непосредственно с графами без необходимости извлечения признаков фиксированной длины с действительными значениями для преобразования их в векторы признаков . Они находят применение в биоинформатике , в хемоинформатике (как разновидность ядер молекул [2] ), и в анализе социальных сетей . [1]
Концепции ядер графов существуют с 1999 года, когда Д. Хаусслер [3] ввел сверточные ядра на дискретных структурах. Термин «ядро графа» был более официально введен в 2002 году Р.И. Кондором и Дж. Лафферти. [4] в качестве ядер на графах, т.е. функций подобия между узлами одного графа, с Всемирной паутины графом гиперссылок в качестве предлагаемого приложения. В 2003 году Гертнер и др. [5] и Касима и др. [6] определенные ядра между графами. В 2010 году Вишванатан и др. дали их единую основу. [1] В 2018 году Гош и др. [7] описал историю ядер графов и их эволюцию за два десятилетия.
Приложения
[ редактировать ]Было показано, что ядро маргинального графа позволяет точно прогнозировать энергию атомизации небольших органических молекул. [8]
Примеры ядер
[ редактировать ]Примером ядра между графами является ядро случайного блуждания , [5] [6] который концептуально выполняет случайные обходы двух графов одновременно, а затем подсчитывает количество путей , созданных обоими обходами. Это эквивалентно случайному блужданию по прямому произведению пары графов, и на основе этого можно получить ядро, которое можно эффективно вычислить. [1]
Другой пример - ядро графа Вейсфейлера-Лемана. [9] который вычисляет несколько раундов алгоритма Вейсфейлера-Лемана, а затем вычисляет сходство двух графиков как внутреннее произведение векторов гистограмм обоих графов. В этих векторах гистограмм ядро собирает количество раз, когда цвет встречается на графике на каждой итерации. Обратите внимание, что ядро Вейсфейлера-Лемана теоретически имеет бесконечную размерность, поскольку число возможных цветов, присваиваемых алгоритмом Вейсфейлера-Лемана, бесконечно. Если ограничиться цветами, которые присутствуют на обоих графиках, вычисление по-прежнему возможно.
См. также
[ редактировать ]- Ядро дерева , как частный случай нециклических графов
- Молекулярный майнинг , как частный случай небольших многометочных графов
Ссылки
[ редактировать ]- ^ Jump up to: а б с д СВН Вишванатан; Никол Н. Шраудольф; Риси Кондор; Карстен М. Боргвардт (2010). «Ядра графа» (PDF) . Журнал исследований машинного обучения . 11 : 1201–1242.
- ^ Л. Ралайвола; С. Дж. Свамидасс; Х. Сайго; П. Балди (2005). «Ядра графов для химической информатики». Нейронные сети . 18 (8): 1093–1110. дои : 10.1016/j.neunet.2005.07.009 . ПМИД 16157471 .
- ^ Хаусслер, Дэвид (1999). Ядра свертки на дискретных структурах . CiteSeerX 10.1.1.110.638 .
- ^ Ризи Имре Кондор; Джон Лафферти (2002). Диффузионные ядра в графах и других пространствах дискретного ввода (PDF) . Учеб. Международная конференция. по машинному обучению (ICML).
- ^ Jump up to: а б Томас Гертнер; Питер А. Флах; Стефан Вробель (2003). О ядрах графов: результаты твердости и эффективные альтернативы . Учеб. 16-я ежегодная конференция по теории вычислительного обучения (COLT) и 7-й семинар по ядру. дои : 10.1007/978-3-540-45167-9_11 .
- ^ Jump up to: а б Хисаси Касима; Кодзи Цуда; Акихиро Инокучи (2003). Маргинализированные ядра между помеченными графами (PDF) . Учеб. 20-я Международная конференция по машинному обучению (ICML).
- ^ Гош, Сварненду; Дас, Нибаран; Гонсалвес, Тереза; Куарежма, Пауло; Кунду, Махантапас (2018). «Путешествие ядер графов через два десятилетия». Обзор компьютерных наук . 27 : 88–111. дои : 10.1016/j.cosrev.2017.11.002 .
- ^ Ю-Ханг Тан; Вибе А. де Йонг (2019). «Прогнозирование энергии атомизации с использованием ядра графа и активного обучения». Журнал химической физики . 150 (4): 044107. arXiv : 1810.07310 . Бибкод : 2019JChPh.150d4107T . дои : 10.1063/1.5078640 . ПМИД 30709286 .
- ^ Шервашидзе, Нино и др. «Ядра графа Вейсфейлера-Лемана». Журнал исследований машинного обучения 12.9 (2011).
 | Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее . |