Жаңа тәсілмен AI-ды бақылаусыз граф деректерінде үйрету

```html Авторлар: Чжэнь Пэн Вэньбин Хуан Миннань Ло Цинхуа Чжэн Юй Жун Тинъян Сюй Цзюньчжоу Хуан Аннотация Богатство содержания различных информационных сетей, таких как социальные сети и коммуникационные сети, предоставляет беспрецедентный потенциал для обучения высококачественных выразительных представлений без внешнего надзора. В этой статье исследуется, как сохранять и извлекать обильную информацию из данных, структурированных в виде графа, в пространство встраивания в режиме без надзора. Для этого мы предлагаем новую концепцию, графическую взаимную информацию (GMI), для измерения корреляции между входными графами и скрытыми представлениями высокого уровня. GMI обобщает идею традиционных вычислений взаимной информации из векторного пространства в граф, где измерение взаимной информации с двух точек зрения: признаков узлов и топологической структуры, является обязательным. GMI обладает рядом преимуществ: во-первых, он инвариантен к изоморфным преобразованиям входных графов — неизбежному ограничению во многих существующих алгоритмах обучения представлений графов; кроме того, его можно эффективно оценивать и максимизировать с помощью текущих методов оценки взаимной информации, таких как MINE; наконец, наш теоретический анализ подтверждает его корректность и рациональность. С помощью GMI мы разрабатываем модель обучения без надзора, обученную путем максимизации GMI между входом и выходом графового нейронного кодировщика. Обширные эксперименты по трансдуктивной и индуктивной классификации узлов и прогнозированию связей демонстрируют, что наш метод превосходит современные методы без надзора, а иногда даже превосходит методы с надзором. 1 ВВЕДЕНИЕ Для достижения надежного количественного анализа различных информационных сетей обучение высококачественных представлений для данных, структурированных в виде графа, стало одной из самых увлекательных тем современности. Современные методы, направленные на достижение этой цели, обычно категоризируемые как Графовые Нейронные Сети (GNN), добились замечательных успехов во многих обучающих задачах, таких как классификация узлов [ , , ], прогнозирование связей [ , , ], выравнивание графов [ , , ], генерация молекул [ , , ] и другие. Несмотря на плодотворный прогресс, обучение GNN в существующих подходах обычно требует некоторой формы надзора. Несомненно, получение информации для маркировки дорогостояще — ручное аннотирование или оплата разрешения, и даже невозможно из-за политики конфиденциальности. Не говоря уже о том, что надежность предоставленных меток иногда вызывает сомнения. Следовательно, как достичь высококачественного представления графа без надзора, становится необходимым для множества практических случаев, что мотивирует исследование данной статьи. 35 42 50 26 27 49 12 19 43 4 5 46 Тщательно изучив собранные нами графовые данные, мы обнаружили, что они обычно поступают из различных источников, таких как социальные сети, сети цитирования и коммуникационные сети, где существует огромный объем как контентной, так и структурной информации. Например, данные на многих социальных платформах, таких как Twitter, Flickr и Facebook, включают характеристики пользователей, , основные личные данные, тексты, изображения, IP-адреса, и их отношения, , покупка одного и того же товара, наличие друзей. Эти богатые контентные данные достаточны для последующих задач майнинга без дополнительного руководства: если две сущности демонстрируют крайнюю схожесть в признаках, существует высокая вероятность связи между ними (прогнозирование связей), и они, вероятно, принадлежат к одной категории (классификация); если две сущности оба связаны с одной и той же сущностью, они, вероятно, имеют схожие характеристики (рекомендация). В этом смысле сохранение и извлечение максимально возможной информации из информационных сетей в пространство встраивания облегчает обучение высококачественных выразительных представлений, которые демонстрируют желаемую производительность в задачах майнинга без какой-либо формы надзора. Обучение представлений графов без надзора является более предпочтительным выбором во многих случаях благодаря отсутствию необходимости в метках, особенно когда мы намереваемся использовать большие объемы немаркированных данных в реальном мире. например например Чтобы полностью унаследовать богатую информацию в графах, в этой статье мы выполняем встраивание графов на основе максимизации взаимной информации (MI), вдохновленной эмпирическим успехом метода Deep Info-Max [ ], который работает с изображениями. Чтобы обнаружить полезные представления, Deep InfoMax обучает кодировщик максимизировать MI между его входами ( , изображениями) и выходами ( , скрытыми векторами). При рассмотрении Deep InfoMax в графовой области, первый камень, который нам нужно преодолеть, — это как определить MI между графами и скрытыми векторами, в то время как топология графов более сложна, чем у изображений (см. Рисунок Одна из проблем заключается в обеспечении симметричного свойства функции MI между скрытым представлением каждого узла и входными признаками его соседей, или, эквивалентно, инвариантности к перестановкам соседей. В одной из недавних работ, посвященных MI, Deep Graph Infomax (DGI) [ ] сначала встраивает входной граф и соответствующий ему искаженный граф, затем суммирует входной граф в вектор с помощью функции чтения, наконец, максимизирует MI между этим суммарным вектором и скрытыми представлениями, различая входной граф (положительный образец) от искаженного графа (отрицательный образец). Рисунок дает понятный обзор DGI. Максимизация такого рода MI эквивалентна максимизации MI между входными признаками узлов и скрытыми векторами, но это эквивалентность выполняется при нескольких предварительных условиях, , функция чтения должна быть инъективной, что, кажется, чрезмерно ограничено в реальных случаях. Даже если мы можем гарантировать существование инъективной функции чтения путем определенного дизайна, , той, которая используется в DeepSets [ ], инъекционная способность функции чтения также зависит от того, как обучаются ее параметры. Это означает, что изначально инъективная функция все еще рискует стать неинъективной, если она обучается без какого-либо внешнего надзора. И если функция чтения не инъективна, информация входного графа, содержащаяся в суммарном векторе, уменьшится с увеличением размера графа. Более того, DGI остается на уровне грубой максимизации MI на уровне графа/патча. Следовательно, в DGI нет гарантии, что кодировщик сможет извлечь достаточную информацию из входных данных, поскольку он никогда не коррелирует скрытые представления со своими исходными входами. 20 т.е. т.е. 1). 41 1 например например 47 В этой статье мы предлагаем более простой способ рассмотрения MI с точки зрения графических структур, не используя какую-либо функцию чтения и функцию искажения. Мы напрямую выводим MI, сравнивая вход ( , подграф, состоящий из входного соседства) и выход ( , скрытое представление каждого узла) кодировщика. И, что интересно, наши теоретические выводы показывают, что непосредственно сформулированная MI может быть разложена на взвешенную сумму локальных MI между каждым признаком соседа и скрытым вектором. Таким образом, мы разложили входные признаки и сделали вычисление MI управляемым. Кроме того, эта форма MI может легко удовлетворять симметричному свойству, если мы корректируем весовые коэффициенты. Подробнее см. § Поскольку вышеупомянутая MI в основном измеряется на уровне признаков узлов, мы называем ее Feature Mutual Information (FMI). т.е. т.е. 3.1. Остаются два вопроса относительно FMI: весовые коэффициенты сочетания все еще неизвестны, и он не учитывает топологию ( , признаки ребер). Чтобы далее решить эти два вопроса, мы определяем нашу меру Графической Взаимной Информации (GMI) на основе FMI. В частности, GMI применяет интуитивное присвоение значений, устанавливая веса в FMI равными близости между каждым соседом и целевым узлом в пространстве представлений. Чтобы сохранить топологическую информацию, GMI далее коррелирует эти веса с признаками входных ребер с помощью дополнительного члена взаимной информации. Полученная GMI топологически инвариантна и также вычислима с помощью Mutual Information Neural Estimation (MINE) [ ]. Основные вклады нашей работы заключаются в следующем: 1. 2. т.е. 2 • : Мы обобщаем традиционную оценку MI на граф и соответственно предлагаем новую концепцию Графической Взаимной Информации (GMI). GMI свободна от Концепции потенциального риска, вызванного функцией чтения, поскольку она рассматривает MI между входными графами и встраиваниями высокого уровня в простой закономерности. • : Благодаря нашему теоретическому анализу, мы даем управляемую и вычисляемую форму GMI, которая разлагает Алгоритмы общую GMI на взвешенную сумму локальных MI. С помощью метода MINE максимизация GMI может быть легко достигнута на уровне узла. • : Мы проверяем эффективность GMI на нескольких популярных задачах классификации узлов и прогнозирования связей, Экспериментальные результаты включая как трансдуктивные, так и индуктивные. Эксперименты демонстрируют, что наш метод показывает многообещающую производительность на различных эталонных тестах, и он даже иногда превосходит методы с надзором. 2 СВЯЗАННЫЕ РАБОТЫ В соответствии с фокусом нашей работы, мы кратко рассматриваем предыдущие работы в двух следующих областях: оценка взаимной информации, и нейронные сети для обучения представлений на графах. 1. 2. . Поскольку принцип InfoMax [ ] выступает за максимизацию MI между входами и выходами нейронных сетей, многие методы, такие как алгоритмы ICA [ , ], пытаются применить идею MI в обучении признаков без надзора. Тем не менее, эти методы не могут быть легко обобщены на глубокие нейронные сети из-за сложности вычисления MI между высокомерными непрерывными переменными. К счастью, Mutual Information Neural Estimation (MINE) [ ] делает оценку MI на глубоких нейронных сетях возможной путем обучения статистической сети в качестве классификатора для различения образцов, поступающих из совместного распределения, и продукта маргинальных распределений двух случайных переменных. В частности, MINE использует формулировку MI, основанную на точном KL-расстоянии, в то время как альтернатива, не основанная на KL, — дивергенция Йенсена-Шеннона (JSD) [ ], может использоваться без беспокойства о точном значении MI. Оценка взаимной информации 3 1 21 2 30 . С быстрым развитием графовых нейронных сетей (GNN) в последние годы было предложено множество алгоритмов обучения представлений графов на основе GNN, которые демонстрируют более высокую производительность, чем традиционные подходы к встраиванию на основе случайных блужданий и факторизации [ , , , , ]. Как правило, эти методы можно разделить на категории с надзором и без надзора. Среди них существует богатая литература по обучению представлений с надзором на графах [ , , , , ]. Несмотря на их различия в сетевой архитектуре, они достигают эмпирического успеха с помощью меток, которые часто недоступны в реальных сценариях. В этом случае методы обучения графов без надзора [ , , ] имеют более широкий потенциал применения. Известным методом является GraphSAGE [ ], индуктивная структура для обучения GNN с помощью цели, основанной на случайных блужданиях, в его режиме без надзора. И недавно DGI [ ] применяет идею максимизации MI в графовой области и получает сильные результаты в режиме без надзора. Однако DGI реализует крупномасштабную максимизацию ( , максимизацию MI на уровне графа/патча), что затрудняет сохранение тонкой информации во входном графе. Кроме того, условие, наложенное на функцию чтения, используемую в DGI, кажется чрезмерно ограниченным в реальных случаях. В отличие от этого, мы сосредоточены на снятии ограничения функции чтения и достижении максимизации графической взаимной информации на уровне узла путем прямой максимизации MI между входами и выходами кодировщика. Представления, полученные нашим методом, более сложны в сохранении информации входного графа, что обеспечивает их потенциал для последующих задач майнинга графов, , классификации узлов, прогнозирования связей и рекомендаций. Нейронные сети для обучения представлений графов 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 т.е. например 3 ГРАФИЧЕСКАЯ ВЗАИМНАЯ ИНФОРМАЦИЯ: ОПРЕДЕЛЕНИЕ И МАКСИМИЗАЦИЯ Прежде чем перейти дальше, мы сначала приводим предварительные концепции, используемые в этой статье. Пусть G = (V, E) обозначает граф с узлами ∈ V и ребрами = ( , ) ∈ E. Признаки узлов, с предполагаемым эмпирическим распределением вероятностей P, задаются как ∈ N vi eij vi vj X R × = { 1, · · · , }, где ∈ R обозначает признак для узла . Матрица смежности ∈ R × представляет соединения ребер, где , связанный с ребром , может быть действительным числом или многомерным вектором1. N D x x N xi D vi A N N Aij eij Цель обучения представлений графов — научить кодировщик : R × × R × → R × ′, так чтобы скрытые векторы = { 1, · · · , } = ( , ) обозначали представления высокого уровня для всех узлов. Процесс кодирования может быть переписан в поузловом виде. f N D N N N D H h hN f X A Чтобы показать это, мы определяем и для узла как соответственно признаки его соседей и соответствующую матрицу смежности Xi Ai i условную на соседей. В частности, состоит из всех k-hop соседей при ≤ , когда кодировщик является -слойной GNN, и он включает сам узел , если мы дополнительно добавляем петли в матрицу смежности. Здесь мы называем подграф, расширенный и , для узла , обозначаемым G . С определением опорного графа кодирование для каждого узла становится = (G ) = ( , ). Xi vi k l f l i Xi Ai опорным графом i i hi f i f Xi Ai В Deep InfoMax [ ] цель обучения кодировщика заключается в максимизации MI между его входами и выходами. MI оценивается с помощью статистической сети в качестве дискриминатора для классификации образцов, поступающих из совместного распределения, и образцов, извлеченных из произведения маргинальных распределений. Естественно, при адаптации идеи Deep InfoMax к графам мы должны максимизировать MI между представлением и опорным графом G для каждого узла. Мы обозначаем такую графическую MI как ( ; G ). Однако определить I (hi ; Gi ) не так просто. Трудности заключаются в следующем: Трудности в определении графической взаимной информации. 20 hi i I hi i • Графическая MI должна быть инвариантна относительно индекса узла. Другими словами, мы должны иметь ( ; G ) = ( ; G′ ), если G и G′ изоморфны друг другу. I hi i I hi i i i • Если мы используем метод MINE для расчета MI, дискриминатор в MINE принимает только входы фиксированного размера. Это все еще невыполнимо для G , так как разные G обычно включают разное количество узлов и, следовательно, имеют разные размеры. i i Чтобы обойти проблему определения графической взаимной информации, этот раздел начинается с введения концепции Feature Mutual Information (FMI), которая опирается только на признаки узлов. Основываясь на разложении FMI, мы затем определяем Graphical Mutual Information (GMI), которая учитывает как признаки узлов, так и 3.1 Взаимная информация признаков Мы обозначаем эмпирическое распределение вероятностей признаков узлов как ( ), вероятность как ( ), а совместное распределение — ( , ). Согласно теории информации, MI между и определяется как Xi p Xi hi p hi p hi Xi hi Xi Интересно, что у нас есть следующая теорема разложения взаимной информации для вычисления ( ; ). I hi Xi Теорема 1 (Разложение взаимной информации). ( | ) ( ; ) Если условная вероятность p hi Xi является мультипликативной (см. определение мультипликативной в [ ]), глобальная взаимная информация I 36 hi Xi определенная в уравнении (1) может быть разложена на взвешенную сумму локальных MI, а именно, ≤ ≤ 1 где, xj является j-м соседом узла i, in — количество всех элементов в Xi , а весовой коэффициент wij удовлетворяет 1 wij для каждого j. Чтобы доказать вышеуказанную теорему, мы сначала вводим две леммы и одно определение. Лемма 1. Для любых случайных переменных X, Y и Z, мы имеем С разложением в Теореме мы можем вычислить правую часть Уравнения с помощью MINE, так как входы дискриминатора теперь становятся парами ( , ), размер которых всегда остается одинаковым ( , ′-на- ). Кроме того, мы можем регулировать веса, чтобы отразить изоморфное преобразование входных графов. Например, если содержит только однохоповых соседей узла , установка всех весов одинаковыми приведет к одинаковой MI для входных узлов в разном порядке. 1, (2) hi xj т.е. D D Xi i Несмотря на некоторые преимущества разложения, трудно охарактеризовать точные значения весов, поскольку они связаны со значениями ( ; ) и их базовыми распределениями вероятностей. I hi xj Тривиальный способ — установка всех весов равными , затем максимизация правой части Уравнения эквивалентна максимизации нижней границы ( ; ), с помощью которой истинная FMI также максимизируется в некоторой степени. Помимо этого метода, мы дополнительно предоставляем более усовершенствованное решение, рассматривая веса как обучаемые механизмы внимания, что является темой следующего подраздела. 1 (2) I hi Xi Вдохновленные разложением в Теореме мы пытаемся построить обучаемые веса с другой точки зрения графов ( , 3.2 Взаимная информация, учитывающая топологию 1, т.е. топологической точки зрения), чтобы значения могли быть более гибкими и отражать присущие свойства графов. В конечном итоге мы выводим определение Графической Взаимной Информации (GMI). wij Определение 2 (Графическая Взаимная Информация). G = ( , ) MI между скрытым вектором h и его опорным графом X A определяется как где определения как xj, так и in такие же, как в Теореме 1, aij — это вес/признак ребра в матрице смежности A, а σ (·) — сигмоидная функция. Интуитивно, весовой коэффициент wij в первом члене Уравнения (10) измеряет обрабатываются в экспериментах без весов. Формально, мы вычисляем I (wij ; aij ) = aijloдwij + (1 − aij )loд(1 − wij ). (12) Максимизируя I (hi ; Gi ) с суммой Уравнения (11) и Уравнения (12) по всем скрытым векторам H , мы получаем нашу полную целевую функцию для вклад локальной MI в глобальную. Мы реализуем вклад I (hi ; xj ) через сходство между представлениями hi и hj (т.е. wij = σ (hThj )), а член I (wij ; aij ) максимизирует MI между wij и весом/признаком ребра входного графа (т.е. aij ), чтобы заставить wij соответствовать топологическим отношениям. В этом смысле степень вклада будет соответствовать близости в топологической структуре, что общепринято как факт, что wij может быть больше, если узел j "ближе" к узлу i, и меньше в противном случае. Эта стратегия компенсирует недостаток FMI, который фокусируется только на признаках узлов, и позволяет локальным MI вносить адаптивный вклад в глобальный. Чтобы лучше понять идею внимания в этой стратегии, вы можете обратиться к GCN на основе внимания [40]. Обратите внимание, что определение Уравнения (10) применимо к общим случаям. Для определенных конкретных ситуаций мы можем немного изменить Уравнение (10) для эффективности. Например, при работе с невзвешенными графами (т.е. значение ребра равно 1, если оно связано, и 0 в противном случае), мы можем заменить второй член MI I (wij ; aij ) отрицательной кросс-энтропийной функцией потерь. Минимизация кросс-энтропии также способствует максимизации MI и обеспечивает более эффективное вычисление. Подробнее см. следующий раздел. В целом, определение Уравнения (10) имеет несколько преимуществ. Во-первых, этот тип MI инвариантен к изоморфным преобразованиям входных графов. Во-вторых, он вычислительно осуществим, поскольку каждый компонент правой части может быть оценен с помощью MINE. Что еще более важно, GMI мощнее DGI в захвате исходной входной информации благодаря явной корреляции между скрытыми векторами и входными признаками как узлов, так и ребер на мелкозернистом уровне узлов. 3.3 Максимизация GMI Теперь мы напрямую максимизируем правую часть Уравнения с помощью MINE. Обратите внимание, что MINE оценивает нижнюю границу MI с использованием представления Донскера-Варадана (DV) [ ] KL-дивергенции между совместным распределением и произведением маргинальных распределений. Поскольку мы больше сосредоточены на максимизации MI, а не на получении ее конкретного значения, могут быть использованы другие альтернативы, не основанные на KL, такие как оценщик Йенсена-Шеннона MI (JSD) [ ] и оценщик Noise-Contrastive (infoNCE) [ ]. Основываясь на экспериментальных результатах и анализе в [ ], мы прибегаем к оценщику JSD в этой статье для эффективности и действенности, поскольку оценщик infoNCE чувствителен к стратегиям отрицательного выборки (количеству отрицательных выборок), поэтому может стать узким местом для крупномасштабных наборов данных при фиксированной доступной памяти. Напротив, инвариантность оценщика JSD к стратегиям отрицательного выборки и его уважительные результаты во многих задачах делают его более подходящим для нашей задачи. В частности, мы вычисляем ( ; ) в первом члене Уравнения с помощью (10) 10 30 31 20 I hi xj (10) где D : × ′ → R — дискриминатор, построенный нейронной сетью с параметром . — это отрицательный образец, взятый из P = P, а ( ) = (1 + ) обозначает функцию soft-plus. w D D w x j sp x loд ex Как упоминалось в § мы максимизируем ( ; ) путем вычисления его кросс-энтропии вместо использования оценщика JSD, поскольку графы, с которыми мы работали в экспериментах, не взвешены. Формально, мы вычисляем 3.2, I wij aij Максимизируя I (hi ; Gi ) с суммой Уравнения (11) и Уравнения (12) по всем скрытым векторам H , мы получаем нашу полную целевую функцию для оптимизации GMI. Кроме того, мы можем добавить параметры компромисса для балансировки Уравнения (11) и Уравнения (12) для большей гибкости. 4 ЭКСПЕРИМЕНТЫ В этом разделе мы эмпирически оцениваем производительность GMI на двух распространенных задачах: классификация узлов (трандуктивная и индуктивная) и прогнозирование связей. Дополнительное относительно справедливое сравнение GMI с двумя другими алгоритмами без надзора (EP-B и DGI) далее демонстрирует ее эффективность. Также мы представляем визуализацию t-SNE графиков и анализируем влияние глубины модели. 4.1 Наборы данных Для оценки качества нашего подхода в каждой задаче мы используем 4 или 5 общепринятых эталонных наборов данных из предыдущих работ [ , , Подробная статистика приведена в Таблице 16 25 41]. 1. В задаче классификации Cora, Citeseer и PubMed [ ]2 являются сетями цитирования, где узлы соответствуют документам, а ребра представляют собой цитирования. Каждый документ связан с вектором представления мешка слов и принадлежит к одному из предопределенных классов. В соответствии с трансдуктивным сценарием в [ , ], обучение проводится на всех узлах, и 1000 тестовых узлов используются для оценки. Reddit3 — это большая социальная сеть, состоящая из многочисленных взаимосвязанных постов Reddit, созданных в сентябре 2014 года [ ]. Посты рассматриваются как узлы, а ребра означают, что один и тот же пользователь комментирует. 38 25 41 16 ![ Таблица 1: Статистика наборов данных, использованных в экспериментах. ](https://cdn.hack